Concurrency and synchronization — theory with a counter that loses uploads, too much milk in the fridge and spotify’s buffer (and the 30 euros a shared spreadsheet swallowed)

Last year I was in charge of the kitty for our class dinner, kept in a OneDrive spreadsheet. It held €200. I recorded a €30 payment that had just come in and, almost at the same time, a classmate subtracted €80 for the restaurant deposit. We both had the sheet open, each of us did the maths on “our” 200 and saved. Result: €120. It should have been 200 + 30 − 80 = 150. Nobody stole the €30: whoever saved second simply wrote over them.

That, with two people and a spreadsheet, is exactly what happens to two threads that touch the same variable. It has a name (a race condition) and it is the reason this whole topic exists. We come from CPU scheduling, where we saw that the scheduler can take the CPU away from a process at any moment. Today we look at what happens when that happens in the middle of an addition, and at the tools that prevent it: the critical section, software and hardware solutions, the mutex, condition variables, semaphores and the three classic problems. At the end you have two Python simulators and, when you are done, the exam-style concurrency exercises.

Our running example is twofold: a student flat for intuition (the fridge and the shared account) and your laptop for the numbers (two onedrive threads counting uploaded files and spotify filling its audio buffer).

Concurrency: existing at the same time is not running at the same time

In everyday language, concurrent means happening at the same time. In computing, there is concurrency when several processes in execution exist simultaneously. Notice the word exist: they have started and not finished, but that does not imply they run at the same time.

With a single core, onedrive, the campus site and spotify are concurrent even though only one of them uses the CPU at each instant: they take turns so quickly that they seem to run together. That is what the scheduler from the previous topic did.

Parallelism is a particular case of concurrency: there is simultaneous execution of instructions on several processors (or cores). And when those processors are in different machines joined by a network, we talk about distributed computing.

Concept	What it means	What it needs
Concurrency	Several processes exist at the same time (started and unfinished)	One core that shares itself out is enough
Parallelism	Several processes run at the same instant	Several processors or cores
Distributed computing	Parallelism across different machines	Several machines joined by a network

How concurrency is written in a program

When we learn to program we learn sequential algorithms: one instruction after another. To say “this can happen at the same time as that” there are three ways:

• An API, such as pthreads in C (creating threads with pthread_create).
• Concurrent objects provided by the language, such as Java or C++ threads.
• Concurrent statements of the language itself, as in Ada or Go.

The course notes use a made-up statement, CONCURRENT { … }, meaning “what is inside may run in any order or at the same time”. The example is breakfast:

void have_breakfast() {
  prepare_ingredients();
  CONCURRENT {           // these three may interleave or run in parallel
    make_coffee();
    heat_toast();
    heat_milk();
  }
  eat();                 // only once all three have finished
}

Nothing forces the coffee to come before the toast: they are three independent activities. What does matter is that eat() waits until all three are done. The picture makes it clear:

What is programming like this good for? Three things:

1. Expressing the real world better, where many things happen at once (breakfast, an app that downloads while it plays).
2. Using several processors: if you mark what can run in parallel, the system can spread it across cores.
3. Writing certain algorithms more easily, such as a cyclic monitor that keeps an eye on several things.

The price is high: a concurrent program must work with every possible interleaving of its instructions. Cooperating threads are non-deterministic and non-reproducible: the same run can go well ninety-nine times and fail on the hundredth. That is why they are so hard to debug unless they are designed carefully.

The problem: shared data

Two threads of the same process share global variables. That is very handy for communicating, but modifying shared data at the same time can give wrong results. Let’s see why with the simplest thing there is: adding 1.

Why uploaded += 1 is not a single operation

onedrive has two threads: one uploads photos and the other uploads notes. Every time one of them finishes a file, it does uploaded = uploaded + 1 on a shared counter. In C it is one line, but the CPU does not add in memory: it needs three instructions.

lw   $t1, uploaded       # 1. read: copy the value from memory into a register
addi $t1, $t1, 1         # 2. add: add in the register (memory does not change)
sw   $t1, uploaded       # 3. write: store the register in memory

Each thread has its own registers (they are saved in its control block on a context switch). So, between step 1 and step 3, the value the thread is going to write lives in a private place nobody else can see.

And there is the hole: if the scheduler preempts the thread after reading and before writing, another thread can read the old value from memory.

A race condition step by step

Suppose uploaded is 7 and both threads finish a file at the same time. The scheduler uses Round Robin with a quantum of two instructions. These are the real data from the first simulator in the Check it with Python section:

Read it column by column. At t = 1 and t = 2, photos reads 7 and computes 8 in its register, but its quantum runs out before it writes. At t = 3, notes reads from memory… a 7, because photos’ 8 is still in a register. Both write 8. Two files were uploaded and the counter only went up by one: 7 + 2 = 9, but we get 8.

