Синхронизация

Цели урока

• Понимать mutex и причины deadlock (4 условия Коффмана)
• Различать mutex и semaphore: ownership vs counting
• Применять condition variable для event-driven ожидания без busy spin
• Строить фазовую синхронизацию через barrier, понимать load imbalance

Предварительные знания

• Threads and Processes

1997 год. Марсоход Pathfinder перезагружается на Марсе - снова и снова. Причина: priority inversion. Низкоприоритетный поток держит mutex, который нужен высокоприоритетному. Баг синхронизации за 265 млн долларов - на другой планете. Инженеры NASA починили его удалённо через patch. Понимание примитивов синхронизации буквально спасает миссии.

• **Базы данных:** каждая транзакция использует locks для ACID-гарантий; deadlock detection - стандартная функция СУБД
• **Операционные системы:** все ресурсы ядра (файловая система, сеть, память) защищены мьютексами и семафорами
• **Game engines:** рендер-поток и физика-поток синхронизируются через barrier каждый кадр
• **PyTorch DDP:** barrier синхронизирует градиенты между GPU после каждого backward pass

Дейкстра и семафоры

Эдсгер Дейкстра изобрёл семафоры в 1965 году при разработке операционной системы THE. Операции P (proberen = проверить, acquire) и V (verhogen = увеличить, release) - голландские слова. В том же году Дейкстра сформулировал задачу обедающих философов - классическую иллюстрацию deadlock и проблем синхронизации. Оба результата вышли в одной статье "Cooperating Sequential Processes".

Mutex: взаимное исключение

1997 год. Марсоход Pathfinder на Марсе начинает перезагружаться без причины. Инженеры NASA за 300 миллионов км от проблемы. Причина - низкоприоритетный поток держит mutex, нужный высокоприоритетному. Priority inversion. Баг синхронизации стоимостью в 265 млн долларов - на другой планете.

**Mutex** (mutual exclusion) - замок, гарантирующий что критическую секцию кода выполняет только один поток. Одноместная кабинка: дверь заперта - жди. Открыта - заходи и запри за собой.

**Deadlock** - смертельная опасность мьютексов. Поток A захватил lock1, ждёт lock2. Поток B захватил lock2, ждёт lock1. Оба ждут вечно. Решение: всегда захватывать мьютексы в одном порядке (lock ordering) или использовать trylock с таймаутом.

**4 условия Коффмана** для deadlock: 1. mutual exclusion 2. hold and wait 3. no preemption 4. circular wait. Убери любое - deadlock невозможен. Lock ordering убирает circular wait.

Semaphore: обобщённый счётчик

Mutex - бинарный: занят или свободен. **Семафор** - обобщение: счётчик, разрешающий N одновременных потоков. Парковка на 5 мест: если свободных нет - жди. Когда кто-то уезжает - заезжай. Connection pool в любом production-приложении работает именно так.

**Ключевое отличие от mutex:** семафор не имеет владельца. Один поток может сделать acquire, а другой - release. Это позволяет реализовать паттерн **producer-consumer**: producer делает release ("произвёл элемент"), consumer делает acquire ("забрал элемент").

Condition Variable: ждём события

Mutex защищает данные. Но что если поток должен **ждать определённого состояния** данных? "Жди, пока очередь не станет непустой". Можно крутить цикл (busy waiting) - но это жжёт CPU впустую. В Go runtime, Java thread pool, Rust Tokio - везде под капотом одно и то же: **condition variable**. Усни и проснись, когда условие выполнено.

**Spurious wakeups:** поток может проснуться без notify! Поэтому всегда используйте `while (condition)`, а не `if (condition)` перед wait(). Это не баг - это особенность реализации на уровне ОС (сигналы, планировщик).

**Паттерн:** condition variable всегда используется в связке с mutex. Mutex защищает shared state, condition variable - для ожидания изменения этого state. Операция wait() **атомарно** отпускает mutex и усыпляет поток. При пробуждении mutex снова захвачен.

Barrier: точка синхронизации

Google MapReduce, Apache Spark, обучение нейросетей - все делают одно: разбивают работу на независимые куски, считают параллельно, потом **объединяют**. Момент "все посчитали, теперь объединяем" - это barrier. Точка, где все потоки ждут друг друга, прежде чем продолжить.

Barrier - потенциальное узкое место. Если один поток медленнее остальных, все остальные простаивают. Это **load imbalance** - одна из главных проблем параллельных систем. Решение: динамическое распределение работы (work stealing). В GPU-вычислениях `__syncthreads()` в CUDA синхронизирует все потоки в блоке - без этого один warp может прочитать данные, которые другой ещё не записал.

Ключевые идеи

• **Mutex** - один поток в критической секции; deadlock возможен при нарушении lock ordering
• **Semaphore** - счётчик на N одновременных доступов; нет владельца (producer/consumer паттерн)
• **Condition Variable** - "усни, пока условие не выполнено"; всегда с while (spurious wakeups убивают с if)
• **Barrier** - "жди всех, потом продолжай"; время фазы = время самого медленного потока

Связанные темы

Синхронизация - основа для параллельных алгоритмов и систем:

• Потоки и процессы — Синхронизация нужна, потому что потоки разделяют память
• Системы реального времени — Priority inversion и priority inheritance - критичны для RT-систем
• Консенсус в distributed systems — Mutex на уровне кластера - те же идеи, другой масштаб

Вопросы для размышления

• Go продвигает каналы вместо мьютексов: "Don't communicate by sharing memory; share memory by communicating". В чём преимущество этого подхода?
• Можно ли полностью избежать мьютексов, используя только lock-free структуры данных? Какие trade-offs?
• Как инженеры NASA починили баг priority inversion на Pathfinder, находясь на Земле, а марсоход - на Марсе?

Связанные уроки

• par-02 — Потоки и shared memory - основа для понимания зачем нужны примитивы
• par-04 — Lock-free структуры строятся поверх понимания mutex
• rts-02 — Priority inversion в RT-системах - прямое следствие mutex ownership
• ds-03 — Консенсус в distributed systems - mutex на уровне кластера
• par-08 — Параллельные алгоритмы требуют грамотной sync-стратегии
• stream-03 — Message brokers как альтернатива shared memory через message passing
• os-05-sync
• os-03-threads