How to understand the "Incorrect synchronization" samples in Go Memory Model

Question

I am just starting learning golang, when reading Go Memory Model I got a question to understand what it says about "Another incorrect idiom is busy waiting for a value,"

var a string
var done bool
func setup() {
    a = "hello, world"
    done = true
}
func main() {
    go setup()
    for !done {
    }
    print(a)
}

It says:

"Worse, there is no guarantee that the write to done will ever be observed by main, since there are no synchronization events between the two threads. The loop in main is not guaranteed to finish."

I know that the order of writes to 'a' and 'done' is not deterministic in setup(), My question is: why main is not guaranteed to see the write to done?

Thank you

peterSO · Accepted Answer · 2017-05-08T12:21:37.263

5

package main

var a string

var done bool

func setup() {
    a = "hello, world"
    done = true
}
func main() {
    go setup()
    for !done {
    }
    println(a)
}

You have two goroutines, main and setup. For example, assume that they are running on separate threads on separate CPUs with local memory cache. Assume that both main and setup read the done variable into a local CPU memory cache. The setup goroutine updates done in its local memory cache, which does lazy writes. Since there is no cache synchronization event between the independent main and setup goroutines there is no guarantee of cache coherency, no guarantee that main memory and both CPU memory caches will be synchronized. Different hardware handles this differently. In Go, only the lowest common denominator can be guaranteed.

See Cache coherence.

edited May 08 '17 at 12:21

answered May 08 '17 at 11:41

peterSO

158,998
31
281
276

1

Further, if you're running this on a single thread, the main routine, since it has an infinite loop with no function calls or anything else that would cause a goroutine scheduling to occur, could consume 100% of the run time without ever allowing `setup()` to proceed. That's why channels are the general solution for communicating between goroutines. The common axiom in Go is: "Don't communicate by sharing memory, share memory by communicating". – Kaedys May 08 '17 at 16:30
@Kaedys: The question says we are running on two threads: "there are no synchronization events between the two threads." – peterSO May 08 '17 at 16:42
1

The question itself does not indicate how many OS threads the OP is running, just the quote from the article linked. The problem OP highlighted ("busy waiting on a value") occurs far more often out here due to the main routine consuming 100% run time than it does due to cache coherence. In any case, _both_ are worth highlighting, as either one can cause an issue in this case depending on the architecture being run on. – Kaedys May 08 '17 at 17:01
@kaedys,@peterSO,Thank you for clear explanation, CPU cache coherence and no-func goroutine can't get schedule are new to me, seems there are lots of knowledge to be learnt. – flyingpine May 09 '17 at 02:11
On the goroutine side, the important thing to remember is to have some sort of pause in a goroutine. Reading from/writing to an unbuffered channel, writing out to disk or console/log or something, entering a function, all of these actions can cause the scheduler to yield to another goroutine. If you just have an infinite loop, however, that goroutine never yields, and the others don't get a chance to run unless you have multiple OS threads available. That's why channels are so nice for communicating between goroutines. – Kaedys May 09 '17 at 14:21
For example, your original code re-implemented using channels for communication: https://play.golang.org/p/E5qq8X2j2S – Kaedys May 09 '17 at 14:24
Modern CPUs have coherent caches. That it taken care of by the cache coherence protocol like MESI. In simple terms; before a write can be made to a cache line, the cacheline needs to invalidated on all other CPUs before the write can be made. This will guarantee that other CPUs are going to see this write. – pveentjer Aug 30 '22 at 08:26

pveentjer · Answer 2 · 2023-06-08T14:31:09.090

The go memory model is an axiomatic memory model and is defined in terms of a happens-before relation.

So if A happens-before B, then B should see A and everything before A.

In Golang all actions in a single Goroutine create such happens-before edges due to the sequence-before rule. So a Goroutine should always be able to see its own changes.

But if you share state between different Goroutines, things can become problematic if there is no happens-before edge.

2 Memory actions to a shared location are conflicting when at least one of them is a write. When you have 2 conflicting memory actions that are concurrent, so there is no happens-before edge between them, then you have a data race.

And as soon as you have a data race, weird problems can happen. So typically atomicity, visibility, and reordering problems.

In your example, there is a data race on 'a' and 'done'.

func setup() {
    a = "hello, world" (1)
    done = true (2)
}
func main() {
    go setup()
    for !done { (3)
    }
    println(a) (4)
}

The 2 stores in the setup function could be reordered for example. To fix this problem you would need to update 'done' using an atomic.

In that case, you have a happens-before edge between (1) and (2) due to sequenced-before. And also between (3) and (4). And between (2) and (3) there is a happens-before edge due to synchronized-before. Since happens-before is transitive, there is a happens-before edge between (1) and (4). And therefore you get the guarantee, that when you read 'done=true', you will see 'a=hello world'.

Looking at [this](https://stackoverflow.com/questions/33274920/incorrect-synchronization-in-go-lang) question on SO, which asks a similar question from the same article, your last statement would be false. It quotes `compilers and processors may reorder the reads and writes executed within a single goroutine only when the reordering does not change the behavior within that goroutine as defined by the language specification.` therefore allowing the compiler to reorder (1) and (2). If you meant that it is meant with the use of atomic, it would be good to show it in the example. — Marko, Jun 08 '23 at 14:02
@Marko. Yes; there is only a happens-before edge when 'done' is an atomic. Let me make a small modification to my answer to make that clearer. — pveentjer, Jun 08 '23 at 14:30

How to understand the "Incorrect synchronization" samples in Go Memory Model

2 Answers2