Как устроен лок: от железа к futex

Зачем лок и почему «флаг занято» не работает

В главе про потоки два потока делали count++ и теряли инкремент: каждый читал 5, прибавлял единицу и записывал 6. Лечится это взаимным исключением: пока один поток внутри критической секции, второй ждёт снаружи. Инструмент для этого называется лок (lock, замок, мьютекс). В Go вы пишете mu.Lock() и не задумываетесь, что внутри. Эта глава про то, что внутри: от инструкции процессора до системного вызова ядра ОС.

В главе встречаются два разных «ядра»: ядро ОС (kernel, привилегированный код операционной системы) и ядро процессора (core). Где можно спутать, пишем полностью.

Первая идея, которая приходит в голову: завести обычную переменную busy (0 — свободно, 1 — занято). Хочу войти — проверяю, что busy == 0, и ставлю busy = 1. Проблема в том, что «проверить» и «поставить» — две отдельные операции, и между ними может вклиниться другой поток:

  busy = 0
 
  Поток A                          Поток B
  ─────────────────────────        ─────────────────────────
  читает busy → 0
                                   читает busy → 0   (тоже «свободно»)
  пишет busy = 1
                                   пишет busy = 1
  входит в критическую секцию      входит в критическую секцию

Оба прочитали 0 раньше, чем кто-то успел записать 1, и оба вошли. Защита от гонки сама оказалась гонкой, ровно той же формы, что потерянный count++. Из обычных чтений и записей правильный лок не собрать (на самом деле можно, алгоритм Петерсона это делает, но он требует строгого порядка операций с памятью, которого современные процессоры без барьеров не дают; об этом в следующей главе). Нужна помощь железа.

Атомарные инструкции: test-and-set и compare-and-swap

Процессор умеет выполнять «прочитать и записать» как одну неделимую операцию: пока она идёт, никакое другое ядро процессора не может вклиниться в эту ячейку памяти. Такие операции называют атомарными (от греческого «неделимый»). На x86 это инструкции с префиксом LOCK и XCHG, на ARM — LDXR/STXR или (в новых ядрах) CAS, SWP, LDADD.

Две классические атомарные операции, на которых строятся локи:

test-and-set (TAS) — записать 1 и вернуть, что было до записи.

  TAS(addr):            // выполняется как одна инструкция
      old = *addr
      *addr = 1
      return old

Вернулось 0 — замок был свободен, и теперь он наш. Вернулось 1 — замок уже кто-то держал, мы ничего не испортили (записали 1 поверх 1), надо пробовать ещё.

compare-and-swap (CAS) — записать новое значение, только если в ячейке сейчас лежит ожидаемое.

  CAS(addr, expected, new):   // одна инструкция
      if *addr == expected:
          *addr = new
          return true
      return false

CAS гибче: им можно не только захватывать замок, но и атомарно обновлять счётчики, указатели, флаги состояния. Почти вся неблокирующая синхронизация стоит на нём (следующая глава). В Go CAS доступен через sync/atomic: atomic.CompareAndSwapInt32 или метод CompareAndSwap у типов atomic.Int32, atomic.Pointer и других (см. атомики в Go-курсе).

Если два потока одновременно делают CAS(&state, 0, 1), железо упорядочит их: один увидит 0 и получит true, второй увидит уже 1 и получит false. Выиграть один и тот же CAS вдвоём нельзя.

Спинлок

Самый простой лок на CAS: пытаемся перевести состояние из 0 в 1, пока не получится. Поток не засыпает, а крутится в цикле, отсюда название спинлок (spinlock, от spin — вращаться).

package main
 
import (
	"fmt"
	"runtime"
	"sync"
	"sync/atomic"
)
 
type SpinLock struct {
	state atomic.Int32 // 0 — свободно, 1 — занято
}
 
func (l *SpinLock) Lock() {
	for !l.state.CompareAndSwap(0, 1) {
		runtime.Gosched() // уступить процессор другим горутинам
	}
}
 
func (l *SpinLock) Unlock() {
	l.state.Store(0)
}
 
