Chapter 11 · Synchronization Primitives and Patterns

11.2 Мьютекс

sync.Mutex — наиболее фундаментальный примитив синхронизации: он допускает в критическую секцию лишь одну горутину одновременно. За этим простым интерфейсом скрывается постоянное балансирование между двумя конкурирующими целями: пропускная способность (передать блокировку как можно быстрее, не оставляя процессор простаивать) и справедливость (не допускать бесконечного ожидания в очереди). Достичь обеих целей в полной мере невозможно: передача блокировки строго по порядку поступления наиболее справедлива, однако сопряжена с переключением контекста при каждой передаче; предоставление только что пробудившемуся ожидающему свободно конкурировать с уже выполняющимися горутинами — наиболее быстро, однако чревато тем, что некоторые ожидающие будут проигрывать снова и снова. Данный раздел сначала излагает теорию и аппаратные основы классической задачи взаимного исключения, а затем рассматривает, как мьютекс Go держит этот баланс.

11.2.1 Задача взаимного исключения и её аппаратная основа

Взаимное исключение — одна из первых тем в теории параллельного программирования. Дейкстра формализовал «задачу взаимного исключения» в 1965 году и предложил первое программное решение, позволяющее нескольким процессам поочерёдно входить в критическую секцию с использованием лишь обычных операций чтения и записи, без каких-либо специальных аппаратных инструкций. Позднее алгоритм булочника Лэмпорта (1974) привёл это направление к законченному результату: каждый поток, желающий войти в критическую секцию, сначала «берёт номер», а затем входит в порядке возрастания номеров. Это гарантирует и взаимное исключение, и справедливую очередь по принципу FIFO — при использовании лишь обычных операций чтения и записи, без атомарных инструкций «чтение–модификация–запись».

Чисто программное решение самодостаточно в теории, однако дорогостояще на практике: алгоритм булочника вынужден просматривать номера всех потоков, и его стоимость растёт пропорционально их числу; кроме того, он критически зависит от последовательно согласованной модели памяти (11.9), требуя дополнительных барьеров на современном оборудовании со слабым порядком операций. Современные блокировки поэтому больше не следуют чисто программному пути, а опираются непосредственно на атомарные инструкции «чтение–модификация–запись», предоставляемые аппаратурой: compare-and-swap (CAS), fetch-and-add и им подобные (11.3). Одна инструкция CAS атомарно выполняет то, что алгоритму булочника требует нескольких шагов; смена фундамента влечёт за собой смену всей надстройки.

На основе этих примитивов блокировки сформировались в целое семейство; понимание его устройства помогает точнее определить место мьютекса Go.

Спин-блокировка — простейший вариант: она повторяет CAS снова и снова, входя при успехе и активно ожидая при неудаче. При низкой конкуренции она практически бесплатна, однако при высокой превращается в катастрофу: несколько ядер оспаривают одну и ту же переменную-блокировку, и каждый CAS вызывает повторную инвалидацию и перезагрузку строки кэша между ядрами — так называемый cache-line bouncing, — который усугубляется по мере роста числа претендентов.
Блокировка на основе талонов (ticket lock) использует fetch-and-add для выдачи номеров, после чего каждый поток ожидает в цикле своего номера, что восстанавливает FIFO-справедливость. Однако все ожидающие по-прежнему крутятся на одной переменной «сейчас обслуживается», поэтому проблема cache-line bouncing не устраняется.
Блокировка MCS (Mellor-Crummey и Scott, 1991) — классика среди масштабируемых блокировок. Каждый ожидающий встраивается в явную очередь и ожидает в цикле на своей собственной локальной переменной; при освобождении предыдущим держателем блокировки запись производится только в эту одну локальную переменную преемника. В результате, сколько бы претендентов ни было, каждая передача затрагивает лишь одну строку кэша, и трафик кэша при конкуренции снижается до константы.

