Concurrency and synchronization — practice with guided problems step by step: a race condition, a semaphore with its queue, the bounded buffer and an exercise in the exam format (and the sale I swore could not be lost)

While revising for the midterm, a classmate asked me: «If two threads do seats = seats - 1 at the same time and there were 5 seats, how many are left?». I said 3 without hesitating: two sales, two seats fewer. He drew on a napkin the three steps of each thread (read, subtract, write), mixed them in one particular way and showed me the result: 4. A sale lost without either thread doing anything wrong. Since then, every time I see shared data, I do not ask what each thread does, but in what order their steps can mix.

This is the guided practice for concurrency and synchronization. In the concurrency and synchronization theory you saw race conditions, the critical section, the mutex and semaphores, with the student flat and the laptop. Here we solve four problems step by step: counting the possible results of a race, tracing a semaphore with its queue, following the bounded buffer and reasoning about what a program with semaphores can print, as in the written part of the exam. Afterwards, in the concurrency and synchronization exercises, it is your turn.

Before you start

It helps to be clear about:

• That x = x - 1 is not one operation: it is three steps (read into a register, subtract, write), and a context switch can fall between any of them.
• What a critical section is and the three requirements (mutual exclusion, progress and bounded waiting).
• The theory’s definition of a semaphore: wait() subtracts if the value is greater than 0 and otherwise blocks the process in the queue; signal() wakes the first in the queue and, if there is nobody, adds.
• The bounded buffer with three semaphores: empty (free slots), full (items) and mutex.

If any of them sounds shaky, go over the theory before carrying on.

How to solve a concurrency problem

The four problems follow the same four-step method:

1. Split each operation into its atomic steps (read, operate, write; or wait and signal) and number them per thread.
2. Decide which interleavings matter: all of them if there are few, or the worst case if you are asked to show that something can fail.
3. Trace in a table the value of each variable and each semaphore after each step, with who is blocked.
4. Check: that each thread has done all its steps in its order, that the semaphores end with a consistent value and that nobody is left blocked for no reason.

Problem 1: a race condition

Statement. A concert website has seats = 5. Two threads, A and B, serve two buyers at the same time and each runs seats = seats - 1 without any protection. a) What final values can seats have? b) How many different interleavings are there and how many give the right value? c) How is it fixed?

The idea

Each thread does three steps: read seats into its register, subtract 1 in the register and write the register into seats. The internal order of each thread is fixed; what changes is how the six steps mix. It is enough to look at when each thread reads: if one reads after the other has written, all is well; if both read before either writes, one of them loses its sale.

Step by step

An interleaving that fails, ABABAB:

Step	Thread	What it does	A’s register	B’s register	seats
1	A	reads	5	—	5
2	B	reads	5	5	5
3	A	subtracts	4	5	5
4	B	subtracts	4	4	5
5	A	writes	4	4	4
6	B	writes	4	4	4

a) The possible values are 3 (right) and 4 (one sale lost). It cannot be 5: both threads write at least a 4.

b) There are $\binom{6}{3} = 20$ interleavings (A’s positions among 6). Only those that do not mix anything give 3: AAABBB and BBBAAA. The other 18 give 4. As soon as the second thread reads before the first one writes, a sale is lost.

c) By making seats = seats - 1 a critical section: lock(m); seats = seats - 1; unlock(m); with a mutex, or with a semaphore S = 1 and wait(S) / signal(S). That way one thread’s three steps cannot mix with the other’s.

Check

• Each row of the table respects each thread’s order: A reads, subtracts and writes in that order (steps 1, 3 and 5), and so does B (2, 4 and 6).
• 2 + 18 = 20: every interleaving is counted.
• The result 4 is the value written by the last one: it is the theory’s «overwriting write».

Questions you might ask

Why can it not be 5? Because both threads end up writing, and what they write is what they read minus 1. At least one writes 4, and nobody writes 5.

If it is so likely, why does it almost always work on my computer? Because the three steps take nanoseconds and a context switch hardly ever falls right between them. Hardly ever is not never: with millions of operations, or with several cores, the fault appears. In threads in C you saw it: 1,550,167 sums out of 2,000,000 in a single attempt.

What if each thread sold two tickets? With more steps there are many more interleavings, and the final seats can go from 1 (all four sales counted) to 3 (only two).

Would seats-- do? No. In C, seats-- is also translated into read, subtract and write. Writing it on one line does not make it atomic.

