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

Программа считает `1 + 1 = 1`. Банковский счёт теряет деньги при переводе. Это **race condition**. Когда несколько потоков одновременно модифицируют данные без синхронизации, результат непредсказуем и зависит от случайного порядка выполнения инструкций процессора. Синхронизация - это не просто "замки для данных", это фундаментальная проблема параллельных вычислений, которую решали величайшие умы Computer Science: Dijkstra, Hoare, Lamport.

• **Базы данных:** транзакции с уровнями изоляции - это реализация семафоров и блокировок на уровне строк и таблиц. MVCC (Multi-Version Concurrency Control) в PostgreSQL позволяет читателям и писателям не блокировать друг друга.
• **Веб-серверы:** thread pool обрабатывает запросы параллельно, но лог-файл один. Без mutex для записи в лог - файл будет испорчен перемешанными строками разных потоков. Nginx использует lock-free структуры для минимизации блокировок.
• **ОС:** планировщик процессов сам использует spin-lock и семафоры для синхронизации своих внутренних структур. Linux kernel: futex (fast userspace mutex) - гибрид spin-lock и системного вызова для минимизации переключений контекста.
• **Игры:** рендеринг в одном потоке, физика в другом, AI в третьем. Все читают позиции объектов - нужна синхронизация. Unreal Engine использует lock-free queues для коммуникации между потоками, чтобы не тормозить рендеринг.

Цели урока

• Идентифицировать critical section и понять зачем нужна mutual exclusion
• Применять mutex, semaphore (binary/counting), condition variable
• Реализовать producer-consumer с bounded buffer на mutex + cond vars
• Объяснить почему `i++` не atomic и зачем lock prefix / atomic ops
• Различать spinlock и block-wait mutex: когда какой выгоднее

Critical Section

**Критическая секция (Critical Section)** - это участок кода, который обращается к общему ресурсу (переменной, файлу, структуре данных) и не должен выполняться одновременно несколькими потоками. Если два потока одновременно модифицируют разделяемую переменную, возникает **race condition** - результат зависит от случайного порядка выполнения.

**Проблема:** `counter++` - это НЕ атомарная операция! Она компилируется в три инструкции: `LOAD`, `ADD`, `STORE`. Если поток A загрузил значение 100, но не успел сохранить 101, а поток B тоже загрузил 100 - оба сохранят 101, потеряв одно увеличение.

Dijkstra сформулировал **три требования** к решению проблемы критической секции: 1. **Mutual Exclusion** - только один поток в критической секции 2. **Progress** - если никто не в секции, решение о входе должно быть принято за конечное время 3. **Bounded Waiting** - поток не может ждать входа бесконечно долго (нет голодания)

**Наивное решение с флагами НЕ работает!** Пример Peterson's algorithm использует два флага и переменную `turn`, но даже он требует строгих гарантий от процессора (memory barriers). Современные системы используют аппаратные примитивы синхронизации.

Mutex

**Mutex (Mutual Exclusion)** - это примитив синхронизации, который гарантирует, что только один поток может владеть блокировкой в любой момент времени. Mutex имеет два состояния: **locked** (занят) и **unlocked** (свободен). Операции: `lock()` - захватить (если занят - ждать), `unlock()` - освободить.

**Важно:** Mutex должен освобождаться тем же потоком, который его захватил! Это отличает mutex от семафора. Также нельзя захватывать один mutex дважды в одном потоке (deadlock), если только он не **recursive mutex**.

**Типы mutex:** - **Normal mutex** - deadlock при повторном захвате - **Recursive mutex** - можно захватывать многократно (счётчик), нужно столько же раз освободить - **Error-checking mutex** - возвращает ошибку при неправильном использовании (для отладки) - **Adaptive mutex** - сначала spin-lock, потом блокировка (если ожидание короткое - не усыплять поток)

**Deadlock с mutex:** Поток A захватывает mutex1, потом пытается захватить mutex2. Поток B захватывает mutex2, потом пытается mutex1. Оба ждут друг друга вечно! **Решение:** всегда захватывать mutex в одном и том же порядке.

Semaphores

**Семафор (Semaphore)** - это обобщение mutex, которое хранит целое число (счётчик) и поддерживает две атомарные операции: - **wait() (P, down)** - уменьшить счётчик, если он > 0, иначе заблокироваться - **signal() (V, up)** - увеличить счётчик, разбудить один ждущий поток **Binary semaphore** (счётчик 0 или 1) эквивалентен mutex. **Counting semaphore** позволяет N потокам одновременно.

**Ключевое отличие от mutex:** семафор может быть освобождён любым потоком, не обязательно тем, кто его захватил. Это позволяет реализовывать схемы producer-consumer, где производитель увеличивает счётчик, а потребитель уменьшает.

**Применения counting semaphore:** - **Пул ресурсов** - N лицензий, N подключений к БД, N потоков в thread pool - **Сигнализация** - поток A делает `signal()`, поток B ждёт `wait()` (барьер синхронизации) - **Throttling** - ограничение скорости обработки (не более N запросов одновременно)

