Key Synchronization Primitives

Why This Matters

Synchronization primitives are the foundation of concurrent programming and operating systems design. When you're tested on OS concepts, you're not just being asked to define a mutex or semaphore. You're being evaluated on whether you understand why different primitives exist, when to use each one, and what trade-offs they involve. These concepts connect directly to bigger themes like process coordination, resource management, deadlock prevention, and system performance optimization.

The primitives covered here demonstrate core principles: mutual exclusion, signaling and waiting, busy-waiting vs. blocking, and lock-free programming. Each primitive solves a specific synchronization problem, and exam questions often ask you to identify which tool fits which scenario. Don't just memorize definitions. Know what problem each primitive solves and when you'd choose one over another.

---

Mutual Exclusion Primitives

These primitives enforce the fundamental rule that only one thread can access a critical resource at a time. The core mechanism is acquiring exclusive ownership before entering a critical section and releasing it upon exit.

Mutex (Mutual Exclusion)

• Provides exclusive access to a shared resource. Only the thread holding the mutex can enter the critical section.
• Ownership semantics mean the same thread that acquires the mutex must release it, unlike semaphores. This distinction matters for correctness and is a common exam question.
• Blocking behavior: if the mutex is already held, a requesting thread is put to sleep (descheduled) and woken up when the mutex becomes available. This avoids wasting CPU cycles but incurs context-switch overhead.
• Deadlock risk exists when multiple mutexes are acquired in inconsistent orders. For example, if Thread A holds Mutex 1 and waits for Mutex 2, while Thread B holds Mutex 2 and waits for Mutex 1, neither can proceed. Establishing a global lock ordering prevents this circular wait.

Spinlocks

• Busy-waiting mechanism where a thread continuously polls the lock in a tight loop until it becomes available. The thread never yields the CPU.
• Low overhead for short waits because it avoids context-switch costs. If the critical section executes in microseconds or less, spinning is cheaper than sleeping and waking.
• Wastes CPU cycles during contention, making spinlocks unsuitable for locks held across I/O operations or long computations. On a single-processor system, spinlocks are almost always a bad idea because the thread holding the lock can't make progress while the spinning thread occupies the CPU.

Critical Sections

• A critical section is a code region accessing shared data that must execute atomically with respect to other threads. It's not a primitive itself but rather what primitives protect.
• Minimizing critical section length directly improves concurrency by reducing the time locks are held. A common mistake is putting I/O or expensive computation inside a critical section when only the actual shared-data access needs protection.

---

Signaling and Waiting Primitives

These primitives allow threads to communicate about state changes and coordinate their execution. The key mechanism is enabling threads to sleep efficiently until a condition becomes true, rather than wasting cycles polling.

Semaphores

• Counting mechanism that maintains an integer value representing available resource units or permits. The two fundamental operations are wait() (also called P() or down()), which decrements the count and blocks if it would go negative, and signal() (also called V() or up()), which increments the count and wakes a blocked thread if one exists.
• Binary semaphores (values 0 or 1) function similarly to mutexes. Counting semaphores allow up to $n$ threads to access a resource pool simultaneously, such as limiting concurrent database connections to 10.
• No ownership requirement: any thread can signal a semaphore, not just the one that waited on it. This is what makes semaphores suitable for producer-consumer patterns, where one thread produces work and a different thread signals availability.

Condition Variables

• Wait-and-signal mechanism used together with a mutex to let threads sleep until a specific condition becomes true. You can't use a condition variable without an associated mutex.
• Three core operations:
  1. wait(mutex): atomically releases the mutex and blocks the calling thread. When the thread is woken, it reacquires the mutex before returning.
  2. signal(): wakes one waiting thread (if any).
  3. broadcast(): wakes all waiting threads.
• Always check the condition in a while loop, not an if statement. A thread can be woken spuriously or another thread might change the condition between the signal and the woken thread reacquiring the mutex. This is one of the most common bugs in concurrent code.
• Essential for producer-consumer and bounded-buffer problems where threads must wait for data availability or buffer space.

Monitors

