12 Задача сохранения моментального состояния. Алгоритм Чанди-Лампорта. Алгоритм Лаи-Янга

ÐàñïðåäåëåííûåàëãîðèòìûËÅÊÒÎÐ: Â.À. ÇàõàðîâËåêöèÿ 12.Çàäà÷à ñîõðàíåíèÿ ìîìåíòàëüíîãîñîñòîÿíèÿÀëãîðèòì ×àíäè-ËàìïîðòàÀëãîðèòì Ëàè-ßíãàÏðèìåíåíèå àëãîðèòìîâ ñîõðàíåíèÿìîìåíòàëüíîãî ñîñòîÿíèÿÇàäà÷à ñîõðàíåíèÿ ìîìåíòàëüíîãî ñîñòîÿíèÿÒðóäíî ñëåäèòü çà âû÷èñëåíèÿìè ðàñïðåäåëåííîé ñèñòåìûèçíóòðè ñàìîé ñèñòåìû. Ïðè ïðîåêòèðîâàíèè ðàñïðåäåëåííûõàëãîðèòìîâ âàæíûì êîíñòðóêòèâíûì áëîêîì ñëóæèò ïðîöåäóðàðàñ÷åòà è ñîõðàíåíèÿ â ïàìÿòè îòäåëüíûõ êîíôèãóðàöèéâû÷èñëåíèÿ, òàê íàçûâàåìûõ ìîìåíòàëüíûõ ñîñòîÿíèéñèñòåìû (snapshots).Ðàñïðåäåëåííîå âû÷èñëåíèå ýòî ïîñëåäîâàòåëüíîñòüêîíôèãóðàöèé ðàñïðåäåëåííîé ñèñòåìû. Êîíôèãóðàöèÿñèñòåìû ýòî íàáîð ñîñòîÿíèé åå ïðîöåññîâ ïëþñ ñîäåðæàíèåêàíàëîâ ñâÿçè.

Êàæäûé ïðîöåññ ìîæåò ñîõðàíÿòü â ïàìÿòèñâîå ñîñòîÿíèå. Íî íå âñÿêèé íàáîð ñîñòîÿíèé ïðîöåññîâîáðàçóåò êîíôèãóðàöèþ ñèñòåìû.Êàê íàó÷èòü ïðîöåññû ðàñïðåäåëåííîé ñèñòåìû çàïîìèíàòüñâîè ñîñòîÿíèÿ ñîãëàñîâàííî?Çàäà÷à ñîõðàíåíèÿ ìîìåíòàëüíîãî ñîñòîÿíèÿÏîñòðîåíèå ìîìåíòàëüíûõ ñîñòîÿíèé ñèñòåìû èñïîëüçóåòñÿ âðÿäå ïðèëîæåíèé.1) Âû÷èñëåíèÿ ìîæíî àíàëèçèðîâàòü â ðåæèìå o-line,èññëåäóÿ (ôèêñèðîâàííîå) ìîìåíòàëüíîå ñîñòîÿíèå âñåéñèñòåìû, à íå (èçìåí÷èâûå) òåêóùèå ñîñòîÿíèÿ ïðîöåññîâ.Câîéñòâî P êîíôèãóðàöèé íàçûâàåòñÿ óñòîé÷èâûì , åñëèñïðàâåäëèâî ñîîòíîøåíèå P(γ) ∧ γδ =⇒ P(δ).Åñëè áóäåò îáíàðóæåíî, ÷òî ñâîéñòâî P âûïîëíÿåòñÿ äëÿìîìåíòàëüíîãî ñîñòîÿíèÿ íåêîòîðîé êîíôèãóðàöèè ñèñòåìû, òîîòñþäà ìîæíî ñäåëàòü âûâîä î âûïîëíèìîñòè P äëÿ âñåõïîñëåäóþùèõ êîíôèãóðàöèé.

