5 Concurrency and Synchronization

Concurrency and critical sections

Concurrency occurs when multiple threads or processes make progress during overlapping periods. On a multicore system, they may run at the same time; on a single-core system, the operating system can interleave their execution. In either case, the order of operations may vary from run to run.

When concurrent threads access shared data, an operation that looks indivisible in source code may consist of several machine instructions. If two threads increment the same counter, both may read its old value before either writes the new one, so one increment is lost. This is a race condition: the result depends on the timing or order of execution.

A critical section is a portion of code that accesses shared data or a resource that must not be used concurrently. For a shared counter, it includes both reading the value and writing the incremented value. Synchronization protects critical sections and helps coordinate when threads may proceed.

A sound critical-section solution aims for three properties:

• Mutual exclusion: At most one thread at a time executes the protected section for a given resource. This prevents a race on protected data.

• Progress: If no thread is in the section and some want to enter, choosing the next entrant should not be postponed indefinitely.

• Bounded waiting: A thread requesting entry should not be bypassed forever by other threads.

Progress and bounded waiting address whether threads can make progress and avoid indefinite unfairness.

Synchronization primitives

Operating systems and thread libraries provide synchronization mechanisms. Choose a mechanism that matches the coordination needed, and keep protected sections short.

• Mutex (lock): Grants exclusive access. A thread locks it before accessing shared state and unlocks it afterward. A mutex can protect a data structure or a group of related operations.

• Semaphore: Holds a count accessed through atomic operations. A binary semaphore can be used for mutual exclusion; a counting semaphore can represent several identical available resources. For example, a semaphore initialized to 4 can limit access to a pool of four connections.

• Condition variable: Lets a thread sleep until a condition involving shared state may have changed. It is used with a mutex. The waiter checks a predicate while holding the lock, waits while releasing the lock, then checks the predicate again after waking. A wake-up is not proof that the condition is true, so use a loop to recheck it. POSIX condition-variable waits atomically release the associated mutex while waiting and reacquire it before returning.

• Read-write lock: Allows multiple readers at once, but excludes readers when a writer holds the lock. It can help when reads are frequent and writes are relatively uncommon; fairness and performance depend on the implementation.

• Barrier: Makes a group of threads wait until all have reached the same stage, which is useful in computations split into synchronized phases.

A lock protects access; a condition variable coordinates waiting for a state change. For example, a consumer should wait until a shared queue is nonempty, not merely until another thread signals it. The predicate, such as “queue is nonempty,” is the actual condition to test.

Deadlock and other progress problems

A deadlock occurs when a set of threads are permanently blocked because each is waiting for a resource or action that another blocked thread must provide. The four conditions for the classic resource deadlock must all hold:

1. Mutual exclusion: At least one resource is usable by only one thread at a time.

2. Hold and wait: A thread holds a resource while waiting for another.

3. No preemption: A resource cannot simply be taken away; its holder must release it.

4. Circular wait: There is a cycle of threads, each waiting for a resource held by the next.

For example, thread A may hold lock X and wait for Y, while thread B holds Y and waits for X. Each holds the lock the other needs, so neither can proceed.

Common approaches to handling deadlock include:

• Prevention: Design the system so at least one necessary condition cannot occur. Acquiring multiple locks in a single global order is a common technique that prevents circular wait.

• Avoidance: Grant a resource request only when the resulting allocation is known to remain in a safe state. This requires enough information about future resource needs.

• Detection and recovery: Allow deadlocks, detect them, then recover—for example, by terminating a process or reclaiming resources where safe.

Not every failure to make progress is a deadlock. Starvation means a thread waits indefinitely because others repeatedly get priority or access first. Livelock means threads keep responding to one another but make no useful progress. Fair queues, careful scheduling, and bounded retries can help address these problems.

Common coordination problems

Producer–consumer with a bounded buffer

Producers add items to a shared buffer, and consumers remove them. The buffer must not be accessed unsafely; producers must wait when it is full, and consumers must wait when it is empty. A mutex can protect the queue, while condition variables notify waiting threads when items are added or space becomes available. This pattern illustrates the distinction between protecting shared state and coordinating around a condition.

Readers–writers

Many readers may be able to examine shared data simultaneously, while a writer generally needs exclusive access to update it. A readers–writers lock supports this pattern, but its policy matters: favoring readers may starve writers, while favoring writers may delay readers.

Dining philosophers

Imagine philosophers around a table, each needing the two forks beside them to eat. If every philosopher picks up one fork and waits for the other, all can become deadlocked. One remedy is to require forks to be acquired in a consistent global order; another is to use a coordinator that grants both forks together. A solution should consider not only deadlock, but also starvation and how much independent work it allows.

Practical synchronization principles

Protect shared data consistently, and define which lock guards each piece of state. Acquire multiple locks in a consistent order, release them promptly, and avoid waiting for unrelated work while holding a lock.

Use condition variables to wait on predicates rather than polling repeatedly. Test concurrent programs under varied timing, because synchronization bugs may appear only under particular interleavings.