Experimenting with GO

Both statements are true. Go programs generally use goroutines and
channels to meet these sorts of needs. E.g., route all changes
through a single goroutine which therefore does not need locks. Or
use a single goroutine to manage the locks, and use a separate timer
goroutine to implement timeouts via a select statement.

Ian

The fundamental reason to use a mutex is that mutexes
protect invariants, perhaps internal invariants like
``p.Prev.Next == p for all elements of the ring,'' or perhaps
external invariants like ``my local variable x is equal to p.Prev.''

Locking a mutex asserts ``I need the invariants to hold''
and perhaps ``I will temporarily break those invariants.''
Releasing the mutex asserts ``I no longer depend on those
invariants'' and ``If I broke them, I have restored them.''

Understanding that mutexes protect invariants is essential to
identifying where mutexes are needed and where they are not.
For example, does a shared counter updated with atomic
increment and decrement instructions need a mutex?
It depends on the invariants. If the only invariant is that
the counter has value i - d after i increments and d decrements,
then the atmocity of the instructions ensures the
invariants; no mutex is needed. But if the counter must be
in sync with some other data structure (perhaps it counts
the number of elements on a list), then the atomicity of
the individual operations is not enough. Something else,
often a mutex, must protect the higher-level invariant.
This is the reason that operations on maps in Go are not
guaranteed to be atomic: it would add expense without
benefit in typical cases.

Let's take a look at recursive mutexes.
Suppose we have code like this:

func F() {
mu.Lock()
... do some stuff ...
G()
... do some more stuff ...
mu.Unlock()
}

func G() {
mu.Lock()
... do some stuff ...
mu.Unlock()
}

Normally, when a call to mu.Lock returns, the calling code
can now assume that the protected invariants hold, until
it calls mu.Unlock.

A recursive mutex implementation would make G's mu.Lock
and mu.Unlock calls be no-ops when called from within F
or any other context where the current thread already holds mu.
If mu used such an implementation, then when mu.Lock
returns inside G, the invariants may or may not hold. It depends
on what F has done before calling G. Maybe F didn't even realize
that G needed those invariants and has broken them (entirely
possible, especially in complex code).

Recursive mutexes do not protect invariants.
Mutexes have only one job, and recursive mutexes don't do it.

There are simpler problems with them, like if you wrote

func F() {
mu.Lock()
... do some stuff
}

you'd never find the bug in single-threaded testing.
But that's just a special case of the bigger problem,
which is that they provide no guarantees at all about
the invariants that the mutex is meant to protect.

If you need to implement functionality that can be called
with or without holding a mutex, the clearest thing to do
is to write two versions. For example, instead of the above G,
you could write:

// To be called with mu already held.
// Caller must be careful to ensure that ...
func g() {
... do some stuff ...
}

func G() {
mu.Lock()
g()
mu.Unlock()
}

or if they're both unexported, g and gLocked.

