Лекция 2. Мат. модель. Системы переходов. Системы с синхронным и асинхронным обменом сообщениями_ ..., страница 3
Описание файла
PDF-файл из архива "Лекция 2. Мат. модель. Системы переходов. Системы с синхронным и асинхронным обменом сообщениями_ ...", который расположен в категории "". Всё это находится в предмете "распределенные алгоритмы" из 10 семестр (2 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 3 страницы из PDF
Êàêèå åùå âûïîëíåíèÿ âîçìîæíû äëÿ ýòîéðàñïðåäåëåííîé ñèñòåìû?2. Åñëè äðóãèå âûïîëíåíèÿ åñòü, òî íàñêîëüêî çíà÷èòåëüíîîíè îòëè÷àþòñÿ îò äðóã îò äðóãà?Ñèñòåìû ñ àñèíõðîííîé ñâÿçüþ.Çàìå÷àíèÿIÂíóòðåííåå ñîáûòèå e = (c, d) ïðîöåññà p äîïóñòèìî âêîíôèãóðàöèè γ = (cp , . . . , cp , . . . , cp , M) , åñëè cp = c .Òîãäà e(γ) = (cp , . .
. , d, . . . , cp , M) .11NNÑèñòåìû ñ àñèíõðîííîé ñâÿçüþ.Çàìå÷àíèÿIÂíóòðåííåå ñîáûòèå e = (c, d) ïðîöåññà p äîïóñòèìî âêîíôèãóðàöèè γ = (cp , . . . , cp , . . . , cp , M) , åñëè cp = c .Òîãäà e(γ) = (cp , . . . , d, . . . , cp , M) .Ñîáûòèå e = (c, m, d) îòïðàâëåíèÿ ñîîáùåíèÿ ïðîöåññîìp äîïóñòèìî â êîíôèãóðàöèèγ = (cp , . .
. , cp , . . . , cp , M) , åñëè cp = c . Òîãäàe(γ) = (cp , . . . , d, . . . , cp , M ∪ {m}) .1N1I1NN1NÑèñòåìû ñ àñèíõðîííîé ñâÿçüþ.Çàìå÷àíèÿIÂíóòðåííåå ñîáûòèå e = (c, d) ïðîöåññà p äîïóñòèìî âêîíôèãóðàöèè γ = (cp , . . . , cp , . . . , cp , M) , åñëè cp = c .Òîãäà e(γ) = (cp , . . . , d, . . . , cp , M) .Ñîáûòèå e = (c, m, d) îòïðàâëåíèÿ ñîîáùåíèÿ ïðîöåññîìp äîïóñòèìî â êîíôèãóðàöèèγ = (cp , . . .
, cp , . . . , cp , M) , åñëè cp = c . Òîãäàe(γ) = (cp , . . . , d, . . . , cp , M ∪ {m}) .Ñîáûòèå e = (c, m, d) ïðèåìà ñîîáùåíèÿ ïðîöåññîì päîïóñòèìî â êîíôèãóðàöèè γ = (cp , . . . , cp , . . . , cp , M) ,åñëè cp = c , m ∈ M . Òîãäàe(γ) = (cp , . . . , d, . . . , cp , M \ {m}) .1N1I1NN1IN11NNÑèñòåìû ñ àñèíõðîííîé ñâÿçüþ.Çàìå÷àíèÿÂíóòðåííåå ñîáûòèå e = (c, d) ïðîöåññà p äîïóñòèìî âêîíôèãóðàöèè γ = (cp , . . . , cp , . .
. , cp , M) , åñëè cp = c .Òîãäà e(γ) = (cp , . . . , d, . . . , cp , M) .I Ñîáûòèå e = (c, m, d) îòïðàâëåíèÿ ñîîáùåíèÿ ïðîöåññîìp äîïóñòèìî â êîíôèãóðàöèèγ = (cp , . . . , cp , . . . , cp , M) , åñëè cp = c . Òîãäàe(γ) = (cp , . .
. , d, . . . , cp , M ∪ {m}) .I Ñîáûòèå e = (c, m, d) ïðèåìà ñîîáùåíèÿ ïðîöåññîì päîïóñòèìî â êîíôèãóðàöèè γ = (cp , . . . , cp , . . . , cp , M) ,åñëè cp = c , m ∈ M . Òîãäàe(γ) = (cp , . . . , d, . . . , cp , M \ {m}) .Ñîãëàøåíèå: äëÿ êàæäîãî ñîîáùåíèÿ èìååòñÿ åäèíñòâåííûéïðîöåññ , êîòîðûé ìîæåò ïîëó÷àòü ýòî ñîîáùåíèå. Ýòîòïðîöåññ áóäåì íàçûâàòü àäðåñàòîì äàííîãî ñîîáùåíèÿ.I1N11NN1N11NNÑèñòåìû ñ ñèíõðîííîé ñâÿçüþ.Îáìåí ñîîáùåíèÿìè íàçûâàåòñÿ ñèíõðîííûì , åñëè ñîáûòèåîòïðàâëåíèÿ ñîîáùåíèÿ è ñîîòâåòñòâóþùåå åìó ñîáûòèåïðèåìà ñîîáùåíèÿ ñîãëàñîâàíû òàê, ÷òî îáðàçóþò åäèíûéïåðåõîä â ñèñòåìå. Èíà÷å ãîâîðÿ, ïðîöåññó íå äîçâîëåíîîòïðàâëÿòü ñîîáùåíèå äî òåõ ïîð, ïîêà àäðåñàò ýòîãîñîîáùåíèÿ íå áóäåò ãîòîâ ê åãî ïðèåìó.Ñèñòåìû ñ ñèíõðîííîé ñâÿçüþ.Îáìåí ñîîáùåíèÿìè íàçûâàåòñÿ ñèíõðîííûì , åñëè ñîáûòèåîòïðàâëåíèÿ ñîîáùåíèÿ è ñîîòâåòñòâóþùåå åìó ñîáûòèåïðèåìà ñîîáùåíèÿ ñîãëàñîâàíû òàê, ÷òî îáðàçóþò åäèíûéïåðåõîä â ñèñòåìå.
Èíà÷å ãîâîðÿ, ïðîöåññó íå äîçâîëåíîîòïðàâëÿòü ñîîáùåíèå äî òåõ ïîð, ïîêà àäðåñàò ýòîãîñîîáùåíèÿ íå áóäåò ãîòîâ ê åãî ïðèåìó. ñîîòâåòñòâèè ñ ýòèì ïåðåõîäû â ñèñòåìå ðàçäåëÿþòñÿ íà äâàòèïà: ïåðåõîäû ïåðâîãî òèïà ñâÿçàíû ñ èçìåíåíèåì âíóòðåííèõñîñòîÿíèé ïðîöåññà, à ïåðåõîäû âòîðîãî òèïà ñâÿçàíû ñêîìáèíèðîâàííûì îñóùåñòâëåíèåì ñîáûòèéîòïðàâëåíèÿ-ïðèåìà ñîîáùåíèÿ äâóìÿ ïðîöåññàìè.Ñèñòåìû ñ ñèíõðîííîé ñâÿçüþ.Îïðåäåëåíèå 7.Ïóñòü çàäàíî ñåìåéñòâî ïðîöåññîâ P = {p1, . . . , pN } . Òîãäàñèñòåìà ïåðåõîäîâ ñèíõðîííî ñâÿçàííûõ ïðîöåññîâS = (C, →, I)òàêîâà:Ñèñòåìû ñ ñèíõðîííîé ñâÿçüþ.Îïðåäåëåíèå 7.Ïóñòü çàäàíî ñåìåéñòâî ïðîöåññîâ P = {p1, .
. . , pN } . Òîãäàñèñòåìà ïåðåõîäîâ ñèíõðîííî ñâÿçàííûõ ïðîöåññîâS = (C, →, I)1.òàêîâà:C = {(cp1 , . . . , cpN ) : ∀p ∈ P : cp ∈ Zp }.Ñèñòåìû ñ ñèíõðîííîé ñâÿçüþ.Îïðåäåëåíèå 7.Ïóñòü çàäàíî ñåìåéñòâî ïðîöåññîâ P = {p1, . . . , pN } . Òîãäàñèñòåìà ïåðåõîäîâ ñèíõðîííî ñâÿçàííûõ ïðîöåññîâS = (C, →, I)1.2.òàêîâà:., ãäåC = {(cp1 , . .
. , cpN ) : ∀p ∈ P : cp ∈ Zp }→ = (∪p∈P →p ) ∪ (∪p,q∈P: p6=q →pq )Ñèñòåìû ñ ñèíõðîííîé ñâÿçüþ.Îïðåäåëåíèå 7.Ïóñòü çàäàíî ñåìåéñòâî ïðîöåññîâ P = {p1, . . . , pN } . Òîãäàñèñòåìà ïåðåõîäîâ ñèíõðîííî ñâÿçàííûõ ïðîöåññîâS = (C, →, I)1.2.òàêîâà:., ãäåC = {(cp1 , . . . , cpN ) : ∀p ∈ P : cp ∈ Zp }→ = (∪p∈P →p ) ∪ (∪p,q∈P: p6=q →pq )I→pi ïðåäñòàâëÿåò ñîáîé ìíîæåñòâî ïàð(cp1 , . . . , cpi , . . . , cpN ), (cp1 , .
. . , cp0 i , . . . , cpN ),0iäëÿ êîòîðûõ (cpi , cp ) ∈ `p ;iiÑèñòåìû ñ ñèíõðîííîé ñâÿçüþ.Îïðåäåëåíèå 7.Ïóñòü çàäàíî ñåìåéñòâî ïðîöåññîâ P = {p1, . . . , pN } . Òîãäàñèñòåìà ïåðåõîäîâ ñèíõðîííî ñâÿçàííûõ ïðîöåññîâS = (C, →, I)1.2.òàêîâà:., ãäåC = {(cp1 , . . . , cpN ) : ∀p ∈ P : cp ∈ Zp }→ = (∪p∈P →p ) ∪ (∪p,q∈P: p6=q →pq )II→pi ïðåäñòàâëÿåò ñîáîé ìíîæåñòâî ïàð(cp1 , . .
. , cpi , . . . , cpN ), (cp1 , . . . , cp0 i , . . . , cpN ),0iäëÿ êîòîðûõ (cpi , cp ) ∈ `p ;ii→pi pj ïðåäñòàâëÿåò ñîáîé ìíîæåñòâî ïàð(. . . , cpi , . . . , cpj , . . .), (. . . , cp0 i , . . . , cp0 j , . . .),äëÿ êîòîðûõ åñòü òàêîå ñîîáùåíèå m ∈ M , ÷òî(cpi , m, cp0 i ) ∈ `spi è (cpj , m, cp0 j ) ∈ `rpj .Ñèñòåìû ñ ñèíõðîííîé ñâÿçüþ.Îïðåäåëåíèå 7.Ïóñòü çàäàíî ñåìåéñòâî ïðîöåññîâ P = {p1, . . .
, pN } . Òîãäàñèñòåìà ïåðåõîäîâ ñèíõðîííî ñâÿçàííûõ ïðîöåññîâS = (C, →, I)1.2.., ãäåC = {(cp1 , . . . , cpN ) : ∀p ∈ P : cp ∈ Zp }→ = (∪p∈P →p ) ∪ (∪p,q∈P: p6=q →pq )II3.òàêîâà:→pi ïðåäñòàâëÿåò ñîáîé ìíîæåñòâî ïàð(cp1 , . . .
, cpi , . . . , cpN ), (cp1 , . . . , cp0 i , . . . , cpN ),0iäëÿ êîòîðûõ (cpi , cp ) ∈ `p ;ii→pi pj ïðåäñòàâëÿåò ñîáîé ìíîæåñòâî ïàð(. . . , cpi , . . . , cpj , . . .), (. . . , cp0 i , . . . , cp0 j , . . .),äëÿ êîòîðûõ åñòü òàêîå ñîîáùåíèå m ∈ M , ÷òî(cpi , m, cp0 i ) ∈ `spi è (cpj , m, cp0 j ) ∈ `rpj .I = {(cp1 , . .
. , cpN ) : (∀p ∈ P : cp ∈ Ip )}.Ñèñòåìû ñ ñèíõðîííîé ñâÿçüþ.'$Êîíôèãóðàöèÿ:Ïðîöåññ p1(s11 , s21 )'Ïðîöåññ p2s11s21II`sp1`ip1$`ip2`rp2RRRs12&s22%&%Ñèñòåìû ñ ñèíõðîííîé ñâÿçüþ.'$Êîíôèãóðàöèÿ:Ïðîöåññ p1(s12 , s21 )'Ïðîöåññ p2s11s21II`sp1`ip1$`ip2`rp2RRRs12&s22%&%Ñèñòåìû ñ ñèíõðîííîé ñâÿçüþ.'$Êîíôèãóðàöèÿ:Ïðîöåññ p1(s11 , s22 )'Ïðîöåññ p2s11s21II`sp1`ip1$`ip2`rp2RRRs12&s22%&%Ñèñòåìû ñ ñèíõðîííîé ñâÿçüþ.'$Êîíôèãóðàöèÿ:Ïðîöåññ p1(s11 , s21 )'Ïðîöåññ p2s11s21II`sp1`ip1$`ip2`rp2RRRs12&s22%&%Ñïðàâåäëèâîñòü.Èíîãäà ïðè èññëåäîâàíèè ïîâåäåíèÿ ñèñòåì âîçíèêàåòíåîáõîäèìîñòü îãðàíè÷èòüñÿ ðàññìîòðåíèåì òîëüêî òàêíàçûâàåìûõ ñïðàâåäëèâûõ âûïîëíåíèé. Óñëîâèÿñïðàâåäëèâîñòè ïîçâîëÿþò èñêëþ÷èòü èç ðàññìîòðåíèÿ òàêèåâûïîëíåíèÿ, â êîòîðûõ íåêîòîðûå ñîáûòèÿ îêàçûâàþòñÿäîïóñòèìûìè âñåãäà (èëè áåñêîíå÷íî ÷àñòî), íî ïðè ýòîì íèðàçó íå îñóùåñòâëÿþòñÿ â âèäå ïåðåõîäîâ (èç-çà òîãî, ÷òîâûïîëíåíèå ïðîäîëæàåòñÿ âñÿêèé ðàç çà ñ÷åò îñóùåñòâëåíèÿäðóãèõ ñîáûòèé).Ñïðàâåäëèâîñòü.Èíîãäà ïðè èññëåäîâàíèè ïîâåäåíèÿ ñèñòåì âîçíèêàåòíåîáõîäèìîñòü îãðàíè÷èòüñÿ ðàññìîòðåíèåì òîëüêî òàêíàçûâàåìûõ ñïðàâåäëèâûõ âûïîëíåíèé.
Óñëîâèÿñïðàâåäëèâîñòè ïîçâîëÿþò èñêëþ÷èòü èç ðàññìîòðåíèÿ òàêèåâûïîëíåíèÿ, â êîòîðûõ íåêîòîðûå ñîáûòèÿ îêàçûâàþòñÿäîïóñòèìûìè âñåãäà (èëè áåñêîíå÷íî ÷àñòî), íî ïðè ýòîì íèðàçó íå îñóùåñòâëÿþòñÿ â âèäå ïåðåõîäîâ (èç-çà òîãî, ÷òîâûïîëíåíèå ïðîäîëæàåòñÿ âñÿêèé ðàç çà ñ÷åò îñóùåñòâëåíèÿäðóãèõ ñîáûòèé).Èìåþòñÿ äâå îñíîâíûå ôîðìû ñïðàâåäëèâîñòè: ñëàáàÿñïðàâåäëèâîñòü è ñèëüíàÿ ñïðàâåäëèâîñòü.Ñïðàâåäëèâîñòü.Îïðåäåëåíèå 8.1.
Êàæäîå âûïîëíåíèå, îêàí÷èâàþùååñÿ çàêëþ÷èòåëüíîéêîíôèãóðàöèåé, ÿâëÿåòñÿ ñïðàâåäëèâûì (êàê â ñëàáîì, òàêè â ñèëüíîì ñìûñëå).Ñïðàâåäëèâîñòü.Îïðåäåëåíèå 8.1. Êàæäîå âûïîëíåíèå, îêàí÷èâàþùååñÿ çàêëþ÷èòåëüíîéêîíôèãóðàöèåé, ÿâëÿåòñÿ ñïðàâåäëèâûì (êàê â ñëàáîì, òàêè â ñèëüíîì ñìûñëå).2. Áåñêîíå÷íîå âûïîëíåíèå E = (γ0, γ1, γ2, . . .) ñ÷èòàåòñÿñëàáî ñïðàâåäëèâûì , åñëè íå ñóùåñòâóåò òàêîãîíàòóðàëüíîãî ÷èñëà n, n > 0 , è òàêîãî ñîáûòèÿ e , ÷òî äëÿëþáîãî i, i ≥ n , ñîáûòèå e äîïóñòèìî â êîíôèãóðàöèè γi ,íî ïðè ýòîì γi+1 6= e(γi ) .Ñïðàâåäëèâîñòü.Îïðåäåëåíèå 8.1. Êàæäîå âûïîëíåíèå, îêàí÷èâàþùååñÿ çàêëþ÷èòåëüíîéêîíôèãóðàöèåé, ÿâëÿåòñÿ ñïðàâåäëèâûì (êàê â ñëàáîì, òàêè â ñèëüíîì ñìûñëå).2.
Áåñêîíå÷íîå âûïîëíåíèå E = (γ0, γ1, γ2, . . .) ñ÷èòàåòñÿñëàáî ñïðàâåäëèâûì , åñëè íå ñóùåñòâóåò òàêîãîíàòóðàëüíîãî ÷èñëà n, n > 0 , è òàêîãî ñîáûòèÿ e , ÷òî äëÿëþáîãî i, i ≥ n , ñîáûòèå e äîïóñòèìî â êîíôèãóðàöèè γi ,íî ïðè ýòîì γi+1 6= e(γi ) .3. Áåñêîíå÷íîå âûïîëíåíèå E = (γ0, γ1, γ2, . . .) ñ÷èòàåòñÿñèëüíî ñïðàâåäëèâûì , åñëè íå ñóùåñòâóåò òàêîãîíàòóðàëüíîãî ÷èñëà n, n > 0 , è òàêîãî ñîáûòèÿ e , ÷òî äëÿëþáîãî i, i ≥ n , ñîáûòèå e äîïóñòèìî â íåêîòîðîéêîíôèãóðàöèè γj , ãäå j ≥ i , íî ïðè ýòîì γi+1 6= e(γi ) .Ñïðàâåäëèâîñòü.'$Ïðîöåññ p1I`sp1$Ïðîöåññ p2'$s11`ip1'-∅s21I`rp2`ip2RRs12&&%Êîììóíèêàöèîííàÿñèñòåìà%Rs22&%Ñïðàâåäëèâîñòü.'$Ïðîöåññ p1I`sp1$Ïðîöåññ p2'$s11`ip1'-∅s21I`rp2`ip2RRs12&&%Êîììóíèêàöèîííàÿñèñòåìà%Rs22&%Ñïðàâåäëèâîñòü.'$Ïðîöåññ p1I`sp1$Ïðîöåññ p2'$s11`ip1'-M1s21I`rp2`ip2RRs12&&%Êîììóíèêàöèîííàÿñèñòåìà%Rs22&%Ñïðàâåäëèâîñòü.'$Ïðîöåññ p1I`sp1$Ïðîöåññ p2'$s11`ip1'-M1s21I`rp2`ip2RRs12&&%Êîììóíèêàöèîííàÿñèñòåìà%Rs22&%Ñïðàâåäëèâîñòü.'$Ïðîöåññ p1I`sp1$Ïðîöåññ p2'$s11`ip1'-M1M2s21I`rp2`ip2RRs12&&%Êîììóíèêàöèîííàÿñèñòåìà%Rs22&%Ñïðàâåäëèâîñòü.'$Ïðîöåññ p1I`sp1$Ïðîöåññ p2'$s11`ip1'-M1M2s21I`rp2`ip2RRs12&&%Êîììóíèêàöèîííàÿñèñòåìà%Rs22&%Ñïðàâåäëèâîñòü.'$Ïðîöåññ p1Ïðîöåññ p2I`sp1-M1M2&%`ip2R&%Êîììóíèêàöèîííàÿñèñòåìàs21I`rp2t t tè.
ò. ä.s12'$s11R$Íå÷åñòíî!!!`ip1'Rs22&%Ïðè÷èííî-ñëåäñòâåííûé ïîðÿäîê ñîáûòèé.Ñîïîñòàâèì âûïîëíåíèþ E = (γ0, γ1, . . .) ñâÿçàííóþ ñ íèìïîñëåäîâàòåëüíîñòü ñîáûòèé E = (e0, e1, . . .) , ãäå eiîáîçíà÷àåò ñîáûòèå ïðåîáðàçîâàíèÿ êîíôèãóðàöèè γi âêîíôèãóðàöèþ γi+1 . Äëÿ âèçóàëèçàöèè âûïîëíåíèÿ ìîæíîèñïîëüçîâàòü ïðîñòðàíñòâåííîâðåìåííûå äèàãðàììû .Ïðè÷èííî-ñëåäñòâåííûé ïîðÿäîê ñîáûòèé.Ñîïîñòàâèì âûïîëíåíèþ E = (γ0, γ1, . . .) ñâÿçàííóþ ñ íèìïîñëåäîâàòåëüíîñòü ñîáûòèé E = (e0, e1, . . .) , ãäå eiîáîçíà÷àåò ñîáûòèå ïðåîáðàçîâàíèÿ êîíôèãóðàöèè γi âêîíôèãóðàöèþ γi+1 .
