Лекция 12. Задача сохранения моментального состояния. Алгоритм Чанди-Лампорта_ Лаи-Янги. Применение на практике (1185662), страница 2
Текст из файла (страница 2)
Òîãäà ðàâíîñèëüíû ñëåäóþùèå òðèóòâåðæäåíèÿ:1) S ∗ îñóùåñòâèìî;2) L ñîãëàñîâàíî;3) S ∗ çíà÷èìî.Äîêàçàòåëüñòâî.Ïîêàæåì ñïðàâåäëèâîñòü ñîîòíîøåíèé(1) =⇒ (2) =⇒ (3) =⇒ (3)Çàäà÷à ñîõðàíåíèÿ ìîìåíòàëüíîãî ñîñòîÿíèÿ(1) ⇒ (2)Äîïóñòèì, ÷òî ñîñòîÿíèå S ∗ îñóùåñòâèìî. ×òîáû óáåäèòüñÿ âòîì, ÷òî L ñîãëàñîâàíî, ðàññìîòðèì e ∈ L è e 0 e . Ïîîïðåäåëåíèþ îòíîøåíèÿ äîñòàòî÷íî ïîêàçàòü, ÷òîâêëþ÷åíèå e 0 ∈ L âûïîëíÿåòñÿ â ñëåäóþùèõ äâóõ ñëó÷àÿõ.Äîêàçàòåëüñòâî.Çàäà÷à ñîõðàíåíèÿ ìîìåíòàëüíîãî ñîñòîÿíèÿ(1) ⇒ (2)Äîïóñòèì, ÷òî ñîñòîÿíèå S ∗ îñóùåñòâèìî. ×òîáû óáåäèòüñÿ âòîì, ÷òî L ñîãëàñîâàíî, ðàññìîòðèì e ∈ L è e 0 e . Ïîîïðåäåëåíèþ îòíîøåíèÿ äîñòàòî÷íî ïîêàçàòü, ÷òîâêëþ÷åíèå e 0 ∈ L âûïîëíÿåòñÿ â ñëåäóþùèõ äâóõ ñëó÷àÿõ.1. Âûïîëíÿåòñÿ ñîîòíîøåíèå e 0 p e (ãäå p ýòî ïðîöåññ, âêîòîðîì ïðîèñõîäÿò e 0 è e ).
 òàêîì ñëó÷àå âêëþ÷åíèå e 0 ∈ Lâûïîëíÿåòñÿ áëàãîäàðÿ òîìó, ÷òî L ñå÷åíèå.Äîêàçàòåëüñòâî.Çàäà÷à ñîõðàíåíèÿ ìîìåíòàëüíîãî ñîñòîÿíèÿ(1) ⇒ (2)Äîïóñòèì, ÷òî ñîñòîÿíèå S ∗ îñóùåñòâèìî. ×òîáû óáåäèòüñÿ âòîì, ÷òî L ñîãëàñîâàíî, ðàññìîòðèì e ∈ L è e 0 e . Ïîîïðåäåëåíèþ îòíîøåíèÿ äîñòàòî÷íî ïîêàçàòü, ÷òîâêëþ÷åíèå e 0 ∈ L âûïîëíÿåòñÿ â ñëåäóþùèõ äâóõ ñëó÷àÿõ.1. Âûïîëíÿåòñÿ ñîîòíîøåíèå e 0 p e (ãäå p ýòî ïðîöåññ, âêîòîðîì ïðîèñõîäÿò e 0 è e ).
 òàêîì ñëó÷àå âêëþ÷åíèå e 0 ∈ Lâûïîëíÿåòñÿ áëàãîäàðÿ òîìó, ÷òî L ñå÷åíèå.2. Ñîáûòèå e 0 ýòî ñîáûòèå îòïðàâëåíèÿ ñîîáùåíèÿ, àñîáûòèå e ñîîòâåòñòâóþùåå åìó ñîáûòèå ïðèåìàñîîáùåíèÿ.Äîêàçàòåëüñòâî.Çàäà÷à ñîõðàíåíèÿ ìîìåíòàëüíîãî ñîñòîÿíèÿ(1) ⇒ (2)Äîïóñòèì, ÷òî ñîñòîÿíèå S ∗ îñóùåñòâèìî. ×òîáû óáåäèòüñÿ âòîì, ÷òî L ñîãëàñîâàíî, ðàññìîòðèì e ∈ L è e 0 e . Ïîîïðåäåëåíèþ îòíîøåíèÿ äîñòàòî÷íî ïîêàçàòü, ÷òîâêëþ÷åíèå e 0 ∈ L âûïîëíÿåòñÿ â ñëåäóþùèõ äâóõ ñëó÷àÿõ.1.
