Операционные системы распределенных вычислительных систем

       

Взаимное исключение.


Централизованный алгоритм.

Все процессы  запрашивают  у  координатора  разрешение  на вход в критическую секцию и ждут этого  разрешения.  Координатор  обслуживает запросы в  порядке  поступления.  Получив  разрешение процесс входит в критическую секцию.  При  выходе  из   нее   он   сообщает   об   этом координатору. Количество  сообщений  на  одно  прохождение критической секции - 3.

Недостатки алгоритма   -   обычные  недостатки  централизованного алгоритма (крах координатора или его перегрузка сообщениями).

Алгоритм с круговым маркером.

Все процессы составляют логическое кольцо,  когда  каждый  знает, кто следует за ним. По кольцу циркулирует маркер, дающий право на вход в критическую   секцию.   Получив   маркер   (посредством    сообщения точка-точка)  процесс  либо  входит в критическую секцию (если он ждал разрешения)  либо  переправляет  маркер  дальше.   После   выхода   из критической  секции  маркер  переправляется  дальше,  повторный вход в секцию при том же маркере не разрешается.

Проблемы.

Если маркер потеряется,  то его надо  регенерировать.  Обнаружить потерю тяжело (время прихода неизвестно).

Если какой-то процесс перестанет функционировать,  то алгоритм не работает.  Однако восстановление проще,  чем в других случаях. Наличие квитанций позволит обнаружить такой процесс в момент передачи  маркера (если  поломка  произошла  вне  критического  интервала).  Переставший функционировать процесс должен быть исключен  из  логического  кольца, для этого придется каждому знать текущую конфигурацию кольца.



Содержание раздела