Chapter 11 · Synchronization Primitives and Patterns

11.3 Атомарные операции

sync/atomic — это уровень примитивов синхронизации Go, расположенный ближе всего к аппаратуре. Все более высокоуровневые инструменты — мьютекс (11.1) и каналы (8) — внутри построены на атомарных операциях. Пакет обеспечивает «неделимые» чтения, записи и операции «чтение–модификация–запись»: атомарная операция либо выполняется целиком, либо не выполняется вовсе, и ни одна горутина никогда не видит её в незавершённом состоянии. Однако смысл атомарных операций простирается далеко за пределы «отсутствия частичной записи». Они составляют фундамент неблокирующего (lock-free) программирования, а за неблокирующим программированием стоит глубокая теория о том, «какой примитив на что способен». Именно эту теорию данный раздел стремится прояснить.

Сначала мы рассмотрим базовые операции и обоснуем центральную роль CAS; затем отступим на шаг назад и воспользуемся иерархией консенсуса Херлихи, чтобы ответить на вопрос «почему именно CAS»; далее погрузимся в подводные камни неблокирующего программирования — проблему ABA и безопасное освобождение памяти, — чтобы объяснить, почему Go хранит сложные неблокирующие структуры данных внутри рантайма; и наконец вернёмся к инженерной стороне вопроса, рассмотрев гарантию последовательной согласованности sync/atomic и эволюцию Go 1.19, которая закодировала принцип «к этой переменной следует обращаться атомарно» в систему типов.

11.3.1 Базовые операции

Семейство атомарных операций невелико: Load (атомарное чтение), Store (атомарная запись), Add (атомарный инкремент/декремент), Swap (атомарный обмен), CompareAndSwap (сравнение с обменом, CAS), а также And/Or (атомарные побитовые операции), добавленные в Go 1.23. Все они сводятся к единственной машинной инструкции с префиксом LOCK: на x86 CAS — это LOCK CMPXCHG, на ARMv8 — пара load-linked / store-conditional LDXR/STXR с повторной попыткой, а сложение — LOCK XADD. Иными словами, конечная гарантия атомарности обеспечивается аппаратурой, а sync/atomic лишь оборачивает эти инструкции в переносимые функции Go.

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

1
2
3
4
5
6
7
8


// Семантика CompareAndSwap (псевдокод, выполняемый неделимо как единое целое)
func CompareAndSwapInt64(addr *int64, old, new int64) (swapped bool) {
    if *addr == old {
        *addr = new
        return true
    }
    return false
}

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

1
2
3
4
5
6
7
8


for {
    old := atomic.LoadInt64(&x)   // прочитать текущее значение
    new := f(old)                 // вычислить ожидаемое новое значение
    if atomic.CompareAndSwapInt64(&x, old, new) {
        break                     // никто не успел раньше; фиксация прошла успешно
    }
    // неудачный CAS означает, что другая горутина изменила x первой; берём новое значение и пересчитываем
}

flowchart TD
    S["Хотим изменить x со старого значения на новое"] --> L["Читаем текущее значение cur"]
    L --> CMP["Вычисляем ожидаемое новое значение на основе cur"]
    CMP --> CAS{"CompareAndSwap(x, cur, new) успешен?"}
    CAS -->|успех| DONE["Фиксация выполнена"]
    CAS -->|"неудача: кто-то изменил x первым"| L

Этот цикл скрывает в себе стоимость неблокирующего программирования. В отличие от блокировки, неудачный CAS не блокирует горутину, а немедленно повторяет попытку. При невысокой конкуренции это выгодная сделка, позволяющая обойтись без захвата блокировки, потенциального засыпания и пробуждения; однако при острой конкуренции множество горутин раз за разом считывают перезаписанные друг другом значения и раз за разом терпят неудачу CAS — процессор целиком расходуется на активное ожидание, и пропускная способность оказывается хуже, чем при обычной блокировке. Существует и ещё одна угроза — livelock (активная взаимоблокировка): все горутины повторяют попытки, система в целом выглядит функционирующей, однако конкретная горутина может долго не добиться фиксации. Поэтому атомарные операции подходят для сценариев с обращением к единственному слову, невысокой конкуренцией или преобладанием чтения: счётчики, флаги, указатели на конфигурацию и тому подобное; принудительное разложение сложной критической секции в CAS-цикл, как правило, не оправдывает себя.

