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

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

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

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

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

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

Пример с найденным согласованным срезом, тут координатор по очереди сделал зелёными все процессы:

Wcp-search-central-good.png


Пример с не найденным согласованным срезом, тут координатор сначала сделал зелёным $P$, потом сделал зелёным $S$, а потом получил мажорирующий их вектор от $Q$ и сделал всех красными, кроме $Q$:

Wcp-search-central-bad.png