Synchronization

Consider a program that calculates `1 + 1 = 1`. Or a bank account that loses money during a transfer. It is a **race condition**. When multiple threads simultaneously modify data without synchronization, the result is unpredictable and depends on the random order of processor instruction execution. Synchronization is not just "locks for data," it's a fundamental problem of parallel computing, solved by the greatest minds in Computer Science: Dijkstra, Hoare, Lamport.

• **Databases:** transactions with isolation levels are implementations of semaphores and locks at the row and table level. MVCC (Multi-Version Concurrency Control) in PostgreSQL allows readers and writers not to block each other.
• **Web servers:** a thread pool processes requests in parallel, but the log file is one. Without a mutex for writing to the log - the file will be corrupted with interleaved lines from different threads. Nginx uses lock-free structures to minimize locks.
• **OS:** the process scheduler itself uses spin-lock and semaphores to synchronize its internal structures. Linux kernel: futex (fast userspace mutex) - a hybrid of spin-lock and system call to minimize context switches.
• **Games:** rendering in one thread, physics in another, AI in a third. All read object positions - synchronization is needed. Unreal Engine uses lock-free queues for communication between threads to avoid slowing down rendering.

Цели урока

• Identify a critical section and understand why mutual exclusion is required
• Apply mutex, semaphore (binary/counting), and condition variable correctly
• Implement producer-consumer over a bounded buffer with mutex + cond vars
• Explain why `i++` is not atomic and why the lock prefix / atomic ops exist
• Distinguish spinlock from block-wait mutex and know which one fits each workload

Critical Section

**Critical Section** is a portion of code that accesses a shared resource (variable, file, data structure) and should not be executed by more than one thread at a time. If two threads simultaneously modify a shared variable, a **race condition** occurs - the result depends on the random order of execution.

**Problem:** `counter++` is NOT an atomic operation! It compiles into three instructions: `LOAD`, `ADD`, `STORE`. If thread A loads the value 100 but doesn't save 101 in time, and thread B also loads 100 - both will save 101, losing one increment.

Dijkstra formulated **three requirements** for solving the critical section problem: 1. **Mutual Exclusion** - only one thread in the critical section 2. **Progress** - if no one is in the section, the decision to enter must be made in finite time 3. **Bounded Waiting** - a thread cannot wait indefinitely to enter (no starvation)

**Naive flag solution DOES NOT work!** Example: Peterson's algorithm uses two flags and a `turn` variable, but even it requires strict guarantees from the processor (memory barriers). Modern systems use hardware synchronization primitives.

Mutex

**Mutex (Mutual Exclusion)** is a synchronization primitive that ensures only one thread can own the lock at any given time. A mutex has two states: **locked** and **unlocked**. Operations: `lock()` - acquire (if locked - wait), `unlock()` - release.

**Important:** A mutex must be released by the same thread that acquired it! This distinguishes a mutex from a semaphore. Also, the same mutex cannot be acquired twice in one thread (deadlock), unless it is a **recursive mutex**.

**Types of mutex:** - **Normal mutex** - deadlock on repeated acquisition - **Recursive mutex** - can be acquired multiple times (counter), must be released the same number of times - **Error-checking mutex** - returns an error on incorrect use (for debugging) - **Adaptive mutex** - first spin-lock, then block (if waiting is short - do not put the thread to sleep)

**Deadlock with mutex:** Thread A acquires mutex1, then tries to acquire mutex2. Thread B acquires mutex2, then tries mutex1. Both wait for each other forever! **Solution:** always acquire mutexes in the same order.

Semaphores

**Semaphore** is a generalization of a mutex that holds an integer (counter) and supports two atomic operations: - **wait() (P, down)** - decrease the counter if it is > 0, otherwise block - **signal() (V, up)** - increase the counter, wake one waiting thread **Binary semaphore** (counter 0 or 1) is equivalent to a mutex. **Counting semaphore** allows N threads simultaneously.

**Key difference from a mutex:** a semaphore can be released by any thread, not necessarily the one that acquired it. This allows implementing producer-consumer schemes, where the producer increases the counter, and the consumer decreases it.

**Applications of counting semaphore:** - **Resource pool** - N licenses, N database connections, N threads in a thread pool - **Signaling** - thread A does `signal()`, thread B waits `wait()` (synchronization barrier) - **Throttling** - rate limiting (no more than N requests simultaneously)

