Race conditions and the critical-section problem

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. Which parts of a process do its threads share? from Lesson 1.2.1
2. Which IPC method needs the processes to synchronize by themselves? from Lesson 1.2.2
3. Can the OS pre-empt a process in the middle of its work? from Lesson 2.2.1

1 · The Hook

You and a friend share a bank account with ₹100. You both deposit ₹50 at the same moment from two ATMs. Each ATM reads ₹100, adds 50 and writes back ₹150. One deposit has vanished. Nothing was broken; two careful machines simply interleaved at the wrong moment. Threads that share variables have exactly this problem, and Phase 3 is about stopping it. GATE asks for "all possible final values" of such code almost every year.

3 · Core Concept

Predict First — the answer

1 or 2. It is 2 if one thread finishes before the other starts. It is 1 if both read 0 before either writes back: one update is lost.

In plain words

A line like count++ looks like one step, but the CPU does it in three: read the value into a register, add 1, write it back. If another thread runs between those steps, it works with an out-of-date value and an update is lost. The fix is to let only one thread at a time run the code that touches the shared data.

1. Why count++ is not safe

count++ becomes three machine instructions:

load  R, count      (R = count)
add   R, 1          (R = R + 1)
store count, R      (count = R)

Each thread has its own registers (Lesson 1.2.1), and a pre-emption can happen between any two instructions. One bad interleaving, with count = 0:

Two increments, but count grew by only 1. This is a lost update.

2. Race condition

A race condition happens when the result depends on the exact order (timing) in which threads run. Races are hard to find by testing, because the bad order may happen only rarely.

3. The critical section

The critical section (CS) is the part of a program that uses shared data. Every process is organised like this:

entry section      (ask permission to enter)
   critical section
exit section       (announce that you left)
remainder section  (everything else)

The job of the entry and exit sections is to make sure the critical sections of different processes never overlap.

4. The three requirements for a correct solution

1. Mutual exclusion: at most one process is inside its critical section at any time.
2. Progress: if the critical section is free and some processes want to enter, one of them must get in; the choice cannot be delayed forever, and a process that is busy in its remainder section has no say in it.
3. Bounded waiting: once a process asks to enter, there is a limit on how many times other processes may enter before it gets its turn (so no process waits forever).

Also, a solution must not assume anything about the speed of the processes or the number of CPUs.

5. Finding all possible final values

Write each thread's statements as load / compute / store. Then:

• One after the other (no overlap) gives the "correct" value.
• Both load before either stores: whichever thread stores last wins, and the other update is lost.

Example: c = 5; thread 1 runs c++, thread 2 runs c--. Sequential → 5. Thread 1 stores last → 6. Thread 2 stores last → 4. Possible values {4, 5, 6}.

4 · Visual

Two threads, one shared variable, three steps each

Thread 1:  load ──── add ──── store
Thread 2:        load ──── add ──── store
                  ▲
                  both have read the same old value:
                  the store that happens last wins

5 · Worked Examples

Example 1 Easy

x = 0; two threads each run x++ once. List the possible final values.

Solution

1 or 2 (1 when both load 0 before either stores).

Example 2 Medium

D = 100. Thread 1 runs D = D + 20, thread 2 runs D = D − 50. Each statement is a load, a compute and a store. Possible final values?

Solution

One after the other: 70. Both load 100: if thread 1 stores last, 120; if thread 2 stores last, 50. So {50, 70, 120}.

Example 3 GATE

x = 0. Two threads each run x++ twice (a loop of 2). What is the smallest possible final value?

Solution

2. Thread 1 loads 0. Thread 2 runs its first x++ fully (x = 1). Thread 1 adds and stores 1 (thread 2's work is lost). Thread 2 loads 1 for its second x++. Thread 1 runs its second x++ fully (x = 2). Thread 2 adds and stores 2. It can't end at 1: every store writes at least 1, so once a thread has stored, x never drops below 1. That thread's second load reads at least 1, so its second store writes at least 2, and the very last store of all is some thread's second store.

6 · GATE Traps

• x++, x = x + 1 and x += 1 are not atomic (single-step) in general.
• The "lost update" needs both threads to read before either writes.
• Mutual exclusion alone is not enough: progress and bounded waiting matter too.
• Only shared variables matter; each thread's local variables and registers are private.

7 · Memory Hook

"Read, change, write: anyone can sneak in between. Guard the critical section."

8 · Connect the Dots

We know what a correct critical-section solution must do. The next lesson tries to build one using only ordinary variables, sees the simple attempts fail, and arrives at Peterson's solution.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 1 mark(s) — Final values

c = 5; thread 1 runs c++ and thread 2 runs c-- at the same time. How many different final values of c are possible?

Numerical answer: ________

Q2 · NAT · 1 mark(s) — Final values

x = 0; three threads each run x++ once. Smallest possible final value of x?

Numerical answer: ________

Q3 · NAT · 2 mark(s) — Loops

x = 0; two threads each run x++ three times. Smallest possible final value of x?

Numerical answer: ________

Q4 · MCQ · 1 mark(s) — Requirements

"A process that is running in its remainder section must not stop other processes from entering the critical section." This describes:

1. (A) atomicity
2. (B) bounded waiting
3. (C) progress
4. (D) mutual exclusion

Q5 · MSQ · 2 mark(s) — Requirements

Which of these must a correct critical-section solution guarantee?

1. (A) Mutual exclusion
2. (B) Every process runs at the same speed
3. (C) Progress
4. (D) Bounded waiting

10 · Rule Card

• x++ = load, add, store; a pre-emption can fall between them.
• Race condition: the result depends on timing. Lost update: both load before either stores; the last store wins.
• Structure: entry section, CS, exit section, remainder section.
• Requirements: mutual exclusion, progress, bounded waiting; no assumptions about speed.
• x++ in two loops of n ≥ 2 each from 0: minimum 2, maximum 2n.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

shared datarace conditionlost updatenon-atomic incrementcritical sectionentry, exit and remainder sectionsmutual exclusionprogressbounded waitingfinding all possible final values