**Частая ошибка:** забыть вызвать `signal()` после `wait()` - это приведёт к утечке ресурса. Или вызвать `signal()` дважды - счётчик станет больше реального количества ресурсов, и система упадёт при обращении к несуществующему ресурсу.

Monitors

**Монитор (Monitor)** - это высокоуровневый примитив синхронизации, который объединяет данные, процедуры для работы с ними и неявную взаимоисключительность. Только один поток может выполнять код монитора в любой момент времени. Мониторы автоматически захватывают блокировку при входе в любой метод.

**Condition Variables (условные переменные)** - механизм ожидания внутри монитора. Когда поток не может продолжить (например, буфер пуст), он вызывает `wait()` на условной переменной, освобождает монитор и засыпает. Другой поток вызывает `signal()` - спящий поток просыпается и снова захватывает монитор.

**Важно:** `pthread_cond_wait()` атомарно освобождает mutex и усыпляет поток. При пробуждении автоматически захватывает mutex обратно. Это критично для избежания race condition между проверкой условия и ожиданием.

**Spurious wakeup** - ложное пробуждение. `pthread_cond_wait()` может вернуться, даже если никто не вызвал `signal()`! Поэтому проверка условия должна быть в цикле `while`, а не `if`. Иначе поток может продолжить работу при невыполненном условии.

**Readers-Writers Problem** - множество читателей могут работать одновременно (чтение безопасно), но писатель требует эксклюзивный доступ. Решение: счётчик читателей + mutex для записи. Проблема: писатели могут голодать, если всегда есть читатели. Решение: приоритет писателям (новые читатели не входят, если ждёт писатель).

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

• **Критическая секция** - участок кода, работающий с разделяемым ресурсом. Race condition возникает, когда несколько потоков выполняют критическую секцию без синхронизации. Решение должно удовлетворять условиям Dijkstra: mutual exclusion, progress, bounded waiting.
• **Mutex** - примитив для взаимоисключения (только один поток владеет блокировкой). Освобождается тем же потоком, что захватил. Реализован через атомарные инструкции (test-and-set, compare-and-swap) + блокировка потока через ОС. Deadlock возможен при неправильном порядке захвата нескольких mutex.
• **Semaphore** - обобщение mutex со счётчиком. Binary semaphore (0/1) ≈ mutex, counting semaphore (N) - для пула ресурсов. Операции wait()/signal() атомарны. Классическая задача: producer-consumer с ограниченным буфером (два семафора для заполненных/свободных слотов + mutex для защиты буфера).
• **Monitor** - высокоуровневая абстракция, объединяющая данные + методы + автоматическую блокировку. Condition variables позволяют ждать выполнения условия внутри монитора. pthread_cond_wait() атомарно освобождает mutex и усыпляет поток. Проверка условия в цикле while (spurious wakeups). Классические проблемы: dining philosophers, readers-writers.

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

Синхронизация - это основа многопоточного программирования. Она связана с множеством других тем в ОС и Computer Science:

• Процессы и потоки — Синхронизация нужна только при наличии параллельных потоков выполнения, которые делят общую память. Процессы изолированы, но могут синхронизироваться через IPC (shared memory + семафоры).
• Планирование — Mutex и семафоры блокируют потоки - планировщик переводит их в состояние WAITING и снимает с процессора. Приоритетная инверсия: низкоприоритетный поток держит блокировку, высокоприоритетный ждёт - решается priority inheritance.
• Deadlock — Неправильное использование синхронизации (захват нескольких ресурсов в разном порядке) приводит к deadlock. Условия возникновения: mutual exclusion, hold and wait, no preemption, circular wait.
• Memory Consistency — Современные процессоры переупорядочивают инструкции и кешируют данные. Простые флаги не работают без memory barriers. Mutex и семафоры гарантируют правильную видимость изменений между потоками (acquire-release семантика).

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

• Почему spin-lock (busy-waiting) иногда лучше, чем mutex с блокировкой? Подсказка: цена системного вызова и переключения контекста. Когда критическая секция очень короткая (несколько инструкций), выгоднее крутиться в цикле.
• Как реализовать read-write lock (множество читателей, один писатель) используя только mutex и condition variables? Подсказка: счётчик читателей + флаг "писатель внутри" + два условия (для читателей и для писателей).
• Почему в Java каждый объект имеет встроенный монитор (synchronized), а в C++ mutex - отдельный объект? Какой подход лучше и почему? Подсказка: цена памяти (каждый объект в Java тяжелее) и гибкость (в C++ можно выбрать тип блокировки).

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

• os-03-threads — Синхронизация нужна только при наличии нескольких потоков
• os-06-deadlocks — Дедлоки возникают именно при неправильной синхронизации
• os-17-locks-advanced — Продвинутые примитивы: spinlock, RCU, lockless структуры
• db-15-locks
• db-13-transactions