Process Synchronization — Race Conditions to the Sleeping Barber

Race condition. A race condition occurs when two or more processes or threads concurrently access the same shared data, at least one of them writes it, and the final value therefore depends on the particular order in which the concurrent accesses happen. The program is correct for some interleavings and wrong for others — and you cannot predict which interleaving the scheduler will pick.

The example as printed in the Dec-2024 answer

Two threads share one integer, and each simply adds one to it:

int counter = 0;

Thread 1:  counter = counter + 1;
Thread 2:  counter = counter + 1;

That one statement is three memory operations at machine level — read → modify → write — and the hardware may interleave them arbitrarily between the two threads. Using one register each:

Thread 1                  Thread 2
reg1 = counter;           reg2 = counter;
reg1 = reg1 + 1;          reg2 = reg2 + 1;
counter = reg1;           counter = reg2;

Both threads read the same starting value 0, both computed 1, and the second write simply overwrote the first. One increment has been destroyed — which is why the symptom is called a lost update. Had the two threads run strictly one after the other the answer would be 2, so the same program gives two different results on two different runs.

What a race condition needs before it can happen

1. The data is shared — a global variable, a kernel table, a file, a device register, the buffer of a producer–consumer pair.
2. At least one accessor writes it — read–read overlaps are harmless.
3. The accesses overlap in time: two threads on two cores, or one thread preempted halfway through its update by another.

Remove any one of the three and the race disappears. In practice you cannot remove the sharing, so the OS makes the accesses mutually exclusive — which is the critical section of the next section.

Where the same race reappears on this page: the two bit-flip tables of the Jul-2016 answer illustrate it, and it is the reason the 2016 paper Q.4(c) asks you to show that if wait and signal are not executed automatically, mutual exclusion may be violated — see Section G.

Critical section. A critical section is that segment of code of a process in which the process accesses a shared object — it changes or reads a shared variable, updates a shared table, or writes to a shared file or device. Because simultaneous entry would corrupt that object, the rule is: while one process is executing in its critical section, no other process may execute in its critical section for the same object. “Critical” describes the section of code, not the shared variable.

The shared-variable example — Counter = 100

Let Counter be an integer shared by two processes, each of which must increment it once. The intended result of two increments is 102.

int Counter = 100;

P0:  Counter = Counter + 1;      P1:  Counter = Counter + 1;

Each statement again expands to read–add–write, and this time the two processes are allowed to interleave:

P1’s write destroys P0’s increment, because P1 had already copied 100 into its own register before P0 stored anything. One increment is lost — so the final value of Counter can be 101 or 102 depending only on the order of execution. Controlling that order is exactly what a critical section is for.

Structure of a process that uses a critical section

Every process that touches the shared object is written in the same four-part shell. The entry and exit sections are the protocol that grants and releases permission; they are the only parts that may themselves contain races — which is why sections E and F spend so much effort on them.

do {
      entry section;        /* ask for permission to enter */
      /* CRITICAL SECTION */ /* the code that touches the shared object */
      exit section;         /* release permission */
      remainder section;    /* everything else — no shared data */
} while (true);

The four-part shell, term by term

“What are various methods to solve the critical section problem?”

That clause of the question expects the three-way classification, set out in full in Section D · Mutual exclusion and then implemented in Section E (software: Peterson’s, Dekker’s, Bakery’s) and Section F (hardware: disable interrupts, Test-and-Set, Swap). The third approach — programming-language constructs such as monitors and critical regions — is compared with semaphores in Section G.

The critical-section problem. Suppose each of n processes has a section of code — its critical section — in which shared variables, shared tables or shared devices are changed. The critical-section problem is to design a protocol that the processes can use to cooperate, so that when one process is executing in its critical section no other process is allowed to execute in its critical section. The protocol is the entry section and the exit section that wrap the critical section:

do {
      entry section;
      /* critical section */   /* the shared Counter is written here */
      exit section;
      remainder section;
} while (true);

Any solution to the critical-section problem must satisfy three requirements.

Requirement 1 — Mutual Exclusion

If process P_i is executing in its critical section, then no other process may be executing in its critical section. This is the safety property: at most one process inside the critical region at any instant. It is violated by the naive “just check a flag” scheme, where two processes can both read the flag as clear and both charge in — which is the Counter = 101 outcome of Section B.

Requirement 2 — Progress

Printed wording from the older-paper answer: “If no process is executing in its critical section and there exist some processes that wish to enter their critical sections, then only those processes that are not executing in their remainder section can participate in the decision of which will enter its critical section next, and this decision cannot be postponed indefinitely.” Two halves to remember: (a) processes sitting quietly in their remainder section must not be able to influence the decision — otherwise a process that has no interest in the shared data blocks the one that does, which is the flaw of strict alternation; (b) if the lock is free, somebody who is waiting must get in. Progress is therefore also the “no deadlock” property.

Requirement 3 — Bounded Waiting

There must exist a bound on the number of times other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted. In other words a waiting process cannot be overtaken an unlimited number of times; the printed answer adds the practical picture — “once a process enters its critical section, it does not get another turn until a waiting process gets a turn (managed as a queue)”. The bound is normally stated as “at most n − 1 overtakes”. Bounded waiting is the anti-starvation property: the plain Test-and-Set loop satisfies the first two requirements but not this one, which is why the bounded-waiting variant exists (Section F).

Two further assumptions usually stated with them

• Each process must exit its critical section only from within that critical section, and it must remain there for only a bounded time — otherwise “no other process can enter” becomes permanent.
• No assumption is made about the number or the relative speeds of processes and CPUs. Once a process starts, it cannot be stopped except by another process.

Mutual exclusion is a property of process synchronization: no two processes can exist in the critical section at any given point of time. The term was first coined by Dijkstra. It is the enforcement half of the relationship — the critical section names the dangerous code, mutual exclusion names the rule that keeps that code single-file.

Why the need arises — with concurrency

