What does it mean for a lock to be fair, how does an unfair (barging) lock differ, and when is fairness worth its cost?

## Two grant policies When a lock is released and several threads want it, someone must choose the next owner. - **Fair / FIFO:** waiters queue on arrival; the lock is handed to the head of the queue. Ownership order matches request order, and bounded waiting is guaranteed — you are overtaken at most a bounded number of times (zero, in a strict FIFO lock). - **Unfair / barging:** the lock is simply marked free and whoever wins the next atomic attempt gets it. A thread arriving fresh, still running on a CPU with warm caches, will usually beat a parked thread that must be woken. Many real implementations are unfair by default and offer fairness as an explicit option, precisely because the default is the fast one. ## Why barging is faster The cost driver is the **handoff gap**. Parking and unparking a thread involves the OS scheduler: signal the waiter, mark the thread runnable, wait for a core, restore its context, then it re-enters the critical section. That is commonly 1–10 microseconds. If the critical section itself is 100 nanoseconds, a strictly fair lock spends most of its time with the lock *idle but reserved* for a thread that is not yet running. A barging lock avoids that: a thread already executing grabs the free lock, completes its short section, and releases — possibly many times — while the queued thread is still waking. Throughput can differ by an order of magnitude for short critical sections. The flip side is exactly the same mechanism seen from the queued thread's perspective: it can be overtaken again and again. ## The tail-latency argument If you measure mean acquisition wait, unfair looks better. If you measure p99.9 or maximum wait, fair looks better and unfair may show pathological outliers — a thread waiting milliseconds or worse while a hot loop monopolises the lock. In a service with a latency objective, the tail is the product requirement, so the trade is not obvious in either direction. The honest answer to 'which should I use' is: measure the acquisition wait distribution, not just throughput. ## Middle grounds Real systems rarely pick a pure policy: - **Bounded barging / batched fairness:** allow barging, but after a waiter has been overtaken N times, or after T microseconds, switch to handing off. This keeps most of the throughput and caps the tail. - **Ticket locks:** each arrival takes a number and waits for its number to be served. Strictly fair and simple, but every waiter spins on the same shared cache line, which scales poorly with core count. - **Queue locks (MCS-style):** each waiter spins on its *own* cache line, linked into a queue, and the releaser hands off to its successor. Fair *and* scalable, at the cost of a small per-acquire node and a more complex release path. - **Fairness plus timeouts:** a fair queue where waiters can abandon at a deadline gives bounded waiting and bounded blocking simultaneously. ## Fairness is only about the lock Two caveats candidates often miss. First, a fair lock guarantees grant order, not *execution* order — once granted, the thread still competes for CPU with everything else, so the OS scheduler can reorder outcomes anyway. Second, fairness does not fix **priority inversion**: a low-priority thread holding a lock can block a high-priority waiter regardless of policy. That needs priority inheritance (temporarily boosting the holder to the highest waiter's priority) or a priority-ceiling protocol, both properties of the lock implementation, not of FIFO ordering. ## Practical selection rules Prefer fairness when: critical sections are long relative to a context switch (milliseconds of work, so the handoff gap is negligible); the number of contenders is small; or an unbounded wait is a correctness or SLA violation. Prefer unfair when: sections are short, contention is high, and throughput is the objective — then keep a wait-time histogram so you can see starvation if it appears rather than guessing.