It's not fair, but (from the description) it does make some effort to be fairish. It'll queue up waiters in a linked list that is fairly fair, but new people can jump ahead of the line and grab the CAS before the list is processed.
However, it has added logic to start chunking through the queue after 30 wakeups from a waiter. With that, waiting isn't indefinite, but it also isn't fair.
I have no idea how that compares to other implementation's fairness. I know the JDK recently abandoned fairness because of the overhead and complexity it added around mutex handling.
Fairness is known to cause serious problems such as convoys, so while "unfair" isn't itself a desirable property, you might choose to be unfair because the alternatives are worse for some applications.
Probably a specifically Fair version of any concurrent primitive which can be fair is worth giving a distinct name, the way you'd offer both a stable and an unstable sort, knowing that the unstable sort will often (though not always) be faster but some people cannot tolerate an unstable sort so it's useless for them.
On the other hand, maybe it's an attractive nuisance and if you offered this you'd find most users took your FairMutex, and then were angry because of the inevitable problems from fairness, even though the unfair one was right there...
In a lot of cases, programmers don't even care about fairness, but do care about starvation. Is there a word for structures like the one discussed here, that are unfair but appear to prevent unlimited starvation?
I don't think this lock is _guaranteed_ to prevent starvation, it just makes an effort at it. There's only two priority levels and a hard-coded 30 wake-ups required to enter high priority - if waiters were continually joining then there could always be more than one entry in high priority and an entry could get stuck there forever. Typically it won't matter, but if you have high contention then this might not be good enough.
All primitive performance evaluations should be multidimensional, IMO, with fairness being one of the highest-priority variables.
The importance of fairness varies with the algorithm. For instance, one that alternates between being CPU-bound and disk-bound may use N_workers >>> N_cores. These workers might not care about individual starvation at all.
At the other end, consider a strictly CPU-bound algorithm with N_workers==N_cores, and a rogue-ish worker that ends up hogging an important mutex by spinning around it (e.g. the one written by author of the benchmark.) If the other well-behaved workers briefly lock the mutex once prior to each job, but end up getting woken up only once every 30 locks (as this implementation apparently does,) you might end up with core utilization <<< 100%.
This in turn means that APIs that let you customize the behavior can win out even if they're not #1 on any benchmark.
