← Back to branch summary

~john-koepi/ubuntu/trusty/golang/default

« back to all changes in this revision

Viewing changes to doc/go_mem.html

  • Committer: Bazaar Package Importer
  • Author(s): Ondřej Surý
  • Date: 2011-04-20 17:36:48 UTC
  • Revision ID: james.westby@ubuntu.com-20110420173648-ifergoxyrm832trd
Tags: upstream-2011.03.07.1
Import upstream version 2011.03.07.1

Show diffs side-by-side

added added

removed removed

Lines of Context:
doc/go_mem.html
 
1
<!-- The Go Memory Model -->
 
2
 
 
3
<h2>Introduction</h2>
 
4
 
 
5
<p>
 
6
The Go memory model specifies the conditions under which
 
7
reads of a variable in one goroutine can be guaranteed to
 
8
observe values produced by writes to the same variable in a different goroutine.
 
9
</p>
 
10
 
 
11
<h2>Happens Before</h2>
 
12
 
 
13
<p>
 
14
Within a single goroutine, reads and writes must behave
 
15
as if they executed in the order specified by the program.
 
16
That is, compilers and processors may reorder the reads and writes
 
17
executed within a single goroutine only when the reordering
 
18
does not change the behavior within that goroutine
 
19
as defined by the language specification.
 
20
Because of this reordering, the execution order observed
 
21
by one goroutine may differ from the order perceived
 
22
by another.  For example, if one goroutine
 
23
executes <code>a = 1; b = 2;</code>, another might observe
 
24
the updated value of <code>b</code> before the updated value of <code>a</code>.
 
25
</p>
 
26
 
 
27
<p>
 
28
To specify the requirements of reads and writes, we define
 
29
<i>happens before</i>, a partial order on the execution
 
30
of memory operations in a Go program.  If event <span class="event">e<sub>1</sub></span> happens
 
31
before event <span class="event">e<sub>2</sub></span>, then we say that <span class="event">e<sub>2</sub></span> happens after <span class="event">e<sub>1</sub></span>.
 
32
Also, if <span class="event">e<sub>1</sub></span> does not happen before <span class="event">e<sub>2</sub></span> and does not happen
 
33
after <span class="event">e<sub>2</sub></span>, then we say that <span class="event">e<sub>1</sub></span> and <span class="event">e<sub>2</sub></span> happen concurrently.
 
34
</p>
 
35
 
 
36
<p>
 
37
Within a single goroutine, the happens before order is the
 
38
order expressed by the program.
 
39
</p>
 
40
 
 
41
<p>
 
42
A read <span class="event">r</span> of a variable <code>v</code> is <i>allowed</i> to observe a write <span class="event">w</span> to <code>v</code>
 
43
if both of the following hold:
 
44
</p>
 
45
 
 
46
<ol>
 
47
<li><span class="event">w</span> happens before <span class="event">r</span>.</li>
 
48
<li>There is no other write <span class="event">w'</span> to <code>v</code> that happens
 
49
    after <span class="event">w</span> but before <span class="event">r</span>.</li>
 
50
</ol>
 
51
 
 
52
<p>
 
53
To guarantee that a read <span class="event">r</span> of a variable <code>v</code> observes a
 
54
particular write <span class="event">w</span> to <code>v</code>, ensure that <span class="event">w</span> is the only
 
55
write <span class="event">r</span> is allowed to observe.
 
56
That is, <span class="event">r</span> is <i>guaranteed</i> to observe <span class="event">w</span> if both of the following hold:
 
57
</p>
 
58
 
 
59
<ol>
 
60
<li><span class="event">w</span> happens before <span class="event">r</span>.</li>
 
61
<li>Any other write to the shared variable <code>v</code>
 
62
either happens before <span class="event">w</span> or after <span class="event">r</span>.</li>
 
63
</ol>
 
64
 
 
65
<p>
 
66
This pair of conditions is stronger than the first pair;
 
67
it requires that there are no other writes happening
 
68
concurrently with <span class="event">w</span> or <span class="event">r</span>.
 
69
</p>
 
70
 
 
71
<p>
 
72
Within a single goroutine,
 
73
there is no concurrency, so the two definitions are equivalent:
 
74
a read <span class="event">r</span> observes the value written by the most recent write <span class="event">w</span> to <code>v</code>.
 
75
When multiple goroutines access a shared variable <code>v</code>,
 
76
they must use synchronization events to establish
 
