4 Race conditions, semaphores and synchronization

This is one of the highest-priority units. The 2016 exam devoted an entire 11-point problem to instruction-level race tracing, semaphore repair, semaphore semantics and execution ordering. 12-ibn-klausur-2016.pdf The recent exam protocol also reports an independent pseudocode-based race-condition problem. 13-Ged-chtnisprotokoll_Klausur_-IBN_Ersttermin.pdf

The coverage below follows Day 2 of your plan and the selected Sheet 3 exercises. 15-Operating-Systems-and-Networks-SoSe-25-Notes.pdf 11-ueb03-ibn-SS2025.pdf

Why synchronization is necessary

Threads belonging to the same process have:

separate registers and stacks;
a shared address space containing global variables, heap objects and other shared resources.

Sharing makes communication inexpensive, but it allows multiple threads to access the same data concurrently.

Consider:

counter = counter + 1

Although this looks like one operation, it normally consists conceptually of:

LOAD  counter into register R
ADD   1 to R
STORE R into counter

A thread can be interrupted between any two of these instructions.

Suppose counter = 0 and two threads both increment it:

Step	Thread A	Thread B	Shared `counter`
1	Load `counter` into `RA` (`RA=0`)		0
2		Load `counter` into `RB` (`RB=0`)	0
3	Add 1 to `RA` (`RA=1`)		0
4	Store `RA`		1
5		Add 1 to `RB` (`RB=1`)	1
6		Store `RB`	1

The correct result would be 2, but the final result is 1. One increment has been overwritten: a lost update.

This can happen on a single-core CPU. The threads do not need to execute physically at the same instant; preemption and interleaving are enough.

Race conditions

A race condition exists when the correctness or result of a program unintentionally depends on the timing or execution order of concurrent operations.

A typical race condition requires:

shared state;
concurrent accesses to that state;
at least one access that modifies it;
insufficient synchronization.

The output may differ between executions because the scheduler can produce different interleavings.

Critical region

A critical region or critical section is a part of a program that accesses shared data and must not be executed simultaneously with a conflicting critical region.

entry protocol

critical region

exit protocol

non-critical region

The entry and exit protocols are implemented using a mutex, semaphore or another synchronization primitive.

Requirements of a good mutual-exclusion solution

A correct solution should provide:

Mutual exclusion: conflicting threads are never simultaneously inside their critical regions.
Progress: a thread outside its critical region must not unnecessarily prevent others from entering.
No timing assumptions: correctness must not depend on CPU speed or the number of cores.
No starvation/bounded waiting: a thread requesting entry should not be postponed forever.

The first is a safety property: “nothing bad happens.” Progress and absence of starvation are liveness properties: “something good eventually happens.”

Atomicity

An operation is atomic if other threads cannot observe or interrupt a partially completed execution of that operation.

For example, the abstract operation

wait(S)

must itself be atomic. If two threads could simultaneously test and decrement the semaphore non-atomically, the semaphore would not provide synchronization.

Protecting a critical region does not mean that all its ordinary instructions become individually atomic. It means that the entry protocol ensures that only the permitted thread or threads can execute that region.

Semaphores

A semaphore contains:

a nonnegative count representing available permits or resource instances;
an associated queue of blocked threads;
two atomic operations, conventionally called wait and signal.

Other common names are:

Operation	Alternative names
`wait(S)`	`P(S)`, `down(S)`, `sem_wait(S)`
`signal(S)`	`V(S)`, `up(S)`, `post(S)`, `sem_post(S)`

`wait(S)`

Conceptually:

if a permit is available:
    consume one permit
    continue
else:
    block until a permit becomes available

Thus, wait may block.

`signal(S)`

Conceptually:

make one permit available
if a thread is waiting:
    wake one waiting thread

signal does not normally block.

The implementation may represent blocked threads using negative values or separate queues, but exam solutions should normally describe the abstract behaviour rather than depend on a particular representation.

Binary and counting semaphores

A binary semaphore has at most one available permit:

Semaphore mutex = 1

A counting semaphore can represent several identical resource instances:

Semaphore printers = 3

Up to three successful wait(printers) operations can occur before another thread must release a permit.

Mutual exclusion with a semaphore

Initialize the semaphore to 1:

Semaphore mutex = 1

Every thread uses:

wait(mutex)

    // critical region

signal(mutex)

The first thread consumes the only permit. Other threads calling wait(mutex) must block until the first thread calls signal(mutex).