I am sure that we'll need TryLock eventually; feel free to
send us a CL for that. Lock with timeout seems less essential
but if there were a clean implementation (I don't know of one)
then maybe it would be okay. Please don't send a CL that
implements recursive mutexes.

Recursive mutexes are just a mistake, nothing more than
a comfortable home for bugs.

Russ

Say the mutex protects the invariant that a == b, as in these functions:

func up() {
mutex.Lock()
a++
// See below
b++
mutex.Unlock()
}

func down() {
mutex.Lock()
if a != b { panic("HELP!") }
a--
b--
mutex.Unlock()
}

What happens if down() is called on the line marked "See below" in f? (this could happen through subtle paths in realistic code, as you know.) The invariant is not true when down() is called *even though it holds the mutex*, and down() will panic.

That is what it means to say that reentrant mutexes don't preserve invariants. It's because they don't preserve invariants when called recursively, which defeats the purpose of having a mutex.

-rob

-rob

Acquiring mutexes in a different order in different code sounds like a
recipe for deadlock. And this approach in turn sounds very hard to
show to be correct. One of the great things about Go is cheap channel
communication mean that you don't have to reason your way through
complex scenarios like this. You can write code that is much easier
to understand and much more likely to be correct on a multicore
system.

Ian

Given that you're trying trying to implement a database lock manager,
perhaps there's some confusion between mutexes and locks. One way
databases implement concurrent transactions is via read/write locks.
But these are not the same as mutexes. A transaction might acquire a
read or write lock on a row prior to examining or updating it. These
locks are typically held for the duration of the transaction to
prevent other transactions from seeing uncommitted data, thus
achieving the illusion of atomicity. But, once a transaction has a
write lock, it doesn't need another one later to read or write the
same row. Or if it already has a read lock and wants to write, it
must upgrade to a write lock.

I can see how you would think this implies re-entrant locks, since the
same transaction seemingly needs to acquire that lock twice. But
either that transaction already knows what locks it has (how else
would it release them all on commit), or the lock manager is keeping
track for us.

None of these issues are unique to Go. The only thing that requires
coordination here is the lock manager state, and channels seem like a
good fit there. Communicating lock requests via a channel ensures
that you can process lock requests serially without need for mutexes.
You'll probably also want to include a response channel with each lock
request, to send the response when the lock is acquired, or an error
in the case of deadlock. The lock manager will have to maintain the
wait queues explicitly anyway to do deadlock detection.

-Dan

both of these are easily implemented with channels.

here's an alternative implementation of a simple mutex,
which uses a channel with a buffer size of 1:

type Mutex chan bool
func NewMutex() Mutex { return make(chan bool, 1) }
func (m Mutex) Lock() { m <- false }
func (m Mutex) Unlock() { <-m }

given this, TryLock is simple:

func (m Mutex) TryLock() bool { return m <- false }

and here's a lock with a timeout (assuming import "time"):

func (m Mutex) LockWithTimeout(t int64) (locked bool) {
tick := time.NewTicker(t)
select {
case m <- false:
locked = true
case <-tick.C:
break
}
tick.Stop()
return
}

sync.Mutex is useful because it's considerably more
efficient than using a channel, but in many circumstances,
the above code will run acceptably fast.

sync.Mutex is also nice because it requires no allocation and
no initialization, unlike the channel-based mutex.

BTW i just did some timing tests.
on my machine, given:

var sm sync.Mutex
m := NewMutex()

{sm.Lock(); sm.Unlock()} takes 0.054us
{m.Lock(); m.Unlock()} takes 0.172us
{m.Trylock(); m.Unlock()} takes 0.176us
m.Trylock() on a locked channel takes 0.082us
m.LockWithTimeout(1) on a locked channel takes 32.40us

so sync.Mutex is about 3 times faster than using
a channel, which isn't so bad, considering.

the outlier is LockWithTimeout, which is about 200 times slower
than Lock (or 600 times slower than sync.Mutex.Lock).
most timings are more-or-less unchanged with GOMAXPROCS>1,
but LockWithTimeout goes up to 82.27us, 1500 times slower than
sync.Mutex.Lock.

i wonder if there's room for a lighter-weight timer mechanism
within go, perhaps as part of the language itself?

i can easily envisage a scenario where one
goroutine hands a locked data structure off to another
goroutine that does some more work and finally unlocks it.

why should this be disallowed?

Sent from my BlackBerry smartphone from Virgin Media

go has a different approach to concurrency - mutexes are
barely needed at all - if you find yourself using them a lot,
you're probably doing something wrong.

your original lockmgr package seemed very un-go-like to me.
it seems to me that the java program you're porting
could do with some restructuring to make better use
of the facilities that go provides, rather than trying to
use java-style concurrency in go.

one implication is that you can't do recursive mutexes,
because it's perfectly legitimate for a process to try
to lock a mutex that it itself locked and has not yet been
unlocked (it should block until it is unlocked).

yes, but they are invariably guarding a simple piece
of shared state. i don't know of any places where
two locks are acquired at once.

please do.

You then wouldn't need the global mutex, as the goroutine that owns
the hash table can ensure that nothing is accessing it while it
resizes or otherwise modifies it.

I'm pretty sure that you could replace a lot of the current use of
mutexes with channels and a for/select loop. The code would get a lot
simpler too.

Apologies if I've missed some subtleties of your program, I've only
looked at it quite briefly.

Andrew

What I'm suggesting is nowhere near a complete rewrite. Most of the
code you already have will remain intact. I'm suggesting this because
I think it will make your code simpler and thus easier to understand
and maintain. It will also allow you to see first-hand the benefits of
some of Go's core features.

This thread is titled "Experiments in Go," therefore I am suggesting
you conduct an experiment. :-)