11.3.2 Иерархия консенсуса: почему именно CAS

У читателя может возникнуть вопрос: раз Load и Store тоже атомарны, почему нельзя строить неблокирующие структуры данных на их основе и необходимо настаивать на CAS? Ответ даёт классическая работа Херлихи 1991 года — иерархия консенсуса, которая вводит точную, доказуемую меру того, «насколько силён данный примитив синхронизации».

Рассмотрим $n$ потоков, которые должны согласовать единственное значение: каждый поток предлагает своё значение, и в итоге все потоки обязаны прочитать одно и то же выбранное предложение, причём оно действительно должно быть одним из предложенных. Наибольшее $n$ , для которого некоторый разделяемый объект способен решить задачу консенсуса среди $n$ потоков без ожидания (wait-free) — каждый поток завершает работу за ограниченное число шагов независимо от действий остальных — называется числом консенсуса этого объекта.

flowchart LR
    RW["Атомарный регистр чтения/записи<br/>число консенсуса = 1"] --> FAA["FetchAndAdd / Swap / очередь / стек<br/>число консенсуса = 2"]
    FAA --> CAS["CompareAndSwap / LL-SC<br/>число консенсуса = ∞"]

Обычный атомарный регистр чтения/записи имеет число консенсуса лишь 1 и неспособен координировать даже два потока. Интуитивно доказательство выглядит так: чтобы два потока достигли консенсуса о том, «кто пришёл первым», должен существовать критический момент, в котором состояние системы балансирует между «в конечном итоге будет выбран A» и «в конечном итоге будет выбран B». С регистром чтения/записи первый из двух потоков может лишь прочитать или записать некоторую ячейку. Если он читает — он не оставляет следа, и второй поток не может определить, был ли первый здесь; если он пишет — либо он записывает в ячейку, которую второй поток немедленно перезапишет (след стирается), либо оба записывают в разные ячейки, и тогда порядок чтения вторым потоком не позволяет определить, кто пришёл первым. Как бы ни чередовались шаги, всегда можно построить такое исполнение, которое два потока не смогут различить, — поэтому wait-free консенсус невозможен. Это классический результат невозможности, восходящий к той же линии, что и теорема FLP.

Напротив, число консенсуса CAS равно бесконечности. Доказательство поразительно кратко: возьмём разделяемую ячейку, инициализированную значением «победитель не определён», и каждый поток выполнит CompareAndSwap(&cell, empty, my proposal); только первый, кому это удаётся, записывает в ячейку своё значение, все остальные терпят неудачу, после чего все потоки читают cell и видят единственного победителя. Единственная строчка с CAS позволяет произвольному числу потоков достичь wait-free консенсуса.

Этот разрыв между $1$ и $\infty$ — фундаментальная причина, по которой библиотека атомарных операций каждого языка программирования ставит CAS в центр. Далее Херлихи доказал, что любой примитив с числом консенсуса $\infty$ является универсальным: с его помощью любой последовательный объект может быть механически преобразован в эквивалентную wait-free параллельную реализацию (так называемая универсальная конструкция). CAS для мира неблокирующего программирования — то же, что машина Тьюринга для теории вычислимости: универсальный ключ. Пара load-linked / store-conditional (LL/SC), используемая в архитектурах ARM и POWER, — близкий родственник CAS, также обладающий числом консенсуса $\infty$ ; тогда как FetchAndAdd, Swap и даже атомарные очереди и стеки останавливаются на числе консенсуса 2 и не способны обеспечить wait-free координацию произвольного числа потоков. Go предоставляет пользователям Add/Swap/CAS в равной мере, однако только CAS способен выдержать произвольный неблокирующий алгоритм — именно поэтому.

11.3.3 Уровни гарантий: блокирующий, lock-free, wait-free

