Модуль 2 ⏱ ~36 мин чтения 📐 4 Mermaid диаграмм

33. Mutex, Semaphore, Spinlock на уровне ОС

Введение: Эволюция от блокировок к примитивам

В предыдущих разделах мы подробно исследовали, как операционная система жонглирует памятью, переключает контексты процессов и обрабатывает системные прерывания. Но как только несколько потоков или процессов начинают одновременно претендовать на один и тот же участок памяти, мы неизбежно сталкиваемся с фундаментальной дилеммой Computer Science: как гарантировать взаимное исключение (Mutual Exclusion), не превращая высокопроизводительный процессор в бесполезную печку?

В повседневной разработке на Go программист привычно пишет:

mu.Lock()
defer mu.Unlock()

Эта конструкция выглядит обманчиво просто — словно мы повернули механический ключ в замочной скважине. Однако за этой строчкой скрывается сложнейший и элегантный танец между userspace, ядром Linux и аппаратной когерентностью процессорных кэшей. Чтобы не платить за каждое обращение к разделяемому ресурсу колоссальную цену системного вызова и полного context switch, инженеры создали три ключевых примитива синхронизации: Spinlock, Mutex и Semaphore.

Понимание их внутреннего устройства на уровне транзисторов, инструкций CPU и структур ядра критично для проектирования надежных highload-сервисов и успешного прохождения глубоких архитектурных интервью.

Spinlock: Busy-waiting и цена cache coherency

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

// Классический концептуальный цикл спинлока
while (!trylock(&lock)) {
    // Ждем в активном цикле, прожигая такты CPU
}

Житейская аналогия проста: представьте кабинку, у двери которой стоит человек и каждые полсекунды дергает ручку двери. Если человек внутри зашел буквально на две секунды помыть руки, такое поведение оправдано: дергающий сэкономит время на возвращение за свой рабочий стол. Но если человек внутри решил принять часовую ванну, дергающий ручку потратит 100% своих сил впустую, мешая всем вокруг.

flowchart TD
    Start["Попытка захватить Spinlock"] --> CAS{"Атомарная проверка<br/>LOCK CMPXCHG"}
    CAS -->|"Успех (был 0, стал 1)"| Acquired["Критическая секция захвачена!"]
    CAS -->|"Занят (уже 1)"| Spin["Активный цикл (PAUSE / nop)<br/>Прожигание тактов CPU"]
    Spin --> CAS

    classDef ok fill:#022c22,stroke:#10b981,stroke-width:2px,color:#f8fafc;
    classDef busy fill:#450a0a,stroke:#f43f5e,stroke-width:2px,color:#f8fafc;
    classDef step fill:#1e293b,stroke:#38bdf8,stroke-width:2px,color:#f8fafc;

    class Start,CAS step;
    class Acquired ok;
    class Spin busy;

Под капотом: Атомарность и MESI

В современных многопроцессорных системах (SMP) каждое ядро хранит данные в своих локальных кэшах L1/L2. Когда ядро хочет атомарно изменить переменную блокировки, оно должно гарантировать, что ни одно другое ядро не прочитает устаревшее значение. Это аппаратное требование обеспечивается протоколом MESI (Modified, Exclusive, Shared, Invalid).

Для реализации Spinlock процессор использует инструкцию LOCK CMPXCHG (Compare-And-Swap).

Префикс LOCK# исторически блокировал системную шину памяти, а в современных CPU захватывает монопольное владение строкой кэша в состоянии Exclusive / Modified.
Если флаг свободен (0), процессор атомарно меняет его на 1 и передает управление в критическую секцию за доли наносекунды.
Если флаг занят (1), ядро продолжает крутиться в бесконечном цикле while !trylock().

Ловушка / Gotcha

Cache Thrashing (пинг-понг кэш-линий): При высокой конкуренции кэш-линия, содержащая флаг, постоянно переходит в состояние Invalid на ядрах, которые не владеют блокировкой. Это убивает производительность. Spinlock эффективен только при:

Крайне коротких критических секциях (< 100 инструкций).
Низкой конкуренции.
Коде ядра, где поток вообще нельзя усыплять (обработчики аппаратных прерываний). На одноядерной системе спинлок вообще не крутится в цикле: ядро (в сборке без SMP) в этом случае лишь отключает вытеснение, ведь пока владелец не отпустил блокировку, ждать её на единственном ядре бессмысленно.

Блокирующий Mutex и архитектура futex

Если критическая секция длинная (например, запись на диск, сетевой вызов или сложная перестройка хэш-таблицы), сжигать миллионы тактов процессора в активном спинлоке — непозволительное расточительство.