func main() {
	var (
		lock    SpinLock
		counter int
		wg      sync.WaitGroup
	)
	for g := 0; g < 8; g++ {
		wg.Add(1)
		go func() {
			defer wg.Done()
			for i := 0; i < 100_000; i++ {
				lock.Lock()
				counter++ // критическая секция
				lock.Unlock()
			}
		}()
	}
	wg.Wait()
	fmt.Println(counter)
}

800000

Восемь горутин по сто тысяч инкрементов дают ровно 800 000, и go run -race молчит: CAS и Store из sync/atomic дают те же гарантии видимости, что и мьютекс. Уберите lock.Lock()/lock.Unlock() — получите число меньше 800 000 и отчёт race detector'а.

Зачем runtime.Gosched()? Если горутина-владелец лока вытеснена, а на её потоке крутится ожидающая, крутиться бессмысленно: владелец не вернётся, пока ждущий не уступит процессор. Без Gosched при GOMAXPROCS=1 выручит только принудительное вытеснение рантаймом, а это порядка 10 мс впустую на каждый такой случай. В настоящих спинлоках ядра ОС в цикл ставят инструкцию PAUSE (x86) или YIELD (ARM), которая подсказывает процессору «я жду» и снижает энергопотребление.

Свой спинлок на sync/atomic вы напишете и проверите тестами с -race в задаче «Спинлок на atomic».

Крутиться или спать

Пока поток A держит лок, поток B в спинлоке занимает ядро процессора на 100% и ничего полезного не делает.

  Поток A ──────[ работает в критической секции ]──────► Unlock
                                                            │
  Поток B   CAS CAS CAS CAS CAS CAS CAS CAS CAS CAS ────────┘ захватил
            (ядро процессора занято, полезной работы ноль)

Альтернатива — заснуть: попросить ОС снять поток с процессора и разбудить, когда лок освободится. Сон дорог по-своему: это системный вызов и два переключения контекста (уснуть и проснуться), единицы микросекунд (цифры — в главе о цене системного вызова).

Выбор зависит от того, сколько держат лок:

• Критическая секция на десятки наносекунд (инкремент, вставка в map). Владелец отпустит лок раньше, чем ОС успеет усыпить ждущего. Выгоднее покрутиться.
• Секция на миллисекунды (ввод-вывод, тяжёлый расчёт). Крутясь, ждущий сожжёт миллионы тактов. Выгоднее заснуть и отдать ядро процессора другим.
• Одно ядро процессора. Спин бесполезен в принципе: пока ждущий крутится, владелец не исполняется и не может отпустить лок.

Поэтому настоящие мьютексы гибридные: немного крутятся (вдруг лок отпустят прямо сейчас) и только потом засыпают. Осталось понять, как заснуть дёшево.

Ticket lock: очередь вместо лотереи

У простого спинлока есть ещё один изъян. Когда лок освобождается, его хватает тот, чей CAS успел первым, а это во многом случайность (и топология кэшей: ядро процессора, которое только что держало линию с замком, часто выигрывает снова). Какой-то поток может проигрывать раз за разом. Это голодание (starvation).

Ticket lock работает как электронная очередь в банке: берёте талон с номером и ждёте, пока табло покажет ваш номер.

  next_ticket — какой номер выдать следующему
  now_serving — чей номер на табло
 
  Lock():
      my = atomic_fetch_add(&next_ticket, 1)   // взять талон
      while atomic_load(&now_serving) != my:   // ждать свою очередь
          pause
  Unlock():
      atomic_add(&now_serving, 1)              // позвать следующего

fetch_add (атомарно прибавить и вернуть старое значение, в Go — atomic.AddInt64(...) - 1 или x.Add(1) - 1) раздаёт номера без повторов. Прогоним: next_ticket = 0, now_serving = 0. A берёт талон 0 и сразу входит. B берёт 1, C берёт 2, оба крутятся. A делает Unlock → табло 1 → входит B. B делает Unlock → табло 2 → входит C. Порядок строго по приходу, обогнать некого. Такой лок много лет использовало ядро Linux для спинлоков (сейчас там qspinlock, развитие той же идеи).

futex: лок без системного вызова в обычном случае

