TAO/examples/Kokyu_dsrt_schedulers/README

   1 Design approaches for the Kokyu based DSRT scheduler/dispatcher
   2 --------------------------------------------------------
   3
   4 The DSRT schedulers in this directory use the Kokyu DSRT
   5 dispatching classes present in $ACE_ROOT/Kokyu. These
   6 act as wrappers/adapters around the Kokyu DSRT dispatcher.
   7 The Kokyu DSRT dispatcher is responsible for scheduling
   8 threads which ask the dispatcher to schedule themselves.
   9 Currently there are two implementations for the Kokyu
  10 DSRT dispatcher. One uses a condition-variable based
  11 approach for scheduling threads and the other manipulates
  12 priorities of threads and relies on the OS scheduler for
  13 dispatching the threads appropriately.
  14
  15 CV-based approach
  16 -----------------
  17 In this approach, it is assumed that the threads "yield"
  18 on a regular basis to the scheduler by calling
  19 update_scheduling_segment. Only one thread is running at
  20 any point in time. All the other threads are blocked
  21 on a condition variable. When the currently running
  22 thread yields, it will cause the condition variable
  23 to be signalled. All the eligible threads are stored
  24 in a scheduler queue (rbtree), the most eligible thread
  25 determined by the scheduling discipline. This approach
  26 has the drawback that it requires a cooperative
  27 threading model, where threads yield voluntarily
  28 on a regular basis. The application threads are
  29 responsible for doing this voluntary yielding.
  30
  31 OS-based approach
  32 -----------------
  33 This approach relies on the OS scheduler to do the
  34 actual thread dispatching. The Kokyu DSRT dispatcher manipulates
  35 the priorities of the threads. The scheduler maintains
  36 a queue (rbtree) of threads. The scheduler also has
  37 an executive thread, which runs at the maximum available
  38 priority. This thread runs in a continuous loop until
  39 the dispatcher is shut down. The executive thread is
  40 responsible for selecting the most eligible thread from
  41 the scheduler queue and bump up its priority if necessary
  42 while bumping down the priority of the currently running
  43 thread, if it is not the most eligible. There are four
  44 priority levels required for this mechanism to work,
  45 listed in descending order of priorities. For example,
  46 a thread running at Active priority will preempt a
  47 thread running at Inactive priority level.
  48
  49 1. Executive priority - priority at which the scheduler
  50    executive thread runs.
  51 2. Blocked priority - this is the priority to which
  52    threads about to block on remote calls will be bumped
  53    up to.
  54 3. Active priority - this is the priority to which
  55    the most eligible thread is set to.
  56 4. Inactive priority - this is the priority to which
  57    all threads except the most eligible thread is set
  58    to.
  59
  60 As soon as a thread asks to be scheduled, a
  61 wrapper object is created and inserted into the queue.
  62 This object carries the qos (sched params) associated
  63 with that thread. A condition variable is signalled
  64 to inform the executive thread that the queue is
  65 "dirty". The scheduler thread picks up the most
  66 eligble one and sets its priority to "active" and
  67 sets the currently running thread priority to
  68 "inactive".
  69
  70 The drawback to this approach is that it relies on
  71 the OS scheduler to dispatch the threads. Also,
  72 with the current implementation, there is only
  73 one thread running at active priority and others
  74 are all at "inactive" level. This will create
  75 undesirable effects with multi-processor systems,
  76 which could select any one of the "inactive" level
  77 threads and this could cause priority inversions.
  78
  79 How to write a new DSRT scheduler using Kokyu
  80 ---------------------------------------------
  81 One can use one of the schedulers as a starting
  82 point. The variation points are
  83
  84 1. The scheduler parameters that need to be propagated
  85    along with the service context.
  86 2. The QoS comparison function, that determines which
  87    thread is more eligible.
  88
  89 To aid (1), we have created a Svc_Ctxt_DSRT_QoS idl
  90 interface (see ./Kokyu_qos.pidl). This interface
  91 currently has the necessary things to be propagated
  92 for FP, MIF and MUF schedulers. This can be altered
  93 if necessary to accommodate new sched params. The
  94 idea here is to let the IDL compiler generate the
  95 marshalling code (including Any operators) so that
  96 these parameters can be shipped across in the
  97 service context in an encapsulated CDR.
  98
  99 To create customized QoS comparator functions, we
 100 used the idea of C++ traits to let the user define
 101 customized comparator functions. For example, the
 102 MIF scheduler uses the following traits class.
 103
 104   struct MIF_Scheduler_Traits
 105   {
 106     typedef RTScheduling::Current::IdType Guid_t;
 107
 108     struct _QoSDescriptor_t
 109     {
 110       typedef long Importance_t;
 111       Importance_t importance_;
 112     };
 113
 114     typedef _QoSDescriptor_t QoSDescriptor_t;
 115
 116     typedef Kokyu::MIF_Comparator<QoSDescriptor_t> QoSComparator_t;
 117
 118     class _Guid_Hash
 119     {
 120     public:
 121       u_long operator () (const Guid_t& id)
 122       {
 123         return ACE::hash_pjw ((const char *) id.get_buffer (),
 124                               id.length ());
 125       }
 126     };
 127
 128     typedef _Guid_Hash Guid_Hash;
 129   };
 130
 131 The idea of traits makes the Kokyu dispatcher more flexible
 132 in terms of creating new schedulers. For example, the
 133 Kokyu classes do not care about what concrete type
 134 Guid is. It could be an OctetSequence for some applications,
 135 whereas it could be an int for some others. The exact type
 136 is defined by the application (in this case, the MIF scheduler)
 137 using the traits class. In the above traits class the
 138 Guid's type is defined to be an octet sequence (indirectly).
 139 The Kokyu dispatcher expects the following typedef's to
 140 be present in the traits class:
 141
 142 Guid_t - Type of GUID.
 143 QoSDescriptor_t - aggregate for scheduler parameters
 144 QoSComparator_t - used by the scheduler queue to determine most eligible item
 145 Guid_Hash - used by the internal hash map in the scheduler to hash the guid.
 146
 147 It is also expected that the following operator be defined
 148 for comparing QoS parameters. This comparator function
 149 will be used by the scheduler queue to determine
 150 the most eligible item in the queue.
 151
 152 QoSComparator_t::operator ()(const QoSDescriptor_t& qos1,
 153             const QoSDescriptor_t& qos2)
 154
 155 Future work
 156 -----------
 157 1. It looks like there is a general structure to the
 158    different schedulers. May be this can be abstracted
 159    using templates or some similar mechanism.
 160
 161 2. Thread sched policy and sched scope are currently
 162    being passed explicitly from the application to
 163    the scheduler. This can be changed later to get
 164    this information from the ORB. This requires the
 165    usage of RTORB and the actual values can be set
 166    using svc.conf parameters for RT_ORB_Loader.
 167
 168 3. See whether the approaches could be extended
 169    to multiprocessor systems.
 170