Блокирующий Mutex (Mutual Exclusion) решает эту проблему радикально: если ресурс занят, вызывающий поток добровольно засыпает, освобождая процессорное ядро для выполнения других полезных задач.

В ранних версиях Unix каждый вызов мьютекса требовал безусловного обращения к ядру через системный вызов. Это было крайне медленно: даже когда на мьютекс никто не претендовал, программа платила сотни наносекунд за смену колец привилегий. Революция произошла в ядре Linux 2.6 с появлением подсистемы futex (Fast Userspace Mutex), спроектированной Франком ван де Веном, Расти Расселом и Ульрихом Дреппером.

Как работает futex (пошагово)

Фундаментальный принцип futex — разделить путь без конкуренции (Fast Path) и путь с конфликтом (Slow Path):

Userspace Fast Path: Программа пытается захватить мьютекс атомарной инструкцией CMPXCHG прямо в пользовательском пространстве. Если блокировка свободна (никто не держит ресурс), значение меняется с 0 на 1 за одну машинную инструкцию (~10–15 нс). Никаких системных вызовов, никакого перехода в кольцо Ring 0!
Slow Path: Если флаг уже занят, userspace-код понимает, что без ожидания не обойтись, и выполняет системный вызов futex() с флагом FUTEX_WAIT. Ядро Linux находит соответствующий хэш-бакет, создает внутреннюю очередь ожидания (waitqueue) и переводит вызывающий поток из состояния TASK_RUNNING в спящее состояние TASK_INTERRUPTIBLE (поэтому ожидание на futex прерывается сигналом и возвращает EINTR), паркуя его.
Wake Up: Когда владелец критической секции освобождает ресурс, он сбрасывает счетчик в userspace. Если он видит, что за мьютекс боролись другие потоки, он выполняет syscall futex с флагом WAKE_OP (или FUTEX_WAKE). Ядро будит поток из очереди ожидания, переводит его обратно в TASK_RUNNING и планировщик ОС возвращает ему управление.

flowchart TD
    classDef process  fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success  fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef error    fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
    classDef warning  fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef entry    fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
    classDef aux      fill:#334155,stroke:#64748b,stroke-width:1px,color:#f8fafc
    classDef system   fill:#312e81,stroke:#a78bfa,stroke-width:1px,color:#f8fafc
    classDef data     fill:#132d29,stroke:#2dd4bf,stroke-width:1px,color:#f8fafc
    classDef network  fill:#881337,stroke:#fb7185,stroke-width:1px,color:#f8fafc
    classDef accent   fill:#1e1b4b,stroke:#818cf8,stroke-width:1px,color:#f8fafc
    A["Попытка захвата в userspace"]:::warning -->|"Атомарная CAS"| B{"Флаг свободен?"}
    B -->|"Да"| C["Захват успешно выполнен"]
    B -->|"Нет"| D["syscall futex FUTEX_WAIT"]
    D --> E["Ядро: добавление в очередь ожидания"]
    E --> F["Усыпление потока"]
    G["Владелец: syscall futex FUTEX_WAKE"]:::system --> H["Ядро: удаление из очереди"]
    H --> I["Будение потока"]
    I --> A

Semaphore: Обобщение mutex

Если Mutex — это замок, рассчитанный строго на одного владельца (бинарный семафор с емкостью 1), то Semaphore (семафор Дейкстры) — это примитив с внутренним целочисленным счетчиком ($N$) и очередью ожидания. Он разрешает одновременный доступ не более чем $N$ конкурентным потокам:

Wait (исторически операция P от нидерландского proberen — пробовать / уменьшать): уменьшает счетчик на 1. Если счетчик был равен 0, вызывающий поток блокируется до тех пор, пока кто-то не освободит слот.
Post (исторически операция V от нидерландского verhogen — увеличивать): увеличивает счетчик на 1 и пробуждает один ожидающий поток из очереди.

Как это устроено на разных уровнях:

Linux: Системные вызовы sem_wait() / sem_post() работают с объектами ядра через системные вызовы semop() (в System V) или через мультиплексирование futex (в POSIX libpthread).
Go: В расширенной библиотеке Go пакет golang.org/x/sync/semaphore (в стандартной библиотеке sync/semaphore нет) реализует взвешенные семафоры. Сама же блокировка горутин в рантайме Go опирается на структуру semaRoot с двусвязным списком (next, prev) для очередей ожидания (g структур) и обходится без системных вызовов ядра, если конкуренция мала.