Теперь главное. Мы хотим лок, который:

• в обычном случае (лок свободен) не ходит в ядро ОС вообще, только атомарная инструкция в пространстве пользователя;
• при борьбе за лок усыпляет ждущих, а не жжёт CPU.

Так устроен futex (fast userspace mutex) в Linux. Это не готовый мьютекс, а системный вызов, который даёт две операции над целым числом в памяти процесса:

• futex_wait(addr, expected) — «усыпи меня, если *addr всё ещё равно expected». Проверку и засыпание ядро ОС делает атомарно, под своим внутренним локом. Если значение уже другое, вызов сразу возвращается.
• futex_wake(addr, n) — «разбуди до n потоков, спящих на этом адресе».

Само значение лока живёт в обычной памяти программы, и всё, что можно сделать атомиками, делается без ядра ОС. Ядро ОС нужно только для очереди спящих.

Почему двух состояний мало

Попробуем сделать лок на 0 (свободно) и 1 (занято). Захват — CAS(0 → 1), при неудаче futex_wait(addr, 1). Отпускание — записать 0 и... звать futex_wake или нет? Если звать всегда, каждый Unlock стоит системного вызова, и весь смысл пропал. Если не звать, спящий поток никогда не проснётся. По значению 1 нельзя понять, есть ли ждущие.

Поэтому классическая реализация (её описал Ульрих Дреппер в статье «Futexes Are Tricky») использует три состояния:

  0 — свободно
  1 — занято, ждущих нет
  2 — занято, возможно, есть ждущие
 
  Lock():
      if CAS(&v, 0, 1):              // быстрый путь: был свободен
          return
      while XCHG(&v, 2) != 0:         // помечаем «есть ждущие»;
          futex_wait(&v, 2)           // если лок всё ещё занят — спим
 
  Unlock():
      if XCHG(&v, 0) == 2:            // было «возможно, есть ждущие»
          futex_wake(&v, 1)           // разбудить одного

XCHG — атомарный обмен: записать новое значение и вернуть старое.

Прогоним по шагам с двумя потоками.

  шаг  поток  действие                              v    syscall
  ───  ─────  ────────────────────────────────────  ───  ─────────
   1   A      CAS(0→1) успех, A внутри               1    нет
   2   B      CAS(0→1) неудача (v=1)                 1    нет
   3   B      XCHG(v,2) вернул 1 ≠ 0                 2    нет
   4   B      futex_wait(v, 2): v == 2, B уснул      2    да
   5   A      Unlock: XCHG(v,0) вернул 2             0    нет
   6   A      futex_wake(v, 1): B разбужен           0    да
   7   B      XCHG(v,2) вернул 0 → B внутри          2    нет
   8   B      Unlock: XCHG(v,0) вернул 2             0    нет
   9   B      futex_wake(v, 1): спящих нет           0    да (лишний)

Что видно из прогона:

• Если борьбы нет (только шаги 1 и Unlock с XCHG, вернувшим 1), системных вызовов ноль. Это и есть выигрыш futex: подавляющее большинство захватов в нормальном сервисе проходит без ядра.
• На шаге 7 B захватывает лок со значением 2, а не 1. Он не знает, остались ли другие спящие, и пессимистично считает, что да. Отсюда лишний futex_wake на шаге 9: плата за простоту, один системный вызов впустую.
• Между шагами 3 и 4 A мог успеть отпустить лок. Тогда v уже 0, и futex_wait(v, 2) не уснёт, а сразу вернётся: ядро сверяет значение перед тем, как положить поток в очередь. Без этой проверки B заснул бы после единственного futex_wake и не проснулся бы никогда. Эта ошибка называется потерянное пробуждение (lost wakeup), она снова встретится в главе про условные переменные.

На этой схеме (с вариациями) построены pthread_mutex_t в glibc и большинство локов в user space Linux. Частая ошибка на собеседовании — сказать, что futex «вообще не ходит в ядро». Ходит, но только при борьбе за лок.

sync.Mutex в Go

Мьютекс в Go решает ту же задачу, только спят у него не потоки ОС, а горутины.

