ACE/Kokyu/DSRT_Sched_Queue_T.h

   1 /* -*- C++ -*- */
   2 /**
   3  *  @file  DSRT_Sched_Queue_T.h
   4  *
   5  *  @author Venkita Subramonian (venkita@cs.wustl.edu)
   6  */
   7
   8 #ifndef DSRT_SCHED_QUEUE_T_H
   9 #define DSRT_SCHED_QUEUE_T_H
  10 #include /**/ "ace/pre.h"
  11
  12 #include "DSRT_Dispatch_Item_T.h"
  13 #include "ace/RB_Tree.h"
  14 #include "ace/Hash_Map_Manager_T.h"
  15 #include "ace/Null_Mutex.h"
  16
  17 #if !defined (ACE_LACKS_PRAGMA_ONCE)
  18 # pragma once
  19 #endif /* ACE_LACKS_PRAGMA_ONCE */
  20
  21 #include "Kokyu_dsrt.h"
  22
  23 namespace Kokyu
  24 {
  25   /**
  26    * @class Sched_Ready_Queue
  27    *
  28    * @brief RB_Tree based template class for implementation of
  29    * reordering queue.
  30    *
  31    * This queue is used as a priority queue to store schedulable
  32    * entities. The item at the top of the RB_Tree is the most eligible
  33    * item. The comparator used to determine the most eligible item is
  34    * passed as a template parameter <code> More_Eligible_Comparator
  35    * </code>. This is expected to be a functor which compares two
  36    * schedulable items. The mutex type template parameter for RB_Tree
  37    * is chosen to be a null mutex since all the methods in the
  38    * enclosing <code> Sched_Ready_Queue </code> class are thread
  39    * safe. Since QoS is used for comparison between two schedulable
  40    * items, QoSDescriptor is the ideal candidate to be used as the key
  41    * or the EXT_ID for RB_Tree instantiation. But two qos descriptors
  42    * could be the same. The existing implementation of RB_Tree does
  43    * not allow duplicate keys. In order to facilitate insertion of
  44    * duplicate qos descriptors, the qos descriptors are contained in a
  45    * <code> DSRT_Dispatch_Item </code> and this is used as the basis
  46    * of comparison. To resolve tie between equal qos values, an
  47    * insertion time stamp is maintained in each item and an item with
  48    * an earlier time stamp is more eligible than an item with an
  49    * identical qos value. Another requirement is that it should be
  50    * possible to remove an item from the RB_Tree based on guid. Since
  51    * we have already used up the qos descriptor for the key, we need a
  52    * separate index into the list of schedulable items. The second
  53    * index should be based on guid. This is achieved by using a hash
  54    * map to store <guid, RB_Tree_Node*> pairs. This makes the deletion
  55    * of nodes from RB_Tree more efficient.
  56    *
  57    */
  58   template <class DSRT_Scheduler_Traits,
  59             class More_Eligible_Comparator,
  60             class ACE_LOCK>
  61   class Sched_Ready_Queue
  62   {
  63     /// Extract the necessary types from the traits class
  64     typedef typename DSRT_Scheduler_Traits::Guid_t Guid_t;
  65
  66     typedef typename
  67     DSRT_Scheduler_Traits::QoSDescriptor_t DSRT_QoSDescriptor_t;
  68
  69   public:
  70     /**
  71      * Given a guid, find an item in the priority queue.
  72      *
  73      * @param guid Guid of item
  74      *
  75      * @param found_item Reference to DSRT_Dispatch_Item_var
  76      *                   to hold the found item.
  77      * @return  -1 if no item found and 0 otherwise.
  78      */
  79     int find(Guid_t guid,
  80              DSRT_Dispatch_Item_var<DSRT_Scheduler_Traits>&
  81              found_item);
  82
  83
  84     /**
  85      * Insert an item in the priority queue. If item with same guid is
  86      * already in the queue, the existing one is deleted and the new
  87      * one inserted. A deletion and insertion has to happen instead of
  88      * update since the rebalancing of the RB_Tree should take place.
  89      *
  90      * @param item <code> DSRT_Dispatch_Item </code> object containing guid and qos.
  91      *
  92      * @return -1 if insertion failed and 0 otherwise.
  93      */
  94     int insert(DSRT_Dispatch_Item<DSRT_Scheduler_Traits>* item);
  95
  96     /**
  97      * Remove an item from the priority queue.
  98      *
  99      * @param guid Guid of item.
 100      *
 101      * @param qos QoS associated with item.
 102      *
 103      * @return -1 if removal failed and 0 otherwise.
 104      */
 105     int remove(Guid_t guid);
 106
 107     /**
 108      * Returns current size of the priority queue.
 109      */
 110     int current_size ();
 111
 112     /**
 113      * Get the most eligible item from the priority queue.
 114      *
 115      * @param item Item which is most eligible, i.e. one at the
 116      *             "top" of the priority queue.
 117      *
 118      * @return -1 if there are no items in the priority queue.
 119      */
 120     int most_eligible (DSRT_Dispatch_Item_var<DSRT_Scheduler_Traits>&
 121                        item);
 122
 123     /**
 124      * change blocked_prio_ item to inactive_prio_
 125      */
 126     int change_prio (int old_prio, int new_prio, int policy);
 127
 128     void dump();
 129
 130   private:
 131     /**
 132      * @class Guid_Hash
 133      *
 134      * @brief Internal class to generate hash for guid.
 135      *
 136      * This acts just as a wrapper functor to the Hash functor passed
 137      * as part of the traits class <code> DSRT_Scheduler_Traits
 138      * </code>.
 139      *
 140      */
 141     class Guid_Hash
 142     {
 143     public:
 144       /// Returns hash value.
 145       u_long operator () (const typename DSRT_Scheduler_Traits::Guid_t &id)
 146       {
 147         typename DSRT_Scheduler_Traits::Guid_Hash guid_hash;
 148         return guid_hash(id);
 149       }
 150     };
 151
 152     // RB_Tree related typedefs
 153     typedef ACE_RB_Tree <DSRT_Dispatch_Item_var<DSRT_Scheduler_Traits>,
 154                          DSRT_Dispatch_Item_var<DSRT_Scheduler_Traits>,
 155                          More_Eligible_Comparator,
 156                          ACE_SYNCH_NULL_MUTEX> Dispatch_Items_Priority_Queue;
 157
 158
 159     typedef
 160     ACE_RB_Tree_Node<DSRT_Dispatch_Item_var<DSRT_Scheduler_Traits>,
 161                      DSRT_Dispatch_Item_var<DSRT_Scheduler_Traits> >
 162     RB_Tree_Dispatch_Item_Node;
 163
 164     typedef typename
 165     Dispatch_Items_Priority_Queue::ITERATOR PRIO_QUEUE_ITERATOR;
 166
 167     typedef typename
 168     Dispatch_Items_Priority_Queue::ENTRY PRIO_QUEUE_ENTRY;
 169
 170     // Hash map related typedefs
 171     typedef ACE_Hash_Map_Manager_Ex<Guid_t,
 172                                     RB_Tree_Dispatch_Item_Node*,
 173                                     Guid_Hash,
 174                                     ACE_Equal_To<Guid_t>,
 175                                     ACE_SYNCH_NULL_MUTEX>
 176     Dispatch_Items_Hash_Map;
 177
 178     typedef ACE_Hash_Map_Iterator_Ex<Guid_t,
 179                                      RB_Tree_Dispatch_Item_Node*,
 180                                      Guid_Hash,
 181                                      ACE_Equal_To<Guid_t>,
 182                                      ACE_SYNCH_NULL_MUTEX>
 183     Dispatch_Items_Hash_Map_Iterator;
 184
 185     typedef ACE_Hash_Map_Entry <Guid_t,
 186                                 RB_Tree_Dispatch_Item_Node*>
 187     Dispatch_Items_Hash_Map_Entry;
 188
 189     /**
 190      * Lock used to protect the state of the scheduler queue. A
 191      * separate lock is not used for the internal RB_Tree and hashmap.
 192      */
 193     ACE_LOCK lock_;
 194
 195     /**
 196      * Hash table to maintain a second index into the list of
 197      * schedulable items. This is for efficient removal of items from
 198      * the RB_Tree based on guid. The guid is used as the key for the
 199      * hash map, whereas the qos value is used as the key for the
 200      * RB_Tree.
 201      */
 202     Dispatch_Items_Hash_Map dispatch_items_hash_map_;
 203
 204     /**
 205      * RB_Tree implementation of priority queue of schedulable items.
 206      */
 207     Dispatch_Items_Priority_Queue dispatch_items_prio_queue_;
 208   };
 209 }
 210
 211 #include "DSRT_Sched_Queue_T.cpp"
 212
 213 #include /**/ "ace/post.h"
 214 #endif /* DSRT_SCHED_QUEUE_T_H */