Лекция 10. Задача избрания лидера. Нижние оценки. Оптимальные выборы. Алгоритм GHS и Корача-Каттена-Морана, страница 5
Описание файла
PDF-файл из архива "Лекция 10. Задача избрания лидера. Нижние оценки. Оптимальные выборы. Алгоритм GHS и Корача-Каттена-Морана", который расположен в категории "". Всё это находится в предмете "распределенные алгоритмы" из 10 семестр (2 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 5 страницы из PDF
Ìàðêåð äîñòèã ïðîöåññà, â êîòîðîì õðàíèòñÿ ìàðêåð òîãîæå óðîâíÿ, ïðåáûâàþùèé â ðåæèìå îæèäàíèÿ; òîãäà îáàìàðêåðà èçûìàþòñÿ è â ýòîì ïðîöåññå íà÷èíàåòñÿ íîâûéîáõîä.3. Ìàðêåð äîñòèã ïðîöåññà òîãî æå óðîâíÿ, è ïðè ýòîìïîñëåäíèé èç ïîñåòèâøèõ ýòîò ïðîöåññ ìàðêåðîâ ïðåáûâàëâ ðåæèìå ïîãîíè; òîãäà íàø ìàðêåð ïåðåõîäèò â ðåæèìîæèäàíèÿ.Àëãîðèòì Êîðà÷àÊàòòåíàÌîðàíàÏðèíöèï 5.Ìàðêåð â ðåæèìå îæèäàíèÿ îñòàåòñÿ â òîì ïðîöåññå, êîòîðîãîîí äîñòèã, äî òåõ ïîð ïîêà íå ñëîæèòñÿ îäíà èç ñëåäóþùèõñèòóàöèé.Àëãîðèòì Êîðà÷àÊàòòåíàÌîðàíàÏðèíöèï 5.Ìàðêåð â ðåæèìå îæèäàíèÿ îñòàåòñÿ â òîì ïðîöåññå, êîòîðîãîîí äîñòèã, äî òåõ ïîð ïîêà íå ñëîæèòñÿ îäíà èç ñëåäóþùèõñèòóàöèé.1. Ìàðêåð áîëåå âûñîêîãî óðîâíÿ äîñòèãíåò òîãî æå ñàìîãîïðîöåññà; òîãäà îæèäàþùèé ìàðêåð áóäåò ïîäàâëåí.Àëãîðèòì Êîðà÷àÊàòòåíàÌîðàíàÏðèíöèï 5.Ìàðêåð â ðåæèìå îæèäàíèÿ îñòàåòñÿ â òîì ïðîöåññå, êîòîðîãîîí äîñòèã, äî òåõ ïîð ïîêà íå ñëîæèòñÿ îäíà èç ñëåäóþùèõñèòóàöèé.1. Ìàðêåð áîëåå âûñîêîãî óðîâíÿ äîñòèãíåò òîãî æå ñàìîãîïðîöåññà; òîãäà îæèäàþùèé ìàðêåð áóäåò ïîäàâëåí.2.
Ìàðêåð òîãî æå ñàìîãî óðîâíÿ äîñòèã òîãî æå ñàìîãîïðîöåññà; òîãäà îáà ìàðêåðà èçûìàþòñÿ, è â äàííîìïðîöåññå íà÷èíàåòñÿ íîâûé îáõîä áîëåå âûñîêîãî óðîâíÿ.Àëãîðèòì Êîðà÷àÊàòòåíàÌîðàíàÇàäà÷à.IÄîêàçàòü, ÷òî àëãîðèòìÊîðà÷àÊàòòåíàÌîðàíà ÿâëÿåòñÿàëãîðèòìîì èçáðàíèÿ ëèäåðà.Àëãîðèòì Êîðà÷àÊàòòåíàÌîðàíàÇàäà÷à.IIÄîêàçàòü, ÷òî àëãîðèòìÊîðà÷àÊàòòåíàÌîðàíà ÿâëÿåòñÿàëãîðèòìîì èçáðàíèÿ ëèäåðà.Îöåíèòü êîììóíèêàöèîííóþ ñëîæíîñòüàëãîðèòì Êîðà÷àÊàòòåíàÌîðàíà ïðèóñëîâèè, ÷òî â êà÷åñòâå ïðîöåäóðû îáõîäàèñïîëüçóåòñÿ àëãîðèòì Òàððè.ÊÎÍÅÖ ËÅÊÖÈÈ 9..