I've been using a waiter-count approach to futex-based locks: adjacent to the futex int, having a second int that's a waiter count which waiters contending for the lock atomically increment before performing a futex wait operation, and atomically decrement upon return from the futex syscall. However, I've noticed that this has pathologically bad properties in terms of the number of useless wake syscalls performed when the number of threads running is greater than the number of cpus, which goes like this:
Thread A is suspended waiting on the futex, and thus has the waiter count incremented, but it's not going to receive a timeslice again soon because all cpus are in use. Meanwhile, thread B is rapidly performing operations that momentarily acquire and release the lock. Each time, it sees that there is a waiter, and therefore makes a futex wake syscall, despite the fact that thread A has already been sent a wake and just has not yet had a chance to run and decrement itself from the waiter count.
Is there any good way around this? I feel like there should be some safe way for the thread sending the wake event to do the equivalent of decrementing the waiter count (doing that directly doesn't seem possible since it would be hard to negotiate so that multiple-decrements don't happen). Adding one or more extra int fields to the lock state would be acceptable if necessary.
One alternate design I'm aware of is foregoing the waiters count and instead having only a contention flag on the atomic locking int itself. The way this goes, unlock operations clear the flag, and attempts (successful or not) to obtain the lock after it was found to be held set the flag. On unlock, if the flag is set, the wake operation is performed. I believe this design avoids the problem I'm experiencing, but it has a different issue: under low contention, a waiter that arrives while the lock was held will unconditionally make a futex wake syscall when it releases the lock, even if there are no other waiters. Perhaps this design could be hybridized with a waiter count to eliminate some or all spurious wake syscalls?
I believe it's possible to have the thread sending the wake event perform the decrement, and still maintain an accurate waiter count. The key details are:
FUTEX_WAIT returns an indication of whether it was woken by FUTEX_WAKE (zero) or something else (nonzero). A waiter woken by FUTEX_WAKE should not decrement the waiter count (it should assume the waker did so on its behalf); a waiter woken for any other reason should decrement the count (unless of course it is immediately going to wait again).
FUTEX_WAKE returns the number of threads woken up: the waker should decrement the waiter count by this number.
The important point is that both sides know whether the responsibility of decrementing the waiter count has been successfully handed over.
Of course, the devil is always in the detail, and whether this scheme is strictly the most efficient way of managing waiters will depend on how well it integrates with the rest of the locking scheme in question - but it certainly deserves consideration.