How 'fair' is a Standard C++ atomic_flag in waking up threads from a wait() on a notify_one() call

Question

Is there any information about fairness in relation to the sequence in which threads that called wait() on an atomic_flag are woken up when notify_one() is called. Are they woken-up in the exact order that they entered the wait(), FIFO so to say ?

Atomic flag variables seem to return 'always lock free'. I knew they were guaranteed to be lock free in any implementation but i am not sure about whether they still are if the wait() is used, and hence some mechanism must decide on waiters wake-up. Some other synchronization means guarantee fairness but it comes at a cost of memory allocation behind the scene.

Is there anyone that knows how this works with atomic_flags. I changed all my synchro's to use atomic flag and they work super fast. However I overlooked the fairness aspect.

Thank you.

Answer 1

The C++ standard makes no requirements here - each implementation is free to wake the thread it finds most appropriate.

This is something you might want to compare across the compilers that exist for your platforms, if it matters to you.

Answer 2

There are no guarantees from the standard, it will depend on the implementation of the standard library.

It isn't even guaranteed that only one thread is unblocked. Any number of eligible threads, but at least one if at least one is eligible, may be unblocked. An implementation that simply forwards notify_one to notify_all would be conforming.

Answer 3

In summary from the several answers the answer would be:

• the Standard C++ specs do not have any guidelines related to fairness of atomic_flags, and probably by extension to all other atomic types.

• each implementation may wake-up waiting threads as they see fit.

• using notify_all() instead of notify_one() would give all threads an almost equal chance to compete for the atomic_flag and leave it further to the scheduler.

• the preemptive thread scheduler leads the orchestra on what thread gets the first chance. I conclude from that, that with notify_all() starvation of a thread might become impossible, or less problematic at least, because each thread would be given chances by the scheduler.

• multi-core doesn't guarantee that a same thread always and completely executes on a same core anyways, so fairness would not bring anything to the table in attempting to better spreading load over the several cores.

Thank you all. Feel good now because that fairness is a lesser problem than i initially thought/feared.