Mechanical Sympathy: CPU, кэш-линии и контекстные переключения

Для Senior/Lead инженера критично понимать реальную физическую стоимость операций на современном оборудовании:

Примитив	Механизм блокировки	Стоимость при конкуренции	Влияние на CPU
Spinlock	Атомарный цикл (CAS)	Низкая (если contention < 10%)	Высокий (busy-wait, кэш-линии в MESI)
Mutex (futex)	userspace CAS + kernel sleep	Средняя/Высокая	Низкий (поток спит, CPU свободен)
Semaphore	Счетчик + очередь	Зависит от N и contention	Аналогично Mutex

Ключевой инсайт: Контекстный switch в Linux требует смены стека ядра, обновления task_struct, инвалидации TLB и переключения CSR (Control Status Register). Это не "бесплатно". Go runtime минимизирует эту стоимость за счет адаптивного спиннинга и мультиплексирования горутин.

flowchart LR
    subgraph OSContextSwitch["Цена смены контекста ОС (~1-3 мкс)"]
        direction TB
        SaveRegs["Сохранение регистров CPU"]
        SwitchStack["Переключение стека ядра (RSP)"]
        UpdateTask["Обновление task_struct"]
        FlushTLB["Сброс кэша трансляции страниц (TLB)"]
    end

    subgraph GoContextSwitch["Смена контекста горутины в Go (~10-50 нс)"]
        direction TB
        SaveG["Сохранение 3 регистров (SP, PC, BP) в g.sched"]
        SwitchG["Перестановка указателя g на m.curg"]
        ResumeG["Переход по PC следующей горутины"]
    end

    classDef os fill:#450a0a,stroke:#f43f5e,stroke-width:2px,color:#f8fafc;
    classDef go fill:#022c22,stroke:#10b981,stroke-width:2px,color:#f8fafc;

    class OSContextSwitch,SaveRegs,SwitchStack,UpdateTask,FlushTLB os;
    class GoContextSwitch,SaveG,SwitchG,ResumeG go;

Go-реализация: Почему мы не используем OS-мьютексы?

В традиционных языках (C++, Java, Rust) std::mutex или ReentrantLock часто напрямую оборачивают вызовы pthread_mutex или POSIX futex. В мире Go это было бы катастрофой из-за уникальной модели планировщика M-P-G (Machine-Processor-Goroutine).

Внутреннее устройство `sync.Mutex`

В рантайме Go структура sync.Mutex предельно компактна:

type Mutex struct {
    state int32
    sema  uint32
}

Поле состояния mutex в структуре sync.Mutex — это 32-битная битовая маска:

Бит 0 (mutexLocked): заблокировано
Бит 1 (mutexWoken): взведен флаг пробуждения (горутина уже проснулась и пытается захватить лок)
Бит 2 (mutexStarving): режим голодания (Starvation Mode, если ожидание превысило 1 мс)
Старшие 29 бит: количество ожидающих горутин (waiters)

flowchart LR
    subgraph Bitmask["32-битное поле state в sync.Mutex"]
        direction LR
        Waiters["Биты 3..31: waiters count (Ожидающие g)"]
        Starv["Бит 2: mutexStarving"]
        Woken["Бит 1: mutexWoken"]
        Locked["Бит 0: mutexLocked"]
    end

    classDef bmask fill:#1e293b,stroke:#6366f1,stroke-width:2px,color:#f8fafc;
    class Bitmask,Waiters,Starv,Woken,Locked bmask;

При вызове Lock() рантайм Go выполняет умный трехступенчатый алгоритм:

Fast Path: Атомарно проверяет флаг с помощью atomic.CompareAndSwapInt32(&m.state, 0, mutexLocked). Если мьютекс свободен — захватывает и моментально возвращает управление.
Адаптивный Spinlock: Если мьютекс занят, но мы работаем на многоядерной машине, планировщик пытается выполнить короткий SpinLock (до ~4 итераций инструкции PAUSE), пока waiters равны 0. Если критическая секция владельца крошечная, мы успеем забрать лок без усыпления!
Slow Path: Если спин не удался, вызывается функция runtime_SemacquireMutex(), которая:
- Добавляет структуру текущей горутины g в очередь ожидания (двусвязный список).
- Горутина переходит в состояние _Gwaiting и снимается с системного потока m. Поток m берет на исполнение другую готовую горутину!
- Если свободных горутин нет вообще, тред m может сделать syscall futex для усыпления.
- При освобождении мьютекса разблокированная горутина проверяет, действительно ли она получила блокировку (защита от ложных пробуждений — spurious wakeup).

