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

Афек и др. [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> шагов.

Та же идея может быть использована для создания мультирайтерных снимков из мультирайтерных регистров. Использование неограниченных порядковых номеров позволяет получить алгоритм без ожидания, использующий m регистров, хранящих по <math>\Theta(nd \; + \; log \; k)</math> бит, в котором каждая операция завершается за O(mn) шагов. (Этот алгоритм в явном виде приведен в работе [9]). Ни один алгоритм не может использовать меньше m регистров, если <math>n \ge m</math> [9]. Если вместо этого используются биты рукопожатия, то алгоритм мультирайтерного моментального снимка использует <math>n^2</math> 1-битных регистров, m(d + log n)-битных регистров и n (md)-битных регистров, а каждая операция требует <math>O(nm + n^2)</math> шагов [1].

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

Аттия, Херлихи и Рахман [3] определили объект ''«решеточное согласование»'' (lattice agreement), очень тесно связанный с задачей реализации однорайтерного моментального снимка при известной верхней границе на k. Затем они показали, как построить однорайтерный снимок (без ограничения на k) из бесконечной последовательности таких объектов. Каждая операция с моментальным снимком дважды обращается к объекту решеточного согласования и выполняет O(n) дополнительных шагов. Их реализации решеточных согласований обсуждаются в разделе «Не требующие ожидания реализации на основе небольших и более сильных объектов».