77
happens-before conditions that ensure reads observe the
 
78
desired writes.
 
79
</p>
 
80
 
 
81
<p>
 
82
The initialization of variable <code>v</code> with the zero value
 
83
for <code>v</code>'s type behaves as a write in the memory model.
 
84
</p>
 
85
 
 
86
<p>
 
87
Reads and writes of values larger than a single machine word
 
88
behave as multiple machine-word-sized operations in an
 
89
unspecified order.
 
90
</p>
 
91
 
 
92
<h2>Synchronization</h2>
 
93
 
 
94
<h3>Initialization</h3>
 
95
 
 
96
<p>
 
97
Program initialization runs in a single goroutine and
 
98
new goroutines created during initialization do not
 
99
start running until initialization ends.
 
100
</p>
 
101
 
 
102
<p class="rule">
 
103
If a package <code>p</code> imports package <code>q</code>, the completion of
 
104
<code>q</code>'s <code>init</code> functions happens before the start of any of <code>p</code>'s.
 
105
</p>
 
106
 
 
107
<p class="rule">
 
108
The start of the function <code>main.main</code> happens after
 
109
all <code>init</code> functions have finished.
 
110
</p>
 
111
 
 
112
<p class="rule">
 
113
The execution of any goroutines created during <code>init</code>
 
114
functions happens after all <code>init</code> functions have finished.
 
115
</p>
 
116
 
 
117
<h3>Goroutine creation</h3>
 
118
 
 
119
<p class="rule">
 
120
The <code>go</code> statement that starts a new goroutine
 
121
happens before the goroutine's execution begins.
 
122
</p>
 
123
 
 
124
<p>
 
125
For example, in this program:
 
126
</p>
 
127
 
 
128
<pre>
 
129
var a string
 
130
 
 
131
func f() {
 
132
        print(a)
 
133
}
 
134
 
 
135
func hello() {
 
136
        a = "hello, world"
 
137
        go f()
 
138
}
 
139
</pre>
 
140
 
 
141
<p>
 
142
calling <code>hello</code> will print <code>"hello, world"</code>
 
143
at some point in the future (perhaps after <code>hello</code> has returned).
 
144
</p>
 
145
 
 
146
<h3>Goroutine destruction</h3>
 
147
 
 
148
<p>
 
149
The exit of a goroutine is not guaranteed to happen before
 
150
any event in the program.  For example, in this program:
 
151
</p>
 
152
 
 
153
<pre>
 
154
var a string
 
155
 
 
156
func hello() {
 
157
        go func() { a = "hello" }()
 
158
        print(a)
 
159
}
 
160
</pre>
 
161
 
 
162
<p>
 
163
the assignment to <code>a</code> is not followed by
 
164
any synchronization event, so it is not guaranteed to be
 
165
observed by any other goroutine.
 
166
In fact, an aggressive compiler might delete the entire <code>go</code> statement.
 
167
</p>
 
168
 
 
169
<p>
 
170
If the effects of a goroutine must be observed by another goroutine,
 
171
use a synchronization mechanism such as a lock or channel
 
172
communication to establish a relative ordering.
 
173
</p>
 
174
 
 
175
<h3>Channel communication</h3>
 
176
 
 
177
<p>
 
178
Channel communication is the main method of synchronization
 
179
between goroutines.  Each send on a particular channel
 
180
is matched to a corresponding receive from that channel,
 
181
usually in a different goroutine.
 
182
</p>
 
183
 
 
184
<p class="rule">
 
185
A send on a channel happens before the corresponding
 
186
receive from that channel completes.
 
187
</p>
 
188
 
 
189
<p>
 
190
This program:
 
191
</p>
 
192
 
 
193
<pre>
 
194
var c = make(chan int, 10)
 
195
var a string
 
196
 
 
197
func f() {
 
198
        a = "hello, world"
 
199
        c &lt;- 0
 
200
}
 
201
 
 
202
func main() {
 
203
        go f()
 
204
        &lt;-c
 
205
        print(a)
 
206
}
 
207
</pre>
 
208
 
 
209
<p>
 
210
is guaranteed to print <code>"hello, world"</code>.  The write to <code>a</code>
 
211
happens before the send on <code>c</code>, which happens before
 
212
the corresponding receive on <code>c</code> completes, which happens before
 
213
the <code>print</code>.
 
214
</p>
 
215
 
 
216
<p class="rule">
 
