eventually fair mutex

Skip to first unread message

Dmitry Vyukov

Feb 18, 2019, 3:27:14 PM2/18/19
to lock...@googlegroups.com

I did this change some time ago, but thought it's still worth sharing
(better late than never!):


There are mutexes that let threads in in strict FIFO order. This is
good for fairness, but very bad for performance as 2 threads
effectively need to go in lock-step: one thread can't immediate
reacquire the mutex if there is another thread waiting, so it has to
yield to the other thread, and then they swap roles and the second
thread needs to yield to the first one and so on.
There are also mutexes that allow the first thread that is _runnning_
when the mutex is free to acquire it. This is great for performance,
but bad for fairness. In the worst case scenario, a thread holds a
mutex for along time, then briefly releases and reacquires again. This
can starve other threads literally infinitely: whenever they wake the
first thread has already reacquired the mutex.

The idea of the change to get best of both worlds: good fast path
performance and (at eventual, or bounded) fairness. If a thread
discovers that it is starved for too long (say a second), it marks the
mutex state as "starved". In this mode Unlock will directly handoff
mutex ownership to the blocked/started thread.
When a thread discovers that it's not starving on lock operation but
the mutex is in starvation mode, it resets the starvation flag the
mutex returns to normal "no handoff" operation.
This allowed to resolve unbounded starvation problems encountered in
real applications with no performance effect for normal use cases.
Reply all
Reply to author
0 new messages