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

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