This is called a race condition: the result depends on the order in which the threads access the shared data. Whoever writes last wins.

The flat’s shared account: three endings for the same code

The course notes tell it with a bank account. In the flat, the shared account starts at 0; one thread deposits 100 and another withdraws 50:

int balance;               // shared by both threads
main() {
  balance = 0;
  CONCURRENT {
    deposit(100);          // thread 1
    withdraw(50);          // thread 2
  }
}
void deposit(int N)  { balance = balance + N; }   // read, add, write
void withdraw(int N) { balance = balance - N; }   // read, subtract, write

One after the other, the final balance is 0 + 100 − 50 = 50. But depending on how the three steps of each thread interleave, the same code ends with very different numbers:

In interleaving A, thread 2 reads 0 before thread 1 writes its 100, so its subtraction starts from 0 and ends at −50: the deposit vanishes. In interleaving B it is the other way round: the withdrawal is lost and 100 remains. The notes work it out with Round Robin with Q = 2 on the assembly code (thread 2 has four instructions because it loads the 50 into a register) and get −50, like our interleaving A.

This is not just an exam problem. The Therac-25 (1985) was a radiotherapy accelerator where part of the hardware control was replaced by software. Several processes shared variables and accessed them in a non-deterministic order, just like our balance. If the operator edited the prescription at the wrong moment, the machine delivered an overdose. Patients died.

Sharing in small or large blocks

The challenge of concurrency is sharing: many threads sharing resources and data. And the size of the piece you reserve changes things a lot:

If you share in…	Concurrency	Performance	Difficulty	Example
Small blocks	Goes up	Goes up	More complex	1 ms CPU turns; locking one database row
Large blocks	Goes down	Goes down	Easy to implement	1 minute turns; locking the whole table

You will see it straight away with the flat’s fridge: padlocking it is easy, but it leaves everyone waiting.

The critical section

We know where the danger is. Now let’s name it. A critical section is a segment of code where data shared with other processes or threads is accessed. And its rule is: there must never be more than one process or thread inside the critical section at the same time (mutual exclusion).

In the balance example, the critical section is the function that touches balance:

void deposit(int N)  { amount1 = N;  update_balance(amount1); }
void withdraw(int N) { amount2 = -N; update_balance(amount2); }

void update_balance(int amount) {
  balance = balance + amount;    // CRITICAL SECTION: touches the shared data
}

amount1 and amount2 belong to each thread; the problem is only in the line that reads and writes balance. In the breakfast example, the notes mark eat() as the critical section: it is where everything the three threads prepared comes together.

Every thread that shares data has the same shape: it works on its own, asks for permission, touches the data, gives the permission back and carries on on its own.

Everything from here on (notes, Peterson, atomic instructions, mutex, semaphores) is a different way of writing the entry protocol and the exit protocol.

The three requirements

A solution to the critical-section problem must satisfy three requirements, and the exam asks for them by their exact names:

1. Mutual exclusion: there is never more than one process or thread in the critical section.
2. Progress: if no process is in the critical section and some processes 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 ahead of a process that has already asked to enter.

Why do we need all three? Because it is very easy to meet one while breaking another. “Nobody ever gets in” satisfies mutual exclusion beautifully… and fails progress. This table helps you recognise what is failing in each case:

If this fails…	What you see
Mutual exclusion	Two threads inside: corrupted data (8 instead of 9)
Progress	The section is free and still nobody gets in, or processes that don’t even want to enter take part in the decision
Bounded waiting	A thread asks to enter and the others keep cutting in front of it (starvation)

Too much milk: software solutions (and why they fail)

Before the “proper” tools, it is worth looking at the home-made attempts: they show what is hard. The example in the notes is a student flat with a shared fridge (with the warning that computers don’t think like people).

Pepito checks the fridge, there is no milk and he goes to the shop. While he is out, Juanito checks, there is no milk either and he goes too. They come back with two cartons. It is the usual race condition: checking and buying should be a single indivisible action, and here they interleave. The conditions we want are: only one buys and someone buys if needed.

A brute-force solution is the padlock: Pepito locks the fridge, goes shopping and unlocks it when he comes back. It works, but if Juanito only wanted a piece of fruit, he waits an hour. That is the overly large block from the previous table.

Attempt 1: a note

Leave a note before going shopping, don’t go if there is a note, and remove it on return:

if (noMilk) {
  if (noNote) {
    leave_note();        // too late: the other one may have checked already
    buy_milk();
    remove_note();
  }
}

It looks perfect, but the context switch can fall between checking the note and leaving it. Both see “no note”, both leave one and both buy. Mutual exclusion fails, and only rarely: that is worse than having no solution, because you believe it works.

Attempt 2: named notes

Now each one leaves their own note before checking the other’s:

// Thread A                   // Thread B
leave_noteA();                leave_noteB();
if (noNoteB) {                if (noNoteA) {
  if (noMilk) {                 if (noMilk) {
    buy_milk();                   buy_milk();
  }                             }
}                             }
remove_noteA();               remove_noteB();

Now they cannot both buy: whoever buys has seen that the other had no note up. But if both leave their notes at the same time, each one sees the other’s and nobody buys. Empty fridge with the section free: progress fails.

Attempt 3: named notes and a while

We make thread A asymmetric: if it sees B’s note, it waits for B to remove it instead of giving up.

// Thread A                   // Thread B
leave_noteA();                leave_noteB();
while (noteB) { }             if (noNoteA) {
if (noMilk) {                   if (noMilk) {
  buy_milk();                     buy_milk();
}                               }
remove_noteA();               }
                              remove_noteB();

Now it works: only one buys (mutual exclusion), one of them buys (progress) and, if one is buying, the other eventually carries on (bounded waiting). But it has serious drawbacks: it is asymmetric (each thread has different code), it is hard to generalise to many threads and, while A waits, it burns CPU spinning in the while. That is called busy waiting.

Attempt 4: the turn variable

Another idea for two processes: a shared variable says whose turn it is.

int turn = 1;                      // shared
// process 1                       // process 2
while (true) {                     while (true) {
  NCS1;                              NCS2;          // non-critical section
  while (turn != 1) { }              while (turn != 2) { }
  CS1;                               CS2;           // critical section
  turn = 2;                          turn = 1;      // hand over the turn
}                                  }

Mutual exclusion, yes: turn can only hold one value. But it forces strict alternation: if process 1 wants to enter twice in a row and process 2 is busy in its non-critical section, process 1 is left waiting for a turn nobody gives back. The section is free and it cannot get in: progress fails.

Peterson’s algorithm

Peterson combines both ideas: the named note (“I want to get in”) and the turn (“but you go first”).

bool wants1 = false, wants2 = false;     // shared: who wants to get in?
int turn = 1;                            // shared: who is given way to
// process 1                             // process 2
while (true) {                           while (true) {
  NCS1;                                    NCS2;
  wants1 = true;                           wants2 = true;    // raise my hand
  turn = 2;                                turn = 1;         // but let you go first
  while (wants2 && turn == 2) { }          while (wants1 && turn == 1) { }
  CS1;                                     CS2;
  wants1 = false;                          wants2 = false;   // no longer want in
}                                        }

The key is the while: I wait only if the other one wants to get in and I have given them the turn. If the other doesn’t want in, I go straight in (progress). If we both want in, turn decides, and since it can only hold one value, we never both get in (mutual exclusion). And since each one gives way when asking, nobody cuts in twice in a row (bounded waiting).

This is the trace of the interleaving from the notes, with the value of the three variables at each step:

Look at steps 2 and 4: both write turn, and whoever writes it last is the one left waiting, because they were the last to give way. Thread 2 wrote turn = 1, so thread 1 gets in.

Summary of the attempts

The moral from the notes: the variety of synchronisation problems is endless, and we cannot invent such a delicate algorithm every time. We need tools that solve any case. There are two kinds: help from the hardware and tools from the operating system.

Help from the hardware

Disabling interrupts

The most direct idea: if the CPU ignores interrupts, the timer cannot preempt the process. Before entering the critical section, interrupts are disabled, and on leaving they are enabled again. That way nobody can take the CPU away while you touch the data.

It works on a single processor, but it has three drawbacks that come up in the test:

• While a process is in its critical section, all the concurrency of the system is suspended, which hurts processes that don’t even want to enter.
• It does not work on multiprocessors: you cannot send a simultaneous signal to every processor, and the other CPU carries on and can get in.
• It does not guarantee bounded waiting.

Besides, disabling interrupts is a privileged instruction: a user program cannot do it (we saw this with dual mode).

Atomic instructions

An atomic instruction always runs to completion: it is indivisible. On most systems, reading or storing a word in memory is already atomic; what is not atomic is reading, operating and writing (our uploaded += 1), nor other operations such as reading or storing floating-point numbers. The hardware’s answer is instructions that read and modify in a single step:

• Test-and-set(A): sets A to true and returns the old value of A. While it runs, no other processor can touch A.
• Compare-and-swap, CAS(M, A, B): compares cell M with A. If they are equal, it stores B in M and returns true; otherwise it returns false.

This is how a critical section is protected with test-and-set:

bool busy = false;                  // global and shared
while (true) {
  /* non-critical section */
  while (test_and_set(busy)) { }    // if it returns true, someone is inside: wait
  /* critical section */
  busy = false;                     // leaving: release
  /* rest of the program */
}

With compare-and-swap the idea is the same: “if lock is 0, set it to 1 and get in”. Careful, because the notes write the loop as while (Compare_and_swap(&lock, 0, 1)); with the definition above (it returns true if it managed to change it), the consistent thing is to wait while you don’t succeed:

while (true) {
  /* non-critical section */
  while (!compare_and_swap(&lock, 0, 1)) { }  // retry until it changes 0 → 1
  /* critical section */
  lock = 0;                                    // release
  /* rest */
}

A bit of history that sometimes appears: IBM invented in the 1960s a SWAP instruction that atomically exchanged two memory cells. MIPS (and ARM, very similar) uses the LL/SC pair (Load Linked and Store Conditional), and x86 has LOCK BTS (Bit Test and Set): the CPU takes over the bus while it does the test-and-set.

These instructions give mutual exclusion on multiprocessors too, but they do not guarantee bounded waiting (nobody decides who wins next time) and they still wait with a while.

Busy waiting: the problem we keep dragging along

The note with a while, the turn variable, Peterson, test-and-set… they all wait by spinning in a loop. That is busy waiting: the waiting thread uses the CPU to check, again and again, a condition that has not changed yet.

With a single core it is even worse: while B spins, A (the one that has to leave the critical section so B can get in) makes no progress. Ideally, B would go to sleep and the operating system would wake it up when it can get in. That is exactly what the tools in the next section do.

Synchronisation tools from the operating system

Cooperating processes need to communicate (if they are threads, through shared variables), and a process often has to stop until an event happens or a condition caused by another process or thread holds. That is synchronisation. The classic tools are these:

Based on shared memory	No shared memory needed
Semaphores (Dijkstra, 1965)	Channels (Hoare, 1978)
Conditional critical regions (Hansen, 1972)	Mailboxes
Monitors (Hoare, 1972) → mutex and condition variables	Promises and futures (Friedman and Wise, 1976; Baker and Hewitt, 1977)

The course works with the ones highlighted in the notes: semaphores and what comes out of monitors, the mutex and condition variables.

Mutex or lock

Mutex comes from mutual exclusion. It is an object used to acquire exclusive access rights to a resource. It has two states, free and acquired, and starts free. Its two operations are atomic:

• lock(): acquires the mutex. If it was already acquired, the process blocks until it gets it.
• unlock(): releases the mutex. If processes are waiting, one of them acquires it and is unblocked.

Using it means wrapping the critical section:

// non-critical section
mutex.lock();        // entry protocol: I either take it or go to sleep
uploaded = uploaded + 1;   // critical section
mutex.unlock();      // exit protocol: release it (and wake one up)
// non-critical section

The difference from test-and-set is huge: whoever cannot get in blocks (moves to the blocked state we saw with processes) and uses no CPU. This is run 3 of the simulator: the same Round Robin that lost an upload, now with a lock.

At t = 3, notes tries lock() and goes to sleep. The scheduler gives the CPU to photos, which finishes its addition and at t = 6 calls unlock(): since notes was waiting, the lock goes straight to notes. When notes reads, memory already holds an 8. Result: 9.

Condition variables

The mutex answers “can I get in?”. But sometimes the problem is different: “I’m inside and I can’t carry on until something happens” (for example, the buffer is empty). That is what condition variables are for:

• They manage a queue of waiters for a resource or a logical condition.
• They represent a queue of threads waiting for something inside a critical section (protected by a lock).
• They are always associated with a mutex.

Their operations, atomic:

• wait(): blocks the process and puts it in the queue. While it is blocked, the mutex is released. When it is unblocked, it must reacquire the mutex.
• signal(): unblocks one process from the queue. If nobody is there, it does nothing.
• broadcast(): unblocks all the processes in the queue.

Releasing the mutex inside wait() is essential: if the thread slept holding the lock, nobody could get in to change the condition it is waiting for. The usage pattern is always the same:

Mutex mutex = new Mutex();
Condition cond = new Condition(mutex);   // the condition is tied to the mutex

void WaitExample() {
  mutex.lock();
  while (condition) {      // while I can't carry on…
    cond.wait();           // …sleep and release the mutex
  }
  // here what I was waiting for holds, and I have the mutex
  mutex.unlock();
}

void SignalExample() {
  mutex.lock();
  // … change the state: now the condition holds
  cond.signal();           // wake up one waiter
  mutex.unlock();
}

An example from the notes: several processes wait for an event. One signals it with broadcast() and wakes them all:

bool happened = false;
Mutex mutex = new Mutex();
Condition queue = new Condition(mutex);

P1() {                      // signals the event
  mutex.lock();
  happened = true;
  queue.broadcast();        // wakes up everyone waiting
  mutex.unlock();
}

P2() {                      // waits for the event
  mutex.lock();
  while (!happened) {
    queue.wait();
  }
  mutex.unlock();
  // … do things
}

What happens right after a signal: Hoare and Mesa

P calls signal() on a condition Q was blocked on. Both need the mutex: who carries on?