Andrew

The third option is that people learn to write Go code in Go instead
of writing Java code in Go. By not having certain features that other
languages have programmers coming from other languages are forced to
actually think about their programs in a Go way instead of just
writing the same thing they'd write in another language.
There is pretty much no point in rewriting a Java programming in Go if
you don't use Go idioms.

From a brief look at the code you linked to,(a bit of constructive criticism)
1. You have a linked list implementation in there to implement a
queue, you could use the linked list that is part of the standard lib
and use the "range" keyword in your for loop so you don't have to do
this "for link := item.queue.GetHead(); link != nil; link =
link.Next() {"
2. In that whole program you haven't used a single channel or a
goroutine, which is kind of weird for >1000 lines of Go. A program
like this with lots of complex locking stuff seems like it could
really show off Go's concurrency features, but this just reads like a
Java program with slightly different syntax.
3. I also suggest that you break this code up in to a number of packages.

If you read some of the standard library packages or some of the
programs at http://go-lang.cat-v.org you might get a better idea of
some of the more common Go idioms.

- jessta
--
=====================
http://jessta.id.au

to show what i mean, i've attached a toy version of your code
that uses a goroutine per contended lock, which means that
for the presumably common case of an uncontended lock
that there's no need to interact with a central goroutine.

it relies heavily on the fact that when doing a select,
nil channels are ignored. the locker() process makes
sure that it will only accept channel operations on
those channels that correspond to acceptable operations.
other operations will delay until they
are acceptable.

i don't know if it's possible to do everything you need in terms
of this kind of structure, but i thought you might find it an interesting
illustration of a possible approach regardless.

i've barely tested it.

those numbers would be correct (well, almost correct - the freec is
shared between all locks) if all locks are contended.

if a lock is uncontended, then it uses only one allocation (the lock header),
as mutexes do not require any allocation.

so if 1% of the channels are contended, then my code will use 100 goroutines,
700 channels and 10000 mutexes. oh yes, current implementation detail:
once a lock is contended, its goroutine never goes away. the freeLocker
channel (currently unused) can be used to garbage collect
locker processes.

so the number of resources consumed would depend very much on the
actual scenario.

having fixed things so that Release works, an equivalent test to yours
gives the following timing, which isn't too much different. it might be slower,
but it's perhaps more versatile, as it could easily be adapted to use timeouts,
for example. note that it does test the worst case scenario - a continually
contended lock.

0.21 real 0.17 user 0.13 sys

i attach my code. i was a bit cheeky and rearranged the API somewhat according
to my whims and to allow reentrant locks. this may or may not fit with how
you envisage using it :-). my code also doesn't implement upgrading/degrading,
which may or may not require a complete rewrite of Lock...

as i said before, this code is a toy - i thought it was perhaps a neat way
to solve (some of) this interesting problem, not that it's necessarily
the most efficient
way.

finally, i think it's fair to say that the problem is something of a
special case, being specifically
to do with locks - most problems are not like this.

FWIW that's not my contention. But you shouldn't be surprised at such
a reaction to someone porting a mutex-heavy program from Java to Go
without even _trying_ Go's concurrency features. :-)

Andrew

it was a fun problem to have a look at.
if one has something that one thinks might be a universal
solvent, it's always interesting to see whether and how it dissolves
a new material :-)

actually, in the last version i sent you, locks are owned
(see the LockOwner type), and thus can be reentrant.

i wasn't sure how reentrancy should work if the
the same process tries to change the lock mode though.

no, it won't. several requests at the same locking level
will queue, but requests at different levels will
be received by "fair sharing" i.e. randomly.

as for your performance issue, it's just possible
that you're triggering an issue that i discovered quite
a while ago,

http://groups.google.com/group/golang-nuts/browse_thread/thread/ea7ca41edeee5c7b/43f8766ab1c09272

i did actually look into this and found that it
was a scheduling issue where two processes would
get into lock-step and end up triggering the garbage collection
every time a process was scheduled.

as for your implementation, i think realistically, my approach
probably isn't viable, although technically interesting, as
you won't have enough control over the locking semantics
(e.g. fairness). i think i'd probably go for a similarly hybrid
approach but have the locker process receive on a single
channel and send replies to unlock clients when needed.
it would need to manually manage the queues, as your
current implementation does.