Workaround for missing RWMutex.Try*Lock()

[Liam Breck]

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]

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]

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]

Which looks like...?

[Robert Engels]

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]

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]

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]

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]

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]

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]

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]

This may be of relevance to you:

https://pkg.go.dev/gvisor.dev/gvisor/pkg/tmutex?tab=doc

[Robert Engels]

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.

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/94c7a670-0a71-432a-aa19-035e1f4c9648%40googlegroups.com.

[Liam]

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?

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/022a5bb5-be27-4721-afe4-7e08f4531a3d%40googlegroups.com.

[roger peppe]

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:

https://play.golang.org/p/N33t7uyxeiM

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]

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