• Быстрый путь. Lock делает CAS над полем state из 0 в «занято». Если получилось, всё, ни рантайм, ни ядро не участвуют. Unlock без ждущих — одна атомарная операция.
• Короткий спин. Если лок занят, горутина может немного покрутиться (до четырёх коротких итераций с инструкцией PAUSE), но только когда это имеет смысл: ядер больше одного, GOMAXPROCS > 1, есть другие работающие P и локальная очередь пуста. Те же условия, что мы вывели для спина выше.
• Парковка. Не повезло — горутина встаёт в очередь семафора рантайма и паркуется: планировщик снимает её с потока ОС и запускает на этом потоке другую горутину. Поток не спит, он работает. Futex в Go тоже есть, но уровнем ниже: им рантайм усыпляет сами потоки ОС (M), когда им нечего делать. Подробнее — в главе о планировщике Go.
• Режим голодания. Если горутина ждёт лок дольше 1 мс, мьютекс переходит в starvation mode: лок передаётся напрямую первой горутине в очереди, новые пришедшие не могут его перехватить. Идея та же, что у ticket lock.

API и практика использования мьютексов — в Go-курсе: примитивы синхронизации.

  Go:     sync.Mutex      CAS → короткий спин → парковка горутины
  Linux:  futex           CAS в user space → futex_wait/futex_wake
  CPU:    CAS, XCHG, TAS  атомарная инструкция

Отсюда практический вывод. Цена mu.Lock() в горячем пути сильно зависит от contention (сколько горутин одновременно хотят этот лок). Без борьбы это десятки наносекунд. При борьбе — парковки, пробуждения, переключения, и лок становится узким местом. Как уменьшить борьбу, разбираем в следующей главе.

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

• Говорить, что futex «не ходит в ядро». Ходит, но только при борьбе за лок.
• Ставить спинлок там, где лок держат долго или где ядро процессора одно: ожидающий сожжёт CPU, а владелец не продвинется.
• Писать спинлок без уступки процессора (runtime.Gosched, PAUSE).
• Думать, что горутина, ждущая sync.Mutex, усыпляет поток ОС. Паркуется горутина, поток ОС берёт другую работу.
• Делать лок на обычной переменной bool с проверкой и записью: это гонка в самом замке.

Проверьте себя

1. Почему проверка busy == 0 и запись busy = 1 не могут быть двумя отдельными инструкциями?
2. Чем test-and-set отличается от compare-and-swap?
3. Зачем futex-мьютексу состояние 2 и почему простой схеме из двух состояний его не хватает?
4. Три потока A, B, C по очереди вызывают Lock на futex-мьютексе из главы, пока A внутри. Сколько системных вызовов будет сделано к моменту, когда все трое отработают и отпустят лок?

Что спрашивают на собесе

• Почему нельзя сделать лок на обычной булевой переменной? Проверка и установка — два действия, между ними вклинивается другой поток. Нужна атомарная инструкция (TAS, CAS, XCHG), которая делает это неделимо.
• Чем CAS отличается от test-and-set? TAS безусловно пишет 1 и возвращает старое значение. CAS пишет новое значение, только если там лежит ожидаемое. CAS гибче, на нём строят lock-free структуры.
• Когда спинлок лучше засыпания? Когда лок держат очень коротко (меньше цены двух переключений контекста) и ядер процессора больше одного. На одном ядре процессора спин бесполезен. На практике — гибрид: чуть покрутиться, потом заснуть.
• Что такое futex и в чём выигрыш? Системный вызов с операциями wait/wake над словом в памяти процесса. Свободный лок захватывается и отпускается атомиком без ядра ОС; в ядро ОС идут только чтобы уснуть или разбудить.
• Зачем futex-мьютексу три состояния? Чтобы Unlock знал, нужно ли звать futex_wake. Состояние 2 означает «возможно, есть ждущие».
• Как futex избегает потерянного пробуждения? futex_wait(addr, val) атомарно проверяет, что значение не изменилось, и только тогда усыпляет.
• Как устроен sync.Mutex? CAS на быстром пути, короткий спин при борьбе, парковка горутины на семафоре рантайма, режим голодания при ожидании дольше 1 мс.