Зачем вообще лок и почему «флаг занято» — это ловушка

Лок (lock, замок) — это способ сказать: «пока я работаю с общими данными, больше никто их не трогает». Бытовая аналогия — туалет в самолёте: замок на двери показывает «занято», и второй человек ждёт, пока не освободится. Без замка двое зашли бы одновременно, и было бы неловко.

В программировании «неловко» означает гонку данных (race condition) — когда две нити (потока) одновременно меняют одну переменную, и результат зависит от того, кто успел первым. Что такое нить и почему гонки портят данные — разобрано в главе threads-intro. Здесь мы спускаемся на уровень ниже: как сам замок устроен внутри — от инструкции процессора до системного вызова.

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

  Наивный лок на обычном флаге — САМ порождает гонку
 
  busy = 0   (0 = свободно, 1 = занято)
 
  Нить A                         Нить B
  ───────────────────────        ───────────────────────
  читает busy → видит 0
                                 читает busy → видит 0   ← тоже думает «свободно»!
  пишет busy = 1
                                 пишет busy = 1
  ВОШЛА в критическую            ВОШЛА в критическую
  секцию                         секцию
 
           ОБЕ внутри одновременно → данные испорчены

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

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

Лекарство — атомарная операция: процессор выполняет «прочитать и записать» как одно неделимое действие, которое никто не может прервать посередине. Слово «атом» здесь в исходном смысле — «неделимый». Никакая другая нить не вклинится между чтением и записью.

Две базовые атомарные инструкции, на которых строятся все локи:

test-and-set (TAS) — «атомарно: запиши 1 и верни то, что было раньше».

  TAS(addr):              // всё это — ОДНА неделимая инструкция CPU
      old = *addr         // прочитать старое значение
      *addr = 1           // записать 1 (захватить)
      return old          // вернуть, что было ДО записи

Если вернулось 0 — замок был свободен, и я его только что захватил. Если 1 — он был занят, я ничего не сломал, надо ждать. Главное: прочитать-и-записать прошло одним куском, второй нити не вклиниться.

compare-and-swap (CAS) — «атомарно: запиши новое значение, но только если там сейчас лежит ожидаемое». Более гибкий и потому более популярный примитив.

  CAS(addr, expected, new):   // одна неделимая инструкция CPU
      if *addr == expected:
          *addr = new
          return true         // успех: значение было тем, что я ждал
      else:
          return false        // кто-то опередил, значение уже другое

CAS — это фундамент всей неблокирующей синхронизации (lock-free структур, счётчиков, очередей; см. главу concurrent-structures). В Go он доступен через пакет sync/atomic — см. atomic.

  Захват лока через CAS-цикл (так делают спинлоки)
 
  state: 0 = свободно, 1 = занято
 
  Lock():
    ┌───────────────────────────────────────────┐
    │  пробуем: CAS(&state, 0, 1)                 │
    │     "если свободно (0) → поставь занято (1)"│
    └───────────────┬───────────────────────────┘
                    │
         ┌──────────┴───────────┐
       true                   false
   (было 0, мы захватили)  (было 1, занято кем-то)
         │                      │
         ▼                      ▼
   входим в секцию      крутимся в цикле и пробуем снова

Что нарисовано: цикл повторяет CAS, пока не поймает момент, когда замок свободен (0), и в тот же неделимый миг ставит 1. Двое не смогут «выиграть» один и тот же CAS — у одного вернётся true, у второго false.

Спинлок: просто, но жжёт CPU

Спинлок (spinlock, «крутящийся замок») — это и есть CAS-цикл выше: нить не засыпает, а активно крутится в цикле, постоянно дёргая CAS, пока замок не освободится. Аналогия — вы стоите под дверью туалета и каждую секунду дёргаете ручку, вместо того чтобы отойти и подождать сигнала.

  Спинлок: ожидающая нить В сжигает такты процессора впустую
 
  Нить A держит лок ──────[ работает в секции ]──────► отпускает
                                                          │
  Нить B  ручка-ручка-ручка-ручка-ручка-ручка-ручка ─────┘ поймала!
          (CAS,CAS,CAS,CAS — 100% загрузка ядра, ноль полезной работы)

Что нарисовано: пока A в критической секции, B молотит CAS вхолостую, занимая ядро на 100% и не делая ничего полезного. Если A держит лок наносекунды — это нормально: B покрутится чуть-чуть и войдёт, дешевле, чем городить сон. Но если A держит лок долго (например, делает ввод-вывод), B сожжёт миллионы тактов зря.

