Recursive mutex implementation?

[Jens Alfke]

I’ve noticed that sync.Mutex isn't recursive — so if you lock one, and then lock it again on the same goroutine, you deadlock. This is kind of annoying (a method that locks the mutex can’t call another method that also locks it, unlike e.g. synchronized methods in Java). Worse is that RWLock won’t let you grab the read-lock and then later the write-lock — it deadlocks the same way. So I have a few questions:

(1) Is there a recursive lock implementation? I didn’t see one in the package dashboard. (And would an implementation in Go be a lot slower than the built-in one?)

(2) Is there already a proposal to add one to the standard sync package? I think this would be a good idea, especially since some popular languages like Java and Objective-C (and C#?) have synchronization primitives based on recursive locks, so it’s a bit jarring to switch to non-recursive ones in Go.

(3) Without such a class, how can I implement a read/write mutex where I can “promote” a read to a write? For example, a getter method that caches a value would need to grab the read lock first, then promote it to a write lock if it needs to update the cache. Do I use two Mutex objects, one for reading and one for writing, and always order them so I grab the read lock first, then the write?

—Jens

[Dave Cheney]

Hello

> (1) Is there a recursive lock implementation? I didn’t see one in the package dashboard. (And would an implementation in Go be a lot slower than the built-in one?)

I don't see why it would be intrinsically slower, all the current sync
types are implemented using sync/atomic operations.

> (2) Is there already a proposal to add one to the standard sync package? I think this would be a good idea, especially since some popular languages like Java and Objective-C (and C#?) have synchronization primitives based on recursive locks, so it’s a bit jarring to switch to non-recursive ones in Go.

Maybe you could explain a bit more about the problem you are trying to
solve, rather than the solution you would like to use.

> (3) Without such a class, how can I implement a read/write mutex where I can “promote” a read to a write? For example, a getter method that caches a value would need to grab the read lock first, then promote it to a write lock if it needs to update the cache. Do I use two Mutex objects, one for reading and one for writing, and always order them so I grab the read lock first, then the write?

This has been discussed a few times on the mailing list. I don't
remember the details, but I think it is prone to deadlocks.

[Robert]

On Monday, 25 February 2013 03:36:01 UTC+1, Jens Alfke wrote:

(3) Without such a class, how can I implement a read/write mutex where I can “promote” a read to a write? For example, a getter method that caches a value would need to grab the read lock first, then promote it to a write lock if it needs to update the cache. Do I use two Mutex objects, one for reading and one for writing, and always order them so I grab the read lock first, then the write?

What should happen if two threads have the read lock and both wish to promote it to a write lock? You either need a read, promotable, and write lock or you need the Promote() call to possibly fail. Your two-mutex implementation IIUC (I understand that for reads first lock is RLocked and for writes the first one is RLocked and second is Locked) doesn't prevent readers concurrent with writers: it just prevents two concurrent writers.

Robert

[Jens Alfke]

On Feb 24, 2013, at 6:45 PM, Dave Cheney <da...@cheney.net> wrote:

> Maybe you could explain a bit more about the problem you are trying to
> solve, rather than the solution you would like to use.

The typical problem is that you have two public methods A and B, each of which has to acquire the mutex before accessing the internal data. Method A wants to call method B (maybe it performs a superset of B’s functionality.) Unfortunately this deadlocks. So you have to refactor the code by moving the main body of B into an un-locked internal method b that both A and B can call.

By contrast, in Java a ‘synchronized’ method or block can freely call into another synchronized method, since the mutexes used are recursive. (Ditto for Objective-C’s @synchronized blocks.)

As I said, this is mostly just annoying. It’s the read-write lock promotion that’s actively confusing me.

> This has been discussed a few times on the mailing list. I don't
> remember the details, but I think it is prone to deadlocks.

Hm. I don’t see why it would deadlock, as long as you always make sure to grab the read lock before the write one. But I admit synchronization primitives are notoriously tricky (which is why I really don’t want to get into rolling my own, just like I don’t want to roll my own crypto primitives…)

—Jens

[Kevin Gillette]

On Sunday, February 24, 2013 7:45:27 PM UTC-7, Dave Cheney wrote:

Maybe you could explain a bit more about the problem you are trying to
solve, rather than the solution you would like to use.

The behavior and properties of recursive/reentrant locks are well-known -- it's not usually one of those things that people would ask for if they didn't know what they were doing.  I too have had cases where a mutex of some description is the right fit, but that I've had to demote common operations into unexported methods, provided exported methods that do nothing at all besides acquiring/releasing the lock and calling the demoted methods.

[andrey mirtchovski]

> The behavior and properties of recursive/reentrant locks are well-known --

saying 'the solution is well known' still doesn't do much to describe
the problem. maybe the behaviour of reentrant locks needs to be
reiterated just for this list where not everyone is used to
concurrency in terms of locking. there may be an obvious idiomatic
solution using goroutines (a write arbitrator, for example) that we
wouldn't know to suggest because we're not familiar with the problem.

[Steven Blenkinsop]

On Sunday, 24 February 2013, Jens Alfke wrote:

> This has been discussed a few times on the mailing list. I don't
> remember the details, but I think it is prone to deadlocks.

Hm. I don’t see why it would deadlock, as long as you always make sure to grab the read lock before the write one.

If two goroutines are holding read locks, promote will block. If both try to call promote, they'll deadlock. You'd have to try promote, and release your read lock if it would block, or perhaps if only if someone else is waiting on a promote.

[Kevin Gillette]

http://en.wikipedia.org/wiki/Reentrant_mutex

Gist is: a given thread can acquire the reentrant mutex any number of times, the first acquisition will block until the lock is acquired, while subsequent locking attempts from the same thread (goroutine) will complete immediately. The mutex must be unlocked the same number of times as it is locked.

This is similar to sub-transactions in database systems.

The benefit is that it's a major convenience to programmers, since the programmer does not have deliberately organize code (which can reduce readability/maintainability) just to make sure they only lock the mutex once even if a series of (sub)operations need to be completed in critical sections. I would not expect it to have more of a chance of deadlocks occurring due to programmer error, since if a programmer can be expected to call unlock (often deferred) for every lock call in a regular mutex, then they can be expected to, exactly the same, call unlock for every lock call in a reentrant mutex.

[Kevin Gillette]

It sounds like we're talking about two different things -- a reentrant mutex (also called recursive mutex), and a RWMutex with the ability to promote an RLock to a write Lock. This has been discussed before, and I believe it was determined that while demotion is trivial (turning a write Lock into an RLock), a blocking mutex implementation (as opposed to some locking setups that return an error if the lock couldn't be acquired) has too many problems when trying to promote, since at most one promotion can be guaranteed to work (all others must fail, since the intent is that you want assurances that the state hasn't changed since you held the RLock).

[Devon H. O'Dell]

2013/2/24 Steven Blenkinsop <stev...@gmail.com>:

No! It absolutely will not deadlock!

If both try calling promote, you will have the same behavior you would
when attempting to have two writers: one will (atomically) acquire the
lock, the other will block trying to acquire it. It's not that
complicated:

func (rw *RWMutex) Promote() {
rw.RUnlock();
rw.Lock();
}

Done. The atomicity doesn't have to apply to the whole block here: the
semantics of RUnlock and Lock aren't vulnerable to deadlocks due to
pre-emption or some kind of race. RUnlock is non-blocking, and Lock
must wait for 0 readers and 0 writers.

No deadlocks, and no reason to get confused.

--dho

> --
> 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.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>

[Steven Blenkinsop]

On Sun, Feb 24, 2013 at 10:56 PM, Kevin Gillette <extempor...@gmail.com> wrote:

It sounds like we're talking about two different things

Yes ;).

 

a reentrant mutex (also called recursive mutex), and a RWMutex with the ability to promote an RLock to a write Lock. This has been discussed before, and I believe it was determined that while demotion is trivial (turning a write Lock into an RLock), a blocking mutex implementation (as opposed to some locking setups that return an error if the lock couldn't be acquired) has too many problems when trying to promote, since at most one promotion can be guaranteed to work (all others must fail, since the intent is that you want assurances that the state hasn't changed since you held the RLock).

If you need this guarantee, then yes, this is a problem. 

On Sun, Feb 24, 2013 at 11:07 PM, Devon H. O'Dell <devon...@gmail.com> wrote:

No! It absolutely will not deadlock!

If both try calling promote, you will have the same behavior you would
when attempting to have two writers: one will (atomically) acquire the
lock, the other will block trying to acquire it. It's not that
complicated:

func (rw *RWMutex) Promote() {
    rw.RUnlock();
    rw.Lock();
}

Done. The atomicity doesn't have to apply to the whole block here: the
semantics of RUnlock and Lock aren't vulnerable to deadlocks due to
pre-emption or some kind of race. RUnlock is non-blocking, and Lock
must wait for 0 readers and 0 writers.

No deadlocks, and no reason to get confused. 

Assuming you don't care if someone else holds the promotion first, then yes, this is okay. But in that case, you just need two RWMutexes (untested):

http://play.golang.org/p/9KUvLb8MwE

Obviously, you can simplify this if you don't need RLocker.

[Dave Cheney]

> Assuming you don't care if someone else holds the promotion first, then yes,
> this is okay. But in that case, you just need two RWMutexes (untested):

Ahh, that is the thing I couldn't remember. It is currently not
possible to upgrade from the Read Lock to the Write Lock atomically,
you have to drop your Read Lock first, which means you have to test
your preconditions again on acquiring the Write Lock.

[Kyle Lemons]

Problem with reentrant locks:

Data structure has two locks, Alpha and Bravo.  To prevent deadlocks, it is specified that, when both are needed, Alpha must be locked before Bravo.  Method X only needs Bravo, and so only locks Bravo.  Method Y needs both, and so locks Alpha and then Bravo.  Adding a call to Y within X could succeed if Alpha and Bravo were reentrant mutexes, despite this breaking the lock policy in a way which is very difficult to spot.

Problem with write lock promotion:

When you RLock a RWMutex, the data is guaranteed not to change until you release the RLock.  So, when two processes both hold and RLock, neither can promote to a WLock until the other has released the RLock.  Otherwise you could get into a situation where the data you accessed while RLocked is not the same as the data once the write promotion has succeeded.

--

[John Nagle]

Reentrant locks make sense for object-oriented languages.
There's a concept of control being "inside an object".
Objects have invariants which are supposed to be true when
control is not inside the object. Reentrant locks are usually
an issue for object methods which are callable from both inside
and outside the object. From a formal perspective, there should
be no such methods, because a method can be called from within
the object with the object invariant not true.

Go doesn't have a real concept of "inside an object", or
of private and public members. The visibility boundary is the
package, not the struct. In C++ terms, all structs of a package
are friends. Concepts like object invariants don't map
well to Go.

Also, goroutines are anonymous. There's no such
thing as a goroutine ID at the language level. So
you can't write a recursive lock in Go without
breaking through to the implementation level, or carrying
around some user-implemented goroutine ID. So, arguably
re-entrant mutexes don't belong in the language.

Effective Go' says "Do not communicate by sharing memory; instead,
share memory by communicating". If you need recursive locks, you're
supposedly getting too fancy with shared data, and are doing it wrong.

John Nagle

[Kevin Gillette]

On Sunday, February 24, 2013 9:16:15 PM UTC-7, Steven Blenkinsop wrote:

Assuming you don't care if someone else holds the promotion first, then yes, this is okay. But in that case, you just need two RWMutexes (untested):

There's literally no semantic difference between "not caring if someone else promotes first" and the current process of releasing an RLock, grabbing a write Lock, and checking the state to see if it still meets expectations. In other words, if you don't care if another goroutine promotes first, then you don't need or want promotion at all.

[Jens Alfke]

On Feb 24, 2013, at 8:21 PM, Kyle Lemons <kev...@google.com> wrote:

Problem with reentrant locks:

Data structure has two locks, Alpha and Bravo.  To prevent deadlocks, it is specified that, when both are needed, Alpha must be locked before Bravo.  Method X only needs Bravo, and so only locks Bravo.  Method Y needs both, and so locks Alpha and then Bravo.  Adding a call to Y within X could succeed if Alpha and Bravo were reentrant mutexes, despite this breaking the lock policy in a way which is very difficult to spot.

Agreed, and lock ordering is part of why I treat mutexes of any sort very gingerly. It is impossible to make mutexes not be dangerous in one way or another. Nonetheless, recursive locks are something a great many programmers have experience with from other languages, that avoid some of the dangers that non-recursive locks are prone to (while creating others, yes.) I don’t think it’s a bad idea to let people pick a dangerous tool they’re familiar with, over another dangerous tool they’re not.

(If I sound a little testy, it’s because I’m getting a sense that the lack of recursive locks might be intentional, another of the many religious design decisions made by Go, like the one true formatting style and lack of inheritance and so forth. I’m getting a bit weary of running into more of these.)

Problem with write lock promotion:

When you RLock a RWMutex, the data is guaranteed not to change until you release the RLock.  So, when two processes both hold and RLock, neither can promote to a WLock until the other has released the RLock.  Otherwise you could get into a situation where the data you accessed while RLocked is not the same as the data once the write promotion has succeeded.

This is true. But lock promotion is successfully used for things like database transactions. I am trying and failing right now to remember the algorithm used by SQLite, for example; I may need to go look it up.

—Jens

[Jim Whitehead II]

On Mon, Feb 25, 2013 at 6:39 AM, Jens Alfke <je...@mooseyard.com> wrote:

On Feb 24, 2013, at 8:21 PM, Kyle Lemons <kev...@google.com> wrote:

Problem with reentrant locks:

Data structure has two locks, Alpha and Bravo.  To prevent deadlocks, it is specified that, when both are needed, Alpha must be locked before Bravo.  Method X only needs Bravo, and so only locks Bravo.  Method Y needs both, and so locks Alpha and then Bravo.  Adding a call to Y within X could succeed if Alpha and Bravo were reentrant mutexes, despite this breaking the lock policy in a way which is very difficult to spot.

Agreed, and lock ordering is part of why I treat mutexes of any sort very gingerly. It is impossible to make mutexes not be dangerous in one way or another. Nonetheless, recursive locks are something a great many programmers have experience with from other languages, that avoid some of the dangers that non-recursive locks are prone to (while creating others, yes.) I don’t think it’s a bad idea to let people pick a dangerous tool they’re familiar with, over another dangerous tool they’re not.

(If I sound a little testy, it’s because I’m getting a sense that the lack of recursive locks might be intentional, another of the many religious design decisions made by Go, like the one true formatting style and lack of inheritance and so forth. I’m getting a bit weary of running into more of these.)

I'm not sure that this is an intentional design decision, so much as a decision that follows from other design decisions (and I think it is worth making such a distinction). When goroutines have no form of identity and there is no concept of being 'inside an object', then it is difficult to see how you could begin to implement a recursive lock in a way that makes sense.

Certainly sync.Mutex is not recursive, and I think that's a reasonable decision. It's a low-level mechanism for providing mutual exclusion. Most people would expect the following code to fail, considering almost 50   years of experience and research with working with monitors and semaphores.

m.Lock()

m.Lock()

So recursion is a special case, an enhancement of sync.Mutex, in the same way that a RWMutex is a special case with different semantics. These differences make sense. Right now its not immediately obvious how you could use runtime.Semacquire to implement a recursive mutex.

Assume you have your own notion of identity (say, using strings) that you can use, how could you implement a recursive mutex using the sync/atomic and runtime packages. That's may reveal some useful changes to the runtime that could enable this sort of this for those who want it.

I have felt the pain of this, having to split my API into a 'locking' public API and a private 'non-locking' API. It can make things difficult when designing a program, with this sort of mutual exclusion requirement. That's not to say I *want* this sort of package, but I do think its worth looking into what it would take to provide one.

Remember that sync.Mutex is just provided in a package. There's nothing to stop other forms of mutual exclusion from being provided as packages for those who want something a little different.

- Jim

Problem with write lock promotion:

When you RLock a RWMutex, the data is guaranteed not to change until you release the RLock.  So, when two processes both hold and RLock, neither can promote to a WLock until the other has released the RLock.  Otherwise you could get into a situation where the data you accessed while RLocked is not the same as the data once the write promotion has succeeded.

This is true. But lock promotion is successfully used for things like database transactions. I am trying and failing right now to remember the algorithm used by SQLite, for example; I may need to go look it up.

—Jens

--

[Rémy Oudompheng]

On 2013/2/25 Kevin Gillette <extempor...@gmail.com> wrote:
> http://en.wikipedia.org/wiki/Reentrant_mutex
>
> Gist is: a given thread can acquire the reentrant mutex any number of times,
> the first acquisition will block until the lock is acquired, while
> subsequent locking attempts from the same thread (goroutine) will complete
> immediately. The mutex must be unlocked the same number of times as it is
> locked.
>
> This is similar to sub-transactions in database systems.
>
> The benefit is that it's a major convenience to programmers, since the
> programmer does not have deliberately organize code (which can reduce
> readability/maintainability) just to make sure they only lock the mutex once
> even if a series of (sub)operations need to be completed in critical
> sections. I would not expect it to have more of a chance of deadlocks
> occurring due to programmer error, since if a programmer can be expected to
> call unlock (often deferred) for every lock call in a regular mutex, then
> they can be expected to, exactly the same, call unlock for every lock call
> in a reentrant mutex.

And such a program will immediately deadlock whenever you turn a for
loop into a parallel for idiom, or fork a goroutine for a stupid
reason (for example to break an annoying stack split).

It is deliberate that goroutines don't have "goroutine-local global
variables" or reliable IDs, and I think it is better and simpler that
the user keeps a small boolean to remember not to lock things.

Rémy.

[Rémy Oudompheng]

2013/2/25 Dave Cheney <da...@cheney.net> wrote:
>> (3) Without such a class, how can I implement a read/write mutex where I can “promote” a read to a write? For example, a getter method that caches a value would need to grab the read lock first, then promote it to a write lock if it needs to update the cache. Do I use two Mutex objects, one for reading and one for writing, and always order them so I grab the read lock first, then the write?
>
> This has been discussed a few times on the mailing list. I don't
> remember the details, but I think it is prone to deadlocks.

It was indeed discussed in issue 4026
(http://code.google.com/p/go/issues/detail?id=4026)

Rémy.

[Dave Cheney]

Thank you. That was the discussion I was thinking of.

[Jens Alfke]

On Feb 24, 2013, at 10:06 PM, Jim Whitehead II <jnwh...@gmail.com> wrote:

I'm not sure that this is an intentional design decision, so much as a decision that follows from other design decisions (and I think it is worth making such a distinction). When goroutines have no form of identity and there is no concept of being 'inside an object', then it is difficult to see how you could begin to implement a recursive lock in a way that makes sense.

Good point. Internally of course a goroutine must have an identity, but if that's not exposed to Go code then it wouldn’t be possible to implement recursive mutexes in Go. They’d have to be provided as primitives by the runtime.

Certainly sync.Mutex is not recursive, and I think that's a reasonable decision. It's a low-level mechanism for providing mutual exclusion. Most people would expect the following code to fail, considering almost 50   years of experience and research with working with monitors and semaphores.

m.Lock()

m.Lock()

I know this, but my _practical_ experience with multithreading has been in languages that provide recursive mutexes as built-in constructs, so it was surprising to me to run into a mutex that deadlocks this way just like in my old college textbooks. As I keep saying, given the popularity of Java, a lot of programmers coming to Go are going to make the naive assumption that sync.Mutex is a direct replacement for “synchronized”.

Remember that sync.Mutex is just provided in a package. There's nothing to stop other forms of mutual exclusion from being provided as packages for those who want something a little different.

Unless their implementation needs to keep track of goroutines, as a recursive mutex would. Then you’re stuck, unless you want to make the API awkward by requiring some kind of token to keep track of who has the lock.

—Jens

[Jens Alfke]

On Feb 24, 2013, at 10:10 PM, Rémy Oudompheng <remyoud...@gmail.com> wrote:

And such a program will immediately deadlock whenever you turn a for
loop into a parallel for idiom, or fork a goroutine for a stupid
reason (for example to break an annoying stack split).

It took a bit of thought, but I see your point — if I lock the mutex and spawn some goroutines to do the work, they’re not going to be holding the lock, so if they call something that locks it they’ll block; and if I then block waiting for the goroutines to complete, it’s a deadlock.

So the desire to make goroutines very lightweight and allow their promiscuous use by programs, conflicts with locking semantics that put a lot of weight on the identity of specific goroutines. That makes sense.

Still, my gut feeling is that most modules won’t be mixing locks and goroutines much, since they’re often alternative solutions to the same problems. But I haven’t written enough parallel Go code to know if that’s accurate.

—Jens

[wkharold]

There's also this discussion of the lack of reentrant mutexes: https://groups.google.com/forum/?fromgroups=#!searchin/golang-nuts/reentrant$20mutex/golang-nuts/XqW1qcuZgKg/tYq8frpidd8J. The comments by Russ Cox and Rob Pike are especially helpful in understanding the issues involved.

... WkH

[Robert Johnstone]

Hello,

You've probably thought of this, but since you are manually managing locking and unlocking, recursive mutexes are just a convenience.  You can factor out code you want to call while holding the lock.  It is perhaps a little more error prone, but at least the code changes will be minimal.

http://play.golang.org/p/KT4j0dXKah

[John Nagle]

On 2/24/2013 9:39 PM, Jens Alfke wrote:

> (If I sound a little testy, it�s because I�m getting a sense that the

> lack of recursive locks might be intentional, another of the many
> religious design decisions made by Go, like the one true formatting

> style and lack of inheritance and so forth. I�m getting a bit weary

> of running into more of these.)

It seems to be intentional. See

https://groups.google.com/forum/?fromgroups=#!searchin/golang-nuts/reentrant$20mutex/golang-nuts/XqW1qcuZgKg/tYq8frpidd8J

It's amusing to see the Go people talking about "invariants".
Go isn't a tight enough language to have enforceable invariants.
For a modern one that is, see "Spec#"
(http://research.microsoft.com/en-us/projects/specsharp/)

Object invariants are a useful concept. The general idea is that
1) at most one activity (thread, goroutine, whatever) can be
active inside an object at a time, and
2) there are invariants (Boolean expressions) which are true
whenever zero activities are inside the object. This
is quite useful. Objects with internal structure, like trees
or hashes, have a consistency condition which must hold when
when the object is not being modified.

To make this work, the language must be clear about what
"inside an object" means. Most languages, even those with
invariants in the language, are hazy about this. If you
call out of an object and call back in via a public method,
you've violated the rules. (This is a classic cause of bugs
in GUI libraries, which tend to be a huge collection of
tightly coupled objects frantically calling each other.)
In a system without recursive locks, you'd deadlock.
Recursive locks are mostly a hack to allow calling a
public method from inside an object.

The Spec# developers were forced to get very clear about
the inside/outside distinction. They probably did a
better job of it than anyone previously had, because
they had to make it work for objects with concurrency.

Go, lacking objects, doesn't have a clear inside/outside
distinction like that. Control is never "inside a struct".
With Go's type system, structs don't own their methods.
The public/private distinction in Go is at the package level,
not the struct level. So it's hard to even talk about
invariants in Go. There's no language syntax for them,
and when they would apply is vague.

If you don't share data between goroutines at all, and
do everything across channels, there's no problem, of course.
But in practice, Go programs mostly seem to use shared data,
use channels as locks and to carry indicators of what shared
data to work on, and still need mutexes.

I'd suggest sending data over channels, not sharing data,
not sending references, and profiling to see if that's really
a problem. Modern CPUs are very fast at copying and at
accessing recently copied data that's still in cache.
Avoiding copying matters less than it did on older CPUs.

Deep copy support at the compiler level would probably be
more useful than recursive mutexes. There's a package for
deep copying, but it uses the reflection API to disassemble
the objects, so it has to do a job interpretively that the
compiler could do once at compile time.

John Nagle

[Devon H. O'Dell]

2013/2/25 John Nagle <na...@animats.com>:

> On 2/24/2013 9:39 PM, Jens Alfke wrote:
>

>> (If I sound a little testy, it’s because I’m getting a sense that the

>> lack of recursive locks might be intentional, another of the many
>> religious design decisions made by Go, like the one true formatting

>> style and lack of inheritance and so forth. I’m getting a bit weary

>> of running into more of these.)
>
> It seems to be intentional. See
>
> https://groups.google.com/forum/?fromgroups=#!searchin/golang-nuts/reentrant$20mutex/golang-nuts/XqW1qcuZgKg/tYq8frpidd8J
>
> It's amusing to see the Go people talking about "invariants".
> Go isn't a tight enough language to have enforceable invariants.
> For a modern one that is, see "Spec#"
> (http://research.microsoft.com/en-us/projects/specsharp/)

I don't understand this statement. Invariants are a concept, an idea.
One enforces invariance in simultaneous execution environment by (for
instance) serializing access to the data that must not change. A mutex
protects a critical section. The critical section is so-named because
there need to be guarantees that behavior will not vary as a result of
simultaneous execution. So we can define an invariants in terms of the
data we want to protect in relation to whether we protect them. Go
(for all intents and purposes) requires that level of protection, and
invariance of data is solvable through channels and / or functionality
provided by the sync package.

> Object invariants are a useful concept. The general idea is that
> 1) at most one activity (thread, goroutine, whatever) can be
> active inside an object at a time, and
> 2) there are invariants (Boolean expressions) which are true
> whenever zero activities are inside the object. This
> is quite useful. Objects with internal structure, like trees
> or hashes, have a consistency condition which must hold when
> when the object is not being modified.
>

> [snip]

It sounds like you're talking about access paradigms and "ownership"
in a way that Go indeed does not support, so I will concede that Go
does not support this sort of "invariant". But I don't understand why
that makes Go a language that is "not tight enough to have enforceable
invariants." I am not familiar with Spec#, and I may also not be
familiar with what you mean when you say "enforceable invariant." I
can certainly enforce invariance by careful ordering of locking and
unlocking, or by using the "share memory by communicating" paradigm
exposed by Go.

Either way, there isn't anything stopping one from making a hashmap
package that guarantees invariance in read / write access by either
using locks internally or through implementing lock-free algorithms
for interacting with the data structure.

I'm definitely interested in understanding what, if anything, I am missing here.

--dho

[Jan Mercl]

On Mon, Feb 25, 2013 at 7:50 PM, John Nagle <na...@animats.com> wrote:
> It's amusing to see the Go people talking about "invariants".
> Go isn't a tight enough language to have enforceable invariants.

This recurring, specific FUD/BS has been discussed on this list ad
nausea. Is there an agenda for it?

-j

[John Nagle]

On 2/25/2013 11:02 AM, Devon H. O'Dell wrote:
> 2013/2/25 John Nagle <na...@animats.com>:
>> On 2/24/2013 9:39 PM, Jens Alfke wrote:
>>

>>> (If I sound a little testy, it�s because I�m getting a sense that the

>>> lack of recursive locks might be intentional, another of the many
>>> religious design decisions made by Go, like the one true formatting

>>> style and lack of inheritance and so forth. I�m getting a bit weary

>>> of running into more of these.)
>>
>> It seems to be intentional. See
>>
>> https://groups.google.com/forum/?fromgroups=#!searchin/golang-nuts/reentrant$20mutex/golang-nuts/XqW1qcuZgKg/tYq8frpidd8J
>>
>> It's amusing to see the Go people talking about "invariants".
>> Go isn't a tight enough language to have enforceable invariants.
>> For a modern one that is, see "Spec#"
>> (http://research.microsoft.com/en-us/projects/specsharp/)
>
> I don't understand this statement. Invariants are a concept, an idea.

Ah. I see the problem.

By an "enforceable invariant", I mean one that can potentially
be machine checked, and for which passing the check provides
a guarantee that the invariant is true when it is supposed to be.
This can be done either with an automated theorem proving system,
as in Spec# and the Microsoft Driver Verifier, or at run time, as
in Eiffel.

Before you can even start thinking about doing that, you
have to have clarity on exactly what code can access which data,
and which data is locked by which locks. Go, like C, doesn't
really address this for shared data.

Serious invariants are supported by the language, or
some tool set that processes a version of the language with
invariants. Go doesn't support that, and it would be hard to
add, because of the vagueness about the inside/outside issue.

Sometimes one sees invariants written as comments in code.
That at least gives guidance to maintenance programmers.
Invariants which are not written down anywhere are just
hand-waving.

> One enforces invariance in simultaneous execution environment by (for
> instance) serializing access to the data that must not change. A mutex
> protects a critical section. The critical section is so-named because
> there need to be guarantees that behavior will not vary as a result of
> simultaneous execution.

That's the simple case one sees in programming textbooks. This
thread, though, is about recursive mutexes. By the time you want or
need a recursive mutex, things have become complex enough that the
inside/outside distinction is getting confused. Typically a
recursive mutex is needed where some long call chain results in
the same data being messed with from multiple function calls
in the same thread/activity/goroutine. You're now in
territory where obscure concurrency/reentrancy bugs appear.

> It sounds like you're talking about access paradigms and "ownership"
> in a way that Go indeed does not support, so I will concede that Go
> does not support this sort of "invariant". But I don't understand why
> that makes Go a language that is "not tight enough to have enforceable
> invariants."

Invariants are a property of data. A key point is ensuring that
the data doesn't change outside of regions where it's supposed to.
Thus, access control and ownership matter when talking about invariants.
Go structs are weakly protected in that sense. "Leakage" out of
a critical section is possible, and can arise subtly through
implicit references like slices.

> Either way, there isn't anything stopping one from making a hashmap
> package that guarantees invariance in read / write access by either
> using locks internally or through implementing lock-free algorithms
> for interacting with the data structure.

The simple case is easy to get right. But here, we have
people arguing for better support for complex, error-prone cases.

Send data across channels, like Effective Go says to do, and
things will go well. Don't use channels as a locking primitive, like
the examples in Effective Go actually do. If you need recursive locks,
you're trying to write C in Go.

John Nagle

[Kyle Lemons]

On Mon, Feb 25, 2013 at 11:36 AM, John Nagle <na...@animats.com> wrote:

On 2/25/2013 11:02 AM, Devon H. O'Dell wrote:
> 2013/2/25 John Nagle <na...@animats.com>:
>> On 2/24/2013 9:39 PM, Jens Alfke wrote:
>>

>>> (If I sound a little testy, it’s because I’m getting a sense that the

>>> lack of recursive locks might be intentional, another of the many
>>> religious design decisions made by Go, like the one true formatting

>>> style and lack of inheritance and so forth. I’m getting a bit weary

>>> of running into more of these.)
>>
>>    It seems to be intentional.  See
>>
>> https://groups.google.com/forum/?fromgroups=#!searchin/golang-nuts/reentrant$20mutex/golang-nuts/XqW1qcuZgKg/tYq8frpidd8J
>>
>> It's amusing to see the Go people talking about "invariants".
>> Go isn't a tight enough language to have enforceable invariants.
>> For a modern one that is, see "Spec#"
>> (http://research.microsoft.com/en-us/projects/specsharp/)
>
> I don't understand this statement. Invariants are a concept, an idea.

   Ah.  I see the problem.

   By an "enforceable invariant", I mean one that can potentially
be machine checked, and for which passing the check provides
a guarantee that the invariant is true when it is supposed to be.
This can be done either with an automated theorem proving system,
as in Spec# and the Microsoft Driver Verifier, or at run time, as
in Eiffel.

   Before you can even start thinking about doing that, you
have to have clarity on exactly what code can access which data,
and which data is locked by which locks. Go, like C, doesn't
really address this for shared data.

If you share memory by communicating, you don't end up needing locks and such very often, and when you do, they tend to be simple.  The boilerplate and language support for such mechanisms does not seem a right fit for go.

 

[Andy Balholm]

On Monday, February 25, 2013 11:36:29 AM UTC-8, John Nagle wrote:

   Sometimes one sees invariants written as comments in code.
That at least gives guidance to maintenance programmers.
Invariants which are not written down anywhere are just
hand-waving.

The main place I've seen references to invariants was "loop invariants" in WEB programs written by Donald Knuth. Of course they were mentioned in the comments—or perhaps commentary would be a better word for the prose section of a literate program. But they were definitely not a language feature. 

[Jim Whitehead II]

On Mon, Feb 25, 2013 at 7:18 AM, Jens Alfke <je...@mooseyard.com> wrote:

On Feb 24, 2013, at 10:06 PM, Jim Whitehead II <jnwh...@gmail.com> wrote:

I'm not sure that this is an intentional design decision, so much as a decision that follows from other design decisions (and I think it is worth making such a distinction). When goroutines have no form of identity and there is no concept of being 'inside an object', then it is difficult to see how you could begin to implement a recursive lock in a way that makes sense.

Good point. Internally of course a goroutine must have an identity, but if that's not exposed to Go code then it wouldn’t be possible to implement recursive mutexes in Go. They’d have to be provided as primitives by the runtime.

I think that's very unlikely, but I'm far from an authority. The anonymity of processes is one of the key differences between CSP and other concurrency models, such as the actor model. Exposing (even through the runtime) a way to distinguish between processes for this sort of purpose flies against that quite a bit and (I personally think) massively complicates the mental concurrency model.

 

Certainly sync.Mutex is not recursive, and I think that's a reasonable decision. It's a low-level mechanism for providing mutual exclusion. Most people would expect the following code to fail, considering almost 50   years of experience and research with working with monitors and semaphores.

m.Lock()

m.Lock()

I know this, but my _practical_ experience with multithreading has been in languages that provide recursive mutexes as built-in constructs, so it was surprising to me to run into a mutex that deadlocks this way just like in my old college textbooks. As I keep saying, given the popularity of Java, a lot of programmers coming to Go are going to make the naive assumption that sync.Mutex is a direct replacement for “synchronized”.

Hopefully the documentation and examples can help make the difference more distinct. The 'synchronized' keyword does all forms of magic to provide a lot of features that are fairly important in concurrent programming in a 100% object-oriented environment. They are very different beasts, although they both fall under 'providing mutual exclusion of some sort'. It's a big problem if people think they are the same.

It might be worth something in 'Effective Go' that talks about the differences between 'synchronized' and sync.Mutex. I don't think there's much of a need to distinguish from other languages, since C/C++ concurrency mechanisms seem mostly in-line with what Go provides.

  

Remember that sync.Mutex is just provided in a package. There's nothing to stop other forms of mutual exclusion from being provided as packages for those who want something a little different.

Unless their implementation needs to keep track of goroutines, as a recursive mutex would. Then you’re stuck, unless you want to make the API awkward by requiring some kind of token to keep track of who has the lock.

Yes, it's awkward, and the current runtime package doesn't expose goroutine identity. But we can implement it using channels in order to see how it might work. That's how I think about concurrency, so it's a good place to start.

I've been thinking about this problem since seeing the thread this morning (HOW it might be done, not whether or not it SHOULD be done), so here's one take on it.

Let's design a simple CSP model that describes how we want the system to function. We'll have two channels 'lock' and 'unlock' which take an integer as part of the message. This integer will represent a goroutine or process identifier.

RecMutex = let

    Unlocked = lock?id -> Locked(id, 1)

    Locked(id, n) = n < MAX_DEPTH & lock!id -> Locked(id, n+1)

                 [] n == 1 & unlock!id -> Unlocked

                 [] n > 1 & unlock!id -> Locked(id, n-1)

    within Unlocked

A RecMutex begins in the unlocked state, and will accept a lock message from one of its registered clients. Once locked by a client the same client can lock it again (up to a certain depth which is necessary to limit the model being checked). The client can also unlock the mutex. When the client has unlocked the same number of times it has locked, the mutex goes back to te 'Unlocked' state.

This seems to give us what we want. So let's build a thing that can use the mutex, a Locker:

Locker(id) = let

    Unlocked(id) = lock!id -> Locked(id, 1)

    Locked(id, n) = n < MAX_DEPTH & lock!id -> Locked(id, n+1)

                 [] n == 1 & unlock!id -> Unlocked(id)

                 [] n > 1 & unlock!id -> Locked(id, n-1)

                 [] work!id -> Locked(id, n)

    within Unlocked(id)

This looks mostly the same, except the locker only participates in events (channel communications) that include its own process identifier. In addition, while the mutex is locked, the locker can do some work, which is does by signalling the 'work' event.

We can then build a system that consists of N different lockers all competing for the re-entrant mutex. The lockers don't synchronize on any events, they just interleave. The mutex will synchronize with ALL of the lockers on any communications on the lock and unlock channels.

Lockers(n) = (||| id:{0..n-1} @ Locker(id))

System(n) = RecMutex [|lockEvents|] Lockers(n)

From here, we can do a sanity check to ensure the system is deadlock and livelock free, which it is.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Translating back to Go land, what we want to do is build a goroutine that can listen for lock messages from a number of registered clients. Once it receives a lock message, it will only listen for lock and unlock events from that client. Once the unlocks have matched the number of locks, it will go back to the unlocked state so another client can acquire it.

There are many different ways to put this together. I've chosen one that I'm familiar with, so bear with me.

Let's say we have a type that bundles a lock and unlock channel together:

type bundle struct {

lock chan bool

unlock chan bool

}

Our goroutine, given a chan *bundle, could listen for initial messages. Let's mirror the CSP code:

func loop(master chan *bundle) {

var b *bundle

unlocked:

select {

case b = <-master:

goto locked

}

locked:

count := 1

for {

select {

case <-b.lock:

count = count + 1

case <-b.unlock:

count = count - 1

if count == 0 {

goto unlocked

}

}

}

}

Once we receive a bundle on the 'primary' lock channel, we only listen to messages from that bundle, until the mutex has been properly unlocked.

So now we have a process that matched our definition and we know that it should be free from deadlocks (unless we've messed something up). At least we have a solid mental model of how our system should work.

But this is only part of the implementation, since we need to provide a way for goroutines to 'register' with this mutex and get a sync.Locker that they can call in the normal way.

That turns out to be a bit more difficult to get right. You have multiple clients that are all attempting to send their bundle to the mutex at the same time, in order to get exclusive access. Once obtained,  subsequent calls to the client's method should use the bundle's channels instead of of the 'master' channel.

So this means that a 'client' needs to have a way to track whether or not it is in a locked state. Storing this makes the client interface racy since multiple goroutines could share the same client (even though that goes against everything we're doing here). So we'll need to protect that either using a mutex or a data server process like the one used above.

The Lock method looks something like this:

func (c *client) Lock() {

  if c.bundle == nil {

    bundle := &bundle{

      make(chan bool),

      make(chan bool),

    }

    c.master <- bundle

  } else {

    c.bundle.lock <- true

  }

}

In addition we should probably track the number of times the lock has been locked, so we can match on the other side of things.

Putting this all together with a bunch of bad code and decoration we get a system that can be used like this:

rm := NewREMutex()

m1 := rm.NewClient()

m2 := rm.NewClient()

go worker(m1, done)

go worker(m2, done)

<-done

<-done

The worker function just takes a sync.Locker and is able to use it without knowing that it is any different than a normal mutex. Of course that's almost certainly one of the arguments against re-entrant mutexes in the first place, but this was just a form of mental masturbation in the first place.

There are several pitfalls here that were a bit unexpected. The server was the easier part, a simple translation of the CSP definition into Go. The clients are much more difficult.

Channels helped a lot when thinking about how I might structure something like this, but got in the way when it came to building the client.

Let's say we have C which is the client, and M which is the mutex server process. If we introduce any form of buffering between C and M, such as a forwarding process X, then it is possible for C to see the unlock message succeed and assume the object is free. It might then take action based on this, despite the fact that the mutex has not been unlocked yet.

This may only be a superficial issue, since the very next action the mutex takes is receiving the unlock message, but it didn't sit well with me having this dangling. Extended rendezvous would allow us to take action DURING the receive operation, removing the buffer.

I suspect that I'm rambling like a madman at 10:30 at night, but I enjoyed thinking about how I could apply the simple semantics of channels to a problem that seemed somewhat confusing and difficult.

I've attached the code (the client is using a mutex) and the CSP model for those that are interested. I probably made some mistakes along the way (and the code is FAR from idiomatic), but I'm sure someone will helpfully point these out for me =).

This probably deserves a more coherent narrative, so I may post this on my blog at some point in the future if anyone would be interested in a deeper look at the issue.

- Jim

[Russ Cox]

I don't have anything to add to this: https://groups.google.com/d/msg/golang-nuts/XqW1qcuZgKg/Ui3nQkeLV80J

[Kyle Lemons]

On Mon, Feb 25, 2013 at 1:42 PM, Jim Whitehead II <jnwh...@gmail.com> wrote:

On Mon, Feb 25, 2013 at 7:18 AM, Jens Alfke <je...@mooseyard.com> wrote:

On Feb 24, 2013, at 10:06 PM, Jim Whitehead II <jnwh...@gmail.com> wrote:

I'm not sure that this is an intentional design decision, so much as a decision that follows from other design decisions (and I think it is worth making such a distinction). When goroutines have no form of identity and there is no concept of being 'inside an object', then it is difficult to see how you could begin to implement a recursive lock in a way that makes sense.

Good point. Internally of course a goroutine must have an identity, but if that's not exposed to Go code then it wouldn’t be possible to implement recursive mutexes in Go. They’d have to be provided as primitives by the runtime.

I think that's very unlikely, but I'm far from an authority. The anonymity of processes is one of the key differences between CSP and other concurrency models, such as the actor model. Exposing (even through the runtime) a way to distinguish between processes for this sort of purpose flies against that quite a bit and (I personally think) massively complicates the mental concurrency model.

The runtime does have a notion of a goroutine ID, but this is an implementation detail and won't be exposed at a higher level.

 

Certainly sync.Mutex is not recursive, and I think that's a reasonable decision. It's a low-level mechanism for providing mutual exclusion. Most people would expect the following code to fail, considering almost 50   years of experience and research with working with monitors and semaphores.

m.Lock()

m.Lock()

I know this, but my _practical_ experience with multithreading has been in languages that provide recursive mutexes as built-in constructs, so it was surprising to me to run into a mutex that deadlocks this way just like in my old college textbooks. As I keep saying, given the popularity of Java, a lot of programmers coming to Go are going to make the naive assumption that sync.Mutex is a direct replacement for “synchronized”.

Hopefully the documentation and examples can help make the difference more distinct. The 'synchronized' keyword does all forms of magic to provide a lot of features that are fairly important in concurrent programming in a 100% object-oriented environment. They are very different beasts, although they both fall under 'providing mutual exclusion of some sort'. It's a big problem if people think they are the same.

It might be worth something in 'Effective Go' that talks about the differences between 'synchronized' and sync.Mutex. I don't think there's much of a need to distinguish from other languages, since C/C++ concurrency mechanisms seem mostly in-line with what Go provides.

  

Remember that sync.Mutex is just provided in a package. There's nothing to stop other forms of mutual exclusion from being provided as packages for those who want something a little different.

Unless their implementation needs to keep track of goroutines, as a recursive mutex would. Then you’re stuck, unless you want to make the API awkward by requiring some kind of token to keep track of who has the lock.

Yes, it's awkward, and the current runtime package doesn't expose goroutine identity. But we can implement it using channels in order to see how it might work. That's how I think about concurrency, so it's a good place to start.

I've been thinking about this problem since seeing the thread this morning (HOW it might be done, not whether or not it SHOULD be done), so here's one take on it.

I think there's a simpler solution.  Instead of using some sort of goroutine ID, you can pass around a "token" which is essentially a proxy for goroutine ID, and this can also store the lock depth of the mutex and know when to return it.  Straw man here:

http://play.golang.org/p/nF1hQzlu-y

Again, not saying it should be done, only that it takes less time to implement it than to complain about the fact that it doesn't exist :).

[Steven Blenkinsop]

Or just pass around a T for a held resource, and a chan T for a resource you have to acquire. Then you don't have a broken abstraction.

[Jim Whitehead II]

On Tue, Feb 26, 2013 at 12:02 AM, Kyle Lemons <kev...@google.com> wrote:

On Mon, Feb 25, 2013 at 1:42 PM, Jim Whitehead II <jnwh...@gmail.com> wrote:

On Mon, Feb 25, 2013 at 7:18 AM, Jens Alfke <je...@mooseyard.com> wrote:

On Feb 24, 2013, at 10:06 PM, Jim Whitehead II <jnwh...@gmail.com> wrote:

I'm not sure that this is an intentional design decision, so much as a decision that follows from other design decisions (and I think it is worth making such a distinction). When goroutines have no form of identity and there is no concept of being 'inside an object', then it is difficult to see how you could begin to implement a recursive lock in a way that makes sense.

Good point. Internally of course a goroutine must have an identity, but if that's not exposed to Go code then it wouldn’t be possible to implement recursive mutexes in Go. They’d have to be provided as primitives by the runtime.

I think that's very unlikely, but I'm far from an authority. The anonymity of processes is one of the key differences between CSP and other concurrency models, such as the actor model. Exposing (even through the runtime) a way to distinguish between processes for this sort of purpose flies against that quite a bit and (I personally think) massively complicates the mental concurrency model.

The runtime does have a notion of a goroutine ID, but this is an implementation detail and won't be exposed at a higher level.

Of course, I've already mentioned this twice in this thread.

 

Certainly sync.Mutex is not recursive, and I think that's a reasonable decision. It's a low-level mechanism for providing mutual exclusion. Most people would expect the following code to fail, considering almost 50   years of experience and research with working with monitors and semaphores.

m.Lock()

m.Lock()

I know this, but my _practical_ experience with multithreading has been in languages that provide recursive mutexes as built-in constructs, so it was surprising to me to run into a mutex that deadlocks this way just like in my old college textbooks. As I keep saying, given the popularity of Java, a lot of programmers coming to Go are going to make the naive assumption that sync.Mutex is a direct replacement for “synchronized”.

Hopefully the documentation and examples can help make the difference more distinct. The 'synchronized' keyword does all forms of magic to provide a lot of features that are fairly important in concurrent programming in a 100% object-oriented environment. They are very different beasts, although they both fall under 'providing mutual exclusion of some sort'. It's a big problem if people think they are the same.

It might be worth something in 'Effective Go' that talks about the differences between 'synchronized' and sync.Mutex. I don't think there's much of a need to distinguish from other languages, since C/C++ concurrency mechanisms seem mostly in-line with what Go provides.

  

Remember that sync.Mutex is just provided in a package. There's nothing to stop other forms of mutual exclusion from being provided as packages for those who want something a little different.

Unless their implementation needs to keep track of goroutines, as a recursive mutex would. Then you’re stuck, unless you want to make the API awkward by requiring some kind of token to keep track of who has the lock.

Yes, it's awkward, and the current runtime package doesn't expose goroutine identity. But we can implement it using channels in order to see how it might work. That's how I think about concurrency, so it's a good place to start.

I've been thinking about this problem since seeing the thread this morning (HOW it might be done, not whether or not it SHOULD be done), so here's one take on it.

I think there's a simpler solution.  Instead of using some sort of goroutine ID, you can pass around a "token" which is essentially a proxy for goroutine ID, and this can also store the lock depth of the mutex and know when to return it.  Straw man here:

http://play.golang.org/p/nF1hQzlu-y

Again, not saying it should be done, only that it takes less time to implement it than to complain about the fact that it doesn't exist :).

 

How is that really any different from what I've done? Mine is certainly more complicated, but that's because I intentionally approached it as a translation from the CSP model (since I know many people have no experience with CSP, but will be able to read the Go code). You also made the intentional decision to make Token non-goroutine-safe, something that I mention as being a possibility as well.

I think my post clearly indicates that I fully understand all of this, but wanted to come at it from a slightly different perspective, because I enjoy thinking about things in that way. I don't want to see re-entrant mutexes in the language because I think they're badly broken =)

[John Nagle]

On 2/25/2013 9:26 PM, Jim Whitehead II wrote:
> On Tue, Feb 26, 2013 at 12:02 AM, Kyle Lemons <kev...@google.com> wrote:
>
>> On Mon, Feb 25, 2013 at 1:42 PM, Jim Whitehead II <jnwh...@gmail.com>wrote:
>>
>>> On Mon, Feb 25, 2013 at 7:18 AM, Jens Alfke <je...@mooseyard.com> wrote:
>>>
>>>>
>>>> On Feb 24, 2013, at 10:06 PM, Jim Whitehead II <jnwh...@gmail.com>
>>>> wrote:

>> Let's design a simple CSP model that describes how we want the system to
>>> function. We'll have two channels 'lock' and 'unlock' which take an integer
>>> as part of the message.

Yes, you can do that. But constructing locks out of channels is
painful. If you need a mutex, use a mutex.

John Nagle

[Jim Whitehead II]

--
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.
For more options, visit https://groups.google.com/groups/opt_out.

It seems to me that your response completely misses the entire point of my post, which may mean I failed to communicate it effectively.

I am personally interested in using channel based communication as a mental model for reasoning about concurrency. I guessed that someone else might be interested in the reasoning process that I went through, so I shared it to the list. This includes defining something like a re-entrant mutex using channel communications. Thinking about it in those terms helps to reveal a different set of issues than you get from coming at it from the other side of things. I think those difficulties are useful.

I acknowledge several times in my post that I do not believe there is any practical use in having this sort of mutex in Go, because it just doesn't fit. I understand that you feel incredibly strongly about encouraging the use of channels for communication and not for mutual exclusion. I get that; I think most people on the mailing list get that, you made it incredibly clear.

That doesn't make an exercise like this futile. In fact, I think for me it highlights the difficulties of using channels (the buffering issue that I mention, without extended rendezvous) for mutual exclusion. It furthers the idea that mutex semantics can be expressed using channels and vice versa. 

In my post I am not advocating using channels for mutual exclusion.

- Jim

[David Leimbach]

I do not believe recursive mutex behaviors or code that relies on them do me or anyone who's ever going to maintain code any favors.

1. Mutexes protect invariants across multiple concurrently scheduled "thingies" (goroutines, threads, fibers, processes).  These should be held for the shortest time allowable to get your work done or you reduce the opportunity for overlap of work across your cores on a shared resource.

2. Code that is obviously taking a lock plans to mess with those invariants for a little bit, or at least rely on them not breaking. (mutex, read/write locks etc)

3. Code that takes the lock, and then takes it again appears to be written in a very sloppy way (in my opinion).  It's really trivial to make the functions that do mess with invariants in a C compilation unit "static" and the public API functions take the locks.  Then anything behind the "lock wall" can call the "allowed-to-mess-with-invariant-functions" all day.  This can be achieved in C++ with private member functions too.  Even if you do this, minimizing the time locks are held is a good idea.

It's interesting to also note that pthreads have recursive mutexes because of a dare... and the person who did it discourages their use greatly.

https://groups.google.com/forum/?hl=en&fromgroups=#!msg/comp.programming.threads/tcrTKnfP8HI/me2K7_byNdgJ

Dave