I have modified a little the code on RosettaCode (no changes in
the logic).
monarch_dodra:
Avoids deadlock.
imagine 2 threads:
a: from 2 to 5.
b: from 5 to 2.
If both threads acquire their first lock, then you have a dead
lock, and your program is basically dead.
By always locking low first, you avoid the deadlock in a rather
simple but elegant way.
The Go language has four different solutions, one of them is:
http://rosettacode.org/wiki/Atomic_updates#Lock-free
From the site:
This version uses no locking for the phase where the
two clients are updating the buckets. Instead it
watches for collisions and retries as needed.
func (bl *lfList) transfer(b1, b2, a int, ux int) {
if b1 == b2 {
return
}
bl.RLock()
for {
t := int32(a)
v1 := atomic.LoadInt32(&bl.b[b1])
if t > v1 {
t = v1
}
if atomic.CompareAndSwapInt32(&bl.b[b1], v1, v1-t) {
atomic.AddInt32(&bl.b[b2], t)
break
}
// else retry
}
bl.tc[ux]++
bl.RUnlock()
runtime.Gosched()
}
Bye,
bearophile
