Concurrency 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)
In my first mock exam for this block I came across a test-and-set question and answered without thinking that it “returns true if it manages to get in”. It was exactly the opposite: it returns the old value, and true means someone is inside. Since then, in concurrency, I read every definition twice before ticking anything.
That is what this article is for: practising with exam-like questions until the definitions come out on their own. If you haven’t read the theory yet, start with concurrency and synchronization: nothing is explained from scratch here, although every question comes with its explanation. And if you first want to see the traces solved step by step, there is the concurrency guided practice.
Table of Contents
How to use this article
- Do the test without looking at the theory. Each question has its own “Check” button, so you see the explanation right when you need it.
- Multiple-answer questions subtract, like in the exam: every wrong option you tick takes marks away. If you are unsure about one, ask yourself whether you would really tick it in the exam.
- Do the traces on paper. Before filling in the boxes, write down the value of the semaphore and the state of each process step by step on a sheet.
- Write the long answers in full and then compare them with the model answer and the list of what the marker looks for. At the end you have the cheat sheet for revision.
Test: concurrency, critical section and synchronisation
Thirty questions in every exam format: single choice, multiple choice that subtracts, true or false, gaps, matching, ordering and short answer. They cover the whole topic, from the definition of concurrency to the philosophers.
Your laptop has a single core and you have onedrive, the campus site and spotify open. Which sentence is correct?
- The three processes are concurrent even though two of their instructions never run at the same instant
- There is no concurrency because there is only one core
- There is parallelism, because all three move forward at the same time
- There is only concurrency if the three processes share data
Solution
Answer: The three processes are concurrent even though two of their instructions never run at the same instant
Concurrency is the simultaneous existence of several processes in execution. It does not imply simultaneous execution: with one core, the processes interleave.
Concurrency, parallelism and distributed computing. True or false:
- Parallelism is a particular case of concurrency.
- If two processes are concurrent, they are running on two different processors.
- Parallelism needs several processors (or cores).
- Distributed computing is concurrency on a single very fast processor.
Solution
- T — Parallelism is a particular case of concurrency.
- F — If two processes are concurrent, they are running on two different processors.
- T — Parallelism needs several processors (or cores).
- F — Distributed computing is concurrency on a single very fast processor.
All parallelism is concurrency, but not the other way round. Parallelism = simultaneous execution on several processors; if those processors are in different machines joined by a network, we talk about distributed computing.
Fill in the missing word:
When several processes exist at the same time we talk about ____. If they also run at the same time on several processors, it is ____. And if those processors are spread across a ____, the computing is ____.
Words:
- network
- multiprogramming
- concurrency
- distributed
- cache
- sequential
- parallelism
Solution
When several processes exist at the same time we talk about concurrency. If they also run at the same time on several processors, it is parallelism. And if those processors are spread across a network, the computing is distributed.
From most general to most specific: concurrency → parallelism → distributed computing (parallelism over a network).
Which mechanisms can a programmer use to express concurrency in code?
- Calling a threads API, such as pthreads
- Concurrent objects provided by the language
- Concurrent statements of the language itself
- Declaring the variables as global
- Increasing the cache size
- Storing the data in a shared file
Solution
Answer: Calling a threads API, such as pthreads · Concurrent objects provided by the language · Concurrent statements of the language itself
Three ways: an API (pthreads), concurrent objects (Java, C++) and concurrent statements (Ada, Go…).
What is concurrent programming for?
- Describing in a natural way real-world activities that happen at the same time
- Marking pieces of code that can run in parallel to use several processors
- Writing certain algorithms more easily
- Making the program always give the same result on every run
- Not having to protect shared data
- Having more input and output devices
Solution
Answer: Describing in a natural way real-world activities that happen at the same time · Marking pieces of code that can run in parallel to use several processors · Writing certain algorithms more easily
Expressing the real world better, using several processors and simplifying some algorithms. The price: results that can depend on the interleaving.
Why is a concurrency bug so hard to reproduce when debugging?
- Because the result depends on how the threads’ instructions interleave, and that interleaving changes from one run to the next
- Because the compiler removes shared variables
- Because threads cannot be debugged with a debugger
- Because it only happens on single-core computers
Solution
Answer: Because the result depends on how the threads’ instructions interleave, and that interleaving changes from one run to the next
A concurrent program has to work with every possible interleaving; testing it ten times and getting the right result proves nothing.
What is the situation called in which a program’s result depends on the order in which threads access shared data?
Solution
Answer: Race condition
It is a race condition: two threads “race” towards the same data and whoever writes last wins.
visits is 10 and two threads run visits = visits + 1 (read, add, write). The scheduler does: T1 reads, T2 reads, T1 adds, T2 adds, T1 writes, T2 writes. What is visits at the end?
- 11
- 12
- 10
- It depends on the number of cores
Solution
Answer: 11
T1: 10 → 11. T2 also read 10 before T1 wrote: 10 → 11. The second write overwrites the 11 with another 11. One update is lost.
Put in order what the CPU does to run counter = counter + 1:
- Store the register in counter’s memory location
- Load the value of counter from memory into a register
- Add 1 to the register
Solution
Correct order:
- Load the value of counter from memory into a register
- Add 1 to the register
- Store the register in counter’s memory location
Read (lw), add (addi) and write (sw). If the scheduler preempts the thread between the first and the last step, another thread can read an old value.
What is a critical section?
- The piece of code of a process or thread where it accesses data it shares with others
- The part of the operating system that runs in kernel mode
- Any infinite loop in a program
- The code that uses the most CPU time
Solution
Answer: The piece of code of a process or thread where it accesses data it shares with others
Critical section: a segment of code where shared data is accessed. Basic requirement: mutual exclusion, never more than one process or thread inside.
Which three conditions must a solution to the critical-section problem satisfy?
- Mutual exclusion
- Progress
- Bounded waiting
- Busy waiting
- Priority for the shortest process
- Deadlock
Solution
Answer: Mutual exclusion · Progress · Bounded waiting
Mutual exclusion (at most one inside), progress (if it is free, the decision is made soon and only among those who want to enter) and bounded waiting (nobody cuts in front of you without limit).
Match each requirement with its meaning:
| Mutual exclusion | |
| Progress | |
| Bounded waiting |
Definitions:
- If nobody is inside and someone wants to enter, only those interested decide, and in finite time
- There is a maximum number of times others can enter before a thread that has already asked
- There is never more than one thread inside the critical section
- The thread that enters first leaves last
Solution
- Mutual exclusion → There is never more than one thread inside the critical section
- Progress → If nobody is inside and someone wants to enter, only those interested decide, and in finite time
- Bounded waiting → There is a maximum number of times others can enter before a thread that has already asked
Mutual exclusion protects the data; progress and bounded waiting stop anyone from waiting forever.
Protecting the critical section by disabling interrupts. True or false:
- While a process is in its critical section, no other process in the system can make progress on that CPU.
- It works just as well on a multiprocessor.
- It guarantees bounded waiting.
- It stops the timer from preempting the process while it touches the shared data.
Solution
- T — While a process is in its critical section, no other process in the system can make progress on that CPU.
- F — It works just as well on a multiprocessor.
- F — It guarantees bounded waiting.
- T — It stops the timer from preempting the process while it touches the shared data.
Without interrupts there is no preemption, so on a single processor there is mutual exclusion. But it freezes all concurrency, it doesn’t work with several processors (each has its own interrupts) and it doesn’t guarantee bounded waiting.
Match each instruction or idea with its description:
| Atomic instruction | |
| Test-and-set | |
| Compare-and-swap | |
| LOCK BTS |
Definitions:
- Sets the variable to true and returns the value it had before
- If the variable holds the expected value, gives it a new value and returns true
- The x86 version: the CPU keeps the bus while it does the test-and-set
- It runs to the end without anything interrupting it
- Disables the interrupts of every processor at once
Solution
- Atomic instruction → It runs to the end without anything interrupting it
- Test-and-set → Sets the variable to true and returns the value it had before
- Compare-and-swap → If the variable holds the expected value, gives it a new value and returns true
- LOCK BTS → The x86 version: the CPU keeps the bus while it does the test-and-set
All three are help from the hardware: they read and modify a memory cell in a single indivisible step. IBM already had an atomic SWAP in the 1960s; MIPS and ARM use the LL/SC pair.
A thread runs while (test_and_set(busy)) {} and at that moment busy is true. What happens?
- The call returns true, busy stays true and the thread goes round again waiting
- The call returns false and the thread enters the critical section
- The call sets busy to false so the next one can enter
- The thread blocks and frees the CPU
Solution
Answer: The call returns true, busy stays true and the thread goes round again waiting
test-and-set returns the old value. If it was true, someone is inside and the loop keeps spinning (busy waiting). Only whoever gets false enters.
A semaphore is 0 and there are two blocked processes in its queue. Another process calls signal. What happens, with the definition from the notes?
- One of the two blocked processes wakes up and the semaphore is still 0
- The semaphore becomes 1 and both stay blocked
- Both wake up and the semaphore becomes 1
- The process calling signal blocks
Solution
Answer: One of the two blocked processes wakes up and the semaphore is still 0
signal wakes a process if there is one waiting; only if the queue is empty does it add 1. That is why the value doesn’t go up when someone was asleep.
In the flat, each flatmate does: if there is no milk and no note, leave a note, buy and remove the note. What can go wrong?
- Both check, see there is no note and both buy, because the context switch comes before the note is left
- Nobody ever buys
- One person buys twice in a row
- Nothing: the note always solves it
Solution
Answer: Both check, see there is no note and both buy, because the context switch comes before the note is left
Checking the note and leaving it are two separate steps. If both check before either leaves it, both buy: the “solution” works almost always and fails at the worst moment.
Now each one leaves THEIR note (noteA, noteB) before checking the other’s. What is the worst case?
- Both leave their note, each sees the other’s and nobody buys
- Both buy
- One waits forever in a loop
- The milk gets bought twice in the afternoon
Solution
Answer: Both leave their note, each sees the other’s and nobody buys
Mutual exclusion is solved, but if both leave their note at the same time, both back off and the fridge stays empty.
Solution with a shared turn variable (while (turn != my_number) {}). True or false:
- It guarantees mutual exclusion between the two processes.
- It forces the processes to enter alternately, whether they want to or not.
- It satisfies the progress requirement.
- While it waits, the process uses CPU spinning in the loop.
Solution
- T — It guarantees mutual exclusion between the two processes.
- T — It forces the processes to enter alternately, whether they want to or not.
- F — It satisfies the progress requirement.
- T — While it waits, the process uses CPU spinning in the loop.
If it is process 2’s turn but it doesn’t want to enter, process 1 cannot enter again even though the section is free: strict alternation, progress fails.
About Peterson’s algorithm for two processes:
- It satisfies mutual exclusion, progress and bounded waiting
- It uses two “I want to enter” variables and a turn variable, all shared
- A modern processor or compiler that reorders reads and writes can break it
- It works unchanged for any number of processes
- It uses no CPU while waiting
- It needs interrupts to be disabled
Solution
Answer: It satisfies mutual exclusion, progress and bounded waiting · It uses two “I want to enter” variables and a turn variable, all shared · A modern processor or compiler that reorders reads and writes can break it
Peterson combines the named note (wants1, wants2) with the turn variable. It is correct in theory, but only for two processes, with busy waiting and sensitive to instruction reordering.
With Peterson, both threads set their wants to true. Then thread 1 writes turn = 2 and right after that thread 2 writes turn = 1. Who gets in first?
- Thread 1
- Thread 2
- Both at the same time
- Neither: both block
Solution
Answer: Thread 1
Thread 2 waits while wants1 && turn == 1, and both are true. Thread 1 waits while wants2 && turn == 2, and turn is 1: it gets in. Whoever writes turn last is the one who gives way.
What is true about a mutex (lock)?
- It has two states, free and acquired, and starts free
- If a thread calls lock() and the mutex is already acquired, that thread blocks until it gets it
- On unlock(), if threads are waiting, one of them acquires it and is unblocked
- Its operations are lock() and signal()
- lock() never blocks the calling thread
- Each thread has its own mutex for its critical section
Solution
Answer: It has two states, free and acquired, and starts free · If a thread calls lock() and the mutex is already acquired, that thread blocks until it gets it · On unlock(), if threads are waiting, one of them acquires it and is unblocked
mutex = mutual exclusion. lock() acquires (or blocks), unlock() releases (and wakes one up). Both operations are atomic.
About condition variables:
- They are always associated with a mutex
- wait() blocks the thread and, while it sleeps, releases the mutex
- If nobody is waiting, signal() does nothing
- broadcast() wakes up every thread in the queue
- A signal() with nobody in the queue is saved for the next wait()
- They replace the mutex: with them, lock() is no longer needed
Solution
Answer: They are always associated with a mutex · wait() blocks the thread and, while it sleeps, releases the mutex · If nobody is waiting, signal() does nothing · broadcast() wakes up every thread in the queue
A condition variable is a queue of threads waiting for a condition inside a critical section. On waking up, the thread reacquires the mutex before carrying on.
P signals a condition Q is waiting on. Match:
| Hoare style | |
| Mesa style | |
| broadcast | |
| FIFO unblocking |
Definitions:
- The one that has waited longest wakes up
- Q stays asleep until the next context switch
- Everyone waiting wakes up and they compete for the mutex
- Q becomes ready, but waits for P to release the mutex
- Q carries on straight away and P is left without the mutex until Q finishes
Solution
- Hoare style → Q carries on straight away and P is left without the mutex until Q finishes
- Mesa style → Q becomes ready, but waits for P to release the mutex
- broadcast → Everyone waiting wakes up and they compete for the mutex
- FIFO unblocking → The one that has waited longest wakes up
Mesa style is the most used today. When several are waiting, the choice can be FIFO, by priority or random; broadcast wakes them all.
Why do we write while (condition) cond.wait(); and not if (condition) cond.wait();?
- Because with Mesa style, by the time the thread has the mutex again the condition may have changed again, so it must be checked again
- Because if cannot be used inside a critical section
- Because the while does busy waiting, which is faster
- It makes no difference: they are equivalent
Solution
Answer: Because with Mesa style, by the time the thread has the mutex again the condition may have changed again, so it must be checked again
Between the signal and the moment the woken thread gets the mutex back, another thread can get in and fill (or empty) the buffer again. The while checks again.
Synchronisation tools. Fill in:
____ were proposed by Dijkstra in 1965. Hoare’s ____ (1972) give us the mutex and condition variables. ____ and mailboxes don’t need ____ memory.
Words:
- monitors
- interrupts
- private
- registers
- shared
- Semaphores
- Channels
Solution
Semaphores were proposed by Dijkstra in 1965. Hoare’s monitors (1972) give us the mutex and condition variables. Channels and mailboxes don’t need shared memory.
With shared memory: semaphores, conditional critical regions and monitors. Without shared memory: channels, mailboxes, and promises and futures.
In the bounded-buffer problem with N slots and a counter count, when must the producer wait?
- When count == N
- When count == 0
- When count < N
- Never: the consumer will empty the buffer anyway
Solution
Answer: When count == N
Producer: waits if it is full (count == N). Consumer: waits if it is empty (count == 0).
count is 4. A producer does count++ and a consumer count-- at the same time, unprotected (each one reads, operates and writes). Which values can count end with?
- 4
- 5
- 3
- 6
- 2
Solution
Answer: 4 · 5 · 3
If both read 4 before either writes, whoever writes last wins: 5 or 3. Only the order “one whole, then the other” gives the correct 4.
Readers and writers on a database. True or false:
- Several readers can read at the same time.
- A writer can write while there are readers inside, as long as they don’t touch the same row.
- If readers have priority, a writer may wait indefinitely.
- If writers have priority, every risk of starvation disappears.
Solution
- T — Several readers can read at the same time.
- F — A writer can write while there are readers inside, as long as they don’t touch the same row.
- T — If readers have priority, a writer may wait indefinitely.
- F — If writers have priority, every risk of starvation disappears.
Several readers or a single writer, never mixed. Priority to readers → writers starve; priority to writers → readers starve.
In the five philosophers problem, which measures avoid deadlock?
- Even philosophers pick up one chopstick first and odd ones the other
- Letting at most four philosophers try to pick up chopsticks at the same time
- Picking up both chopsticks in a single atomic operation
- Everyone picks up their left chopstick first
- They wait spinning in a while until a chopstick is free
Solution
Answer: Even philosophers pick up one chopstick first and odd ones the other · Letting at most four philosophers try to pick up chopsticks at the same time · Picking up both chopsticks in a single atomic operation
If all five pick up their left chopstick at the same time, each one waits for the one their neighbour holds: deadlock. The three solutions from the notes break that circle.
If you get several of the milk solutions wrong, review which requirement each attempt breaks. One note: mutual exclusion. Named notes: progress. Turn variable: progress (strict alternation).
Step-by-step traces: races, mutexes and semaphores
Here you follow the execution instruction by instruction, as in the calculation questions. The rules for every table:
- A semaphore never drops below 0.
waitsubtracts 1 if it can; if it is 0, the process blocks in the queue. signalwakes one up if someone is in the queue (FIFO), and then the value does not change; if nobody is there, it adds 1.- For states, write a single word: inside, outside, blocked, printing or ready, depending on the table. In Peterson, enters or waits. Capital letters don’t matter.
The class dinner kitty, in a shared spreadsheet, holds 200. Thread 1 adds 30 and thread 2 takes out 80 for a payment; each one reads, operates and writes, and the scheduler alternates one step each. Fill in the private registers (reg1, reg2) and the balance in memory after each step:
| Step | Thread | Instruction | reg1 | reg2 | balance |
|---|---|---|---|---|---|
| 1 | 1 | read | – | ||
| 2 | 2 | read | |||
| 3 | 1 | add 30 | |||
| 4 | 2 | subtract 80 | |||
| 5 | 1 | write | |||
| 6 | 2 | write |
Solution
| Step | Thread | Instruction | reg1 | reg2 | balance |
|---|---|---|---|---|---|
| 1 | 1 | read | 200 | – | 200 |
| 2 | 2 | read | 200 | 200 | 200 |
| 3 | 1 | add 30 | 230 | 200 | 200 |
| 4 | 2 | subtract 80 | 230 | 120 | 200 |
| 5 | 1 | write | 230 | 120 | 230 |
| 6 | 2 | write | 230 | 120 | 120 |
Both threads read 200 before anyone writes. Thread 1 writes 230, but thread 2 then writes its 120 on top of it: the 30 that was added is lost. The correct result was 200 + 30 − 80 = 150, and we get 120.
Three processes A, B and C protect their critical section with a semaphore m that starts at 1 (a mutex). Fill in the value of m and the state of each process (inside, blocked or outside) after each operation. The queue is FIFO:
| Step | Operation | m | A | B | C |
|---|---|---|---|---|---|
| 1 | A: wait(m) | ||||
| 2 | B: wait(m) | ||||
| 3 | C: wait(m) | ||||
| 4 | A: signal(m) | ||||
| 5 | B: signal(m) | ||||
| 6 | C: signal(m) |
Solution
| Step | Operation | m | A | B | C |
|---|---|---|---|---|---|
| 1 | A: wait(m) | 0 | inside | outside | outside |
| 2 | B: wait(m) | 0 | inside | blocked | outside |
| 3 | C: wait(m) | 0 | inside | blocked | blocked |
| 4 | A: signal(m) | 0 | outside | inside | blocked |
| 5 | B: signal(m) | 0 | outside | outside | inside |
| 6 | C: signal(m) | 1 | outside | outside | outside |
m drops to 0 when A enters, and B and C queue up. When A signals, m does NOT go up: the permit goes straight to B (first in the queue). The same happens with B → C. Only the last signal, with nobody waiting, brings m back to 1.
The lab has 2 printers and a semaphore printers = 2. Four processes request a printer with wait and return it with signal. Fill in the value of the semaphore and the state of each process (printing, blocked or outside). The queue is FIFO:
| Step | Operation | printers | A | B | C | D |
|---|---|---|---|---|---|---|
| 1 | A: wait | |||||
| 2 | B: wait | |||||
| 3 | C: wait | |||||
| 4 | B: signal | |||||
| 5 | D: wait | |||||
| 6 | A: signal | |||||
| 7 | C: signal | |||||
| 8 | D: signal |
Solution
| Step | Operation | printers | A | B | C | D |
|---|---|---|---|---|---|---|
| 1 | A: wait | 1 | printing | outside | outside | outside |
| 2 | B: wait | 0 | printing | printing | outside | outside |
| 3 | C: wait | 0 | printing | printing | blocked | outside |
| 4 | B: signal | 0 | printing | outside | printing | outside |
| 5 | D: wait | 0 | printing | outside | printing | blocked |
| 6 | A: signal | 0 | outside | outside | printing | printing |
| 7 | C: signal | 1 | outside | outside | outside | printing |
| 8 | D: signal | 2 | outside | outside | outside | outside |
A counting semaphore counts free printers. A and B take both (2 → 0); C and then D block. Each signal with someone waiting hands the printer over without touching the value; at the end, with nobody waiting, it climbs back to 1 and 2.
Spotify with a 2-slot buffer: semaphores empty = 2 and full = 0. D (downloader) puts a chunk and P (player) takes one; whoever is woken up by a signal already has its permit and completes its operation on its next turn. Fill in, after each turn, the chunks in the buffer, empty, full and the state of D and P (ready or blocked):
| Turn | Who | Action | Chunks | empty | full | D | P |
|---|---|---|---|---|---|---|---|
| 1 | D | puts | |||||
| 2 | D | puts | |||||
| 3 | D | blocks | |||||
| 4 | P | takes | |||||
| 5 | P | takes | |||||
| 6 | P | blocks | |||||
| 7 | D | puts |
Solution
| Turn | Who | Action | Chunks | empty | full | D | P |
|---|---|---|---|---|---|---|---|
| 1 | D | puts | 1 | 1 | 1 | ready | ready |
| 2 | D | puts | 2 | 0 | 2 | ready | ready |
| 3 | D | blocks | 2 | 0 | 2 | blocked | ready |
| 4 | P | takes | 1 | 0 | 1 | ready | ready |
| 5 | P | takes | 0 | 1 | 0 | ready | ready |
| 6 | P | blocks | 0 | 1 | 0 | ready | blocked |
| 7 | D | puts | 1 | 1 | 0 | ready | ready |
Turn 3: no empty slots, D blocks. Turn 4: P takes a chunk and its signal(empty) wakes D, so empty stays at 0. Turn 6: the buffer is empty and P blocks. Turn 7: D puts its chunk without waiting (it already had the permit) and its signal(full) wakes P, so full stays at 0.
Peterson’s algorithm, but this time thread 2 starts. Fill in wants1, wants2 and turn after each instruction and, in the while rows, whether the thread enters or waits (enters / waits). Initially wants1 = wants2 = false and turn = 1:
| Step | Thread | Instruction | wants1 | wants2 | turn | Result |
|---|---|---|---|---|---|---|
| 1 | 2 | wants2 = true | – | |||
| 2 | 2 | turn = 1 | – | |||
| 3 | 2 | while (wants1 && turn == 1) | ||||
| 4 | 1 | wants1 = true | – | |||
| 5 | 1 | turn = 2 | – | |||
| 6 | 1 | while (wants2 && turn == 2) | ||||
| 7 | 2 | wants2 = false | – | |||
| 8 | 1 | while (wants2 && turn == 2) |
Solution
| Step | Thread | Instruction | wants1 | wants2 | turn | Result |
|---|---|---|---|---|---|---|
| 1 | 2 | wants2 = true | false | true | 1 | – |
| 2 | 2 | turn = 1 | false | true | 1 | – |
| 3 | 2 | while (wants1 && turn == 1) | false | true | 1 | enters |
| 4 | 1 | wants1 = true | true | true | 1 | – |
| 5 | 1 | turn = 2 | true | true | 2 | – |
| 6 | 1 | while (wants2 && turn == 2) | true | true | 2 | waits |
| 7 | 2 | wants2 = false | true | false | 2 | – |
| 8 | 1 | while (wants2 && turn == 2) | true | false | 2 | enters |
Thread 2 finds wants1 = false and goes straight in. Thread 1 raises its hand, gives way (turn = 2) and waits, because thread 2 wants in and it is its turn. As soon as thread 2 sets wants2 = false, thread 1’s condition becomes false and it enters.
Increasing the semaphore on a signal when someone was blocked. If there is a queue, the permit goes straight to the one woken up and the value stays the same: that is why in the mutex trace m is 0 for five steps in a row.
Long-answer questions
Four long questions like the ones in the exam. Write your answer in the box and then compare it with the model answer. There is no automatic mark: you decide whether you covered each point of “what the marker looks for”.
What is a race condition? Explain it with two threads that increment the same counter and say how it is avoided.
Solution
Model answer:
A race condition happens when two or more threads access shared data, at least one of them modifies it, and the result depends on the order in which their instructions interleave.
Example: counter is 7 and two threads do counter = counter + 1. In the CPU that is three steps: read into a register, add and write. If thread 1 reads 7 and loses the CPU before writing, thread 2 also reads 7; both compute 8 and both write 8. One addition is lost: it should be 9.
It is avoided by turning the access to the data into a critical section with mutual exclusion: for example, wrapping the addition with mutex.lock() and mutex.unlock(), or using an atomic instruction. That way the second thread cannot read until the first one has written.
What the marker looks for:
- Definition: shared data, some write, and a result that depends on the interleaving
- The increment is three steps (read, add, write) and is not atomic
- A concrete interleaving that loses an update, with the values
- The fix: a critical section with mutual exclusion (mutex, semaphore or atomic instruction)
What matters is the why: the thread works on a copy in its register and writes a value computed from data that is already stale.
List and explain the three requirements of a solution to the critical-section problem. Then argue whether disabling interrupts is a good solution.
Solution
Model answer:
1. Mutual exclusion: there can never be more than one process or thread running its critical section.
2. Progress: if nobody is in the critical section and there are processes that want to enter, only those processes take part in the decision, and it is made in finite time.
3. Bounded waiting: there is a limit on the number of times other processes can enter before one that has already asked to enter.
Disabling interrupts achieves mutual exclusion on a single processor, because without interrupts nobody preempts the process. But it is not a good general solution: it suspends all the concurrency of the system (hurting those who don’t want to enter), it doesn’t work on multiprocessors (each CPU has its own interrupts and another one can get in) and it doesn’t guarantee bounded waiting.
What the marker looks for:
- The three requirements by their exact names
- A correct definition of each one
- Why disabling interrupts gives mutual exclusion on one processor
- Its three drawbacks: freezes the system, useless on multiprocessors, no bounded waiting
Exams usually ask for the exact names of the requirements: mutual exclusion, progress and bounded waiting.
Compare a mutex and a condition variable: what each one is for, which operations they have and what happens after a signal in Hoare style and in Mesa style.
Solution
Model answer:
A mutex is used to get exclusive access to a resource. It has two states (free and acquired) and two atomic operations: lock() acquires it, or blocks the process if it was already acquired; unlock() releases it and, if processes are waiting, one of them acquires it.
A condition variable is used to wait for a condition to hold inside a critical section. It is always associated with a mutex and manages a queue of processes. Operations: wait() blocks the process and releases the mutex while it sleeps (on waking up it must reacquire it); signal() wakes one from the queue (if nobody is there, it does nothing); broadcast() wakes them all.
After P signals with Q waiting: in Hoare style, Q resumes immediately and P loses the mutex; in Mesa style, Q is unblocked but waits for P to release the mutex. Mesa is the most used, which is why the condition is checked with while and not if.
What the marker looks for:
- What each tool is for (exclusion versus waiting for a condition)
- Mutex operations: lock and unlock, with their effect
- Condition variable operations: wait (releases the mutex), signal and broadcast
- Hoare versus Mesa and the consequence for the while
A tip to keep them apart: the mutex answers “can I get in?”; the condition variable, “does what I’m waiting for hold yet?”.
Bounded-buffer problem: explain which conditions must be respected and how it is solved with a mutex and two condition variables (write the pseudocode for the producer and the consumer).
Solution
Model answer:
Producers and consumers share a FIFO queue of N positions. The producer must not put if the buffer is full (count == N) and the consumer must not take if it is empty (count == 0). Besides, count++ and count– touch shared data: without protection, an interleaving can leave a wrong value.
Producer: mutex.lock(); while (count == N) cprod.wait(); buffer[in] = thing; in = (in + 1) % N; count++; ccons.signal(); mutex.unlock();
Consumer: mutex.lock(); while (count == 0) ccons.wait(); thing = buffer[out]; out = (out + 1) % N; count--; cprod.signal(); mutex.unlock(); consume(thing);
The mutex guarantees that only one of them touches buffer, in, out and count. Each one waits on its own condition variable and tells the other with signal after changing the state. while is used because, with Mesa style, the condition has to be checked again on waking up.
What the marker looks for:
- The two conditions: full (count == N) and empty (count == 0)
- The mutex wraps all access to the buffer, the indices and count
- Each side waits on its own condition and signals the other’s
- while and not if, because of Mesa style
- consume() outside the critical section
consume(thing) goes after unlock(): it touches no shared data and, if it were inside, it would make the producer wait for no reason.
The whole topic in one picture
If you can only review one thing before the exam, make it this map: the problem (shared data and race conditions), the rule (the critical section and its three requirements) and the three families of solutions.
Cheat sheet: concurrency and synchronization
The essentials in 30 seconds
- Concurrency = several processes exist at the same time. Parallelism = they run at the same time on several processors. Distributed = parallelism over a network.
x = x + 1is three steps (read, add, write): a context switch in the middle causes a race condition.- Critical section = code that touches shared data. Requirements: mutual exclusion, progress and bounded waiting.
- Hardware: disabling interrupts (one processor only), test-and-set and compare-and-swap (busy waiting, no bounded waiting).
- Operating system: mutex (lock/unlock), condition variables (wait/signal/broadcast, always with a mutex) and semaphores (counter + queue).
- Classics: bounded buffer, readers and writers, philosophers (deadlock).
If they ask you… / Answer
| If they ask you… | Answer |
|---|---|
| Does concurrency imply simultaneous execution? | No: that is parallelism |
| How is concurrency expressed in code? | API (pthreads), concurrent objects (Java, C++), concurrent statements (Ada, Go) |
| What is concurrent programming for? | Expressing the real world, using several processors, making some algorithms easier |
| What fails with one note? | Mutual exclusion: both buy |
| What fails with named notes? | Progress: maybe nobody buys |
| What fails with the turn variable? | Progress: strict alternation |
| What does Peterson satisfy? | All three requirements (catch: reordering, two processes, busy waiting) |
| Does disabling interrupts work on a multiprocessor? | No, and it doesn’t guarantee bounded waiting either |
| What does test-and-set return? | The old value, after setting it to true |
| What does CAS(M, A, B) return? | True if M = A (and then M ← B); false otherwise |
| What does wait() do on a condition variable? | Blocks and releases the mutex while asleep |
| signal() with nobody in the queue? | Condition variable: nothing. Semaphore: adds 1 |
| Hoare or Mesa? | Hoare: Q runs at once. Mesa: Q waits for P to release the mutex (the usual one) |
| Tools without shared memory? | Channels, mailboxes, promises and futures |
| Priority to readers? | Writers starve (and the other way round) |
| Solutions to the philosophers? | Asymmetric even/odd, at most four asking, take both chopsticks atomically |
Templates
Critical section with a mutex:
mutex.lock(); // critical section mutex.unlock();
Waiting for a condition (Mesa style, hence while):
mutex.lock(); while (!condition) cond.wait(); // sleeps and releases the mutex // … now it holds mutex.unlock();
Bounded buffer with semaphores (empty = N, full = 0, m = 1):
// Producer // Consumer wait(empty); wait(full); wait(m); wait(m); put(thing); thing = take(); signal(m); signal(m); signal(full); signal(empty);
Peterson (process 1; process 2 is symmetric):
wants1 = true;
turn = 2;
while (wants2 && turn == 2) { }
// critical section
wants1 = false;
Symptom / Likely cause
| Symptom | Likely cause |
|---|---|
| The counter ends up lower than expected | Race condition: read-add-write without protection |
| Two processes inside the critical section | Mutual exclusion fails (single note, interrupts on a multiprocessor) |
| Section free and nobody gets in | Progress fails (named notes, turn variable) |
| One process never gets in although the rest progress | Starvation: no bounded waiting, or another group has priority |
| Nobody progresses and everyone waits for someone else | Deadlock (philosophers with the left chopstick) |
| CPU at 100 % while a thread waits | Busy waiting (a while that checks over and over) |
| A thread wakes up and the buffer is still empty | if was used instead of while with Mesa style |
Before handing in, ask yourself
- Did I tell concurrency (existing at the same time) apart from parallelism (running at the same time)?
- Did I write the three requirements by their exact names: mutual exclusion, progress and bounded waiting?
- In the traces, did I check whether anyone was in the queue before adding on a
signal? - Can I say which requirement each solution breaks, and what the catch is for the ones that meet them all?
This wraps up the processes block of IC2. If you want to review, go back to the concurrency and synchronization theory or the CPU scheduling exercises. The next topic is memory management: contiguous memory, segmentation and paging.
Keep goingAll Operating systems articlesDid this article help you? Here is how you can support SergioLearns →
Ready for the exam?IC2 theory mock exam — first midterm, second midterm or the full exam, with your real mark and a review of every mistake (as if you were in the exam room)
