Взаимное исключение в распределенной системе. Алгоритм обедающих философов, алгоритм на основе токена, алгоритм на основе кворума

By Денис Чащин  

Задача об обедующих философах

Философы за обеденным столом

Философы за обеденным столом

Здесь считается, что для того, чтобы есть, философу необходимо иметь все вилки.

  1. Процесс ест, когда у него есть все вилки и все вилки чистые
  2. После еды вилки помечаются грязными
  3. Чистые вилки не отдавать
  4. Полученные вилки — чистые
  5. Грязные вилки можно мыть, когда есть все остальные

Token ring

Связываем все процессы в кольцо и передаем по кольцу токен.

Token Ring

Передача токена по кольцу из процессов

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

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

Кворум — множество наборов процессов, в котором каждые два элемента имеют не пустое пересечение. Кворум замкнут по надмножнеству, что позволяет решить задачу доступа к критической секции. Надо просто спросить все процессы кворума. Рассмотрим как распределить процессы, чтобы они образовали кворум.

Простое большинство

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

Рушащаяся стена

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

Кворум методом рушащейся стены

Кворум методом рушащейся стены

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

Предыдущая статья из серии «О параллельном программировании»>


Post a Comment

Your email is never shared. Required fields are marked *

*
*