Централизованный алгоритм для WCP — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «Категория: Параллельное программирование '''Централизованный алгоритм для WCP''' -- алгор…»)
 
Строка 1: Строка 1:
 
[[Категория: Параллельное программирование]]
 
[[Категория: Параллельное программирование]]
'''Централизованный алгоритм для WCP''' -- алгоритм для поиска [[Срез, согласованный срез|согласованного среза]] в котором выполняется слабый конъюнктивный предикат.
+
'''Централизованный алгоритм для WCP''' -- алгоритм для поиска наименьшего (проще говоря, самого левого) [[Срез, согласованный срез|согласованного среза]] в котором выполняется слабый конъюнктивный предикат.
 +
 
 +
В централизованном алгоритме используются векторные часы. В таком случае, срезом будет задается векторами.
 +
 
 +
Суть алгоритма:
 +
* Есть один процесс-координатор, который ответственный за поиск согласованного среза;
 +
* Остальные процессы обычные, их задача проверять свои локальные предикаты;
 +
* Всякий раз, когда впервые с момента последнего отправленного сообщения локальный предикат становится true, оповещаем об этом координатора, указывая свое векторное время;
 +
* Координатор поддерживает в памяти срез-кандидат и очередь необработанных сообщений от каждого процесса;
 +
* Срез-кандидат согласован тогда и только тогда, когда все соответствующие вектора попарно несравнимы;
 +
* Координатор хранит вектора среза-кандидата и флажок для каждой его компоненты: красный – этот элемент не может быть частью согласованного среза, зеленый – может;
 +
* Начальное состояние – все по нулям, красные;
 +
* Обрабатываем приходящие сообщения только от красных процессов, сообщения от зеленых ставим в очередь.
 +
** Сравниваем пришедший вектор попарно с другими процессами, если новый вектор больше, то делаем меньший процесс красным.
 +
** После обработки сообщения делаем процесс зеленым.
 +
* Если все зеленое, то мы нашли согласованный срез.

Версия 15:19, 14 марта 2018

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

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

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

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