• High-level abstraction combining mutual exclusion with condition variables in a single construct. Languages like Java (with synchronized methods) and Python (with threading.Condition) provide monitor-style synchronization.
• Automatic lock management: entering a monitor procedure implicitly acquires the lock; exiting releases it. This eliminates a whole class of bugs where programmers forget to release locks.
• Encapsulates synchronization logic within the data structure itself, reducing programmer error compared to manual mutex/condition variable pairing.

---

Coordination Primitives

These primitives synchronize groups of threads at specific execution points. The mechanism involves blocking threads until all participants reach a synchronization point or complete their phase.

Barriers

• Synchronization checkpoint where all participating threads must arrive before any can proceed past the barrier. If 8 threads are involved, the first 7 to arrive block until the 8th arrives, then all 8 continue.
• Phase-based parallelism relies on barriers. Threads complete phase $k$, synchronize at the barrier, then begin phase $k+1$ together. This is common in scientific simulations where each time step depends on the previous step's complete results.
• Reusable barriers reset automatically after all threads pass, enabling iterative algorithms with multiple synchronization rounds.

---

Read-Write Optimization Primitives

These primitives improve concurrency for workloads where reads vastly outnumber writes. The mechanism allows shared access for readers while maintaining exclusive access for writers.

Read-Write Locks

• Multiple concurrent readers can hold the lock simultaneously since read operations don't modify shared state. This is safe because concurrent reads can't produce inconsistencies.
• Exclusive writer access blocks all readers and other writers, ensuring data consistency during modifications.
• Writer starvation risk occurs when continuous reader arrivals indefinitely postpone waiting writers. Many implementations use fairness policies (e.g., once a writer is waiting, no new readers are admitted) to prevent this.
• The overhead of tracking reader counts means read-write locks only pay off when the read-to-write ratio is high. For balanced workloads, a plain mutex is simpler and often faster.

---

Lock-Free Primitives

These primitives provide synchronization without traditional blocking locks. The mechanism relies on hardware-supported instructions that complete atomically, enabling progress guarantees even when threads are delayed.

Atomic Operations

• Hardware-guaranteed indivisibility: operations like compare-and-swap (CAS) and fetch-and-add execute as single, uninterruptible steps at the hardware level.
• Compare-and-swap is the workhorse: compare_and_swap(addr, expected, new) checks if the value at addr equals expected. If yes, it atomically replaces it with new and returns success. If no, it fails and the caller typically retries in a loop. This retry loop is the basic pattern behind most lock-free data structures.
• Other common operations include fetch_and_add(addr, value) and test_and_set(addr).
• Lock-free algorithms built on these operations guarantee system-wide progress: at least one thread always makes forward progress regardless of what other threads are doing. This is stronger than what lock-based approaches can guarantee, since a thread holding a lock could be descheduled indefinitely.

Locks (General Concept)

• Abstract mechanism for enforcing mutual exclusion. Mutexes, spinlocks, and read-write locks are all specific lock implementations.
• Acquisition and release define the protocol: acquire before entering the critical section, release after exiting.
• Correctness hazards include:
  • Deadlock: circular waiting where threads block each other permanently.
  • Livelock: threads actively change state in response to each other but none makes real progress (like two people stepping side to side in a hallway).
  • Priority inversion: a high-priority thread is blocked waiting for a lock held by a low-priority thread, which itself can't run because a medium-priority thread is using the CPU. Priority inheritance protocols address this.

---

Quick Reference Table

---

Self-Check Questions

1. Which two primitives both enforce mutual exclusion but differ in how they handle waiting? When would you choose each one?

2. A producer-consumer problem requires threads to wait until a buffer has space (producer) or data (consumer). Which primitive combination would you use, and why wouldn't a simple mutex suffice?

3. Compare semaphores and condition variables: what happens if you signal each one when no thread is currently waiting?

4. Your system has a shared configuration object read by 50 threads per second but updated only once per minute. Which synchronization primitive optimizes this workload, and what risk must you mitigate?

5. FRQ-style: Explain why atomic operations like compare-and-swap enable lock-free data structures. Describe one advantage and one disadvantage compared to mutex-based synchronization.