Алгоритм древовидный маркерный (Raymond).
Все процессы представлены в виде сбалансированного двоичного дерева. Каждый процесс имеет очередь запросов от себя и соседних процессов (1-го, 2-х или 3-х) и указатель в направлении владельца маркера.
Вход в критическую секцию
Если есть маркер, то процесс выполняет КС.
Если нет маркера, то процесс:
1) помещает свой запрос в очередь запросов
2) посылает сообщение «ЗАПРОС» в направлении владельца маркера и ждет сообщений.
Поведение процесса при приеме сообщений
Процесс, не находящийся внутри КС должен реагировать на сообщения двух видов -«МАРКЕР» и «ЗАПРОС».
А) Пришло сообщение «МАРКЕР»
М1. Взять 1-ый запрос из очереди и послать маркер его автору (концептуально, возможно себе);
М2. Поменять значение указателя в сторону маркера;
М3. Исключить запрос из очереди;
М4. Если в очереди остались запросы, то послать сообщение «ЗАПРОС» в сторону маркера.
Б) Пришло сообщение «ЗАПРОС».
1. Поместить запрос в очередь
2. Если нет маркера, то послать сообщение «ЗАПРОС» в сторону маркера, иначе (если есть маркер) - перейти на пункт М1.
Выход из критической секции
Если очередь запросов пуста, то при выходе ничего не делается, иначе - перейти к пункту М1.
Децентрализованный алгоритм на основе временных меток.
Алгоритм носит имя Ricart-Agrawala и является улучшением алгоритма, который предлжил Lamport.
Требуется глобальное упорядочение всех событий в системе по времени.
Вход в критическую секцию
Когда процесс желает войти в критическую секцию, он посылает всем процессам сообщение-запрос, содержащее имя критической секции, номер процесса и текущее время.
После посылки запроса процесс ждет, пока все дадут ему разрешение. После получения от всех разрешения, он входит в критическую секцию.
Поведение процесса при приеме запроса
Когда процесс получает сообщение-запрос, в зависимости от своего состояния по отношению к указанной критической секции он действует одним из следующих способов.