Ê óñòîé÷èâûì ñâîéñòâàìîòíîñÿòñÿ, íàïðèìåð, çàâåðøåííîñòü âû÷èñëåíèÿ, áëîêèðîâêà(ïîïàäàíèå â òóïèêîâóþ ñèòóàöèþ), ïîòåðÿ ìàðêåðà, à òàêæåíåäîñòèæèìîñòü îáúåêòîâ â ñòðóêòóðàõ äèíàìè÷åñêîé ïàìÿòè.Çàäà÷à ñîõðàíåíèÿ ìîìåíòàëüíîãî ñîñòîÿíèÿ2) Ìîìåíòàëüíûå ñîñòîÿíèÿ ñèñòåìû ìîæíî èñïîëüçîâàòüâìåñòî íà÷àëüíûõ êîíôèãóðàöèé, åñëè òðåáóåòñÿ ïåðåçàïóñòèòüâû÷èñëåíèå ââèäó îòêàçà êàêîãî-ëèáî ïðîöåññà.Äëÿ ýòîãî ïðîöåññ p ñëåäóåò ïåðåóñòàíîâèòü â òî ëîêàëüíîåñîñòîÿíèå cp , êîòîðîå áûëî çàïå÷àòëåíî â ìîìåíòàëüíîìñîñòîÿíèè ñèñòåìû, è ïðîäîëæèòü ðàáîòó àëãîðèòìà.3) Ìîìåíòàëüíûå ñîñòîÿíèÿ ñèñòåìû ÿâëÿþòñÿ ïîëåçíûìñðåäñòâîì îòëàäêè ðàñïðåäåëåííûõ ïðîãðàìì.

Ïðîâåäÿ âðåæèìå o-line àíàëèç êîíôèãóðàöèè, ¾âûõâà÷åííîé¿ èçîøèáî÷íîãî âûïîëíåíèÿ, ìîæíî îáíàðóæèòü ïðè÷èíó, ïîêîòîðîé ïðîãðàììà âåäåò ñåáÿ íå òàê, êàê ýòîãî îæèäàþò.Çàäà÷à ñîõðàíåíèÿ ìîìåíòàëüíîãî ñîñòîÿíèÿÐàññìîòðèì âû÷èñëåíèå C ðàñïðåäåëåííîé ñèñòåìû,ñîñòîÿùåé èç íåêîòîðîãî ìíîæåñòâà ïðîöåññîâ P .Ìû áóäåì ïîëàãàòü, ÷òî ñåòü ÿâëÿåòñÿ ñèëüíî ñâÿçíîé èâûïîëíÿåòñÿ äîïóùåíèå ñëàáîé ñïðàâåäëèâîñòè: êàæäîåñîîáùåíèå áóäåò äîñòàâëåíî ïî íàçíà÷åíèþ ñïóñòÿ êîíå÷íûéïðîìåæóòîê âðåìåíè.Îáîçíà÷èì çàïèñüþ Ev ìíîæåñòâî ñîáûòèé ýòîãî âû÷èñëåíèÿ.Ëîêàëüíîå âû÷èñëåíèå ïðîöåññà p ïðåäñòàâëÿåò ñîáîé(0)(1)(0)ïîñëåäîâàòåëüíîñòü cp , cp , .