The protected operation must lie entirely between wait and signal:

wait(mutex)
counter = counter + 1
signal(mutex)

Protecting only the load or only the store would still allow an unsafe interleaving.

Mutex versus binary semaphore

At the level required by many introductory exercises, a mutex can be viewed as a binary lock. More precisely:

a mutex normally has an owner;
only the thread that locked it should unlock it;
a semaphore represents permits and does not necessarily have ownership.

Semaphores can consequently express both mutual exclusion and dependencies between different threads.

Enforcing an execution order

Suppose block X in Thread 1 may execute only after block Y in Thread 2.

Initialize a semaphore to zero:

Semaphore finished_Y = 0

Thread 1:

wait(finished_Y)
X

Thread 2:

Y
signal(finished_Y)

Why initialize it to zero?

If Thread 1 reaches wait first, it blocks.
After Thread 2 completes Y, signal provides the permit.
If Thread 2 finishes first, the semaphore retains the permit. Thread 1’s later wait consumes it and continues immediately.

This is what is meant by saying that a semaphore has memory: an earlier signal can be remembered in its counter.

Blocking versus busy waiting

A primitive can wait in two ways.

Busy waiting

while lock is unavailable:
    repeatedly test lock

The thread remains runnable and consumes CPU time. A lock implemented this way is often called a spinlock.

Busy waiting can be reasonable for extremely short waits inside kernels or multiprocessor code, but it is inefficient for long waits.

Blocking

If the resource is unavailable:

the thread is placed in a waiting queue;
its state becomes Waiting/Blocked;
another runnable thread receives the CPU;
a later signal makes the blocked thread Ready.

Notice that waking a thread normally produces:

Waiting → Ready

not immediately Waiting → Running.

Condition variables

A condition variable allows a thread to sleep until some condition involving shared state may have become true.

It must be used together with:

a predicate, such as count > 0 or production_done;
a mutex protecting that predicate;
the condition variable on which threads wait.

Canonical pattern:

lock(mutex)

while (!condition) {
    cond_wait(condition_variable, mutex)
}

// condition is true; access shared state

unlock(mutex)

cond_wait(cv, mutex) performs three important actions:

atomically releases mutex and puts the caller to sleep;
waits for a notification;
reacquires mutex before returning.

The atomic release-and-sleep step prevents the following lost-wakeup race:

waiter checks that the condition is false;
notifier makes it true and sends a signal;
waiter goes to sleep after the signal;
no future signal arrives.

Why `while`, not `if`?

After waking, the thread must check the predicate again because:

wakeups may be spurious;
another awakened thread may acquire the mutex first and consume the resource;
a notification means “the condition may now be true,” not “the condition is guaranteed to remain true.”

Correct:

while (count == 0)
    cond_wait(not_empty, mutex)

Unsafe:

if (count == 0)
    cond_wait(not_empty, mutex)

`signal` versus `broadcast`

cond_signal(cv) wakes at least one waiting thread.
cond_broadcast(cv) wakes all threads waiting on cv.

A producer adding one item normally needs to wake only one consumer. If production_done becomes true and every consumer must notice it and terminate, a broadcast is appropriate.

The awakened threads do not all enter the critical region simultaneously: each must first reacquire the mutex.

Condition variables do not remember notifications

If cond_signal or cond_broadcast is called while nobody is waiting, the notification disappears.

This differs from a semaphore:

signal(S)

with no waiter increments or preserves the semaphore’s permit count, so a later wait(S) can consume it.

A mutex remembers whether it is currently locked, but an unlock is not a stored notification that a future thread can consume.

Why update and signal under the mutex?

The standard protocol is:

lock(mutex)
done = true
cond_broadcast(done_changed)
unlock(mutex)

The mutex makes changing the predicate and notifying waiters part of one synchronized protocol. A waiter cannot slip between checking done and beginning to wait. When it wakes and reacquires the mutex, it sees a consistent value of done.

Example: producer-consumer queue

producers create items / jobs and insert them into a shared queue.
consumers remove items
a consumer cannot remove an item while the queue is empty
instead of repeatedly checking the queue in a busy loop, it sleeps on not_empty

Concrete Example: downloading and playing a video

The producer downloads video chunks:

network -> buffer

The consume decodes and siplays them

buffer -> video player

the downloader puts some chunks into the buffer
the player begins consuming them
both continue concurrently

Other canonical examples:

