OS Concurrency and Synchronization Primitives

By the end of this lesson, you will be able to...

• Trace how a mutex and condition variables keep a bounded queue's shared state coherent.

• Explain why waking a thread is not permission to act, and why the predicate must be rechecked.

• Choose a mutex, condition variable, or semaphore from the coordination fact the program must protect or count.

Idea in one sentence: Synchronization makes a shared-state rule survive the instruction interleavings that the scheduler is free to choose.

Core Insight

A Queue That Looks Safe Until Two Threads Arrive

A small image-processing service receives jobs from two network threads and hands them to one worker. To keep memory bounded, its in-process queue holds at most two jobs.

receivers R1 and R2  ->  [ queue: capacity 2 ]  ->  worker W

The obvious rule seems sufficient: a receiver checks for space, appends a job, and the worker removes it. That model works while only one thread touches the queue at a time.

It fails as soon as the scheduler interleaves the steps. Suppose the queue has one free slot:

R1 observes: one slot is free
R2 observes: one slot is free
R1 appends job A
R2 appends job B

Both receivers made a locally sensible decision. Together they exceeded the capacity rule. The problem is not that the scheduler behaved badly; either order is legal. The program assumed that an observation and the later update were one indivisible action when they were not.

The stronger model is an invariant: a fact that must hold whenever another thread is allowed to inspect the shared state. For this queue, a useful teaching model is:

0 <= item_count <= 2
item_count, head, tail, and stored jobs describe the same queue

The exact data representation is not important. What matters is that these facts change together. Synchronization is how the program says which thread may make that temporary, internally inconsistent transition and which condition makes waiting work useful.

The First Model Breaks at the Instruction Boundary

Source code can hide the boundary. Consider a counter written as:

counter = counter + 1

As a teaching expansion, read it as three actions: read the old value, compute the new value, and store it. Two threads can then follow this illustrative interleaving:

counter begins at 0

R1 reads 0
R2 reads 0
R1 writes 1
R2 writes 1

result: 1, although two increments were attempted

In a real language, whether this is a data race and what outcomes are permitted also depends on that language's memory model. This track does not teach those formal rules. The host-level lesson is narrower: when several threads access mutable shared state, source-line order is not a coordination contract.

A critical section is the region in which a thread observes and changes the state needed to preserve an invariant. It is not merely “the line containing a lock.” For our queue, checking whether it is full and appending a job belong to the same critical section. Separating them recreates the race.

Three Questions, Three Primitives

It helps to choose a primitive by the question it answers instead of by habit.

A mutex gives exclusive ownership of a critical section. If another thread already owns it, a normal lock operation may block until it becomes available. It does not, by itself, say what a consumer should do when the queue is empty. Repeatedly locking, checking, unlocking, and checking again would be a busy loop: correct in a narrow sense, but wasteful because it consumes CPU while no useful state change has occurred.

A condition variable pairs waiting with a predicate over state protected by a mutex. In plain English, the worker says: “I cannot pop while item_count == 0; wake me only so I can check that fact again.” The condition variable is not the queue and does not store the job. The queue state is the durable fact.

A semaphore is a counter with waiting behavior. A wait decrements it when its value is positive; when it is zero, the caller blocks until a permit becomes available. It is especially natural when the important fact is a number of identical units: two free slots, eight database connections, or one item available to consume.

The Queue Mechanism, Step by Step

We will use one mutex and two condition variables:

state:
  queue, item_count, capacity = 2
  mutex
  not_empty   # predicate: item_count > 0
  not_full    # predicate: item_count < capacity

The API names differ by language. This pseudocode shows the contract rather than a particular library:

producer(job):
  lock mutex
  while item_count == capacity:
    wait(not_full, mutex)
  append job; item_count increases
  signal not_empty
  unlock mutex

consumer():
  lock mutex
  while item_count == 0:
    wait(not_empty, mutex)
  remove job; item_count decreases
  signal not_full
  unlock mutex
  process job outside the mutex

The wait(condition, mutex) operation has a crucial shape: it releases the mutex while the caller sleeps, then reacquires the mutex before it returns. If the consumer slept while holding the mutex, no producer could lock the queue to append the job that makes not_empty true. POSIX condition waits define that release-and-wait relationship atomically with respect to the mutex and condition variable.

Why is the guard a while, not an if? A wakeup says only that the predicate may have changed. Another consumer might acquire the mutex first and take the only job. A condition wait can also return without the predicate becoming true. The thread must own the mutex, inspect the actual queue state, and decide again.

A Worked Trace: Empty Queue, Full Queue, Then Progress

Start with an empty queue. The events below are illustrative, but every state transition is the point of the design.