. . ñîñòîÿíèé ïðîöåññà, ãäå cp ýòî íà÷àëüíîå ñîñòîÿíèå ïðîöåññà p .(i−1)(i)Ïåðåõîä èç ñîñòîÿíèÿ cpâ ñîñòîÿíèå cp îáóñëîâëåí(i)îñóùåñòâëåíèåì ñîáûòèÿ ep â ïðîöåññå p .(1)(2)Òàêèì îáðàçîì, Ev = ∪p∈P {ep , ep , . . .} .Çàäà÷à ñîõðàíåíèÿ ìîìåíòàëüíîãî ñîñòîÿíèÿ(0)cp6(1)ucp(1)6ep(i)u ucp(i)6epÍà÷àëüíîå ñîñòîÿíèåuu(i+1)6ep-Çàäà÷à ñîõðàíåíèÿ ìîìåíòàëüíîãî ñîñòîÿíèÿÍà ìíîæåñòâå ñîáûòèé ïðîöåññà p ââåäåìïðè÷èííî-ñëåäñòâåííûé ïîðÿäîê p ïðè ïîìîùè ñîîòíîøåíèÿ(i)(j)ep p ep⇐⇒ i ≤ j.Êàæäîå ñîáûòèå ìîæåò áûòü ñîáûòèåì îòïðàâëåíèÿñîîáùåíèÿ , ïðèåìà ñîîáùåíèÿ èëè âíóòðåííèì ñîáûòèåì .Äëÿ óïðîùåíèÿ îïèñàíèÿ àëãîðèòìîâ è ôîðìóëèðîâêè òåîðåìáóäåì ïðèäåðæèâàòüñÿ äîïóùåíèÿ î òîì, ÷òî èñòîðèÿ îáìåíàèíôîðìàöèåé ñ ïðîöåññîì îïðåäåëÿåòñÿ åãî ñîñòîÿíèåì.(i)Äëÿ êàíàëà ñâÿçè, âåäóùåãî èç p â q , ñîñòîÿíèå cp ïðîöåññà(i)p âêëþ÷àåò â ñåáÿ ñïèñîê sentpq ñîîáùåíèé, êîòîðûå ïðîöåññ pîòïðàâèë ïðîöåññó q ïðè îñóùåñòâëåíèè ñîáûòèé íà÷èíàÿ ñ(1)(i)ep è îêàí÷èâàÿ ep .(i)(i)Ñîñòîÿíèå cq ïðîöåññà q òàêæå ñîäåðæèò ñïèñîê rcvdpqñîîáùåíèé, êîòîðûå ïðîöåññ q ïîëó÷èë îò ïðîöåññà p ïðè(1)(i)îñóùåñòâëåíèè ñîáûòèé, íà÷èíàÿ ñ eq è îêàí÷èâàÿ eq .Çàäà÷à ñîõðàíåíèÿ ìîìåíòàëüíîãî ñîñòîÿíèÿÀëãîðèòì ïîñòðîåíèÿ ìîìåíòàëüíîãî ñîñòîÿíèÿ ñèñòåìûïðåäíàçíà÷åí äëÿ ðåêîíñòðóêöèè ãëîáàëüíîé êîíôèãóðàöèè,êîòîðàÿ îáðàçóåòñÿ èç ëîêàëüíûõ ñîñòîÿíèé (ìîìåíòàëüíûõñîñòîÿíèé) âñåõ ïðîöåññîâ.Ïðîöåññ p çàïå÷àòëåâàåò ñâîå ëîêàëüíîå ñîñòîÿíèå , çàïèñûâàÿâ ïàìÿòü îäíî ëîêàëüíîå ñîñòîÿíèå cp∗ , êîòîðîå íàçûâàåòñÿìîìåíòàëüíûì ëîêàëüíûì ñîñòîÿíèåì ïðîöåññà p .Åñëè ìîìåíòàëüíûì ëîêàëüíûì ñîñòîÿíèåì ïðîöåññà ÿâëÿåòñÿ(i)cp , ò.