«Lock-free» (неблокирующий) — это на самом деле целое семейство гарантий различной силы. В книге The Art of Multiprocessor Programming Херлихи и Шавит формулируют стандартную трёхуровневую иерархию прогресса:

Obstruction-free (без препятствий): если поток в какой-то момент выполняется эксклюзивно (все остальные приостановлены), ему гарантируется завершение за ограниченное число шагов. Это самая слабая гарантия: при одновременном продвижении нескольких потоков они могут мешать друг другу так, что ни один не завершит операцию (livelock).
Lock-free (без блокировок): в любой момент, пока система продолжает работать, какой-либо поток всегда способен завершить свою операцию. Это исключает deadlock и livelock и гарантирует, что система в целом продвигается вперёд, но не гарантирует, что отдельный поток не будет голодать. Типичный пример — CAS- цикл из предыдущего раздела: каждый раз, когда чей-то CAS терпит неудачу, чей-то другой CAS обязательно завершается успехом.
Wait-free (без ожидания): каждый поток завершает работу за ограниченное число шагов, независимо от поведения остальных. Это самая сильная и самая сложная в реализации гарантия, обычно достигаемая ценой более сложных алгоритмов и более высоких постоянных накладных расходов.

flowchart TD
    WF["wait-free<br/>каждый поток завершает за ограниченное число шагов (сильнейшая)"] --> LF["lock-free<br/>какой-либо поток всегда продвигается, нет deadlock/livelock"]
    LF --> OF["obstruction-free<br/>завершает при эксклюзивном выполнении"]
    OF --> BL["blocking<br/>если держатель блокировки заблокирован, все останавливаются"]

Стоит развеять распространённое заблуждение: каналы и мьютексы Go используют CAS внутри, однако сами по себе являются блокирующими примитивами — они заставляют горутины блокироваться и отдавать управление. Использование атомарных инструкций не равнозначно понятию «lock-free»; lock-free — это гарантия прогресса, а не описание техники реализации. Подлинное стремление к lock-free свойственно специализированным параллельным структурам данных, таким как стек Трейбера и очередь Майкла–Скотта. Рассмотрим простейший стек Трейбера в качестве примера: он сводит всю lock-free операцию push к одному CAS-циклу:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


// Push для lock-free стека: обёртка CAS-цикла из 11.3.1 вокруг «подмены вершины стека»
type node struct {
    val  int
    next *node
}
type Stack struct {
    top atomic.Pointer[node] // вершина стека, типизированный атомарный указатель Go 1.19
}

func (s *Stack) Push(v int) {
    n := &node{val: v}
    for {
        old := s.top.Load()  // прочитать текущую вершину
        n.next = old         // направить новый узел на неё
        if s.top.CompareAndSwap(old, n) {
            return           // вершина не изменилась; узел успешно присоединён
        }
        // кто-то изменил вершину первым; повторяем с новой вершиной
    }
}

Этот код выглядит безобидным, однако именно он становится запалом для подводного камня следующего раздела.

11.3.4 ABA и безопасное освобождение памяти: подводные камни lock-free

CAS имеет известную ловушку — проблему ABA. Поток читает значение A и готовится выполнить CAS; тем временем другой поток изменяет значение с A на B и обратно на A; CAS видит «по-прежнему A» и считает, что никто не вмешивался, фиксируя результат, тогда как в действительности структура давно изменена до неузнаваемости.

Подставим это обратно в стек Трейбера для наглядности: поток 1 выполняет Load вершины и видит узел A, замечая, что A.next указывает на B, и готовится выполнить CompareAndSwap(A, B), чтобы извлечь A. В этот момент поток 2 дважды подряд извлекает узлы, удаляя и A, и B, а затем помещает обратно новый узел A’, повторно использующий блок памяти A; next у A’ давно указывает в другое место. CAS потока 1 сравнивает значения указателей: A’ имеет тот же адрес, что и A, поэтому CAS завершается успешно, вершина стека устанавливается на узел, чей next уже невалиден, и стек оказывается повреждён. Корень проблемы двоякий: CAS распознаёт лишь значения, а не «что произошло между чтением и записью», и память извлечённого узла была освобождена и повторно использована преждевременно.