spin vs sleep: крутиться или спать?

Вот ключевой инженерный выбор. Когда замок занят, у ждущей нити два пути:

• spin (крутиться) — занять ядро и активно проверять. Плюс: как только лок освободился, входим мгновенно, без накладных расходов. Минус: жжём CPU.
• sleep (заснуть) — сказать ОС «разбуди меня, когда освободится», и отдать ядро другим. Плюс: не тратим CPU впустую. Минус: усыпление и пробуждение — это системный вызов и переключение контекста, дорогая операция (тысячи тактов; цену syscall разбирает глава syscall-cost).

  Что выгоднее — зависит от того, КАК ДОЛГО держат лок
 
  Время удержания лока:   очень коротко          долго
                          ────────────────────────────────────►
  spin (крутиться):       ВЫГОДНО ✓             плохо: жжём ядро
                          (вошли сразу,         все время ожидания
                           дешевле сна)
  sleep (заснуть):        невыгодно: цена       ВЫГОДНО ✓
                          syscall > выигрыша     (отдали ядро другим)

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

ticket lock: честность против голодания

У простого спинлока есть несправедливость: когда лок освобождается, его хватает случайная из крутящихся нитей. Одна и та же нить может проигрывать гонку много раз подряд — это голодание (starvation), когда поток вечно не получает ресурс.

Ticket lock («замок с талончиками») решает это как очередь в поликлинике с электронным табло. Каждая нить берёт талончик с номером и ждёт, пока на табло не загорится её номер.

  Ticket lock = «возьми талончик» + «обслуживается номер»
 
  next_ticket = 4   ← какой номер выдадим следующему
  now_serving = 2   ← кого обслуживаем прямо сейчас
 
  Lock():
     my = atomic_fetch_add(&next_ticket, 1)   // взял свой талончик, очередь сдвинул
     while now_serving != my:                 // жду, пока табло покажет мой номер
         spin
  Unlock():
     now_serving += 1                          // зову следующего по порядку
 
   Талончики:  [2]→[3]→[4]→[5]   обслуживаются строго по очереди, FIFO
                ↑
            now_serving

Что нарисовано: fetch_add атомарно выдаёт уникальный номер и сдвигает счётчик. Нити входят строго в порядке прихода — никто не проскочит вперёд, голодание исключено. Ценой того, что нельзя «случайно повезти» и войти раньше очереди.

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

Теперь главный трюк Linux. Чистый спинлок жжёт CPU. Чистый сон через ОС дорог даже тогда, когда лок свободен (всё равно идём в ядро спросить). Хочется лучшее из двух миров. Это и есть futex — fast userspace mutex, «быстрый мьютекс в пространстве пользователя».

Ключевое наблюдение: в подавляющем большинстве случаев лок свободен. Зачем тогда вообще ходить в ядро (делать syscall), если можно просто захватить замок атомарным CAS прямо в userspace? В ядро надо идти, только когда лок реально занят и нужно по-настоящему заснуть/разбудить.

Напомним два «слоя». Userspace (пространство пользователя) — обычный код вашей программы. Kernel (ядро) — привилегированный код ОС; попасть туда можно только через системный вызов, а это дорого. Идея futex: переменную-замок держать в userspace, и трогать ядро лишь в крайнем случае.

  FAST PATH — лок свободен (99% вызовов): НИКАКОГО syscall
 
  Lock:   CAS(&val, 0, 1) == true   → захватили, работаем. Ядро не трогали.
  Unlock: CAS(&val, 1, 0)           → отпустили. Ядро не трогали.
 
  ┌─────────────── userspace ───────────────┐
  │  atomic CAS  →  всё произошло здесь       │   ← быстро, наносекунды
  └──────────────────────────────────────────┘
            (граница ядра НЕ пересекается)
 
 
  SLOW PATH — лок занят: только тогда зовём ядро
 
  Lock:   CAS не удался (val уже 1)
            → syscall futex(WAIT)   "усыпи меня, пока val не изменится"
 
  ┌──────── userspace ────────┐   ┌────────── kernel ──────────┐
  │  CAS провалился ──────────────►  futex_wait: нить спит      │
  └───────────────────────────┘   │  в очереди ожидания         │
                                   └────────────────────────────┘
 
  Unlock (когда были ждущие):
            CAS(val→0), затем syscall futex(WAKE)   "разбуди одного из спящих"
 
  ┌──────── userspace ────────┐   ┌────────── kernel ──────────┐
  │  отпустил, есть ждущие ────────►  futex_wake: будит нить    │
  └───────────────────────────┘   └────────────────────────────┘

