5. Concurrency and Synchronization

Introduction and Context

Operating systems rarely execute one activity in isolation. A modern system may run several processes and hundreds of threads while interrupt handlers, device drivers, kernel services, and user applications interact with shared resources. Concurrency improves responsiveness, throughput, and resource utilization, but it also creates a fundamental problem: the correctness of a computation may depend on the order in which operations occur.

If two threads update the same counter simultaneously, one update may overwrite the other. If a process reads a data structure while another modifies it, the reader may observe an inconsistent state. More serious failures arise when threads wait indefinitely for resources held by one another. These problems are not solved merely by having multiple processors; they require a disciplined theory of mutual exclusion, ordering, visibility, and progress.

This chapter develops that theory. It begins with the critical-section problem and proceeds through atomic instructions, locks, semaphores, monitors, condition variables, barriers, lock-free algorithms, and memory-consistency models. The emphasis is not only on how synchronization mechanisms work, but also on selecting, composing, verifying, and evaluating them in real systems.

Learning Objectives

After studying this chapter, the learner should be able to:

1. Distinguish concurrency from parallelism and explain the sources of race conditions.

2. State and evaluate the correctness requirements of a critical-section solution.

3. Explain how hardware atomic instructions support operating-system synchronization.

4. Select and use mutexes, spinlocks, semaphores, monitors, condition variables, and barriers appropriately.

5. Analyze deadlock, starvation, livelock, priority inversion, and performance costs.

6. Explain lock-free techniques and the role of compare-and-swap.

7. Relate synchronization correctness to memory-consistency and happens-before models.

8. Design and critique concurrent solutions for operating-system and industry scenarios.

Concurrency, Shared State, and the Critical Section

Concurrency is the logical coexistence of multiple activities whose executions overlap in time. Parallelism is the physical execution of activities at the same time on different processing units. A single-core system can be concurrent through interleaving, whereas a multicore system can be both concurrent and parallel. Synchronization is required in both cases because an interleaving that is harmless on one execution may be harmful on another.

A race condition occurs when the result depends on the relative timing of concurrent operations. Consider the apparently simple operation `counter = counter + 1`. It normally consists of reading `counter`, adding one, and writing the result. If two threads read the value 7 before either writes, both may write 8, although the intended result is 9. The statement is therefore not atomic merely because it is written as one line of source code.

A critical section is a part of a program that accesses shared data or a shared resource and must not be executed concurrently with conflicting critical sections. A complete concurrent program is often represented as:

• an entry section, in which a thread requests permission to enter;
• the critical section itself;
• an exit section, in which the permission is released; and
• a remainder section, containing unrelated work.

A correct solution to the critical-section problem traditionally satisfies three properties. Mutual exclusion means that at most one process or thread executes a protected critical section at a time. Progress means that if no thread is in the critical section and some threads wish to enter, the choice of the next entrant cannot be postponed indefinitely by threads that are not trying to enter. Bounded waiting means that a thread requesting entry has a finite bound on how many other entries may occur before its request is served. Mutual exclusion prevents simultaneous conflicting access; progress and bounded waiting address indefinite postponement.

These properties are distinct. A system can provide mutual exclusion but fail progress, for example if all participants wait forever. It can provide progress but permit starvation, violating bounded waiting. Correctness therefore includes both safety and liveness. Safety states that something bad never happens, such as two owners entering a protected region. Liveness states that something good eventually happens, such as a waiting thread eventually acquiring a resource.

Hardware Support for Atomicity

Software alone cannot safely implement synchronization if the underlying machine permits concurrent conflicting reads and writes without atomic support. Modern processors provide indivisible read-modify-write instructions. Typical examples include test-and-set, exchange, fetch-and-add, and compare-and-swap (CAS).

A test-and-set instruction atomically reads a lock value and sets it. A thread can repeatedly test the old value until it observes that the lock was free. An exchange instruction atomically swaps a register value with a memory value. CAS compares a memory location with an expected value and replaces it with a new value only if the comparison succeeds:

`CAS(address, expected, new)`

CAS is especially powerful because it permits a thread to express an optimistic update. If another thread has changed the location since it was read, CAS fails and the operation can be retried using the new value. This principle supports both locks and non-blocking data structures.

Atomicity alone does not solve every synchronization problem. An atomic instruction must be combined with appropriate visibility and ordering guarantees. A processor or compiler may reorder independent memory operations unless the programming language or hardware memory model prevents that reordering. Thus, a lock implementation must ensure not only that ownership changes atomically, but also that writes performed by the previous owner become visible to the next owner.

Locks and Their Trade-offs

A mutex, or mutual-exclusion lock, has an ownership discipline: one thread acquires it and later releases it. The protected invariant is established before release and is assumed by the next owner after acquisition. Mutexes are appropriate for ordinary critical sections that may involve blocking or relatively lengthy computation.

A spinlock repeatedly tests a lock until it becomes available. Spinning avoids the overhead of putting a thread to sleep and later waking it, so it can be effective when the critical section is extremely short and the owner is expected to run immediately. On a single processor, however, spinning can be disastrous if the lock holder is not scheduled while the waiter consumes the processor. Spinlocks are commonly used in kernels for short regions where sleeping is impossible, such as certain interrupt or low-level scheduler contexts.

Lock implementations may be simple test-and-set locks, ticket locks, queue locks, or hybrid adaptive locks. A ticket lock gives each arriving thread a ticket and serves tickets in order, improving fairness. Queue locks reduce contention on one shared cache location by arranging waiters in a queue. Adaptive locks may spin briefly and then block if the owner does not release the lock quickly.

Lock granularity affects both correctness and performance. A coarse-grained lock simplifies reasoning but may serialize unrelated work. Fine-grained locking increases concurrency but introduces more lock-ordering obligations and greater risk of deadlock. A sound design protects an explicitly stated invariant rather than placing locks around arbitrary lines of code.

Semaphores: Counting Access and Signalling Events

A semaphore is an integer-based synchronization abstraction accessed only through atomic operations traditionally called `wait` and `signal`, or `P` and `V`. A counting semaphore represents a number of available instances of a resource. `wait` decreases the count when a unit is available; otherwise the caller blocks. `signal` increases the count and may awaken a waiting thread.

A binary semaphore has values associated with unavailable and available states and can sometimes be used for mutual exclusion. Nevertheless, a mutex is usually preferable for ownership-based protection because it documents intent and can enforce that the releasing thread is the owner. Semaphores are especially useful when one thread must signal that an event occurred or when a fixed number of identical resources is available.

The bounded-buffer problem illustrates a standard semaphore design. Let `empty` count unused buffer slots, `full` count occupied slots, and `mutex` protect the buffer structure. A producer waits on `empty`, then acquires `mutex`, inserts an item, releases `mutex`, and signals `full`. A consumer waits on `full`, acquires `mutex`, removes an item, releases `mutex`, and signals `empty`. The order matters: acquiring the mutex before waiting for a slot can create deadlock if all participants hold the mutex while waiting for a condition that another participant needs the mutex to establish.

Semaphores are expressive but error-prone. Missing a `signal` can cause permanent blocking; signalling the wrong semaphore can violate an invariant; and inconsistent acquisition order can produce deadlock. Their use should therefore be accompanied by a statement of the resource invariant and a proof of each possible blocking path.

Monitors and Condition Variables

A monitor combines shared data, procedures that operate on that data, and implicit mutual exclusion. At most one thread executes a monitor procedure at a time. This encapsulation places synchronization close to the invariant and reduces accidental access to unprotected state.

A condition variable allows a thread inside a monitor to sleep until a logical condition becomes true. The operations are generally `wait`, `signal`, and sometimes `broadcast`. Calling `wait` atomically releases the monitor lock and blocks the caller; when awakened, the caller reacquires the lock before continuing. `signal` wakes one eligible waiter, whereas `broadcast` wakes all waiters.