a network interface receives packets, while an application processes them
a web server accepts requests while worker threads handle earlier requests
one thread reads files, while another processes their contents.
keyboard input arriving while the application processe earlier input

The general pattern is that

a buffer crates a pipleline and absorbs temporary differences in speed between producers and consumers

Benefits of concurrent production and consumption

lower latency: the consumer can start as soon as the first item exists instead of waiting for all items
higher throughput: production and consumption may overlap
1. one core produces while another consumes
2. a network or disk operation runs while the cpu processes previous data

bounded memory use: for a large or infinite stream, we may use a bounded buffer:

producer -> fixed-size buffer -> consumer

A bounded buffer typically uses two predicates and two condition variables:

std::condition_variable not_empty; // consumers wait here
std::condition_variable not_full; // producers wait here

Complete producer-consumer program

shared Queue jobs
shared Mutex mutex
shared ConditionVariable not_empty
shared Boolean production_done = false

function producer():
    for number from 1 to 10:
        job = create_job(number)

        lock(mutex) //begin critical region 1

        jobs.push(job)
        signal(not_empty)

        unlock(mutex)

        // end critical region 1

    // no more jobs will be produced
    lock(mutex) // begin critical region 2

    production_done = true
    broadcast(not_empty)

    unlock(mutex) // end cr 2

function consumer(worker_id):
    while true:
        lock(mutex)

        while jobs.empty() and not production_done:
            wait(not_empty, mutex)
        
        if jobs.empty() and production_done:
            unlock(mutex)
            return
        
        job = jobs.pop()

        unlock(mutex)

        // processing is done outside of critical region
        process(job)

function main():
    producer_thread = start_thread(producer)
    consumer_thread_1 = start_thread(consumer, 1)
    consumer_thread_2 = start_thread(consumer, 2)

    join(producer_thread)
    join(consumer_thread_1)
    join(consumer_thread_2)

    print("all jobs completed")

Bounded-buffer producer-consumer problem

uses a shared queue with a fixed maximum capacity

consumers wait on not_empty when the buffer is empty
producers wait on not_full when the buffer is full
a mutex protexts the buffer and related shared state

The bounded buffer provides backpressure: if consumers cannot keep up, producers are forced to wait instead of allowing the queue to grow indefiniely.

Practical Example

Consider a program that reads large imagems from disk and processes them:

the producer reads images and places them in memory
several consumers resize / transform or analyze the images
each image may occupy considerable memory

An unbounded queue could consumer all abailable memory if disk reading is temporarily faster than image processing. A buffer limited to, say, five images ensures that at most five unprocessed images are held in memory

Complete typed pseudocode


// shared state

constant BUFFER_CAPACITY = 5
constant NUMBER_OF_JOBS = 20
constant NUMBER_OF_CONSUMERS = 2

shared Queue<Job> jobs

shared Mutex mutex
shared ConditionVarialbe not_empty
shared ConditionVarialbe not_full

shared production_done = false


// producer
function producer() -> Void:
    for job_number from 1 to NUMBER_OF_JOBS:
        job = new Job(job_number)

        lock(mutex)

        while jobs.size() == BUFFER_CAPACITY:
            wait(not_full, mutex)
        
        // buffer is not full
        jobs.push(job)

        // buffer is not empty
        signal(not_empty)
        
        unlock(mutex)

    lock(mutex)

    production_done = true
    // every sleeping consumer must discover that production is finished
    broadcast(not_empty)

    unlock(mutex)

// consumer

function consumer() -> Void:
    while true:
        lock(mutex)

        while jobs.empty() and not production_done:
            wait(not_empty, mutex)
        
        // no buffered jobs remain, and no new jobs will arrive
        if jobs.empty() and production_done:
            unlock(mutex)
            return

        // buffer not empty
        job = jobs.pop()

        // at least one producer may now be able to proceed
        signal(not_full)

        unlock(mutex)

        process(job)


// main program

function main() -> Void:
    consumers = new Array<Thread>(NUMBER_OF_CONSUMERS)

    for i from 0 to NUMBER_OF_CONSUMERS - 1:
        consumers[i] = start_thread(consumer)

    producer_thread = start_thread(producer)

    join(producer_thread)
    
    for i in [1, NUMBER_OF_CONSUMERS]:
        join(consumers[i])

    print("all jobs completed")

join()

join() does not end the thread. It makes the calling thread wait until another thread has finished.

consumer_thread_1 = start_thread(consume, 1)

... 

join(consumer_thread_1)

