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

Предположим, что каждый компонент однорайтерного объекта моментального снимка представлен однорайтерным регистром. Процесс i выполняет операцию обновления update(i, v), записывая v и порядковый номер в регистр i и увеличивая его порядковый номер. Выполнить операцию сканирования сложнее, чем просто прочитать каждый из m регистров, поскольку в ходе чтения некоторые регистры могут измениться. Чтобы выполнить сканирование, процесс неоднократно считывает все регистры. Последовательность считываний всех регистров называется ''сбором''. Если два сбора возвращают один и тот же вектор, то сканирование возвращает этот вектор (с обрезанными порядковыми номерами). Порядковые номера гарантируют, что если одно и то же значение читается в регистре дважды, то регистр содержал это значение в течение всего интервала между двумя считываниями. Сканирование может быть назначено точкой линеаризации между двумя одинаковыми сборами, а обновления линеаризуются при выполнении операции записи. Этот алгоритм является неблокирующим, поскольку сканирование продолжается только в том случае, если во время каждого сбора завершается хотя бы одна операция обновления. Аналогичный алгоритм с идентификаторами процессов, добавляемыми к номерам последовательностей, реализует неблокирующий мультирайтерный моментальный снимок из m мультирайтерных регистров.

Афек и др. [1] предложили способ модификации неблокирующего однорайтерного алгоритма выполнения моментального снимка, позволяющий сделать его свободным от ожидания, встроив сканирование в операции обновления. Обновление update(i, v) сначала выполняет сканирование, а затем записывает тройку, содержащую результат сканирования, v и порядковый номер, в регистр i. Пока процесс P неоднократно выполняет процесс сбора для выполнения сканирования, имеет место одна из двух ситуаций: либо два сбора возвращают один и тот же вектор (который P может вернуть), либо P в конце концов увидит три разные тройки в регистре какого-то другого процесса. В последнем случае третья тройка, которую увидел P, должна содержать вектор, являющийся результатом сканирования, начавшегося уже после сканирования P, поэтому сканирование P выводит этот вектор. Обновлениям и сканированиям, которые завершаются после просмотра двух идентичных сборов, назначаются точки линеаризации описанным ранее способом. Если один скан получает свой вывод от встроенного скана, то оба скана получают одну и ту же точку линеаризации. Это не требующая ожидания реализация однорайтерного моментального снимка из n однорайтерных регистров по (n + 1)d + log k бит каждый. Операции выполняются за <math>O(n^2)</math> шагов. Афек и др. в работе [1] также говорят о том, как заменить неограниченные порядковые номера битами «рукопожатия». Для этого требуется <math>n \Theta(nd)</math>-битных регистров и <math>n^2</math> 1-битных регистров; операции по-прежнему выполняются за <math>O(n^2)</math> шагов.