Âûïîëíÿåòñÿ ñîîòíîøåíèå e 0 p e (ãäå p ýòî ïðîöåññ, âêîòîðîì ïðîèñõîäÿò e 0 è e ).  òàêîì ñëó÷àå âêëþ÷åíèå e 0 ∈ Lâûïîëíÿåòñÿ áëàãîäàðÿ òîìó, ÷òî L ñå÷åíèå.2. Ñîáûòèå e 0 ýòî ñîáûòèå îòïðàâëåíèÿ ñîîáùåíèÿ, àñîáûòèå e ñîîòâåòñòâóþùåå åìó ñîáûòèå ïðèåìàñîîáùåíèÿ.Ðàññìîòðèì ïðîöåññ p , â êîòîðîì ïðîèñõîäèòñîáûòèå e 0 , ïðîöåññ q , â êîòîðîì ïðîèñõîäèò e , è ñîîáùåíèåm , êîòîðûì îáìåíèâàþòñÿ ïðîöåññû. ÒîãäàÄîêàçàòåëüñòâî.Çàäà÷à ñîõðàíåíèÿ ìîìåíòàëüíîãî ñîñòîÿíèÿ(1) ⇒ (2)Äîïóñòèì, ÷òî ñîñòîÿíèå S ∗ îñóùåñòâèìî. ×òîáû óáåäèòüñÿ âòîì, ÷òî L ñîãëàñîâàíî, ðàññìîòðèì e ∈ L è e 0 e .
Ïîîïðåäåëåíèþ îòíîøåíèÿ äîñòàòî÷íî ïîêàçàòü, ÷òîâêëþ÷åíèå e 0 ∈ L âûïîëíÿåòñÿ â ñëåäóþùèõ äâóõ ñëó÷àÿõ.1. Âûïîëíÿåòñÿ ñîîòíîøåíèå e 0 p e (ãäå p ýòî ïðîöåññ, âêîòîðîì ïðîèñõîäÿò e 0 è e ).  òàêîì ñëó÷àå âêëþ÷åíèå e 0 ∈ Lâûïîëíÿåòñÿ áëàãîäàðÿ òîìó, ÷òî L ñå÷åíèå.2. Ñîáûòèå e 0 ýòî ñîáûòèå îòïðàâëåíèÿ ñîîáùåíèÿ, àñîáûòèå e ñîîòâåòñòâóþùåå åìó ñîáûòèå ïðèåìàñîîáùåíèÿ.Ðàññìîòðèì ïðîöåññ p , â êîòîðîì ïðîèñõîäèòñîáûòèå e 0 , ïðîöåññ q , â êîòîðîì ïðîèñõîäèò e , è ñîîáùåíèåm , êîòîðûì îáìåíèâàþòñÿ ïðîöåññû. ÒîãäàÄîêàçàòåëüñòâî.e∈L∗ ,=⇒ m ∈ rcvdpqò.ê. e ïðåäìîìåíòàëüíîå ñîáûòèåÇàäà÷à ñîõðàíåíèÿ ìîìåíòàëüíîãî ñîñòîÿíèÿ(1) ⇒ (2)Äîïóñòèì, ÷òî ñîñòîÿíèå S ∗ îñóùåñòâèìî.
×òîáû óáåäèòüñÿ âòîì, ÷òî L ñîãëàñîâàíî, ðàññìîòðèì e ∈ L è e 0 e . Ïîîïðåäåëåíèþ îòíîøåíèÿ äîñòàòî÷íî ïîêàçàòü, ÷òîâêëþ÷åíèå e 0 ∈ L âûïîëíÿåòñÿ â ñëåäóþùèõ äâóõ ñëó÷àÿõ.1. Âûïîëíÿåòñÿ ñîîòíîøåíèå e 0 p e (ãäå p ýòî ïðîöåññ, âêîòîðîì ïðîèñõîäÿò e 0 è e ).  òàêîì ñëó÷àå âêëþ÷åíèå e 0 ∈ Lâûïîëíÿåòñÿ áëàãîäàðÿ òîìó, ÷òî L ñå÷åíèå.2. Ñîáûòèå e 0 ýòî ñîáûòèå îòïðàâëåíèÿ ñîîáùåíèÿ, àñîáûòèå e ñîîòâåòñòâóþùåå åìó ñîáûòèå ïðèåìàñîîáùåíèÿ.Ðàññìîòðèì ïðîöåññ p , â êîòîðîì ïðîèñõîäèòñîáûòèå e 0 , ïðîöåññ q , â êîòîðîì ïðîèñõîäèò e , è ñîîáùåíèåm , êîòîðûì îáìåíèâàþòñÿ ïðîöåññû.
ÒîãäàÄîêàçàòåëüñòâî.e∈L∗ ,=⇒ m ∈ rcvdpq∗=⇒ m ∈ sentpq ,ò.ê. e ïðåäìîìåíòàëüíîå ñîáûòèåò.ê. S ∗ îñóùåñòâèìîÇàäà÷à ñîõðàíåíèÿ ìîìåíòàëüíîãî ñîñòîÿíèÿ(1) ⇒ (2)Äîïóñòèì, ÷òî ñîñòîÿíèå S ∗ îñóùåñòâèìî. ×òîáû óáåäèòüñÿ âòîì, ÷òî L ñîãëàñîâàíî, ðàññìîòðèì e ∈ L è e 0 e . Ïîîïðåäåëåíèþ îòíîøåíèÿ äîñòàòî÷íî ïîêàçàòü, ÷òîâêëþ÷åíèå e 0 ∈ L âûïîëíÿåòñÿ â ñëåäóþùèõ äâóõ ñëó÷àÿõ.1. Âûïîëíÿåòñÿ ñîîòíîøåíèå e 0 p e (ãäå p ýòî ïðîöåññ, âêîòîðîì ïðîèñõîäÿò e 0 è e ).  òàêîì ñëó÷àå âêëþ÷åíèå e 0 ∈ Lâûïîëíÿåòñÿ áëàãîäàðÿ òîìó, ÷òî L ñå÷åíèå.2. Ñîáûòèå e 0 ýòî ñîáûòèå îòïðàâëåíèÿ ñîîáùåíèÿ, àñîáûòèå e ñîîòâåòñòâóþùåå åìó ñîáûòèå ïðèåìàñîîáùåíèÿ.Ðàññìîòðèì ïðîöåññ p , â êîòîðîì ïðîèñõîäèòñîáûòèå e 0 , ïðîöåññ q , â êîòîðîì ïðîèñõîäèò e , è ñîîáùåíèåm , êîòîðûì îáìåíèâàþòñÿ ïðîöåññû.
ÒîãäàÄîêàçàòåëüñòâî.e∈L∗ ,=⇒ m ∈ rcvdpq∗=⇒ m ∈ sentpq ,=⇒ e 0 ∈ L.ò.ê. e ïðåäìîìåíòàëüíîå ñîáûòèåò.ê. S ∗ îñóùåñòâèìîÇàäà÷à ñîõðàíåíèÿ ìîìåíòàëüíîãî ñîñòîÿíèÿÄîêàçàòåëüñòâî.(2) ⇒ (3)Çàäà÷à ñîõðàíåíèÿ ìîìåíòàëüíîãî ñîñòîÿíèÿÄîêàçàòåëüñòâî.(2) ⇒ (3)Ïîñòðîèì òàêîå âûïîëíåíèå âû÷èñëåíèÿ, â êîòîðîì âñåïðåäìîìåíòàëüíûå ñîáûòèÿ ïðîèñõîäÿò ðàíåå ëþáîãîïîñòìîìåíòàëüíîãî ñîáûòèÿ.Ââåäåì ñëåäóþùóþ íóìåðàöèþ f = (f0 , f1 , . . .) ñîáûòèéìíîæåñòâà Ev .Âíà÷àëå ïåðå÷èñëèì âñå ïðåäìîìåíòàëüíûå ñîáûòèÿ èç Ev âïðîèçâîëüíîì ïîðÿäêå, ñîãëàñîâàííîì ñ îòíîøåíèåì , àäàëåå ïåðå÷èñëèì âñå ïîñòìîìåíòàëüíûå ñîáûòèÿ âïðîèçâîëüíîì ïîðÿäêå, ñîãëàñîâàííîì ñ îòíîøåíèåì .Çàäà÷à ñîõðàíåíèÿ ìîìåíòàëüíîãî ñîñòîÿíèÿuHHHHjuu Huu u u u uue uJuueJ QAeQJQAUAusuQeJJJJu u u u uÏðîñòðàíñòâåííîâðåìåííàÿäèàãðàììà CÏîñëåäîâàòåëüíîñòü fÇàäà÷à ñîõðàíåíèÿ ìîìåíòàëüíîãî ñîñòîÿíèÿÄîêàçàòåëüñòâî.(2) ⇒ (3)Ïîñòðîèì òàêîå âûïîëíåíèå âû÷èñëåíèÿ, â êîòîðîì âñåïðåäìîìåíòàëüíûå ñîáûòèÿ ïðîèñõîäÿò ðàíåå ëþáîãîïîñòìîìåíòàëüíîãî ñîáûòèÿ.Ââåäåì ñëåäóþùóþ íóìåðàöèþ f = (f0 , f1 , .
. .) ñîáûòèéìíîæåñòâà Ev .Âíà÷àëå ïåðå÷èñëèì âñå ïðåäìîìåíòàëüíûå ñîáûòèÿ èç Ev âïðîèçâîëüíîì ïîðÿäêå, ñîãëàñîâàííîì ñ îòíîøåíèåì , àäàëåå ïåðå÷èñëèì âñå ïîñòìîìåíòàëüíûå ñîáûòèÿ âïðîèçâîëüíîì ïîðÿäêå, ñîãëàñîâàííîì ñ îòíîøåíèåì .Âîñïîëüçóåìñÿ òåîðåìîé î âû÷èñëåíèÿõ.Ïóñòü f = (f0 , f1 , f2 , .
. .) ïåðåñòàíîâêà ñîáûòèé âûïîëíåíèÿE , ñîõðàíÿþùàÿ ïðè÷èííî-ñëåäñòâåííûé ïîðÿäîê ñîáûòèéâûïîëíåíèÿ . Òîãäà f îïðåäåëÿåò åäèíñòâåííîå âûïîëíåíèå F ,íà÷èíàþùååñÿ ñ òîé æå êîíôèãóðàöèè, ÷òî è âûïîëíåíèå E .Çàäà÷à ñîõðàíåíèÿ ìîìåíòàëüíîãî ñîñòîÿíèÿ×òîáû âîñïîëüçîâàòüñÿ ýòîé òåîðåìîé, ïîêàæåì, ÷òî âñÿïîñëåäîâàòåëüíîñòü f ñîãëàñîâàíà ñ îòíîøåíèåì . Äîïóñòèì,÷òî fi fj .Çàäà÷à ñîõðàíåíèÿ ìîìåíòàëüíîãî ñîñòîÿíèÿ×òîáû âîñïîëüçîâàòüñÿ ýòîé òåîðåìîé, ïîêàæåì, ÷òî âñÿïîñëåäîâàòåëüíîñòü f ñîãëàñîâàíà ñ îòíîøåíèåì . Äîïóñòèì,÷òî fi fj .Åñëè îáà ñîáûòèÿ fi è fj ïðåäìîìåíòàëüíûå, òî i ≤ j ,ïîñêîëüêó â f ïðåäìîìåíòàëüíûå ñîáûòèÿ ïåðå÷èñëåíû âïîðÿäêå, ñîãëàñîâàííîì ñ îòíîøåíèåì .Çàäà÷à ñîõðàíåíèÿ ìîìåíòàëüíîãî ñîñòîÿíèÿ×òîáû âîñïîëüçîâàòüñÿ ýòîé òåîðåìîé, ïîêàæåì, ÷òî âñÿïîñëåäîâàòåëüíîñòü f ñîãëàñîâàíà ñ îòíîøåíèåì .
Äîïóñòèì,÷òî fi fj .Åñëè îáà ñîáûòèÿ fi è fj ïðåäìîìåíòàëüíûå, òî i ≤ j ,ïîñêîëüêó â f ïðåäìîìåíòàëüíûå ñîáûòèÿ ïåðå÷èñëåíû âïîðÿäêå, ñîãëàñîâàííîì ñ îòíîøåíèåì .Ïî òåì æå ïðè÷èíàì ýòî íåðàâåíñòâî âûïîëíÿåòñÿ, êîãäà îáàñîáûòèÿ fi è fj ÿâëÿþòñÿ ïîñòìîìåíòàëüíûìè.Çàäà÷à ñîõðàíåíèÿ ìîìåíòàëüíîãî ñîñòîÿíèÿ×òîáû âîñïîëüçîâàòüñÿ ýòîé òåîðåìîé, ïîêàæåì, ÷òî âñÿïîñëåäîâàòåëüíîñòü f ñîãëàñîâàíà ñ îòíîøåíèåì . Äîïóñòèì,÷òî fi fj .Åñëè îáà ñîáûòèÿ fi è fj ïðåäìîìåíòàëüíûå, òî i ≤ j ,ïîñêîëüêó â f ïðåäìîìåíòàëüíûå ñîáûòèÿ ïåðå÷èñëåíû âïîðÿäêå, ñîãëàñîâàííîì ñ îòíîøåíèåì .Ïî òåì æå ïðè÷èíàì ýòî íåðàâåíñòâî âûïîëíÿåòñÿ, êîãäà îáàñîáûòèÿ fi è fj ÿâëÿþòñÿ ïîñòìîìåíòàëüíûìè.Åñëè fi ïðåäìîìåíòàëüíîå ñîáûòèå, à fj ïîñòìîìåíòàëüíîå, òî íåðàâåíñòâî i ≤ j ñîáëþäàåòñÿ ò.ê.
â fâñå ïðåäìîìåíòàëüíûå ñîáûòèÿ ïðåäøåñòâóþòïîñòìîìåíòàëüíûì.Çàäà÷à ñîõðàíåíèÿ ìîìåíòàëüíîãî ñîñòîÿíèÿ×òîáû âîñïîëüçîâàòüñÿ ýòîé òåîðåìîé, ïîêàæåì, ÷òî âñÿïîñëåäîâàòåëüíîñòü f ñîãëàñîâàíà ñ îòíîøåíèåì . Äîïóñòèì,÷òî fi fj .Åñëè îáà ñîáûòèÿ fi è fj ïðåäìîìåíòàëüíûå, òî i ≤ j ,ïîñêîëüêó â f ïðåäìîìåíòàëüíûå ñîáûòèÿ ïåðå÷èñëåíû âïîðÿäêå, ñîãëàñîâàííîì ñ îòíîøåíèåì .Ïî òåì æå ïðè÷èíàì ýòî íåðàâåíñòâî âûïîëíÿåòñÿ, êîãäà îáàñîáûòèÿ fi è fj ÿâëÿþòñÿ ïîñòìîìåíòàëüíûìè.Åñëè fi ïðåäìîìåíòàëüíîå ñîáûòèå, à fj ïîñòìîìåíòàëüíîå, òî íåðàâåíñòâî i ≤ j ñîáëþäàåòñÿ ò.ê.
â fâñå ïðåäìîìåíòàëüíûå ñîáûòèÿ ïðåäøåñòâóþòïîñòìîìåíòàëüíûì.Ñëó÷àé, êîãäà fj ïðåäìîìåíòàëüíîå ñîáûòèå, à fi ïîñòìîìåíòàëüíîå, èñêëþ÷åí, ââèäó òîãî ÷òî ñå÷åíèå L ïîïðåäïîëîæåíèþ ÿâëÿåòñÿ ñîãëàñîâàííûì.Çàäà÷à ñîõðàíåíèÿ ìîìåíòàëüíîãî ñîñòîÿíèÿÈòàê, ïîñëåäîâàòåëüíîñòü f ñîãëàñîâàíà ñ îòíîøåíèåì .Çíà÷èò, ïî òåîðåìå î âû÷èñëåíèÿõ ñóùåñòâóåò âûïîëíåíèåâû÷èñëåíèÿ F , ñîñòîÿùåå èç âñåõ ñîáûòèé ìíîæåñòâà Ev ,îñóùåñòâëÿåìûõ â òîì ïîðÿäêå, êîòîðûé ïðåäñòàâëåíïîñëåäîâàòåëüíîñòüþ f .
Âûïîëíåíèå F ñîäåðæèòêîíôèãóðàöèþ γ ∗ , êîòîðàÿ âîçíèêàåò ñðàçó æå ïîñëåîñóùåñòâëåíèÿ âñåõ ïðåäìîìåíòàëüíûõ ñîáûòèé.Äîêàçàòåëüñòâî.(3) ⇒ (1)Çàäà÷à ñîõðàíåíèÿ ìîìåíòàëüíîãî ñîñòîÿíèÿÈòàê, ïîñëåäîâàòåëüíîñòü f ñîãëàñîâàíà ñ îòíîøåíèåì .Çíà÷èò, ïî òåîðåìå î âû÷èñëåíèÿõ ñóùåñòâóåò âûïîëíåíèåâû÷èñëåíèÿ F , ñîñòîÿùåå èç âñåõ ñîáûòèé ìíîæåñòâà Ev ,îñóùåñòâëÿåìûõ â òîì ïîðÿäêå, êîòîðûé ïðåäñòàâëåíïîñëåäîâàòåëüíîñòüþ f . Âûïîëíåíèå F ñîäåðæèòêîíôèãóðàöèþ γ ∗ , êîòîðàÿ âîçíèêàåò ñðàçó æå ïîñëåîñóùåñòâëåíèÿ âñåõ ïðåäìîìåíòàëüíûõ ñîáûòèé.Äîêàçàòåëüñòâî.(3) ⇒ (1)Åñëè ìîìåíòàëüíîå ñîñòîÿíèå S ∗ ÿâëÿåòñÿ çíà÷èìûì, òîêîíôèãóðàöèÿ γ ∗ âîçíèêàåò ïðè âûïîëíåíèè âû÷èñëåíèÿ C . Âêàæäîì âûïîëíåíèè âñÿêîå ñîîáùåíèå íå ìîæåò áûòüäîñòàâëåíî ïî íàçíà÷åíèþ, ïðåæäå ÷åì îíî áóäåò îòïðàâëåíî.Îòñþäà ñëåäóåò, ÷òî äëÿ êàæäîé ïàðû ïðîöåññîâ p è q èìååò∗ ⊆ sent ∗ .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
