Атомарность и неблокирующие структуры

Можно синхронизироваться и без блокировок — на атомарных операциях процессора.

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

Гонка возникает потому, что x += 1 делимая. А что если бы существовала команда «прибавь 1 целиком, не давая никому вклиниться»? Такие команды есть на уровне процессора — это атомарные инструкции, и на них строят неблокирующие (lock-free) структуры данных.

Compare-and-swap (CAS)

Краеугольная атомарная операция — compare-and-swap: «если в ячейке всё ещё старое значение, замени его на новое; иначе сообщи, что не вышло». Всё это — за одну неделимую инструкцию.

def compare_and_swap(cell, expected, new):
    # атомарно: сравнить и при совпадении заменить
    if cell["value"] == expected:
        cell["value"] = new
        return True
    return False

cell = {"value": 5}

# поток прочитал 5 и пытается заменить на 6
print(compare_and_swap(cell, 5, 6))  # успех
print(cell["value"])
# повтор с устаревшим ожиданием 5 -> провал (значение уже 6)
print(compare_and_swap(cell, 5, 7))

Вывод:

True
6
False

Цикл повтора вместо ожидания

На CAS строят неблокирующий инкремент: прочитали значение, посчитали новое, попытались CAS; если кто-то опередил — повторяем с новым прочитанным значением. Поток не засыпает на блокировке, а «крутится» до успеха.

while True:
    old = read(counter)
    new = old + 1
    if compare_and_swap(counter, old, new):
        break          # удалось без блокировок

Плюсы и минусы lock-free

Как работает под капотом

Атомарные инструкции (CAS, fetch-and-add) реализованы аппаратно: процессор гарантирует их неделимость через протокол согласования кэшей между ядрами. В Python из-за GIL вам редко нужны lock-free структуры в чистом виде, но именно на CAS внутри построены сами мьютексы и потокобезопасные очереди. Классическая засада lock-free — проблема ABA: значение поменялось с A на B и обратно на A, CAS видит «A на месте» и ошибочно считает, что ничего не происходило.

Частые ошибки

• Считать любую операцию атомарной. Атомарность нужно обеспечивать явно; по умолчанию составные операции делимы.
• Забывать про ABA. Простой CAS не отличает «не менялось» от «менялось и вернулось».
• Тянуть lock-free туда, где хватит обычной блокировки. Это сложный инструмент; чаще достаточно мьютекса или очереди.

Итог

• Атомарная операция неделима для других потоков.
• Compare-and-swap — основа неблокирующих структур.
• Lock-free избегает deadlock, но сложен и страдает от проблемы ABA.
• На CAS внутри построены сами блокировки и очереди.