Mutual exclusion is unnecessary in a strictly sequential system, because there is only one instruction stream and a read–modify–write sequence can never be interrupted halfway. The need appears the moment execution becomes concurrent: several instruction streams making progress over the same interval while sharing some object. Concurrency creates the interleaving of Section A, and the interleaving creates the lost update.

The four kinds of concurrent execution

Three approaches to implementing mutual exclusion

The six requirements of mutual exclusion — as printed

1. Only one process may be in its critical section at a time.
2. The mechanism must be implementable purely in software on a machine — it may not assume special hardware that the machine does not provide.
3. A process must remain in its critical section for a bounded time only.
4. No assumption may be made about the relative speeds of asynchronous concurrent processes, nor about the number of processors.
5. A process that is outside its critical section cannot prevent another process from entering its critical section.
6. A process must not be indefinitely postponed from entering its critical section.

Read requirements 1, 5 and 6 against Section C and the mapping is immediate: 1 = mutual exclusion, 5 and the bounded-time clauses = progress, 6 = bounded waiting. The other clauses (2, 3, 4) are what makes the requirement set implementable rather than merely idealistic — a scheme that needs a lock-free broadcast bus, or that assumes all processes run at the same speed, is not admissible.

This build-up is not asked as a question by itself in either book, but the Peterson’s and Bakery’s answers are impossible to justify without it: the marks are earned by saying which requirement a naive scheme breaks. Assume exactly two processes, P₀ and P₁; for P_i write j for the other process (j = 1 − i).

Attempt 1 — one shared variable: turn (strict alternation)

int turn = 0;                     /* shared */

/* P0 */  while (turn != 0) { /* spin */ }   /* entry */
          /* CRITICAL SECTION */
          turn = 1;                           /* exit */

/* P1 */  while (turn != 1) { /* spin */ }   /* entry */
          /* CRITICAL SECTION */
          turn = 0;                           /* exit */

Read it: one variable records whose go it is; each process spins until the turn equals its own number, and hands the turn over on exit. Only one process can ever be inside, so mutual exclusion holds. But suppose P₀ finishes, sets turn = 1, and then never wants the critical section again, while P₁ wants it twice in a row. P₁ completes one pass, sets turn = 0, and on its second request spins forever although P₀ is idle — it is being vetoed by a process that is not even competing. Progress fails.

Attempt 2 — one shared variable: flag (“is anybody inside?”)

boolean flag = false;             /* shared */

while (flag) { /* spin */ }       /* entry: is somebody inside? */
flag = true;
/* CRITICAL SECTION */
flag = false;                     /* exit */

Read it: a single boolean says whether someone is inside; look before you leap, then raise the flag. The fatal detail is that look and leap are two separate memory operations, so the test-and-set is not atomic: P₀ reads flag == false and is preempted, P₁ also reads flag == false, and both then set it — and both enter. Mutual exclusion fails, for exactly the reason Counter became 101. Any software solution must therefore get atomicity from somewhere: the standard trick is to require only that a single memory write be atomic, and to spread the state over several variables so that no one test-then-set pair can be broken in half.

Attempt 3 — two shared variables: flag[2] (interest only)

boolean flag[2] = {false, false};   /* shared: flag[i] = "Pi wants in" */

flag[i] = true;
while (flag[j]) { /* spin */ }      /* wait while the other is interested */
/* CRITICAL SECTION */
flag[i] = false;

Read it: each process announces its interest by writing its own variable — a write that is atomic — and waits while the other’s flag is set. Mutual exclusion now holds: if both are interested, neither can pass its loop. But both may set their flags before either checks: P₀ sets flag[0], P₁ sets flag[1], each then sees the other’s flag set, and both spin politely forever at a lock that is in fact free. Progress fails — a deadlock created purely by the protocol.

Attempt 4 — two shared variables: flag[2] + turn, naively combined

/* P0 */  flag[0] = true;  while (flag[1]) { /* spin */ }  turn = 0;
/* P1 */  flag[1] = true;  while (flag[0]) { /* spin */ }  turn = 1;

Read it: raise your flag, wait for the other to lower its, and only then record the turn. Because the flag is raised before the test, the two processes can again both be stuck waiting on each other; and if the interleaving lets one process pass the test just before the other’s flag store lands, both enter. So this version can break both mutual exclusion and progress. The repair is a change of order: set turn after raising your own flag, so that whoever wrote last is the one that waits. That is Peterson’s algorithm.

Purpose

To achieve mutual exclusion between exactly two processes using only two shared variables and ordinary atomic reads and writes — no special machine instruction at all. It repairs attempt 4 above purely by ordering the writes: each process first declares its interest, then politely gives the turn away, and only then checks.

The variables

Pseudocode

boolean flag[2];      /* both false */
int     turn;         /* 0 or 1     */

do {
      flag[i] = true;                        /* 1. I am interested        */
      turn      = j;                         /* 2. but you may go first   */
      while (flag[j] && turn == j) { /* spin */ }  /* 3. wait if both hold */

      /* CRITICAL SECTION */

      flag[i] = false;                       /* 4. no longer interested   */

      /* REMAINDER SECTION */
} while (true);

Read the entry section as one sentence: “I want in, and I concede priority to you; I will hang around only while you actually want in and it really is your turn.” Statement 3 is a spin loop — Peterson’s is a busy-waiting solution.

Why it works — plain-English walkthrough

1. Mutual exclusion. Suppose both were inside. For P_i to have passed its loop, either flag[j] was false — impossible while P_j is inside, because P_j raises its flag before entering and lowers it only on exit — or turn != j. By symmetry P_j needs turn != i. But turn holds exactly one of the two values, so both cannot hold: at most one process passes.
2. Progress. If both are interested, both execute their turn = j statements and the last write wins; so exactly one process sees turn == j and waits, while the other sees a false condition and enters at once. A process in its remainder section has flag == false, which alone is enough to release the loop — idle processes take no part in the decision.
3. Bounded waiting. The one that loses the race over turn gets in once the winner eventually executes flag[i] = false on exit; the loser then sees the flag clear and enters. On a single processor that is all it takes, because the winner is the only other process that can enter, so the loser is overtaken at most once per request. (With more than one CPU a third process could in principle intervene, which is one more reason the algorithm is stated for two processes.)
4. The worked interleaving (this is the “EXAMPLE” table the 2017 answer draws). P₀ executes steps 1 and 2 → flag[0]=true, turn=1. P₁ now executes 1 and 2 → flag[1]=true, turn=0. P₀ tests flag[1] && turn==1 = true && false → it proceeds into its critical section. P₁ tests flag[0] && turn==0 = true && true → it waits. The process that wrote turn last is the one that waits.