Все перечисленные схемы относятся к семейству «активного ожидания», при котором ожидающие удерживают процессор в цикле. Иная линия делает «сон» дешёвым. В ранние времена поток мог заблокироваться, только совершив системный вызов в ядро, оплачивая его стоимость даже при полном отсутствии конкуренции. Futex в Linux (fast userspace mutex; Franke, Russell и Kirkwood, 2002) устранил эту проблему: при отсутствии конкуренции блокировка и разблокировка выполняются полностью в пространстве пользователя единственной атомарной операцией; и лишь когда ожидающий действительно должен быть заблокирован или разбужен, происходит обращение к ядру с этим адресом пространства пользователя для постановки в очередь. Практически все современные пользовательские блокировки, включая мьютекс Go, опираются на этот принцип «быстро в пространстве пользователя, ядро — как запасной вариант» (futex и его аналоги на каждой платформе). Go не вызывает futex напрямую. Вместо этого семафор рантайма (runtime_SemacquireMutex / runtime_Semrelease) оборачивает низкоуровневый примитив блокировки каждой платформы и предоставляет единый интерфейс наверх.

11.2.2 Слово состояния и быстрый путь: почти нулевая стоимость без конкуренции

Мьютекс Go сжимает блокировку в два поля: слово состояния и семафор.

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


type Mutex struct {
    state int32  // битовое поле: бит0 — заблокировано, бит1 — пробуждённый ожидающий, бит2 — режим голодания, старшие биты — счётчик ожидающих
    sema  uint32 // семафор для блокировки и пробуждения ожидающих
}

const (
    mutexLocked      = 1 << iota // бит0: заблокирован ли мьютекс
    mutexWoken                   // бит1: был ли пробуждён ожидающий, участвующий в гонке за блокировку
    mutexStarving                // бит2: активен ли режим голодания
    mutexWaiterShift = iota      // = 3, старшие биты state>>3 хранят счётчик ожидающих
    starvationThresholdNs = 1e6  // 1 мс: порог ожидания для переключения в режим голодания
)

Упаковка нескольких единиц информации в один int32 позволяет единственной атомарной операцией одновременно считывать и изменять всё ключевое состояние блокировки: заблокирована ли она, есть ли пробуждённый ожидающий, активен ли режим голодания, сколько ожидающих. Три младших бита — флаги, старшие биты — счётчик ожидающих; добавить или убрать одного ожидающего — значит прибавить или вычесть 1<<mutexWaiterShift из state. Такая побитовая кодировка позволяет свести быстрый путь захвата блокировки к единственному CAS над одним целым числом.

При отсутствии конкуренции захват блокировки сводится к атомарному изменению state с 0 (разблокировано, нет ожидающих) на mutexLocked:

1
2
3
4
5
6


func (m *Mutex) Lock() {
    if atomic.CompareAndSwapInt32(&m.state, 0, mutexLocked) {
        return // быстрый путь: один CAS успешен, ядро не задействуется
    }
    m.lockSlow() // неудача CAS означает конкуренцию — переход на медленный путь
}

Этот быстрый путь не обращается к ядру и не переводит горутину в сон. Именно он обеспечивает лёгкость мьютекса при высокой частоте использования: подавляющее большинство операций захвата и освобождения завершается здесь. Только при неудаче CAS — то есть когда блокировка удерживается или уже есть ожидающие — управление передаётся медленному пути lockSlow. Освобождение симметрично следует тем же быстрым путём: сбрасывается бит mutexLocked, и если state оказывается ровно 0 (нет ожидающих, нет других флагов), всё завершено без вызова unlockSlow.

11.2.3 Медленный путь: сначала вращение, затем сон

При возникновении конкуренции горутина не засыпает немедленно. Погружение в сон и пробуждение из него требуют взаимодействия с рантаймом и обходятся далеко не дёшево, тогда как блокировка нередко удерживается лишь ненадолго и скоро освобождается. Поэтому lockSlow сначала вращается (spin) несколько итераций, рассчитывая, что блокировка вот-вот освободится; если расчёт оправдывается — экономится целый цикл засыпания и пробуждения.

Вращение допускается лишь при одновременном выполнении ряда условий; нарушение любого из них означает прекращение вращения и переход ко сну:

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


