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

Аттия, Херлихи и Рахман [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], в которой была приведена реализация, достигающая аналогичной сложности, но только для однорайтерного снимка.