Распределённый алгоритм для WCP — различия между версиями
Rgolchin (обсуждение | вклад) (Новая страница: «Категория: Параллельное программирование '''Распределенный алгоритм для WCP''' – алгори…») |
Rgolchin (обсуждение | вклад) |
||
| Строка 8: | Строка 8: | ||
Токен состоит из двух векторов. Первый назовем $G$. $G[i] = k$ означает, что состояние $k$ $i$-го процесса входит в срез-кандидат. Важно, что этот срез может не быть согласованным, но все состояния в нем удовлетворяют локальным предикатам. $G$ инициализируется нулями. | Токен состоит из двух векторов. Первый назовем $G$. $G[i] = k$ означает, что состояние $k$ $i$-го процесса входит в срез-кандидат. Важно, что этот срез может не быть согласованным, но все состояния в нем удовлетворяют локальным предикатам. $G$ инициализируется нулями. | ||
| − | Второй вектор назовем color, где color[i] обозначает цвет состояния среза-кандидата для $i$-го процесса. Цвет состояния может быть красным или зеленым. Если color[i] равен красному, то состояние $(i, G [i])$ и все его предшествующие состояния уже красные и никогда не смогут удовлетворить $WCP$. Если color [i] зеленый, то нет такого состояния в $G$, что $(i, G[i])$ предшествует ему. $color$ инициализируется красными. | + | Второй вектор назовем $color$, где $color[i]$ обозначает цвет состояния среза-кандидата для $i$-го процесса. Цвет состояния может быть красным или зеленым. Если $color[i]$ равен красному, то состояние $(i, G [i])$ и все его предшествующие состояния уже красные и никогда не смогут удовлетворить $WCP$. Если $color[i]$ зеленый, то нет такого состояния в $G$, что $(i, G[i])$ предшествует ему. $color$ инициализируется красными. |
Работа $i$-го монитор-процесса описана следующим псевдокодом. Гарантируется: когда переменная $detect = true$, мы получим искомый срез. | Работа $i$-го монитор-процесса описана следующим псевдокодом. Гарантируется: когда переменная $detect = true$, мы получим искомый срез. | ||
=== Псевдокод === | === Псевдокод === | ||
| − | + | [[Файл:Proc_algo.png]] | |
| − | [[Файл: | ||
Версия 18:28, 29 марта 2018
Распределенный алгоритм для WCP – алгоритм для поиска наименьшего (проще говоря, самого левого) согласованного среза в котором выполняется слабый конъюнктивный предикат.
В распределенном алгоритме используются векторные часы.
В дополнение к каждому из $N$ процессов заведем еще $N$ монитор-процессов, где каждый процесс связан со своим монитор-процессом. Монитор-процессы отправляют друг другу так называемый токен (его описание ниже) и получают вектор часов от соответствующих процессов.
Токен состоит из двух векторов. Первый назовем $G$. $G[i] = k$ означает, что состояние $k$ $i$-го процесса входит в срез-кандидат. Важно, что этот срез может не быть согласованным, но все состояния в нем удовлетворяют локальным предикатам. $G$ инициализируется нулями.
Второй вектор назовем $color$, где $color[i]$ обозначает цвет состояния среза-кандидата для $i$-го процесса. Цвет состояния может быть красным или зеленым. Если $color[i]$ равен красному, то состояние $(i, G [i])$ и все его предшествующие состояния уже красные и никогда не смогут удовлетворить $WCP$. Если $color[i]$ зеленый, то нет такого состояния в $G$, что $(i, G[i])$ предшествует ему. $color$ инициализируется красными.
Работа $i$-го монитор-процесса описана следующим псевдокодом. Гарантируется: когда переменная $detect = true$, мы получим искомый срез.
Псевдокод