Классические контрмеры делятся на две категории. Первая — присоединение номера версии / тега к указателю (tagged pointer): тег инкрементируется при каждой модификации, и ABA обнаруживается как $A_1 \neq A_3$ ; CAS сравнивает «указатель + тег» целиком, и повторное использование того же адреса не может его обмануть. Ценой является необходимость инструкции, способной атомарно оперировать значением двойной ширины слова (на x86 — LOCK CMPXCHG16B), а также неизбежное переполнение тега. Вторая — решение фундаментального вопроса «когда память может быть безопасно освобождена», более глубокий класс методов:

Hazard pointers (Michael, 2004): каждый поток регистрирует указатель, с которым он сейчас работает, в публичном массиве; перед фактическим освобождением утилизатор просматривает этот массив и откладывает освобождение всех зарегистрированных указателей.
Epoch-based reclamation (освобождение на основе эпох): глобально инкрементируемая «эпоха» формирует поколения, и лишь после подтверждения того, что все потоки пересекли определённую эпоху, узлы, отставленные до неё, безопасно освобождаются.
RCU (read-copy-update): парадигма ядра Linux, при которой читатели несут практически нулевые накладные расходы, а писатели копируют данные и откладывают освобождение.

sequenceDiagram
    participant T1 as Поток 1
    participant Top as Вершина стека
    participant T2 as Поток 2
    T1->>Top: Load читает A, замечает A.next=B
    T2->>Top: извлекает A, извлекает B
    T2->>Top: помещает обратно новый узел A', повторно использующий память A
    T1->>Top: CAS(A, B) ошибочно считает, что ничего не изменилось; успех
    Note over Top: вершина указывает на устаревший узел, структура повреждена

Таков контекст решения Go не поощрять пользователей к написанию сложных неблокирующих структур данных вручную. Корректность неблокирующего программирования исключительно хрупка: ABA и безопасное освобождение памяти — подводные камни, на которых раз за разом ошибаются даже опытные разработчики. Кроме того, Go располагает сборщиком мусора: сборка мусора естественным образом устраняет один класс проблем ABA, поскольку пока какой-либо указатель ссылается на узел, тот не будет освобождён и повторно использован, — поэтому atomic.Pointer[T] значительно безопаснее, чем CAS с голым указателем в C (сборщик мусора действует как автоматическая схема безопасного освобождения памяти). Тем не менее Go по-прежнему хранит по-настоящему сложные неблокирующие структуры внутри рантайма — очереди с перехватом работы в шедулере, неблокирующие множества span в аллокаторе памяти (12.2) — многократно отполированные быстрые пути — и предоставляет пользовательскому уровню лишь базовые примитивы с рекомендацией отдавать предпочтение каналам и блокировкам. Это тот же компромисс «сложность — внутри», что и в решении 11.9 предоставлять только последовательно согласованные атомарные операции, но не операции со слабым упорядочением.

11.3.5 Атомарные операции последовательно согласованы

Все операции sync/atomic являются последовательно согласованными атомарными операциями (sequentially consistent atomics). Начиная с ревизии модели памяти Go 1.19, это стало явным обещанием (11.9): все атомарные операции подчиняются единому глобальному полному порядку, и если эффект атомарной операции $A$ наблюдается атомарной операцией $B$ , то $A$ «произошла до» $B$ (happens before). Это означает, что атомарная операция не только неделима сама по себе, но и устанавливает порядок событий между горутинами и может полноценно использоваться как средство синхронизации, а не просто как защита от «частичной записи». Обычная запись, выполненная до атомарной записи, также становится видимой для читателя, наблюдающего эту атомарную запись, — именно на это опираются неблокирующие алгоритмы при передаче данных.

В контексте различных языков компромисс Go выглядит особенно определённым:

