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
|
<!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="Non-Preemptive Priorities">
<meta name="DC.subject" content="Non-Preemptive Priorities">
<meta name="keywords" content="Non-Preemptive Priorities">
<meta name="DC.Relation" scheme="URI" content="../../tbb_userguide/Design_Patterns/Design_Patterns.htm">
<meta name="DC.Format" content="XHTML">
<meta name="DC.Identifier" content="Non-Preemptive_Priorities">
<link rel="stylesheet" type="text/css" href="../../intel_css_styles.css">
<title>Non-Preemptive Priorities</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="Non-Preemptive_Priorities">
<!-- ==============(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="Non-Preemptive_Priorities"><!-- --></a>
<h1 class="topictitle1">Non-Preemptive Priorities</h1>
<div>
<div class="section"><h2 class="sectiontitle">Problem</h2>
<p>Choose the next work item to do, based on priorities.
</p>
</div>
<div class="section"><h2 class="sectiontitle">Context</h2>
<p>The scheduler in Intel® Threading Building Blocks (Intel® TBB) chooses
tasks using rules based on scalability concerns. The rules are based on the
order in which tasks were spawned or enqueued, and are oblivious to the
contents of tasks. However, sometimes it is best to choose work based on some
kind of priority relationship.
</p>
</div>
<div class="section"><h2 class="sectiontitle">Forces</h2>
<ul type="disc">
<li>
<p>Given multiple work items, there is a rule for which item should
be done next that is
<em>not</em> the default Intel® TBB rule.
</p>
</li>
<li>
<p>Preemptive priorities are not necessary. If a higher priority item
appears, it is not necessary to immediately stop lower priority items in
flight. If preemptive priorities are necessary, then non-preemptive tasking is
inappropriate. Use threads instead.
</p>
</li>
</ul>
</div>
<div class="section"><h2 class="sectiontitle">Solution</h2>
<p>Put the work in a shared work pile. Decouple tasks from specific work,
so that task execution chooses the actual piece of work to be selected from the
pile.
</p>
</div>
<div class="section"><h2 class="sectiontitle">Example</h2>
<p id="NonPreemptivePrioritiesExample"><a name="NonPreemptivePrioritiesExample"><!-- --></a>The following example implements
three priority levels. The user interface for it and top-level implementation
follow:
</p>
<pre>enum Priority {
P_High,
P_Medium,
P_Low
};
template<typename Func>
void EnqueueWork( Priority p, Func f ) {
WorkItem* item = new ConcreteWorkItem<Func>( p, f );
ReadyPile.add(item);
}</pre>
<p>The caller provides a priority
<samp class="codeph">p</samp> and a functor
<samp class="codeph">f</samp> to routine
<samp class="codeph">EnqueueWork</samp>. The functor may be the result of a
lambda expression.
<samp class="codeph">EnqueueWork</samp> packages
<samp class="codeph">f</samp> as a
<samp class="codeph">WorkItem</samp> and adds it to global object
<samp class="codeph">ReadyPile</samp>.
</p>
<p>Class
<samp class="codeph">WorkItem</samp> provides a uniform interface for running
functors of unknown type:
</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></pre>
<pre id="ConcreteWorkItem"><a name="ConcreteWorkItem"><!-- --></a>class ConcreteWorkItem: public WorkItem {
Func f;
/*override*/ void run() {
f();
delete this;
}
public:
ConcreteWorkItem( Priority p, const Func& f_ ) :
WorkItem(p), f(f_)
{}
};</pre>
<p>Class
<samp class="codeph">ReadyPile</samp> contains the core pattern. It maintains a
collection of work and fires off tasks that choose work from the collection:
</p>
<pre id="ReadyPile"><a name="ReadyPile"><!-- --></a>class ReadyPileType {
// One queue for each priority level
tbb::concurrent_queue<WorkItem*> level[P_Low+1];
public:
void add( WorkItem* item ) {
level[item->priority].push(item);
tbb::task::enqueue(*new(tbb::task::allocate_root()) RunWorkItem);
}
void runNextWorkItem() {
// Scan queues in priority order for an item.
WorkItem* item=NULL;
for( int i=P_High; i<=P_Low; ++i )
if( level[i].try_pop(item) )
break;
assert(item);
item->run();
}
};
ReadyPileType ReadyPile;</pre>
<p>The task enqueued by
<samp class="codeph">add(item)</samp> does
<em>not</em> necessarily execute that item. The task executes
<samp class="codeph">runNextWorkItem()</samp>, which may find a higher priority
item. There is one task for each item, but the mapping resolves when the task
actually executes, not when it is created.
</p>
<p>Here are the details of class
<samp class="codeph">RunWorkItem</samp>:
</p>
<pre>class RunWorkItem: public tbb::task {
/*override*/tbb::task* execute(); // Private override of virtual method
};
...
tbb::task* RunWorkItem::execute() {
ReadyPile.runNextWorkItem();
return NULL;
};</pre>
<p><samp class="codeph">RunWorkItem</samp> objects are fungible. They enable the
Intel® TBB scheduler to choose when to do a work item, not which work item to
do. The override of virtual method
<samp class="codeph">task::execute</samp> is private because all calls to it are
dispatched via base class
<samp class="codeph">task</samp>.
</p>
<p>Other priority schemes can be implemented by changing the internals
for
<samp class="codeph">ReadyPileType</samp>. A priority queue could be used to
implement very fine grained priorities.
</p>
<p>The scalability of the pattern is limited by the scalability of
<samp class="codeph">ReadyPileType</samp>. Ideally scalable concurrent
containers should be used for it.
</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></div>
</body>
</html>
|
