Атомарные операции: test-and-set, fetch-and-add и CAS

Если ты знаешь, что делают test-and-set, fetch-and-add и CAS, как написать цикл CAS и почему он дорожает под нагрузкой, листай до «Теперь сам».

Как думаешь, что изменится

В уроке о гонке два потока по два раза делали c = c + 1, и из 924 чередований правильную четвёрку давали шесть. Теперь прибавление делается одной неделимой операцией fetch_add(c, 1). Сколько чередований останется и сколько из них дадут 4?

Ответь себе до чтения. Операций у каждого потока теперь две, а не шесть, и чередований - C(4, 2) = 6. Сколько из шести верны - разбор посчитает перебором.

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

Банкомат и сберкнижка. Если кассир читает остаток, считает на бумажке и вписывает новый, двое кассиров затрут работу друг друга. Банкомат делает списание одной транзакцией: «если на счёте не меньше суммы - списать», и никто не вклинится между проверкой и списанием.

CAS - такая транзакция на одной ячейке памяти: «если там всё ещё 100 - запиши 90, иначе скажи, что не вышло». Не вышло - значит, кто-то успел раньше: перечитай остаток и попробуй снова.

Механизм: три операции и цикл CAS

Все три операции процессор выполняет так, что ни один другой поток не вклинится между чтением и записью:

test_and_set(a):      старое = a; a = 1; вернуть старое
fetch_and_add(a, d):  старое = a; a = старое + d; вернуть старое
cas(a, ожид, новое):  если a == ожид: a = новое; вернуть «да»
                      иначе вернуть «нет»

Замок на test-and-set: пока test_and_set(lock) == 1: ждать, выход - lock = 0. Одна ячейка вместо n: нижняя граница Бёрнса и Линча касалась только чтений и записей, а здесь операция сильнее.

Цикл CAS - универсальный рецепт атомарного обновления x = f(x):

повторять:
    старое = x
    новое = f(старое)
    если cas(x, старое, новое): выйти

Если между чтением и CAS кто-то изменил x, CAS вернёт «нет», и поток повторит попытку с новым значением. Оговорка: если x успели изменить и вернуть прежнее значение, CAS этого не заметит - для счётчика это безвредно, а для указателей это проблема ABAРазбирается в разделе 25, глава «Неблокирующие структуры, консенсус и ABA»: Проблема ABA: CAS видит то же значение, а мир уже другой, о ней речь пойдёт в следующем разделе. Так делают атомарный максимум, добавление в связный список, обновление ссылки на неизменяемый объект. В x86 это инструкция cmpxchg, в ARM - инструкция CAS (расширение LSE) или пара load-linked / store-conditional, в языках - compare_exchange в C++ и Rust, compareAndSet в Java.

Правило

Атомарные операции «прочитать-изменить-записать» неделимы: test-and-set даёт замок на одной ячейке, fetch-and-add - счётчик без гонки, CAS (записать, только если значение не изменилось) - любое атомарное обновление через цикл «прочитать, вычислить, CAS, при неудаче повторить». Под конкуренцией цикл CAS делает лишние попытки, и их число растёт с числом потоков.

Разбор: fetch_add против трёх операций

Тот же перебор всех чередований, что в уроке о гонке, но теперь с двумя режимами: прибавление тремя операциями и одной неделимой.

def itogi(k, atomarno):
    # два потока по k прибавлений; atomarno - fetch_add одной операцией,
    # иначе - прочитать, прибавить, записать
    na_odno = 1
    if not atomarno:
        na_odno = 3
    vsego = k * na_odno
    vstrecheno = {}
    stek = [[0, 0, 0, 0, 0]]
    while len(stek) > 0:
        c, s0, s1, r0, r1 = stek.pop()
        if s0 == vsego and s1 == vsego:
            vstrecheno[c] = vstrecheno.get(c, 0) + 1
            continue
        for t in [0, 1]:
            s = [c, s0, s1, r0, r1]
            if s[1 + t] == vsego:
                continue
            faza = s[1 + t] % na_odno
            if atomarno:
                s[0] = c + 1
            elif faza == 0:
                s[3 + t] = c
            elif faza == 1:
                s[3 + t] = s[3 + t] + 1
            else:
                s[0] = s[3 + t]
            s[1 + t] = s[1 + t] + 1
            stek.append(s)
    otvet = []
    for c in sorted(vstrecheno):
        otvet.append([c, vstrecheno[c]])
    return otvet