Limitations

• Two processes only. The concession turn = j has no natural meaning for n > 2; generalising it to n processes is what Bakery’s algorithm does with ticket numbers (next card).
• It busy-waits — the loser burns CPU in the while loop (see Section H).
• It assumes ordered (sequentially consistent) memory. On real multiprocessors the CPU and compiler may reorder the flag store after the turn store; without a memory barrier both processes can read stale flags and both enter. Peterson’s is correct as a textbook algorithm, not as kernel code.

Purpose — and the book’s own opening line

Printed verbatim in the older paper: “Dekker's algorithm was the first provably-correct solution to the critical section problem. It requires both an array of boolean values and an integer variable.” Like Peterson’s it solves the two-process case purely in software. Its difference is the way it breaks symmetry: instead of the last writer simply losing, a process that finds the turn held by the other backs off entirely, waits, and then asks again.

The variables

Pseudocode — as printed in the older answer

var flag : array [0..1] of boolean;   /* both false */
    turn : 0..1;                      /* say, 0     */

repeat
      flag[i] := true;                       /* announce interest */
      while flag[j] do                       /* the other is interested too */
            if turn = j then                 /* ... and the right of way is his */
            begin
                  flag[i] := false;          /* 1. I back off completely      */
                  while turn = j do no-op;   /* 2. I wait while he is inside  */
                  flag[i] := true;           /* 3. now I ask again            */
            end;
      /* CRITICAL SECTION */
      turn := j;                             /* hand the right of way over */
      flag[i] := false;                      /* leave                      */
      /* REMAINDER SECTION */
until false;

The three statements inside begin … end are the heart of Dekker’s. If the turn is the other’s, you must not push on: you lower your own flag so the other process can finish testing, spin until it has left (that is, until turn comes back to you), and then raise your flag again and re-enter the outer test.

Why it works — plain-English walkthrough

1. Both processes raise their flags, so the outer test while flag[j] is true for both and both fall into the “someone else is interested” branch.
2. Exactly one of them is named by turn. Suppose turn = 1. For P₀ the inner test turn = j reads turn = 1 and is true, so P₀ lowers its flag and waits at while turn = j do no-op. For P₁ the same test reads turn = 0 and is false, so P₁ does nothing and re-tests — against P₀’s flag, which has just fallen. P₁ enters, and P₀ cannot pass its inner wait until P₁ leaves. That is mutual exclusion.
3. P₁ exits by executing turn := j — i.e. turn := 0 — and then flag[1] := false. That release frees P₀ from its inner spin; P₀ raises its flag again, sees flag[1] = false, and enters. So an idle lock never stays idle: progress holds.
4. A process that backs off is guaranteed the turn next, so it cannot be jumped over more than once: bounded waiting holds.

Limitations

• Two processes only — like Peterson’s, it does not scale to n; use Bakery for n.
• Notoriously harder to read and to prove than Peterson’s: it nests two spin loops and uses a “back off and retry” structure, so it is easy to get wrong in an exam.
• Both loops are busy-waits — spinning no-op keeps a CPU (or a core) from doing useful work.
• Correctness assumes atomic, ordered reads and writes of flag and turn, so it is unsafe on out-of-order multiprocessors without memory barriers.

Purpose

Printed opening of the older answer (with the book’s own typos, as the notes record them): “The Bakery algorithm is one of the simplest known solutions to the mutual exclusion problem for the general case of N processes.” Peterson’s and Dekker’s are two-process protocols; Bakery is the software solution that works for an arbitrary number of processes, and it does so without any special machine instruction.

The idea, in the book’s own words

Quoting the printed answer: “The basic idea is that each non-thinking process has a variable that indicates the position of that process in a hypothetical queue of all the non-thinking processes. Each process in this queue scans the variables of the other processes, and enters the critical section only upon determining that it is at the head of the queue.” Lamport’s metaphor is the counter of a bakery: you take a numbered token before you are served, and the clerk always serves the smallest number on display. The notes also record that the printed answer then admits “the resulting algorithm is still not easy to understand” and presents a simplified version first — worth saying in an exam, because it shows you know the hard part.

The variables

Two shorthands used below: (number[i], i) < (number[k], k) means the pair is compared lexicographically — either number[i] < number[k], or the two numbers are equal and i < k. And max(a₀ … aₙ₋₁) returns the largest value, breaking ties by the largest index.

Pseudocode

do {
      choosing[i] = true;                       /* my ticket is not final yet   */
      number[i]   = max(number[0..n-1]) + 1;     /* take the next token          */
      choosing[i] = false;                      /* ticket is now stable         */

      for (k = 0; k < n; k++)
            if (k != i) {
                  while (choosing[k]) ;                                   /* a */
                  while (number[k] != 0 &&
                         (number[k], k) < (number[i], i)) ;                /* b */
            }

      /* CRITICAL SECTION */

      number[i] = 0;                            /* surrender the token          */

      /* REMAINDER SECTION */
} while (true);

Read it line by line. (1) Declare that a number is being picked, so nobody judges you on a half-written value. (2) Take a ticket one greater than the highest ticket visible. (3) Mark the ticket stable. (4) Then walk through every other process: at (a) wait until its ticket is stable, at (b) wait while it holds a non-zero ticket that sorts ahead of yours. Only when the whole scan finishes with nobody ahead of you do you enter. (5) On exit you set your number to 0 — that is how “I am not interested” is written.

