Synchronization

When multiple threads/processes access shared resources concurrently, synchronization prevents data corruption and ensures correctness.

The Critical Section Problem

A critical section is a code segment that accesses shared resources and must not be executed by more than one thread simultaneously.

Requirements

Mutual exclusion: At most one thread in the critical section at any time.
Progress: If no thread is in the critical section and some threads want to enter, the decision can't be postponed indefinitely.
Bounded waiting: A thread's wait to enter the critical section is bounded (no starvation).

entry_section();
    // CRITICAL SECTION — access shared resource
exit_section();
    // REMAINDER SECTION

Peterson's Solution

A software solution for two threads (historical importance — proves the problem is solvable without hardware support).

// Peterson's Solution (simplified — needs atomic operations in practice)
SHARED flag[0..1] ← [false, false]
SHARED turn ← 0

PROCEDURE ENTER_CRITICAL(id)
    other ← 1 - id
    flag[id] ← true
    turn ← other
    WHILE flag[other] AND turn = other
        // busy wait

PROCEDURE EXIT_CRITICAL(id)
    flag[id] ← false

Satisfies all three properties for two threads. Doesn't generalize well to n threads. Not used in practice (hardware instructions are faster and simpler).

Hardware Support

Test-and-Set (TAS)

Atomically read a value and set it to true. Returns the old value.

// Hardware atomic instruction (conceptual)
FUNCTION TEST_AND_SET(lock)
    old_value ← lock
    lock ← true
    RETURN old_value   // atomic: read + set happen indivisibly

// Spinlock using TAS
PROCEDURE ACQUIRE(lock)
    WHILE TEST_AND_SET(lock) = true
        // spin until we get false (lock was free)

PROCEDURE RELEASE(lock)
    lock ← false

Compare-and-Swap (CAS)

Atomically: if current value equals expected, set to new value. Returns success/failure.

PROCEDURE ACQUIRE(lock)
    WHILE COMPARE_AND_SWAP(lock, expected: false, new: true) fails
        // spin

CAS is the foundation of lock-free data structures.

Fetch-and-Add

Atomically add to a value and return the old value. Used for counters, ticket locks.

Ticket Lock

Fair spinlock — threads take a "ticket" (fetch-and-add) and wait until their ticket is called.

CLASS TicketLock
    FIELDS: ticket ← 0, serving ← 0

    PROCEDURE ACQUIRE()
        my_ticket ← FETCH_AND_ADD(self.ticket, 1)
        WHILE self.serving ≠ my_ticket
            SPIN_WAIT()

    PROCEDURE RELEASE()
        FETCH_AND_ADD(self.serving, 1)

FIFO ordering — no starvation. But all waiters spin on the same cache line (scalability issue).

Mutex Locks

A mutex (mutual exclusion) lock allows only one thread to hold it at a time.

data ← MUTEX(value: [1, 2, 3])

// Thread 1
BEGIN
    guard ← LOCK(data)
    APPEND 4 TO guard
END   // lock automatically released when guard goes out of scope (RAII)

Spinlock vs Blocking Mutex

Spinlock: Thread loops (spins) checking the lock. Wastes CPU but no context switch. Best when critical section is very short and CPUs are available.

Blocking mutex: Thread is put to sleep (blocked) until the lock is available. OS scheduler runs another thread. Best when critical sections are longer or CPU is scarce.

Adaptive mutex: Spin briefly, then block. Linux futex (fast userspace mutex) uses this.

Semaphores

A semaphore is a counter with two atomic operations:

wait() (P / acquire / down): Decrement. If counter < 0, block.
signal() (V / release / up): Increment. If counter ≤ 0, wake a waiting thread.

Binary Semaphore

Counter is 0 or 1. Equivalent to a mutex. Used for mutual exclusion.

Counting Semaphore

Counter can be any non-negative integer. Controls access to a resource with N instances.

