Алгоритм древовидный маркерный (Raymond).

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

Вход в  критическую секцию

Если есть маркер, то процесс выполняет КС.

Если нет маркера, то процесс:

1) помещает свой  запрос в  очередь запросов

2)   посылает сообщение «ЗАПРОС» в направлении владельца маркера и ждет  сообщений.

Поведение процесса при приеме сообщений

Процесс, не находящийся внутри  КС должен реагировать на сообщения двух видов -«МАРКЕР» и «ЗАПРОС».

А)  Пришло сообщение  «МАРКЕР»

М1. Взять 1-ый запрос из очереди  и послать маркер его автору (концептуально, возможно себе);

М2. Поменять значение указателя в сторону маркера;

М3. Исключить  запрос из очереди;

М4. Если  в очереди остались запросы, то послать сообщение  «ЗАПРОС» в  сторону маркера.

Б)  Пришло сообщение «ЗАПРОС».

1. Поместить запрос в очередь

2. Если нет маркера, то послать сообщение «ЗАПРОС» в сторону маркера, иначе (если  есть маркер) - перейти на пункт М1.

Выход из критической секции

Если очередь  запросов  пуста,  то при выходе ничего  не делается, иначе - перейти к пункту М1.

Децентрализованный алгоритм  на  основе временных меток.

Алгоритм носит  имя   Ricart-Agrawala   и   является   улучшением алгоритма, который предлжил Lamport.

Требуется глобальное  упорядочение  всех  событий  в  системе  по времени.

Вход в  критическую секцию

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

После посылки   запроса   процесс   ждет,   пока  все  дадут  ему разрешение. После  получения  от  всех   разрешения,   он   входит   в критическую секцию.

Поведение процесса при приеме запроса

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