Try it yourself

• With seats = 1 and both threads doing if (seats > 0) seats = seats - 1;, can seats end at −1? Find the interleaving.
• How many interleavings are there if A has 3 steps and B has 2?

Problem 2: a semaphore with its queue

Statement. Three processes, P1, P2 and P3, use a semaphore S initialised to 1 to protect a critical section (wait(S) on entry and signal(S) on exit). They run in this order: P1 wait, P2 wait, P3 wait, P1 signal, P2 signal, P3 signal. Trace the value of S, who is in the critical section and the queue of blocked processes after each operation.

The idea

With the theory’s definition, wait only subtracts if there is a permit (S > 0); otherwise the process blocks in the queue and S stays at 0. signal does the opposite: if someone is blocked, it hands them the permit directly (wakes them and they go in) and S does not change; only if the queue is empty does S go up.

Step by step

Step	Operation	S	In the critical section	Blocked on S
1	P1 wait	0	P1	—
2	P2 wait	0	P1	P2
3	P3 wait	0	P1	P2, P3
4	P1 signal	0	P2	P3
5	P2 signal	0	P3	—
6	P3 signal	1	—	—

Check

• At no point are there two processes in the critical section: mutual exclusion holds.
• At the end S goes back to 1, its initial value: as many waits as signals, and nobody blocked.
• The queue is FIFO: P2 goes in before P3 because it blocked earlier.

Questions you might ask

Why does P1’s signal not raise S to 1? Because someone is waiting. If it raised S, the permit would be free and another process arriving could jump ahead of P2. Handing it over directly respects the queue order.

And with the negative-counter definition? S would be 0, −1, −2, −1, 0 and 1: the negative value counts the blocked ones. The trace of who is inside would be the same.

What if P1 forgets the signal? P2 and P3 stay blocked forever: it is not a deadlock between several, but it has the same effect. It is the most common mistake with semaphores and mutexes.

And if someone does two signals? S would end at 2 and, next time, two processes could be in the critical section at once. A semaphore used as a mutex must always be between 0 and 1.

Try it yourself

• Repeat the trace with S initialised to 2. How many processes are inside at the same time at most?
• Change the order to P1 wait, P1 signal, P2 wait, P3 wait, P2 signal, P3 signal. Does anyone block?

Problem 3: the bounded buffer

Statement. Spotify downloads songs (producer) and plays them (consumer) through a 2-slot buffer, with the semaphores empty = 2, full = 0 and mutex = 1. The producer does wait(empty); wait(mutex); put; signal(mutex); signal(full); and the consumer wait(full); wait(mutex); take; signal(mutex); signal(empty);. Trace empty, full and the items in the buffer for the sequence: produce, produce, produce, consume, consume, consume, consume.

The idea

empty counts free slots and full, items. The producer blocks in wait(empty) if the buffer is full and the consumer in wait(full) if it is empty. The mutex only protects the instant of putting or taking; in this trace it never blocks anyone, so we leave it out of the table.

Step by step

Operation	empty	full	Buffer	What happens
produce	1	1	1	puts a song
produce	0	2	2	puts another: the buffer is full
produce	0	2	2	blocks in wait(empty)
consume	0	2	2	takes a song; its signal(empty) wakes the producer, which puts its own and does signal(full)
consume	1	1	1	takes one
consume	2	0	0	takes the last: the buffer is empty
consume	2	0	0	blocks in wait(full)

Check

• At every moment empty + full = 2 (the buffer size), except while someone is halfway through. In this trace it holds in every row.
• 3 songs have been produced and 3 consumed: the fourth consumer has nothing to take and blocks.
• The buffer never goes above 2 or below 0: the semaphores do their job.

Questions you might ask

Why does empty stay at 0 in row 4? Because the consumer’s signal does not raise empty: it wakes the blocked producer, which immediately fills the slot that has just become free. Slot freed and filled again, buffer back at 2.

What is the mutex for, then? So that producer and consumer do not touch the buffer indices (where to put and where to take) at the same time. Without it, even if empty and full are right, two simultaneous operations could write into the same slot.

Does the order of the producer’s two waits matter? Hugely. If it does wait(mutex) before wait(empty) and the buffer is full, it blocks holding the mutex and the consumer cannot get in to empty it: deadlock.

