diff options
Diffstat (limited to 'Kokyu/docs/Kokyu.html')
| -rw-r--r-- | Kokyu/docs/Kokyu.html | 416 |
1 files changed, 0 insertions, 416 deletions
diff --git a/Kokyu/docs/Kokyu.html b/Kokyu/docs/Kokyu.html deleted file mode 100644 index 55c8016cd1c..00000000000 --- a/Kokyu/docs/Kokyu.html +++ /dev/null @@ -1,416 +0,0 @@ -<!-- $Id$ --> -<!doctype html public "-//w3c//dtd html 4.0 transitional//en"> -<html> -<head> - <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1"> - <meta name="Author" content="Venkita Subramonian"> - <meta name="GENERATOR" content="Mozilla/4.79 [en] (Windows NT 5.0; U) [Netscape]"> - <title>Kokyu</title> -</head> -<body> - -<center> -<h2> -<b><font size=+2>Kokyu - A middleware framework for flexible scheduling -and dispatching</font></b></h2></center> -<a href="#Introduction">Introduction</a> -<br><a href="#SchedFramework">Strategized Scheduling framework</a> -<br><a href="#FlexDispatch">Flexible Dispatching Framework</a> -<br><a href="#KokyuEC">Use of Kokyu within the TAO Real-time Event Channel(RTEC)</a> -<br><a href="#ConfigKokyuEC">Configuration of RTEC to use Kokyu dispatching</a> -<br><a href="#KokyuDSRTCORBA">Use of Kokyu within the Dynamic Scheduling -Real-time CORBA (DSRTCORBA) schedulers</a> -<br><a href="#newDSRTSched">How to write a new DSRT scheduler using Kokyu</a> -<br><a href="#DSRTCORBAvsRTEC">Kokyu DSRTCORBA vs Kokyu RTEC</a> -<br><a href="#Status">Current status</a> -<br><a href="#Future">Future work</a> -<br><a href="#Papers">Papers on Kokyu</a> -<br> -<h3> -<a NAME="Introduction"></a>Introduction</h3> -Kokyu is a portable middleware scheduling framework designed to provide -flexible scheduling and dispatching services within the context of higher-level -middleware. Kokyu currently provides real-time scheduling and dispatching -services for TAO’s real-time CORBA Event Service, which mediates supplier-consumer -relationships between application operations. Kokyu consists primarily -of two cooperating infrastructure segments, illustrated in Figure 1: -<center> -<p><img SRC="kokyu1.jpg" height=285 width=489> -<br><b>Figure 1: Kokyu Scheduling and Dispatching Infrastructure</b></center> - -<ol> -<li> -A pluggable scheduling infrastructure with efficient support for adaptive -execution of diverse static, dynamic, and hybrid static/dynamic scheduling -heuristics.</li> - -<li> -A flexible dispatching infrastructure that allows composition of primitive -operating system and middleware mechanisms to enforce arbitrary scheduling -heuristics.</li> -</ol> -The scheduler is responsible for specifying how operation dispatch requests -are ordered, by assigning priority levels and rates to tasks, and producing -a configuration specification for the dispatching mechanism. The dispatcher -is responsible for enforcing the ordering of operation dispatches using -different threads, requests queues, and timers configured according to -the scheduler’s specification. The combined framework provides an implicit -projection of scheduling heuristics into appropriate dispatching infrastructure -configurations, so that the scheduling and dispatching infrastructure segments -can be optimized both separately and in combination. -<h3> -<a NAME="SchedFramework"></a>Strategized Scheduling framework</h3> -The Kokyu scheduling framework is designed to support a variety of scheduling -heuristics including RMS, EDF, MLF, and MUF. In addition, this framework -provides a common environment to compare systematically both existing and -new scheduling strategies. This flexibility is achieved in the Kokyu framework -via the Strategy pattern, which allows parts of the sequence of steps in -an algorithm to be replaced, thus providing interchangeable variations -within a consistent algorithmic framework. The Kokyu scheduling framework -uses the Strategy pattern to encapsulate a family of scheduling algorithms -within a fixed CORBA IDL interface, thereby enabling different strategies -to be configured independently from applications that use them. -<h3> -<a NAME="FlexDispatch"></a>Flexible Dispatching Framework</h3> -The right side of Figure 1 shows the essential features of Kokyu’s flexible -task dispatching infrastructure. Key features of the dispatching infrastructure -that are essential to performing our optimizations are as follows: -<p><b>Dispatching queues:</b> Each task is assigned by our strategized -Kokyu scheduling framework to a specific dispatching queue, each -of which has an associated queue number, a queueing discipline, and a unique -operating-system-specific priority for its single associated dispatching -thread. -<p><b>Dispatching threads:</b> Operating-system thread priorities decrease -as the queue number increases, so that the 0th queue is served by the highest -priority thread. Each dispatching thread removes the task from the head -of its queue and runs its entry point function to completion before retrieving -the next task to dispatch. Adapters can be applied to operations to intercept -and possibly short-circuit the entry-point upcall. In general, however, -the outermost operation entry point must complete on each dispatch. -<p><b>Queueing disciplines: </b>Dispatching thread priorities determine -which queue is active at any given time: the highest priority queue with -a task to dispatch is always active, preempting tasks in lower priority -queues. In addition, each queue may have a distinct discipline for determining -which of its enqueued tasks has the highest eligibility, and must ensure -the highest is at the head of the queue at the point when one is to be -dequeued. We consider three disciplines: -<ul> -<li> -Static – Tasks are ordered by a static subpriority value – results in FIFO -ordering if all static subpriorities are made the same; static queues at -different priority levels can be used to implement an RMS scheduling strategy.</li> - -<li> -Deadline – Tasks are ordered by time to deadline; a single deadline queue -can be used to implement the earliest deadline first (EDF) scheduling strategy.</li> - -<li> -Laxity – Tasks are ordered by slack time, or laxity – the time to deadline -minus the execution time; a single laxity queue can be used to implement -the minimum laxity first (MLF) scheduling strategy; laxity queues at different -priority levels can be used to implement the maximum urgency first (MUF) -scheduling strategy.</li> -</ul> -Any discipline for which a maximal eligibility may be selected can be employed -to manage a given dispatching queue in this approach. Scheduling strategies -can be constructed from one or more queues of each discipline alone, or -combinations of queues with different disciplines can be used. Figure 2 -illustrates the general queueing mechanism used by the dispatching modules -in the Kokyu dispatching framework. -<center> -<p><img SRC="kokyu2.jpg" height=176 width=779> -<p><b>Figure 2: Example Queueing Mechanism in a Kokyu Dispatching Module</b></center> - -<p>In addition, this figure shows how the output information provided by -the Kokyu scheduling framework is used to configure and operate a dispatching -module. During system initialization, each dispatching module obtains the -thread priority and dispatching type for each of its queues, typically -from the scheduling service’s output interface. Next, each queue is assigned -a unique dispatching priority number, a unique thread priority, and an -enumerated dispatching type. Finally, each dispatching module has an ordered -queue of pending dispatches per dispatching priority. To preserve QoS guarantees, -operations are inserted into the appropriate dispatching queue according -to their assigned dispatching priority. Operations within a dispatching -queue are ordered by their assigned dispatching subpriority. To minimize -priority inversions, operations are dispatched from the queue with the -highest thread priority, preempting any operation executing in a lower -priority thread. To minimize preemption overhead, there is no preemption -within a given priority queue. The following three values are defined for -the dispatching type: -<ul> -<li> -<b>STATIC DISPATCHING</b>: This type specifies a queue that only considers -the static portion of an operation’s dispatching subpriority.</li> - -<li> -<b>DEADLINE DISPATCHING</b>: This type specifies a queue that considers -the dynamic and static portions of an operation’s dispatching subpriority, -and updates the dynamic portion according to the time remaining until the -operation’s deadline.</li> - -<li> -<b>LAXITY DISPATCHING</b>: This type specifies a queue that considers the -dynamic and static portions of an operation’s dispatching subpriority, -and updates the dynamic portion according to the operation’s laxity.</li> -</ul> - -<h3> -<a NAME="KokyuEC"></a>Use of Kokyu within the TAO Real-time Event Channel(RTEC)</h3> -Figure 3 shows the sequence of operations that take place in the Kokyu -based dispatching module in the TAO RTEC. The client application registers -all relevant operations with the scheduler along with their real-time requirements. -This is done through the concept of an <font face="Courier New,Courier">RT_Info -</font>(see -TAO/orbsvcs/orbsvcs/RtecScheduler.idl) structure which is a structure that -contains the execution time, criticality, period, etc of an operation. -The client then calls <font face="Courier New,Courier">compute_schedule</font> -method on the scheduler. The scheduler creates a dependency graphs of all -operations and partitions operations into equivalence classes based on -the scheduling parameters supplied. The scheduler can be configured to -have any scheduling policy which determines the equivalence class partitioning -(queues) and possibly a partial ordering of operations within an equivalence -class (ordering within a queue). Once this is done, the scheduler has the -configuration information for the Kokyu dispatcher like the number of dispatch -queues, priorities for the threads processing each queue, etc. -<p>When the client calls <font face="Courier New,Courier">activate</font> -on the event channel, the EC inturn activates the Kokyu based EC dispatching -module. The EC dispatching module queries the dispatch configuration from -the scheduler and uses that to create the Kokyu dispatcher with the appropriate -number of lanes and threads. When an event is pushed into the EC, the EC -pushes the event to the appropriate consumers, who are subscribed to that -event. For each consumer, the EC queries the scheduler for the RT_Info -of that consumer. It then hands over the event to the Kokyu based dispatching -module. The dispatching module then enqueues the event into the appropriate -queue for processing by the thread watching that queue. -<center> -<p><img SRC="KokyuEC.jpg" height=784 width=716> -<p><b>Figure 3: Kokyu based dispatching module within TAO RTEC</b></center> - -<h3> -<a NAME="ConfigKokyuEC"></a>Configuration of RTEC to use Kokyu dispatching</h3> -<b>Static configuration</b>: In the <b>svc.conf</b> file, make sure you -have the following configuration for Kokyu dispatching. You can combine -this with other -ECxxx options. -<p><font face="Courier New,Courier">static EC_Factory "-ECdispatching kokyu -SCHED_FIFO -ECscheduling kokyu -ECfiltering kokyu"</font> -<p>To run the threads in the real-time FIFO class, use SCHED_FIFO. You -could use SCHED_RR and SCHED_OTHER also. -<br>The default is SCHED_FIFO. -<p>In your program, call -<p><font face="Courier New,Courier">TAO_EC_Kokyu_Factory::init_svcs ();</font> -<p>to statically create the EC Kokyu dispatching and other Kokyu related -modules. -<p><b>Dynamic configuration</b>: In the <b>svc.conf</b> file, make sure -you have the following configuration for Kokyu dispatching. You can combine -this with other -ECxxx options. -<p><font face="Courier New,Courier">dynamic EC_Factory Service_Object * -TAO_RTKokyuEvent:_make_TAO_EC_Kokyu_Factory() "-ECdispatching kokyu -ECscheduling -kokyu -ECfiltering kokyu"</font> -<h3> -<a NAME="KokyuDSRTCORBA"></a>Use of Kokyu within the Dynamic Scheduling -Real-time CORBA (DSRTCORBA) schedulers</h3> -An initial implementation of mechanisms to support DSRTCORBA schedulers -have been released. DSRTCORBA uses the concept of distributed threads, -which traverse multiple end systems giving the application the illusion -of a single logical thread executing an end-to-end task. The distributed -thread carries with it the scheduling parameters like importance, deadline, -etc so that it can get scheduled by a local scheduler on each endsystem. -The Kokyu DSRT dispatching framework is used as an enforcing mechanism. -<p>The DSRT schedulers are available in the directory $TAO_ROOT/examples/Kokyu_dsrt_schedulers. -They use the Kokyu DSRT -<br>dispatching classes present in $ACE_ROOT/Kokyu. These act as wrappers/adapters -around the Kokyu DSRT dispatcher. The Kokyu DSRT dispatcher is responsible -for scheduling threads which ask the dispatcher to schedule themselves. -Currently there are two implementations for the Kokyu DSRT dispatcher. -One uses a condition-variable based approach for scheduling threads and -the other manipulates priorities of threads and relies on the OS scheduler -for dispatching the threads appropriately. -<h4> -CV-based approach:</h4> -In this approach, it is assumed that the threads "yield" on a regular basis -to the scheduler by calling <tt>update_scheduling_segment</tt>. Only one -thread is running at any point in time. All the other threads are blocked -on a condition variable. When the currently running thread yields, it will -cause the condition variable to be signalled. All the eligible threads -are stored in a scheduler queue (rbtree), the most eligible thread determined -by the scheduling discipline. This approach has the drawback that it requires -a cooperative threading model, where threads yield voluntarily on a regular -basis. The application threads are responsible for doing this voluntary -yielding. -<h4> -OS-based approach:</h4> -This approach relies on the OS scheduler to do the actual thread dispatching. -The Kokyu DSRT dispatcher manipulates the priorities of the threads. The -scheduler maintains a queue (rbtree) of threads. The scheduler also has -an executive thread, which runs at the maximum available priority. This -thread runs in a continuous loop until the dispatcher is shut down. The -executive thread is responsible for selecting the most eligible thread -from the scheduler queue and bump up its priority if necessary while bumping -down the priority of the currently running thread, if it is not the most -eligible. There are four priority levels required for this mechanism to -work, listed in descending order of priorities. For example, a thread running -at <i>Active</i> priority will preempt a -<br>thread running at <i>Inactive</i> priority level. -<ol> -<li> -Executive priority - priority at which the scheduler executive thread runs.</li> - -<li> -Blocked priority - this is the priority to which threads about to block -on remote calls will be bumped up to.</li> - -<li> -Active priority - this is the priority to which the most eligible thread -is set to.</li> - -<li> -Inactive priority - this is the priority to which all threads except the -most eligible thread is set to.</li> -</ol> -As soon as a thread asks to be scheduled, a wrapper object is created and -inserted into the queue. This object carries the qos (sched params) associated -with that thread. A condition variable is signalled to inform the executive -thread that the queue is "dirty". The scheduler thread picks up the most -eligble one and sets its priority to <i>active</i> and sets the currently -running thread priority to -<br><i>inactive</i>. -<p>The drawback to this approach is that it relies on the OS scheduler -to dispatch the threads. Also, with the current implementation, there is -only one thread running at active priority and others are all at <i>inactive</i> -level. This will create undesirable effects with multi-processor systems, -which could select any one of the <i>inactive</i> level threads and this -could cause priority inversions. -<h3> -<a NAME="newDSRTSched"></a>How to write a new DSRT scheduler using Kokyu</h3> -One can use one of the schedulers as a starting point. The variation points -are -<ol> -<li> -The scheduler parameters that need to be propagated along with the service -context.</li> - -<li> -The QoS comparison function, that determines which thread is more eligible.</li> -</ol> -To aid (1), we have created a Svc_Ctxt_DSRT_QoS idl interface (see ./Kokyu_qos.pidl). -This interface currently has the necessary things to be propagated for -FP, MIF and MUF schedulers. This can be altered if necessary to accomodate -new sched params. The idea here is to let the IDL compiler generate the -marshalling code (including Any operators) so that these parameters can -be shipped across in the service context in an encapsulated CDR. -<p>To create customized QoS comparator functions, we used the idea of C++ -traits to let the user define customized comparator functions. For example, -the MIF scheduler uses the following traits class. -<p><tt> struct MIF_Scheduler_Traits</tt> -<br><tt> {</tt> -<br><tt> typedef RTScheduling::Current::IdType Guid_t;</tt> -<p><tt> struct _QoSDescriptor_t</tt> -<br><tt> {</tt> -<br><tt> typedef long Importance_t;</tt> -<br><tt> Importance_t importance_;</tt> -<br><tt> };</tt> -<p><tt> typedef _QoSDescriptor_t QoSDescriptor_t;</tt> -<p><tt> typedef Kokyu::MIF_Comparator<QoSDescriptor_t> -QoSComparator_t;</tt> -<p><tt> class _Guid_Hash</tt> -<br><tt> {</tt> -<br><tt> public:</tt> -<br><tt> u_long operator () (const Guid_t& -id)</tt> -<br><tt> {</tt> -<br><tt> return ACE::hash_pjw -((const char *) id.get_buffer (),</tt> -<br><tt> -id.length ());</tt> -<br><tt> }</tt> -<br><tt> };</tt> -<p><tt> typedef _Guid_Hash Guid_Hash;</tt> -<br><tt> };</tt> -<p>The idea of traits makes the Kokyu dispatcher more flexible in terms -of creating new schedulers. For example, the Kokyu classes do not care -about what concrete type Guid is. It could be an OctetSequence for some -applications, whereas it could be an int for some others. The exact type -is defined by the application (in this case, the MIF scheduler) using the -traits class. In the above traits class the Guid's type is defined to be -an octet sequence (indirectly). The Kokyu dispatcher expects the following -typedef's to -<br>be present in the traits class: -<p><tt>Guid_t - </tt>Type of GUID. -<br><tt>QoSDescriptor_t - </tt>aggregate for scheduler parameters -<br><tt>QoSComparator_t - </tt>used by the scheduler queue to determine -most eligible item -<br><tt>Guid_Hash - </tt>used by the internal hash map in the scheduler -to hash the guid. -<p>It is also expected that the following operator be defined for comparing -QoS parameters. This comparator function will be used by the scheduler -queue to determine the most eligible item in the queue. -<p><tt>QoSComparator_t::operator ()(const QoSDescriptor_t& qos1,</tt> -<br><tt> -const QoSDescriptor_t& qos2)</tt> -<h3> -<a NAME="DSRTCORBAvsRTEC"></a>Kokyu DSRTCORBA vs Kokyu RTEC</h3> -Currently we have separate interfaces for DSRTCORBA and RTEC dispatching -mechanisms. Once we get more use cases and experience, there is a possibility -of these getting merged in the future. The RTEC related dispatching interface -is in <tt>Kokyu::Dispatcher (Kokyu.h)</tt> and DSRTCORBA related dispatching -interface is in <tt>Kokyu::DSRT_Dispatcher (Kokyu_dsrt.h)</tt> -<h3> -<a NAME="Status"></a>Current status</h3> -Kokyu dispatching framework is available as a separate module under <tt><font size=+1>ACE_wrappers/Kokyu</font></tt> -as part of the <a href="http://deuce.doc.wustl.edu/Download.html">ACE/TAO -distribution</a>. Note that this module is not dependent on TAO, though -it is built on top of ACE. The TAO Event Channel uses the Strategy and -Service Configurator patterns to use configurable dispatching modules. -A Kokyu based EC dispatching module is available in the <tt><font size=+1>TAO/orbsvcs/orbsvcs/RTKokyuEvent</font></tt> -module. This module acts as an adapter between the Kokyu dispatcher and -the RTEC. -<p>Kokyu scheduling framework is available under the TAO source tree (<tt><font size=+1>TAO/orbsvcs/orbsvcs/Sched</font></tt>). -<p>An example using the RTEC Kokyu dispatching module is available under -<tt><font size=+1>TAO/orbsvcs/examples/RtEC/Kokyu</font></tt>. -<h3> -<a NAME="Future"></a>Future work</h3> - -<ol> -<li> -Currently there is no support for timers in the Kokyu dispatching module. -We plan to do this in the near future.</li> - -<li> -It looks like there is a general structure to the different schedulers. -May be this can be abstracted using templates or some similar mechanism.</li> - -<li> -Thread sched policy and sched scope are currently being passed explicitly -from the application to the scheduler. This can be changed later to get -this information from the ORB. This requires the usage of RTORB and the -actual values can be set using svc.conf parameters for RT_ORB_Loader.</li> - -<br> -<li> -See whether the approaches could be extended to multiprocessor systems.</li> -</ol> - -<h3> -<a NAME="Papers"></a>Papers on Kokyu</h3> - -<ol> -<li> -Christopher D. Gill, <a href="http://www.cse.wustl.edu/~cdgill/PDF/cdgill_dissertation.pdf">Dissertation:Flexible -Scheduling in Middleware for Distributed Rate-Based Real-Time Applications</a></li> - -<li> -Christopher D. Gill, David L. Levine, and Douglas C. Schmidt <a href="http://www.cse.wustl.edu/~cdgill/PDF/dynamic.pdf">The -Design and Performance of a Real-Time CORBA Scheduling Service</a>, Real-Time -Systems: the International Journal of Time-Critical Computing Systems, -special issue on Real-Time Middleware, guest editor Wei Zhao, March 2001, -Vol. 20 No. 2</li> - -<li> -Christopher D. Gill, Douglas C. Schmidt, and Ron Cytron, <a href="http://www.cs.wustl.edu/~schmidt/PDF/embedded_sched.pdf">Multi-Paradigm -Scheduling for Distributed Real-Time Embedded Computing</a>, IEEE Proceedings -Special Issue on Modeling and Design of Embedded Systems, Volume 91, Number -1, January 2003.</li> -</ol> - -</body> -</html> |