[Async-sig] question re: asyncio.Condition lock acquisition order

[Nathaniel Smith]

On Tue, Jun 27, 2017 at 12:29 AM, Chris Jerdonek
<chris.jerdonek at gmail.com> wrote:
> I have a couple questions about asyncio's synchronization primitives.
>
> Say a coroutine acquires an asyncio Condition's underlying lock, calls
> notify() (or notify_all()), and then releases the lock. In terms of
> which coroutines will acquire the lock next, is any preference given
> between (1) coroutines waiting to acquire the underlying lock, and (2)
> coroutines waiting on the Condition object itself? The documentation
> doesn't seem to say anything about this.
>
> Also, more generally (and I'm sure this question gets asked a lot),
> does asyncio provide any guarantees about the order in which awaiting
> coroutines are awakened? For example, for synchronization primitives,
> does each primitive maintain a FIFO queue of who will be awakened
> next, or are there no guarantees about the order?

In fact asyncio.Lock's implementation is careful to maintain strict
FIFO fairness, i.e. whoever calls acquire() first is guaranteed to get
the lock first. Whether this is something you feel you can depend on
I'll leave to your conscience :-). Though the docs do say "only one
coroutine proceeds when a release() call resets the state to unlocked;
first coroutine which is blocked in acquire() is being processed",
which I think might be intended to say that they're FIFO-fair?

asyncio.Condition internally maintains a FIFO list so that notify(1)
is guaranteed to wake up the task that called wait() first. But if you
notify multiple tasks at once, then I don't think there's any
guarantee that they'll get the lock in FIFO order -- basically
notify{,_all} just wakes them up, and then the next time they run they
try to call lock.acquire(), so it depends on the underlying scheduler
to decide who gets to run first.

There's also an edge condition where if a task blocked in wait() gets
cancelled, then... well, it's complicated. If notify has not been
called yet, then it wakes up, reacquires the lock, and then raises
CancelledError. If it's already been notified and is waiting to
acquire the lock, then I think it goes to the back of the line of
tasks waiting for the lock, but otherwise swallows the CancelledError.
And then returns None, which is not a documented return value.

In case it's interesting for comparison -- hopefully these comments
aren't getting annoying -- trio does provide documented fairness
guarantees for all its synchronization primitives:

  https://trio.readthedocs.io/en/latest/reference-core.html#fairness

There's some question about whether this is a great idea or what the
best definition of "fairness" is, so it also provides
trio.StrictFIFOLock for cases where FIFO fairness is actually a
requirement for correctness and you want to document this in the code:

  https://trio.readthedocs.io/en/latest/reference-core.html#trio.StrictFIFOLock

And trio.Condition.notify moves tasks from the Condition wait queue
directly to the Lock wait queue while preserving FIFO order. (The
trade-off is that this means that trio.Condition can only be used with
trio.Lock exactly, while asyncio.Condition works with any object that
provides the asyncio.Lock interface.) Also, it has a similar edge case
around cancellation, because cancellation and condition variables are
very tricky :-). Though I guess trio's version arguably a little less
quirky because it acts the same regardless of whether it's in the
wait-for-notify or wait-for-lock phase, it will only ever drop to the
back of the line once, and cancellation in trio is level-triggered
rather than edge-triggered so discarding the notification isn't a big
deal.

-n

-- 
Nathaniel J. Smith -- https://vorpus.org