Key Synchronization Primitives

Why This Matters

Synchronization primitives are the foundation of everything you'll encounter in 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
• Deadlock risk exists when multiple mutexes are acquired in inconsistent orders, requiring careful design to prevent circular wait conditions

Spinlocks

• Busy-waiting mechanism where a thread continuously polls the lock in a tight loop until it becomes available
• Low overhead for short waits—avoids context switch costs when critical sections execute in microseconds or less
• Wastes CPU cycles during contention, making spinlocks unsuitable for locks held across I/O operations or long computations

Critical Sections

• Code regions accessing shared data that must execute atomically with respect to other threads
• Protected by synchronization primitives—the critical section itself isn't a primitive but rather what primitives protect
• Minimizing critical section length directly improves concurrency by reducing the time locks are held

---

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
• Binary semaphores (values 0 or 1) function similarly to mutexes; counting semaphores allow $n$ threads to access a resource pool simultaneously
• No ownership requirement—any thread can signal (increment) a semaphore, enabling producer-consumer patterns

Condition Variables

• Wait-and-signal mechanism used with a mutex to let threads sleep until a specific condition becomes true
• Three core operations: wait() releases the mutex and blocks; signal() wakes one waiting thread; broadcast() wakes all waiting threads
• 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
• Automatic lock management—entering a monitor procedure implicitly acquires the lock; exiting releases it
• 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
• Phase-based parallelism relies on barriers—threads complete phase $k$, synchronize at the barrier, then begin phase $k+1$ together
• 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
• 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 to prevent this

---

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
• Foundation for lock-free algorithms that guarantee system-wide progress; at least one thread always makes progress regardless of other threads' states
• Common operations include compare_and_swap(addr, expected, new), fetch_and_add(addr, value), and test_and_set(addr)

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 critical section, release after exiting
• Correctness hazards include deadlock (circular waiting), livelock (threads actively prevent each other's progress), and priority inversion (high-priority thread blocked by low-priority lock holder)

---

Quick Reference Table

---

Self-Check Questions

1. Which two primitives both enforce mutual exclusion but differ in how they handle waiting—and 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 and contrast 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, and describe one advantage and one disadvantage compared to mutex-based synchronization.