Централизованный алгоритм для WCP

Материал из Викиконспекты
Перейти к: навигация, поиск

Централизованный алгоритм для WCP – алгоритм для поиска наименьшего (проще говоря, самого левого) согласованного среза в котором выполняется слабый конъюнктивный предикат. Если есть хотя бы один согласованный срез, в котором выполняется слабый конъюнктивный предикат, то такой срез существует и единственен (см. слабый конъюнктивный предикат).

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

Суть алгоритма:

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