Собеседование

Вопрос: Почему sync.Mutex не использует системный pthread_mutex напрямую?

Ответ: Системный мьютекс блокирует ОС-поток (m). Если горутине нужно ждать, а она привязана к m, все остальные горутины на этом m останавливаются (thread parking).

Go реализует свой мьютекс в userspace, который будит именно легкую структуру g из очереди ожидания планировщика, а не m. Поток операционной системы остается активным и немедленно берет в работу соседние горутины. Это спасает сервер от тысяч заблокированных потоков ОС и экономит гигабайты оперативной памяти.

Ловушки, corner-case и вопросы с собеседований

1. Lock Convoying (Конвой блокировок)

Когда множество горутин борются за один и тот же Mutex, они выстраиваются в длинную очередь. Если критическая секция занимает даже скромные несколько десятков микросекунд, конвой начинает расти лавинообразно. Время удержания блокировки складывается со временем пробуждения, резко повышая 99-й перцентиль задержки (p99 latency).

Решение:

Используйте sync.RWMutex для сценариев, где чтений многократно больше, чем записей (read-heavy workload).
Дробите гранулярность блокировок (Striping / Sharding, как сделано в высоконагруженных concurrent cache).
Используйте golang.org/x/sync/semaphore с пулом разрешений N > 1 для параллельного доступа.

2. Priority Inversion (Инверсия приоритетов)

Классическая беда многопоточности: низкоприоритетный поток захватывает мьютекс. Поток со средним приоритетом вытесняет его на CPU. В это время высокоприоритетный поток пытается взять мьютекс и блокируется. В итоге высокоприоритетная задача ждет среднюю, к которой вообще не имеет отношения!

В Go: Планировщик не имеет жестких приоритетов в классическом понимании, но sync.Mutex внедряет механизм защиты от голодания (Starvation Mode) через очередь waitq. Если горутина ждет мьютекс дольше 1 миллисекунды, мьютекс переключается в режим starvation: владение передается строго по очереди первой ожидающей горутине, а вновь прибывшие горутины лишаются права вклиниваться через спиннинг.

3. Gotcha: `sync.Mutex` не реентерабельный

В отличие от std::recursive_mutex в C++ или мониторов в Java, sync.Mutex в Go не является реентерабельным. Если горутина, уже владеющая мьютексом, попытается вызвать mu.Lock() повторно в той же цепочке вызовов, она заблокирует сама себя навсегда. Это моментальный взаимный тупик (Deadlock).

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

4. Сравнение с другими языками

PHP / Java (классический Threading): Используют потоки операционной системы и системные мьютексы. Блокировка мьютекса = блокировка потока ОС. Высокая стоимость переключения при сильной конкурентности.
Go: Green threads (горутины) + собственный планировщик в пространстве пользователя + кастомный гибридный мьютекс на базе спиннинга и очередей горутин. Стоимость блокировки в 10–100 раз ниже на высоких параллельных нагрузках.
C++: std::mutex чаще всего прямо транслируется в вызовы pthread_mutex. Максимальная скорость в простых сценариях, но отсутствие встроенного мультиплексирования легких потоков.

Итоги

Spinlock эффективен только при крайне коротких критических секциях и низкой конкуренции. Он избегает затрат на context switch, но сжигает ресурсы процессора и порождает лавину инвалидаций кэш-линий по протоколу MESI.
Mutex (futex) — признанный золотой стандарт системной синхронизации. Он блестяще сочетает Fast Path в userspace через инструкцию CMPXCHG с медленным путем засыпания в ядре (FUTEX_WAIT / TASK_INTERRUPTIBLE).
Semaphore обобщает концепцию взаимного исключения до $N$-конкурентных слотов. В Go блокировка горутин на семафорах рантайма организована через semaRoot с двусвязным списком очередей горутин g, а готовый взвешенный семафор — в golang.org/x/sync/semaphore.
Go не использует системные мьютексы ОС напрямую, поскольку парковка потока ядра m парализовала бы все остальные горутины, назначенные на этот поток.
Инженерное правило: Никогда не оптимизируйте блокировки вслепую. Снимайте профили блокировок через pprof (блок block и mutex), заменяйте простые счетчики на sync/atomic и держите критические секции предельно компактными.

Мы детально разобрали, как примитивы синхронизации балансируют между пользовательским пространством и ядром. Однако неправильное использование этих примитивов порождает опаснейшие аномалии многопоточных систем. В следующей лекции мы разберем главных врагов конкурентного программирования: 34. Deadlock, Livelock, Starvation.