A mutual-exclusion lock can hand ownership to the longest-waiting thread in strict FIFO order, or let whichever thread happens to be running acquire it first. Compare the two policies and explain why the fair one usually delivers lower throughput.

## The two policies Every blocking mutex has to answer one question: when the owner releases, who gets it next? - **Fair / FIFO**: the lock maintains a queue; release transfers ownership directly to the head of that queue (a *handoff*), or at least the queue's order is enforced so no one else may take it. Property: **bounded waiting** — once you enqueue, at most the threads already ahead of you enter first. - **Unfair / barging**: release simply marks the lock free. A waiter is signalled, but any runnable thread that calls acquire in the meantime can win. Property: only **deadlock-freedom** — someone progresses, but no promise for you. Both are correct in the safety sense; they differ purely on liveness guarantees and performance. ## Why fairness costs throughput **Handoff latency dominates short critical sections.** Parking and unparking a thread costs on the order of a few microseconds (syscall, scheduler run-queue insertion, possible IPI to another core, context switch). A well-written critical section may run in tens or hundreds of nanoseconds. Under strict handoff the lock is unavailable during the entire wake-up window, so the *effective* critical-section length becomes the wake-up cost. Throughput is then bounded by roughly 1 / (wake-up latency) acquisitions per second, potentially one to two orders of magnitude below what a barging lock achieves, where the next acquirer is already running. **Cache locality.** The barging thread is on a CPU right now; the lock word, and often the protected data, are hot in its L1/L2. The handed-off thread starts on a different core, so the lock cache line and every protected line must migrate — each migration is tens to hundreds of cycles. Fairness deliberately maximises the number of migrations by rotating ownership among all waiters. **Convoying.** With strict FIFO the whole queue proceeds in lock-step. If one holder is descheduled or takes a page fault while holding, every waiter behind it stalls and the group stays bunched: they finish together, contend together, queue together again. Unfair locks let threads drift out of phase, which reduces contention naturally. **Preemption sensitivity.** In a fair lock the next owner may be preempted before it even runs; the lock stays blocked until the scheduler comes back to it. Barging lets any other runnable thread use the lock in that gap, so the resource is not held hostage by one scheduling decision. ## What fairness buys - **Bounded tail latency.** The p999 of lock-wait becomes a function of queue length rather than of luck. For latency-SLO systems this can matter more than mean throughput. - **No starvation.** Every waiter is guaranteed to be served, which matters when the contending population is heterogeneous — for example, a background scanner competing with user requests, or many tenants on one resource. - **Predictability and easier reasoning.** Wait time correlates with observable queue depth, so capacity planning and back-pressure decisions become tractable. A useful framing: unfair locks optimise the **mean**, fair locks optimise the **maximum**. If your objective function is requests per second, choose unfair. If it is "99.9% of requests under X ms", fairness (or bounded overtaking) is often the cheaper way to get there than shaving the mean. ## The middle ground Real lock implementations rarely sit at an extreme: - **Bounded overtaking / eventual fairness**: allow barging, but if a waiter has been overtaken k times, or has waited longer than a threshold, switch that lock into handoff mode until the waiter is served. This keeps nearly all the throughput while capping the tail. Several production mutexes use exactly this design. - **Spin-then-park**: spin briefly before parking, so short critical sections never pay wake-up cost, and only long waits go to the queue. - **Queue-based spin locks (MCS/CLH-style)**: each waiter spins on its own cache line and is granted the lock in order — fair *and* scalable, at the cost of requiring spinning, which is only viable when holders are never preempted and hold times are tiny. - **Cohort or NUMA-aware locks**: prefer handing the lock to a thread on the same socket to preserve locality, with a bound on how long one socket may keep it — trading a little fairness for a lot of locality. ## Choosing in practice Ask four questions. How long is the critical section relative to a context switch? If shorter, fairness is expensive. How contended is the lock? Uncontended locks make the policy irrelevant. Is the workload homogeneous? If all threads do the same work, unfairness is statistically self-correcting; if some class can be systematically slower to wake, it will starve. What is the objective — throughput or bounded tail? State the objective first, and the policy follows. And remember the meta-answer an interviewer wants: the best fix is usually to reduce contention, not to tune the policy. Shorter critical sections, sharding the data, per-thread or per-core state, read-mostly structures, or replacing the lock with a queue that a single owner drains all remove the question entirely.