mutual exclusion algorithm of Dijkstra - strange behaviour

[dr.ch....@gmail.com]

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

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

--
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/d/optout.

[Jan Mercl]

On Mon, Oct 30, 2017 at 6:29 PM <dr.ch....@gmail.com> 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

[dr.ch....@gmail.com]

Dear Community and dear Go-developers,

Meanwhile it is clear why things do not work:

The Go-Scheduler is unable to allow to switch to another goroutine in busy-waiting-loops -

the only possibility to get around that problem is either to put "switch-steps" into the source

- either "time.Sleep(1)" or "runtime.Gosched()".

I think that THIS SHOULD BE DOCUMENTED IN THE LANGUAGE SPECIFICATION !!!!!

(See my book on https://maurer-berlin.eu/nspbuch - in it's 4th edition things are mentioned.)

With kind regards,

Christian Maurer

[Robert Engels]

Your code is incorrect for Go. You need to use correct concurrent code. It is documented that tight loops that do not involve function calls may not allow GC to occur. 

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

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/f83856a2-0661-4425-9861-196b83fcf07f%40googlegroups.com.

[Jan Mercl]

On Fri, Aug 16, 2019 at 8:09 PM <dr.ch....@gmail.com> wrote:

> Meanwhile it is clear why things do not work:
> The Go-Scheduler is unable to allow to switch to another goroutine in busy-waiting-loops -
> the only possibility to get around that problem is either to put "switch-steps" into the source
> - either "time.Sleep(1)" or "runtime.Gosched()".
> I think that THIS SHOULD BE DOCUMENTED IN THE LANGUAGE SPECIFICATION !!!!!
>
> (See my book on https://maurer-berlin.eu/nspbuch - in it's 4th edition things are mentioned.)

That conclusion is not correct and you should correct your book. The
code in the OP is racy. You cannot say anything meaningful about the
behavior of a racy Go program - it is undefined.

[Ian Davis]

On Fri, 16 Aug 2019, at 7:09 PM, dr.ch....@gmail.com wrote:

Dear Community and dear Go-developers,

Meanwhile it is clear why things do not work:

The Go-Scheduler is unable to allow to switch to another goroutine in busy-waiting-loops -

the only possibility to get around that problem is either to put "switch-steps" into the source

- either "time.Sleep(1)" or "runtime.Gosched()".

I think that THIS SHOULD BE DOCUMENTED IN THE LANGUAGE SPECIFICATION !!!!!

I don't believe this is a language issue. Different compiler implementations could support pre-emption if they chose to.

Ian

[xkw...@connect.hku.hk]

Could you let me know which compiler can support pre-emption and how to enable it? Thanks.

On Saturday, August 17, 2019 at 9:20:07 AM UTC+8, Ian Davis wrote:

[Ian Lance Taylor]

On Fri, Aug 16, 2019 at 9:24 PM <xkw...@connect.hku.hk> wrote:
>
> Could you let me know which compiler can support pre-emption and how to enable it? Thanks.

No current Go toolchain supports preemption in all cases; for the gc
toolchain, that is https://golang.org/issue/10958. But the exact
definition of a busy loop is compiler dependent.

Ian

> On Saturday, August 17, 2019 at 9:20:07 AM UTC+8, Ian Davis wrote:
>>
>> On Fri, 16 Aug 2019, at 7:09 PM, dr.ch...@gmail.com wrote:
>>
>> Dear Community and dear Go-developers,
>>
>> Meanwhile it is clear why things do not work:
>> The Go-Scheduler is unable to allow to switch to another goroutine in busy-waiting-loops -
>> the only possibility to get around that problem is either to put "switch-steps" into the source
>> - either "time.Sleep(1)" or "runtime.Gosched()".
>> I think that THIS SHOULD BE DOCUMENTED IN THE LANGUAGE SPECIFICATION !!!!!
>>
>>
>> I don't believe this is a language issue. Different compiler implementations could support pre-emption if they chose to.
>>
>> Ian
>>

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

> To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/2399f893-7030-476f-956c-b3f9d6565f67%40googlegroups.com.

[Robert Engels]

But as was pointed out, in this case it does not matter as the code is sharing memory without proper synchronization so preemption doesn’t really matter.

> To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CAOyqgcUszubiss809%2B4Q9U6NB9wV-SM7tnDmH5as4%2BYswbFvHA%40mail.gmail.com.

[Jesper Louis Andersen]

On Fri, Aug 16, 2019 at 8:09 PM <dr.ch....@gmail.com> wrote:

The Go-Scheduler is unable to allow to switch to another goroutine in busy-waiting-loops -

the only possibility to get around that problem is either to put "switch-steps" into the source

- either "time.Sleep(1)" or "runtime.Gosched()".

I think that THIS SHOULD BE DOCUMENTED IN THE LANGUAGE SPECIFICATION !!!!!

Usually, you want implementation specific quirks to be part of a description of the implementation, not of the language specification. The reason for this being that it allows a certain amount of leeway in implementations to improve. The typical exceptions to this case is when an implementation detail is so important that the language will not function properly without. A good example are the Scheme specifications (r7rs.org) in which any implementation must implement proper tail-call optimization. But r7rs leaves the execution order of parameters in function calls unspecified. The latter somewhat breaks semantics in the presence of side effects, but it allows implementations to choose the order in which they want to evaluate parameters.

The key here is a trade-off between efficiency and concurrency. Adding checks to tight loops are bound to make that loop slower in some way, or impose a considerable complexity into the language runtime. Most programs caring about concurrency are unlikely to ever hit the problem, provided they synchronize properly, because the synchronization is a possible rendezvous point. If we add forced preemption into the language specification, we prohibit language implementations to make this trade-off.

You might then argue this is bad design anyway, to which I respond: "Have you ever seen Javascript, Python or C++?"

-- 

J.

[David Chase]

If you want preemption within a particular package, you can compile it "go build -gcflags=particular_package=-d=ssa/insert_resched_checks/on" .

That will not fix any problems with underlying raciness, though it may mask them.

If you want an entire compiler that defaults to that mode and libraries also built that way, "GOEXPERIMENT=preemptibleloops ./make.bash" .

This can slow code down quite a bit.

We're not super-excited about this approach, but a fix that doesn't trash performance is tricky (we've been working on it for a while).

When we do get it done right, the flags and the experiment are likely to go away.