--- title: 'Locks, Mutexes, and Semaphores' source: 'https://academia.sh/en/courses/operating-system-concepts/locks-and-mutual-exclusion' course: 'Operating System Concepts' language: en updated: '2026-08-17T18:08:19+00:00' license: 'CC BY-SA 4.0' --- # Locks, Mutexes, and Semaphores How mutual exclusion secures the critical section, the cost of contention in time and waiting steps, and what a semaphore gains and what it relaxes. The previous lesson set up the race condition and named the fix: mutual exclusion. Naming it is free; implementing it is not. This lesson first shows that exclusion genuinely works, then counts **how much it costs**. The axis of measurement should be stated up front. A lock does not speed a program up; it removes no work and shortens no step. The only thing it does is make some threads **wait**. Its cost is therefore measured in a single unit: **waiting steps**. ## What a Lock Guarantees A **lock** is an object that carries the right to enter a critical section. A lock that can be granted to only one thread at a time is called a **mutex**; its name comes directly from the guarantee it provides. The shared definition's `counter_run` routine carries this guarantee as an option: when `lock=True` is passed, the critical section is treated as indivisible. The measurement below sweeps the previous lesson's 20 interleavings twice. ```python def counter_run(pattern: list[int], lock: bool = False) -> int: """lock=True treats the critical section as indivisible.""" if lock: return 2 counter, local = 0, {0: None, 1: None} stage = {0: 0, 1: 0} for who in pattern: s = stage[who] if s == 0: local[who] = counter elif s == 1: local[who] = local[who] + 1 else: counter = local[who] stage[who] = s + 1 return counter def interleavings(a: int, b: int) -> list[list[int]]: if a == 0: return [[1] * b] if b == 0: return [[0] * a] return ([[0] + s for s in interleavings(a - 1, b)] + [[1] + s for s in interleavings(a, b - 1)]) everything = interleavings(3, 3) for lock in (False, True): results = [counter_run(d, lock) for d in everything] wrong = sum(1 for s in results if s != 2) print(f"lock {str(lock):5s} | interleavings {len(everything):2d} | distinct results {sorted(set(results))}" f" | wrong {wrong:2d} | wrong ratio {wrong / len(everything):.4f}") ``` ``` lock False | interleavings 20 | distinct results [1, 2] | wrong 18 | wrong ratio 0.9000 lock True | interleavings 20 | distinct results [2] | wrong 0 | wrong ratio 0.0000 ``` The difference is **different in kind** from what the quantum setting did in the previous lesson. The quantum narrowed the reachable interleaving set from 20 to 2; the lock does not narrow the set — it **makes all twenty of the twenty interleavings in the set correct**. The distinct result set goes from `[1, 2]` to `[2]`. Correctness no longer depends on the scheduler's setting. ## Measuring Contention The gain has been counted; now the cost. The shared definition's `locked_run` routine runs threads that each carry a critical section and a piece of non-critical work, and returns three numbers: time, waiting steps, and processor utilization. **CC7.** Acquiring and releasing a lock are treated as free; only waiting steps are measured. **CC8.** Each thread carries **10 steps** of critical section and **10 steps** of non-critical work. **CC9.** Non-critical work is fully parallel; the number of cores is not a limiting factor here. **CC10.** A waiting thread does not hold a core; waiting steps are counted but not counted as busy. **CC11.** The lock's queue is fair; no thread is locked out indefinitely. An increase in the number of threads entering the same critical section is called **contention**. The sweep raises contention from 1 to 16. ```python def locked_run(thread_count: int, critical: int, non_critical: int, permits: int = 1) -> dict: """Each thread does a `critical`-length critical section and `non_critical` steps of non-critical work. permits=1 is a mutex, permits>1 is a semaphore.""" remaining = [{"critical": critical, "outside": non_critical} for _ in range(thread_count)] inside, t, waiting, busy = [], 0, 0, 0 while any(k["critical"] or k["outside"] for k in remaining): active = 0 for j, k in enumerate(remaining): if k["outside"]: # non-critical work is parallel k["outside"] -= 1 active += 1 continue if not k["critical"]: continue if j in inside or len(inside) < permits: if j not in inside: inside.append(j) k["critical"] -= 1 active += 1 if not k["critical"]: inside.remove(j) else: waiting += 1 busy += active t += 1 return {"time": t, "waiting": waiting, "busy": busy, "utilization": round(busy / (t * thread_count), 4)} print("mutex (permits 1), critical 10 , non-critical 10") print(" threads time waiting utilization waiting/(n*(n-1))") for n in (1, 2, 3, 4, 6, 8, 12, 16): k = locked_run(n, 10, 10, 1) ratio = "-" if n == 1 else f"{k['waiting'] / (n * (n - 1)):.1f}" print(f" {n:7d} {k['time']:4d} {k['waiting']:7d} {k['utilization']:11.4f} {ratio:>17s}") ``` ``` mutex (permits 1), critical 10 , non-critical 10 threads time waiting utilization waiting/(n*(n-1)) 1 20 0 1.0000 - 2 29 9 0.6897 4.5 3 38 27 0.5263 4.5 4 47 54 0.4255 4.5 6 65 135 0.3077 4.5 8 83 252 0.2410 4.5 12 119 594 0.1681 4.5 16 155 1080 0.1290 4.5 ``` A single thread finishes its work in **20 time units**, with **0** waiting steps and utilization **1.0000**. Adding a second thread brings the time to **29**. With a fourth, **47**; with an eighth, **83**; with a sixteenth, **155**. This is the plainest form of the course's second claim: **a second thread slows the work down.** Two threads carry 40 steps of work in total and finish the single thread's 20 steps in 29 time units; because the critical sections are serialized, there is no speedup at all, only a 9-time-unit delay. ## Time Is Linear, Waiting Is Quadratic The two columns do not grow at the same rate, and the difference is measurable. The time column is linear: each thread adds **9 time units**. Because the critical sections are serialized, the total time approaches the sum of the serialized critical sections. The waiting column is quadratic. The last column shows this directly: the ratio of waiting steps to $n(n-1)$ is constant at **4.5** across every row. That is, waiting steps grow approximately as $4.5 \cdot n^2$. Doubling the thread count does not double the time, but it **quadruples** the waiting: **252** at 8 threads, **1080** at 16. The consequence is read in the utilization column: it drops from **1.0000** to **0.1290**. The sixteenfold power of sixteen threads cannot actually be used, because of the critical section. The design rule that follows rests on this number: **the way to lower contention is not a faster lock but a shorter critical section.** This claim cannot be left uncosted; it has to be counted. ## Measuring the Effect of Shortening the Critical Section The next sweep fixes the thread count at **8** and varies the critical section's share of the total work. **CC12.** Total work per thread is fixed at **20 steps**; what varies is only how many of those 20 steps fall in the critical section. ```python def locked_run(thread_count: int, critical: int, non_critical: int, permits: int = 1) -> dict: remaining = [{"critical": critical, "outside": non_critical} for _ in range(thread_count)] inside, t, waiting, busy = [], 0, 0, 0 while any(k["critical"] or k["outside"] for k in remaining): active = 0 for j, k in enumerate(remaining): if k["outside"]: k["outside"] -= 1 active += 1 continue if not k["critical"]: continue if j in inside or len(inside) < permits: if j not in inside: inside.append(j) k["critical"] -= 1 active += 1 if not k["critical"]: inside.remove(j) else: waiting += 1 busy += active t += 1 return {"time": t, "waiting": waiting, "busy": busy, "utilization": round(busy / (t * thread_count), 4)} TOTAL = 20 print("8 threads , 20 total steps per thread , mutex") print(" critical non-critical critical share time waiting utilization") for critical in (1, 2, 5, 10, 15, 20): k = locked_run(8, critical, TOTAL - critical, 1) print(f" {critical:8d} {TOTAL - critical:12d} {critical / TOTAL:14.2f}" f" {k['time']:4d} {k['waiting']:7d} {k['utilization']:11.4f}") ``` ``` 8 threads , 20 total steps per thread , mutex critical non-critical critical share time waiting utilization 1 19 0.05 20 0 1.0000 2 18 0.10 27 28 0.7407 5 15 0.25 48 112 0.4167 10 10 0.50 83 252 0.2410 15 5 0.75 118 392 0.1695 20 0 1.00 153 532 0.1307 ``` The work done is the same in every row: eight threads, 20 steps each. The only thing that changes is how many of those steps must be serialized. At a critical share of 0.50, the time is **83**; dropping the share to 0.25 gives **48**. Halving the critical section nearly halves the time. At a share of 0.05, the time becomes **20** — the same as a single thread. Eight threads can use their eightfold power only once the critical section shrinks to a single step. The reverse direction is just as clear. Raising the share from 0.50 to 0.75 takes the time from 83 to **118**, and to 1.00 takes it to **153**. Waiting steps rise from 252 to **532**. In work that is entirely critical section, concurrency gains nothing at all; it only produces waiting. The table's first row is also what later lessons rest on: work whose critical section is a **single step** produces no contention. When hardware executes such a step indivisibly, it is called an **atomic operation**, and its cost in this table is **zero**. ## The Semaphore A **semaphore** is a tool that can admit more than one thread into a critical section at the same time. The number it carries is the number of **permits** that can be granted. **CC13.** The permit count is fixed and does not change during a run. ```python def locked_run(thread_count: int, critical: int, non_critical: int, permits: int = 1) -> dict: """Each thread does a `critical`-length critical section and `non_critical` steps of non-critical work. permits=1 is a mutex, permits>1 is a semaphore.""" remaining = [{"critical": critical, "outside": non_critical} for _ in range(thread_count)] inside, t, waiting, busy = [], 0, 0, 0 while any(k["critical"] or k["outside"] for k in remaining): active = 0 for j, k in enumerate(remaining): if k["outside"]: k["outside"] -= 1 active += 1 continue if not k["critical"]: continue if j in inside or len(inside) < permits: if j not in inside: inside.append(j) k["critical"] -= 1 active += 1 if not k["critical"]: inside.remove(j) else: waiting += 1 busy += active t += 1 return {"time": t, "waiting": waiting, "busy": busy, "utilization": round(busy / (t * thread_count), 4)} print("semaphore: varying the permit count") print(" threads permits time waiting utilization") for n in (2, 4, 8, 16): for permits in (1, 2, 4): k = locked_run(n, 10, 10, permits) print(f" {n:7d} {permits:7d} {k['time']:4d} {k['waiting']:7d} {k['utilization']:11.4f}") ``` ``` semaphore: varying the permit count threads permits time waiting utilization 2 1 29 9 0.6897 2 2 20 0 1.0000 2 4 20 0 1.0000 4 1 47 54 0.4255 4 2 29 18 0.6897 4 4 20 0 1.0000 8 1 83 252 0.2410 8 2 47 108 0.4255 8 4 29 36 0.6897 16 1 155 1080 0.1290 16 2 83 504 0.2410 16 4 47 216 0.4255 ``` A semaphore with two permits brings two threads' time down from **29 to 20** and waiting from **9 to 0**. There is a regular pattern across the whole table: **the permit count divides contention.** Eight threads with two permits finish at **47**, the same as four threads with one permit. Sixteen threads with four permits also finish at **47**. Waiting steps do not divide the same way. Four threads with one permit produce **54** waiting steps, while eight threads with two permits produce **108**, and sixteen threads with four permits produce **216**. The time is equal, but the waiting is four times as much: **reaching the same time with more threads does not come for free.** ## A Semaphore Does Not Provide Mutual Exclusion The gain in the table invites an easy but wrong conclusion: raising the permit count both protects us and speeds us up. This is wrong. A semaphore with two permits, by definition, **admits two threads into the critical section at the same time.** The previous lesson's counter is not protected under this condition: with two threads inside, the read-increment-write triplets interleave again, and **18 of the 20 interleavings** again produce a wrong result. This is a return to this lesson's first measurement's `lock=False` row. So the two tools do different jobs. **A mutex is a correctness tool**; it protects the critical section. **A semaphore is a resource tool**; it limits how many threads can use a resource pool at the same time. If a pool has four connections, a semaphore with four permits is correct; a semaphore with two permits in front of a shared counter is **a bug**. The shared definition's fourth reading sums this up in one sentence: a semaphore with two permits brings 29 down to 20, but this is **relaxing mutual exclusion**, and it is not free. ## How Waiting Is Done In this measurement, a waiting thread does not hold a core (CC10). There is a second form of waiting: **busy waiting** — continuously polling whether the lock has become free. The shared definition's third reading makes remeasuring this option unnecessary: the polling model makes processor utilization **1.0000** and **does not change the time at all**. Applied to the table above, sixteen threads' utilization would read 1.0000 instead of 0.1290, and the time would still be **155**. Here, utilization is a proxy metric, and it misleads. ## Three Numbers | Metric | Baseline without abstraction | Setup with abstraction | Cost | |---|---|---|---| | Time | single thread, **20** | eight threads, mutex, **83** | 63 time units | | Waiting steps | **0** | **252** | 252 steps | | Processor utilization | **1.0000** | **0.2410** | 0.7590 drop | | Wrong interleavings | 18 (unprotected) | **0** | correctness gained | The last row says why the first three rows are paid. If the cost looks high, so is what it buys: without protection, eight threads would finish in 20 time units, and there would be no guarantee at all that the result was correct. ## Summary - A mutex does not narrow the reachable interleaving set; it makes every interleaving in the set correct — the distinct result set goes from `[1, 2]` to `[2]`. - As contention grows, time grows linearly: each thread adds 9 time units; going from 1 to 16 threads, time rises from 20 to 155. - Waiting steps grow quadratically; the ratio to $n(n-1)$ is 4.5 across every row. Doubling the thread count quadruples the waiting. - A semaphore divides contention by the permit count and lowers time, but it relaxes mutual exclusion; it is not a correctness tool in front of a shared counter. - The way to lower contention is not a faster lock but a shorter critical section: at eight threads, dropping the critical share from 0.50 to 0.25 lowers time from 83 to 48, and to 0.05 lowers it to 20. ## Next Step This lesson measured the cost of a single lock. Real programs do not use a single lock: every shared structure gets its own lock, and a thread can request two at once. The next lesson takes up two new failure modes that arise from this — **deadlock**, where a group of threads waits on each other forever, and **starvation**, where a thread's turn never comes. The waiting relationship will be turned into a graph, the Data Structures course's cycle detection will be called directly, and it will be shown, by scanning 648 cases, that lock ordering structurally eliminates deadlock.