Re: [go-nuts] Re: mutual exclusion algorithm of Dijkstra - strange behaviour
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. On Saturday, August 17, 2019 at 12:24:58 AM UTC-4, xkw...@connect.hku.hk wrote: > > 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: >> >> 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+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/a735e0bb-f2a6-4dcc-a041-48357569f379%40googlegroups.com.
Re: [go-nuts] Re: mutual exclusion algorithm of Dijkstra - strange behaviour
On Fri, Aug 16, 2019 at 8:09 PM 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. -- 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. To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CAGrdgiWxuMh68ugdrb0n8rCj8Ai46NBfa8bxktJtjCCbCHeTxA%40mail.gmail.com.
Re: [go-nuts] Re: mutual exclusion algorithm of Dijkstra - strange behaviour
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. > On Aug 16, 2019, at 11:29 PM, Ian Lance Taylor wrote: > >> On Fri, Aug 16, 2019 at 9:24 PM 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+unsubscr...@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. > > -- > 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. > To view this discussion on the web visit > https://groups.google.com/d/msgid/golang-nuts/CAOyqgcUszubiss809%2B4Q9U6NB9wV-SM7tnDmH5as4%2BYswbFvHA%40mail.gmail.com. -- 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. To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/62CB4B9C-6B1B-4AB2-A884-B0641DB5A947%40ix.netcom.com.
Re: [go-nuts] Re: mutual exclusion algorithm of Dijkstra - strange behaviour
On Fri, Aug 16, 2019 at 9:24 PM 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+unsubscr...@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. -- 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. To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CAOyqgcUszubiss809%2B4Q9U6NB9wV-SM7tnDmH5as4%2BYswbFvHA%40mail.gmail.com.
Re: [go-nuts] Re: mutual exclusion algorithm of Dijkstra - strange behaviour
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: > > 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+unsubscr...@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.
Re: [go-nuts] Re: mutual exclusion algorithm of Dijkstra - strange behaviour
On Fri, 16 Aug 2019, at 7:09 PM, dr.ch.mau...@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+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/1d53eed0-2702-450c-a3bd-50473c98b862%40www.fastmail.com.
Re: [go-nuts] Re: mutual exclusion algorithm of Dijkstra - strange behaviour
On Fri, Aug 16, 2019 at 8:09 PM 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. -- 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. To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CAA40n-XQpGu%2BUt4hABbt7Hn%2BNt02s%2B_tbBjEZDrSQmzEV8gW5w%40mail.gmail.com.
Re: [go-nuts] Re: mutual exclusion algorithm of Dijkstra - strange behaviour
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.
> On Aug 16, 2019, at 1:09 PM, dr.ch.mau...@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 !
>
> (See my book on https://maurer-berlin.eu/nspbuch - in it's 4th edition things
> are mentioned.)
>
> With kind regards,
> Christian Maurer
>
> Am Montag, 30. Oktober 2017 18:30:06 UTC+1 schrieb Christian 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.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/golang-nuts/f83856a2-0661-4425-9861-196b83fcf07f%40googlegroups.com.
--
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.
To view this discussion on the web visit
https://groups.google.com/d/msgid/golang-nuts/2678AD8A-6D96-4D46-B977-7A78A2CFC12B%40ix.netcom.com.
[go-nuts] Re: mutual exclusion algorithm of Dijkstra - strange behaviour
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
Am Montag, 30. Oktober 2017 18:30:06 UTC+1 schrieb Christian 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.
To view this discussion on the web visit
https://groups.google.com/d/msgid/golang-nuts/f83856a2-0661-4425-9861-196b83fcf07f%40googlegroups.com.
