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