Part 2 of 7 · 2 min read
The problem
Think of it this way. A bank has one ledger page for an account. Two clerks must each read the balance, change it and write it back. If both do so at the same time, one change is lost. The rule at the bank is: only one clerk may hold the page at a time. The analogy stops in one place: a clerk can see the other clerk with the page, while a thread cannot see what another thread is in the middle of doing.
In plain words: A race condition is a situation in which the result of a program depends on the order in which threads happen to interleave their steps (Level 2, page 4). It arises when two or more threads use shared data and at least one of them changes it. Take a withdrawal from a shared balance:
balance = balance - 30; /* really: load, subtract, store */
Two threads each withdraw 30 from a balance of 100. The correct result is 40. An unlucky interleaving gives 70:
| Step | Thread A | Thread B | balance in memory |
|---|---|---|---|
| 1 | load 100 into a register | 100 | |
| 2 | load 100 into a register | 100 | |
| 3 | subtract: register is 70 | 100 | |
| 4 | subtract: register is 70 | 100 | |
| 5 | store 70 | 70 | |
| 6 | store 70 | 70 |
One withdrawal vanished. The bank lost 30. The three steps of the update must not interleave with the same steps of another thread.
The stretch of code that touches the shared data is the critical section. Every thread that uses the data is written in the same form:
loop:
entry section <- ask for permission
critical section <- use the shared data
exit section <- give permission back
remainder section <- everything else
The critical-section problem is to design the entry and exit sections so that threads can share the data safely. For this level, the term "process" and "thread" can be used interchangeably, because the same reasoning applies to both.
Critical section
A critical section is a segment of code in which a thread accesses data that other threads may also access, so that the segment must not be executed by more than one thread at the same time.
Example: the load, subtract and store of balance = balance - 30 is a critical section, since two threads in it at once can lose an update.
Check yourself: 1. In the trace, which step makes the second withdrawal disappear? 2. What are the four parts of every thread's loop? 3. Why is code that only reads a constant not a critical section?