fairness in NPTL mutex

[Halim Amer]

Hi

This question concerns the NPTL mutex implementation but it is tightly 
related to the futex syscall. So, please let me know if you think this 
is not the right place to seek answers.

In short, I would like to know if there is a way to guarantee fairness 
in lock acquisition when using a mutex. AFAIK, the NPTL mutex 
implementation is based on atomic operations to acquire the lock and 
block on a FUTEX_WAIT if not successful. The problem arises when a the 
lock is released, a thread/process wakes up with a FUTEX_WAKE but has to 
race again to acquire the lock through atomic operations. Since cases 
where another thread/process wins the lock instead of the one that just 
woke up (ex. tight loop where the thread releases the lock will acquire 
it faster than others) unfairness is  happening.

This issue was already pointed out in the paper "Fuss, Futexes and 
Furwocks: Fast Userlevel Locking in Linux". The authors proposed a fair 
futex syscall (futex_up_fair) to avoid this problem. However it seems 
like it never went to the mainstream kernel. Am I wrong, or there is no 
way to achieve this behavior with the current futex available operations?

I am aware of fair lock implementations such as ticket and queue-based 
locks, but I would like a lock that guarantees fairness while blocking 
threads/processes in the kernel space instead of busy waiting. Any 
suggestions are welcome.

Thank you,
Halim