1.. _Non-Preemptive_Priorities:
2
3Non-Preemptive Priorities
4=========================
5
6
7.. container:: section
8
9
10   .. rubric:: Problem
11      :class: sectiontitle
12
13   Choose the next work item to do, based on priorities.
14
15
16.. container:: section
17
18
19   .. rubric:: Context
20      :class: sectiontitle
21
22   The scheduler in |full_name|
23   chooses tasks using rules based on scalability concerns. The rules
24   are based on the order in which tasks were spawned or enqueued, and
25   are oblivious to the contents of tasks. However, sometimes it is best
26   to choose work based on some kind of priority relationship.
27
28
29.. container:: section
30
31
32   .. rubric:: Forces
33      :class: sectiontitle
34
35   -  Given multiple work items, there is a rule for which item should
36      be done next that is *not* the default oneTBB rule.
37
38
39   -  Preemptive priorities are not necessary. If a higher priority item
40      appears, it is not necessary to immediately stop lower priority
41      items in flight. If preemptive priorities are necessary, then
42      non-preemptive tasking is inappropriate. Use threads instead.
43
44
45.. container:: section
46
47
48   .. rubric:: Solution
49      :class: sectiontitle
50
51   Put the work in a shared work pile. Decouple tasks from specific
52   work, so that task execution chooses the actual piece of work to be
53   selected from the pile.
54
55
56.. container:: section
57
58
59   .. rubric:: Example
60      :class: sectiontitle
61
62   The following example implements three priority levels. The user
63   interface for it and top-level implementation follow:
64
65
66   ::
67
68
69      enum Priority {
70         P_High,
71         P_Medium,
72         P_Low
73      };
74       
75
76      template<typename Func>
77      void EnqueueWork( Priority p, Func f ) {
78         WorkItem* item = new ConcreteWorkItem<Func>( p, f );
79         ReadyPile.add(item);
80      }
81
82
83   The caller provides a priority ``p`` and a functor ``f`` to routine ``EnqueueWork``.
84   The functor may be the result of a lambda expression. ``EnqueueWork`` packages ``f`` as a ``WorkItem`` and adds
85   it to global object ``ReadyPile``.
86
87
88   Class ``WorkItem`` provides a uniform interface for running functors of unknown type:
89
90
91   ::
92
93
94      // Abstract base class for a prioritized piece of work.
95      class WorkItem {
96      public:
97         WorkItem( Priority p ) : priority(p) {}
98         // Derived class defines the actual work.
99         virtual void run() = 0;
100         const Priority priority;
101      };
102       
103
104      template<typename Func>
105      class ConcreteWorkItem: public WorkItem {
106         Func f;
107         /*override*/ void run() {
108             f();
109             delete this;
110         }
111      public:
112         ConcreteWorkItem( Priority p, const Func& f_ ) :
113             WorkItem(p), f(f_)
114         {}
115      };
116
117
118   Class ``ReadyPile`` contains the core pattern. It maintains a
119   collection of work and fires off tasks through the ``oneapi::tbb::task_group::run`` interface
120   and then choose a work from the collection:
121
122
123   ::
124
125
126      class ReadyPileType {
127         // One queue for each priority level
128         oneapi::tbb::concurrent_queue<WorkItem*> level[P_Low+1];
129         oneapi::tbb::task_group tg;
130      public:
131         void add( WorkItem* item ) {
132             level[item->priority].push(item);
133             tg.run(RunWorkItem());
134         }
135         void runNextWorkItem() {
136             // Scan queues in priority order for an item.
137             WorkItem* item=NULL;
138             for( int i=P_High; i<=P_Low; ++i )
139                 if( level[i].try_pop(item) )
140                     break;
141             assert(item);
142             item->run();
143         }
144      };
145       
146
147      ReadyPileType ReadyPile;
148
149
150   The task added by ``add(item)`` does *not* necessarily execute
151   that item. The task itself executes ``runNextWorkItem()``, which may find a
152   higher priority item. There is one task for each item, but the
153   mapping resolves when the task actually executes, not when it is created.
154
155   Here are the details of class ``RunWorkItem``:
156
157   ::
158
159      class RunWorkItem {
160         void operator()() {
161             ReadyPile.runNextWorkItem();
162         };
163      };
164
165
166   ``RunWorkItem`` objects are fungible. They enable the oneTBB
167   scheduler to choose when to do a work item, not which work item to do.
168
169
170   Other priority schemes can be implemented by changing the internals
171   for ``ReadyPileType``. A priority queue could be used to implement
172   very fine grained priorities.
173
174   The scalability of the pattern is limited by the scalability of
175   ``ReadyPileType``. Ideally scalable concurrent containers should be
176   used for it.
177
178