Proof of the three requirements — the two-case argument

(1) Mutual exclusion. Suppose P_i is in its critical section and P_k (k ≠ i) has already chosen number[k]. There are two cases:

1. Case 1 — (number[i], i) < (number[k], k). When P_k’s scan reaches index i it finds number[i] != 0 and the tuple comparison true, so P_k waits in loop (b). It can leave that loop only when P_i sets number[i] = 0, i.e. only after P_i has left its critical section. So the two are never inside together.
2. Case 2 — (number[k], k) < (number[i], i). Then P_k chose its ticket before P_i did: had P_i chosen later, its max(number[0..n-1]) + 1 would have seen number[k] and returned something strictly larger, contradicting (number[k],k) < (number[i],i). But P_i is inside, so its scan must already have passed index k — impossible while P_k held the smaller non-zero ticket. The only consistent reading is that P_k had not yet reached its own scan when P_i passed, and having now reached it P_k waits behind P_i. Mutual exclusion holds in both cases.

Because the comparison is lexicographic, one of the two cases always holds: ties on number are broken by the process id, so the hypothetical queue has a total order and two processes can never occupy the same position and fight over it.

(2) Progress. Only processes with number[k] != 0 — those that actually asked to enter — are ever considered by the scan, so a process sitting in its remainder section holds 0 and cannot veto anybody. Among the requesters, the scan takes the smallest (number, id) pair, and that choice is fixed by values already written; the decision is reached in finite time and cannot be postponed indefinitely.

(3) Bounded waiting. Once P_i holds (t, i), every process that arrives later takes max(...) + 1 > t and therefore sorts behind P_i — it cannot overtake. Only the processes already holding smaller tickets may go first, and there are at most n − 1 of them, each getting at most one turn before P_i’s ticket reaches the head. So P_i waits for at most n − 1 entries: a bound exists, hence no starvation.

Limitations

• Busy waiting, twice over — a process spins in loops (a) and (b), so n processes can keep n − 1 CPUs spinning for nothing.
• O(n) shared-memory reads per entry; the scan, not the lock, is the cost, and on exit a holder must still be waited for by everybody else.
• Ticket numbers grow without bound in this form, and choosing[] is essential: without it a torn read of a half-written number[k] can hand two processes the “same” position and break mutual exclusion.
• It still needs atomic single-word reads and writes; on weakly-ordered hardware the scan must be fenced.

What makes a solution “hardware”

Every software attempt in Section E had to build atomicity out of pieces that are not atomic. Hardware solutions invert that: the machine supplies an instruction that performs test and set (or read and write) in one uninterruptible step. The entry section then collapses into a single call to such an instruction, and mutual exclusion follows from the instruction’s atomicity rather than from a clever ordering of writes.

1. Disable interrupts

while (true) {
      disable_interrupts();      /* entry — no interrupt can arrive now */
      /* CRITICAL SECTION */
      enable_interrupts();       /* exit  — interrupts allowed again    */
      /* REMAINDER SECTION */
}

Why it works: on a uniprocessor the only way to switch from one process to another is an interrupt — the clock tick, or an I/O completion. With interrupts off, the running process cannot be preempted, so no other process can reach the shared data while its critical section executes. Mutual exclusion is therefore absolute.

Why it is a bad idea in general: disable_interrupts() is a privileged instruction, so user code must not be allowed to switch off the clock — a process could then monopolise the machine and defeat the scheduler. It does nothing at all on a multiprocessor: masking interrupts on CPU 1 does not stop CPU 2 from touching the same memory. And it slows the whole system, because the interrupt latency of unrelated devices grows while the critical section runs. It survives as the standard technique for very short kernel-mode critical regions, which is exactly the “interrupt handlers” row of the concurrency table in Section D.

2. Test-and-Set

boolean testAndSet(boolean *target) {
      boolean oldValue = *target;
      *target = true;
      return oldValue;           /* the read AND the write are ATOMIC     */
}

Read it: the instruction stamps true into the target and hands back the value that was there before, and nothing can come between the read and the write. Two processes calling it simultaneously get different answers: exactly one receives false — the lock was free and it has just taken it — and every other caller receives true and must keep trying.

boolean lock = false;                   /* shared, one lock per critical region */

do {
      while (testAndSet(&lock)) ;   /* entry: spin until a call returns false   */
      /* CRITICAL SECTION */
      lock = false;                 /* exit:  a plain release                   */
      /* REMAINDER SECTION */
} while (true);

Walkthrough: P₀ calls testAndSet, receives false, so the while body never runs and P₀ enters; lock is now true. P₁ calls it, receives true, and therefore re-calls it in the loop, receiving true every time — because each failed call re-stamps lock as true. When P₀ finishes and stores lock = false, P₁’s next call returns false and it enters. Mutual exclusion: satisfied. Progress: satisfied — a free lock is taken by whichever caller next executes the instruction.

Bounded waiting: NOT satisfied. Nothing orders the losers. A process that has just left its remainder section can win the race against a process that has been spinning for minutes, and on a multiprocessor the spinner may keep losing simply because the other’s stores land closer in time. That is starvation, so the plain loop needs a queue.

3. The bounded-waiting Test-and-Set variant

The repair is to record who is waiting in a shared array and, on exit, to open the door for the next waiter in cyclic order instead of for whoever happens to win the race.

boolean lock = false;                  /* the test-and-set lock   */
boolean waiting[n];                    /* all false initially     */
int     n;                             /* number of processes     */

do {
      waiting[i] = true;                        /* 1. raise my hand          */
      key = true;
      while (waiting[i] && key)                 /* 2. queue + lock race      */
            key = testAndSet(&lock);
      waiting[i] = false;                       /* 3. I am through           */

      /* CRITICAL SECTION */

      j = (i + 1) % n;                          /* 4. find the next waiter   */
      while ((j != i) && !waiting[j])
            j = (j + 1) % n;                    /*    ... cyclically         */

      if (j == i)  lock = false;                /*    nobody: release lock   */
      else         waiting[j] = false;          /*    somebody: hand it over */

      /* REMAINDER SECTION */
} while (true);

