Order of execution of waiting threads blocked by mutex

Question

I have a mutex that controls access to a single object from multiple threads. When a thread has finished the mutex is unlocked to allow order threads to operate on the object. On Windows using the WaitForSingleObject function is there an order that threads are signaled? I want the first thread that attempts to lock the mutex to now be allowed to lock the mutex. This would be a FIFO queue so that signaling to the blocked threads is not random. Would I have to implement my own queuing mechanism to achieve this? And if so what functions are useful?

Answer 1

FIFO signaling leads to lock convoys. On newer versions of the Win32 API the convoy issue is addressed by macking mutexes and other synchrnonization primitives explicitly unfair (ie. no FIFO).

If more than one thread is waiting on a mutex, a waiting thread is selected. Do not assume a first-in, first-out (FIFO) order. External events such as kernel-mode APCs can change the wait order.

Answer 2

Yes you would need to implement your own queueing mechanism if you want a FIFO queue.

Answer 3

if you want the unlocking to occur in FIFO order, you can use a custom lock. A FIFO lock exist in ACE; it's called ACE_Token, and since it's open source, perhaps you can use it as a reference implementation. i think the overhead of using it will be minimal.

Answer 4

The Windows way to do your own scheduling is by using fibers. The main thread will wait on the mutex, once it returns, you explicitly call SwitchToFiber from a thread safe QUEUE (FIFO).

1. The thread calling SwitchToFiber will need to call ConvertThreadToFiber
2. The function in SwitchToFiber should call to SwitchToFiber from the QUEUE