Locks, Mutexes, and Semaphores

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.

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.

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.

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.

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.