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

Андерсон [3] предложил реализацию мультирайтерного снимка из однорайтерного. Каждый процесс хранит свое последнее обновление каждого компонента мультирайтерного снимка в однорайтерном снимке с соответствующими данными временной метки, вычисленными путем сканирования однорайтерного снимка. Операция сканирования выполняется с помощью однократного сканирования однорайтерного снимка. Для обновления требуется дважды просканировать и обновить однорайтерный снимок. Реализация предполагает некоторое увеличение размеров компонентов, т. е. для реализации мультирайтерного снимка с областью D требуется однорайтерный снимок с гораздо большей областью D'. Если целью является реализация мультирайтерных снимков из однорайтерных регистров (а не мультирайтерных), то построение Андерсона дает более эффективное решение, чем у Афека и коллег.

Аттия и Фурэн [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).

Аттия, Херлихи и Рахман [7] предложили элегантное рекурсивное решение проблемы решеточного согласования по принципу «разделяй и властвуй». Разделение процессов на группы для рекурсии может быть выполнено динамически с помощью объектов типа «проверка и установка» (test&set). В результате получается алгоритм взятия снимка, который выполняется за время O(n) на одну операцию и использует <math>O(kn2^ \; log \; n)</math> небольших однорайтерных регистров и <math>O(kn \; log^2 \; n)</math> объектов «проверка и установка». (Он требует модификации их предыдущей реализации для замены больших регистров, которые записываются только один раз, на несколько небольших). Используя рандомизацию, каждый объект «проверка и установка» можно заменить однорайтерными регистрами, чтобы получить реализацию моментального снимка, используя только регистры, с O(n) ожидаемых шагов на операцию.

Джаянти [13] представил мультирайтерную реализацию моментального снимка из <math>O(mn^2)</math> небольших объектов типа «сравнение с обменом» (compare&swap), в которой обновление занимает O(1) шагов, а сканирование – O(m) шагов. Он начинается с очень простой односканерной и однорайтерной реализации моментального снимка из регистров, которая использует вспомогательный массив для хранения копий последних обновлений. Операция сканирования очищает этот массив, собирает основной массив, а затем собирает вспомогательный, чтобы найти пропущенные обновления. Для получения мультисканерного и мультирайтерного снимка общего вида вводится несколько дополнительных механизмов. В частности, операции сравнения с обменом используются вместо операций записи для координации процессов-райтеров, обновляющих один и тот же компонент, а несколько сканеров координируются друг с другом для имитации работы одного сканера. Алгоритм Джаянти основывается на более ранней работе Риани, Шавита и Туиту [16], в которой была приведена реализация, достигающая аналогичной сложности, но только для однорайтерного снимка.

Некоторые нижние границы сложности для реализаций из регистров известны [9], но остаются пробелы между лучшими известными алгоритмами и лучшими нижними границами. В частности, неизвестно, существует ли эффективная реализация моментальных снимков из небольших регистров без ожидания.