Walkthrough. Step 1 makes the request visible to everybody. Step 2 spins only while both “I am still queued” and “I have not yet got the lock” hold — the second half of that condition is what lets an exiting process drag a waiter out by clearing its waiting entry instead of releasing the lock. Step 4 is the whole point: on leaving, the process scans waiting[] forward from its own index, wrapping at n. If it finds a waiter it does not touch lock — it clears that waiter’s waiting[j], which breaks the waiter out of its loop and passes the lock directly to it. Only when the scan comes full circle with nobody waiting is lock set to false and returned to the pool. Because service moves in one fixed direction around the ring, no process can be overtaken more than n − 1 times: mutual exclusion, progress and bounded waiting all hold. The price is still spinning, plus an O(n) scan executed while holding the lock.

Purpose

Swap (also called exchange) is the second standard atomic instruction. Where Test-and-Set writes the constant true and returns the old value, Swap exchanges the contents of two boolean variables in one uninterruptible step. That extra flexibility lets a process both ask for the lock and remember what it got, in a single memory transaction.

The instruction and the variables

void swap(boolean *a, boolean *b) {   /* executes ATOMICALLY */
      boolean temp = *a;
      *a = *b;
      *b = temp;
}

Pseudocode — including the line exactly as printed in the 2017 answer

do {
      var = true;
      while (var == true)                 /* printed verbatim: while (var == true) swap(lock, var); */
            swap(&lock, &var);
      /* CRITICAL SECTION */
      lock = false;                       /* exit */
      /* REMAINDER SECTION */
} while (true);

Read it. The process seeds its local var with true and keeps exchanging it with lock. After one swap, lock holds true — so the next caller will fail too — and var holds whatever lock held beforehand. The loop ends only when the value received is false, i.e. only when this process found the region free and has just marked it busy. Exiting is the plain store lock = false.

Why it works, and what it costs

• Mutual exclusion: exactly one caller can receive false from the exchange, because the swap is atomic — the winner writes true into lock in that same step, so a simultaneous loser necessarily reads back true.
• Progress: when the holder stores lock = false, the next spinning swap returns false and that process enters.
• Bounded waiting: no. As with the plain Test-and-Set loop, winners are chosen by the memory bus rather than by a queue, so an overtaken process can starve; the waiting[] construction of the previous card repairs it in the same way.
• Cost: every failed spin still performs a memory write (it pushes true back into lock), so on a shared bus the loop generates far more traffic than a read-only spin would.

Definition. A semaphore S is an integer variable that, apart from initialisation, can be accessed only through two standard atomic operations, wait() and signal() — Dijkstra’s original names P() and V(). It is a synchronisation tool the OS uses to control concurrent access to a shared resource: the integer counts how many entries are still permitted, and a process that finds the count exhausted is kept out — and, in the correct implementation, put to sleep.

wait(S)   /* P(S) */  { /* test-and-decrement: MUST be atomic */ }
signal(S) /* V(S) */  { /* increment                             */ }

The semantics in words: wait(S) blocks until S > 0 and then decrements S by one — “spend one permit”. signal(S) increments S by one — “return one permit”. Only initialisation touches S directly; no other code may read or write it.

Implementation 1 — the busy-wait version (as printed in your papers)

wait(S)   {  while (S <= 0) ;   /* spin, doing nothing */   S--;   }
signal(S) {  S++;   }

Read it. wait refuses to proceed while the count is zero or negative: it sits in an empty while loop re-testing S, and only when S is positive does it decrement and fall through. signal simply adds one, which releases the next waiting process. This version is the one printed for Nov-2023 Q.1(e) — but the spinning is precisely busy waiting, and the whole while (S<=0); S--; sequence is not atomic unless something makes it so: two processes can both see S = 1 and both decrement, driving S to −1 and letting both enter.

Why atomicity of wait/signal is the whole answer — the 2016 proof

The 2016 paper asks you to show that if wait and signal are not executed automatically, mutual exclusion may be violated. Let S = 1 guard one critical region, and suppose wait is split into “test” and “decrement”. P₀ tests (S > 0, true) and is preempted; P₁ now tests (still true), decrements to 0 and enters; P₀ resumes and completes only its decrement (S = −1) and also enters. Both are inside — mutual exclusion broken — and S has silently gone negative. The fix is exactly what the blocking implementation below does: make test-and-decrement one indivisible action, by disabling interrupts around it in the kernel or by using an atomic hardware instruction.

Types of semaphores

Implementation 2 — the correct blocking implementation (no busy waiting)

To stop the spinning, the semaphore is made a record holding the integer plus a queue of blocked processes, and both operations are executed with interrupts disabled so that they are atomic:

typedef struct {
      int              value;
      struct process  *list;      /* wait queue of blocked PCBs */
} semaphore;

wait(semaphore *S) {
      S->value--;
      if (S->value < 0) {                  /* no permit was left      */
            add this process to S->list;    /* park it on the queue    */
            block();                        /* give up the CPU         */
      }
}

signal(semaphore *S) {
      S->value++;
      if (S->value <= 0) {                 /* somebody is parked      */
            remove a process P from S->list;
            wakeup(P);                      /* put P back on ready queue */
      }
}

Read it carefully — the sign convention is the trick. wait decrements first. If the result is non-negative, a permit existed and the process just continues — no queueing, no sleep. If the result is negative, this process has taken a permit that belonged to somebody else, so it adds itself to S->list and calls block(), which hands the CPU to the scheduler. signal likewise increments first; a result ≤ 0 means a permit that was owed has now come back, so it removes one PCB from the queue and wakeup()s it into the ready queue. A negative value is therefore exactly the number of blocked processes: value = −3 means three processes are parked on this semaphore’s queue.