func (m *Mutex) lockSlow() {
    var waitStartTime int64
    starving, awoke, iter := false, false, 0
    old := m.state
    for {
        // Вращаться только когда «заблокировано и не в режиме голодания» и рантайм считает вращение целесообразным
        if old&(mutexLocked|mutexStarving) == mutexLocked && runtime_canSpin(iter) {
            // Перед вращением установить флаг mutexWoken, чтобы Unlock не будил никого другого
            if !awoke && old&mutexWoken == 0 && old>>mutexWaiterShift != 0 &&
                atomic.CompareAndSwapInt32(&m.state, old, old|mutexWoken) {
                awoke = true
            }
            runtime_doSpin() // выполнить несколько инструкций PAUSE
            iter++
            old = m.state
            continue
        }
        // ...условие вращения больше не выполняется: вычислить новое состояние, выполнить CAS для постановки в очередь, заблокироваться на семафоре и уснуть (подробности ниже)
    }
}

runtime_canSpin жёстко ограничивает «целесообразность вращения»: машина должна быть многоядерной, счётчик вращений не должен превышать предел (4 по умолчанию), и в локальной очереди выполнения не должно быть других горутин, ожидающих запуска. Иными словами, вращение происходит только тогда, когда «блокировка, по всей видимости, будет получена в ближайшее время, и вращение не лишит ресурсов других»; как только блокировка переходит в режим голодания или счётчик вращений исчерпан, горутина честно подвешивается на семафоре sema и засыпает, чтобы быть разбуженной, когда держатель блокировки её освободит. Эта гибридная стратегия «вращение при коротком ожидании, сон при долгом» не является исключительной особенностью Go: адаптивный мьютекс pthread (PTHREAD_MUTEX_ADAPTIVE_NP), bias/lightweight locks в Java, parking_lot и другие реализуют тот же подход, различаясь лишь пороговыми значениями длительности вращения и моментом отказа от него.

11.2.4 Справедливость: нормальный режим и режим голодания

Наиболее искусное решение в архитектуре мьютекса — два режима, введённые в Go 1.9. Они соответствуют двум концам каната из раздела 11.2.1: один конец тянет к пропускной способности, другой удерживает справедливость.

stateDiagram-v2
    [*] --> Normal
    Normal --> Normal: "новые горутины конкурируют с пробуждёнными ожидающими (barging, приоритет пропускной способности)"
    Normal --> Starving: "ожидающий провёл в очереди более 1 мс"
    Starving --> Starving: "при освобождении — прямая FIFO-передача первому ожидающему"
    Starving --> Normal: "очередь исчерпана, или первый ожидал менее 1 мс"

Нормальный режим ориентирован на пропускную способность. Ожидающие выстраиваются в очередь FIFO, однако только что пробуждённый ожидающий не получает блокировку напрямую — он вынужден конкурировать за неё с новыми горутинами, которые уже выполняются и тоже хотят её захватить. Новые горутины находятся в естественно выгодном положении: они уже выполняются на процессоре и не нуждаются в пробуждении, тогда как пробуждённый ожидающий только вышел из сна и ещё не получил процессорное время. Поэтому новые горутины нередко «влезают» (barging) и захватывают блокировку. Barging сокращает число переключений контекста и существенно повышает пропускную способность, однако ценой того, что проигравший пробуждённый ожидающий может снова и снова отправляться в голову очереди, проигрывая раз за разом и впадая в состояние голодания.

Для ограничения хвостовой задержки в наихудшем случае в мьютекс введён режим голодания. Когда время ожидания какого-либо ожидающего — от постановки в очередь до получения блокировки — превышает 1 мс (starvationThresholdNs) и он так и не добился успеха, то в момент получения блокировки он переключает мьютекс в режим голодания. С этого момента правила меняются на противоположные: при освобождении никому не позволяется вмешиваться, а право владения блокировкой напрямую передаётся первому ожидающему в порядке FIFO (при освобождении бит mutexLocked даже не устанавливается — его устанавливает сам ожидающий после пробуждения); вновь прибывшая горутина, даже если видит, что блокировка «выглядит свободной», не пытается её захватить, не вращается, а честно встаёт в хвост очереди. Как только очередь исчерпывается или первый ожидающий на этот раз ждал менее 1 мс, мьютекс возвращается в нормальный режим.

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

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


