SyntaxPilot
Courses/CS Fundamentals for Placements/Lesson 24
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

CS Fundamentals for Placements · Lesson 24 of 90

Synchronization 1: race conditions and the critical-section problem

race condition (live demo)shared variablecritical sectionentry and exit sectionsremainder sectionrequirements (mutual exclusion, progress, bounded waiting)lock variable failurestrict alternationPeterson's solutionDekker's algorithmdisabling interrupts

These are the notes for CS Fundamentals for Placements, episode 24. For three episodes the scheduler decided which thread runs when, switching threads at any moment. Today that freedom bites back: when two threads share data, a switch at the wrong moment gives a wrong answer. You will see a race condition live, name the critical section and its entry, exit and remainder sections, define the three requirements (mutual exclusion, progress, bounded waiting), watch two obvious fixes fail live (a lock variable and strict alternation), invent Peterson's solution, watch a real CPU break it, fix it with a memory fence, and meet Dekker's algorithm and disabling interrupts. Every term is explained in plain words the first time it appears, and there is a full glossary at the end.

All program outputs below are real: every C program was compiled with gcc 13.3 -O2 (the SyntaxPilot compiler's flags) and run on Linux x86-64 with 2 CPUs on 2 November 2026. Programs with a race print different numbers on every run; the numbers shown are from one run.

Refresher from episode 20: a thread is a flow of execution inside a process; threads of one process share global variables and the heap. pthread_create starts a thread running a function; pthread_join waits for it to finish. A timer interrupt lets the OS switch threads at any instruction.

The six problems

Problem What it teaches
Two threads, wrong total Race condition; why counter++ is three steps
Which code is dangerous? Critical section; entry, exit, remainder sections
What is a correct fix? Mutual exclusion, progress, bounded waiting
An "engaged" sign The lock variable fails (check and set are two steps)
Take turns Strict alternation keeps exclusion but breaks progress
"After you" Peterson's solution; memory reordering and fences; Dekker; disabling interrupts

Problem 1: two threads, wrong total (race condition)

#include <stdio.h>
#include <pthread.h>

volatile int counter = 0;           // shared by both threads

void *work(void *arg) {
    for (int i = 0; i < 10000000; i++)
        counter++;                  // read, add 1, write back
    return NULL;
}

int main(void) {
    pthread_t a, b;
    pthread_create(&a, NULL, work, NULL);
    pthread_create(&b, NULL, work, NULL);
    pthread_join(a, NULL);
    pthread_join(b, NULL);
    printf("expected 20000000, got %d\n", counter);
    return 0;
}

Output (one run; every run differs):

expected 20000000, got 13966142

volatile tells the compiler to really read and write memory on every access, instead of keeping the value in a register (without it, -O2 can turn the loop into a single counter += 10000000 and hide the bug).

Why: counter++ is three machine steps

Step What the CPU does
load copy counter from memory into a register (a tiny storage slot inside the CPU)
add add 1 to the register
store write the register back to memory

One bad interleaving (counter starts at 5):

Thread T1 Thread T2 counter
1 load reg1 = 5 5
2 ← timer interrupt, switch 5
3 load reg2 = 5 5
4 add reg2 = 6 5
5 store counter = 6 6
6 add reg1 = 6 6
7 store counter = 6 6 (should be 7)

A race condition is a situation where the result depends on the exact timing (interleaving) of threads. It may give the right answer most of the time, so testing often misses it.

Real-life example: the last train berth sold twice. One berth is left. Clerk A checks: 1 free, starts the form. At the same moment clerk B checks: 1 free. Both book it; two passengers, one berth. The check and the booking were separate steps and someone squeezed in between. Real booking systems lock the seat while one clerk books it.

Problem 2: which code is dangerous? (critical section)

Real-life example: a single trial room.

Trial room Code
Inside the room, one person at a time Critical section: code that reads or writes shared data (counter++)
Check the door and lock it Entry section: code that asks permission to enter
Unlock as you leave Exit section: code that lets others in
Shopping around the store Remainder section: everything else
while (true) {
    entry section
        critical section
    exit section
    remainder section
}

The critical-section problem: design entry and exit sections so that threads cooperate correctly.

Problem 3: what is a correct solution? (three requirements)

Requirement Meaning Trial room
Mutual exclusion At most one thread is in its critical section at any time One person inside
Progress If no one is inside and some threads want in, one of them gets in in finite time; threads in their remainder section take no part in the decision A free room never stays locked because someone is out shopping
Bounded waiting After a thread asks to enter, there is a limit on how many times others may enter before it Nobody starves at the door

Plus: no assumptions about the relative speed of threads or the number of CPUs. (Mutual exclusion is about safety; progress and bounded waiting are about liveness, the guarantee that something good eventually happens.)

Problem 4: an "engaged" sign (lock variable, fails)

Real-life example: a train toilet's ENGAGED sign. Shared lock: 0 = free, 1 = taken.

while (lock == 1) { }   // entry: wait while taken
lock = 1;               //        take it
    critical section
lock = 0;               // exit: release

To see the bad timing on every run, the demo calls sched_yield() (give up the CPU, let another thread run) exactly where a timer interrupt could hit:

#include <stdio.h>
#include <pthread.h>
#include <sched.h>

volatile int counter = 0;
volatile int lock = 0;              // 0 = free, 1 = taken

void *work(void *arg) {
    for (int i = 0; i < 100000; i++) {
        while (lock == 1) { }       // entry: wait while taken...
        sched_yield();              // (a timer interrupt could hit here)
        lock = 1;                   // ...then take it
        int x = counter;            // critical section:
        sched_yield();              //   read, add, write back
        counter = x + 1;
        lock = 0;                   // exit: release
    }
    return NULL;
}

int main(void) {
    pthread_t a, b;
    pthread_create(&a, NULL, work, NULL);
    pthread_create(&b, NULL, work, NULL);
    pthread_join(a, NULL);
    pthread_join(b, NULL);
    printf("expected 200000, got %d\n", counter);
    return 0;
}

Output (one run):

expected 200000, got 153215

Why it fails:

T1 T2 lock
1 sees lock == 0, leaves the loop 0
2 ← switch 0
3 sees lock == 0, leaves the loop 0
4 lock = 1, enters 1
5 lock = 1, enters 1 — both inside

Checking and setting are two separate steps, so the lock itself has a race condition. Mutual exclusion is violated. (Next episode: hardware instructions that check and set in one step.)

Problem 5: take turns (strict alternation, breaks progress)

Real-life example: Riya and Aman share one cycle and must strictly alternate rides. They're never both on it (mutual exclusion holds), but if Aman is at tuition, Riya can't ride twice in a row even though the cycle is free.

#include <stdio.h>
#include <pthread.h>
#include <time.h>

volatile int turn = 0;              // whose turn: 0 or 1

void visit(int me, int times) {
    for (int k = 1; k <= times; k++) {
        time_t start = time(NULL);
        while (turn != me) {        // entry: wait for my turn
            if (time(NULL) - start >= 2) {
                printf("T%d stuck before visit %d: turn = %d\n", me, k, turn);
                return;
            }
        }
        printf("T%d in critical section (visit %d)\n", me, k);
        turn = 1 - me;              // exit: give the turn away
    }
}

void *t1(void *arg) { visit(1, 1); return NULL; }   // T1 needs it once

int main(void) {
    pthread_t b;
    pthread_create(&b, NULL, t1, NULL);
    visit(0, 3);                    // T0 (main thread) needs it 3 times
    pthread_join(b, NULL);
    return 0;
}

Output (the same on every run):

T0 in critical section (visit 1)
T1 in critical section (visit 1)
T0 in critical section (visit 2)
T0 stuck before visit 3: turn = 1
Requirement Strict alternation
Mutual exclusion ✓ only the turn holder enters
Progress ✗ a thread outside (finished, in its remainder section) blocks entry
Bounded waiting ✓ you wait at most one turn

It also forces both threads to run at the same pace (T0 T1 T0 T1 ...). The 2-second check is only there so the demo ends; real strict alternation would spin forever.

Problem 6: "after you" (Peterson's solution)

Real-life example: two people at a narrow doorway. Each says "I want to go through" (intent), then "after you" (politeness). If both say "after you", the one who said it last waits; the other walks through.

flag[me] = true;                          // I want to enter
turn = other;                             // after you
while (flag[other] && turn == other) { }  // wait only if you want in AND it's your turn
    critical section
flag[me] = false;                         // I'm done

Peterson published it in 1981 in a two-page paper, "Myths About the Mutual Exclusion Problem".

Why it satisfies all three (for two threads)

  • Mutual exclusion: if both want in, both flags are true, and turn holds only one value, so exactly one of them passes the while.
  • Progress: if the other thread doesn't want in, flag[other] is false and you enter immediately. Only threads that want in affect the decision.
  • Bounded waiting: if the other thread enters, exits and immediately wants back in, it sets turn = you first, so you go next. You wait at most one turn.

Live: the textbook version in C

Each thread loops: entry, counter++, exit, and counts its entries. After 2 seconds both stop; if the solution is correct, counter equals the number of entries.

The textbook writes the flags as bool. Without the header, gcc says:

main.c:5:10: error: unknown type name 'bool'
    5 | volatile bool flag[2], stop;              // flag[i]: thread i wants in
      |          ^~~~
main.c: In function 'work':
main.c:10:20: error: 'true' undeclared (first use in this function)
   10 |         flag[me] = true;            // I want to enter

In C, bool, true and false come from <stdbool.h> (C23 makes them keywords, but gcc 13's default is still C17). With the include:

#include <stdio.h>
#include <pthread.h>
#include <stdbool.h>
#include <unistd.h>
volatile int counter = 0, turn = 0;       // turn: who gives way
volatile bool flag[2], stop;              // flag[i]: thread i wants in
long entries[2]; int ids[2] = {0, 1};     // how often each thread got in
void *work(void *arg) {
    int me = *(int *)arg, other = 1 - me;
    while (!stop) {
        flag[me] = true;            // I want to enter
        turn = other;               // but you go first if you want
        while (flag[other] && turn == other) { }   // wait
        counter++;                  // critical section
        flag[me] = false;           // exit: I'm done
        entries[me]++;
    }
    return NULL;
}
int main(void) {
    pthread_t a, b;
    pthread_create(&a, NULL, work, &ids[0]);
    pthread_create(&b, NULL, work, &ids[1]);
    sleep(2); stop = true;          // let them race for 2 seconds
    pthread_join(a, NULL); pthread_join(b, NULL);
    long total = entries[0] + entries[1];
    printf("entered %ld, counter %d, lost %ld\n", total, counter, total - counter);
}

Output (two runs):

entered 1868567, counter 1868565, lost 2
entered 5905071, counter 5905037, lost 34

Most runs lose a few updates (on a busy machine some runs lose none, because the two threads rarely run at the same instant): both threads were sometimes inside together.

Why: the CPU reordered a write and a read

Peterson's proof assumes each thread's memory operations happen in program order and are seen by the other thread at once (sequential consistency). Real CPUs and compilers don't promise that. An x86 core puts writes into a store buffer (a small queue of writes not yet visible to other cores) and may let a later read go ahead before an earlier write becomes visible:

T0 (core 0) T1 (core 1)
1 flag[0] = true (sits in store buffer) flag[1] = true (sits in store buffer)
2 turn = 1 turn = 0
3 reads flag[1] → false (T1's write not visible yet) reads flag[0] → false
4 enters enters — both inside

Fix: a memory fence (memory barrier), an instruction that makes all earlier memory operations complete (become visible) before any later ones. In gcc: __sync_synchronize() (a full fence; on x86-64, gcc 13 compiles it to a locked instruction, lock orq $0, (%rsp), which has the same effect).

        flag[me] = true;            // I want to enter
        turn = other;               // but you go first if you want
        __sync_synchronize();       // fence: finish both writes first
        while (flag[other] && turn == other) { }   // wait

Output with the fence (two runs):

entered 2581025, counter 2581025, lost 0
entered 453323, counter 453323, lost 0

In real programs you use a mutex (lock) from the threads library, which already contains the right atomic instructions and fences. That is episode 25.

Dekker's algorithm (1962)

Dekker's algorithm was the first provably correct software solution to the two-thread critical-section problem. It also uses "wants" flags and a turn, with a back-off step: if both want in and it's not my turn, I lower my flag, wait for my turn, and raise it again.

#include <stdio.h>
#include <pthread.h>
#include <stdbool.h>
#include <unistd.h>

volatile int counter = 0, turn = 0;       // turn: who has priority
volatile bool wants[2], stop;
long entries[2];
int ids[2] = {0, 1};

void *work(void *arg) {
    int me = *(int *)arg, other = 1 - me;
    while (!stop) {
        wants[me] = true;
        __sync_synchronize();               // fence (needed on real CPUs)
        while (wants[other]) {              // the other wants in too
            if (turn != me) {               // and it's not my turn:
                wants[me] = false;          //   back off
                while (turn != me) { }      //   wait for my turn
                wants[me] = true;
                __sync_synchronize();
            }
        }
        counter++;                          // critical section
        turn = other;                       // give priority away
        wants[me] = false;
        entries[me]++;
    }
    return NULL;
}

int main(void) {
    pthread_t a, b;
    pthread_create(&a, NULL, work, &ids[0]);
    pthread_create(&b, NULL, work, &ids[1]);
    sleep(2);
    stop = true;
    pthread_join(a, NULL);
    pthread_join(b, NULL);
    long total = entries[0] + entries[1];
    printf("entered %ld times, counter = %d, lost %ld\n", total, counter, total - counter);
    return 0;
}

Output:

entered 48298662 times, counter = 48298662, lost 0

Peterson's version is shorter and easier to prove, which is why textbooks teach it first. Both work for two threads only (generalisations exist, such as Lamport's bakery algorithm for n threads), and both busy-wait: a waiting thread spins in a loop, burning CPU time.

Disabling interrupts

If no interrupt can occur inside the critical section, no switch can occur either: disable interrupts in the entry section, enable them in the exit section.

✓ Works on a single core; kernels use it for very short sections
✗ Useless on multicore: other cores keep running and can enter
✗ Dangerous for user programs: forget to re-enable, and the timer and devices are ignored; the machine stops responding
✗ Delays every interrupt, hurting response time

It is a privileged instruction (allowed only in kernel mode, episode 15). A user program that tries it is stopped by the CPU:

#include <stdio.h>

int main(void) {
    printf("disabling interrupts...\n");
    fflush(stdout);
    __asm__ volatile ("cli");       // x86: clear interrupt flag (privileged)
    printf("interrupts are off!\n");
    return 0;
}

Output (exit code 139):

disabling interrupts...
Segmentation fault

The CPU raised a protection fault, and Linux delivered SIGSEGV, killing the program.

The whole chain

Step Problem Invention
1 Lost updates Race condition: load, add, store interleave
2 Which code is dangerous? Critical section; entry, exit, remainder
3 What does correct mean? Mutual exclusion, progress, bounded waiting
4 An engaged sign Lock variable ✗ (check + set are two steps)
5 Take turns Strict alternation ✗ (breaks progress)
6 Intent + politeness Peterson ✓ on paper; + memory fence on real CPUs

Comparing the attempts

Solution Mutual exclusion Progress Bounded waiting Notes
Lock variable ✗ ✓ ✗ Check and set are separate
Strict alternation ✓ ✗ ✓ Forces alternating order
Peterson ✓ ✓ ✓ 2 threads; needs fences on modern CPUs; busy-waits
Dekker ✓ ✓ ✓ 2 threads; first correct (1962); busy-waits
Disabling interrupts ✓ (1 core only) ✓ depends Kernel only, short sections

Common mistakes

Mistake What you see Why Fix
Thinking counter++ is atomic expected 20000000, got 13966142 It's load, add, store Protect it with a critical section (a lock, or an atomic)
bool in C without the header error: unknown type name 'bool' bool comes from <stdbool.h> #include <stdbool.h>
Calling strict alternation correct T0 stuck before visit 3: turn = 1 It gives mutual exclusion only It fails progress
Peterson with plain variables on a multicore CPU lost 2 (differs every run) The CPU reorders a write and a later read A memory fence, or a real mutex
Forgetting volatile on a spin variable the loop never ends at -O2 The compiler reads the variable once volatile (or atomics)
Disabling interrupts in a user program Segmentation fault Privileged instruction Use OS locks

Mini project: measure the race

Change the race program to run with 2, 4 and 8 threads (an array of pthread_t), each adding 1,000,000. Print expected vs got and the percentage lost. Then wrap counter++ in Peterson's entry and exit (2 threads, with the fence) and confirm nothing is lost. Notice how much slower the protected version is: busy-waiting is expensive, which motivates the blocking locks of the next episodes.

Practice

1. Two threads each run counter++ 3 times (counter starts at 0). What is the lowest possible final value?

Solution

2. T1 loads 0 (and is switched out). T2 runs two full increments (counter = 2). T1 stores 1 (counter = 1). T2 loads 1 (switched out). T1 runs its remaining two increments (counter = 3). T2 adds and stores 2. Final value 2. The highest is 6.

2. In Peterson's entry, swap the two lines: turn = other; first, then flag[me] = true;. What breaks?

Solution

Mutual exclusion. T0 sets turn = 1. Switch. T1 sets turn = 0, flag[1] = true, sees flag[0] == false, enters. Switch. T0 sets flag[0] = true, checks flag[1] && turn == 1: turn is 0, so T0 enters too. Both inside. The flag must be raised before giving the turn away.

3. Show that strict alternation allows only the order T0 T1 T0 T1 ...

Solution

A thread enters only when turn == me, and on exit sets turn to the other thread. So after T0 exits, only T1 can enter next, and after T1, only T0. Starting with turn = 0, the order is forced to alternate.

4. Why can't user programs disable interrupts?

Solution

Disabling interrupts is a privileged instruction: only kernel mode may run it. A user program trying cli gets a protection fault (Segmentation fault above). Even if allowed, one buggy program could freeze the whole machine, and it wouldn't stop other cores.

5. Does Peterson's solution satisfy bounded waiting? With what bound?

Solution

Yes, with bound 1: when a thread is waiting, the other can enter at most once more, because on its next entry attempt it sets turn to the waiting thread.

6. Which requirement does a solution violate if two threads can wait forever even though nobody is inside?

Solution

Progress (this situation is also called deadlock when each waits for the other, or livelock when they keep reacting to each other without entering).

Quick quiz

// turn starts at 0
while (turn != me) { }
    critical section
turn = 1 - me;

Which requirement does this break? A. Mutual exclusion B. Progress C. Nothing, it's correct D. It doesn't compile

Answer

B. Progress. Only the turn holder enters, so mutual exclusion holds, but a thread that stays in its remainder section never gives the turn back, so a free critical section stays blocked (strict alternation).

Interview questions

  1. What is a race condition? A bug where the result depends on the timing of threads accessing shared data.
  2. Why is count++ not thread-safe? It is a load, an add and a store; another thread can run between them.
  3. Define critical section, entry, exit and remainder sections.
  4. What are the three requirements of a critical-section solution? Mutual exclusion, progress, bounded waiting.
  5. Why does a simple lock variable fail? Testing and setting it are two steps.
  6. What's wrong with strict alternation? It violates progress (and forces alternation).
  7. Explain Peterson's solution. Flags show intent, turn breaks ties politely; the last to set turn waits.
  8. Does Peterson's solution work on modern hardware? Not as written: CPUs reorder memory operations; it needs memory fences.
  9. What is a memory fence? An instruction ensuring earlier memory operations complete before later ones.
  10. Why not just disable interrupts? Only works on one core, privileged, risky, delays interrupts.

Glossary

Term Meaning in plain words Example
Shared variable Data more than one thread can read and write counter
Race condition The result depends on the timing of threads berth sold twice
Interleaving The order in which steps of different threads actually run load, load, store, store
Register A tiny storage slot inside the CPU reg1
Load / store Copy from memory to a register / back to memory counter++
volatile Tells the compiler to really access memory each time volatile int counter
Critical section Code that accesses shared data counter++
Entry section Code that asks permission to enter the while wait
Exit section Code that lets others in flag[me] = false
Remainder section Everything else shopping around
Critical-section problem Designing entry/exit sections so threads cooperate correctly —
Mutual exclusion At most one thread inside at a time one person in the trial room
Progress A free critical section is given to some waiting thread in finite time; outsiders don't block it no locked empty room
Bounded waiting A limit on how often others enter before you at most 1 in Peterson
Busy waiting / spinning Waiting in a loop that keeps checking while (...) { }
Lock variable A shared flag meaning free/taken ENGAGED sign
sched_yield() Give up the CPU so another thread can run demo pause
Strict alternation Threads enter strictly in turns via turn cycle rule
Peterson's solution flag (intent) + turn (politeness) for two threads, 1981 doorway
Dekker's algorithm First provably correct two-thread solution, 1962 wants + turn + back off
Sequential consistency Memory operations appear in program order to everyone Peterson's assumption
Store buffer A core's queue of writes not yet visible to other cores why Peterson broke
Memory reordering CPU/compiler running memory operations out of program order read before earlier write
Memory fence / barrier Forces earlier memory operations to complete first __sync_synchronize()
<stdbool.h> C header defining bool, true, false #include <stdbool.h>
Disabling interrupts Turning off interrupts so no switch can happen kernel, single core
Privileged instruction Allowed only in kernel mode cli
Segmentation fault (SIGSEGV) Signal that kills a program after an illegal access or instruction the cli demo
Mutex A lock from the OS/threads library; one holder at a time episode 25
Deadlock / livelock Threads wait for each other forever / keep reacting without progress episode 28

Summary

  • A race condition is when timing decides the result; counter++ is load, add, store, and steps from two threads can interleave.
  • The code touching shared data is the critical section, wrapped by entry and exit sections; the rest is the remainder section.
  • A correct solution needs mutual exclusion, progress and bounded waiting, with no assumptions about speed or CPU count.
  • A lock variable fails (check and set are two steps); strict alternation keeps exclusion but breaks progress.
  • Peterson's solution (flag + turn) satisfies all three for two threads on paper; on real CPUs it needs a memory fence.
  • Dekker's algorithm (1962) came first; disabling interrupts works only on one core and only in the kernel.

Next episode: Synchronization 2: hardware support and locks: atomic instructions, test-and-set, compare-and-swap, spinlocks, mutexes and memory barriers.