**Common mistake:** forgetting to call `signal()` after `wait()` - this will lead to resource leakage. Or calling `signal()` twice - the counter will exceed the actual number of resources, and the system will crash when accessing a non-existent resource.

Monitors

**Monitor** is a high-level synchronization primitive that combines data, procedures for working with them, and implicit mutual exclusion. Only one thread can execute monitor code at any given time. Monitors automatically acquire a lock when entering any method.

**Condition Variables** - a mechanism for waiting inside a monitor. When a thread cannot continue (e.g., buffer is empty), it calls `wait()` on a condition variable, releases the monitor, and sleeps. Another thread calls `signal()` - the sleeping thread wakes up and re-acquires the monitor.

**Important:** `pthread_cond_wait()` atomically releases the mutex and puts the thread to sleep. Upon waking, it automatically re-acquires the mutex. This is critical to avoid race conditions between checking the condition and waiting.

**Spurious wakeup** - false wakeup. `pthread_cond_wait()` can return even if no one called `signal()`! Therefore, the condition check must be in a `while` loop, not `if`. Otherwise, the thread may continue working with an unmet condition.

**Readers-Writers Problem** - multiple readers can work simultaneously (reading is safe), but a writer requires exclusive access. Solution: reader counter + mutex for writing. Problem: writers may starve if there are always readers. Solution: prioritize writers (new readers do not enter if a writer is waiting).

Key Ideas

• **Critical Section** - a portion of code working with a shared resource. A race condition occurs when multiple threads execute a critical section without synchronization. The solution must satisfy Dijkstra's conditions: mutual exclusion, progress, bounded waiting.
• **Mutex** - a primitive for mutual exclusion (only one thread owns the lock). Released by the same thread that acquired it. Implemented through atomic instructions (test-and-set, compare-and-swap) + blocking the thread via the OS. Deadlock is possible with incorrect order of acquiring multiple mutexes.
• **Semaphore** - a generalization of a mutex with a counter. Binary semaphore (0/1) ≈ mutex, counting semaphore (N) - for a resource pool. Operations wait()/signal() are atomic. Classic problem: producer-consumer with a bounded buffer (two semaphores for filled/free slots + mutex for buffer protection).
• **Monitor** - a high-level abstraction combining data + methods + automatic locking. Condition variables allow waiting for a condition inside a monitor. pthread_cond_wait() atomically releases the mutex and puts the thread to sleep. Condition check in a while loop (spurious wakeups). Classic problems: dining philosophers, readers-writers.

Related Topics

Synchronization is the foundation of multithreaded programming. It is related to many other topics in OS and Computer Science:

• Processes and Threads — Synchronization is only needed when there are parallel threads of execution sharing memory. Processes are isolated but can synchronize through IPC (shared memory + semaphores).
• Scheduling — Mutexes and semaphores block threads - the scheduler moves them to the WAITING state and removes them from the processor. Priority inversion: a low-priority thread holds a lock, a high-priority thread waits - solved by priority inheritance.
• Deadlock — Incorrect use of synchronization (acquiring multiple resources in different orders) leads to deadlock. Conditions for occurrence: mutual exclusion, hold and wait, no preemption, circular wait.
• Memory Consistency — Modern processors reorder instructions and cache data. Simple flags do not work without memory barriers. Mutexes and semaphores ensure correct visibility of changes between threads (acquire-release semantics).

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

• Why is a spin-lock (busy-waiting) sometimes better than a mutex with blocking? Consider the cost of a system call and context switching. When the critical section is very short (a few instructions), spinning in a loop is more efficient.
• How to implement a read-write lock (multiple readers, one writer) using only mutex and condition variables? Hint: reader counter + "writer inside" flag + two conditions (for readers and writers).
• Why does Java have a built-in monitor (synchronized) for every object, while in C++ a mutex is a separate object? Which approach is better and why? Consider memory cost (every object in Java is heavier) and flexibility (in C++ the type of lock can be chosen).

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

• os-03-threads — Synchronization is only needed when multiple threads are present
• os-06-deadlocks — Deadlocks arise precisely from incorrect synchronization
• os-17-locks-advanced — Advanced primitives: spinlock, RCU, lock-free structures
• db-15-locks
• db-13-transactions