What changes if the buffer had 3 slots? Only the initial value of empty: with 3, the third produce would not block.

Try it yourself

• Trace the sequence consume, produce, produce with the buffer empty at the start. Who blocks and who wakes them?
• What initial value of empty makes the buffer work as a mutex between producer and consumer?

Problem 4: an exercise in the exam format

In the written part of the IC2 exam, concurrency appears in reasoning questions: what can happen with a given piece of code, why it fails or how to fix it with a mutex or a semaphore. The reasoning is marked, not just the answer. This exercise is original and written in that format.

Exercise. Three threads share the semaphores S1 = 0 and S2 = 0:

Thread A:  print("upload");   signal(S1);
Thread B:  wait(S1);  print("compile");  signal(S2);
Thread C:  wait(S2);  print("submit");

a) What can the program print? Justify it. b) What if S1 started at 1? c) What would happen if thread A forgot the signal(S1)?

The idea

A semaphore initialised to 0 does not protect a critical section: it is used to order. wait(S) with S = 0 forces you to wait until someone does signal(S). So you have to look at what waits for what: B waits for A (through S1) and C waits for B (through S2).

Step by step

a) Whatever order the scheduler starts the threads in:

• C cannot print until someone does signal(S2), and only B does that, after printing «compile».
• B cannot print until someone does signal(S1), and only A does that, after printing «upload».
• A waits for nobody.

The only possible output is upload, compile, submit. The semaphores turn three concurrent threads into an ordered chain.

b) With S1 = 1, B can pass its wait(S1) without waiting for A. The possible outputs are: upload, compile, submit; compile, upload, submit; and compile, submit, upload. «submit» still always comes after «compile», because S2 still starts at 0. Also, when A does its signal, S1 will be left at 1 (nobody waits for it): a spare permit.

c) If A does not do signal(S1), B stays blocked forever in wait(S1) and C in wait(S2). Only «upload» is printed and the program does not finish.

Check and how it is marked

• For each output you propose, check that no thread has passed a wait without an earlier signal (or an initial permit).
• To rule out an output, it is enough to find the wait that prevents it: «submit» before «compile» is impossible because C needs B’s signal(S2).

Marking values identifying what each semaphore is for (ordering, not protecting), justifying each output with the waits and signals and seeing the consequence of the forgotten signal. A list of outputs without justification is worth little.

Try it yourself

• What initial values do you need in S1 and S2 for the order to be submit, compile, upload? Which waits and signals would you move?
• Add a thread D that prints «notify» after «upload» but without waiting for «compile». Which new semaphore do you need?

Common mistakes in this practice

• Reasoning with lines of code and not with machine steps. A race only shows when each operation is split into read, operate and write.
• Mixing the two semaphore definitions (with and without negative values) in the same exercise.
• Raising the semaphore and also waking a blocked process in the same signal.
• Swapping the waits of the bounded buffer: first the counter, then the mutex.
• Forgetting a signal in some path of the code: those waiting never wake up.
• Confusing protecting with ordering: a semaphore at 1 protects a critical section; one at 0 orders threads.

Check it with Python

This program counts the 20 interleavings of Problem 1 by running each thread’s three steps, and traces the semaphore of Problem 2 and the buffer of Problem 3 with the theory’s definition. Do it by hand first.

# Concurrency on paper: every interleaving of two threads that sell one ticket each,
# and the trace of a semaphore with its queue of blocked processes.
from itertools import combinations

# Each thread does seats = seats - 1 in three steps: read into its register, subtract and write.
def run(order):                           # order = list of "A"/"B": who takes the next step
    seats, reg, step = 5, {"A": None, "B": None}, {"A": 0, "B": 0}
    for h in order:
        if step[h] == 0: reg[h] = seats           # read
        elif step[h] == 1: reg[h] = reg[h] - 1    # subtract (in its register)
        else: seats = reg[h]                      # write
        step[h] += 1
    return seats

finals = {}
for pos in combinations(range(6), 3):     # in which 3 of the 6 steps A acts
    order = ["A" if i in pos else "B" for i in range(6)]
    finals.setdefault(run(order), []).append("".join(order))
for v, ords in sorted(finals.items()):
    print(f"final seats {v}: {len(ords)} interleavings, for example {ords[0]}")
print("total interleavings:", sum(len(o) for o in finals.values()))

