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
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
|
<!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="Local Serializer">
<meta name="DC.subject" content="Local Serializer">
<meta name="keywords" content="Local Serializer">
<meta name="DC.Relation" scheme="URI" content="../../tbb_userguide/Design_Patterns/Design_Patterns.htm">
<meta name="DC.Relation" scheme="URI" content="Non-Preemptive_Priorities.htm#Non-Preemptive_Priorities">
<meta name="DC.Format" content="XHTML">
<meta name="DC.Identifier" content="Local_Serializer">
<link rel="stylesheet" type="text/css" href="../../intel_css_styles.css">
<title>Local Serializer</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="Local_Serializer">
<!-- ==============(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="Local_Serializer"><!-- --></a>
<h1 class="topictitle1">Local Serializer</h1>
<div>
<div class="section"><h2 class="sectiontitle">Context</h2>
<p>Consider an interactive program. To maximize concurrency and
responsiveness, operations requested by the user can be implemented as tasks.
The order of operations can be important. For example, suppose the program
presents editable text to the user. There might be operations to select text
and delete selected text. Reversing the order of "select" and "delete"
operations on the same buffer would be bad. However, commuting operations on
different buffers might be okay. Hence the goal is to establish serial ordering
of tasks associated with a given object, but not constrain ordering of tasks
between different objects.
</p>
</div>
<div class="section"><h2 class="sectiontitle">Forces</h2>
<ul type="disc">
<li>
<p>Operations associated with a certain object must be performed in
serial order.
</p>
</li>
<li>
<p>Serializing with a lock would be wasteful because threads would be
waiting at the lock when they could be doing useful work elsewhere.
</p>
</li>
</ul>
</div>
<div class="section"><h2 class="sectiontitle">Solution</h2>
<p>Sequence the work items using a FIFO (first-in first-out structure).
Always keep an item in flight if possible. If no item is in flight when a work
item appears, put the item in flight. Otherwise, push the item onto the FIFO.
When the current item in flight completes, pop another item from the FIFO and
put it in flight.
</p>
<p>The logic can be implemented without mutexes, by using
<samp class="codeph">concurrent_queue</samp> for the FIFO and
<samp class="codeph">atomic<int></samp> to count the number of items waiting
and in flight. The example explains the accounting in detail.
</p>
</div>
<div class="section"><h2 class="sectiontitle">Example</h2>
<p>The following example builds on the Non-Preemptive Priorities example
to implement local serialization in addition to priorities. It implements three
priority levels and local serializers. The user interface for it follows:
</p>
<pre>enum Priority {
P_High,
P_Medium,
P_Low
};
template<typename Func>
void EnqueueWork( Priority p, Func f, Serializer* s=NULL );</pre>
<p>Template function
<samp class="codeph">EnqueueWork</samp> causes functor
<var>f</var> to run when the three constraints in the following
table are met.
</p>
<div class="tablenoborder"><table cellpadding="4" summary="" frame="border" border="1" cellspacing="0" rules="all"><caption><span class="tablecap">Implementation of Constraints</span></caption>
<thead align="left">
<tr>
<th class="cellrowborder" valign="top" width="66.39676113360325%" id="d134980e118">
<p>Constraint
</p>
</th>
<th class="cellrowborder" valign="top" width="33.603238866396765%" id="d134980e124">
<p>Resolved by class...
</p>
</th>
</tr>
</thead>
<tbody>
<tr>
<td class="cellrowborder" valign="top" width="66.39676113360325%" headers="d134980e118 ">
<p>Any prior work for the
<samp class="codeph">Serializer</samp> has completed.
</p>
</td>
<td class="cellrowborder" valign="top" width="33.603238866396765%" headers="d134980e124 ">
<p><samp class="codeph">Serializer</samp>
</p>
</td>
</tr>
<tr>
<td class="cellrowborder" valign="top" width="66.39676113360325%" headers="d134980e118 ">
<p>A thread is available.
</p>
</td>
<td class="cellrowborder" valign="top" width="33.603238866396765%" headers="d134980e124 ">
<p><samp class="codeph">RunWorkItem</samp>
</p>
</td>
</tr>
<tr>
<td class="cellrowborder" valign="top" width="66.39676113360325%" headers="d134980e118 ">
<p>No higher priority work is ready to run.
</p>
</td>
<td class="cellrowborder" valign="top" width="33.603238866396765%" headers="d134980e124 ">
<p><samp class="codeph">ReadyPileType</samp>
</p>
</td>
</tr>
</tbody>
</table>
</div>
<p>Constraints on a given functor are resolved from top to bottom in the
table. The first constraint does not exist when s is NULL. The implementation
of
<samp class="codeph">EnqueueWork</samp> packages the functor in a
<samp class="codeph">SerializedWorkItem</samp> and routes it to the class that
enforces the first relevant constraint between pieces of work.
</p>
<pre>template<typename Func>
void EnqueueWork( Priority p, Func f, Serializer* s=NULL ) {
WorkItem* item = new SerializedWorkItem<Func>( p, f, s );
if( s )
s->add(item);
else
ReadyPile.add(item);
}</pre>
<p>A
<samp class="codeph">SerializedWorkItem</samp> is derived from a
<samp class="codeph">WorkItem</samp>, which serves as a way to pass around a
prioritized piece of work without knowing further details of the work.
</p>
<pre>// Abstract base class for a prioritized piece of work.
class WorkItem {
public:
WorkItem( Priority p ) : priority(p) {}
// Derived class defines the actual work.
virtual void run() = 0;
const Priority priority;
};
template<typename Func>
class SerializedWorkItem: public WorkItem {
<span xml:lang="PT-BR"> Serializer* serializer;</span>
<span xml:lang="PT-BR"> Func f;</span>
<span xml:lang="PT-BR"> /*override*/ void run() {</span>
<span xml:lang="PT-BR"> f();</span>
<span xml:lang="PT-BR"> Serializer* s = serializer;</span>
<span xml:lang="PT-BR"> // Destroy f before running Serializer’s next functor.</span>
delete this;
if( s )
s->noteCompletion();
}
public:
SerializedWorkItem( Priority p, const Func& f_, Serializer* s ) :
WorkItem(p), serializer(s), f(f_)
{}
};</pre>
<p>Base class
<samp class="codeph">WorkItem</samp> is the same as class WorkItem in the example
for Non-Preemptive Priorities. The notion of serial constraints is completely
hidden from the base class, thus permitting the framework to extend other kinds
of constraints or lack of constraints. Class
<samp class="codeph">SerializedWorkItem</samp> is essentially
<samp class="codeph">ConcreteWorkItem</samp> from the example for Non-Preemptive
Priorities, extended with a
<samp class="codeph">Serializer</samp> aspect.
</p>
<p>Virtual method
<samp class="codeph">run()</samp> is invoked when it becomes time to run the
functor. It performs three steps:
</p>
<ol>
<li>
<p>Run the functor
</p>
</li>
<li>
<p>Destroy the functor.
</p>
</li>
<li>
<p>Notify the
<samp class="codeph">Serializer</samp> that the functor completed, and thus
unconstraining the next waiting functor.
</p>
</li>
</ol>
<p>Step 3 is the difference from the operation of ConcreteWorkItem::run.
Step 2 could be done after step 3 in some contexts to increase concurrency
slightly. However, the presented order is recommended because if step 2 takes
non-trivial time, it likely has side effects that should complete before the
next functor runs.
</p>
<p>Class
<samp class="codeph">Serializer</samp> implements the core of the Local Serializer
pattern:
</p>
<pre>class Serializer {
tbb::concurrent_queue<WorkItem*> queue;
tbb::atomic<int> count; // Count of queued items and in-flight item
void moveOneItemToReadyPile() { // Transfer item from queue to ReadyPile
WorkItem* item;
queue.try_pop(item);
ReadyPile.add(item);
}
public:
void add( WorkItem* item ) {
queue.push(item);
if( ++count==1 )
moveOneItemToReadyPile();
}
void noteCompletion() { // Called when WorkItem completes.
if( ‐‐count!=0 )
moveOneItemToReadyPile();
}
};</pre>
<p>The class maintains two members:
</p>
<ul type="disc">
<li>
<p>A queue of WorkItem waiting for prior work to complete.
</p>
</li>
<li>
<p>A count of queued or in-flight work.
</p>
</li>
</ul>
<p>Mutexes are avoided by using
<samp class="codeph">concurrent_queue<WorkItem*></samp> and
<samp class="codeph">atomic<int></samp> along with careful ordering of
operations. The transitions of count are the key understanding how class
<samp class="codeph">Serializer</samp> works.
</p>
<ul type="disc">
<li>
<p>If method
<samp class="codeph">add</samp> increments
<samp class="codeph">count</samp> from 0 to 1, this indicates that no other
work is in flight and thus the work should be moved to the
<samp class="codeph">ReadyPile</samp>.
</p>
</li>
<li>
<p>If method
<samp class="codeph">noteCompletion</samp> decrements count and it is
<em>not</em> from 1 to 0, then the queue is non-empty and another
item in the queue should be moved to
<samp class="codeph">ReadyPile.</samp>
</p>
</li>
</ul>
<p>Class
<samp class="codeph">ReadyPile</samp> is explained in the example for
Non-Preemptive Priorities.
</p>
<p>If priorities are not necessary, there are two variations on method
<samp class="codeph">moveOneItemToReadyPile</samp>, with different implications.
</p>
<ul type="disc">
<li>
<p>Method
<samp class="codeph">moveOneItemToReadyPile</samp> could directly
invoke<samp class="codeph">item->run()</samp>. This approach has relatively low
overhead and high thread locality for a given
<samp class="codeph">Serializer</samp>. But it is unfair. If the
<samp class="codeph">Serializer</samp> has a continual stream of tasks, the
thread operating on it will keep servicing those tasks to the exclusion of
others.
</p>
</li>
<li>
<p>Method
<samp class="codeph">moveOneItemToReadyPile</samp> could invoke
<samp class="codeph">task::enqueue</samp> to enqueue a task that invokes
<samp class="codeph">item->run()</samp>. Doing so introduces higher
overhead and less locality than the first approach, but avoids starvation.
</p>
</li>
</ul>
<p>The conflict between fairness and maximum locality is fundamental. The
best resolution depends upon circumstance.
</p>
<p>The pattern generalizes to constraints on work items more general than
those maintained by class Serializer. A generalized
<samp class="codeph">Serializer::add</samp> determines if a work item is
unconstrained, and if so, runs it immediately. A generalized
<samp class="codeph">Serializer::noteCompletion</samp> runs all previously
constrained items that have become unconstrained by the completion of the
current work item. The term "run" means to run work immediately, or if there
are more constraints, forwarding the work to the next constraint resolver.
</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="Non-Preemptive_Priorities.htm#Non-Preemptive_Priorities">Non-Preemptive Priorities
</a></div></div>
</div>
</body>
</html>
|