The queue’s discipline is what buys bounded waiting: a FIFO wait queue bounds how long any process can be held. And because block()/wakeup() manipulate kernel lists, they too must be protected against races — hence “with interrupts disabled”. This is the sleep-lock construction the OS actually uses, and it is the version relied on by the producer–consumer and dining-philosopher solutions later on this page.

Semaphore vs critical region

A critical region (also called a critical section construct, or a critical statement) is a language-level mechanism: the shared variable is declared private to a type, and every statement that modifies it is textually wrapped in a critical x { … } block, so the compiler guarantees that at most one process executes any region protecting that same variable. The Dec-2024 answer illustrates it with exactly this fragment — the guarded statement being a bank update:

/* critical section */
balance = balance + 100;

In semaphore style the same update must be bracketed by hand with wait(mutex); … signal(mutex); — and forgetting any one of those calls is a bug.

Purpose

Some kernels supply only a binary semaphore (a mutex). The question asks you to build a counting semaphore of initial value K out of nothing but mutexes plus one ordinary integer — i.e. to show that the “count” is book-keeping, not hardware.

The variables

Pseudocode

/* down() = wait(),  up() = signal() — both on BINARY semaphores */

semaphore mutex = 1;
semaphore s     = 0;
int     delay   = 0;
int     K;                        /* the counting semaphore's value */

void waitCounting(void) {         /* acts as P(S) on a K-permit semaphore */
      down(&mutex);
      delay = delay + 1;
      if (delay <= K)                   /* a permit is still free  */
            up(&mutex);                 /* ... so just walk through */
      else {
            up(&mutex);                 /* NEVER sleep holding mutex */
            down(&s);                   /* ... queue on s instead     */
      }
      delay = delay - 1;
}

void signalCounting(void) {       /* acts as V(S) */
      up(&s);                       /* release one waiter, or bank a permit */
}

Walkthrough. Every arriving process first locks mutex and increments delay, so delay counts how many processes are at the counter. If that number is still within the K permits, it drops the mutex and proceeds — it has “consumed a permit”. Otherwise it releases the mutex before sleeping (critical: holding it while blocked would freeze everybody else out) and waits on s. A process leaving the resource executes up(&s), which wakes exactly one queued process — or, if none is queued, simply leaves s at 1 so the next arrival passes straight through. The closing line delay = delay - 1 is executed by a process when it resumes, which is what keeps delay equal to the number of processes actually standing at the counter.

Limitation to state: the construction is correct but heavier, and it is order-sensitive — up(&mutex) must happen before down(&s); reverse them and the sleeper keeps the guard and the whole system wedges.

Monitor — as printed in the Jul-2016 answer: “In concurrent programming, a monitor is a synchronization construct that allows threads to have both mutual exclusion and the ability to wait (block) for a certain condition to become true. Monitors also have a mechanism for signalling other threads that their condition has been met. A monitor consists of a mutex (lock) object and condition variables …” At most one thread may be executing any method of the monitored object at a time.

monitor BankAccount {
      double balance = 0;
      condition enough;                  /* a condition variable */

      procedure deposit(double x) {
            balance += x;
            enough.signal();             /* wake a waiting withdrawer */
      }
      procedure withdraw(double x) {
            while (balance < x)         /* wait for a CONDITION, not a permit */
                  enough.wait();         /* releases the monitor lock while waiting */
            balance -= x;
      }
}

Read it. The programmer writes ordinary procedures; the compiler hides the wait(mutex)/signal(mutex) pair around every entry and exit. The only explicit synchronisation left is on a condition variable, and enough.wait() both blocks the caller and releases the lock — something a semaphore cannot do on its own.

The Jul-2016 answer also records the two properties worth quoting: a monitor provides mutual exclusion plus the ability to block until a condition becomes true, and at most one thread may be executing any of its methods at a time.

Definition. Printed wording of the Nov-2023 answer: busy waiting is a synchronisation technique in which a process waits and continuously checks the entry condition; it is also called busy looping or spinning. The process is ready as far as the scheduler is concerned — it is running, executing a loop that does nothing but re-read a shared variable hoping it has changed.

The Dec-2024 answer illustrates it with exactly this fragment — a process holding no lock, polling a flag instead of sleeping:

while (lock == 1) {
      /* do nothing – just keep checking */
}

Read it: as long as somebody else holds the lock, this loop consumes a whole time slice doing nothing useful. Where the lock holder is on another core that is tolerable; where the lock holder is ready but not running on the same single CPU, the spinner is actively preventing the holder from finishing — the worst case, called priority inversion by spinning.

What it costs

• CPU cycles burned by every waiting process, which is cycles nobody else can use — throughput falls even though nothing is “blocked”.
• Memory-bus traffic: each spin re-reads (and with Test-and-Set / Swap re-writes) the same lock word, slowing the very process that holds it.
• Unfairness: spinning gives no ordering, so a process may be overtaken indefinitely — the bounded-waiting failure of Section F.

“Can busy waiting be avoided altogether?” — the honest answer is no

Busy waiting can be avoided, but only at the cost of blocking, and blocking is not free: putting a process to sleep means saving its context, moving it to a device or semaphore queue, later waking it, placing it on the ready queue and performing at least one context switch back. If the lock will be released in a few hundred nanoseconds, all that work costs far more than a short spin would have. So the question “avoided altogether?” has a two-part answer: (i) yes — replace the spin loop with a wait queue, which is exactly the blocking semaphore of Section G; (ii) no — because some form of waiting is unavoidable whenever a resource is contested, and for very short critical sections spinning is strictly cheaper. On a uniprocessor it is worse than useless for a long wait, because the spinner starves the process it is waiting for; on a multiprocessor the holder runs in parallel, so a brief spin is often the best policy.

The four methods of avoiding busy waiting (as printed in Dec-2024)

“How to overcome busy waiting using semaphore operations” (Nov-2023, 2 marks)

Give the two implementations side by side and name the change. The busy-wait definition is wait(S){ while(S<=0); S--; } signal(S){ S++; } — the empty while is the spin. The blocking definition replaces that loop with a queue operation: wait(S){ S->value--; if (S->value < 0) { add this process to S->list; block(); } } and signal(S){ S->value++; if (S->value <= 0) { remove a process P from S->list; wakeup(P); } }. The spin test becomes a single arithmetic test plus a scheduler call, so the waiting process is no longer on the CPU.