# Semaphore S = 1 used as a mutex by three processes, with the theory's definition:
# wait() subtracts if S > 0 and otherwise blocks; signal() wakes the first in the queue and, if there is nobody, adds.
S, queue, inside = 1, [], []
steps = [("P1", "wait"), ("P2", "wait"), ("P3", "wait"), ("P1", "signal"), ("P2", "signal"), ("P3", "signal")]
print("\nstep  operation      S  inside  blocked")
for i, (p, op) in enumerate(steps, 1):
    if op == "wait":
        if S > 0: S -= 1; inside.append(p)      # there is a permit: it takes it and goes in
        else: queue.append(p)                   # there is none: it blocks in the semaphore's queue
    else:
        inside.remove(p)
        if queue: inside.append(queue.pop(0))   # hands the permit to the first one waiting (S does not change)
        else: S += 1                            # nobody is waiting: the permit goes back to the semaphore
    print(f"{i:>4}  {p} {op:<7}  {S:>3}  {', '.join(inside) or '-':>6}  {', '.join(queue) or '-'}")

# Producer-consumer with a 2-slot buffer: empty = 2, full = 0 (mutex apart, always free here)
empty, full, buf, blocked = 2, 0, 0, []
ops = ["prod", "prod", "prod", "cons", "cons", "cons", "cons"]
print("\noperation   empty    full  items  what happens")
for op in ops:
    if op == "prod":
        if empty > 0: empty -= 1; buf += 1; full += 1; what = "puts an item"
        else: blocked.append("prod"); what = "blocks in wait(empty)"
    else:
        if full > 0:
            full -= 1; buf -= 1; what = "takes an item"
            if blocked: blocked.pop(0); buf += 1; full += 1; what += " and wakes the producer, which puts its own"
            else: empty += 1
        else: blocked.append("cons"); what = "blocks in wait(full)"
    print(f"{op:<9}  {empty:>6}  {full:>6}  {buf:>5}  {what}")

Output (run once):

final seats 3: 2 interleavings, for example AAABBB
final seats 4: 18 interleavings, for example AABABB
total interleavings: 20

step  operation      S  inside  blocked
   1  P1 wait       0      P1  -
   2  P2 wait       0      P1  P2
   3  P3 wait       0      P1  P2, P3
   4  P1 signal     0      P2  P3
   5  P2 signal     0      P3  -
   6  P3 signal     1       -  -

operation   empty    full  items  what happens
prod            1       1      1  puts an item
prod            0       2      2  puts an item
prod            0       2      2  blocks in wait(empty)
cons            0       2      2  takes an item and wakes the producer, which puts its own
cons            1       1      1  takes an item
cons            2       0      0  takes an item
cons            2       0      0  blocks in wait(full)

Things to notice:

1. combinations(range(6), 3) generates the 20 ways of sharing out the 6 positions: 2 give 3 seats and 18 give 4, as in the problem.
2. In the semaphore, the S column never goes below 0: the blocked processes are in queue, not in the counter.
3. In the signal, inside.append(queue.pop(0)) hands the permit to the first in the queue without touching S; only the last signal, with the queue empty, raises it to 1.
4. In the buffer, the fourth row is the woken producer: the consumer takes, the producer puts and the counters stay as before.

Summary

• Split each operation into its atomic steps: the race is in how they mix.
• To know the possible results, look at when each thread reads relative to when the other writes.
• With the theory’s definition, wait subtracts or blocks and signal wakes or adds; S is never negative.
• In the bounded buffer, empty + full is the buffer size; the waits go counter first, then mutex.
• A semaphore at 0 orders threads: the output is decided by the signals, not by the scheduler.
• Always check that nobody passes a wait without a permit and that the semaphores end with consistent values.

Checklist: have you practised it?

• Have you done the four problems on paper before reading the step by step?
• Can you count the interleavings of two threads and say which ones fail?
• Can you trace a semaphore with its queue without S going negative?
• Do you know why the order of the bounded buffer’s waits matters?
• Have you checked the problems with the Python program?
• Have you tried the «Try it yourself» tasks without looking at the theory?

If you answered yes to almost everything, you are ready for the concurrency and synchronization exercises, with a test on the whole topic, step-by-step traces and essay questions. See you there!

Next step: exercisesConcurrency and synchronization — exam-style exercises with race conditions, semaphores step by step and the usual milk (and a Peterson that won’t let you in)

Did this article help you? Here is how you can support SergioLearns →