The signal comes after the state mutation. R1 does not signal “here is job A” as if the condition variable carried a message. It signals that the protected state changed and a waiter may now profitably recheck its predicate. If no worker is waiting at that instant, the queue still contains A or B; a later worker sees that fact by locking and inspecting the queue.

So far, the mechanism has made two kinds of waiting visible. W waits because there is no item. A receiver waits only if capacity is exhausted. In both cases the thread gives up the mutex while it cannot make progress, allowing another actor to create the required state change.

The Semaphore Version Changes the Representation, Not the Need for Rules

The same queue can use two semaphores:

free_slots = 2
available_items = 0
queue_mutex

producer:
  wait(free_slots)
  lock queue_mutex
  append job
  unlock queue_mutex
  post(available_items)

consumer:
  wait(available_items)
  lock queue_mutex
  remove job
  unlock queue_mutex
  post(free_slots)

Here the capacity rule is represented directly: a producer must obtain a free-slot permit before appending, and a consumer must obtain an item permit before removing. The mutex remains necessary because a permit count alone does not safely update the queue's head, tail, and storage.

This version is a good fit when the coordination fact really is a count. Condition variables are usually clearer when a thread must wait for a richer predicate, such as “the queue contains a job for tenant X and the worker is not draining.” Neither primitive is a universal upgrade; the state you need to represent decides.

Costs, Limits, and Signals

Synchronization buys safety and explicit waiting. It also adds costs. The central trade-off is simple: stronger coordination protects the invariant, but it can make unrelated work wait when the protected region is too broad.

Holding the queue mutex while processing A would be another subtle error. The invariant does not require it; only removal does. If the worker performs slow I/O under that mutex, receivers cannot append even when there is space. The diagnosis is not “locks are bad.” It is that the protected region includes work that does not need the shared-state guarantee.

Common Confusions

Confusion: A mutex makes the whole program sequential.

Why it is tempting: one thread waits while another owns the lock.

Better model: only the critical section is exclusive. Work outside it can run concurrently. Keep the section as small as the invariant allows, not smaller than the invariant requires.

Confusion: A signal means the condition is now guaranteed.

Why it is tempting: the name sounds like a delivery notification.

Better model: the signal invites a waiter to recheck protected state. The predicate, not the signal, authorizes the next action.

Confusion: A full bounded queue proves the lock is broken.

Why it is tempting: waiting looks like failure.

Better model: a full queue can be correct backpressure. It becomes a problem when it misses a deadline, has no shedding policy, or remains full because consumers cannot make progress.

Check Your Understanding

Check: The worker wakes from not_empty, but R1 has already removed the only job before the worker reacquires the mutex. May the worker pop anyway?

Think first, then reveal.

Answer: No. The wakeup only meant that not_empty might have become true. After it reacquires the mutex, the worker finds item_count == 0 and waits again. This is exactly why the predicate is guarded by while under the mutex.

Practice: Diagnose the Queue Before Changing It

An image service has a capacity-200 queue. For ten minutes, it stays at 200, producers spend most of their time waiting for not_full, and workers show little CPU use. An engineer proposes replacing the mutex with a semaphore.

What should you investigate first, and would that replacement alone address the observation?

A good answer should mention:

• The queue is exposing sustained consumer-side pressure; inspect worker blocking, downstream I/O, job duration, and completed-job rate before changing primitives.
• A semaphore may be a valid representation for capacity, but it does not make a blocked worker or slow dependency faster.
• The bounded queue is useful evidence, not automatically a defect. The operational decision may be to add capacity, reduce input, shed work, or fix the dependency, depending on the trace.
• Any redesign must still protect the queue's structural invariant and define what happens when no capacity is available.

Resources

• [BOOK] Operating Systems: Three Easy Pieces — Focus: Read the concurrency chapters on locks, condition variables, and bounded-buffer reasoning.
• [BOOK] The Little Book of Semaphores — Focus: Work through classical synchronization problems and identify the state predicate each solution protects.
• [ARTICLE] POSIX pthread_mutex_lock — Focus: Inspect ownership, blocking, and mutex-type behavior.
• [ARTICLE] POSIX pthread_cond_wait — Focus: See the atomic release, wait, and reacquisition relationship with the mutex.
• [ARTICLE] Linux sem_wait(3) Manual Page — Focus: See how a semaphore blocks at zero and proceeds by decrementing an available permit.

Key Takeaways

• A race appears when independent-looking actions jointly violate a shared invariant under a legal interleaving.
• A mutex protects the queue state; a condition variable lets a thread wait to recheck a state predicate; a semaphore models available permits.
• A condition-variable wakeup is not permission to act. Recheck the predicate while holding its mutex.
• A bounded queue is both a synchronization mechanism and an overload boundary: it makes capacity pressure observable.
• When the queue is full, inspect the state that prevents consumers from progressing before replacing the synchronization primitive.