217
A receive from an unbuffered channel happens before
 
218
the send on that channel completes.
 
219
</p>
 
220
 
 
221
<p>
 
222
This program (as above, but with the send and receive statements swapped and
 
223
using an unbuffered channel):
 
224
</p>
 
225
 
 
226
<pre>
 
227
var c = make(chan int)
 
228
var a string
 
229
 
 
230
func f() {
 
231
        a = "hello, world"
 
232
        &lt;-c
 
233
}
 
234
</pre>
 
235
 
 
236
<pre>
 
237
func main() {
 
238
        go f()
 
239
        c &lt;- 0
 
240
        print(a)
 
241
}
 
242
</pre>
 
243
 
 
244
<p>
 
245
is also guaranteed to print <code>"hello, world"</code>.  The write to <code>a</code>
 
246
happens before the receive on <code>c</code>, which happens before
 
247
the corresponding send on <code>c</code> completes, which happens
 
248
before the <code>print</code>.
 
249
</p>
 
250
 
 
251
<p>
 
252
If the channel were buffered (e.g., <code>c = make(chan int, 1)</code>)
 
253
then the program would not be guaranteed to print
 
254
<code>"hello, world"</code>.  (It might print the empty string;
 
255
it cannot print <code>"goodbye, universe"</code>, nor can it crash.)
 
256
</p>
 
257
 
 
258
<h3>Locks</h3>
 
259
 
 
260
<p>
 
261
The <code>sync</code> package implements two lock data types,
 
262
<code>sync.Mutex</code> and <code>sync.RWMutex</code>.
 
263
</p>
 
264
 
 
265
<p class="rule">
 
266
For any <code>sync.Mutex</code> or <code>sync.RWMutex</code> variable <code>l</code> and <i>n</i> &lt; <i>m</i>,
 
267
the <i>n</i>'th call to <code>l.Unlock()</code> happens before the <i>m</i>'th call to <code>l.Lock()</code> returns.
 
268
</p>
 
269
 
 
270
<p>
 
271
This program:
 
272
</p>
 
273
 
 
274
<pre>
 
275
var l sync.Mutex
 
276
var a string
 
277
 
 
278
func f() {
 
279
        a = "hello, world"
 
280
        l.Unlock()
 
281
}
 
282
 
 
283
func main() {
 
284
        l.Lock()
 
285
        go f()
 
286
        l.Lock()
 
287
        print(a)
 
288
}
 
289
</pre>
 
290
 
 
291
<p>
 
292
is guaranteed to print <code>"hello, world"</code>.
 
293
The first call to <code>l.Unlock()</code> (in <code>f</code>) happens
 
294
before the second call to <code>l.Lock()</code> (in <code>main</code>) returns,
 
295
which happens before the <code>print</code>.
 
296
</p>
 
297
 
 
298
<p class="rule">
 
299
For any call to <code>l.RLock</code> on a <code>sync.RWMutex</code> variable <code>l</code>,
 
300
there is an <i>n</i> such that the <code>l.RLock</code> happens (returns) after the <i>n</i>'th call to
 
301
<code>l.Unlock</code> and the matching <code>l.RUnlock</code> happens
 
302
before the <i>n</i>+1'th call to <code>l.Lock</code>.
 
303
</p>
 
304
 
 
305
<h3>Once</h3>
 
306
 
 
307
<p>
 
308
The <code>sync</code> package provides a safe mechanism for
 
309
initialization in the presence of multiple goroutines
 
310
through the use of the <code>Once</code> type.
 
311
Multiple threads can execute <code>once.Do(f)</code> for a particular <code>f</code>,
 
312
but only one will run <code>f()</code>, and the other calls block
 
313
until <code>f()</code> has returned.
 
314
</p>
 
315
 
 
316
<p class="rule">
 
317
A single call of <code>f()</code> from <code>once.Do(f)</code> happens (returns) before any call of <code>once.Do(f)</code> returns.
 
318
</p>
 
319
 
 
320
<p>
 
321
In this program:
 
322
</p>
 
323
 
 
324
<pre>
 
325
var a string
 
326
var once sync.Once
 
327
 
 
328
func setup() {
 
329
        a = "hello, world"
 
330
}
 
331
 
 
332
func doprint() {
 
333
        once.Do(setup)
 
334
        print(a)
 
335
}
 
336
 
 
337
func twoprint() {
 
338
        go doprint()
 
339
        go doprint()
 
340
}
 
