--- title: "Как устроен лок: от железа к futex" description: "В главе про потоки два потока делали count++ и теряли инкремент: каждый читал 5, прибавлял единицу и записывал 6. Лечится это взаимным исключением: пока один поток внутри…" canonical: https://graphlms.ru/os/book/locks-hardware course: "Операционные системы" updated: 2026-10-12 lang: ru publisher: GraphLMS --- # Как устроен лок: от железа к futex > Источник: https://graphlms.ru/os/book/locks-hardware — курс «Операционные системы», GraphLMS. ## Зачем лок и почему «флаг занято» не работает В главе про [потоки](/os/book/threads-intro) два потока делали `count++` и теряли инкремент: каждый читал `5`, прибавлял единицу и записывал `6`. Лечится это взаимным исключением: пока один поток внутри критической секции, второй ждёт снаружи. Инструмент для этого называется **лок** (lock, замок, мьютекс). В Go вы пишете `mu.Lock()` и не задумываетесь, что внутри. Эта глава про то, что внутри: от инструкции процессора до системного вызова ядра ОС. В главе встречаются два разных «ядра»: **ядро ОС** (kernel, привилегированный код операционной системы) и **ядро процессора** (core). Где можно спутать, пишем полностью. Первая идея, которая приходит в голову: завести обычную переменную `busy` (0 — свободно, 1 — занято). Хочу войти — проверяю, что `busy == 0`, и ставлю `busy = 1`. Проблема в том, что «проверить» и «поставить» — две отдельные операции, и между ними может вклиниться другой поток: ```text busy = 0 Поток A Поток B ───────────────────────── ───────────────────────── читает busy → 0 читает busy → 0 (тоже «свободно») пишет busy = 1 пишет busy = 1 входит в критическую секцию входит в критическую секцию ``` Оба прочитали `0` раньше, чем кто-то успел записать `1`, и оба вошли. Защита от гонки сама оказалась гонкой, ровно той же формы, что потерянный `count++`. Из обычных чтений и записей правильный лок не собрать (на самом деле можно, алгоритм Петерсона это делает, но он требует строгого порядка операций с памятью, которого современные процессоры без барьеров не дают; об этом в [следующей главе](/os/book/concurrent-structures)). Нужна помощь железа. ## Атомарные инструкции: test-and-set и compare-and-swap Процессор умеет выполнять «прочитать и записать» как одну неделимую операцию: пока она идёт, никакое другое ядро процессора не может вклиниться в эту ячейку памяти. Такие операции называют **атомарными** (от греческого «неделимый»). На x86 это инструкции с префиксом `LOCK` и `XCHG`, на ARM — `LDXR/STXR` или (в новых ядрах) `CAS`, `SWP`, `LDADD`. Две классические атомарные операции, на которых строятся локи: **test-and-set (TAS)** — записать 1 и вернуть, что было до записи. ```text TAS(addr): // выполняется как одна инструкция old = *addr *addr = 1 return old ``` Вернулось `0` — замок был свободен, и теперь он наш. Вернулось `1` — замок уже кто-то держал, мы ничего не испортили (записали 1 поверх 1), надо пробовать ещё. **compare-and-swap (CAS)** — записать новое значение, только если в ячейке сейчас лежит ожидаемое. ```text CAS(addr, expected, new): // одна инструкция if *addr == expected: *addr = new return true return false ``` CAS гибче: им можно не только захватывать замок, но и атомарно обновлять счётчики, указатели, флаги состояния. Почти вся неблокирующая синхронизация стоит на нём ([следующая глава](/os/book/concurrent-structures)). В Go CAS доступен через `sync/atomic`: `atomic.CompareAndSwapInt32` или метод `CompareAndSwap` у типов `atomic.Int32`, `atomic.Pointer` и других (см. [атомики в Go-курсе](/go/book/atomic)). Если два потока одновременно делают `CAS(&state, 0, 1)`, железо упорядочит их: один увидит `0` и получит `true`, второй увидит уже `1` и получит `false`. Выиграть один и тот же CAS вдвоём нельзя. ## Спинлок Самый простой лок на CAS: пытаемся перевести состояние из 0 в 1, пока не получится. Поток не засыпает, а крутится в цикле, отсюда название **спинлок** (spinlock, от spin — вращаться). ```go play 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) } ``` ```text 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»](/os/tasks/spinlock-sum). ## Крутиться или спать Пока поток A держит лок, поток B в спинлоке занимает ядро процессора на 100% и ничего полезного не делает. ```text Поток A ──────[ работает в критической секции ]──────► Unlock │ Поток B CAS CAS CAS CAS CAS CAS CAS CAS CAS CAS ────────┘ захватил (ядро процессора занято, полезной работы ноль) ``` Альтернатива — заснуть: попросить ОС снять поток с процессора и разбудить, когда лок освободится. Сон дорог по-своему: это системный вызов и два переключения контекста (уснуть и проснуться), единицы микросекунд (цифры — в главе [о цене системного вызова](/os/book/syscall-cost)). Выбор зависит от того, сколько держат лок: - Критическая секция на десятки наносекунд (инкремент, вставка в map). Владелец отпустит лок раньше, чем ОС успеет усыпить ждущего. Выгоднее покрутиться. - Секция на миллисекунды (ввод-вывод, тяжёлый расчёт). Крутясь, ждущий сожжёт миллионы тактов. Выгоднее заснуть и отдать ядро процессора другим. - Одно ядро процессора. Спин бесполезен в принципе: пока ждущий крутится, владелец не исполняется и не может отпустить лок. Поэтому настоящие мьютексы гибридные: немного крутятся (вдруг лок отпустят прямо сейчас) и только потом засыпают. Осталось понять, как заснуть дёшево. ## Ticket lock: очередь вместо лотереи У простого спинлока есть ещё один изъян. Когда лок освобождается, его хватает тот, чей CAS успел первым, а это во многом случайность (и топология кэшей: ядро процессора, которое только что держало линию с замком, часто выигрывает снова). Какой-то поток может проигрывать раз за разом. Это **голодание** (starvation). **Ticket lock** работает как электронная очередь в банке: берёте талон с номером и ждёте, пока табло покажет ваш номер. ```text 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») использует три состояния: ```text 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` — атомарный обмен: записать новое значение и вернуть старое. Прогоним по шагам с двумя потоками. ```text шаг поток действие 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), она снова встретится в главе про [условные переменные](/os/book/condition-variables). На этой схеме (с вариациями) построены `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](/go/book/scheduler-deep). - **Режим голодания.** Если горутина ждёт лок дольше 1 мс, мьютекс переходит в starvation mode: лок передаётся напрямую первой горутине в очереди, новые пришедшие не могут его перехватить. Идея та же, что у ticket lock. API и практика использования мьютексов — в Go-курсе: [примитивы синхронизации](/go/book/sync-primitives). ```text Go: sync.Mutex CAS → короткий спин → парковка горутины Linux: futex CAS в user space → futex_wait/futex_wake CPU: CAS, XCHG, TAS атомарная инструкция ``` Отсюда практический вывод. Цена `mu.Lock()` в горячем пути сильно зависит от **contention** (сколько горутин одновременно хотят этот лок). Без борьбы это десятки наносекунд. При борьбе — парковки, пробуждения, переключения, и лок становится узким местом. Как уменьшить борьбу, разбираем в следующей главе. > Интерактивный симулятор «Борьба потоков за лок»: Несколько потоков хотят один лок. Сплошные блоки это работа в критической секции, блёклые это время, потерянное на ожидание. Чем больше потоков и чем длиннее секция, тем дороже contention. Запустить: https://graphlms.ru/os/book/locks-hardware > Квиз по разделу: см. вопросы в конце документа или на https://graphlms.ru/os/book/locks-hardware ## Частые ошибки - Говорить, что 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 внутри. Сколько системных вызовов будет сделано к моменту, когда все трое отработают и отпустят лок? Ответы. (1) Между ними может вклиниться другой поток, прочитать то же «свободно» и тоже войти. (2) TAS безусловно пишет 1 и возвращает старое значение; CAS пишет новое значение, только если в ячейке лежит ожидаемое. (3) Чтобы Unlock знал, есть ли спящие: с двумя состояниями пришлось бы либо звать `futex_wake` при каждом Unlock, либо рисковать никого не разбудить. (4) Пять: B и C делают по `futex_wait` (2), A, B и C при Unlock видят значение 2 и делают по `futex_wake` (3), причём последний — лишний, будить уже некого. ## Что спрашивают на собесе - **Почему нельзя сделать лок на обычной булевой переменной?** Проверка и установка — два действия, между ними вклинивается другой поток. Нужна атомарная инструкция (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 мс. ## Вопросы для самопроверки **Квиз «Локи: от железа к futex»** 1. Почему наивный лок на обычной переменной-флаге не работает? - Переменная занимает слишком много памяти - Флаг нельзя хранить в куче - Проверка «свободно» и запись «занято» — два отдельных действия, между ними вклинивается другая поток (верно) - Компилятор всегда удаляет такую переменную - Пояснение: Между чтением флага и его записью может встрять другая поток, прочитав то же «свободно». Нужна атомарная инструкция, делающая прочитать+записать неделимо. 2. Чем compare-and-swap (CAS) отличается от test-and-set (TAS)? - Между ними нет разницы - CAS записывает новое значение лишь если в ячейке лежит ожидаемое; TAS пишет безусловно и возвращает старое (верно) - CAS всегда записывает 1, TAS — 0 - CAS работает только в ядре - Пояснение: TAS безусловно ставит 1 и возвращает прежнее значение. CAS условен: пишет, только если текущее значение совпало с ожидаемым. Поэтому CAS гибче и лежит в основе lock-free структур. 3. В каких случаях спинлок (крутиться) выгоднее засыпания? (несколько вариантов) - Есть свободное ядро, на котором можно крутиться (верно) - Лок держат очень короткое время (верно) - Лок держат долго (например, во время ввода-вывода) - Потоков в тысячи раз больше, чем ядер, и все ждут долго - Пояснение: Спин выгоден при коротком удержании и наличии свободного ядра: входим мгновенно, дешевле переключения контекста. При долгом удержании выгоднее заснуть и отдать ядро. 4. В чём главный выигрыш futex по сравнению с обычным засыпанием через ядро? - В неконтендном случае lock/unlock — это атомарный CAS в userspace, а syscall нужен только чтобы реально заснуть или разбудить (верно) - Он быстрее за счёт отключения кэша процессора - Он вообще никогда не делает системных вызовов - Он не требует атомарных инструкций - Пояснение: Fast path futex: когда лок свободен, захват/отпускание делаются атомарным CAS прямо в userspace без syscall. В ядро (futex WAIT/WAKE) идём только на медленной тропе — реально заснуть или разбудить спящего. 5. Какую проблему решает ticket lock? - Уменьшает размер критической секции - Делает лок рекурсивным - Полностью убирает атомарные инструкции - Голодание: выдаёт номера и обслуживает потока строго по очереди (FIFO) (верно) - Пояснение: Простой спинлок может бесконечно отдавать лок случайной потока, и одна поток голодает. Ticket lock выдаёт талончики и обслуживает по порядку прихода, гарантируя, что каждый дождётся. 6. Сколько системных вызовов делает идеальный futex-lock и futex-unlock, когда лок свободен (неконтендный случай)? - Ответ: 0 - Пояснение: Ноль. На быстром пути и захват, и отпускание — это только атомарный CAS в userspace. Системный вызов futex нужен лишь когда лок занят: заснуть (WAIT) или разбудить (WAKE).