Язык	Предоставляемые порядки памяти	Проектная ориентация
C / C++11	полный набор `relaxed`/`acquire`/`release`/`acq_rel`/`seq_cst`	выжать максимум из аппаратуры, передав сложность слабого упорядочения разработчику
Java	`volatile` (SC) + `VarHandle` с тонкой настройкой порядка	SC по умолчанию, эксперты могут углубиться
Rust	`Ordering::{Relaxed,Acquire,Release,AcqRel,SeqCst}`	тот же набор уровней, что и в C++
Go	только последовательная согласованность	единственный уровень, слабое упорядочение намеренно не предоставляется

Полное меню порядков памяти C++ позволяет выжать из аппаратуры каждый последний бит производительности, ценой того, что печально известная задача «понимания слабых моделей памяти» целиком перекладывается на прикладного разработчика, а такие проблемы, как значения «из ниоткуда» (out-of-thin-air values) в relaxed-атомиках, остаются нерешёнными для академической науки по сей день (11.9). Позиция Go: для подавляющего большинства программ производительности SC-атомиков вполне достаточно, а приобретаемая простота рассуждений стоит гораздо больше, чем эта крупица пиковой производительности. Поэтому Go предоставляет единственный уровень — последовательную согласованность. Это согласуется с привычным характером Go в планировании и сборке мусора: уступить контролируемую долю производительности в обмен на простую, трудно используемую неправильно семантику. Когда читатель использует atomic.AddInt64, нет необходимости мысленно моделировать буфер записи — и уже одно это является проявлением заботы в дизайне.

11.3.6 Типизированные атомарные переменные: «должна быть доступна атомарно» — в типе

Изначально sync/atomic располагал лишь функциональным API — например, atomic.AddInt64(&x, 1). Он работает, но имеет два давно критикуемых недостатка.

Первый — забывчивость. Ничто не мешает выполнить обычное (неатомарное) обращение к той же переменной в другом месте; для компилятора x++ и atomic.AddInt64(&x, 1) обращаются к одному и тому же обычному int64, и стоит где-то забыть вызвать атомарную функцию — заложена гонка данных, а компилятор не способен её обнаружить; остаётся надеяться, что -race обнаружит её во время выполнения. Второй — выравнивание. На 32-битных платформах атомарная операция над 64-битной переменной требует 8-байтового выравнивания, тогда как выравнивание обычного поля int64 внутри структуры зависит от расположения предшествующих полей, что порождает хрестоматийную ловушку: переставьте поля структуры — и тот же код, безупречно работавший на amd64, аварийно завершается на 32-битном ARM из-за невыровненного атомарного доступа.