// Counting semaphore: limit to 5 concurrent database connections
sem ← SEMAPHORE(5)

ASYNC PROCEDURE QUERY_DB(sem)
    permit ← ACQUIRE(sem)   // blocks if 5 already acquired
    // ... use database connection ...
    RELEASE(permit)          // semaphore incremented

Classic Problems

Producer-Consumer (Bounded Buffer):

Semaphore empty = N;   // N empty slots
Semaphore full = 0;    // 0 full slots
Semaphore mutex = 1;   // mutual exclusion

Producer:                Consumer:
  wait(empty);            wait(full);
  wait(mutex);            wait(mutex);
  add item to buffer      remove item from buffer
  signal(mutex);          signal(mutex);
  signal(full);           signal(empty);

Readers-Writers:

Multiple readers can read simultaneously.
Writers need exclusive access (no readers or other writers).
First readers-writers problem: readers preferred. Second: writers preferred. Third: fair.

Dining Philosophers: 5 philosophers, 5 forks. Each needs 2 adjacent forks to eat. Classic deadlock/starvation example.

Monitors

A monitor is a high-level synchronization construct combining:

Mutual exclusion: Only one thread can execute a monitor procedure at a time.
Condition variables: Allow threads to wait for and signal conditions.

Condition Variables

SHARED queue ← empty deque, protected by mutex
SHARED cvar ← CONDITION_VARIABLE

// Producer
LOCK(queue)
    PUSH_BACK(queue, item)
    NOTIFY_ONE(cvar)          // wake one consumer
UNLOCK(queue)

// Consumer
LOCK(queue)
    WHILE queue is empty
        WAIT(cvar, queue)     // atomically: release lock + sleep. Re-acquires on wake.
    item ← POP_FRONT(queue)
UNLOCK(queue)

wait(condvar, lock): Atomically releases the lock and blocks. When woken, reacquires the lock.

notify_one() / notify_all(): Wake one / all waiting threads.

Spurious wakeups: Threads can wake without being signaled. Always use while (not if) to re-check the condition.

Reader-Writer Locks

Allow concurrent reads but exclusive writes.

data ← RWLOCK(value: [1, 2, 3])

// Multiple readers simultaneously
r1 ← READ_LOCK(data)
r2 ← READ_LOCK(data)          // OK — shared access

// Exclusive writer
RELEASE(r1); RELEASE(r2)
w ← WRITE_LOCK(data)          // blocks until all readers finish
APPEND 4 TO w

Variants: Reader-preferred (may starve writers), writer-preferred (may starve readers), fair (alternate).

Barriers

A barrier synchronizes a group of threads — all must reach the barrier before any can proceed.

barrier ← BARRIER(count: 4)

FOR i ← 0 TO 3
    SPAWN_THREAD(PROCEDURE()
        // Phase 1 work
        WAIT(barrier)        // wait for all 4 threads
        // Phase 2 work (all threads proceed together)
    )

Used in parallel algorithms (e.g., parallel matrix multiply — sync between phases).

// Acquire: No reads/writes after this can be reordered before it
ATOMIC_LOAD(data, ordering: Acquire)

// Release: No reads/writes before this can be reordered after it
ATOMIC_STORE(data, value, ordering: Release)

// SeqCst: Full sequential consistency (strongest, slowest)
ATOMIC_STORE(data, value, ordering: SeqCst)

Covered in depth in parallel computing topic (memory models).

Applications in CS

Databases: Row-level locks, MVCC, two-phase locking — all synchronization at the transaction level.
Operating systems: Kernel synchronization (spinlocks for short critical sections, semaphores/mutexes for longer ones).
Web servers: Connection pool semaphores. Request queue with producer-consumer.
File systems: Inode locks, buffer cache synchronization.
Concurrent data structures: Concurrent hash maps, queues, skip lists — all use fine-grained synchronization.
Real-time systems: Priority inheritance protocols prevent unbounded priority inversion.