channels as trylocks
115 views
Skip to first unread message
shiv...@yelp.com
Jul 24, 2019, 2:24:29 PM7/24/19
to golang-nuts
Several sources, including this issue comment:
state that a buffered channel of size 1 can be used as a trylock by select'ing on it with a default case.
I was thinking about it and it seemed to me that with such an implementation, it is unclear whether a failed acquisition of the trylock guarantees that the lock is held by someone else. More precisely, I can't tell if the following guarantee holds: a failed acquisition of the trylock cannot happen-before a successful acquisition, unless a release happens-between them. (To put it another way: can there be "spurious" failures of trylock acquisition?)
In particular:
1. The memory model documentation states ordering guarantees for *successful* channel receives and sends, but doesn't say anything about failed nonblocking receives and sends, so it seems to me that in principle it can't be promising anything about this behavior.
2. I can't tell whether the fast-path checks in the current implementation allow for this:
In particular, I don't understand why `chanrecv` does an atomic read of `qcount`, but `chansend` just does a normal read.
One case where this is relevant is implementing something like a write-back cache with at most one goroutine performing the writeback:
func update() {
mark_state_dirty()
if trylock.TryAcquire() {
go writeback_worker()
} // else: some writeback worker is guaranteed to be active
}
func writeback_worker() {
for {
perform_writeback()
trylock.Release()
if !state_is_dirty() {
return // nothing more to do
}
if !trylock.TryAcquire() {
return // a new writeback worker is guaranteed to be active
} // else: loop back around and do the writeback again
}
}
where, in the absence of this guarantee, an update can be "missed" and writeback can be delayed arbitrarily.
Thanks very much for your time.
Ian Lance Taylor
Jul 25, 2019, 1:44:25 AM7/25/19
to Shivaram Lingamneni, golang-nuts
On Wed, Jul 24, 2019 at 11:24 AM shivaram via golang-nuts
<golan...@googlegroups.com> wrote:
>
> Several sources, including this issue comment:
>
> https://github.com/golang/go/issues/27544#issuecomment-419265234
>
> state that a buffered channel of size 1 can be used as a trylock by select'ing on it with a default case.
>
> I was thinking about it and it seemed to me that with such an implementation, it is unclear whether a failed acquisition of the trylock guarantees that the lock is held by someone else. More precisely, I can't tell if the following guarantee holds: a failed acquisition of the trylock cannot happen-before a successful acquisition, unless a release happens-between them. (To put it another way: can there be "spurious" failures of trylock acquisition?)
In any realistic program, a lock may be held by a different goroutine
<golan...@googlegroups.com> wrote:
>
> Several sources, including this issue comment:
>
> https://github.com/golang/go/issues/27544#issuecomment-419265234
>
> state that a buffered channel of size 1 can be used as a trylock by select'ing on it with a default case.
>
> I was thinking about it and it seemed to me that with such an implementation, it is unclear whether a failed acquisition of the trylock guarantees that the lock is held by someone else. More precisely, I can't tell if the following guarantee holds: a failed acquisition of the trylock cannot happen-before a successful acquisition, unless a release happens-between them. (To put it another way: can there be "spurious" failures of trylock acquisition?)
as the trylock starts and released as the trylock ends. So it is
always possible for trylock acquisition to fail but for the lock to be
unlocked after trylock completes.
> In particular:
>
> 1. The memory model documentation states ordering guarantees for *successful* channel receives and sends, but doesn't say anything about failed nonblocking receives and sends, so it seems to me that in principle it can't be promising anything about this behavior.
>
> 2. I can't tell whether the fast-path checks in the current implementation allow for this:
>
> https://github.com/golang/go/blob/919594830f17f25c9e971934d825615463ad8a10/src/runtime/chan.go#L159
> https://github.com/golang/go/blob/919594830f17f25c9e971934d825615463ad8a10/src/runtime/chan.go#L437
>
> In particular, I don't understand why `chanrecv` does an atomic read of `qcount`, but `chansend` just does a normal read.
Ian
Shivaram Lingamneni
Jul 25, 2019, 4:00:58 AM7/25/19
to Ian Lance Taylor, golang-nuts
On Thu, Jul 25, 2019 at 1:44 AM Ian Lance Taylor <ia...@golang.org> wrote:
>
> On Wed, Jul 24, 2019 at 11:24 AM shivaram via golang-nuts
> <golan...@googlegroups.com> wrote:
> >
> > Several sources, including this issue comment:
> >
> > https://github.com/golang/go/issues/27544#issuecomment-419265234
> >
> > state that a buffered channel of size 1 can be used as a trylock by select'ing on it with a default case.
> >
> > I was thinking about it and it seemed to me that with such an implementation, it is unclear whether a failed acquisition of the trylock guarantees that the lock is held by someone else. More precisely, I can't tell if the following guarantee holds: a failed acquisition of the trylock cannot happen-before a successful acquisition, unless a release happens-between them. (To put it another way: can there be "spurious" failures of trylock acquisition?)
>
> In any realistic program, a lock may be held by a different goroutine
> as the trylock starts and released as the trylock ends. So it is
> always possible for trylock acquisition to fail but for the lock to be
> unlocked after trylock completes.
As I see it, the problem is that failed acquisitions of a
>
> On Wed, Jul 24, 2019 at 11:24 AM shivaram via golang-nuts
> <golan...@googlegroups.com> wrote:
> >
> > Several sources, including this issue comment:
> >
> > https://github.com/golang/go/issues/27544#issuecomment-419265234
> >
> > state that a buffered channel of size 1 can be used as a trylock by select'ing on it with a default case.
> >
> > I was thinking about it and it seemed to me that with such an implementation, it is unclear whether a failed acquisition of the trylock guarantees that the lock is held by someone else. More precisely, I can't tell if the following guarantee holds: a failed acquisition of the trylock cannot happen-before a successful acquisition, unless a release happens-between them. (To put it another way: can there be "spurious" failures of trylock acquisition?)
>
> In any realistic program, a lock may be held by a different goroutine
> as the trylock starts and released as the trylock ends. So it is
> always possible for trylock acquisition to fail but for the lock to be
> unlocked after trylock completes.
channel-based trylock do not create any happens-before edges with
successful releases or acquisitions.
In contrast, x/sync/semaphore does create these edges, because calls
to Acquire, TryAcquire, and Release are all ordered by the acquisition
and release of `mu`:
https://github.com/golang/sync/blob/112230192c580c3556b8cee6403af37a4fc5f28c/semaphore/semaphore.go
so it cannot happen that a failed TryAcquire is followed by a
successful TryAcquire unless there's a Release in between.
> > In particular:
> >
> > 1. The memory model documentation states ordering guarantees for *successful* channel receives and sends, but doesn't say anything about failed nonblocking receives and sends, so it seems to me that in principle it can't be promising anything about this behavior.
> >
> > 2. I can't tell whether the fast-path checks in the current implementation allow for this:
> >
> > https://github.com/golang/go/blob/919594830f17f25c9e971934d825615463ad8a10/src/runtime/chan.go#L159
> > https://github.com/golang/go/blob/919594830f17f25c9e971934d825615463ad8a10/src/runtime/chan.go#L437
> >
> > In particular, I don't understand why `chanrecv` does an atomic read of `qcount`, but `chansend` just does a normal read.
>
> This is explained by the comments about read ordering and order of operations.
> Ian
Reply all
Reply to author
Forward
0 new messages