CRITICAL SECTION (critical region) a segment of code that accesses SHARED data and must not be executed by more than one process at a time. Note what it is NOT: it is not "code that uses a variable". A local variable needs no protection. The definition requires BOTH sharing AND at least one writer. read-only sharing → no critical section needed each process own copy → no critical section needed shared + any writer → critical section RACE CONDITION a situation where the RESULT depends on the relative timing or interleaving of operations. The output is not a function of the input alone. MUTUAL EXCLUSION (mutex) the property that at most one process is inside its critical section at any instant. It is the requirement; a lock is one mechanism for achieving it. THE FOUR-PART STRUCTURE every solution has: do { ENTRY SECTION request permission to enter CRITICAL SECTION access the shared data EXIT SECTION release permission REMAINDER everything else } while (true); Bugs hide in the entry and exit sections, not the critical section itself. Forgetting to release in the exit section is how a deadlock is created; releasing too early is how mutual exclusion is lost. THE THREE REQUIREMENTS, restated (from the concurrency topic): 1. MUTUAL EXCLUSION one at a time 2. PROGRESS if nobody is inside, someone can enter 3. BOUNDED WAITING a waiting process eventually gets in

THE PROBLEM: 8 threads each increment a shared counter 200,000 times. Expected total 1,600,000. All figures MEASURED on this machine (10 cores, Darwin arm64). approach result correct? time ──────────────────────────────────────────────────── plain counter++ 1,000,000 NO 0.2 ms atomic_fetch_add 1,600,000 yes 14.7 ms pthread_mutex 1,600,000 yes 28.8 ms per-thread + final sum 1,600,000 yes 0.1 ms READ THAT TABLE CAREFULLY — it contains three lessons. 1. THE BROKEN VERSION IS THE FASTEST. 0.2 ms and wrong. Any benchmark that does not check correctness will happily recommend the racy code. Correctness first, then measure. 2. THE ATOMIC IS 2× FASTER THAN THE MUTEX (14.7 vs 28.8 ms). atomic_fetch_add is ONE instruction with a lock prefix; pthread_mutex_lock is a function call plus a CAS plus potential blocking. For a single-word update, prefer the atomic. 3. NOT SHARING BEATS EVERYTHING — 0.1 ms, faster than the racy version, and CORRECT. Each thread increments its own variable; the totals are summed once at the end. That is 288× faster than the mutex. WHY: with a shared counter, the cache line holding it must bounce between all 10 cores' caches on every increment — hundreds of cycles each time. With per-thread counters, each core writes only to its own cache line and never invalidates another's. The cost was never the lock; it was the CACHE COHERENCE traffic the sharing caused. This is the single most useful performance insight in concurrent programming: the question is not "which lock is fastest" but "can I avoid sharing at all". CAVEAT — FALSE SHARING: if the per-thread counters sit in the SAME cache line (an array of longs is 8 bytes apart, a cache line is 64–128 bytes), the coherence traffic returns even though the variables are logically separate. The fix is to pad each counter to its own cache line: struct { long v; char pad[120]; } counters[THREADS]; That is why the measured 0.1 ms could be even better with padding, and why "false sharing" is worth knowing by name.

1. DISABLING INTERRUPTS disable_interrupts(); critical section enable_interrupts(); ✔ trivially correct on a UNIPROCESSOR — no switch can occur ✗ USELESS on a multiprocessor: it stops interrupts on THIS core only; another core continues freely ✗ dangerous — a bug in the critical section freezes the machine ✗ cannot be given to user processes at all Used only inside the kernel, for very short sections. 2. LOCK VARIABLE (naive) while (lock == 1) ; /* wait */ lock = 1; /* acquire */ critical section lock = 0; ✗ BROKEN. The test and the set are two operations, so both processes can pass the while loop before either sets the lock. This is the same load-modify-store problem as counter++ — the lock itself has a race. 3. STRICT ALTERNATION (turn variable) ✗ violates PROGRESS: forces alternation even when the other process does not want to enter. 4. PETERSON'S ALGORITHM ✔ satisfies all three requirements for two processes ✗ needs memory barriers on real hardware (measured in the concurrency topic: ~50% of updates lost without them) ✗ awkward to extend beyond two processes (Bakery algorithm generalises it) 5. HARDWARE ATOMIC INSTRUCTIONS — what is actually used TEST-AND-SET, COMPARE-AND-SWAP, FETCH-AND-ADD ✔ correct, simple, works for n processes and n CPUs ✔ the foundation for every real mutex and semaphore SPINLOCK built on test-and-set: while (TestAndSet(&lock)) ; /* spin until acquired */ critical section lock = false; ✔ no context switch — right when the section is very short ✗ BUSY WAITING wastes CPU; right only when the expected wait is shorter than a context switch (~1–10 µs) ✗ does NOT guarantee bounded waiting on its own — an unlucky process can lose the race repeatedly 6. HIGHER-LEVEL PRIMITIVES (next topics) semaphores, mutexes, monitors, condition variables THE PRACTICAL RULE, in order of preference: 1. avoid sharing (per-thread data, immutability, message passing) — measured 288× faster than a mutex 2. use an atomic if a single word is enough — measured 2× faster than a mutex 3. use the library mutex — correct, portable, includes the right barriers 4. hand-roll a lock only inside a kernel, and only if you must

Mutual exclusion introduces a new failure mode: a high-priority process can be blocked, indirectly, by a low-priority one. LOW acquires the lock HIGH preempts LOW, needs the lock → BLOCKS MED preempts LOW (it does not need the lock) → HIGH now waits for MED, which has LOWER priority than it HIGH's wait is bounded only by how long MED runs, which is unbounded. Hence UNBOUNDED PRIORITY INVERSION. This is the Mars Pathfinder bug from the OS-types topic. The fix is PRIORITY INHERITANCE: while LOW holds a lock that HIGH wants, LOW temporarily runs at HIGH's priority, so MED cannot preempt it. HIGH's wait then becomes bounded by LOW's critical section length — which the programmer controls. THE THREE HAZARDS OF MUTUAL EXCLUSION, together: DEADLOCK two processes each hold what the other needs STARVATION a process is perpetually denied the lock PRIORITY a high-priority process blocked by a low one INVERSION All three are introduced BY the solution to the original problem. That is the recurring theme of this section: synchronisation does not remove difficulty, it relocates it — which is the real reason "avoid sharing" is the first rule rather than a micro-optimisation.