func (m *Mutex) unlockSlow(new int32) {
    if new&mutexStarving == 0 {
        // нормальный режим
        old := new
        for {
            // нет ожидающих, или кто-то уже пробуждён / захватил блокировку / уже режим голодания — будить никого не нужно
            if old>>mutexWaiterShift == 0 ||
                old&(mutexLocked|mutexWoken|mutexStarving) != 0 {
                return
            }
            // завоевать право «разбудить одного»: уменьшить счётчик ожидающих, установить mutexWoken
            new = (old - 1<<mutexWaiterShift) | mutexWoken
            if atomic.CompareAndSwapInt32(&m.state, old, new) {
                runtime_Semrelease(&m.sema, false, 1) // будит первого ожидающего, но он всё равно должен конкурировать за блокировку
                return
            }
            old = m.state
        }
    } else {
        // режим голодания: передать владение напрямую первому ожидающему, handoff=true означает FIFO-передачу
        runtime_Semrelease(&m.sema, true, 1)
    }
}

Вместе два режима позволяют мьютексу в большинстве случаев пользоваться высокой пропускной способностью barging, при этом используя порог 1 мс в качестве гарантии для наихудшего случая: любой ожидающий терпит вытеснение лишь ограниченное время, а после 1 мс ему гарантирована блокировка в порядке FIFO. Нормальный режим эффективен потому, что горутина может многократно подряд захватывать ту же блокировку, даже при наличии целой стопки заблокированных ожидающих впереди; режим голодания введён именно для подавления патологической хвостовой задержки.

11.2.5 Как это делают другие: спектр справедливости

Принцип «пропускная способность по умолчанию, ограниченная гарантия как страховка» не уникален для Go — это компромисс, к которому индустрия приходит снова и снова. Если выстроить различные блокировки по степени справедливости, получится спектр: на одном конце — «полностью справедливые» (строгая FIFO-передача напрямую, без голодания, но с низкой пропускной способностью и значительными накладными расходами на передачу), на другом — «полностью несправедливые» (свободный barging, высокая пропускная способность, но ожидающие могут голодать).

ReentrantLock в Java просто оставляет выбор за пользователем: при создании можно указать справедливую или несправедливую блокировку. По умолчанию используется несправедливая — по той же причине, что и barging в Go: более высокая пропускная способность; справедливая блокировка предоставляет доступ строго в порядке FIFO, что подходит для чувствительных к задержке сценариев, не допускающих голодания, однако обеспечивает заметно меньшую пропускную способность.
parking_lot в Rust реализует «итоговую справедливость»: как правило, он допускает barging для достижения пропускной способности, однако с некоторым коротким интервалом (порядка 1 мс) принудительно выполняет одну справедливую передачу, гарантируя, что ожидающие не будут голодать бесконечно. Идея перекликается с режимом голодания в Go, однако триггером служит «временной интервал», а не «время ожидания конкретного ожидающего».

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

11.2.6 Блокировка чтения-записи и TryLock

sync.RWMutex разграничивает читателей и писателей поверх взаимного исключения: несколько читателей могут одновременно удерживать блокировку, тогда как писатель удерживает её эксклюзивно. Это подходит для сценариев с преобладанием операций чтения, однако следует учитывать внутренний компромисс: если читатели поступают непрерывно, писатель может долго ждать блокировки (голодание писателя). Поэтому в реализации Go читатель, прибывший позже, также блокируется, если писатель уже ожидает, — чтобы писатель не задерживался читателями бесконечно. Гарантии happens-before для RWMutex (один Unlock синхронизируется перед последующим Lock, а RUnlock синхронизируется перед последующим Lock) описаны в разделе 11.9.