Condition variables do not store a condition by themselves. The condition is represented by shared state, such as `buffer_not_empty`. The correct pattern is therefore:

`while (!condition) wait(condition_variable);`

The loop is essential. A wake-up does not guarantee that the condition is still true when the thread reacquires the lock. Another thread may have consumed the resource first, or the wake-up may be spurious. The thread must recheck the predicate while holding the associated lock. Using `if` instead of `while` is a common and serious error.

Monitors and condition variables support a clear separation between a predicate and the mechanism used to wait for it. The predicate should be stated positively and precisely: for example, “the queue contains at least one item,” not merely “the consumer has been notified.” This distinction prevents missed-wakeup errors and makes formal reasoning easier.

Barriers and Coordinated Progress

A barrier coordinates phases of a parallel computation. Each participating thread arrives at the barrier and waits until all expected participants have arrived. The barrier then releases them, usually allowing the next phase to begin. Barriers are useful in numerical algorithms, image processing, simulations, and parallel query execution where phase two must not use incomplete results from phase one.

A reusable barrier must reset its state safely for the next phase. A common design uses a count of arrivals and a generation number. When the final participant arrives, it advances the generation and releases the waiting threads. Without a generation distinction, a fast thread from the next phase may interfere with threads still completing the previous phase. Barriers also require a known participation model: if one expected thread terminates or fails to arrive, all others may wait indefinitely.

Deadlock, Starvation, Livelock, and Priority Inversion

Deadlock is a state in which a set of threads waits forever because each thread holds a resource needed by another. The classical necessary conditions are mutual exclusion, hold and wait, no preemption, and circular wait. Removing any one condition can prevent deadlock in a particular system.

Common prevention strategies include imposing a global order on lock acquisition, acquiring all required resources together, allowing preemption where safe, and using timeouts or deadlock detection. Lock ordering is often the most practical: if resources are numbered, every thread acquires them in increasing order. A thread that needs locks A and B must follow the same order as every other thread.

Starvation occurs when a thread waits indefinitely while other threads continue to make progress. Unfair locks, priority policies, and repeated acquisition by fast threads can cause starvation. Livelock occurs when threads remain active but make no useful progress, as when two processes repeatedly release and retry resources in response to each other. Randomized backoff or a deterministic arbitration rule can help.

Priority inversion occurs when a high-priority thread waits for a lock held by a low-priority thread, while medium-priority work prevents the low-priority thread from running. Priority inheritance temporarily raises the lock holder’s priority; priority ceiling protocols constrain which locks a task may acquire. These mechanisms are important in real-time operating systems.

Lock-Free and Non-Blocking Techniques

Blocking synchronization can reduce responsiveness when a lock holder is delayed, descheduled, or terminated. Non-blocking algorithms instead use atomic operations so that system-wide progress continues even if individual threads are delayed.

A lock-free algorithm guarantees that some thread completes an operation within a finite number of steps, although a particular thread may starve. A wait-free algorithm guarantees completion for every thread within a bounded number of steps and is therefore stronger. A obstruction-free algorithm guarantees progress when a thread executes in isolation.

A basic lock-free stack uses CAS to change the head pointer. A thread reads the current head, links its new node to that head, and uses CAS to install the new node only if the head remains unchanged. If CAS fails, another thread modified the stack, so the operation retries. A similar approach can implement a queue, although queue algorithms require careful treatment of the head and tail pointers.

Lock-free structures introduce the ABA problem. A thread reads value A, is delayed, and later observes A again after another thread changed it to B and back to A. CAS sees no difference even though the object’s history changed. Version tags, hazard pointers, epoch-based reclamation, or suitable garbage collection can address this issue. Memory reclamation is often harder than the update algorithm itself: a node removed by one thread cannot be freed while another thread may still hold a reference to it.

Memory Consistency and Happens-Before Reasoning