• Hoare style: Q resumes immediately and P is stripped of the mutex.
• Mesa style: Q is unblocked, but waits for P to release the mutex. It is the one most used in today’s languages.

And now you understand the while in the pattern. With Mesa, between the signal() and the moment Q gets the mutex back, another thread can slip in and change the condition again. So Q, on waking up, checks it again. With an if it would carry on blindly.

And if several are blocked and a signal() arrives? It depends on the implementation:

Policy	Who is woken
FIFO	The one that has waited longest
By priority	The highest-priority one (useful in real time)
Random	Any of them (what happens with busy waiting)
broadcast	All of them, and they fight for the mutex

Semaphores

Dijkstra’s semaphore (1965) is the oldest and most versatile tool. It is an integer counter with a queue of sleeping processes, and it is only touched through two atomic operations:

• wait(S): if S is greater than 0, it decrements it and the process carries on. If it is 0, the process blocks in the queue.
• signal(S): if there are blocked processes, it wakes one up (and the value does not change, because the permit goes straight to the one woken). If nobody is there, it increments S.

The notes write the simplest version, with busy waiting, which is handy to see the idea:

wait(S) {
  while (S <= 0) { /* wait */ }     // busy-waiting version
  S--;
}
signal(S) {
  S++;
}

A real operating system replaces that while with blocking the process, which is what the diagram shows:

A semaphore solves two kinds of problem:

Initial value	What for	Example
1 (binary semaphore)	Mutual exclusion: it is a mutex	wait(m) = lock(), signal(m) = unlock()
N (counting semaphore)	Counting free resources	2 printers in the lab, 3 slots in a buffer
0	Waiting for an event	The player waits for a chunk to be downloaded

The classic synchronisation problems

These are three problems that serve as a test bench for any tool: the bounded buffer, readers and writers (with two variants) and the dining philosophers.

The bounded buffer (producer-consumer)

Producers and consumers insert and remove items in a FIFO queue of limited size. Spotify is the perfect example: a downloader thread puts chunks of the song into a buffer and the player takes them out to play them. The rules:

• Producers must not add items if the buffer is full (count == N).
• Consumers must not consume if it is empty (count == 0).

The first version in the notes waits with a while and shares the counter count:

// Producer                           // Consumer
while (true) {                        while (true) {
  Item* thing = produce_something();    while (count == 0) { }   // empty: wait
  while (count == N) { }                Item* thing = buffer[out];
  buffer[in] = thing;                   out = (out + 1) % N;
  in = (in + 1) % N;                    count--;                 // shared data!
  count++;             // shared data!                           consume(thing);
}                                     }

The while loops prevent adding to a full buffer and taking from an empty one, but count++ and count-- are another race condition. With count = 2, Round Robin with Q = 2 and one instruction per time unit, the notes make this trace:

t	Producer	Consumer	count in memory
1	reads count (2)		2
2	adds 1 in its register (3)		2
3		reads count (2)	2
4		subtracts 1 in its register (1)	2
5	writes 3		3
6		writes 1	1

One item went in and another went out, so it should still be 2: 2 + 1 − 1 = 2. We get 1.

The good version combines a mutex (to touch buffer, in, out and count one at a time) and two condition variables (one for the producer to wait on and one for the consumer):

Mutex mutex = new Mutex();
Condition cprod = new Condition(mutex);   // the producer sleeps here
Condition ccons = new Condition(mutex);   // the consumer sleeps here

// Producer
Item* thing = produce_something();
mutex.lock();
while (count == N) {
  cprod.wait();          // full: wait for a slot (and release the mutex)
}
buffer[in] = thing;
in = (in + 1) % N;
count++;
ccons.signal();          // there is something now: tell the consumer
mutex.unlock();

// Consumer
mutex.lock();
while (count == 0) {
  ccons.wait();          // empty: wait for something
}
Item* thing = buffer[out];
out = (out + 1) % N;
count--;
cprod.signal();          // there is a slot now: tell the producer
mutex.unlock();
consume(thing);          // outside the critical section: touches nothing shared

It can also be solved with semaphores, and that is what the second simulator does: a semaphore empty that starts at N (free slots), another one full that starts at 0 (chunks ready) and mutual exclusion inside each operation. This is its real output, turn by turn, with a 3-slot buffer:

In turn 1 the player wants to play and there is nothing: it blocks. In turns 2 to 4 the downloader fills the buffer, and in turn 5 it blocks because there are no slots left. Look at turn 2: signal(full) wakes the player, which is why full stays at 0 even though there is a chunk; that chunk is already reserved for the one that woke up. The same happens with empty in turn 6. We go through it line by line in Check it with Python.

Readers and writers

Proposed by Courtois, Heymans and Parnas (1971), it is the scheme for managing access to a database:

• Several readers can access it at the same time.
• Only one writer can be working.
• There cannot be readers and writers at the same time.
• …and, if possible, no starvation.