Что нарисовано: в неконтендном (без борьбы) случае lock и unlock — это просто атомарный CAS в userspace, ядро вообще не задействовано. Системный вызов futex дёргается только на медленной тропе: реально заснуть (WAIT), когда замок занят, или разбудить спящего (WAKE) при отпускании. Так futex платит за дорогой syscall лишь тогда, когда без него правда не обойтись.

Тонкость, ради которой futex и устроен атомарно: между «CAS провалился» и «зову futex(WAIT)» владелец мог уже отпустить лок. Поэтому ядро при WAIT ещё раз сверяет ожидаемое значение и, если оно изменилось, не усыпляет нить — иначе она могла бы заснуть навсегда («потерянное пробуждение»).

Как это связано с sync.Mutex в Go

sync.Mutex в Go построен на той же двухуровневой философии (см. sync-primitives):

• В неконтендном случае захват — это атомарный CAS над внутренним полем состояния, без всякого обращения к ОС. Быстро, как fast path у futex.
• При борьбе мьютекс сначала немного крутится (active spin) — вдруг владелец вот-вот отпустит и не придётся спать.
• Если спин не помог, горутина паркуется рантаймом Go. Здесь нюанс: Go не усыпляет нить ОС напрямую — рантайм снимает горутину с потока и ставит на поток другую, готовую к работе. Но в основе сна реальной OS-нити всё равно лежит futex. Подробнее про планировщик горутин — scheduler-deep.
• У Go-мьютекса есть и режим честности (starvation mode): если горутина ждёт лок дольше 1 мс, мьютекс переключается в FIFO-передачу владения — это лечит голодание ровно той же идеей, что и ticket lock.

  Иерархия: язык → ОС → железо
 
  ┌───────────────────────────────────────────────┐
  │  Go:    sync.Mutex  (спин + парковка горутины) │  языковой слой
  ├───────────────────────────────────────────────┤
  │  Linux: futex (fast CAS в userspace,           │  слой ОС
  │         syscall WAIT/WAKE на медленной тропе)  │
  ├───────────────────────────────────────────────┤
  │  CPU:   test-and-set / compare-and-swap         │  железо
  │         (атомарная инструкция)                  │
  └───────────────────────────────────────────────┘

Что нарисовано: один и тот же принцип проходит сквозь все слои. Внизу — атомарная инструкция процессора, в середине — futex, который экономит syscall'ы, наверху — sync.Mutex, который вы вызываете как обычный API. Понимая нижние слои, вы понимаете, почему «лишний» лок в горячем пути может стоить дёшево (CAS) или дорого (парковка через futex) — в зависимости от контендности.

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

• Почему нельзя сделать лок на обычной булевой переменной? Потому что «проверить свободно» и «поставить занято» — два действия, между ними вклинивается другая нить. Нужна атомарная инструкция (TAS/CAS), которая делает это неделимо.
• Чем CAS отличается от test-and-set? TAS безусловно пишет 1 и возвращает старое значение; CAS пишет новое значение только если там лежит ожидаемое. CAS гибче и лежит в основе lock-free структур.
• Когда спинлок лучше засыпания, и наоборот? Спин — если лок держат очень коротко (дешевле, чем переключение контекста) и есть свободные ядра. Сон — если удержание долгое: иначе сожжём CPU впустую. На практике — гибрид: чуть покрутиться, потом заснуть.
• Что такое futex и в чём его главный выигрыш? Fast userspace mutex: в обычном (неконтендном) случае lock/unlock — это атомарный CAS в userspace без syscall. Системный вызов нужен только чтобы реально заснуть (WAIT) или разбудить (WAKE).
• Что решает ticket lock? Голодание: выдаёт нитям номера и обслуживает строго по очереди (FIFO), так что ни одна нить не застрянет навсегда. В Go ту же проблему лечит starvation mode у sync.Mutex.
• Как устроен sync.Mutex под капотом? Атомарный CAS на быстром пути, короткий спин при борьбе, парковка горутины (в основе — futex) при длительном ожидании, и режим честности при ожидании дольше 1 мс.