print("три операции:", itogi(2, False))
print("fetch_add:   ", itogi(2, True))

три операции: [[2, 702], [3, 216], [4, 6]]
fetch_add:    [[4, 6]]

Тремя операциями - знакомые 924 чередования и три возможных итога. С fetch_add - шесть чередований, и все шесть дают 4. Гонке негде случиться: между чтением и записью больше нет зазора. Это и есть смысл атомарной операции - она уменьшает число «мест», в которые может вклиниться другой поток, до нуля.

Разбор: сколько стоит CAS под нагрузкой

Цикл CAS всегда даёт правильный ответ, но не бесплатно. Смоделируем n потоков, которые наперегонки прибавляют единицу циклом CAS. Каждый шаг планировщик даёт случайному потоку: либо прочитать, либо попытаться CAS. Считаем, сколько попыток CAS уходит на одно успешное прибавление.

import random

def cas_schetchik(n, uspehov, seed):
    # n потоков крутят цикл: прочитать c, потом CAS(c, старое, старое+1);
    # планировщик каждый раз выбирает случайный поток для одного шага
    random.seed(seed)
    c = 0
    prochital = [None] * n
    popytok = 0
    while c < uspehov:
        t = random.randint(0, n - 1)
        if prochital[t] == None:
            prochital[t] = c
        else:
            popytok = popytok + 1
            if c == prochital[t]:
                c = c + 1
            prochital[t] = None
    return round(popytok / uspehov, 2)

print("потоков  попыток CAS на одно прибавление")
for n in [1, 2, 4, 8, 16, 32]:
    print(n, cas_schetchik(n, 400, n))

потоков  попыток CAS на одно прибавление
1 1.0
2 1.39
4 1.98
8 2.67
16 3.77
32 5.44

Один поток - ровно одна попытка на прибавление. Два - 1,39: иногда между чтением и CAS вклинивается сосед. Тридцать два - 5,44: больше четырёх попыток из пяти пропадают зря. Каждая неудачная попытка на настоящем процессоре обычно означает захват строки кеша у другого ядра - сообщения по шине. Поэтому общий счётчик, в который пишут все, - узкое место даже без единой блокировки: на десятках ядер его делят на части (по счётчику на поток или на ядро) и складывают при чтении. Так устроены LongAdder в Java и счётчики статистики в ядре Linux.

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

Проверка и запись отдельно. if x == old: x = new в обычном коде - те же две операции с зазором; CAS делает их одной инструкцией. Свой «CAS» из if и присваивания - гонка.

Бесконечный цикл CAS без изменения входа. Если новое вычислено один раз до цикла, а не от свежего старое, каждая повторная попытка пишет устаревшее значение - и успешный CAS затирает чужое обновление.

Горячая ячейка. Миллион инкрементов в секунду на одном счётчике с 64 ядер: попыток становится в разы больше успехов, и счётчик тормозит всю программу.

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

Атомарные операции - фундамент всех средств синхронизации: мьютекс в pthread, std::mutex и sync.Mutex в Go в быстром случае - это один CAS без обращения к ядру ОС. Счётчики ссылок shared_ptr и Arc - это fetch_add. В базах данных оптимистичная блокировка UPDATE ... SET v = v + 1, version = 6 WHERE id = 1 AND version = 5 - тот же CAS на уровне строки, с тем же повтором при неудаче.

Теперь сам

1. Напиши атомарный максимум x = max(x, y) циклом CAS. Когда цикл может выйти, не делая CAS вовсе?
2. Два потока одновременно вызывают test_and_set на свободном замке. Что вернётся каждому?
3. Почему замок на test-and-set не противоречит границе в n ячеек из прошлой главы?