Конспект: атомарные операции, спин-блокировки и линеаризуемость

Понятия

Атомарная операция «прочитать-изменить-записать» неделима: test-and-set, fetch-and-add, compare-and-swap (CAS - записать, только если значение всё ещё ожидаемое).

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

История - вызовы и ответы с временем. Линеаризуемость - операции можно выстроить по точкам внутри их интервалов в допустимую последовательную работу; точка линеаризации - момент, где операция «случается».

Гарантии прогресса: obstruction-free (один закончит), lock-free (кто-то закончит), wait-free (каждый закончит за ограниченное число шагов).

Что унести

АТОМАРНЫЕ ОПЕРАЦИИ
test_and_set: замок на ОДНОЙ ячейке (граница n - для чтений и записей)
fetch_add: 2 потока по 2 прибавления - 6 чередований, все дают 4
цикл CAS:  повторять: старое = x; новое = f(старое);
           если cas(x, старое, новое): выйти
под нагрузкой: попыток на прибавление 1,0 / 1,39 / 5,44 (1, 2, 32 потока)
горячий счётчик дробят по потокам: LongAdder, percpu-счётчики

СПИН-БЛОКИРОВКИ       ожидание            передача        честность
TAS                   запись в цикле      ~3n сообщений   нет
TTAS                  чтение своей копии  ~2n (всплеск)   нет
талоны (fetch_add)    чтение общей ячейки ~n              n − 1 обгонов
MCS / CLH             своя ячейка         3-5, не растёт  очередь
16 ядер, обгоны: TAS - 94 из 100, талоны - 15
ложное разделение: замок и горячая переменная в одной строке
Linux: TAS → талоны (2008) → qspinlock, вариант MCS (2015)

ЛИНЕАРИЗУЕМОСТЬ (Херлихи, Уинг, 1990)
порядок подходит: закончившаяся раньше начала другой стоит раньше,
                  и последовательный объект даёт записанные ответы
посл. согласованность: только порядок внутри клиента
enq(1) [0,1], enq(2) [2,3], deq → 2: согласована, не линеаризуема
композиционна; проверка в общем случае NP-полна
счётчик: номера 0..m−1 различны, раньше закончившийся - меньший
CAS-счётчик: 40 историй из 40 верны; «прочитал-записал»: 0 из 40

ПРОГРЕСС
взаимоблокировка - 4 условия Коффмана, цикл ожидания
общий порядок захвата: 75 блокировок из 200 → 0
поток уснул с замком: остальные - 0 прибавлений; с CAS - 122-137
цикл CAS - lock-free, не wait-free; fetch_add - wait-free
инверсия приоритетов (Mars Pathfinder, 1997) - наследование приоритета

Ловушки джокера

Свой CAS из if и присваивания. Проверка и запись с зазором - та же гонка.

Новое значение вне цикла CAS. После неудачи успешный CAS пишет устаревшее значение, счётчик может даже уменьшиться.

Цикл test_and_set на многоядерной машине. Ожидающие своими записями тормозят и друг друга, и владельца.

Спин там, где владелец может уснуть. Ожидающие жгут процессор; нужен мьютекс со сном.

Устаревший ответ после подтверждённой записи. Последовательная согласованность его допускает, линеаризуемость - нет; клиенту это выглядит как потерянная запись.

Захват замков в разном порядке. Цикл ожидания и вечная взаимоблокировка.

Замок как гарантия прогресса. Один остановившийся владелец останавливает всех.

«Lock-free» в системе реального времени. Отдельный поток может проигрывать сколько угодно раз.

• Экспоненциальный откат TTAS: после проигранного захвата случайная пауза из растущего ограниченного окна; одинаковые задержки сохраняют синхронность. Откат не даёт FIFO и не исключает голодания.

• Атомарный снимок: двойной collect сравнивает версии; без помех завершается, но может голодать. Wait-free scan берёт сохранённую помощь писателя после второго замеченного движения; O(n²) чтений.