When using Condition variables to manage access to shared resources you can run into starvation issues due to the thread that just gave up a resource (making a call to notify/notify_all) having priority on immediately reacquiring that resource before any of the waiting threads get a chance. The issue appears to arise because unlike the Lock implementation Condition variables are implemented partly in Python and a thread must hold the GIL when it reacquires its underlying condition variable lock.

Coupled with Python's predictable switch interval this means that if a thread notifies others of a resource being available and then shortly after attempts to reacquire that resource it will be able to do so since it will have held the GIL the entire time.

This can lead to some threads being entirely starved (forever) for access to a shared resource. This came up in a real world situation for me when I had multiple threads trying to access a shared database connection repeatedly without blocking between accesses. Some threads were never getting a connection leading to unexpected timeouts. See https://github.com/sqlalchemy/sqlalchemy/issues/7679


Here's a simple example of this issue using the queue.Queue implementation: https://gist.github.com/msg555/36a10bb5a0c0fe8c89c89d8c05d00e21

Similar example just using Condition variables directly: https://gist.github.com/msg555/dd491078cf10dbabbe7b1cd142644910

Analagous C++ implementation. On Linux 5.13 this is still not _that_ fair but does not completely starve threads: https://gist.github.com/msg555/14d8029b910704a42d372004d3afa465

Thoughts:
- Is this something that's worth fixing? The behavior at the very least is surprising and I was unable to find discussion or documentation of it.
- Can Condition variables be implemented using standard C libraries? (e.g. pthreads) Maybe at least this can happen when using the standard threading.Lock as the Condition variables lock?
- I mocked up a fair Condition variable implementation at https://github.com/msg555/fairsync/blob/main/fairsync/condition.py. However fairness comes at its own overhead of additional context switching.


Tested on Python 3.7-3.10