Операционные системы
Продвинутая синхронизация
Big Kernel Lock жил в Linux с появления SMP в 1996 и блокировал ядро целиком на каждом syscall. В мае 2011 Арнд Бергманн вырубил последнее упоминание BKL в 2.6.39, финал десятилетнего марафона перевода ядра на fine-grained spinlocks, RCU и lock-free структуры. Цена синхронизации видна по latency: spinlock ~10ns без contention, ~100ns при борьбе за кеш-линию; futex wakeup ~25ns; полноценный mutex с переходом в kernel ~1µs. Между «масштабируется на 128 ядер» и «лочит каждый syscall» лежит выбор примитива.
- **Linux kernel routing:** RCU позволяет обрабатывать 200M packet lookups/sec без блокировок. Критично для data centers, где каждая наносекунда = деньги.
- **LMAX Disruptor:** Wait-free ring buffer с латентностью 50-100ns. Высокочастотная торговля, где microsecond delay = потеря миллионов долларов.
- **PostgreSQL MVCC:** Читатели не блокируют писателей через Multi-Version Concurrency Control (похоже на RCU). Позволяет обслуживать тысячи транзакций одновременно.
Цели урока
- Различать spinlock и mutex: spinlock выигрывает на коротких критсекциях многоядерных систем
- RW-lock: оптимизация для read-heavy workloads, проблема writer starvation
- RCU (Read-Copy-Update): zero-cost readers в Linux kernel, grace period для writers
- Lock-free vs wait-free, CAS (compare-and-swap), ABA problem
- Знать когда lock-free хуже locked (high contention, memory ordering сложен)
Spinlocks - активное ожидание
**Spinlock** - примитив синхронизации, где поток **активно крутится в цикле** (spinning), проверяя блокировку, вместо того чтобы уснуть. В отличие от mutex, который передаёт управление планировщику, spinlock сжигает CPU циклы в ожидании.
**Когда использовать spinlock:** - Критическая секция **очень короткая** (несколько инструкций) - Переключение контекста дороже, чем активное ожидание - В kernel space, где sleep невозможен (обработчики прерываний) - На многоядерных системах (на одном ядре spinlock = deadlock)
**Почему `pause` инструкция?** Без неё CPU агрессивно спекулирует, загружая cache lines. `pause` (x86) или `yield` (ARM) говорит процессору: "это spinloop, не спекулируй". Снижает энергопотребление и повышает производительность на 2-10x.
Spinlock в Linux kernel
Linux использует spinlock для защиты структур данных в контексте прерываний, где нельзя спать. Пример: `spin_lock_irqsave()` блокирует spinlock **и отключает прерывания на текущем CPU**, предотвращая deadlock. ```c // kernel/sched/core.c - планировщик Linux spin_lock_irqsave(&rq->lock, flags); update_rq_clock(rq); // Критическая секция: ~10 инструкций spin_unlock_irqrestore(&rq->lock, flags); ``` Критическая секция занимает наносекунды - переключение контекста было бы дороже.
**Опасность spinlock в userspace:** Если поток держит spinlock и выгружается планировщиком, остальные потоки жгут CPU в пустую до следующего quantum'а (миллисекунды!). Поэтому в userspace предпочитают **futex** или **adaptive mutex**.
Adaptive mutex - гибрид
Некоторые реализации pthread mutex (например, glibc) используют **adaptive spinning**: сначала спинят несколько итераций, затем засыпают через futex. Это даёт лучшее из двух миров: - Если блокировка быстро освобождается - избегаем context switch - Если ждём долго - не сжигаем CPU впустую
**Spinlock на одноядерном CPU = смерть!** На single-core системе spinlock, захваченный одним потоком, никогда не освободится (владелец не получит CPU). Всегда проверяй: `if (num_cpus > 1)`.
Почему spinlock подходит для критической секции в обработчике прерывания Linux kernel, но не подходит для долгой операции в userspace?
RW-locks - оптимизация для read-heavy workloads
**Read-Write Lock (rwlock)** позволяет **множеству читателей** одновременно держать блокировку, но **писатель эксклюзивен**. Идеально для структур данных, где чтения в 100x чаще записей (кеши, routing tables, конфигурации).
**Семантика rwlock:** - **Read lock (shared):** Несколько потоков могут читать одновременно - **Write lock (exclusive):** Только один писатель, блокирует всех читателей - **Fairness проблема:** Постоянный поток читателей может заморить писателя голодом (writer starvation)
**Проблема writer starvation:** Если читателей много и они постоянно захватывают lock, писатель может ждать бесконечно. Linux решает это через **queued rwlock** с приоритетом писателя: если писатель ждёт, новые читатели блокируются.
Routing table в networking stack
Таблица маршрутизации обновляется редко (при изменении сети), но читается на каждом пакете (миллионы раз в секунду). rwlock идеален: ```c // net/ipv4/fib_trie.c - Forwarding Information Base read_lock(&fib_lock); struct fib_result res; fib_lookup(net, &fl4, &res, 0); // Поиск маршрута read_unlock(&fib_lock); // Обновление (редкое): write_lock(&fib_lock); fib_table_insert(tb, &cfg); // Изменение таблицы write_unlock(&fib_lock); ``` Пропускная способность: ~10M lookups/sec без блокировок читателей.
**Seq-lock - оптимизация для крайне редких записей.** Читатели вообще не блокируются! Вместо этого проверяют **sequence counter** до и после чтения. Если счётчик изменился - повтор. Писатель инкрементирует счётчик. Используется для системного времени в Linux (`xtime_lock`).
Когда rwlock хуже обычного mutex?
Если записей столько же, сколько чтений (50/50), rwlock **медленнее** mutex! Причина: bookkeeping (подсчёт читателей) дороже простого atomic флага. Профилируй перед оптимизацией: - **Чтений 90%+** → rwlock выигрывает - **Чтений 50-60%** → mutex быстрее - **Чтений 99%+, записи редкие** → RCU (следующий концепт)
В каком сценарии rwlock даст наибольший прирост производительности по сравнению с обычным mutex?
RCU - читатели без блокировок
**Read-Copy-Update (RCU)** - революционная техника синхронизации из Linux kernel. Читатели **вообще не берут блокировки**! Идея: писатель создаёт новую версию данных, ждёт пока все читатели закончат со старой версией, затем освобождает старую. RCU - святой Грааль для read-heavy структур.
**RCU ключевые концепции:** - **Grace Period** - период между публикацией новой версии и освобождением старой. Гарантия: все читатели, начавшие до публикации, закончили - **Quiescent State** - момент, когда поток гарантированно не держит RCU-защищённые указатели - **Reclamation** - безопасное удаление старых версий после grace period
**Почему `rcu_read_lock()` не блокирует?** Это просто инкремент thread-local счётчика! Никакого atomic'а, никакой cache coherence traffic. Затраты: ~1-2 CPU цикла. Сравни с mutex (~50-100 циклов) или даже atomic increment (~20 циклов).
RCU в Linux routing table
Linux использует RCU для FIB (Forwarding Information Base) - таблицы маршрутизации. Каждый сетевой пакет делает lookup (миллионы в секунду), обновления редки. ```c // net/ipv4/fib_semantics.c rcu_read_lock(); nh = fib_info_nh(fi, 0); // Поиск next hop if (nh->nh_dev == dev) { // Используем старую версию, даже если кто-то обновляет! } rcu_read_unlock(); ``` Производительность: 40M lookups/sec на single core без cache misses!
**Grace Period реализация:** Как узнать, что все читатели закончили? Linux следит за **context switches**: если все CPU прошли через scheduler, значит все RCU critical sections завершились. Это может занять миллисекунды, поэтому `synchronize_rcu()` - **blocking call**.
Когда НЕ использовать RCU?
RCU не серебряная пуля: 1. **Частые записи** - каждое обновление создаёт копию. Дорого для write-heavy workloads 2. **Большие структуры** - копирование мегабайтной структуры убьёт производительность 3. **Нужен строгий порядок** - читатели могут видеть старые версии до grace period Пример: счётчик запросов. Каждый запрос - запись, копировать счётчик бессмысленно. Atomic increment намного проще.
**Memory ordering в RCU критичен!** `rcu_assign_pointer()` включает **memory barrier**: гарантирует, что новая версия полностью инициализирована до публикации. Без барьера читатели могли бы увидеть частично обновлённые данные (reordering!).
Почему RCU использует Copy-on-Write вместо прямого обновления структуры данных?
Lock-free структуры данных
**Lock-free структуры данных** - святой Грааль многопоточности. Гарантия: хотя бы **один поток всегда прогрессирует**, даже если другие подвисли. Никаких блокировок, только **atomic операции** и **Compare-And-Swap (CAS)**. Сложны в реализации, но дают высокую производительность.
**Уровни прогресса (progress guarantees):** - **Wait-free:** Каждая операция завершается за **ограниченное число шагов**. Идеал, но крайне сложен - **Lock-free:** **Хотя бы один поток** прогрессирует. Retry может быть бесконечным для unlucky потоков - **Obstruction-free:** Прогресс если поток работает **в одиночку** (без contention) - **Blocking (lock-based):** Блокировка может привести к полной остановке
**ABA problem - коварный баг lock-free структур.** Сценарий: поток A читает head=X, засыпает. Поток B удаляет X, затем allocates X снова (тот же адрес!). Поток A просыпается, CAS успешен (адрес тот же), но данные изменились! Решение: **tagged pointers** или **hazard pointers**.
ABA problem визуализация
``` Изначально: Stack = [A → B → C] Thread 1: pop() 1. Читает head=A, next=B 2. Засыпает перед CAS Thread 2: 1. pop() → удаляет A 2. pop() → удаляет B 3. push(A) → аллоцирует A снова (тот же адрес!) Stack = [A → C] Thread 1 просыпается: 1. CAS(&head, A, B) - УСПЕШНО! (адрес A тот же) 2. head = B - но B уже удалён! 3. Stack → [B (freed!) → ???] → КРАШ ``` Решение: вместо указателя хранить `{pointer, version}`.
**Memory ordering в lock-free коде критичен!** CPU и компилятор переупорядочивают инструкции. Без memory barriers можно увидеть частично обновлённые данные. Стандартные модели: **Acquire/Release** (большинство платформ), **Sequential Consistency** (самая сильная, медленная).
Lock-free queue в Facebook Folly
Facebook разработал `folly::MPMCQueue` - Multiple-Producer-Multiple-Consumer lock-free очередь. Используется в тысячах сервисов: ```cpp folly::MPMCQueue<int> queue(1024); // Размер фиксирован // Producer (любое количество потоков): queue.blockingWrite(42); // Wait-free если есть место // Consumer (любое количество потоков): int value; queue.blockingRead(value); // Wait-free если есть элементы ``` Производительность: 40M ops/sec на 8 cores. Обычная очередь с mutex: ~5M ops/sec.
**Когда НЕ использовать lock-free?** Сложность растёт экспоненциально. Если критическая секция короткая и contention низкий - обычный mutex **проще и быстрее**. Lock-free оправдан для: 1) High contention (>8 потоков), 2) Латентность критична, 3) Real-time системы.
Real-world: Disruptor pattern
LMAX Exchange (высокочастотная торговля) разработали **Disruptor** - wait-free ring buffer. Латентность: **50-100 наносекунд** для передачи сообщения между потоками! Идея: производители и потребители работают с разными частями ring buffer, минимизируя cache contention. Каждый элемент имеет sequence number. Координация через atomic increments. Обычная очередь с блокировками: ~1-10 микросекунд. Disruptor: в 100x быстрее.
Ключевые идеи
- **Spinlocks - для коротких критических секций в kernel space.** Активное ожидание дешевле context switch, если блокировка держится наносекунды. В userspace опасны (выгрузка планировщиком).
- **RW-locks оптимизируют read-heavy workloads (90%+ чтений).** Множество читателей параллельно, писатель эксклюзивен. Проблема writer starvation решается через queued locks.
- **RCU - читатели без блокировок через Copy-on-Write.** Новая версия публикуется атомарно, старая удаляется после grace period. Идеально для routing tables, где 99%+ чтений.
- **Lock-free структуры гарантируют прогресс без блокировок.** Через CAS и atomic операции. Сложны (ABA problem, memory ordering), но дают высокую производительность при высоком contention (16+ потоков).
Связанные темы
Продвинутая синхронизация - вершина пирамиды параллелизма. Базируется на низкоуровневых концепциях и применяется в высоконагруженных системах:
- Атомарные операции и memory ordering — Lock-free структуры построены на atomic CAS, load/store с Acquire/Release семантикой. Понимание memory barriers критично
- Cache coherence и MESI protocol — Spinlock на разных CPU создаёт cache coherence traffic. Понимание MESI объясняет почему false sharing убивает производительность
- Распределённые системы — RCU - это распределённый консенсус в рамках одной машины. Grace period похож на 2PC (two-phase commit)
- Database concurrency control — MVCC (Multi-Version Concurrency Control) в PostgreSQL - аналог RCU для транзакций. Snapshot isolation через версионирование
Вопросы для размышления
- Дизайн in-memory cache для веб-сервера: 95% чтений, 5% записей, 64 ядра. Какой примитив синхронизации выбрать: mutex, rwlock, RCU или lock-free map? Почему?
- Почему Linux kernel использует разные примитивы для разных контекстов: spinlock в interrupt handlers, mutex в process context, RCU для routing? Какие trade-offs?
- Допустим, найден lock-free алгоритм, который в benchmark'ах в 10x быстрее mutex. Когда стоит его использовать, а когда остаться с mutex? Какие риски?