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