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.

Catching

Note: This issue is addressed and this question is mentioned in: bugs.python.org/issue45997 – Prayerful

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.

Armenia

It looks like a documentation bug, especially as asyncio docs have recently undergone an overhaul. – Jamnes

The warning to distinguish between documented behavior and an accident of the current implementation, in this case it might not apply. First, the implementation goes out of its way to create a deque to guarantee order - at least a hint of intention. Second, the guarantee makes a lot of sense for the async IO use case, and similar guarantees are provided in other comparable environments (JavaScript callbacks, Tokio thread pool). A hypothetical alternative implementation would have very strong reasons to retain the current behavior. And finally, the docstring still contains the guarantee. – Jamnes

@Jamnes agree with you on all points. Yet, better safe than sorry, isn't it? If project is important and long living and unlocking order is critical, I would prefer to stress that my Lock not only locks, but also unlocks in order with class name like OrderedLock (vendorizing implementation would take minimal effort). Of course it's more personal preference than something definitive. – Armenia

In this particular case I think the best approach would be to file a documentation bug, i.e. request a clarification from the asyncio devs. – Jamnes

Thanks, I've now created a pull request. – Jamnes

Thanks to this PR (github.com/python/cpython/pull/13082) the docs now promise fairness. (The implementation is a different matter, see github.com/python/cpython/issues/90155, which despite the title mentioning only Semaphore applies to other locks too.) – Dysthymia

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.

Upthrow

Is what you wrote guaranteed by specification or is it detail of current implementation? – Armenia

@MikhailGerasimov it’s not guaranteed by the documentation; no, but it is the intent of asyncio.locks primitives to work as “sanely” as possible. All the primitives use such ordered approaches. – Upthrow

Semaphore actually doesn't. It has the underlying deque suggesting it does, but its acquire() doesn't check for existing waiters in it, so there's a race condition after a release() where a new caller can grab the permit before the "rightful" waiter that was scheduled to wake. There's also a bad side effect where, since the permit is already taken, that existing awoken waiter puts itself back into the deque at the back of the line, further screwing up the order. – Cancan