å. p ïðîâîäèò ìîìåíòàëüíûé ñíèìîê ñîñòîÿíèÿ â(i)(i+1)ïðîìåæóòêå ìåæäó îñóùåñòâëåíèåì ñîáûòèé ep è ep, òî(j)ñîáûòèÿ ep , äëÿ êîòîðûõ j ≤ i , íàçûâàþòñÿïðåäìîìåíòàëüíûìè ñîáûòèÿìè ïðîöåññà p , à òå ñîáûòèÿ, äëÿêîòîðûõ j > i , íàçûâàþòñÿ ïîñòìîìåíòàëüíûìè ñîáûòèÿìèïðîöåññà p .Çàäà÷à ñîõðàíåíèÿ ìîìåíòàëüíîãî ñîñòîÿíèÿ(0)cp6(1)ucp(1)e6p(i)u ucp(i)6epÍà÷àëüíîå ñîñòîÿíèå(i)cp∗ = cp6uu-(i+1)6epÇàïå÷àòëåíèåìîìåíòàëüíîãî ñîñòîÿíèÿÇàäà÷à ñîõðàíåíèÿ ìîìåíòàëüíîãî ñîñòîÿíèÿÃëîáàëüíîå ìîìåíòàëüíîå ñîñòîÿíèå S ∗ îáðàçóåòñÿ èçìîìåíòàëüíûõ ñîñòîÿíèé cp∗ âñåõ ïðîöåññîâ p , âõîäÿùèõ âìíîæåñòâî P .

Äëÿ îáîçíà÷åíèÿ ýòîãî ñîñòîÿíèÿ áóäåìèñïîëüçîâàòü çàïèñü S ∗ = (cp∗1 , . . . , cp∗N ) .Òàê êàê ëîêàëüíûå ñîñòîÿíèÿ âêëþ÷àþò â ñåáÿ èñòîðèèîáìåíîâ èíôîðìàöèåé, ìîìåíòàëüíîå ñîñòîÿíèå S ∗ îïðåäåëÿåòêîíôèãóðàöèþ γ ∗ , åñëè ñîñòîÿíèåì êàíàëà pq ñ÷èòàòüìíîæåñòâî ñîîáùåíèé, îòïðàâëåííûõ ïî ýòîìó êàíàëóïðîöåññîì p (ñîãëàñíî ñîñòîÿíèþ cp∗ ), íî åùå íå äîñòàâëåííûõïðîöåññó q (ñîãëàñíî ñîñòîÿíèþ cq∗ ).Èíûìè ñëîâàìè, ñîñòîÿíèå êàíàëà pq â ìîìåíòàëüíîì∗ \ rcvd ∗ .ñîñòîÿíèè S ∗ îïðåäåëÿåòñÿ ñïèñêîì ñîîáùåíèé sentpqpqÊîíôèãóðàöèþ, ñîñòîÿùóþ èç ìîìåíòàëüíûõ ñîñòîÿíèéïðîöåññîâ è îïðåäåëåííûõ òàêèì îáðàçîì ñîñòîÿíèé êàíàëîâ,îáîçíà÷èì ñèìâîëîì γ ∗ .Çàäà÷à ñîõðàíåíèÿ ìîìåíòàëüíîãî ñîñòîÿíèÿp1p2p3ueHHHuHHHjuHHHHjuHeeÏðè ïîñòðîåíèè êîíôèãóðàöèè γ ∗ ïîÿâëÿþòñÿ íåêîòîðûå∗ íå ÿâëÿåòñÿ ïîäìíîæåñòâîìîòêëîíåíèÿ, åñëè ìíîæåñòâî rcvdpq∗sentpq .