The spinlock trade-off — which to pick

The problem. Two processes share a fixed-size buffer and cooperate: the producer generates items and drops them into the buffer; the consumer removes items one at a time and processes them. Three constraints make it non-trivial: the consumer must not take from an empty buffer, the producer must not write into a full buffer, and the two must never update in / out / counter at the same instant — that last one is a plain race condition of Section A.

The bounded buffer as a circular array

#define N 6                     /* buffer size */
item   buffer[N];
int    in  = 0;                 /* next free slot for the producer */
int    out = 0;                 /* next full slot for the consumer */
int    counter = 0;             /* number of items currently in the buffer */

Read it. in and out are indices, not pointers: after writing at slot N−1 the producer wraps to slot 0 with in = (in + 1) % N, and the consumer does the same with out. counter is the shared item count — and because counter++ and counter-- are exactly the read–modify–write pattern of Section A, the naive one-lock version of this code has the classic lost-update bug (counter stuck at 1 while both slots are filled, so the consumer reads garbage).

Solution using three semaphores

semaphore mutex = 1;      /* guards the buffer itself   */
semaphore empty = n;      /* n free slots at the start  */
semaphore full  = 0;      /* no items at the start      */

PRODUCER                          CONSUMER
while (true) {                    while (true) {
   item = produce();
   wait(empty);   /* a slot free? */   wait(full);    /* an item ready? */
   wait(mutex);   /* alone in buf */   wait(mutex);
   buffer[in] = item;                  item = buffer[out];
   in = (in + 1) % n;                  out = (out + 1) % n;
   signal(mutex);                      signal(mutex);
   signal(full);  /* announce item  */  signal(empty); /* a slot freed */
   consume(item);                      process(item);
}                                   }

Walkthrough. The producer first spends an empty permit; if all n slots are occupied empty is 0 and it blocks there — it never even touches the buffer. Only then does it take mutex, so no other updater is inside. It writes the item, advances in modulo n, releases mutex, and finally signals full, which is what wakes a consumer that had been parked on an empty buffer. The consumer runs the mirror image: spend a full permit, lock, take the item at out, advance, unlock, and signal empty to hand a slot back to a parked producer. The two counting semaphores therefore carry the buffer’s state between them — every item in the buffer is a spent empty permit that has not yet been spent again as full, so empty + full ≤ n, with equality whenever no process is half-way through its pair of waits.

Extending the answer: for k producers and m consumers the same three semaphores work unchanged — mutex serialises the buffer, while empty/full count slots and items for everybody. For the unbounded version the empty semaphore is unnecessary (a slot is always available) and only full plus mutex remain.

Problem statement — as printed

The problem is due to E. W. Dijkstra (“Co-operating Sequential Processes”). Printed wording: “There is a dining room containing a circular table with five chairs. At each chair is a plate, and between each plate is a single chopstick. In the middle of the table is a bowl of spaghetti. Near the room are five philosophers who spend most of their time thinking, but who occasionally get hungry and need to eat so they can think some more. In order to eat, a philosopher must sit at the table, pick up the two chopsticks to the left and right of a plate, then serve and eat the spaghetti on the plate.”

The rules printed alongside it: a philosopher may THINK indefinitely; every philosopher who EATs will eventually finish; chopsticks may be PICKED UP and PUT DOWN in either order and non-deterministically, but those are atomic actions, and two philosophers cannot use a single CHOPSTICK at the same time. The task is to design a protocol satisfying the liveness condition “any philosopher who tries to EAT, eventually does.”

The naive pseudocode — as printed in the papers

process P[i]
  while true do
  {  THINK;
     PICKUP(CHOPSTICK[i], CHOPSTICK[i+1 mod 5]);
     EAT;
     PUTDOWN(CHOPSTICK[i], CHOPSTICK[i+1 mod 5])
  }

Read it. Each of the five processes THINKs, then atomically picks up its left chopstick CHOPSTICK[i] and its right one CHOPSTICK[i+1 mod 5], EATs, and puts both down. The mod 5 is what wraps philosopher 4’s right-hand chopstick back to chopstick 0.

The semaphore statement of the same protocol

semaphore chopstick[5];        /* every one initialised to 1 = "on the table" */

do {
      wait(chopstick[i]);                 /* pick up the LEFT  one  */
      wait(chopstick[(i + 1) % 5]);       /* pick up the RIGHT one  */
      /* EAT */
      signal(chopstick[i]);               /* put the LEFT  back */
      signal(chopstick[(i + 1) % 5]);     /* put the RIGHT back */
      /* THINK */
} while (true);

Walkthrough. A chopstick is modelled as a binary semaphore: wait takes it (only one philosopher can succeed), signal returns it. Mutual exclusion per chopstick is therefore perfect — two philosophers can never hold the same stick, which is the rule the problem states. That is precisely the problem: the protocol guarantees the wrong thing. It guarantees exclusion but nothing about progress for the group.

Why it deadlocks

Suppose all five philosophers become hungry at roughly the same instant and all five execute their first wait. Each grabs its left chopstick — all five succeed, because each left chopstick is unique to that philosopher. Now all five execute their second wait for the right chopstick, and each of those sticks is exactly the neighbour’s left stick, which is already held. Every philosopher holds one resource and waits for one held by the next: a circular wait round the whole table, nobody can eat, nobody puts a stick down, and the system is wedged with five hungry processes and a full bowl. As the printed answer puts it, you “will quickly encounter the same deadlock and livelock scenarios we saw in the mutual exclusion problem, but you will quickly see in this case that mutual exclusion is too primitive a synchronization mechanism for solving this problem.”

Livelock is the mirror-image failure: suppose instead every philosopher puts down its left stick when the right one is unavailable, waits a moment, and tries again in the same synchronised rhythm. They then repeat the pickup simultaneously forever — all are active, all are making “effort”, and none ever eats. So the fix must break one of the four deadlock conditions, usually circular wait.