A sequentially consistent execution behaves as though operations from all threads were interleaved in a single order that preserves each thread’s program order. This model is intuitive but may restrict hardware and compiler optimization. Weaker memory models permit reordering, provided specified synchronization operations establish the required visibility relationships.

A happens-before relation is a partial order used to reason about visibility. Program order within one thread contributes to happens-before. A successful lock release happens-before a later acquisition of the same lock; an atomic store with release semantics can synchronize with an acquire load that observes it; and thread creation and joining establish additional relationships in many programming environments.

Without a happens-before relationship, a data race may permit one thread to observe stale or surprising values. Declaring a variable atomic may make individual accesses safe, but it does not automatically make a multi-variable invariant safe. For example, atomically updating a pointer and separately updating the object to which it points may still expose an incompletely initialized object unless release-acquire ordering is used.

A useful verification method is to identify every shared variable, state the invariant it participates in, identify the synchronization operation protecting it, and determine the happens-before edges required for visibility. Synchronization should be chosen at the same abstraction level as the invariant. A lock protecting a queue invariant is clearer than several unrelated atomic flags whose combined meaning is difficult to prove.

Applied Case Study: A Concurrent Web-Server Cache

Background

Consider an illustrative web server with many worker threads. The server maintains an in-memory cache mapping request keys to generated responses. Cache hits should be fast, while cache misses may perform expensive computation or contact a remote service.

Situation and Problem

An initial implementation protects the entire cache with one mutex. This prevents corruption but causes all requests to serialize, including requests for unrelated keys. A revised implementation uses one lock per bucket. It improves throughput but occasionally deadlocks when eviction code acquires the bucket lock and then a global statistics lock, while reporting code acquires the statistics lock and then a bucket lock. Another defect occurs when a thread checks for a missing key, releases the lock, computes the response, and later inserts it: several threads may redundantly compute the same response.

Analysis

The cache has several invariants: a bucket’s linked structure must remain well formed; an entry must not be freed while another thread uses it; statistics must be updated consistently; and duplicate computation may be undesirable even if it does not corrupt data. These are different concerns and need not use exactly the same synchronization mechanism.

Approach and Solution

The design establishes a global lock order: bucket locks are always acquired before the statistics lock, or, alternatively, statistics updates are performed atomically outside the bucket critical section. The eviction subsystem follows the same policy. Each bucket uses a mutex because operations are short but may involve pointer manipulation. A per-key “in progress” state, protected by the bucket lock and represented with a condition variable, allows one thread to compute a missing response while others wait. Waiting threads use a `while` loop to recheck whether the entry is now available or whether the computation failed.

The response is fully constructed before publication. Publication uses release semantics, and readers use acquire semantics when accessing the published entry. Reference counting or an epoch-based reclamation scheme ensures that eviction does not free an entry still being read. Metrics that are independent counters use atomic fetch-and-add operations.

Outcome

The resulting design permits requests for different buckets to proceed concurrently, prevents the lock-order deadlock, avoids most duplicate computation, and preserves memory safety. It is more complex than the original single-lock design, so the implementation includes assertions, lock-order documentation, stress tests, and race-detection tools.

Learning Points

The case demonstrates that synchronization is an architectural decision. Performance improvements through fine-grained locking create proof obligations. Atomic counters are suitable for independent statistics but not for arbitrary compound invariants. Condition variables wait for predicates, not notifications. Finally, memory reclamation and publication ordering must be designed together with the data structure.

Professional Practice, Risks, and Best Practices

Concurrent programs are difficult to test because failures may depend on rare schedules. A test that passes repeatedly does not prove correctness. Useful techniques include stress tests with randomized delays, systematic schedule exploration, dynamic race detectors, thread sanitizers, lock-order checkers, assertions for invariants, and code review focused on ownership and lifetime.

Common mistakes include protecting only writes but not reads, assuming a source-level statement is atomic, holding a lock while performing blocking I/O, calling unknown code while a lock is held, using condition-variable `if` statements, destroying a lock while waiters remain, and mixing synchronization conventions. Another mistake is optimizing before measuring: a complicated lock-free design may perform worse than a well-designed mutex because of retries, cache-line contention, and memory-reclamation overhead.

