Атомарный снимок: значения из одного момента

Если механизм уже знаком - листай до «Теперь сам».

Как думаешь: что нужно сохранить

Два счётчика прошли состояния (0,0)→(1,0)→(1,1). Сканер сначала прочитал первый ноль, затем последний второй один. Он получил (0,1), которого никогда не было. Каждое чтение атомарно, число существует и не повреждено. Чего не хватает результату? Нужен один момент между вызовом и возвратом scan, в котором существовал весь набор вместе.

На что это похоже

Представь групповую фотографию, которую собирают из кадров отдельных людей. У каждого кадра правильная дата, но один человек уже ушёл, когда другой только пришёл. Такой монтаж не доказывает, что группа собиралась. Два одинаковых обхода с версиями подтверждают стабильное пересечение интервалов; помощь писателя даёт готовую фотографию, сделанную тогда, когда собственная камера сканера никак не успевала.

Механизм: от определения к алгоритму

Атомарный снимок возвращает массив значений, который существовал целиком в некоторый момент между началом и концом операции. Рассмотрим n регистров, по одному писателю на регистр; каждый может читать все. Регистр хранит неизменяемую запись целиком, её чтение и замена атомарны. Версии монотонно растут и в математической модели не переполняются.

Collect копирует записи по одной. Выполни collect дважды. Если версии всех компонент совпали, ни один регистр не менялся между двумя своими чтениями. Конец первой выборки предшествует началу второй, значит существует общий промежуток, которому соответствует весь результат. Проблема ABA - значение сменилось с A на B и вернулось к A, а проверка равенства приняла это за отсутствие изменений. Без версий запись могла пройти такой цикл; равенство значений скрывает движение.

Повторение до совпадения даёт корректный, но лишь obstruction-free scan: без помех он завершается, при постоянных помехах может голодать. Чтобы получить wait-free, писатель перед публикацией нового значения сам выполняет scan и сохраняет результат в записи (version,value,snapshot). Сканер ведёт флаги moved[i]. При первом изменении версии писателя запоминает движение и повторяет выборку. Если снова замечает движение того же писателя, возвращает снимок из его новой записи.

Почему нельзя взять помощь при первом движении? Писатель мог начать свой scan ещё до начала нашего вызова. А при втором наблюдаемом движении у одного писателя между ними поместилось целое обновление вместе с его scan. Его снимок имеет точку линеаризации внутри нашего интервала и подходит для ответа. При n писателях после ограниченного числа неуспешных выборок кто-нибудь будет замечен второй раз. Поэтому scan делает O(n²) чтений регистров и завершается за ограниченное число собственных шагов. Сохранённые снимки требуют O(n²) значений памяти.

Правило

Для безопасного scan сравнивай версии; для wait-free завершения добавляй помощь писателей и используй её только после второго замеченного движения одного писателя.

Разбор: проследим вычисление

Сначала явно воспроизведём несуществующий вектор. Затем модель с версиями отвергнет нестабильную пару выборок и примет следующую стабильную. Писатели в модели меняются по заданному сценарию, поэтому вывод воспроизводим. Это объяснение проверки clean double collect, а не реализация wait-free scan: помощь описана отдельно и здесь не исполняется.

history = [(0, 0), (1, 0), (1, 1)]
bad = (history[0][0], history[2][1])
print("раздельные чтения", bad, "было вместе", bad in history)

# Неизменяемые записи: (версия, значение).
registers = [(0, 0), (0, 0)]

def collect():
    return tuple(registers)

def same_versions(a, b):
    return all(x[0] == y[0] for x, y in zip(a, b))

first = collect()
registers[0] = (1, 1)
registers[1] = (1, 1)
second = collect()
print("первые версии совпали", same_versions(first, second))
third = collect()
assert same_versions(second, third)
print("снимок", tuple(value for stamp, value in third))

# ABA: значение вернулось, версия продолжила расти.
before = (5, 7)
after = (7, 7)
assert before[1] == after[1] and before[0] != after[0]
print("ABA: значения равны", before[1] == after[1])
print("ABA: версии равны", before[0] == after[0])
# Первое движение ещё не доказывает свежесть чужого снимка.
scan_start, writer_start, writer_end = 10, 8, 12
assert writer_start < scan_start < writer_end
print("помощь первого движения могла начаться раньше", True)

раздельные чтения (0, 1) было вместе False
первые версии совпали False
снимок (1, 1)
ABA: значения равны True
ABA: версии равны False
помощь первого движения могла начаться раньше True

Разбор: где проходит граница

Один писатель обновляется перед каждой второй выборкой. Сканер получает версии 1,2,3,… и никогда не видит чистую пару. Ни одного неверного ответа нет, но ответа вообще нет. В алгоритме с помощью после второго замеченного обновления этого писателя уже есть подходящий сохранённый снимок. Это переход от «если вернул, то правильно» к гарантии, что вызов завершится после ограниченного числа собственных шагов.

Что ломается без этого

Сравнение только значений пропускает ABA. Неатомарная публикация полей записи позволяет прочитать новую версию со старым значением. Помощь при первом движении может отдать состояние до начала вызова. Переполнение конечного счётчика разрушает доказательство монотонности: практической реализации нужен дополнительный протокол либо обоснованный размер и срок работы. Простой Python-список не следует объявлять реализацией регистра на любой архитектуре.

Зачем это в работе

Снимки нужны, когда согласованность нескольких источников важнее независимой свежести каждого: контрольные точки, наблюдение конкурентных структур, согласованные отчёты. Обычный mutex вокруг всех обновлений и чтений часто проще. Алгоритм снимка нужен там, где требуется неблокирующий прогресс и известна модель регистров. Сначала определи число писателей на компоненту и смысл общего момента, затем выбирай реализацию.

Теперь сам

Состояния (2,4)→(3,4)→(3,5). Сканер вернул (2,5). Допустим ли этот снимок? А результат (3,4) при вызове, охватывающем все три состояния?