12 Задача сохранения моментального состояния. Алгоритм Чанди-Лампорта. Алгоритм Лаи-Янга, страница 3
Описание файла
PDF-файл из архива "12 Задача сохранения моментального состояния. Алгоритм Чанди-Лампорта. Алгоритм Лаи-Янга", который расположен в категории "". Всё это находится в предмете "распределенные алгоритмы" из 10 семестр (2 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 3 страницы из PDF
Ýòî çíà÷èò, ÷òîc = true , è ïîýòîìó q çàïå÷àòëåâàåò ñâîå ñîñòîÿíèå òàêèì,êàêèì îíî áûëî äî ïîëó÷åíèÿ ñîîáùåíèÿ m .Òàêèì îáðàçîì, â ñîñòîÿíèè, êîòîðîå çàïèñàë ïðîöåññ q , íåó÷èòûâàåòñÿ ïîñòóïëåíèå m , è ïðèåì ñîîáùåíèÿ m îòíîñèòñÿê ÷èñëó ïîñòìîìåíòàëüíûõ ñîáûòèé.(Ñóùåñòâåííî çäåñü òî, êàêîå ñîñòîÿíèå çàïèñàòü, à íå òî,êîãäà ïðîâåñòè ýòó çàïèñü; â íàøåì ñëó÷àå çàïèñü ñîñòîÿíèÿïðîâîäèòñÿ îäíîâðåìåííî ñ ïîëó÷åíèåì ïåðâîãîïîñòìîìåíòàëüíîãî ñîáûòèÿ.)Ïðèìåíåíèå àëãîðèòìîâ ñîõðàíåíèÿìîìåíòàëüíîãî ñîñòîÿíèÿÐàññìîòðèì óñòîé÷èâîå ñâîéñòâî P êîíôèãóðàöèé, êîòîðîå âñëó÷àå âûïîëíåíèÿ áóäåò ñîõðàíÿòüñÿ è äëÿ êàæäîéïîñëåäóþùåé êîíôèãóðàöèè.1.Çàâåðøåíèå âû÷èñëåíèÿ. Åñëè γ ýòî çàêëþ÷èòåëüíàÿêîíôèãóðàöèÿ è γδ , òî γ = δ , è ïîýòîìóêîíôèãóðàöèÿ δ òàêæå ÿâëÿåòñÿ çàêëþ÷èòåëüíîé.Ñëåäîâàòåëüíî, çàäà÷à îáíàðóæåíèÿ çàâåðøåíèÿ ìîæåòáûòü ðåøåíà çà ñ÷åò âû÷èñëåíèÿ ìîìåíòàëüíîãî ñîñòîÿíèÿñèñòåìû è àíàëèçà àêòèâíûõ ïðîöåññîâ è áàçîâûõñîîáùåíèé â ýòîì ìîìåíòàëüíîì ñîñòîÿíèè.2.
Íàëè÷èå òóïèêîâ. Åñëè â êîíôèãóðàöèè γ íåêîòîðîåìíîæåñòâî ïðîöåññîâ S îêàçûâàåòñÿ çàáëîêèðîâàííûìè,èç-çà òîãî ÷òî âñå ïðîöåññû èç S îæèäàþò ïîñòóïëåíèÿñîîáùåíèé äðóã îò äðóãà, òî òàêàÿ æå ñèòóàöèÿ ïîâòîðèòñÿè â ïîñëåäóþùèõ êîíôèãóðàöèÿõ, õîòÿ ïðîöåññû âíåìíîæåñòâà S ìîãóò èçìåíÿòü ñâîè ñîñòîÿíèÿ.Ïðèìåíåíèå àëãîðèòìîâ ñîõðàíåíèÿìîìåíòàëüíîãî ñîñòîÿíèÿ3.Ðàññìîòðèì àëãîðèòì, â êîòîðîììàðêåðû öèðêóëèðóþò ìåæäó ïðîöåññàìè, à ñàìèïðîöåññû ìîãóò ïîãëîùàòü ìàðêåðû. Ñâîéñòâî âèäà¾Èìååòñÿ íå áîëåå k ìàðêåðîâ¿ ÿâëÿåòñÿ óñòîé÷èâûì, òàêêàê ìàðêåðû ìîãóò ïîãëîùàòüñÿ, íî íå ìîãóò ïîðîæäàòüñÿ.4.
Íàëè÷èå ¾ìóñîðà¿.  îáúåêòíî-îðèåíòèðîâàííîé ñðåäåïðîãðàììèðîâàíèÿ ñîçäàåòñÿ ñîâîêóïíîñòü îáúåêòîâ,êàæäûé èç êîòîðûõ ìîæåò ñîäåðæàòü ññûëêó íà äðóãèåîáúåêòû. Îáúåêò ñ÷èòàåòñÿ äîñòóïíûì, åñëè ìîæíîîòûñêàòü ïóòü, âåäóùèé ïî ññûëêàì ê äàííîìó îáúåêòó îòíåêîòîðîãî ïðåäïèñàííîãî îáúåêòà; â ïðîòèâíîì ñëó÷àåîáúåêò îáúÿâëÿåòñÿ ¾ìóñîðîì¿.
Ññûëêè ìîãóò ïîÿâëÿòüñÿè èñ÷åçàòü, íî ññûëêè, âåäóùèå ê ¾ìóñîðíûì¿ îáúåêòàì,íèêîãäà íå âîçíèêàþò. Ïîýòîìó, êàê òîëüêî îáúåêòñòàíîâèòñÿ ¾ìóñîðîì¿, îí áóäåò âî âåêè âå÷íûåîñòàâàòüñÿ òàêîâûì.Ïîòåðÿ ìàðêåðîâ.ÊÎÍÅÖ ËÅÊÖÈÈ 12..