341
</pre>
 
342
 
 
343
<p>
 
344
calling <code>twoprint</code> causes <code>"hello, world"</code> to be printed twice.
 
345
The first call to <code>twoprint</code> runs <code>setup</code> once.
 
346
</p>
 
347
 
 
348
<h2>Incorrect synchronization</h2>
 
349
 
 
350
<p>
 
351
Note that a read <span class="event">r</span> may observe the value written by a write <span class="event">w</span>
 
352
that happens concurrently with <span class="event">r</span>.
 
353
Even if this occurs, it does not imply that reads happening after <span class="event">r</span>
 
354
will observe writes that happened before <span class="event">w</span>.
 
355
</p>
 
356
 
 
357
<p>
 
358
In this program:
 
359
</p>
 
360
 
 
361
<pre>
 
362
var a, b int
 
363
 
 
364
func f() {
 
365
        a = 1
 
366
        b = 2
 
367
}
 
368
 
 
369
func g() {
 
370
        print(b)
 
371
        print(a)
 
372
}
 
373
 
 
374
func main() {
 
375
        go f()
 
376
        g()
 
377
}
 
378
</pre>
 
379
 
 
380
<p>
 
381
it can happen that <code>g</code> prints <code>2</code> and then <code>0</code>.
 
382
</p>
 
383
 
 
384
<p>
 
385
This fact invalidates a few common idioms.
 
386
</p>
 
387
 
 
388
<p>
 
389
Double-checked locking is an attempt to avoid the overhead of synchronization.
 
390
For example, the <code>twoprint</code> program might be
 
391
incorrectly written as:
 
392
</p>
 
393
 
 
394
<pre>
 
395
var a string
 
396
var done bool
 
397
 
 
398
func setup() {
 
399
        a = "hello, world"
 
400
        done = true
 
401
}
 
402
 
 
403
func doprint() {
 
404
        if !done {
 
405
                once.Do(setup)
 
406
        }
 
407
        print(a)
 
408
}
 
409
 
 
410
func twoprint() {
 
411
        go doprint()
 
412
        go doprint()
 
413
}
 
414
</pre>
 
415
 
 
416
<p>
 
417
but there is no guarantee that, in <code>doprint</code>, observing the write to <code>done</code>
 
418
implies observing the write to <code>a</code>.  This
 
419
version can (incorrectly) print an empty string
 
420
instead of <code>"hello, world"</code>.
 
421
</p>
 
422
 
 
423
<p>
 
424
Another incorrect idiom is busy waiting for a value, as in:
 
425
</p>
 
426
 
 
427
<pre>
 
428
var a string
 
429
var done bool
 
430
 
 
431
func setup() {
 
432
        a = "hello, world"
 
433
        done = true
 
434
}
 
435
 
 
436
func main() {
 
437
        go setup()
 
438
        for !done {
 
439
        }
 
440
        print(a)
 
441
}
 
442
</pre>
 
443
 
 
444
<p>
 
445
As before, there is no guarantee that, in <code>main</code>,
 
446
observing the write to <code>done</code>
 
447
implies observing the write to <code>a</code>, so this program could
 
448
print an empty string too.
 
449
Worse, there is no guarantee that the write to <code>done</code> will ever
 
450
be observed by <code>main</code>, since there are no synchronization
 
451
events between the two threads.  The loop in <code>main</code> is not
 
452
guaranteed to finish.
 
453
</p>
 
454
 
 
455
<p>
 
456
There are subtler variants on this theme, such as this program.
 
457
</p>
 
458
 
 
459
<pre>
 
460
type T struct {
 
461
        msg string
 
462
}
 
463
 
 
464
var g *T
 
465
 
 
466
func setup() {
 
467
        t := new(T)
 
468
        t.msg = "hello, world"
 
469
        g = t
 
470
}
 
471
 
 
472
func main() {
 
473
        go setup()
 
474
        for g == nil {
 
475
        }
 
476
        print(g.msg)
 
477
}
 
478
</pre>
 
479
 
 
480
<p>
 
481
Even if <code>main</code> observes <code>g != nil</code> and exits its loop,
 
482
there is no guarantee that it will observe the initialized
 
483
value for <code>g.msg</code>.
 
484
</p>
 
485
 
 
486
<p>
 
487
In all these examples, the solution is the same:
 
488
use explicit synchronization.
 
489
</p>