Re: [go-nuts] Workaround for missing RWMutex.Try*Lock()

Robert Engels Wed, 04 Dec 2019 11:07:20 -0800

For completeness, RWMutex.TryLock() is also needed. If you are modifying the stdlib, these are trivial changes to add these methods.

-----Original Message-----
From: Liam
Sent: Dec 4, 2019 12:34 PM
To: golang-nuts
Subject: Re: [go-nuts] Workaround for missing RWMutex.Try*Lock()

Thank you for the refs and pseudocode!

Somehow I imagined this would be simpler... A proposal for Mutex.TryLock() was turned aside years ago because it's trivial to implement with CAS. But they didn't consider RWMutex.TryRLock().

https://github.com/golang/go/issues/6123

@ianlancetaylor, is this worth a new proposal?

On Tuesday, December 3, 2019 at 7:52:54 PM UTC-8, robert engels wrote:
You actually only need a cas and a condition variable (technically the condition in Go requires a backing lock, but if you have wait/notify it isn’t needed).

You can read this https://code.woboq.org/userspace/glibc/nptl/pthread_rwlock_common.c.html and/or https://6826.csail.mit.edu/2019/papers/HO17.pdf for the general idea.

Essentially, you use some bits of the ‘atomic value’ to encode phases (waiting for write lock, holding write lock, reader bits) - and use the cond variable to block the writers (or readers for that matter) and loop and retry the cas.

The following is simplified since it isn’t “fair”, but you can add another bit for “writer waiting” to accomplish this. Also, the ‘condition’ must be a ‘flag’ so that a signal() with no waiters is satisfied by the next wait()

bits 0 - 30 number of readers
bits 31 writer has lock

WRITER = 1<<31
read() is the atomic read of v

pseudo code

try_lock() {
for {
v = read()
if v has writer {
return WOULD_BLOCK
}
if(cas(v,v + 1 reader)) {
return OK
} else {
// loop and try again
}
}
}

runlock() {
for{
v = read()
if(cas(v,v -1 reader)) {
cond.signal() // can be optimized to not always do this, i.e. only when readers is 0
return
} else {
// loop and try again
}
}
}

wlock() {
for {
v = read()
if v !=0 {
cond.wait()
}
else {
if(cas(v,WRITER)) { // we are the writer
return
} else {
// loop and try again
}
}
}

wunlock() {
set(v,0);
cond.signal() // for other waiting writers
}

Obviously if you need readers to block on writers (i.e. rlock() ) it is slightly more work, but you get the idea.

On Dec 3, 2019, at 7:54 PM, Liam <networ...@gmail.com> wrote:

Busy means would-block, yes.

Burak thanks, but that doesn't work for read-lock.

On Tuesday, December 3, 2019 at 5:39:48 PM UTC-8, Robert Engels wrote:
It depends then, because technically the Go RW lock queues readers behind a waiting writer so “busy” is somewhat undefined. If “busy” means “would block” you can still do it - I’ll post the code tonight.

> On Dec 3, 2019, at 6:49 PM, Robert Engels <ren...@ix.netcom.com> wrote:
>
> I would use an atomic and a lock instead of two locks.
>
>>> On Dec 3, 2019, at 6:35 PM, burak serdar <bse...@computer.org> wrote:
>>>
>>> On Tue, Dec 3, 2019 at 5:21 PM Liam Breck <networ...@gmail.com> wrote:
>>>
>>> I have a problem that is trivially solved via
>>>
>>> door sync.RWMutex
>>>
>>> func Reader() T {
>>> if !door.TryRLock() { // missing in stdlib :-(
>>> return busy
>>> }
>>> defer door.RUnlock()
>>> ...
>>> }
>>>
>>> func Writer() {
>>> door.Lock()
>>> defer door.Unlock()
>>> ...
>>> }
>>>
>>> How does one achieve this in Go?
>>
>> Two locks and a bool?
>>
>> var door=sync.Mutex{}
>> var x=sync.Mutex{}
>> var b bool
>>
>> func trylock() bool {
>> x.Lock()
>> if b {
>> x.Unlock()
>> return false
>> }
>> b=true
>> door.Lock()
>> x.Unlock()
>> return true
>> }
>>
>> unlock:
>>
>> x.Lock()
>> b=false
>> door.Unlock()
>> x.Unlock()
>>
>>
>>
>>
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups "golang-nuts" group.
>>> To unsubscribe from this group and stop receiving emails from it, send an email to golan...@googlegroups.com.
>>> To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CAKvHMgTO%3DxfFQ_u7aO9UE-1vHHEKmdhr47sro2mnp6DkEb6mPA%40mail.gmail.com.
>>
>> --
>> You received this message because you are subscribed to the Google Groups "golang-nuts" group.
>> To unsubscribe from this group and stop receiving emails from it, send an email to golan...@googlegroups.com.
>> To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CAMV2RqrDeBNhkeswg%2BhdCf1kSzMEJduota%3D6UrNq4z2PQRtzEQ%40mail.gmail.com.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golan...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/022a5bb5-be27-4721-afe4-7e08f4531a3d%40googlegroups.com.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscr...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/24f60a17-c572-433f-b1ff-10cdad98458f%40googlegroups.com.


-- 

You received this message because you are subscribed to the Google Groups "golang-nuts" group.

To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscr...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/2030733290.1497.1575486349947%40wamui-sadie.atl.sa.earthlink.net.

Re: [go-nuts] Workaround for missing RWMutex.Try*Lock()

Reply via email to