Ñóäÿ ïî ëîêàëüíîìó ñîñòîÿíèþ cp∗1 â ôîðìèðóåìîììîìåíòàëüíîì ñîñòîÿíèè ñèñòåìû, ñîîáùåíèå áûëî îòïðàâëåíîïðîöåññîì p1 ïðîöåññó p3 , íî, êàê îòìå÷åíî â ëîêàëüíîìñîñòîÿíèè cp∗3 , íèêàêîãî ñîîáùåíèÿ îò p1 íå áûëî ïîëó÷åíî.Òàêèì îáðàçîì, â äàííîì ìîìåíòàëüíîì ñîñòîÿíèè ñèñòåìûêàíàë p1 p3 ñîäåðæèò îäíî ñîîáùåíèå; ãîâîðÿò, ÷òî â ýòîììîìåíòàëüíîì ñîñòîÿíèè ñèñòåìû óêàçàííîå ñîîáùåíèåïðåáûâàåò ¾íà ýòàïå ïåðåñûëêè¿.Çàäà÷à ñîõðàíåíèÿ ìîìåíòàëüíîãî ñîñòîÿíèÿp1p2p3uuHHHH eHHHjuHHHejuHeÎáðàòèìñÿ òåïåðü ê ñîîáùåíèþ, êîòîðîå ïðîöåññ p1 îòïðàâèëïðîöåññó p2 .Îòïðàâëåíèå ýòîãî ñîîáùåíèÿ îòíîñèòñÿ ê ÷èñëóïîñòìîìåíòàëüíûõ ñîáûòèé, òîãäà êàê åãî ïîëó÷åíèå ÿâëÿåòñÿïðåäìîìåíòàëüíûì ñîáûòèåì.Çíà÷èò, â ñîîòâåòñòâèè ñ ñîñòîÿíèåì cp∗1 íèêàêèå ñîîáùåíèÿ ïîêàíàëó p1 p2 íå îòïðàâëÿëèñü, òîãäà êàê â ñîñòîÿíèè cp∗2îòìå÷åíî, ÷òî ïî ýòîìó êàíàëó áûëî ïîëó÷åíî íåêîòîðîåñîîáùåíèå. Ïîñêîëüêó rcvdp∗1 p2 6⊆ sentp∗1 p2 , íèêàêîãîîñìûñëåííîãî ñîñòîÿíèÿ êàíàëó p1 p2 ïðèäàòü íåëüçÿ.Çàäà÷à ñîõðàíåíèÿ ìîìåíòàëüíîãî ñîñòîÿíèÿÎïðåäåëåíèå 1.Ìîìåíòàëüíîå ñîñòîÿíèå S ∗ íàçûâàåòñÿ îñóùåñòâèìûì , åñëèäëÿ âñÿêîé ïàðû ñîñåäíèõ ïðîöåññîâ p è q âûïîëíÿåòñÿ∗ ⊆ sent ∗ .âêëþ÷åíèå rcvdpqpqÎñóùåñòâèìîñòü ìîìåíòàëüíîãî ñîñòîÿíèÿ îçíà÷àåò, ÷òî ïðè∗ïîñòðîåíèè ñîîòâåòñòâóþùåé êîíôèãóðàöèè γ ∗ â ñïèñêå rcvdpq∗íåò íè îäíîãî ñîîáùåíèÿ, êîòîðîå íåëüçÿ óäàëèòü èç sentpq .Ñîîáùåíèå, îòïðàâëåíèå êîòîðîãî ÿâëÿåòñÿ ïðåäìîìåíòàëüíûì(ïîñòìîìåíòàëüíûì) ñîáûòèåì, áóäåì íàçûâàòüïðåäìîìåíòàëüíûì (ñîîòâåòñòâåííî, ïîñòìîìåíòàëüíûì )ñîîáùåíèåì.Çàäà÷à ñîõðàíåíèÿ ìîìåíòàëüíîãî ñîñòîÿíèÿÑóùåñòâóåò âçàèìíîîäíîçíà÷íîå ñîîòâåòñòâèå ìåæäóìîìåíòàëüíûìè ñîñòîÿíèÿìè è êîíå÷íûìè ñå÷åíèÿìè íàñîâîêóïíîñòè ñîáûòèé âû÷èñëåíèÿ.

