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

[Chris Jerdonek]

On Tue, Jun 27, 2017 at 3:48 PM, Nathaniel Smith  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
___
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/

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

[Nathaniel Smith]

On Tue, Jun 27, 2017 at 4:15 AM, Chris Jerdonek
 wrote:
> On Tue, Jun 27, 2017 at 3:29 AM, Nathaniel Smith  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
___
Async-sig mailing list
Async-sig@python.org
https://mail.python.org/mailman/listinfo/async-sig
Code of Conduct: 

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

[Chris Jerdonek]

On Tue, Jun 27, 2017 at 3:29 AM, Nathaniel Smith  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
___
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/

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

[Andrew Svetlov]

AFAIK No any guarantee

On Tue, Jun 27, 2017 at 10:29 AM Chris Jerdonek 
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
___
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/

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

[Chris Jerdonek]

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/