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
|
<!DOCTYPE html
PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<!-- saved from url=(0014)about:internet -->
<html xmlns:MSHelp="http://www.microsoft.com/MSHelp/" lang="en-us" xml:lang="en-us"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<meta name="DC.Type" content="topic">
<meta name="DC.Title" content="Compare and Swap Loop">
<meta name="DC.subject" content="Compare and Swap Loop">
<meta name="keywords" content="Compare and Swap Loop">
<meta name="DC.Relation" scheme="URI" content="../../tbb_userguide/Design_Patterns/Design_Patterns.htm">
<meta name="DC.Relation" scheme="URI" content="Reduction.htm#Reduction">
<meta name="DC.Relation" scheme="URI" content="Reference_Counting.htm#Reference_Counting">
<meta name="DC.Format" content="XHTML">
<meta name="DC.Identifier" content="Compare_and_Swap_Loop">
<link rel="stylesheet" type="text/css" href="../../intel_css_styles.css">
<title>Compare and Swap Loop</title>
<xml>
<MSHelp:Attr Name="DocSet" Value="Intel"></MSHelp:Attr>
<MSHelp:Attr Name="Locale" Value="kbEnglish"></MSHelp:Attr>
<MSHelp:Attr Name="TopicType" Value="kbReference"></MSHelp:Attr>
</xml>
</head>
<body id="Compare_and_Swap_Loop">
<!-- ==============(Start:NavScript)================= -->
<script src="..\..\NavScript.js" language="JavaScript1.2" type="text/javascript"></script>
<script language="JavaScript1.2" type="text/javascript">WriteNavLink(2);</script>
<!-- ==============(End:NavScript)================= -->
<a name="Compare_and_Swap_Loop"><!-- --></a>
<h1 class="topictitle1">Compare and Swap Loop</h1>
<div>
<div class="section"><h2 class="sectiontitle">Problem</h2>
<p>Atomically update a scalar value so that a predicate is satisfied.
</p>
</div>
<div class="section"><h2 class="sectiontitle">Context</h2>
<p>Often a shared variable must be updated atomically, by a transform
that maps its old value to a new value. The transform might be a transition of
a finite state machine, or recording global knowledge. For instance, the shared
variable might be recording the maximum value that any thread has seen so far.
</p>
</div>
<div class="section"><h2 class="sectiontitle">Forces</h2>
<ul type="disc">
<li>
<p>The variable is read and updated by multiple threads.
</p>
</li>
<li>
<p>The hardware implements "compare and swap" for a variable of that
type.
</p>
</li>
<li>
<p>Protecting the update with a mutex is to be avoided.
</p>
</li>
</ul>
</div>
<div class="section"><h2 class="sectiontitle">Related</h2>
<ul type="disc">
<li>Reduction
</li>
<li>Reference Counting
</li>
</ul>
</div>
<div class="section"><h2 class="sectiontitle">Solution</h2>
<p>The solution is to atomically snapshot the current value, and then use
<samp class="codeph">atomic<T>::compare_and_swap</samp> to update it. Retry
until the
<samp class="codeph">compare_and_swap</samp> succeeds. In some cases it may be
possible to exit before the
<samp class="codeph">compare_and_swap</samp> succeeds because the current value
meets some condition.
</p>
<p>The template below does the update x=f(x) atomically.
</p>
<pre>// Atomically perform x=f(x).
template<typename F, typename T>
void AtomicUpdate( atomic<T>& x, F f ) {
int o;
do {
// Take a snapshot
o = x;
// Attempt to install new value computed from snapshot
} while( x.compare_and_swap(f(o),o)!=o );
}</pre>
<p>It is critical to take a snapshot and use it for intermediate
calculations, because the value of X may be changed by other threads in the
meantime.
</p>
<p>The following code shows how the template might be used to maintain a
global maximum of any value seen by
<samp class="codeph">RecordMax</samp>.
</p>
<pre>// Atomically perform UpperBound = max(UpperBound,y)
void RecordMax( int y ) {
extern atomic<int> UpperBound;
AtomicUpdate(UpperBound, [&](int value){return std::max(value,y);} );
}</pre>
<p>When y is not going to increase
<samp class="codeph">UpperBound</samp>, the call to
<samp class="codeph">AtomicUpdate</samp> will waste time doing the redundant
operation
<samp class="codeph">compare_and_swap(o,o)</samp>. In general, this kind of
redundancy can be eliminated by making the loop in
<samp class="codeph">AtomicUpdate</samp> exit early if
<samp class="codeph">f(o)==o</samp>. In this particular case where
<samp class="codeph">F==std::max<int></samp>, that test can be further
simplified. The following custom version of
<samp class="codeph">RecordMax</samp> has the simplified test.
</p>
<pre>// Atomically perform UpperBound =max(UpperBound,y)
void RecordMax( int y ) . .
extern atomic<int> UpperBound;
do {
// Take a snapshot
int o = UpperBound;
// Quit if snapshot meets condition.
if( o>=y ) break;
// Attempt to install new value.
} while( UpperBound.compare_and_swap(y,o)!=o );
}</pre>
<p>Because all participating threads modify a common location, the
performance of a compare and swap loop can be poor under high contention. Thus
the applicability of more efficient patterns should be considered first. In
particular:
</p>
<ul type="disc">
<li>
<p>If the overall purpose is a reduction, use the reduction pattern
instead.
</p>
</li>
<li>
<p>If the update is addition or subtraction, use
<samp class="codeph">atomic<T>::fetch_and_add</samp>. If the update is
addition or subtraction by one, use
<samp class="codeph">atomic<T>::operater++</samp> or
<samp class="codeph">atomic<T>::operator--</samp>. These methods
typically employ direct hardware support that avoids a compare and swap loop.
</p>
</li>
</ul>
<div class="Note"><h3 class="NoteTipHead">
Caution</h3>
<p>When using
<samp class="codeph">compare_and_swap</samp> to update links in a linked
structure, be sure you understand if the "ABA problem" is an issue. See the
Internet for discourses on the subject.
</p>
</div>
</div>
</div>
<div class="familylinks">
<div class="parentlink"><strong>Parent topic:</strong> <a href="../../tbb_userguide/Design_Patterns/Design_Patterns.htm">Design Patterns</a></div>
</div>
<div class="See Also">
<h2>See Also</h2>
<div class="linklist">
<div><a href="Reduction.htm#Reduction">Reduction
</a></div>
<div><a href="Reference_Counting.htm#Reference_Counting">Reference Counting
</a></div></div>
</div>
</body>
</html>
|
