Алгоритмы взаимного исключения

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

2. Распределенный алгоритм – когда процесс хочет войти в секцию, он формирует сообщение, содержащее его номер, номер секции, и текущее значение времени. Запрос отправляется всем другим процессам системы. При получении такого сообщения:

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

b. Если получатель уже использует секцию, он ставит запрос в очередь

c. Если получатель собирается использовать секцию, он сравнивает временные отметки и либо отправляет разрешение, либо ставит запрос в очередь

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

3. Алгоритм token ring – процессы системы образуют логическое кольцо, по которому для каждой секции циркулирует токен.

Взаимоблокировки распределенных систем

Распределенные взаимоблокировки (distributed deadlocks) бывают трех типов:

1. Взаимоблокировка ресурсов

2. Взаимоблокировка связей (communication deadlocks) - возникают в ожидании поступления сигналов

3. Фантомные взаимоблокировки (phantom deadlocks) – возникают при использовании стороннего узла для выявления взаимоблокировок из-за задержек на линиях связи.

Для выхода из взаимоблокировок используется снятие одного из заблокированных процессов в зависимости от принятой стратегии.

Существуют три стратегии обнаружения взаимоблокировок:

1. Централизованное обнаружение взаимоблокировок (central deadlock detection) – один из узлов сети осуществляет ее мониторинг в целом и проверяет на наличие замкнутых циклов.

2. Иерархическое обнаружение взаимоблокировок (hierarchical -//-) – система представляется в виде иерархической организации узлов, каждый из которых за исключением листьев собирает информацию по ресурсам всех своих потоков.

3. Распределенное обнаружение взаимоблокировок (distributed -//-) – наличие взаимоблокировок проверяет каждый процесс системы, опрашивая остальные.