Organizations should document which thread owns each resource, which lock protects each invariant, the permitted lock-acquisition order, whether an operation may block, and the memory-ordering assumptions of atomic operations. Security is also relevant. A synchronization bug can become a denial-of-service vulnerability, expose partially initialized data, or corrupt access-control state. In safety-critical and real-time systems, bounded waiting, priority inversion, failure recovery, and auditable timing behavior may matter more than average throughput.

Current systems increasingly combine several approaches: task runtimes use work stealing, databases use optimistic concurrency and multiversion techniques, kernels use per-CPU data and short spinlocks, and high-performance services use lock-free queues or actor-style ownership. Hardware transactional memory can speculatively execute a critical section and abort on conflict, but capacity limits, interrupts, and unpredictable aborts mean it generally complements rather than replaces conventional synchronization.

A practical design sequence is to define the shared-state invariant, minimize shared mutable state, select the simplest mechanism that can protect the invariant, establish a lock order, specify visibility requirements, analyze failure and cancellation paths, and measure contention. Correctness must be demonstrated before performance tuning begins.

Chapter Summary

Concurrency allows multiple activities to overlap and, on multicore systems, execute in parallel. Shared mutable state creates race conditions, making critical-section protection necessary. A correct solution must provide mutual exclusion, progress, and bounded waiting where required. Atomic hardware instructions such as CAS support locks, semaphores, and non-blocking algorithms, but atomicity must be accompanied by appropriate memory ordering.

Mutexes protect ownership-based critical sections; spinlocks suit very short regions; semaphores represent resource counts or signals; monitors and condition variables encapsulate state and predicate-based waiting; and barriers coordinate phases. Deadlock, starvation, livelock, and priority inversion are distinct liveness and scheduling problems requiring different remedies. Lock-free and wait-free algorithms can improve resilience and scalability but introduce ABA and memory-reclamation challenges. Memory-consistency models and happens-before reasoning determine whether updates become visible in the required order. Sound concurrent design combines explicit invariants, disciplined synchronization, testing, measurement, and documentation.

Key Terms

Concurrency: Overlapping execution of multiple logical activities.

Parallelism: Simultaneous physical execution on multiple processing units.

Race condition: Behavior whose result depends on the timing or ordering of concurrent operations.

Critical section: Code that accesses shared state and requires controlled execution.

Mutual exclusion: Property that prevents conflicting threads from entering simultaneously.

Progress: Requirement that an eligible thread can eventually be selected to enter.

Bounded waiting: Guarantee that a requesting thread will not be postponed indefinitely.

Mutex: Ownership-based mutual-exclusion lock.

Spinlock: Lock whose waiters repeatedly test for availability.

Semaphore: Synchronization counter accessed through atomic wait and signal operations.

Monitor: Encapsulated shared data and procedures with implicit mutual exclusion.

Condition variable: Object that allows a thread to sleep until a shared-state predicate may hold.

Barrier: Phase-coordination mechanism that releases participants after all have arrived.

Deadlock: Permanent waiting caused by a circular dependency among resource holders.

Starvation: Indefinite postponement of one thread while others progress.

Priority inversion: Delay of a high-priority task by lower-priority lock ownership and intervening work.

Compare-and-swap: Atomic operation that updates a location only if it equals an expected value.

Lock-free: Progress guarantee that some operation completes within a finite number of steps.

Happens-before: Ordering relation that establishes visibility and permitted causal order.

ABA problem: CAS error in which a location changes away from and back to an observed value.

Review Questions

Short Answer Questions

1. Distinguish concurrency from parallelism and explain why synchronization may be needed for both.

2. State the three classical requirements of a critical-section solution.

3. Why should a condition variable normally be used in a `while` loop rather than an `if` statement?

4. What is the difference between a mutex and a counting semaphore?

5. Define the ABA problem in a lock-free algorithm.