Ñå÷åíèåì íàçûâàåòñÿñîâîêóïíîñòü ñîáûòèé, çàìêíóòàÿ âëåâî îòíîñèòåëüíîîòíîøåíèÿ ëîêàëüíîé ïðè÷èííî-ñëåäñòâåííîé çàâèñèìîñòè.Îïðåäåëåíèå 2.Ñå÷åíèåì íà ìíîæåñòâå Ev íàçûâàåòñÿ òàêîå ïîäìíîæåñòâîL ⊆ Ev , äëÿ êîòîðîãî âûïîëíÿåòñÿ ñîîòíîøåíèåe ∈ L ∧ e 0 p e=⇒e 0 ∈ L.Ñå÷åíèå L2 ñ÷èòàåòñÿ áîëåå ïîçäíèì, ÷åì ñå÷åíèå L1 , åñëèâåðíî âêëþ÷åíèå L1 ⊆ L2 .Ñîãëàñîâàííûì ñå÷å÷íèåì íà ìíîæåñòâå ñîáûòèé Evíàçûâàåòñÿ ñå÷åíèå L , óäîâëåòâîðÿþùåå ñîîòíîøåíèþe ∈ L ∧ e 0 e =⇒ e 0 ∈ L.Çàäà÷à ñîõðàíåíèÿ ìîìåíòàëüíîãî ñîñòîÿíèÿÍåòðóäíî âèäåòü, ÷òî äëÿ êàæäîãî ìîìåíòàëüíîãî ñîñòîÿíèÿS ∗ ñîâîêóïíîñòü L âñåõ ïðåäìîìåíòàëüíûõ ñîáûòèé ÿâëÿåòñÿêîíå÷íûì ñå÷åíèåì.Ðàññìîòðèì òåïåðü ïðîèçâîëüíîå êîíå÷íîå ñå÷åíèå L .Äëÿ êàæäîãî ïðîöåññà p ëèáî íè îäíî ñîáûòèå, ïðîèçîøåäøååâ p , íå âõîäèò â L (â òàêîì ñëó÷àå áóäåì ïîëàãàòü mp = 0 ),(m )ëèáî â L ñóùåñòâóåò íàèáîëüøåå ñîáûòèå ep p è ïðè ýòîì âñå(m )ñîáûòèÿ e p ep p òàêæå ñîäåðæàòñÿ â L .Ïîýòîìó L ïðåäñòàâëÿåò ñîáîé â òî÷íîñòè ìíîæåñòâîïðåäìîìåíòàëüíûõ ñîáûòèé ìîìåíòàëüíîãî ñîñòîÿíèÿ(mp )(mp )S ∗ = (cp1 1 , .

. . , cpN N ) .Çàäà÷à ñîõðàíåíèÿ ìîìåíòàëüíîãî ñîñòîÿíèÿÌîìåíòàëüíîå ñîñòîÿíèå áóäåò èñïîëüçîâàòüñÿ äëÿ èçâëå÷åíèÿèíôîðìàöèè î òîì âû÷èñëåíèè, êîòîðîå îíî çàïå÷àòëåâàåò, íîïðîèçâîëüíî âûáðàííîå ìîìåíòàëüíîå ñîñòîÿíèå ñèñòåìû äàåòî÷åíü ìàëî èíôîðìàöèè î òàêîì âû÷èñëåíèè.Àëãîðèòì ïîñòðîåíèÿ ìîìåíòàëüíîãî ñîñòîÿíèÿ äîëæåíðåêîíñòðóèðîâàòü êîíôèãóðàöèþ, êîòîðàÿ è ¾â ñàìîì äåëå¿ìîæåò âîçíèêíóòü ïðè âû÷ïîëíåíèè ñèñòåìû.Îäíàêî ìíîæåñòâî êîíôèãóðàöèé, ðåàëèçóåìûõ âïðîèçâîëüíîì âûïîëíåíèè ñèñòåìû, íå îïðåäåëÿåòñÿâû÷èñëåíèåì ñèñòåìû îäíîçíà÷íî.Òàêèì îáðàçîì, ðàçóìíûì ñ÷èòàåòñÿ âñÿêèé ðåçóëüòàò ðàáîòûàëãîðèòìà, åñëè îí ïðèâîäèò ê ïîñòðîåíèþ êàêîé-ëèáîêîíôèãóðàöèè, êîòîðàÿ îêàæåòñÿ âîçìîæíîé äëÿ çàäàííîãîâû÷èñëåíèÿ (ò.