Reading together breaks nothing; writing needs the database all to itself. The problem has two variants and each one has its victim:

Variant	What happens	Risk
1st: priority to readers	If a writer is waiting, new readers can overtake it	Starvation of writers
2nd: priority to writers	If writers are waiting, readers that arrive wait until all of them finish	Starvation of readers

This is the solution to the first variant with semaphores. read_count counts how many readers are inside; the first one in shuts the door on writers and the last one out opens it:

semaphore mutex = 1;      // protects read_count
semaphore rw_mutex = 1;   // exclusion among writers (and readers as a group)
int read_count = 0;

Read() {
  wait(mutex);
  read_count++;
  if (read_count == 1) wait(rw_mutex);   // the first reader blocks the writers
  signal(mutex);
  READ FROM THE DB;                       // several readers at once
  wait(mutex);
  read_count--;
  if (read_count == 0) signal(rw_mutex); // the last reader lets the writers in
  signal(mutex);
}

Write() {
  wait(rw_mutex);                         // exclusive
  WRITE TO THE DB;
  signal(rw_mutex);
}

The dining philosophers

Dijkstra’s problem (1965): five philosophers around a table spend their time eating and thinking. There is a chopstick between each pair of philosophers, and to eat each one needs the two chopsticks next to them.

If all five pick up their left chopstick at the same time, each one is left waiting for the chopstick their neighbour holds: nobody lets go and nobody eats. That is a deadlock. The solutions in the notes break that circle:

1. Asymmetric algorithm: even philosophers pick up one chopstick first and odd ones the other.
2. At most four philosophers asking for chopsticks at the same time: there will always be one who gets both.
3. Taking both chopsticks atomically: either you take both or you take none.

Common mistakes

Check it with Python

Two simulators with the data from this article. They don’t use real threads, on purpose: with real threads the interleaving changes on every run and you couldn’t compare your output with mine. Here the simulator itself fixes the interleaving, so you will see exactly what is described above. Run them with python3 and change the data to see other interleavings.

Simulator 1: the race condition and the lock

Two onedrive threads, photos (P) and notes (N), do uploaded = uploaded + 1 starting from 7. The string order says which thread asks for the CPU at each tick ('PPNN' is Round Robin with Q = 2, and it repeats). Each thread has its private register in reg and its program counter in pc.

# Race condition: two onedrive threads do uploaded = uploaded + 1 at the same time.
# The interleaving is not left to chance: ORDER says which thread asks for the CPU at each tick.
NAME = {'P': 'photos', 'N': 'notes'}
STEPS = ['read', 'add', 'write']                # what the CPU does with "uploaded += 1"
LOCKED_STEPS = ['lock()'] + STEPS + ['unlock()']  # the same addition, protected by a lock

def run(title, order, steps):
    uploaded, reg, pc = 7, {'P': '-', 'N': '-'}, {'P': 0, 'N': 0}  # 7 files already uploaded
    owner, sleeping, t = None, set(), 0         # lock owner and blocked threads
    print(f'--- {title} ---')
    print(f'{"t":>2}  {"thread":<8} {"step":<15} {"reg P":>5} {"reg N":>5} {"uploaded":>8}')
    while pc['P'] < len(steps) or pc['N'] < len(steps):
        h = order[t % len(order)]; t += 1
        other = 'N' if h == 'P' else 'P'
        if pc[h] == len(steps) or h in sleeping:  # finished or blocked: it cannot use the CPU
            h, other = other, h                   # so the scheduler gives it to the other one
        step = steps[pc[h]]
        if step == 'lock()' and owner not in (None, h):
            sleeping.add(h); step = 'lock() blocks'  # taken: it sleeps without moving on
        else:
            if step == 'lock()': owner = h
            elif step == 'read': reg[h] = uploaded    # copies the shared data into ITS register
            elif step == 'add': reg[h] += 1           # adds in the register, not in memory
            elif step == 'write': uploaded = reg[h]   # stores the register in memory
            elif step == 'unlock()':
                owner = None
                if other in sleeping:                 # someone was waiting: hand the lock over
                    sleeping.discard(other); owner = other; pc[other] += 1
            pc[h] += 1
        print(f'{t:>2}  {NAME[h]:<8} {step:<15} {reg["P"]:>5} {reg["N"]:>5} {uploaded:>8}')
    verdict = 'correct' if uploaded == 9 else 'an upload has been lost'
    print(f'Result: uploaded = {uploaded} (expected 9): {verdict}\n')

run('1) No lock, one after the other', 'PPPNNN', STEPS)
run('2) No lock, Round Robin with Q = 2', 'PPNN', STEPS)
run('3) With a lock, the same Round Robin', 'PPNN', LOCKED_STEPS)

This is its real output:

--- 1) No lock, one after the other ---
 t  thread   step            reg P reg N uploaded
 1  photos   read                7     -        7
 2  photos   add                 8     -        7
 3  photos   write               8     -        8
 4  notes    read                8     8        8
 5  notes    add                 8     9        8
 6  notes    write               8     9        9
Result: uploaded = 9 (expected 9): correct

--- 2) No lock, Round Robin with Q = 2 ---
 t  thread   step            reg P reg N uploaded
 1  photos   read                7     -        7
 2  photos   add                 8     -        7
 3  notes    read                8     7        7
 4  notes    add                 8     8        7
 5  photos   write               8     8        8
 6  notes    write               8     8        8
Result: uploaded = 8 (expected 9): an upload has been lost

--- 3) With a lock, the same Round Robin ---
 t  thread   step            reg P reg N uploaded
 1  photos   lock()              -     -        7
 2  photos   read                7     -        7
 3  notes    lock() blocks       7     -        7
 4  photos   add                 8     -        7
 5  photos   write               8     -        8
 6  photos   unlock()            8     -        8
 7  notes    read                8     8        8
 8  notes    add                 8     9        8
 9  notes    write               8     9        9
10  notes    unlock()            8     9        9
Result: uploaded = 9 (expected 9): correct

The trickiest part is the one that acts as the lock. When a thread has to do lock() and the lock belongs to the other one, it goes into sleeping and its pc does not move. While it sleeps, if the scheduler picks it, the CPU goes to the other thread (as in a real system, a blocked thread cannot run):

if pc[h] == len(steps) or h in sleeping:  # finished or blocked: it cannot use the CPU
    h, other = other, h                      # so the scheduler gives it to the other one
step = steps[pc[h]]
if step == 'lock()' and owner not in (None, h):
    sleeping.add(h); step = 'lock() blocks'  # taken: it sleeps without moving on

And on unlock(), if the other one was asleep, the lock goes straight to it and its lock() counts as done (pc[other] += 1), just like the definition: “one of them acquires it and is unblocked”.

elif step == 'unlock()':
    owner = None
    if other in sleeping:                    # someone was waiting: hand the lock over
        sleeping.discard(other); owner = other; pc[other] += 1

What to look at:

1. Run 1: no lock, but one after the other. There is no race because photos writes before notes reads: 7 → 8 → 9.
2. Run 2, tick 3: notes reads a 7 when photos already has an 8 in its register. That is the exact moment the upload is lost: at ticks 5 and 6 both write 8.
3. Run 3, tick 3: with the same scheduler, notes tries lock() and blocks. At tick 4 the order says “N”, but notes is asleep, so photos gets the CPU.
4. Run 3, tick 6: photos’ unlock() hands the lock to notes, which at tick 7 reads 8, not 7. Result: 9, even though the scheduler is the same as in run 2.
5. Try it: change the order of run 2 to 'PNPNPN' (Round Robin with Q = 1). What do you get? Do the trace by hand before running it.

Simulator 2: spotify’s buffer with semaphores

The downloader (D) puts numbered chunks into a buffer with N = 3 slots and the player (P) takes them out in order. empty counts the free slots and full, the chunks ready to play. Each turn is a complete operation, so the mutex protecting the buffer doesn’t need to be drawn: nobody can be left halfway.

# Producer-consumer in spotify: the downloader (D) puts chunks of the song into a buffer
# of 3 slots and the player (P) takes them out. Two semaphores coordinate them; turns are fixed.
N, TURNS = 3, 'PDDDDPDPPPP'                  # who asks for the CPU at each turn
NAME = {'D': 'downloader', 'P': 'player'}
sem = {'empty': N, 'full': 0}             # free slots and chunks ready to play
waiting, granted = {}, set()              # who sleeps on each semaphore / woken up
buffer, next_chunk = [], 1

def wait(s, h):
    if h in granted: granted.discard(h); return True  # woken by a signal: it already has its unit
    if sem[s] > 0: sem[s] -= 1; return True         # units left: take one and carry on
    waiting[s] = h; return False                    # it is 0: block (never goes below 0)

def signal(s):
    if s in waiting: granted.add(waiting.pop(s))    # someone was asleep: wake it, do not add
    else: sem[s] += 1                               # nobody was waiting: keep the unit

def state(h):
    return 'blocked' if h in waiting.values() else 'ready'

print(f'{"turn":>5}  {"who":<12} {"action":<11} {"buffer":<8} {"empty":>6} {"full":>6}  {"D":<9} {"P":<9}')
for t, h in enumerate(TURNS, 1):
    if h == 'D':
        if wait('empty', 'D'):
            buffer.append(next_chunk); action = f'puts {next_chunk}'; next_chunk += 1
            signal('full')                          # tell: one more chunk to play
        else: action = 'blocks'
    else:
        if wait('full', 'P'):
            action = f'takes {buffer.pop(0)}'         # FIFO: the oldest chunk plays
            signal('empty')                         # tell: there is a free slot
        else: action = 'blocks'
    box = '[' + ' '.join([str(x) for x in buffer] + ['·'] * (N - len(buffer))) + ']'
    print(f'{t:>5}  {NAME[h]:<12} {action:<11} {box:<8} {sem["empty"]:>6} {sem["full"]:>6}  {state("D"):<9} {state("P"):<9}')
