Re: [go-nuts] mutual exclusion algorithm of Dijkstra - strange behaviour

[Jan Mercl]

On Mon, Oct 30, 2017 at 6:29 PM  wrote:

> I noticed a very strange effect by translating the
> mutual exclusion algorithm of E. W. Dijkstra to Go.

For every combination of lines A/B present/not present, the program has
data races, so there's nothing to reason about.

You can try it by yourself by issuing $ go run -race main.go

-- 

-j

-- 
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.

Re: [go-nuts] mutual exclusion algorithm of Dijkstra - strange behaviour

[Henrik Johansson]

I think it's the non-preemptive scheduler that hits you.
Afaik it is a known behavior that I am not sure how to fix.
I did not at all look at the solution itself.

mån 30 okt. 2017 kl 18:29 skrev :

> 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.
>

-- 
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.

[go-nuts] mutual exclusion algorithm of Dijkstra - strange behaviour

[dr . ch . maurer]

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