Dear Go-community, I noticed a very strange effect by translating the mutual exclusion algorithm of E. W. Dijkstra to Go. Reference: Cooperating Sequential Processes. Technical Report EWD-123, Technological University Eindhoven (1965) http://www.cs.utexas.edu/users/EWD/ewd01xx/EWD123.PDF)
Inserting or omitting code lines A and B resp.
changes the behaviour of this program very severely:
With line A and without line B:
mutual exclusion is not guaranteed,
with line B and without line A:
lock does not terminate and
with both lines:
the program works as it should.
--- 8< --------------------------------------------
package main
import (
"math/rand"
"time"
)
const N = 10 // number of goroutines involved
var (
turn int
b, c = make([]int, N+1), make([]int, N+1)
n = uint(0)
inCS = make([]bool, N+1)
s = make([]string, N+1)
done = make(chan int)
)
func chk(i int) {
for j := 1; j <= N; j++ {
if j != i && inCS[j] {
panic("oops")
}
}
}
func lock(i int) {
b[i] = 0
L:
if turn != i {
c[i] = 1
if b[turn] == 1 {
turn = i
goto L
}
}
time.Sleep(1) // A
c[i] = 0
time.Sleep(1) // B
for j := 1; j <= N; j++ {
if j != i && c[j] == 0 {
goto L
}
}
inCS[i] = true
chk(i)
}
func unlock(i int) {
inCS[i] = false
c[i], b[i] = 1, 1
// turn = 0 // does not matter
}
func v() {
time.Sleep(time.Duration(1e7 + rand.Int63n(1e7)))
}
func count(i int) {
for k := 0; k < 100; k++ {
lock(i)
accu := n
v()
accu++
v()
n = accu
v()
println(s[i], n)
unlock(i)
v()
}
done <- 0
}
func main() {
s[1] = ""
for i := 2; i <= N; i++ {
s[i] = s[i-1] + " "
}
for i := 1; i <= N; i++ {
go count(i)
}
for i := 1; i <= N; i++ {
<-done
}
}
--- >8 --------------------------------------------
The cause for the "freaking out" of the program without
those compulsory breaks (of only 1 ns) is absolutely unclear.
Any sort of help is welcome!
Kind regards to everybody,
Christian Maurer
--
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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
dijkstra.go
Description: Binary data