Go 1.19 представил типизированные атомарные переменные (proposal #50860), разом закрыв обе бреши на уровне типов:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


// Упрощённый эскиз типа: int64 обёрнут в тип, доступный только атомарно
type Int64 struct {
    _ noCopy   // go vet использует это для сообщения «скопировано после первого использования»
    _ align64  // принудительное 8-байтовое выравнивание, устраняющее ловушку на 32-битных платформах
    v int64    // приватное поле, недоступное извне; обращение возможно только через методы
}

func (x *Int64) Load() int64            { return LoadInt64(&x.v) }
func (x *Int64) Store(val int64)        { StoreInt64(&x.v, val) }
func (x *Int64) Add(delta int64) int64  { return AddInt64(&x.v, delta) }
func (x *Int64) CompareAndSwap(old, new int64) bool {
    return CompareAndSwapInt64(&x.v, old, new)
}

Объявите переменную как atomic.Int64 — и поскольку v является приватным полем, обращение к ней возможно только через методы Load/Store/Add/CompareAndSwap; обычный доступ заблокирован на уровне типов, и возможность забыть вызвать атомарную функцию исчезает в зародыше. Поле-маркер нулевой ширины align64 указывает компилятору обеспечить 8-байтовое выравнивание всего типа, и ловушка с выравниванием исчезает вместе с ним. noCopy позволяет go vet обнаруживать «атомарную переменную, скопированную по значению» — ещё один вид тонкой ошибки. Полный набор типизированных атомарных типов: atomic.Int32/Int64/Uint32/Uint64/Uintptr/Bool/Pointer[T]/Value.

Наиболее интересным из них является atomic.Pointer[T], ставший возможным благодаря дженерикам. Он использует параметр типа для выражения «это атомарный указатель на *T»; чтение и запись типизированы, что избавляет от преобразований unsafe.Pointer, разбросанных повсюду. В исходном коде скрыт изящный приём:

1
2
3
4
5


type Pointer[T any] struct {
    _ [0]*T        // упоминание *T, чтобы различные Pointer[T] не могли быть преобразованы друг в друга (issue 56603)
    _ noCopy
    v unsafe.Pointer
}

Массив нулевой длины [0]*T не занимает места, и его единственное назначение — сделать atomic.Pointer[A] и atomic.Pointer[B] типово несовместимыми, перекрыв лазейку, которая в противном случае позволила бы обойти типобезопасность. Это пример совместной эволюции дизайна API и возможностей языка: тип превращает принцип «к этому полю следует обращаться атомарно» из проявления сознательности программиста в контракт, который может проверить компилятор. Новый код всегда должен предпочитать типизированные атомарные переменные функциональному API.

atomic.Value занимает особое место в этом семействе. Он используется для целостной и атомарной замены значения произвольного типа; типичный сценарий — горячая перезагрузка конфигурации: фоновая горутина подготавливает целиком новую конфигурацию и подменяет её за одну операцию Store, а все читатели, использующие Load, видят либо полностью старую, либо полностью новую конфигурацию — но никогда «наполовину изменённое» промежуточное состояние.

1
2
3
4
5


var cfg atomic.Value           // хранит *Config
cfg.Store(loadConfig())        // начальная загрузка при старте

func reload() { cfg.Store(loadConfig()) }          // писатель: замена целиком
func handler() { c := cfg.Load().(*Config); _ = c } // читатель: получение полного снимка без блокировки

Его внутренняя реализация — образец тщательности. Значение interface{} на этапе выполнения состоит из двух частей: «указатель на тип + указатель на данные» (2); чтобы атомарно заменить весь интерфейс, необходимо исключить ситуацию, когда читатель увидит состояние «тип уже заменён, данные ещё нет». Подход Value таков: при первом Store он сначала с помощью CAS устанавливает указатель на тип в специальный маркер незавершённости firstStoreInProgress; в это время runtime_procPin запрещает вытеснение текущей горутины, и лишь после того, как указатели на данные и на тип последовательно зафиксированы, он снимает закрепление; читатель, выполнивший Load и увидевший этот маркер, знает, что первая запись ещё не завершена, и возвращает nil. Это облегчённая форма copy-on-write: читатели работают без блокировок, писатель заменяет значение целиком — подход, оптимальный для данных вроде конфигурации, которые читаются значительно чаще, чем записываются. Начиная с Go 1.19 большая часть нового кода может использовать atomic.Pointer[Config] вместо atomic.Value, получая типобезопасность и избавляясь от утверждения типа; лишь когда необходимо хранить значение, «тип которого определяется только во время выполнения», atomic.Value остаётся незаменимым.

11.3.7 Итог: фундамент и граница

Атомарные операции — нижний уровень средств параллелизма Go, над которым стоят мьютекс, каналы и все неблокирующие быстрые пути рантайма. Основную нить этого раздела можно свести к трём тезисам: CAS — универсальный примитив мира lock-free с числом консенсуса $\infty$ , и в теории он способен выдержать любую неблокирующую структуру данных; однако корректность неблокирующего программирования ограждена подводными камнями вроде ABA и безопасного освобождения памяти и исключительно трудна в инженерной практике; поэтому Go заключает сложные неблокирующие структуры внутри рантайма, предоставляет пользователям лишь последовательно согласованные базовые примитивы и использует типизированные атомарные переменные, чтобы превратить принцип «должна быть доступна атомарно» в контракт времени компиляции. Следующий раздел (11.9) поместит «последовательную согласованность» и «happens before» из этого раздела в полную модель памяти и подробно их разъяснит — именно там берёт начало каждое обещание, данное в этом разделе.