Synchronisation
Introduced| English | Meaning |
|---|---|
| interleaving | interleaving |
| lock | lock |
| mutual exclusion | mutual exclusion |
| spin/spɪn/ | spin |
The lost update
- Two threads run
counter = counter + 1oncounter = 5. Each reads, adds, writes; the interleaving R1 R2 W1 W2 leaves $6$, not $7$ — one update lost. With four increments each, every final value from $1$ to $8$ is reachable: seven increments can vanish.
{exercise:uni-cs0703-race}
Two threads each add 1 to counter = 5 with read-then-write. The unlocked interleaving R1 R2 W1 W2 leaves —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Both reads see 5; both writes store 6 — one increment lost.
What a lock must guarantee
- Mutual exclusion: one thread inside. Progress: someone enters if free. Bounded waiting: no thread starves. Peterson's algorithm meets all three in software;
test-and-setmeets them with one atomic instruction — but both spin, burning the CPU. - Semaphores and mutexes add the OS queue: the blocked waiter sleeps instead of spinning — which is why real systems layer them.
{exercise:uni-cs0703-lock}
A spinning lock burns CPU; a mutex queue avoids it by —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The blocked waiter sleeps in the OS queue instead of spinning.
Deadlock's four horsemen
- A holds L1 wants L2; B holds L2 wants L1. Deadlock needs mutual exclusion, hold-and-wait, no preemption, and circular wait — break any one and it cannot happen.
- The engineer's favourite to break: circular wait, by ordering the locks (always L1 before L2). Sleeping does not fix races; it only narrows the window.
A single-core machine still races: preemption between the read and the write is enough.
{exercise:uni-cs0703-deadlock}
Ordering all lock acquisitions breaks —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
A fixed order makes a cycle impossible — the cheapest condition to break.