start a new htread executing consumer(1)
continue executing the main thread
When join(consumer_thread_1) is reached, pause the main thread until consumer_thread_1 terminates

This guarantees that the main thread will not prematurely terminate before consumer_thread_1 does, which would be possible because the scheduler can decide to execute the return or the final statement of main, ending the main thread, before consumer_thread_1 is finished

Producer–consumer pattern

For a bounded buffer of capacity (N), a semaphore solution uses:

Semaphore empty = N
Semaphore full  = 0
Semaphore mutex = 1

Producer:

produce(item)

wait(empty)
wait(mutex)
insert(item)
signal(mutex)
signal(full)

Consumer:

wait(full)
wait(mutex)
item = remove()
signal(mutex)
signal(empty)

consume(item)

Interpretation:

empty counts free slots;
full counts stored items;
mutex protects the buffer data structure.

Do not acquire mutex before waiting for empty or full. Otherwise a thread might sleep while holding the buffer lock, preventing the other side from changing the condition it is waiting for.

Simplified read–write lock

The reader-writer problem arises whenever many threads access the same shared data, where:

readers only inspect the data and may safely run concurrently
writers modify the data nad therefore need exclusive access

Example 4.1 (In-memory cache) A web server may maintain a shared cache

readers: look up cached pages or database results
writers:
- insert new entries
- remove expoired entries
- refresh existing entries

Naive Solution

Suppose:

Semaphore S = N

A reader consumes one permit:

lock_read:
    wait(S)

unlock_read:
    signal(S)

A writer attempts to consume all (N) permits:

lock_write:
    repeat N times:
        wait(S)

unlock_write:
    repeat N times:
        signal(S)

This appears to permit either:

up to (N) simultaneous readers; or
one writer holding every permit.

But lock_write is not atomic.

For (N=3), two writers could execute:

W1: wait(S)   // S: 3 → 2
W2: wait(S)   // S: 2 → 1
W1: wait(S)   // S: 1 → 0
W2: wait(S)   // blocks
W1: wait(S)   // blocks

Neither writer can acquire all three permits, and neither can release its partial acquisition because it has not entered the critical region. This is a deadlock.

A simple repair serializes writers while they collect the permits:

Semaphore S = N
Semaphore writer_gate = 1

lock_write:
    wait(writer_gate)
    repeat N times:
        wait(S)
    signal(writer_gate)

unlock_write:
    repeat N times:
        signal(S)

Only one writer may now attempt the multi-step acquisition.

This repair prevents the writer–writer split deadlock, but it does not necessarily guarantee fairness: continuously arriving readers might still starve a writer.

One correction to retain from your earlier work: your old Sheet 3 answer identified the interleaved writer acquisition, but described it as permitting simultaneous writing. The direct consequence is instead the deadlock shown above. 14-Operating-Systems-and-Networs-SoSe-25-Solutions.pdf

Solving fairness Problem

First approach: sared entrance gate

Semaphore S = N
Semaphore entry_gate = 1

// reader
lock_read:
    wait(entry_gate)
    wait(S)
    signal(entry_gate)

unlock_read:
    signal(S)


// writer
lock_write:
    wait(entry_gate)
    repeat N times:
        wait(S)

unlock_write:
    repeat N times:
        signal(S)
    signal(entry_gate)

Here, once a writer acquires entry_gate

no new reader can beign acquiring a permit
existing readers may finish and release their permits
the writer eventually collects all N permits
the writer holds both the entrance gate and all permits during its critical region

But the fairness is still not guaranteed, if the semaphore is completely unfair. It is still possible for newly arriving readers repaetedly to acquire the gate before hte writer:

reader 1 releases gate
reader 2 immediately acquires it
reader 2 releases gate
reader 3 immediately acquires it

The the writer could still starve. But with a fair / FIFO semaphore

waiting order
    writer -> reader 2 -> reader 3

new readers cannot overtake the writer.

Note

A fair / FIFO alone would solve the starvation problem but the writer could still wait very long, because its wait requests in the loop could be often intersparsed with the requests of readers continiously arriving

Common exam traps

Treating counter++ as an indivisible operation.
Thinking a race requires multiple CPU cores.
Protecting different threads with different mutexes.
Forgetting to initialize a mutex semaphore to 1.
Initializing an ordering semaphore to 1 instead of 0.
Forgetting that semaphore operations must themselves be atomic.
Omitting signal on some control-flow path.
Sleeping while holding a mutex needed by the thread that could wake you.
Using if instead of while around cond_wait.
Assuming condition-variable notifications are remembered.
Confusing deadlock with starvation.
Calling every timing-dependent output a race: nondeterministic ordering can be intentional and harmless.