Three standard fixes

Fix 1 — asymmetric pickup (odd–even). Make odd-numbered philosophers take the right chopstick first. Two neighbours can then never both hold the stick between them, so a cycle around the table cannot form; the circular-wait condition is destroyed.

do {
      if (i % 2 == 0) {                        /* even: left then right  */
            wait(chopstick[i]);
            wait(chopstick[(i + 1) % 5]);
      } else {                                 /* odd:  right then left  */
            wait(chopstick[(i + 1) % 5]);
            wait(chopstick[i]);
      }
      /* EAT */
      signal(chopstick[i]);
      signal(chopstick[(i + 1) % 5]);
      /* THINK */
} while (true);

Fix 2 — allow at most four philosophers at the table. With n seats but only n − 1 diners, at least one stick always stays free, so at least one philosopher can complete a pair and eventually eat; mutual exclusion over the room breaks the cycle by limiting concurrency. This is the answer the notes record as the “K philosophers” variant.

semaphore roomService = 4;        /* at most FOUR may sit down  */

do {
      wait(roomService);          /* 1. claim a seat             */
      wait(chopstick[i]);         /* 2. then take both sticks    */
      wait(chopstick[(i + 1) % 5]);
      /* EAT */
      signal(chopstick[i]);
      signal(chopstick[(i + 1) % 5]);
      signal(roomService);        /* 3. leave the table          */
      /* THINK */
} while (true);

Fix 3 — an atomic pickup wrapper. The problem says PICKUP is a single atomic action, so implement it as one: wrap the two waits inside a further mutex so that no other philosopher can be partway through a pickup while you are doing yours. Then a partial pair can never be observed, and the all-five-holding-their-left-stick state is unreachable.

semaphore chopstick[5];           /* all 1 */
semaphore pickup    = 1;          /* makes the pair acquisition atomic */

do {
      wait(pickup);               /* only one philosopher picks up at a time */
      wait(chopstick[i]);
      wait(chopstick[(i + 1) % 5]);
      signal(pickup);             /* release BEFORE eating, not after */
      /* EAT */
      signal(chopstick[i]);
      signal(chopstick[(i + 1) % 5]);
      /* THINK */
} while (true);

Note the one price of fix 3: only one philosopher may collect sticks at a time, so pickup becomes a bottleneck — the cleanest statement of the trade-off is that we have bought liveness by giving up some concurrency. The equivalent high-level formulation is the monitor / state-array solution (int state[5] with test(i) checking that both neighbours are not eating, and per-philosopher condition variables), which is the “answer code” the older book prints for the 2017 dining-philosophers program.

Problem statement

A barbershop has one barber, one barber chair, and a waiting room with a fixed number N of chairs. The rules are:

1. If there are no customers, the barber goes to sleep in the barber chair and must not be woken except by the arrival of a customer.
2. A customer who arrives wakes the barber if he is asleep and sits in the barber chair; the barber cuts that customer’s hair and then repeats the cycle.
3. A customer who arrives while the barber is busy sits in the waiting room if a chair is free.
4. A customer who arrives and finds all N waiting chairs occupied leaves the shop and does not come back.
5. Only one haircut may be in progress at a time — the barber is a single, non-shareable resource.

The technical difficulty is the handshake: the barber must sleep only while there really is nobody to serve, must be woken by exactly one arriving customer, and must not race with a customer who arrives at the same instant the previous haircut ends. A naive pair of tests such as “barber: if (waiting > 0) …” and “customer: if (barber asleep) …” produces both lost customers (asleep barber, waiting count already read as 0) and a barber waiting for a customer who is waiting for the barber.

The shared data

Pseudocode

#define CHAIRS 5                     /* seats in the waiting room    */
semaphore customers = 0;             /* how many clients to serve    */
semaphore barbers   = 0;             /* how many haircuts ready      */
semaphore mutex     = 1;             /* protects "waiting"           */
int       waiting   = 0;

/* ---------------- BARBER ---------------- */
while (true) {
      wait(customers);                /* sleep until a customer arrives   */
      wait(mutex);
      waiting = waiting - 1;          /* one fewer in the waiting room    */
      signal(barbers);                /* "come and sit down"              */
      signal(mutex);
      cut_hair();                     /* OUTSIDE the mutex — it is slow   */
}

/* ---------------- CUSTOMER -------------- */
wait(mutex);
if (waiting < CHAIRS) {
      waiting = waiting + 1;          /* take a seat                     */
      signal(customers);              /* wake the barber if asleep       */
      signal(mutex);
      wait(barbers);                  /* wait for the chair to be free   */
      get_haircut();
} else {
      signal(mutex);                  /* no seat: release lock and leave  */
}

Explanation of the handshake. The barber’s very first line, wait(customers), is the sleep: with no customer, the counting semaphore is 0, so the barber is put on the semaphore’s wait queue by the blocking implementation of Section G and consumes no CPU at all — no busy waiting. A customer who arrives takes mutex, finds a free chair, increments waiting, and executes signal(customers); that increments the count and wakes exactly one sleeping barber. The barber then decrements waiting, signals barbers to say “the chair is ready”, drops mutex, and only then starts cutting — deliberately outside the mutex, because a haircut is long and holding mutex through it would block arriving customers from even checking for a seat. Symmetrically the customer parks on wait(barbers) and is released into the chair. If the waiting room is already full the customer releases mutex and walks out, never touching either synchronisation semaphore.

Why it is a good exam topic to have read once: it combines everything on this page — a shared variable protected by a binary semaphore, two counting semaphores used for direction of synchronisation rather than counting resources, blocking instead of busy waiting, and a producer–consumer-shaped buffer (the waiting room) between an unbounded producer (arrivals) and a single slow consumer (the barber). If it is ever asked, the marks are in the handshake; write the two wait/signal pairs and explain why cut_hair() sits outside the mutex.