Martin, it isn't the condition variable which is unfair, but how the constructed locking apparatus is unfair that is the problem.  This lock is written by a Tim, whom I assume to be Tim Peters.  I quote his comment:  
"In general, if the bit can be acquired instantly, it is, else the pair is used to block the thread until the bit is cleared.     9 May 1994 tim@ksr.com"

Herein lies the problem.  This is the behaviour of "greedy" or "unfair" mutexes, not that of "fair" semaphores.  The lock is made 'free' and the just signaled thread has to _race_ to acquire it.

Since the exact mechanics seem to be unclair to many, let me just step you through the series of events.
1) A has the lock, B is waiting for it.  the bit is "set".
2) A releases the lock:  Clears the bit, signals the condition variable.
3) A tries to immediately reacquire the lock.  Sees the bit cleared, sets it, and claims the lock.
4) B wakes up from the condition variable.  Sees the bit "set" and goes back to sleep.  It has lost the race to A.

If the lock were based on a semaphore, the events would be different:
1) A has the semaphore, B is waiting for it, sem.value == 0
2) A releases (signals) the semaphore.  B is made runnable. sem.value stays at 0
3) A tries to immediately reacquire the lock.  Finds the sem.value at 0 and blocks.
4) B wakes up and executes, now the owner of the lock. sem.value stays at 0.

This particular patch implements the latter behaviour by explicitly entering a "handoff" period.  If you want, I can submit a different patch which emulates a semaphore perfectly.  perhaps that is easier to understand, since semaphores are very familiar to people.

The key difference between Tim's lock is that the semaphore "hands off" ownership to a particular waiting thread.  The semaphore doesn't enter a state of "free" so that thread have to race to lock it.  It is this race which is unfair and which the just-releasing lock almost always wins.

If you are asking "why would we want an unfair lock, then?", see issue 8299 where I point out some links that discuss unfair locks and their role in combating lock convoys.


Antoine, if we have A, B, and C, all competing for the lock, at any one point, only one of the three has the lock.  Say, A.  The others are waiting on the condition variable.
Condition variables are generally implemented in a "fair" manner, so that all threads that "wait" on it are woken up in a roughly FIFO manner.  If not exactly, then at least in the long run.  All of the threads have to enter the condition variable's wait queue to acquire the lock.  Because of this, the lock is handed off to the threads in roughly the same order that they enter the condition variable´s wait state.

If, in your example, C is waiting on the condition variable, then A and B, whenever they give up the lock, they will hand it off a single thread which is woken up, typcally the one at the head of the condition variable's internal queue.  If the condition variable is implemented properly, there is no way that A and B can just flip-flop without C never being the thread to be woken up next.

As so often, the proof is in the pudding.  Try your ccprof.py script with the do_yield turned off.
You can also implement an explicitly FIFO condition variable, as I did in issue 8299, if you don't trust the condition variable's own internal mechanism to treat its waiting threads fairly.