292
правки
Изменения
→6 семестр
Эти срезы не обязательно согласованны, но они барьерно-синхронизированы (из-за сообщений координатору и обратно), а значит образуют согласованный интервал. Поэтому между ними есть согласованный срез <tex>G</tex>, а так как состояние процессов в цикле не менялось на всем интервале, и в первом срезе предикат выполнен, для <tex>G</tex> он также выполнен.
===17-18 19 билеты. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для FIFO. Алгоритм для причинно-согласованного порядка. Алгоритм для синхронного порядка ===TODO Порядок * [[Иерархия порядков сообщений:]]# асинхронный (нет * [[Алгоритм для FIFO порядка) # FIFO (сообщения доходят получателю в том порядке, в котором они были ему отправлены в смысле одного потока)# причинно-следственный (если одно сообщение было отправлено раньше другого, то оно будет доставлено раньше другого (в системе целиком, а не в смысле одного потока, как в FIFO)# синхронный (можно выстроить ребра передачи сообщений без пересечений)]]* [[Алгоритм FIFO основан на нумерации сообщений.<br>Псевдокод алгоритма для причинно-согласованного порядка. Вместе с сообщением отправляем матрицу M: M[i, j] — количество сообщений, отправленных процессом i процессу j. '''var''' M:array[l..N, 1..N] of integer initially 0; To send a message to <tex>P_j</tex>: 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 <tex>\land</tex> <tex> \forall k \neq j</tex> <tex>M[k, i] \geqslant W[k, i]</tex> M := max(M, W) ===19 билет. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для синхронного порядка=== Алгоритм для синхронного порядка основан на иерархии процессов.Упорядочим процессы по номеру, назовем сообщение ''большим'', если номер отправителя больше номера получателя, и ''малым'' иначе.Процесс может быть в ''активном'' или ''пассивном состоянии''. Изначально все активны.Процесс может отправить большое сообщение, только если он активен. После отправки он становится пассивным и не может ни отправлять, ни принимать сообщения, пока не получит от получателя ack. Чтобы отправить сообщение большему процессу <tex>P_j</tex>, процесс <tex>P_i</tex> сначала посылает служебное сообщение, ''запрос''. В ответ <tex>P_j</tex> отправляет ''разрешение''; он может сделать это только в активном состоянии. Разрешив, он становится пассивным и остается в этом состоянии, пока не получает сообщение, которое разрешил.]]
===20-21 билеты. Общий порядок (total order). Алгоритмы Лампорта и Скина===