Long Answer Questions

1. Explain test-and-set, exchange, and compare-and-swap, including their role in constructing synchronization mechanisms.

2. Describe the bounded-buffer solution using semaphores and justify the ordering of its wait and signal operations.

3. Compare mutexes, spinlocks, monitors, semaphores, and condition variables in terms of use, cost, and risks.

4. Explain the four necessary conditions for deadlock and discuss practical prevention strategies.

5. Discuss how memory consistency and happens-before relationships affect the correctness of concurrent programs.

Analytical / Application Questions

1. Two services acquire locks X and Y in opposite orders. Construct an execution showing deadlock and propose two different remedies.

2. Design a monitor-based bounded queue that supports multiple producers and consumers. State its predicates and explain why each wait is guarded by a loop.

3. A lock-free stack removes nodes using CAS but immediately frees removed nodes. Identify the likely failure and recommend a safe reclamation strategy.

22. Multiple Choice Questions with Answers

Question 1

Which property specifically prevents indefinite postponement of a thread requesting entry to a critical section?

A. Mutual exclusion

B. Bounded waiting

C. Atomicity

D. Reentrancy

Correct Answer: B. Bounded waiting

Question 2

A spinlock is generally most appropriate when the protected critical section is:

A. Long and performs blocking I/O

B. Short and the lock holder is expected to run soon

C. Executed by a single thread only

D. Dependent on a condition variable

Correct Answer: B. Short and the lock holder is expected to run soon

Question 3

Why is a condition-variable wait normally placed inside a while loop?

A. To acquire two mutexes simultaneously

B. To prevent the monitor from releasing its lock

C. To recheck the predicate after reacquisition and possible spurious wake-up

D. To guarantee that every waiter is awakened

Correct Answer: C. To recheck the predicate after reacquisition and possible spurious wake-up

Question 4

In a bounded-buffer implementation, what does a semaphore named `empty` normally represent?

A. The number of occupied slots

B. The number of consumers

C. The number of available empty slots

D. The number of mutex owners

Correct Answer: C. The number of available empty slots

Question 5

Which lock-acquisition policy is a practical way to prevent circular wait?

A. Allow each thread to choose any order

B. Acquire locks according to one global order

C. Release all locks only at process termination

D. Use a condition variable for every lock

Correct Answer: B. Acquire locks according to one global order

Question 6

What distinguishes a lock-free algorithm from a wait-free algorithm?

A. Lock-free algorithms use no atomic instructions

B. Wait-free algorithms permit system-wide progress only

C. Lock-free guarantees some thread progresses, while wait-free guarantees each thread completes within a bound

D. Wait-free algorithms are always slower than mutexes

Correct Answer: C. Lock-free guarantees some thread progresses, while wait-free guarantees each thread completes within a bound

Question 7

The ABA problem occurs when:

A. A lock is acquired by two owners at once

B. A value changes and later returns to its old value, fooling a CAS comparison

C. A semaphore reaches zero

D. A barrier has too many participants

Correct Answer: B. A value changes and later returns to its old value, fooling a CAS comparison

Question 8

A high-priority thread waits for a lock held by a low-priority thread while medium-priority work runs. This is:

A. Livelock

B. Priority inversion

C. Bounded waiting

D. False sharing

Correct Answer: B. Priority inversion

Question 9

Which statement best describes a happens-before relationship?

A. It guarantees that two operations execute simultaneously

B. It establishes an ordering and visibility relationship between operations

C. It eliminates the need for atomic operations in all cases

D. It requires all threads to use one processor

Correct Answer: B. It establishes an ordering and visibility relationship between operations

Question 10

In the cache case study, why were independent statistics suitable for atomic fetch-and-add?

A. They formed no shared state at all

B. Each counter update could be performed independently without protecting a compound invariant

C. Fetch-and-add prevents every possible deadlock

D. Statistics never need memory visibility

Correct Answer: B. Each counter update could be performed independently without protecting a compound invariant