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
|
<!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="Lazy Initialization">
<meta name="DC.subject" content="Lazy Initialization">
<meta name="keywords" content="Lazy Initialization">
<meta name="DC.Relation" scheme="URI" content="../../tbb_userguide/Design_Patterns/Design_Patterns.htm">
<meta name="DC.Relation" scheme="URI" content="Fenced_Data_Transfer.htm#Fenced_Data_Transfer">
<meta name="DC.Format" content="XHTML">
<meta name="DC.Identifier" content="Lazy_Initialization">
<link rel="stylesheet" type="text/css" href="../../intel_css_styles.css">
<title>Lazy Initialization</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="Lazy_Initialization">
<!-- ==============(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="Lazy_Initialization"><!-- --></a>
<h1 class="topictitle1">Lazy Initialization</h1>
<div>
<div class="section"><h2 class="sectiontitle">Problem</h2>
<p>Perform an initialization the first time it is needed.
</p>
</div>
<div class="section"><h2 class="sectiontitle">Context</h2>
<p>Initializing data structures lazily is a common technique. Not only
does it avoid the cost of initializing unused data structures, it is often a
more convenient way to structure a program.
</p>
</div>
<div class="section"><h2 class="sectiontitle">Forces</h2>
<ul type="disc">
<li>
<p>Threads share access to an object.
</p>
</li>
<li>
<p>The object should not be created until the first access.
</p>
</li>
</ul>
<p>The second force covers several possible motivations:
</p>
<ul type="disc">
<li>
<p>The object is expensive to create and creating it early would slow
down program startup.
</p>
</li>
<li>
<p>It is not used in every run of the program.
</p>
</li>
<li>
<p>Early initialization would require adding code where it is
undesirable for readability or structural reasons.
</p>
</li>
</ul>
</div>
<div class="section"><h2 class="sectiontitle">Related</h2>
<ul type="disc">
<li>Fenced Data Transfer
</li>
</ul>
</div>
<div class="section"><h2 class="sectiontitle">Solutions</h2>
<p>A parallel solution is substantially trickier, because it must deal
with several concurrency issues.
</p>
<div class="nobullet">
<p class="nobullet"><strong>Races:</strong> If two threads attempt to simultaneously access to
the object for the first time, and thus cause creation of the object, the race
must be resolved in a way that both threads end up with a reference to the same
object of type
<samp class="codeph">T</samp>.
</p>
<p class="nobullet"><strong>Memory leaks:</strong> In the event of a race, the implementation
must ensure that any extra transient
<samp class="codeph">T</samp> objects are cleaned up.
</p>
<p class="nobullet"><strong>Memory consistency:</strong> If thread X executes
<samp class="codeph">value=new T()</samp>, all other threads must see stores
by
<samp class="codeph">new T()</samp> occur before the assignment
<samp class="codeph">value=</samp>.
</p>
<p class="nobullet"><strong>Deadlock:</strong> What if the constructor of
<samp class="codeph">T()</samp> requires acquiring a lock, but the current
holder of that lock is also racing to access the object for the first time?
</p>
</div>
<p>There are two solutions. One is based on double-check locking. The
other relies on compare-and-swap. Because the tradeoffs and issues are subtle,
most of the discussion is in the following examples section.
</p>
</div>
<div class="section"><h2 class="sectiontitle">Examples</h2>
<p>An Intel® Threading Building Blocks (Intel® TBB) implementation of the "double-check" pattern is shown
below.
</p>
<pre>template<typename T, typename Mutex=tbb::mutex>
class lazy {
tbb::atomic<T*> value;
Mutex mut;
public:
lazy() : value() {} // Initializes value to NULL
~lazy() {delete value;}
T& get() {
if( !value ) { // Read of value has <em>acquire</em> semantics.
Mutex::scoped_lock lock(mut);
if( !value ) value = new T();. // Write of value has <em>release</em> semantics
}
return *value;
}
};</pre>
<p>The name comes from the way that the pattern deals with races. There
is one check done without locking and one check done after locking. The first
check handles the presumably common case that the initialization has already
been done, without any locking. The second check deals with cases where two
threads both see an uninitialized value, and both try to acquire the lock. In
that case, the second thread to acquire the lock will see that the
initialization has already occurred.
</p>
<p>If
<samp class="codeph">T()</samp> throws an exception, the solution is correct
because
<samp class="codeph">value</samp> will still be NULL and the mutex unlocked when
object
<samp class="codeph">lock</samp> is destroyed.
</p>
<p>The solution correctly addresses memory consistency issues. A write to
a
<samp class="codeph">tbb::atomic</samp> value has
<em>release</em> semantics, which means that all of its prior writes will
be seen before the releasing write. A read from
<samp class="codeph">tbb::atomic</samp> value has
<em>acquire</em> semantics, which means that all of its subsequent reads
will happen after the acquiring read. Both of these properties are critical to
the solution. The releasing write ensures that the construction of
<samp class="codeph">T()</samp> is seen to occur before the assignment to value. The
acquiring read ensures that when the caller reads from
<samp class="codeph">*value</samp>, the reads occur after the
"<samp class="codeph">if(!value)</samp>" check. The release/acquire is
essentially the Fenced Data Transfer pattern, where the
"message" is the fully constructed instance
<samp class="codeph">T()</samp>, and the "ready" flag is the pointer
<samp class="codeph">value</samp>.
</p>
<p>The solution described involves blocking threads while initialization
occurs. Hence it can suffer the usual pathologies associated with blocking. For
example, if the thread first acquires the lock is suspended by the OS, all
other threads will have to wait until that thread resumes. A lock-free
variation avoids this problem by making all contending threads attempt
initialization, and atomically deciding which attempt succeeds.
</p>
<p>An Intel® TBB implementation of the non-blocking variant follows. It
also uses double-check, but without a lock.
</p>
<pre>template<typename T>
class lazy {
tbb::atomic<T*> value;
public:
lazy() : value() {} // Initializes value to NULL
~lazy() {delete value;}
T& get() {
if( !value ) {
T* tmp = new T();
if( value.compare_and_swap(tmp,NULL)!=NULL )
// Another thread installed the value, so throw away mine.
delete tmp;
}
return *value;
}
};</pre>
<p>The second check is performed by the expression<samp class="codeph">
value.compare_and_swap(tmp,NULL)!=NULL</samp>, which conditionally assigns
<samp class="codeph">value=tmp</samp> if
<samp class="codeph">value==NULL</samp>, and returns true if the old
<samp class="codeph">value</samp> was NULL. Thus if multiple threads attempt
simultaneous initialization, the first thread to execute the
<samp class="codeph">compare_and_swap</samp> will set value to point to its T
object. Other contenders that execute the
<samp class="codeph">compare_and_swap</samp> will get back a non-NULL pointer,
and know that they should delete their transient T objects.
</p>
<p>As with the locking solution, memory consistency issues are addressed
by the semantics of
<samp class="codeph">tbb::atomic</samp>. The first check has
<em>acquire</em> semantics and the
<samp class="codeph">compare_and_swap</samp> has both
<em>acquire</em> and
<em>release</em> semantics.
</p>
</div>
<div class="section"><h2 class="sectiontitle">References</h2>
<p>Lawrence Crowl, "Dynamic Initialization and Destruction with Concurrency",
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2660.htm
</p>
</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="Fenced_Data_Transfer.htm#Fenced_Data_Transfer">Fenced Data Transfer
</a></div></div>
</div>
</body>
</html>
|
