Централизованный алгоритм для WCP — различия между версиями
Yeputons (обсуждение | вклад) |
|||
| Строка 7: | Строка 7: | ||
* Есть один процесс-координатор, ответственный за поиск согласованного среза; | * Есть один процесс-координатор, ответственный за поиск согласованного среза; | ||
* Остальные процессы обычные, их задача проверять свои локальные предикаты; | * Остальные процессы обычные, их задача проверять свои локальные предикаты; | ||
| − | * Всякий раз, когда впервые с момента последнего отправленного сообщения локальный предикат становится true, оповещаем об этом координатора, указывая свое векторное время; | + | * Всякий раз, когда впервые с момента последнего отправленного сообщения локальный предикат становится true, оповещаем об этом координатора, указывая свое векторное время (впервые — чтобы не спамить, состояния процесса между посылками сообщений для системы неотличимы); |
* Координатор поддерживает в памяти срез-кандидат и очередь необработанных сообщений от каждого процесса; | * Координатор поддерживает в памяти срез-кандидат и очередь необработанных сообщений от каждого процесса; | ||
* Срез-кандидат согласован тогда и только тогда, когда все соответствующие вектора попарно несравнимы; | * Срез-кандидат согласован тогда и только тогда, когда все соответствующие вектора попарно несравнимы; | ||
Версия 22:22, 2 июня 2019
Централизованный алгоритм для WCP – алгоритм для поиска наименьшего (проще говоря, самого левого) согласованного среза в котором выполняется слабый конъюнктивный предикат.
В централизованном алгоритме используются векторные часы. Срез задается набором векторных часов для всех процессов или просто вектором, в котором соответствующая компонента показывает время для соответствующего потока.
Суть алгоритма:
- Есть один процесс-координатор, ответственный за поиск согласованного среза;
- Остальные процессы обычные, их задача проверять свои локальные предикаты;
- Всякий раз, когда впервые с момента последнего отправленного сообщения локальный предикат становится true, оповещаем об этом координатора, указывая свое векторное время (впервые — чтобы не спамить, состояния процесса между посылками сообщений для системы неотличимы);
- Координатор поддерживает в памяти срез-кандидат и очередь необработанных сообщений от каждого процесса;
- Срез-кандидат согласован тогда и только тогда, когда все соответствующие вектора попарно несравнимы;
- Координатор хранит вектора среза-кандидата и флажок для каждой его компоненты: красный – этот элемент не может быть частью согласованного среза, зеленый – может;
- Начальное состояние – все по нулям, красные;
- Обрабатываем приходящие сообщения только от красных процессов, сообщения от зеленых ставим в очередь:
- Сравниваем пришедший вектор попарно с другими процессами, если новый вектор больше, то делаем меньший процесс красным;
- После обработки сообщения делаем процесс зеленым.
- Если все зеленое, то мы нашли согласованный срез.
