Does Python's asyncio lock.acquire maintain order?

Question

If I have two functions doing

async with mylock.acquire():
    ....

Once the lock is released, is it guaranteed that the first to await will win, or is the order selected differently? (e.g. randomly, arbitrarily, latest, etc.)

The reason I'm asking, if it is not first-come-first-served, there might easily be a case of starvation where the first function attempting to acquire the lock never gets wins it.

Answer 1

When we talk about how something works it's important to distinguish guarantee expressed in specification and side-effect of implementation. First one shouldn't be changed (at least, within major version), second one can be changed any time in the future.

Martijn's answer clearly shows that current implementation preserves order. What about guarantee for future?

Official documentation for Python 3.6 provides guarantee:

only one coroutine proceeds when a release() call resets the state to unlocked; first coroutine which is blocked in acquire() is being processed.

Interesting thing is that neither documentation for Python 3.7 nor documentation for Python 3.8 dev have this line, not sure if it's intentional though. However class's docstring on github has guarantee.

It's also worth mentioning that threading.Lock (prototype for asyncio's lock) explicitly says that order is undefined:

only one thread proceeds when a release() call resets the state to unlocked; which one of the waiting threads proceeds is not defined, and may vary across implementations.

---

Long story short, right now only class's docstring promises to maintain order. It's also fair to note that implementation of lock is unlikely to being changed in the nearest future.

Yet imagine however someone will change it (to increase performance, for example). Will docstring be enough to prevent from implementing lock with undefined order? It's up to you to decide.

If your code critically depends on preserving order and expected to have long life cycle nothing bad if you create your own lock (sub)class which will explicitly guarantee order (OrderedLock or something). You may just vendorize current implementation.

If situation is simpler you may choose not to bother with it and use current implementation.

Answer 2

Yes, tasks that are waiting on the lock are added to a queue, and woken on a FIFO basis.

Specifically, when attempting to acquire a locked lock, a future is created that waits for a signal that the lock has become available, called a waiter. This waiter is added to a collections.deque() double-ended queue, created in Lock.__init__()

self._waiters = collections.deque()

When the lock is released by the task currently holding it, the Lock._wake_up_first() method is called:

def _wake_up_first(self):
    """Wake up the first waiter if it isn't done."""
    try:
        fut = next(iter(self._waiters))
    except StopIteration:
        return


    # .done() necessarily means that a waiter will wake up later on and
    # either take the lock, or, if it was cancelled and lock wasn't
    # taken already, will hit this again and wake up a new waiter.
    if not fut.done():
        fut.set_result(True)

The Future.set_result() call marks the future as done. How exactly this leads to the task awaiting on the future to regain control is implementation dependent, but usually this is done via a callback function given to the event loop to call at its earliest convenience.

The Lock.acquire() method is responsible for both adding and removing futures (as that's where the future will return to when signalled a result has been set):

fut = self._loop.create_future()
self._waiters.append(fut)

# Finally block should be called before the CancelledError
# handling as we don't want CancelledError to call
# _wake_up_first() and attempt to wake up itself.
try:
    try:
        await fut
    finally:
        self._waiters.remove(fut)
except futures.CancelledError:
    if not self._locked:
        self._wake_up_first()
    raise

So if the lock is locked, the current task is made to wait by creating a future object, which is added to the _waiters queue, and the future is awaited on. This blocks the task until the future has a result (await fut won't return until then). The event loop will not give this task any processing time.

Another task that currently holds the lock and releases it will cause the first (longest waiting) future from the _waiters queue to have a result set, indirectly causing the task that is waiting for that future to become active again. When the lock-releasing task hands back control to the event loop (when awaiting on something else), the event loop hands control to the task waiting for that future, the future returns to the await fut line, the future is removed from the queue and the lock is given to the task that waited on that future.

There is one race condition case here that the Lock.acquire() method explicitly handles:

1. Task A releases the lock, the queue holds a future for task B waiting for the lock. The future is set to done.
2. The event loop gives control to a third task C that was awaiting on something unreleated but is now active again, and this task runs code that tries to acquire the lock.

Task C won't be given the lock, however, because at the top of the Lock.acquire() method is this test:

if not self._locked and all(w.cancelled() for w in self._waiters):
    self._locked = True
    return True

not self._locked is true in his case, as task A has released it. But all(w.cancelled() for w in self._waiters) is not, as task B has an active, non-cancelled future in the queue. So task C is made to add their own waiter future to the queue. An unlocked lock with active futures in the _waiters queue is actually considered locked.