Моментальные снимки в разделяемой памяти: различия между версиями

Аттия и Фурэн [5] решают задачу решеточного согласования за O(n) шагов. (В этом случае вместо использования терминологии решеточного согласования алгоритм описывается в терминах реализации моментальных снимков, в котором каждый процесс выполняет не более одной операции взятия снимка). В качестве структуры данных алгоритм использует двумерный массив из <math>O(n^2)</math> ''матриц отражения''. Матрица отражения – это объект, который может использоваться двумя процессами для обмена информацией. Каждая матрица отражения строится из двух больших однорайтерных регистров. Каждый процесс выбирает свой путь через массив матриц отражения таким образом, что каждую матрицу посещают не более двух процессов. Каждый элемент матрицы отражения в столбце i используется процессом i для обмена информацией с одним процессом j < i. Если процесс i достигает матрицы первым, то процесс j узнает об обновлении i (если оно было). Если первым ее достигает процесс j, то процесс i узнает всю информацию, которую уже собрал j. (Если оба процесса доходят до матрицы примерно в одно и то же время, то они получают информацию, описанную выше). По мере того как процессы перемещаются из столбца i - 1 в столбец i, процесс, который входит в столбец i в некоторой строке r, собирает всю информацию, которая была собрана любым процессом, который входит в столбец i ниже строки r (и, возможно, больше). Этот инвариант поддерживается следующим образом: если процесс i передает информацию любому процессу j < i в строке r столбца i, то он также передает эту информацию всем процессам, которые вошли в столбец i выше строки r. Кроме того, процесс i выходит из столбца i в строке, соответствующей количеству информации, которую он узнал, перемещаясь по этому столбцу. Когда процессы достигают крайнего правого столбца массива, процессы, находящиеся в более высоких строках, знают строго больше, чем процессы, находящиеся в более низких строках. Таким образом, порядок линеаризации их сканирования – это порядок выхода из крайнего правого столбца, считая снизу вверх. Упомянутые выше методы Аттии, Херлихи и Рахмана [7, 8] могут быть использованы для снятия ограничения, которое гласит, что каждый процесс выполняет не более одной операции. При этом количество шагов на одну операцию по-прежнему остается O(n).