CONCURRENCY several tasks are IN PROGRESS at once. They may be interleaved on one CPU. It is a way of STRUCTURING a program. PARALLELISM several tasks EXECUTE at the same instant. It requires multiple CPUs. It is a property of the HARDWARE. Concurrency without parallelism: one core, time-sliced. Parallelism without concurrency: SIMD — one instruction on many data items. Both: this machine, 10 cores running 599 processes. Rob Pike's formulation: "concurrency is about dealing with many things at once; parallelism is about doing many things at once." WHERE CONCURRENCY COMES FROM — three sources, and all three produce the same hazards: 1. MULTIPROGRAMMING processes interleaved on one CPU 2. MULTIPROCESSING processes truly parallel on many CPUs 3. DISTRIBUTED processes on separate machines THE THREE CONTROL PROBLEMS concurrency introduces: MUTUAL EXCLUSION only one process may be in a critical section at a time DEADLOCK processes wait for each other forever STARVATION a process is perpetually denied access And underlying all three: RACE CONDITION the outcome depends on the ORDER in which operations interleave

The single most important fact in this topic: one line of high-level code is several machine instructions, and a switch can occur between any two of them. counter++; /* looks atomic, is not */ compiles to roughly: LOAD r1 ← [counter] read ADD r1 ← r1 + 1 modify STORE [counter] ← r1 write INTERLEAVE TWO THREADS AT THE WORST MOMENT: counter = 100 initially thread A: LOAD r1 ← 100 thread B: LOAD r1 ← 100 ← reads the SAME value thread A: ADD r1 = 101 thread B: ADD r1 = 101 thread A: STORE counter = 101 thread B: STORE counter = 101 ← one increment LOST two increments performed, counter advanced by ONE. MEASURED CONSEQUENCE (8 threads × 200,000 increments, expected 1,600,000) — the same binary run four times on this machine: run 1: 1,200,000 lost 400,000 (25.0%) run 2: 200,000 lost 1,400,000 (87.5%) run 3: 1,400,000 lost 200,000 (12.5%) run 4: 1,600,000 lost 0 ( 0.0%) ← CORRECT Run 4 is the frightening one. The buggy program produced the right answer. Nothing changed — same code, same machine, same command. The interleaving simply did not collide. WHY THAT MATTERS MORE THAN THE AVERAGE: · the bug may pass every test you write · it may pass a thousand runs and fail in production · it may behave differently under a debugger, whose timing differs — hence "Heisenbug" · a "fix" that appears to work may have only changed timing The only reliable defences are to REASON about the code, or to use a tool that detects the unsynchronised access itself rather than waiting for a wrong answer: clang -fsanitize=thread (ThreadSanitizer) valgrind --tool=helgrind Both flag the race even on a run that produces 1,600,000.

A correct mutual-exclusion mechanism must provide all three. Exam answers that give only the first are incomplete. 1. MUTUAL EXCLUSION at most one process in its critical section at a time. 2. PROGRESS if no process is in its critical section and some processes want to enter, one of them must be able to. Nothing may block a decision indefinitely. → this is what rules out solutions that deadlock when both processes are polite. 3. BOUNDED WAITING there is a limit on how many times other processes may enter before a waiting process gets its turn. → this is what rules out starvation. Plus two practical requirements: 4. no assumption about the RELATIVE SPEED of processes or the number of CPUs 5. a process outside its critical section must not block others THE STRUCTURE OF EVERY SOLUTION: do { entry section /* request permission */ critical section /* the shared resource */ exit section /* release permission */ remainder section /* other work */ } while (true); WHY NAIVE ATTEMPTS FAIL — the classic two-process cases: ATTEMPT 1: a shared `turn` variable while (turn != me) ; /* wait */ critical section turn = other; ✗ violates PROGRESS. It forces strict alternation, so if P0 does not want to enter, P1 cannot enter twice in a row — it is blocked by a process that is not even competing. ATTEMPT 2: two `flag` variables flag[me] = true; while (flag[other]) ; critical section flag[me] = false; ✗ DEADLOCK. Both set their flag, then both wait forever. Mutual exclusion holds; progress fails. ATTEMPT 3: flag then turn (Peterson's algorithm) — CORRECT flag[me] = true; turn = other; /* be polite */ while (flag[other] && turn == other) ; critical section flag[me] = false; ✔ satisfies all three requirements for two processes. The insight: `turn` breaks the tie when both flags are set, and setting turn = other means the LAST process to express politeness loses. Peterson's algorithm is correct on paper and NOT directly usable on modern hardware without memory barriers, because CPUs and compilers reorder memory operations. MEASURED PROOF on this machine (2 threads × 100,000 increments, expected 200,000): WITH proper atomics (atomic_store / atomic_load): run 1: 200000 CORRECT run 2: 200000 CORRECT run 3: 200000 CORRECT WITH plain `volatile int` instead — the same algorithm, barriers removed: run 1: 102956 WRONG run 2: 102351 WRONG run 3: 100743 WRONG Roughly half the increments lost — barely better than no synchronisation at all. The ALGORITHM is unchanged and provably correct; what fails is the assumption that memory operations become visible to the other thread in program order. THE LESSON: `volatile` is NOT a synchronisation primitive. It tells the compiler not to cache a value in a register; it says nothing about instruction reordering or cache coherence between cores. Every correct implementation needs explicit atomics or memory barriers: C11/C++11 atomic_store / atomic_load, std::atomic Java volatile (which DOES imply barriers in Java — the same keyword means something stronger there, a genuine cross-language trap) This is also why you should use the library mutex rather than hand-rolling Peterson's: pthread_mutex_lock already contains the correct barriers for your platform.

Software-only solutions like Peterson's are correct but slow and awkward for n processes. Hardware provides ATOMIC instructions instead. TEST-AND-SET — atomically read and set to true bool TestAndSet(bool *target) { bool old = *target; *target = true; return old; } /* lock acquire: */ while (TestAndSet(&lock)) ; /* spin */ COMPARE-AND-SWAP (CAS) — the general primitive int CAS(int *v, int expected, int newval) { int old = *v; if (old == expected) *v = newval; return old; } /* acquire: */ while (CAS(&lock, 0, 1) != 0) ; Both execute as ONE indivisible machine instruction, so no interleaving is possible inside them. On ARM64 they compile to LDXR/STXR pairs; on x86-64 to LOCK CMPXCHG. CAS IS THE FOUNDATION OF EVERYTHING: · mutexes, semaphores and condition variables are built on it · so are LOCK-FREE data structures, which use CAS in a retry loop instead of blocking: do { old = *p; new = f(old); } while (CAS(p,old,new) != old); · so are atomic counters: __atomic_fetch_add is one CAS-like instruction, which is why the correct fix for the counter race can be a single instruction rather than a mutex SPINNING vs BLOCKING: SPIN LOCK busy-wait in a loop. Wastes CPU, but avoids the context-switch cost. Correct choice when the critical section is SHORTER than a context switch (~1–10 µs) — which is why kernels use spinlocks internally. BLOCKING the process sleeps and is woken on release. Costs two context switches, but the CPU does useful work meanwhile. Correct for longer waits. Modern mutexes are ADAPTIVE: spin briefly, then block. That gets the best of both without the programmer choosing. THE ABA PROBLEM — a real CAS pitfall worth knowing: a value changes from A to B and back to A between your read and your CAS. The CAS succeeds because the value matches, but the world changed underneath you. The standard fix is a version counter alongside the value — exactly the optimistic-locking pattern from the database concurrency topic.