Workaround for missing RWMutex.Try*Lock()

134 views
Skip to first unread message

Liam Breck

unread,
Dec 3, 2019, 7:21:41 PM12/3/19
to golang-nuts
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?

burak serdar

unread,
Dec 3, 2019, 7:35:15 PM12/3/19
to Liam Breck, golang-nuts
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 golang-nuts...@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.

Robert Engels

unread,
Dec 3, 2019, 7:50:35 PM12/3/19
to burak serdar, Liam Breck, golang-nuts
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:
> To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CAMV2RqrDeBNhkeswg%2BhdCf1kSzMEJduota%3D6UrNq4z2PQRtzEQ%40mail.gmail.com.

Liam Breck

unread,
Dec 3, 2019, 7:52:35 PM12/3/19
to Robert Engels, burak serdar, golang-nuts
Which looks like...?

Robert Engels

unread,
Dec 3, 2019, 8:12:08 PM12/3/19
to Liam Breck, burak serdar, golang-nuts
Can’t code on the phone but a cas on the atomic then take the lock. But if you never need to block you don’t even need the lock. 

On Dec 3, 2019, at 6:52 PM, Liam Breck <networ...@gmail.com> wrote:



Liam

unread,
Dec 3, 2019, 8:31:19 PM12/3/19
to golang-nuts
Erm... not seeing how cas works to try a read-lock, which admits multiple callers...

Which looks like...?

>> 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.

burak serdar

unread,
Dec 3, 2019, 8:37:52 PM12/3/19
to Liam, golang-nuts
On Tue, Dec 3, 2019 at 6:31 PM Liam <networ...@gmail.com> wrote:
>
> Erm... not seeing how cas works to try a read-lock, which admits multiple callers...

Something like this should work:

TryLock:

if CompareAndSwap(&v,0,1) {
door.Lock()
return true
}
return false

Unlock:
door.Unlock()
Store(&v,0)
> To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/2d284bfc-3916-425a-9dd1-59b216ef23e2%40googlegroups.com.

Robert Engels

unread,
Dec 3, 2019, 8:39:48 PM12/3/19
to burak serdar, Liam Breck, golang-nuts
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.

Liam

unread,
Dec 3, 2019, 8:54:09 PM12/3/19
to golang-nuts
Busy means would-block, yes.

Burak thanks, but that doesn't work for read-lock.
>>> 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.

burak serdar

unread,
Dec 3, 2019, 10:05:18 PM12/3/19
to Liam, golang-nuts
On Tue, Dec 3, 2019 at 6:54 PM Liam <networ...@gmail.com> wrote:
>
> Busy means would-block, yes.
>
> Burak thanks, but that doesn't work for read-lock.

You are right, I keep reading it as Lock instead of RLock.

Here's another attempt at solving it:

https://play.golang.org/p/az3hnyIwe47
> To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@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.

robert engels

unread,
Dec 3, 2019, 10:52:54 PM12/3/19
to Liam, golang-nuts
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.


To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@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.

pierre...@gmail.com

unread,
Dec 4, 2019, 5:49:43 AM12/4/19
to golang-nuts

Robert Engels

unread,
Dec 4, 2019, 8:40:07 AM12/4/19
to pierre...@gmail.com, golang-nuts
That pkg is not a RW lock though - it is an exclusive mutex. The pseudo code I provided is a RW try lock.  

On Dec 4, 2019, at 4:49 AM, pierre...@gmail.com wrote:


--
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...@googlegroups.com.

Liam

unread,
Dec 4, 2019, 1:34:29 PM12/4/19
to golang-nuts
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().


@ianlancetaylor, is this worth a new proposal?

roger peppe

unread,
Dec 4, 2019, 1:50:50 PM12/4/19
to Liam, golang-nuts
Thanks to Robert Clapis via Twitter for this suggestion, using channels. As he said, it doesn't quite get there, because a reader can still acquire the lock even when a writer has requested it, but it's still potentially useful and reasonably simple:


To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@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.

Robert Engels

unread,
Dec 4, 2019, 2:06:38 PM12/4/19
to Liam, golang-nuts

For completeness, RWMutex.TryLock() is also needed. If you are modifying the stdlib, these are trivial changes to add these methods.
Reply all
Reply to author
Forward
0 new messages