Алгоритм для причинно-согласованного порядка — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «Этот алгоритм берёт систему с асинхронным(?) порядком и начинает гарантировать в ней Ие…»)
 
Строка 1: Строка 1:
Этот алгоритм берёт систему с асинхронным(?) порядком и начинает гарантировать в ней [[Иерархия порядков сообщений#Причинно-согласованный порядок|причинно-согласованный порядок]].
+
Этот алгоритм берёт систему с асинхронным порядком и начинает гарантировать в ней [[Иерархия порядков сообщений#Причинно-согласованный порядок|причинно-согласованный порядок]].
 +
 
 +
Идея похожа на [[Алгоритм для FIFO порядка]]: прикрепить к каждому сообщению "номер" и обрабатывать только сообщения со следующим ожидаемым номером, а остальные складывать в очередь.
 +
Нам надо не только знать следующее ожидаемое сообщение от каждого процесса, но и
 +
 
 +
Используется что-то вроде матричных часов, но не совсем они (см. раздел 7.7 на странице 125 и раздел 12.2 на странице 193 в Gaarg).
 +
 
 +
Каждый процесс поддерживает счётчик-матрицу: $M_{i,j}$ — количество сообщений, отправленных процессом $i$ процессом $j$ (по мнению хранящего матрицу).
 +
Эта матрица отправляется с каждым сообщением, перед посылкой мы увеличиваем соответствующее число в ней на единицу.
 +
 
 +
Когда процесс $P_i$ с матрицей $M$ получил от $P_j$ сообщение с матрицей $W$, то:
 +
* Если $W_{ji}=M_{ji}+1$, то это ожидаемое сообщение с точки зрения FIFO-порядка между $P_i$ и $P_j$. Иначе надо отложить в очередь.
 +
* Если существует $k \neq j$ такое, что $W_{ki} > M_{ki}$, то это значит, что процесс $k$ отправил нам сообщение, процесс $j$ про это в курсе, а мы ещё его не получили. Тогда для причинно-согласованности надо сначала подождать это сообщение, а потом обрабатывать сообщение от $P_j$.
 +
* Если же такого $k$ не существует, то уже можно обработать сообщение и ничего не нарушится (строго не доказывали).
 +
* Непосредственно перед тем, как обработать сообщение, надо обновить свою матрицу $M$, взяв покомпонентный максимум всех значений.
 +
 
 +
Как и в алгоритме для FIFO, тут очередь принятых, но не обработанных сообщений может раздуваться бесконечно.
 +
Но тут нам сложнее обрабатывать сообщения в очереди: в FIFO это было независимо по процессам и можно было сложить их в очередь с приоритетом, а тут сообщение от одного процесса может вызвать лавину сообщений от остальных, надо перебирать.
  
 
Псевдокод алгоритма для причинно-согласованного порядка. Вместе с сообщением отправляем матрицу M: M[i, j] — количество сообщений, отправленных процессом i процессу j.
 
Псевдокод алгоритма для причинно-согласованного порядка. Вместе с сообщением отправляем матрицу M: M[i, j] — количество сообщений, отправленных процессом i процессу j.

Версия 10:24, 3 июня 2019

Этот алгоритм берёт систему с асинхронным порядком и начинает гарантировать в ней причинно-согласованный порядок.

Идея похожа на Алгоритм для FIFO порядка: прикрепить к каждому сообщению "номер" и обрабатывать только сообщения со следующим ожидаемым номером, а остальные складывать в очередь. Нам надо не только знать следующее ожидаемое сообщение от каждого процесса, но и

Используется что-то вроде матричных часов, но не совсем они (см. раздел 7.7 на странице 125 и раздел 12.2 на странице 193 в Gaarg).

Каждый процесс поддерживает счётчик-матрицу: $M_{i,j}$ — количество сообщений, отправленных процессом $i$ процессом $j$ (по мнению хранящего матрицу). Эта матрица отправляется с каждым сообщением, перед посылкой мы увеличиваем соответствующее число в ней на единицу.

Когда процесс $P_i$ с матрицей $M$ получил от $P_j$ сообщение с матрицей $W$, то:

  • Если $W_{ji}=M_{ji}+1$, то это ожидаемое сообщение с точки зрения FIFO-порядка между $P_i$ и $P_j$. Иначе надо отложить в очередь.
  • Если существует $k \neq j$ такое, что $W_{ki} > M_{ki}$, то это значит, что процесс $k$ отправил нам сообщение, процесс $j$ про это в курсе, а мы ещё его не получили. Тогда для причинно-согласованности надо сначала подождать это сообщение, а потом обрабатывать сообщение от $P_j$.
  • Если же такого $k$ не существует, то уже можно обработать сообщение и ничего не нарушится (строго не доказывали).
  • Непосредственно перед тем, как обработать сообщение, надо обновить свою матрицу $M$, взяв покомпонентный максимум всех значений.

Как и в алгоритме для FIFO, тут очередь принятых, но не обработанных сообщений может раздуваться бесконечно. Но тут нам сложнее обрабатывать сообщения в очереди: в FIFO это было независимо по процессам и можно было сложить их в очередь с приоритетом, а тут сообщение от одного процесса может вызвать лавину сообщений от остальных, надо перебирать.

Псевдокод алгоритма для причинно-согласованного порядка. Вместе с сообщением отправляем матрицу M: M[i, j] — количество сообщений, отправленных процессом i процессу j.

 var
     M:array[l..N, 1..N] of integer initially 0;
 To send a message to [math]P_j[/math]:
     M [i,j] := M[i,j] + 1;
     send M as part of the message;
 To receive a message with matrix W from Pj:
     enabled if W[j,i] = M [j,i] + 1 [math]\land[/math] [math] \forall k \neq j[/math] [math]M[k, i] \geqslant W[k, i][/math]
     M := max(M, W)