1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
|
<html>
<head>
<meta http-equiv="Content-Language" content="en-us">
<meta http-equiv="Content-Type" content=
"text/html; charset=windows-1252">
<meta name="GENERATOR" content="Microsoft FrontPage 4.0">
<meta name="ProgId" content="FrontPage.Editor.Document">
<title>Boost.Threads Definitions</title>
</head>
<body bgcolor="#FFFFFF">
<table summary="header" border="0" cellpadding="7" cellspacing="0"
width="100%">
<tr>
<td valign="top" width="300">
<h3><img src="../../../c++boost.gif" alt="C++ Boost" width=
"277" height="86"></h3>
</td>
<td valign="top">
<h1 align="center">Boost.Threads</h1>
<h2 align="center">Definitions</h2>
</td>
</tr>
</table>
<h2>Introduction</h2>
<p>The definitions are given in terms of the <a href=
"bibliography.html#ISO-98">C++ Standard</a>. References to the standard
are in the form [1.2.3/4], which represents the section number, with
the paragraph number following the "/".</p>
<p>Because the definitions are written in something akin to
"standardese", they can be difficult to understand. The
intent isn't to confuse, but rather to clarify the additional
requirements Boost.Threads places on a C++ implementation as defined by
the C++ Standard.</p>
<h2>Definitions</h2>
<h3>Thread</h3>
<p>Thread is short for "thread of execution". A thread of
execution is an execution environment [1.9/7] within the execution
environment of a C++ program [1.9]. The main() function [3.6.1] of the
program is the initial function of the initial thread. A program in a
multi-threading environment always has an initial thread even if the
program explicitly creates no additional threads.</p>
<p>Unless otherwise specified, each thread shares all aspects of its
execution environment with other threads in the program. Shared aspects
of the execution environment include, but are not limited to, the
following:</p>
<ul>
<li>Static storage duration (static, extern) objects [3.7.1].</li>
</ul>
<ul>
<li>Dynamic storage duration (heap) objects [3.7.3]. Thus each
memory allocation will return a unique addresses, regardless of the
thread making the allocation request.</li>
</ul>
<ul>
<li>Automatic storage duration (stack) objects [3.7.2] accessed via
pointer or reference from another thread.</li>
</ul>
<ul>
<li>Resources provided by the operating system. For example,
files.</li>
</ul>
<ul>
<li>The program itself. In other words, each thread is executing
some function of the same program, not a totally different
program.</li>
</ul>
<p>Each thread has its own:</p>
<ul>
<li>Registers and current execution sequence (program counter)
[1.9/5].</li>
</ul>
<ul>
<li>Automatic storage duration (stack) objects [3.7.2].</li>
</ul>
<h3><a name="Thread-safe">Thread-safe</a></h3>
<p>A program is thread-safe if it has no <a href="#Race condition">race
conditions</a>, does not <a href="#Deadlock">deadlock</a>, and has no
<a href="#Priority failure">priority failures</a>.</p>
<p>Note that thread-safety does not necessarily imply efficiency, and
than while some thread-safety violations can be determined statically
at compile time, many thread-safety errors can only only be detected at
runtime.</p>
<h3>Thread <a name="State">State</a></h3>
<p>During the lifetime of a thread, it shall be in one of the following
states:</p>
<table summary="thread states" border="1" cellpadding="5">
<tr>
<td><b>State</b></td>
<td><b>Description</b></td>
</tr>
<tr>
<td>Ready</td>
<td>Ready to run, but waiting for a processor.</td>
</tr>
<tr>
<td>Running</td>
<td>Currently executing on a processor. Zero or more threads
may be running at any time, with a maximum equal to the number
of processors.</td>
</tr>
<tr>
<td>Blocked</td>
<td>Waiting for some resource other than a processor which is
not currently available, or for the completion of calls to
library functions [1.9/6]. The term "waiting" is
synonymous for "blocked"</td>
</tr>
<tr>
<td>Terminated</td>
<td>Finished execution but not yet detached or joined.</td>
</tr>
</table>
<p>Thread state transitions shall occur only as specified:</p>
<table summary="state transitions" border="1" cellpadding="5">
<tr>
<td><b>From</b></td>
<td><b>To</b></td>
<td><b>Cause</b></td>
</tr>
<tr>
<td>
<p align="left">[none]</p>
</td>
<td>Ready</td>
<td>Thread is created by a call to a library function. In the
case of the initial thread, creation is implicit and occurs
during the startup of the main() function [3.6.1].</td>
</tr>
<tr>
<td>Ready</td>
<td>Running</td>
<td>Processor becomes available.</td>
</tr>
<tr>
<td>Running</td>
<td>Ready</td>
<td>Thread preempted.</td>
</tr>
<tr>
<td>Running</td>
<td>Blocked</td>
<td>Thread calls a library function which waits for a resource
or for the completion of I/O.</td>
</tr>
<tr>
<td>Running</td>
<td>Terminated</td>
<td>Thread returns from its initial function, calls a thread
termination library function, or is cancelled by some other
thread calling a thread termination library function.</td>
</tr>
<tr>
<td>Blocked</td>
<td>Ready</td>
<td>The resource being waited for becomes available, or the
blocking library function completes.</td>
</tr>
<tr>
<td>Terminated</td>
<td>[none]</td>
<td>Thread is detached or joined by some other thread calling
the appropriate library function, or by program termination
[3.6.3].</td>
</tr>
</table>
<p>[Note: if a suspend() function is added to the threading library,
additional transitions to the blocked state will have to be added to
the above table.]</p>
<h3><a name="Race condition">Race condition</a></h3>
<p>A race condition is what occurs when multiple threads read and write
to the same memory without proper synchronization, resulting in an
incorrect value being read or written. The result of a race condition
may be a bit pattern which isn't even a valid value for the data
type. A race condition results in undefined behavior [1.3.12].</p>
<p>Race conditions can be prevented by serializing memory access using
the tools provided by Boost.Threads.</p>
<h3><a name="Deadlock">Deadlock</a></h3>
<p>Deadlock is an execution state where for some set of threads, each
thread in the set is blocked waiting for some action by one of the
other threads in the set. Since each is waiting on the others, none
will ever become ready again.</p>
<h3><a name="Priority failure">Priority failure</a></h3>
<p>A priority failure (such as priority inversion or infinite
overtaking) occurs when threads executed in such a sequence that
required work is not performed in time to be useful.</p>
<h2>Memory visibility between threads</h2>
<p>An address [1.7] shall always point to the same memory byte,
regardless of the thread or processor dereferencing the address.</p>
<p>An object [1.8, 1.9] is accessible from multiple threads if it is of
static storage duration (static, extern) [3.7.1], or if a pointer or
reference to it is explicitly or implicitly dereferenced in multiple
threads.</p>
<p>For an object accessible from multiple threads, the value of the
object accessed from one thread may be indeterminate or different than
the value accessed from another thread, except under the conditions
specified in the following table. For the same row of the table, the
value of an object accessible at the indicated sequence point in thread
A will be determinate and the same if accessed at or after the
indicated sequence point in thread B, provided the object is not
otherwise modified. In the table, the "sequence point at a
call" is the sequence point after the evaluation of all function
arguments [1.9/17], while the "sequence point after a call"
is the sequence point after the copying of the returned value..."
[1.9/17].</p>
<table summary="memory visibility" border="1" cellpadding="5">
<tr>
<td align="center"><b>Thread A</b></td>
<td align="center"><b>Thread B</b></td>
</tr>
<tr>
<td>The sequence point at a call to a library thread-creation
function.</td>
<td>The first sequence point of the initial function in the new
thread created by the Thread A call.</td>
</tr>
<tr>
<td>The sequence point at a call to a library function which
locks a mutex, directly or by waiting for a condition
variable.</td>
<td>The sequence point after a call to a library function which
unlocks the same mutex.</td>
</tr>
<tr>
<td>The last sequence point before thread termination.</td>
<td>The sequence point after a call to a library function which
joins the terminated thread.</td>
</tr>
<tr>
<td>The sequence point at a call to a library function which
signals or broadcasts a condition variable.</td>
<td>The sequence point after the call to the library function
which was waiting on that same condition variable or
signal.</td>
</tr>
</table>
<p>The architecture of the execution environment and the observable
behavior of the abstract machine [1.9] shall be the same on all
processors.</p>
<p>The latitude granted by the C++ standard for an implementation to
alter the definition of observable behavior of the abstract machine to
include additional library I/O functions [1.9/6] is extended to include
threading library functions.</p>
<p>When an exception is thrown and there is no matching exception
handler in the same thread, behavior is undefined. The preferred
behavior is the same as when there is no matching exception handler in
a program [15.3/9]. That is, terminate() is called, and it is
implementation defined whether or not the stack is unwound.</p>
<h2><a name="Acknowledgements">Acknowledgements</a></h2>
<p>This document has been much improved by the incorporation of
comments from William Kempf.</p>
<p>The visibility rules are based on <a href=
"bibliography.html#Butenhof-97">[Butenhof 97]</a>.</p>
<hr>
<p>Revised
<!--webbot bot="Timestamp" S-Type="EDITED" S-Format="%d %b %Y" startspan -->05 Nov 2001<!--webbot bot="Timestamp" endspan i-checksum="15246" --></p>
<p>© Copyright Beman Dawes, 2001</p>
</body>
</html>
|