Exam-like exercises

Do these closed-book. Allow approximately 35–45 minutes in total.

Exercise 1: Race condition and semaphore repair

Two threads share:

integer counter = 0

Thread A:

repeat 3 times:
    counter = counter + 1

Thread B:

repeat 2 times:
    counter = counter + 1

Assume a single-core system and that an increment consists of:

LOAD counter into private register R
ADD 1 to R
STORE R into counter

Questions

Define the term race condition.
What should the final value of counter be?
Give an instruction-level interleaving in which one update is lost.
Explain why the race can occur despite there being only one CPU core.
Repair the program using one semaphore. State its initial value.
Explain completely but concisely what wait and signal do.
Would it be sufficient for A and B to use two different mutexes? Explain.

Use this table for Part 3:

Step	Thread	Instruction	Private register	Shared `counter`
1
2

Exercise 2: Ordering and condition variables

Part A: Ordering

Block send_result in Thread A may execute only after Thread B has completed calculate_result.

Write the simplest semaphore-based pseudocode for both threads. Give the semaphore’s initial value.

Your solution must work regardless of which thread starts first.

Part B: Find the condition-variable errors

A consumer uses:

lock(mutex)

if (count == 0)
    cond_wait(not_empty, mutex)

item = remove_from_buffer()
count = count - 1

unlock(mutex)

The producer uses:

add_to_buffer(item)
count = count + 1
cond_signal(not_empty)

Answer:

Identify at least two synchronization errors.
Rewrite the relevant consumer and producer pseudocode correctly.
Why must the consumer test the condition in a while loop?
What happens if cond_signal(not_empty) is called while nobody is waiting?
What would happen in the analogous situation with signal(S) on a semaphore?
When would broadcast be preferable to signal?

Exercise 3: Debugging a semaphore construction

Let (N=4):

Semaphore S = 4

lock_read:
    wait(S)

unlock_read:
    signal(S)

lock_write:
    for i = 1 to 4:
        wait(S)

unlock_write:
    for i = 1 to 4:
        signal(S)

Give an exact execution involving two writers that leads to failure.
Classify the failure as:
- mutual-exclusion violation,
- deadlock, or
- starvation.
Explain precisely why neither writer can continue.
Repair the construction using one additional semaphore or mutex.
Does your repair also guarantee that a writer can never starve? Explain briefly.

Answers

Exercise 1

a race condition occurs when the reseult of a program depends on the timing or interleaving of unsynchronized accesses to shared state, with at least one acccess modifying that state, so that some interleavings can produce an incorrect result
5

step	Thread	Instruction	private register	shared `counter`
1	A	load counter RA	RA == 0	0
2	A	add 1 RA	RA == 1	0
3	A	store RA counter	RA == 1	1
4	B	load counter RB	RB == 1	1
5	B	add 1 RB	RB == 2	1
6	B	store RB counter	RB == 2	2
7	A	load counter RA	RA == 2	2
8	A	add 1 RA	RA == 3	2
9	A	store RA counter	RA == 3	3
10	A	load counter RA	RA == 3	3
11	A	add 1 RA	RA == 4	3
12	B	load counter RB	RB == 3	3
13	B	add 1 RB	RB == 4	3
14	B	store RB counter	RB == 4	4
15	A	store RA counter	RA == 4	4

A race condition does not require physical parallelism. On a single-core CPU, the scheduler may preempt one thread between its LOAD and STORE instruction and run the other thread. The resulting interleaving allows both treads to operate on the same stale value

code:

semaphore mutex = 1

thread A:
 repeat 3 times: 
     wait(mutex)
     counter = counter + 1
     signal(mutex)
thread B:
 repeat 2 times: 
     wait(mutex)
     counter = counter + 1
     signal(mutex)

answer:
- wait: atomically decrements the value of a semaphore if it is possitive, otherwise blocks the calling thread and places it in the waiting queue associated with the semaphore
- signal: atomically increments the value of the semaphore if there are no waiting threads in the queue, or if the queue is not empty it wakes up a waiting thread
No, if thread A is holding mutexA and executing its critical region a thread B could still lock mutexB, because it is not held by thread A, and thus enter the critical region. This would mean both threads are executing in their conflicting critical regions.

Exercise 2

Part A

Semaphore result_ready = 0

