Linus Torvalds (torvalds.delete@this.linux-foundation.org) on August 21, 2018 5:10 pm wrote:

> So we've almost invariably had to build in fairness in the queuing itself. Our spinlocks,
> for example, are not just a "owner" lock. No, they are ticket locks, so that people
> that get blocked on a spinlock get a particular ordering, and you don't get in the situation
> that some CPU's have an easier time re-taking the lock than others.
>
> And yes, that ended up slowing the spinlocks down and making them more complex, but not really
> noticeably so - and the unfairness case was really noticeable on some big machines. To
> the point where people had watchdogs fire because some CPU wouldn't make progress for tens
> of seconds at a time, just because other CPU's could re-take the lock so quickly.
>
> So I used to detest fairness. It makes locking harder and slower. But almost every time, we've found
> that if something can get contended, fairness isn't just a good idea, it's pretty much required.

Fairness is definitely a double-edged sword (completely ignoring any implementation complexity: let's just pretend that one has infinitely many infinitely smart developers that can develop whatever algorithm the hardware will allow).

It might work for spinlocks in the kernel, but in userspace with "regular" locks that (maybe) spin and then fall back to an OS wait totally fair locks are often the kiss of death. If you have a "hot-but-mostly-not-contented" lock in the sense that it is taken fairly frequently by every thread, but is very short and the total time each thread spends in it is minuscule (say 0.01% of each thread's total time or something), and you have some reasonable spin/backoff before blocking, everything will be fine for a bit (you'll pay some coherence cost pinging this lock back and forth, but whatever) - but then suddenly one thread context-switches while holding the lock, or some other perturbation happens (maybe a cache miss inside the lock or an interrupt or something), such that threads block waiting for the long and you have a lock convoy that might persist indefinitely.

The whole system is very non-linear and a small change like adding a few more threads or changing some kernel thing that changes the context time or wakeup order, or different hardware that is NUMA or something can change the conveys from being self-correcting to self-perpetuating. If the convoy persists can basically brings your process to a halt: it might as well have crashed.

That's why I don't think you'll find many locks that are "fair-by-default" in common userspace libraries.