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

[Nathaniel Smith]

On Tue, Jun 27, 2017 at 4:15 AM, Chris Jerdonek
<chris.jerdonek at gmail.com> wrote:
> On Tue, Jun 27, 2017 at 3:29 AM, Nathaniel Smith <njs at 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