Synchronisation

מילון מונחים

English	משמעות
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.

English

The lost update

Two threads run counter = counter + 1 on counter = 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 —

רמת קושי 1/5 · 100 מטבעות + בונוס קטן בהשלמה הראשונה היום

English

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-set meets 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 —

רמת קושי 1/5 · 100 מטבעות + בונוס קטן בהשלמה הראשונה היום

English

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.

Example

A single-core machine still races: preemption between the read and the write is enough.

{exercise:uni-cs0703-deadlock}

אימונים

Ordering all lock acquisitions breaks —

רמת קושי 1/5 · 100 מטבעות + בונוס קטן בהשלמה הראשונה היום