question re: asyncio.Condition lock acquisition order
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? Thanks a lot, --Chris
AFAIK No any guarantee On Tue, Jun 27, 2017 at 10:29 AM Chris Jerdonek <chris.jerdonek@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?
Thanks a lot, --Chris _______________________________________________ Async-sig mailing list Async-sig@python.org https://mail.python.org/mailman/listinfo/async-sig Code of Conduct: https://www.python.org/psf/codeofconduct/
-- Thanks, Andrew Svetlov
On Tue, Jun 27, 2017 at 12:29 AM, Chris Jerdonek <chris.jerdonek@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.StrictFIFOLoc... 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
On Tue, Jun 27, 2017 at 3:29 AM, Nathaniel Smith <njs@pobox.com> wrote:
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? ...
Thanks. All that is really interesting, especially the issue you linked to in the Trio docs re: fairness: https://github.com/python-trio/trio/issues/54 Thinking through the requirements I want for my RW synchronization use case in more detail, I think I want the completion of any "write" to be followed by exhausting all "reads." I'm not sure if that qualifies as barging. Hopefully this will be implementable easily enough with the available primitives, given what you say. Can anything similar be said not about synchronization primitives, but about awakening coroutines in general? Do event loops maintain strict FIFO queues when it comes to deciding which awaiting coroutine to awaken? (I hope that question makes sense!) --Chris
On Tue, Jun 27, 2017 at 4:15 AM, Chris Jerdonek <chris.jerdonek@gmail.com> wrote:
On Tue, Jun 27, 2017 at 3:29 AM, Nathaniel Smith <njs@pobox.com> wrote:
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? ...
Thanks. All that is really interesting, especially the issue you linked to in the Trio docs re: fairness: https://github.com/python-trio/trio/issues/54
Thinking through the requirements I want for my RW synchronization use case in more detail, I think I want the completion of any "write" to be followed by exhausting all "reads." I'm not sure if that qualifies as barging. Hopefully this will be implementable easily enough with the available primitives, given what you say.
I've only seen the term "barging" used in discussions of regular locks, though I'm not an expert, just someone with eclectic reading habits. But RWLocks have some extra subtleties that "barging" vs "non-barging" don't really capture. Say you have the following sequence: task w0 acquires for write task r1 attempts to acquire for read (and blocks) task r2 attempts to acquire for read (and blocks) task w1 attempts to acquire for write (and blocks) task r3 attempts to acquire for read (and blocks) task w0 releases the write lock task r4 attempts to acquire for read What happens? If r1+r2+r3+r4 are able to take the lock, then you're "read-biased" (which is essentially the same as barging for readers, but it can be extra dangerous for RWLocks, because if you have a heavy read load it's very easy for readers to starve writers). If tasks r1+r2 wake up, but r3+r4 have to wait, then you're "task-fair" (the equivalent of FIFO fairness for RWLocks). If r1+r2+r3 wake up, but r4 has to wait, then you're "phase fair". There are some notes here that are poorly organized but perhaps retain some small interest: https://github.com/python-trio/trio/blob/master/trio/_core/_parking_lot.py If I ever implement one of these it'll probably be phase-fair, because (a) it has some nice theoretical properties, and (b) it happens to be particularly easy to implement using my existing wait-queue primitive, and task-fair isn't :-).
Can anything similar be said not about synchronization primitives, but about awakening coroutines in general? Do event loops maintain strict FIFO queues when it comes to deciding which awaiting coroutine to awaken? (I hope that question makes sense!)
Something like that. There's some complication because there are two ways that a task can become runnable: directly by another piece of code in the system (e.g., releasing a lock), or via some I/O (e.g., bytes arriving on a socket). If you really wanted to ensure that tasks ran exactly in the order that they became runnable, then you need to check for I/O constantly, but this is inefficient. So usually what cooperative scheduling systems guarantee is a kind of "batched FIFO": they do a poll for I/O (a which point they may discover some new runnable tasks), and then take a snapshot of all the runnable tasks, and then run all of the tasks in their snapshot once before considering any new tasks. So this isn't quite strict FIFO, but it's fair-like-FIFO (the discrepancy between when each task should run under strict FIFO, and when it actually runs, is bounded by the number of active tasks; there's no possibility of a runnable task being left unscheduled for an arbitrary amount of time). Curio used to allow woken-by-code tasks to starve out woken-by-I/O tasks, and you might be interested in the discussion in the PR that changed that: https://github.com/dabeaz/curio/pull/127 In trio I actually randomize the order within each batch because I don't want people to accidentally encode assumptions about the scheduler (e.g. in their test suites). This is because I have hopes of eventually doing something fancier :-): https://github.com/python-trio/trio/issues/32 ("If you liked issue #54, you'll love #32!"). Many systems are not this paranoid though, and actually are strict-FIFO for tasks that are woken-by-code - but this is definitely one of those features where depending on it is dubious. In asyncio for example the event loop is pluggable and the scheduling policy is a feature of the event loop, so even if the implementation in the stdlib is strict FIFO you don't know about third-party ones. -n -- Nathaniel J. Smith -- https://vorpus.org
On Tue, Jun 27, 2017 at 3:48 PM, Nathaniel Smith <njs@pobox.com> wrote:
On Tue, Jun 27, 2017 at 4:15 AM, Chris Jerdonek
Thinking through the requirements I want for my RW synchronization use case in more detail, I think I want the completion of any "write" to be followed by exhausting all "reads." I'm not sure if that qualifies as barging. Hopefully this will be implementable easily enough with the available primitives, given what you say.
I've only seen the term "barging" used in discussions of regular locks, though I'm not an expert, just someone with eclectic reading habits. But RWLocks have some extra subtleties that "barging" vs "non-barging" don't really capture. Say you have the following sequence:
task w0 acquires for write task r1 attempts to acquire for read (and blocks) task r2 attempts to acquire for read (and blocks) task w1 attempts to acquire for write (and blocks) task r3 attempts to acquire for read (and blocks) task w0 releases the write lock task r4 attempts to acquire for read
What happens? If r1+r2+r3+r4 are able to take the lock, then you're "read-biased" (which is essentially the same as barging for readers, but it can be extra dangerous for RWLocks, because if you have a heavy read load it's very easy for readers to starve writers).
All really interesting and informative again. Thank you, Nathaniel. Regarding the above, in my case the "writes" will be a background cleanup task that can happen as time is available. So it will be okay if it is starved. --Chris
participants (3)
-
Andrew Svetlov -
Chris Jerdonek -
Nathaniel Smith