print(f'At the end: {len(buffer)} chunks in the buffer, empty = {sem["empty"]}, full = {sem["full"]}')

The important part is in wait and signal, which follow the blocking definition from the notes: wait subtracts if it can and, if the value is 0, goes to sleep without subtracting; signal wakes someone up if there is anyone and, otherwise, adds. The set granted keeps the ones woken up: they already have their permit and on their next turn they go through without waiting again.

def wait(s, h):
    if h in granted: granted.discard(h); return True  # woken by a signal: it already has its unit
    if sem[s] > 0: sem[s] -= 1; return True         # units left: take one and carry on
    waiting[s] = h; return False                    # it is 0: block (never goes below 0)

def signal(s):
    if s in waiting: granted.add(waiting.pop(s))    # someone was asleep: wake it, do not add
    else: sem[s] += 1                               # nobody was waiting: keep the unit

Its real output:

 turn  who          action      buffer    empty   full  D         P        
    1  player       blocks      [· · ·]       3      0  ready     blocked  
    2  downloader   puts 1      [1 · ·]       2      0  ready     ready    
    3  downloader   puts 2      [1 2 ·]       1      1  ready     ready    
    4  downloader   puts 3      [1 2 3]       0      2  ready     ready    
    5  downloader   blocks      [1 2 3]       0      2  blocked   ready    
    6  player       takes 1     [2 3 ·]       0      2  ready     ready    
    7  downloader   puts 4      [2 3 4]       0      3  ready     ready    
    8  player       takes 2     [3 4 ·]       1      2  ready     ready    
    9  player       takes 3     [4 · ·]       2      1  ready     ready    
   10  player       takes 4     [· · ·]       3      0  ready     ready    
   11  player       blocks      [· · ·]       3      0  ready     blocked  
At the end: 0 chunks in the buffer, empty = 3, full = 0

What to look at:

1. Turn 1: the player arrives before anything else and blocks with full = 0. A semaphore at 0 is used to wait for an event.
2. Turn 2: the downloader puts chunk 1 and its signal(full) wakes the player. full stays at 0: the chunk is already reserved for the one that woke up.
3. Turn 5: with the buffer full, empty = 0 and the downloader blocks. In turn 6, the player takes chunk 1 and its signal(empty) wakes it, which is why empty stays at 0 again.
4. The numbers add up except for permits “in transit”. Chunks in the buffer = 3 − empty in every turn except 6 (there the woken downloader has a slot reserved), and chunks = full in every turn except 2 to 5 (the woken player has a chunk reserved until it takes it in turn 6). Count the boxes in each row and check it.
5. Try it: change TURNS to 'DDDDDPPPPPP'. In which turn does the downloader block, and how many chunks does it manage to put in?

Summary

Concept	Key idea
Concurrency	Several processes exist at the same time; it does not imply simultaneous execution
Parallelism	Simultaneous execution on several processors (a particular case of concurrency)
Race condition	The result depends on the interleaving when touching shared data
Critical section	Code that accesses shared data; at most one thread inside
Requirements	Mutual exclusion, progress and bounded waiting
Peterson	Correct for two processes, but with busy waiting and sensitive to reordering
Disabling interrupts	Only works on one processor; freezes everything; no bounded waiting
Test-and-set / CAS	Hardware atomics; busy waiting; no bounded waiting
Mutex	lock() / unlock(); whoever can’t get in blocks
Condition variable	wait() / signal() / broadcast(); goes with a mutex; while because of Mesa style
Semaphore	Counter + queue; wait() subtracts or blocks; signal() wakes or adds
Classics	Bounded buffer, readers and writers, philosophers (deadlock)

Three ideas to take away:

1. x = x + 1 is three steps, and a context switch in the middle is enough to lose data. That is a race condition.
2. Every solution writes an entry protocol and an exit protocol around the critical section, and must satisfy mutual exclusion, progress and bounded waiting.
3. Software solutions and atomic instructions wait by spinning; the mutex, condition variables and semaphores put the waiter to sleep and wake it when it can carry on.

Now it’s time to practice. First, in the concurrency guided practice we follow race conditions and semaphore traces step by step; then, with exam questions: a test with every format, semaphore traces that mark themselves and long-answer questions in the concurrency and synchronization exercises. This topic closes the processes block; the next one is memory management: contiguous memory, segmentation and paging.

Next step: practiceConcurrency 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)

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