| blob | e785f94985912479f0ef80946c2cc52fe9c25c3d |
1 <!-- -->
3 <html>
4 <head>
9 </head>
10 <body>
12 <center>
13 <h2>
15 and dispatching</font></b></h2></center>
22 Real-time CORBA (DSRTCORBA) schedulers</a>
29 <h3>
31 Kokyu is a portable middleware scheduling framework designed to provide
32 flexible scheduling and dispatching services within the context of higher-level
33 middleware. Kokyu currently provides real-time scheduling and dispatching
34 services for TAO�s real-time CORBA Event Service, which mediates supplier-consumer
35 relationships between application operations. Kokyu consists primarily
36 of two cooperating infrastructure segments, illustrated in Figure 1:
37 <center>
41 <ol>
42 <li>
43 A pluggable scheduling infrastructure with efficient support for adaptive
44 execution of diverse static, dynamic, and hybrid static/dynamic scheduling
45 heuristics.</li>
47 <li>
48 A flexible dispatching infrastructure that allows composition of primitive
49 operating system and middleware mechanisms to enforce arbitrary scheduling
50 heuristics.</li>
51 </ol>
52 The scheduler is responsible for specifying how operation dispatch requests
53 are ordered, by assigning priority levels and rates to tasks, and producing
54 a configuration specification for the dispatching mechanism. The dispatcher
55 is responsible for enforcing the ordering of operation dispatches using
56 different threads, requests queues, and timers configured according to
57 the scheduler�s specification. The combined framework provides an implicit
58 projection of scheduling heuristics into appropriate dispatching infrastructure
59 configurations, so that the scheduling and dispatching infrastructure segments
60 can be optimized both separately and in combination.
61 <h3>
63 The Kokyu scheduling framework is designed to support a variety of scheduling
64 heuristics including RMS, EDF, MLF, and MUF. In addition, this framework
65 provides a common environment to compare systematically both existing and
66 new scheduling strategies. This flexibility is achieved in the Kokyu framework
67 via the Strategy pattern, which allows parts of the sequence of steps in
68 an algorithm to be replaced, thus providing interchangeable variations
69 within a consistent algorithmic framework. The Kokyu scheduling framework
70 uses the Strategy pattern to encapsulate a family of scheduling algorithms
71 within a fixed CORBA IDL interface, thereby enabling different strategies
72 to be configured independently from applications that use them.
73 <h3>
75 The right side of Figure 1 shows the essential features of Kokyu�s flexible
76 task dispatching infrastructure. Key features of the dispatching infrastructure
77 that are essential to performing our optimizations are as follows:
79 Kokyu scheduling framework to a specific dispatching queue, each
80 of which has an associated queue number, a queueing discipline, and a unique
81 operating-system-specific priority for its single associated dispatching
82 thread.
84 as the queue number increases, so that the 0th queue is served by the highest
85 priority thread. Each dispatching thread removes the task from the head
86 of its queue and runs its entry point function to completion before retrieving
87 the next task to dispatch. Adapters can be applied to operations to intercept
88 and possibly short-circuit the entry-point upcall. In general, however,
89 the outermost operation entry point must complete on each dispatch.
91 which queue is active at any given time: the highest priority queue with
92 a task to dispatch is always active, preempting tasks in lower priority
93 queues. In addition, each queue may have a distinct discipline for determining
94 which of its enqueued tasks has the highest eligibility, and must ensure
95 the highest is at the head of the queue at the point when one is to be
96 dequeued. We consider three disciplines:
97 <ul>
98 <li>
99 Static � Tasks are ordered by a static subpriority value � results in FIFO
100 ordering if all static subpriorities are made the same; static queues at
101 different priority levels can be used to implement an RMS scheduling strategy.</li>
103 <li>
104 Deadline � Tasks are ordered by time to deadline; a single deadline queue
105 can be used to implement the earliest deadline first (EDF) scheduling strategy.</li>
107 <li>
108 Laxity � Tasks are ordered by slack time, or laxity � the time to deadline
109 minus the execution time; a single laxity queue can be used to implement
110 the minimum laxity first (MLF) scheduling strategy; laxity queues at different
111 priority levels can be used to implement the maximum urgency first (MUF)
112 scheduling strategy.</li>
113 </ul>
114 Any discipline for which a maximal eligibility may be selected can be employed
115 to manage a given dispatching queue in this approach. Scheduling strategies
116 can be constructed from one or more queues of each discipline alone, or
118 illustrates the general queueing mechanism used by the dispatching modules
119 in the Kokyu dispatching framework.
120 <center>
124 <p>In addition, this figure shows how the output information provided by
125 the Kokyu scheduling framework is used to configure and operate a dispatching
126 module. During system initialization, each dispatching module obtains the
127 thread priority and dispatching type for each of its queues, typically
128 from the scheduling service�s output interface. Next, each queue is assigned
129 a unique dispatching priority number, a unique thread priority, and an
130 enumerated dispatching type. Finally, each dispatching module has an ordered
131 queue of pending dispatches per dispatching priority. To preserve QoS guarantees,
132 operations are inserted into the appropriate dispatching queue according
133 to their assigned dispatching priority. Operations within a dispatching
134 queue are ordered by their assigned dispatching subpriority. To minimize
135 priority inversions, operations are dispatched from the queue with the
136 highest thread priority, preempting any operation executing in a lower
137 priority thread. To minimize preemption overhead, there is no preemption
138 within a given priority queue. The following three values are defined for
139 the dispatching type:
140 <ul>
141 <li>
143 the static portion of an operation�s dispatching subpriority.</li>
145 <li>
147 the dynamic and static portions of an operation�s dispatching subpriority,
148 and updates the dynamic portion according to the time remaining until the
149 operation�s deadline.</li>
151 <li>
153 dynamic and static portions of an operation�s dispatching subpriority,
154 and updates the dynamic portion according to the operation�s laxity.</li>
155 </ul>
157 <h3>
159 Figure 3 shows the sequence of operations that take place in the Kokyu
160 based dispatching module in the TAO RTEC. The client application registers
161 all relevant operations with the scheduler along with their real-time requirements.
163 </font>(see
164 TAO/orbsvcs/orbsvcs/RtecScheduler.idl) structure which is a structure that
165 contains the execution time, criticality, period, etc of an operation.
167 method on the scheduler. The scheduler creates a dependency graphs of all
168 operations and partitions operations into equivalence classes based on
169 the scheduling parameters supplied. The scheduler can be configured to
170 have any scheduling policy which determines the equivalence class partitioning
171 (queues) and possibly a partial ordering of operations within an equivalence
172 class (ordering within a queue). Once this is done, the scheduler has the
173 configuration information for the Kokyu dispatcher like the number of dispatch
174 queues, priorities for the threads processing each queue, etc.
176 on the event channel, the EC inturn activates the Kokyu based EC dispatching
177 module. The EC dispatching module queries the dispatch configuration from
178 the scheduler and uses that to create the Kokyu dispatcher with the appropriate
179 number of lanes and threads. When an event is pushed into the EC, the EC
180 pushes the event to the appropriate consumers, who are subscribed to that
181 event. For each consumer, the EC queries the scheduler for the RT_Info
182 of that consumer. It then hands over the event to the Kokyu based dispatching
183 module. The dispatching module then enqueues the event into the appropriate
184 queue for processing by the thread watching that queue.
185 <center>
189 <h3>
192 have the following configuration for Kokyu dispatching. You can combine
193 this with other -ECxxx options.
196 <p>To run the threads in the real-time FIFO class, use SCHED_FIFO. You
197 could use SCHED_RR and SCHED_OTHER also.
198 <br>The default is SCHED_FIFO.
199 <p>In your program, call
201 <p>to statically create the EC Kokyu dispatching and other Kokyu related
202 modules.
204 you have the following configuration for Kokyu dispatching. You can combine
205 this with other -ECxxx options.
207 TAO_RTKokyuEvent:_make_TAO_EC_Kokyu_Factory() "-ECdispatching kokyu -ECscheduling
209 <h3>
211 Real-time CORBA (DSRTCORBA) schedulers</h3>
212 An initial implementation of mechanisms to support DSRTCORBA schedulers
213 have been released. DSRTCORBA uses the concept of distributed threads,
214 which traverse multiple end systems giving the application the illusion
215 of a single logical thread executing an end-to-end task. The distributed
216 thread carries with it the scheduling parameters like importance, deadline,
217 etc so that it can get scheduled by a local scheduler on each endsystem.
218 The Kokyu DSRT dispatching framework is used as an enforcing mechanism.
219 <p>The DSRT schedulers are available in the directory $TAO_ROOT/examples/Kokyu_dsrt_schedulers.
220 They use the Kokyu DSRT
221 <br>dispatching classes present in $ACE_ROOT/Kokyu. These act as wrappers/adapters
222 around the Kokyu DSRT dispatcher. The Kokyu DSRT dispatcher is responsible
223 for scheduling threads which ask the dispatcher to schedule themselves.
224 Currently there are two implementations for the Kokyu DSRT dispatcher.
225 One uses a condition-variable based approach for scheduling threads and
226 the other manipulates priorities of threads and relies on the OS scheduler
227 for dispatching the threads appropriately.
228 <h4>
229 CV-based approach:</h4>
230 In this approach, it is assumed that the threads "yield" on a regular basis
232 thread is running at any point in time. All the other threads are blocked
233 on a condition variable. When the currently running thread yields, it will
234 cause the condition variable to be signalled. All the eligible threads
235 are stored in a scheduler queue (rbtree), the most eligible thread determined
236 by the scheduling discipline. This approach has the drawback that it requires
237 a cooperative threading model, where threads yield voluntarily on a regular
238 basis. The application threads are responsible for doing this voluntary
239 yielding.
240 <h4>
241 OS-based approach:</h4>
242 This approach relies on the OS scheduler to do the actual thread dispatching.
243 The Kokyu DSRT dispatcher manipulates the priorities of the threads. The
244 scheduler maintains a queue (rbtree) of threads. The scheduler also has
245 an executive thread, which runs at the maximum available priority. This
246 thread runs in a continuous loop until the dispatcher is shut down. The
247 executive thread is responsible for selecting the most eligible thread
248 from the scheduler queue and bump up its priority if necessary while bumping
249 down the priority of the currently running thread, if it is not the most
250 eligible. There are four priority levels required for this mechanism to
251 work, listed in descending order of priorities. For example, a thread running
254 <ol>
255 <li>
256 Executive priority - priority at which the scheduler executive thread runs.</li>
258 <li>
259 Blocked priority - this is the priority to which threads about to block
260 on remote calls will be bumped up to.</li>
262 <li>
263 Active priority - this is the priority to which the most eligible thread
264 is set to.</li>
266 <li>
267 Inactive priority - this is the priority to which all threads except the
268 most eligible thread is set to.</li>
269 </ol>
270 As soon as a thread asks to be scheduled, a wrapper object is created and
271 inserted into the queue. This object carries the qos (sched params) associated
272 with that thread. A condition variable is signalled to inform the executive
273 thread that the queue is "dirty". The scheduler thread picks up the most
275 running thread priority to
277 <p>The drawback to this approach is that it relies on the OS scheduler
278 to dispatch the threads. Also, with the current implementation, there is
280 level. This will create undesirable effects with multi-processor systems,
282 could cause priority inversions.
283 <h3>
285 One can use one of the schedulers as a starting point. The variation points
286 are
287 <ol>
288 <li>
289 The scheduler parameters that need to be propagated along with the service
290 context.</li>
292 <li>
293 The QoS comparison function, that determines which thread is more eligible.</li>
294 </ol>
295 To aid (1), we have created a Svc_Ctxt_DSRT_QoS idl interface (see ./Kokyu_qos.pidl).
296 This interface currently has the necessary things to be propagated for
297 FP, MIF and MUF schedulers. This can be altered if necessary to accomodate
298 new sched params. The idea here is to let the IDL compiler generate the
299 marshalling code (including Any operators) so that these parameters can
300 be shipped across in the service context in an encapsulated CDR.
301 <p>To create customized QoS comparator functions, we used the idea of C++
302 traits to let the user define customized comparator functions. For example,
303 the MIF scheduler uses the following traits class.
314 QoSComparator_t;</tt>
319 id)</tt>
322 ((const char *) id.get_buffer (),</tt>
323 <br><tt>
324 id.length ());</tt>
329 <p>The idea of traits makes the Kokyu dispatcher more flexible in terms
330 of creating new schedulers. For example, the Kokyu classes do not care
331 about what concrete type Guid is. It could be an OctetSequence for some
332 applications, whereas it could be an int for some others. The exact type
333 is defined by the application (in this case, the MIF scheduler) using the
334 traits class. In the above traits class the Guid's type is defined to be
335 an octet sequence (indirectly). The Kokyu dispatcher expects the following
336 typedef's to
337 <br>be present in the traits class:
341 most eligible item
343 to hash the guid.
344 <p>It is also expected that the following operator be defined for comparing
345 QoS parameters. This comparator function will be used by the scheduler
346 queue to determine the most eligible item in the queue.
350 <h3>
352 Currently we have separate interfaces for DSRTCORBA and RTEC dispatching
353 mechanisms. Once we get more use cases and experience, there is a possibility
354 of these getting merged in the future. The RTEC related dispatching interface
357 <h3>
359 Kokyu dispatching framework is available as a separate module under <tt><font size=+1>ACE_wrappers/Kokyu</font></tt>
361 distribution</a>. Note that this module is not dependent on TAO, though
362 it is built on top of ACE. The TAO Event Channel uses the Strategy and
363 Service Configurator patterns to use configurable dispatching modules.
364 A Kokyu based EC dispatching module is available in the <tt><font size=+1>TAO/orbsvcs/orbsvcs/RTKokyuEvent</font></tt>
365 module. This module acts as an adapter between the Kokyu dispatcher and
366 the RTEC.
367 <p>Kokyu scheduling framework is available under the TAO source tree (<tt><font size=+1>TAO/orbsvcs/orbsvcs/Sched</font></tt>).
368 <p>An example using the RTEC Kokyu dispatching module is available under
370 <h3>
373 <ol>
374 <li>
375 Currently there is no support for timers in the Kokyu dispatching module.
376 We plan to do this in the near future.</li>
378 <li>
379 It looks like there is a general structure to the different schedulers.
380 May be this can be abstracted using templates or some similar mechanism.</li>
382 <li>
383 Thread sched policy and sched scope are currently being passed explicitly
384 from the application to the scheduler. This can be changed later to get
385 this information from the ORB. This requires the usage of RTORB and the
386 actual values can be set using svc.conf parameters for RT_ORB_Loader.</li>
389 <li>
390 See whether the approaches could be extended to multiprocessor systems.</li>
391 </ol>
393 <h3>
396 <ol>
397 <li>
398 Christopher D. Gill, <a href="http://www.cse.wustl.edu/~cdgill/PDF/cdgill_dissertation.pdf">Dissertation:Flexible
399 Scheduling in Middleware for Distributed Rate-Based Real-Time Applications</a></li>
401 <li>
402 Christopher D. Gill, David L. Levine, and Douglas C. Schmidt <a href="http://www.cse.wustl.edu/~cdgill/PDF/dynamic.pdf">The
403 Design and Performance of a Real-Time CORBA Scheduling Service</a>, Real-Time
404 Systems: the International Journal of Time-Critical Computing Systems,
405 special issue on Real-Time Middleware, guest editor Wei Zhao, March 2001,
408 <li>
409 Christopher D. Gill, Douglas C. Schmidt, and Ron Cytron, <a href="http://www.dre.vanderbilt.edu/~schmidt/PDF/embedded_sched.pdf">Multi-Paradigm
410 Scheduling for Distributed Real-Time Embedded Computing</a>, IEEE Proceedings
411 Special Issue on Modeling and Design of Embedded Systems, Volume 91, Number
413 </ol>
415 </body>
416 </html>