Synchronisation
Introduit| English | Sens |
|---|---|
| interleaving | An ordering of steps from multiple tasks that preserves each task's required internal order. |
| lock | A synchronisation mechanism used by participating tasks to control access to shared resources. |
| mutual exclusion | Ensuring that at most one participating task enters a protected critical section at a time. |
| spin/spɪn/ | Repeatedly checking for a condition while continuing to consume processor time. |
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 —
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
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 —
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
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 —
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
A fixed order makes a cycle impossible — the cheapest condition to break.