TryLock (а также TryLock / TryRLock для RWMutex, добавленные в Go 1.18) пытается захватить блокировку, но никогда не блокируется: возвращает true при успехе и немедленно false при неудаче. Область применения этой функции узка, и официальная документация прямо предупреждает: случаи корректного использования TryLock существуют, однако редки, а частое обращение к TryLock нередко свидетельствует о проблеме в самой схеме работы с блокировками. С точки зрения модели памяти успешный TryLock эквивалентен Lock, тогда как неудачный TryLock не устанавливает никакого отношения synchronizes-before.

Небольшое замечание о размещении реализации: начиная с Go 1.24, основные реализации Mutex, RWMutex и других примитивов перенесены в пакет internal/sync, а sync.Mutex стандартной библиотеки превратился в тонкую обёртку (встраивающую internal/sync.Mutex и маркер noCopy, при этом методы напрямую делегируются). Это сделано для того, чтобы внутренние пакеты, такие как рантайм, могли повторно использовать ту же реализацию без образования циклической зависимости от sync; описанные в данном разделе механизмы — слово состояния, быстрый и медленный пути, два режима — остались неизменными.

11.2.7 Инженерные компромиссы

Архитектура мьютекса — это сплошные компромиссы, каждый из которых подтверждает давно известную истину: прирост производительности никогда не достаётся бесплатно — он всегда сопровождается перекладыванием сложности. Упаковка нескольких единиц информации в один int32 посредством битового поля экономит атомарные операции на пути захвата блокировки ценой непрозрачных побитовых манипуляций; ставка на вращение при коротком ожидании экономит цикл засыпания и пробуждения при выигрыше, или зря вращается несколько итераций при проигрыше; компромисс с barging в пользу пропускной способности влечёт за собой необходимость целого режима голодания с порогом 1 мс для обеспечения справедливости, и большая часть сложности всего lockSlow определяется именно этим страховочным слоем.

Если вписать мьютекс в общую панораму конкурентности Go, он вместе с каналом олицетворяет два стиля: мьютекс прямо выражает «взаимное исключение», канал — «взаимодействие». Максима Go «не общайтесь через разделяемую память — разделяйте память через общение» рекомендует последнее, однако это предпочтение, а не запрет. Выбор между ними определяется тем, что нужно сделать — «защитить разделяемое состояние» или «передать владение данными между горутинами», — а не тем, что «более продвинуто». Следующий раздел обращается к атомарным операциям «чтение–модификация–запись», лежащим в основе самого мьютекса (11.3).

Дополнительная литература

Edsger W. Dijkstra. “Solution of a Problem in Concurrent Programming Control.” Communications of the ACM, 8(9), 1965. https://doi.org/10.1145/365559.365617 (формализация задачи взаимного исключения и первое программное решение)
Leslie Lamport. “A New Solution of Dijkstra’s Concurrent Programming Problem.” Communications of the ACM, 17(8), 1974. https://doi.org/10.1145/361082.361093 (алгоритм булочника)
John M. Mellor-Crummey, Michael L. Scott. “Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors.” ACM TOCS, 9(1), 1991. https://doi.org/10.1145/103727.103729 (блокировка MCS и основы масштабируемых блокировок)
Hubertus Franke, Rusty Russell, Matthew Kirkwood. “Fuss, Futexes and Furwocks: Fast Userlevel Locking in Linux.” Proceedings of the Ottawa Linux Symposium, 2002. (futex — основа быстрой блокировки в пространстве пользователя)
Dmitry Vyukov. sync: make Mutex more fair (режим голодания в Go 1.9), 2016. https://go-review.googlesource.com/c/go/+/34310; связанное обсуждение — issue #13086.
The Go Authors. The Mutex implementation in runtime/internal. src/internal/sync/mutex.go, src/sync/mutex.go. https://github.com/golang/go/tree/master/src/internal/sync
The Go Authors. The Go Memory Model: Locks. https://go.dev/ref/mem
Эта книга, 11.3 Атомарные операции, 11.9 Модель согласованности памяти.