When two threads use the same data
A race condition is a bug where the result depends on which process or thread runs first. A deadlock is a state where processes wait for each other for ever. Both are hard to find, because the program may work a thousand times and then fail once.
This lesson shows how each one happens, and how a lock stops the first.
By the end of this lesson
Note
I can explain a race condition and a deadlock.
Key words
| Word | What it means |
|---|---|
| Thread | one line of work inside a process |
| Shared data | data that more than one thread can change |
| Race condition | a result that depends on which thread goes first |
| Lock | a flag that lets only one thread in at a time |
| Deadlock | threads that wait for each other for ever |
| Wait-for graph | a picture of who waits for whom |
The cells students fill in are left blank in this preview.
A race condition loses an update
Two threads in one process share a counter. To add 1, each thread does three small steps: read the counter, add 1, write the answer back.
If the system switches between the steps, both threads can read the same old value. Each then writes its own answer, and one of the additions is lost.
Worked example: two additions, one result
| Step | Thread A | Thread B | Counter in memory |
|---|---|---|---|
| 1 | reads 0 | 0 | |
| 2 | reads 0 | 0 | |
| 3 | adds 1, writes 1 | 1 | |
| 4 | adds 1, writes 1 | 1 | |
| Result | 1, not 2 |
The cells students fill in are left blank in this preview.
Replay the bad order and change it
# Two threads add 1 to a shared counter. Each one reads, then writes.
counter = 0
a = counter # thread A reads 0
b = counter # thread B reads 0, before A has written
counter = a + 1 # thread A writes 1
counter = b + 1 # thread B writes 1
print(counter) # prints 1, and two additions were made
# Move the line "b = counter" to just after "counter = a + 1".
# Run again. What does it print now, and why?
A common mistake
Warning
Many people think a race needs two cores running at the same instant. It does not. On one core the system can switch between the read and the write, which is enough. Any shared data that more than one thread changes needs protection.
A lock admits one thread at a time
The cure is a lock. A thread takes the lock before it touches the shared data, and gives it back afterwards. A second thread that asks for the lock must wait.
The three steps then form one unit that no other thread can enter. Both additions count, and the counter ends at 2.
The flock command shows a lock on a file. The first flock holds the lock while its command runs. The command inside asks for the same lock, and -n means refuse instead of wait.
Ask for a lock that is already held
flock -n $HOME/scratch/lab.lock sh -c 'flock -n $HOME/scratch/lab.lock true || echo refused'Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Remove the lock file
rm $HOME/scratch/lab.lockShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A deadlock needs four things at once
A deadlock happens when every thread in a group waits for a lock held by another thread in the group. None can go on. It needs four things together.
- Mutual exclusion: a lock has one holder.
- Hold and wait: a thread keeps a lock while it asks for another.
- No taking away: a lock is released only by its holder.
- A circle: the waiting forms a loop.
Worked example: two threads and two locks
| Step | Thread A | Thread B |
|---|---|---|
| 1 | takes lock 1 | |
| 2 | takes lock 2 | |
| 3 | asks for lock 2 and waits | |
| 4 | asks for lock 1 and waits | |
| Result | waits for B | waits for A |
The cells students fill in are left blank in this preview.
A circle in the graph is a deadlock
Draw each thread as a point. Draw an arrow from a thread to the thread that holds the lock it wants. This is the wait-for graph.
A circle of arrows is a deadlock. A thread that only waits for a circle, but is not in it, is stuck too, though not part of the loop.
The simplest prevention is to make every thread take locks in the same order.