Thread A:
    wait(result_ready)
    send_result()

Thread B:
    calculate_result()
    signal(result_ready)

Part B

answer:
- Error 1: cond_wait(not_empty, mutex) should be checked inside a while loop and not an if statement
- Error 2: in producer the access to shared variables must be protected with a mutex lock

correction:

// consumer:
lock(mutex)

while (count == 0) :
    cond_wait(not_empty, mutex)

item = pop(buffer)
count = count - 1

unlock(mutex)

// producer:
lock(mutex)
push(buffer, item)
count = count + 1
cond_signal(not_empty)
unlock(mutex)

after a producer pushes an item into the buffer and sends a signal to not_empty, it doesn’t necessarily mean that a sleeping thread will immediately run. First it becomes ready to run:
```
blocked -> ready
```
scheduler may schedule it at an arbitrary point in time. Meanwhile another consumer previously in ready state might be scheduled and already consumed the item. Which means that the buffer may be empty again. But if we have an if-statement instead of a while loop, after cond_wait(not_empty, mutex) reacquires the mutex it will exit without rechecking the condition whether the buffer is empty and continue with the next statement, which is usually popping the item from the buffer. But this will cause an error since the buffer is empty. Therefore after exiting cond_wait() the consumer must recheck the condition, which is realized with a while loop

more concisely:

A notification only means that the predicate may now be true. Before the awakened consumer reacquires the mutex, another consumer may consume the item; wakeups may also be spurious. Therefore, the consumer must recheck count == 0 after every wakeup, which requires while, not if.
The signal goes undetected, it is not stored or rememberd. This is not necessarily an error because the shared predicate is persistent. A later consumer checks count while holding the mutex and will not wait if an item is already available.
S is incremented, which means that the signal is ‘remembered’, and a later wait(S) can consumer that permit
when all waiting threads must be able continue. For example if the buffer is empty and production is finished in the producer-consumer example, the sleeping threads must all continue. Otherwise they will wait indefinitely, since no new items will arrive and therefore the producer will not send a signal to wake them up.

Exercise 3

answer:

W1: wait(S) // S: 4 -> 3
W1: wait(S) // S: 3 -> 2
W2: wait(S) // S: 2 -> 1
W2: wait(S) // S: 1 -> 0
W1: wait(S) // blocks
W2: wait(S) // blocks

deadlock
In this interleaving, W1 and W2 each hold two permits, while S==0. Each needs two additional permits before it can enter the critical region. Neither reaches unlock_write, so neither can release its already acquired permits. Consequently, both remain blocked forever. More generally, a deadlock occurs if the permits are divided between the writers before either writer acquires all four

answer

Semaphore S = 4
Semaphore writer_gate = 1

lock_read: wait(S)
unlock_read: signal(S)

lock_write:
 wait(writer_gate)
 repeat 4 times:
     wait(S)
 signal(writer_gate)

 unlock_write:
     repeat 4 timtes: signal(S)

No. The gate prevents competing writers from splitting the permits, but it does not prevent newly arriving readers from repeatedly acquiring permits before the waiting writer. Therefore, writer starvation remains possible unless additional fairness—such as a common entry gate or an appropriate FIFO guarantee—is provided.

Why synchronization is necessary

Race conditions

Critical region

Requirements of a good mutual-exclusion solution

Atomicity

Semaphores

wait(S)

signal(S)

Binary and counting semaphores

Mutual exclusion with a semaphore

Mutex versus binary semaphore

Enforcing an execution order

Blocking versus busy waiting

Busy waiting

Blocking

Condition variables

Why while, not if?

signal versus broadcast

Condition variables do not remember notifications

Why update and signal under the mutex?

Example: producer-consumer queue

Concrete Example: downloading and playing a video

Benefits of concurrent production and consumption

Complete producer-consumer program

Bounded-buffer producer-consumer problem

Practical Example

Complete typed pseudocode

Producer–consumer pattern

Simplified read–write lock

Naive Solution

Solving fairness Problem

First approach: sared entrance gate

Common exam traps

Exam-like exercises

Exercise 1: Race condition and semaphore repair

Questions

Exercise 2: Ordering and condition variables

Part A: Ordering

Part B: Find the condition-variable errors

Exercise 3: Debugging a semaphore construction

Answers

Exercise 1

Exercise 2

Part A

Part B

Exercise 3

`wait(S)`

`signal(S)`

Why `while`, not `if`?

`signal` versus `broadcast`