A Discrete-Event Network Simulator
API
Loading...
Searching...
No Matches
calendar-scheduler.cc
Go to the documentation of this file.
1/*
2 * Copyright (c) 2009 INRIA
3 *
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License version 2 as
6 * published by the Free Software Foundation;
7 *
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 * GNU General Public License for more details.
12 *
13 * You should have received a copy of the GNU General Public License
14 * along with this program; if not, write to the Free Software
15 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
16 *
17 * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
18 * Author: Alexander Krotov <krotov@iitp.ru>
19 */
20
21#include "calendar-scheduler.h"
22
23#include "assert.h"
24#include "boolean.h"
25#include "event-impl.h"
26#include "log.h"
27#include "type-id.h"
28
29#include <list>
30#include <string>
31#include <utility>
32
39namespace ns3
40{
41
42NS_LOG_COMPONENT_DEFINE("CalendarScheduler");
43
44NS_OBJECT_ENSURE_REGISTERED(CalendarScheduler);
45
46TypeId
48{
49 static TypeId tid = TypeId("ns3::CalendarScheduler")
51 .SetGroupName("Core")
52 .AddConstructor<CalendarScheduler>()
53 .AddAttribute("Reverse",
54 "Store events in reverse chronological order",
56 BooleanValue(false),
59 return tid;
60}
61
63{
64 NS_LOG_FUNCTION(this);
65 Init(2, 1, 0);
66 m_qSize = 0;
67}
68
70{
71 NS_LOG_FUNCTION(this);
72 delete[] m_buckets;
73 m_buckets = nullptr;
74}
75
76void
78{
79 NS_LOG_FUNCTION(this << reverse);
80 m_reverse = reverse;
81
82 if (m_reverse)
83 {
84 NextEvent = [](Bucket& bucket) -> Scheduler::Event& { return bucket.back(); };
85 Order = [](const EventKey& a, const EventKey& b) -> bool { return a > b; };
86 Pop = [](Bucket& bucket) -> void { bucket.pop_back(); };
87 }
88 else
89 {
90 NextEvent = [](Bucket& bucket) -> Scheduler::Event& { return bucket.front(); };
91 Order = [](const EventKey& a, const EventKey& b) -> bool { return a < b; };
92 Pop = [](Bucket& bucket) -> void { bucket.pop_front(); };
93 }
94}
95
96void
97CalendarScheduler::Init(uint32_t nBuckets, uint64_t width, uint64_t startPrio)
98{
99 NS_LOG_FUNCTION(this << nBuckets << width << startPrio);
100 m_buckets = new Bucket[nBuckets];
101 m_nBuckets = nBuckets;
102 m_width = width;
103 m_lastPrio = startPrio;
104 m_lastBucket = Hash(startPrio);
105 m_bucketTop = (startPrio / width + 1) * width;
106}
107
108void
110{
111 NS_LOG_FUNCTION(this);
112
113 std::cout << "nBuckets=" << m_nBuckets << ", width=" << m_width << std::endl;
114 std::cout << "Bucket Distribution ";
115 for (uint32_t i = 0; i < m_nBuckets; i++)
116 {
117 std::cout << m_buckets[i].size() << " ";
118 }
119 std::cout << std::endl;
120}
121
123CalendarScheduler::Hash(uint64_t ts) const
124{
125 NS_LOG_FUNCTION(this);
126
127 uint32_t bucket = (ts / m_width) % m_nBuckets;
128 return bucket;
129}
130
131void
133{
134 NS_LOG_FUNCTION(this << ev.key.m_ts << ev.key.m_uid);
135 // calculate bucket index.
136 uint32_t bucket = Hash(ev.key.m_ts);
137 NS_LOG_LOGIC("insert in bucket=" << bucket);
138
139 // insert in bucket list.
140 Bucket::iterator end = m_buckets[bucket].end();
141 for (Bucket::iterator i = m_buckets[bucket].begin(); i != end; ++i)
142 {
143 if (Order(ev.key, i->key))
144 {
145 m_buckets[bucket].insert(i, ev);
146 return;
147 }
148 }
149 m_buckets[bucket].push_back(ev);
150}
151
152void
154{
155 NS_LOG_FUNCTION(this << &ev);
156 DoInsert(ev);
157 m_qSize++;
158 ResizeUp();
159}
160
161bool
163{
164 NS_LOG_FUNCTION(this);
165 return m_qSize == 0;
166}
167
170{
171 NS_LOG_FUNCTION(this);
172 NS_ASSERT(!IsEmpty());
174 uint64_t bucketTop = m_bucketTop;
175 Scheduler::Event minEvent;
176 minEvent.impl = nullptr;
177 minEvent.key.m_ts = UINT64_MAX;
178 minEvent.key.m_uid = UINT32_MAX;
179 minEvent.key.m_context = 0;
180 do
181 {
182 if (!m_buckets[i].empty())
183 {
185 if (next.key.m_ts < bucketTop)
186 {
187 return next;
188 }
189 if (next.key < minEvent.key)
190 {
191 minEvent = next;
192 }
193 }
194 i++;
195 i %= m_nBuckets;
196 bucketTop += m_width;
197 } while (i != m_lastBucket);
198
199 return minEvent;
200}
201
204{
205 NS_LOG_FUNCTION(this);
206
208 uint64_t bucketTop = m_bucketTop;
209 int32_t minBucket = -1;
210 Scheduler::EventKey minKey;
211 NS_ASSERT(!IsEmpty());
212 minKey.m_ts = uint64_t(-int64_t(1));
213 minKey.m_uid = 0;
214 minKey.m_context = 0xffffffff;
215 do
216 {
217 if (!m_buckets[i].empty())
218 {
220 if (next.key.m_ts < bucketTop)
221 {
222 m_lastBucket = i;
223 m_lastPrio = next.key.m_ts;
224 m_bucketTop = bucketTop;
225 Pop(m_buckets[i]);
226 return next;
227 }
228 if (next.key < minKey)
229 {
230 minKey = next.key;
231 minBucket = i;
232 }
233 }
234 i++;
235 i %= m_nBuckets;
236 bucketTop += m_width;
237 } while (i != m_lastBucket);
238
239 m_lastPrio = minKey.m_ts;
240 m_lastBucket = Hash(minKey.m_ts);
241 m_bucketTop = (minKey.m_ts / m_width + 1) * m_width;
242 Scheduler::Event next = NextEvent(m_buckets[minBucket]);
243 Pop(m_buckets[minBucket]);
244
245 return next;
246}
247
250{
252 NS_ASSERT(!IsEmpty());
253
255 NS_LOG_LOGIC("remove ts=" << ev.key.m_ts << ", key=" << ev.key.m_uid
256 << ", from bucket=" << m_lastBucket);
257 m_qSize--;
258 ResizeDown();
259 return ev;
260}
261
262void
264{
265 NS_LOG_FUNCTION(this << &ev);
266 NS_ASSERT(!IsEmpty());
267 // bucket index of event
268 uint32_t bucket = Hash(ev.key.m_ts);
269
270 Bucket::iterator end = m_buckets[bucket].end();
271 for (Bucket::iterator i = m_buckets[bucket].begin(); i != end; ++i)
272 {
273 if (i->key.m_uid == ev.key.m_uid)
274 {
275 NS_ASSERT(ev.impl == i->impl);
276 m_buckets[bucket].erase(i);
277
278 m_qSize--;
279 ResizeDown();
280 return;
281 }
282 }
283 NS_ASSERT(false);
284}
285
286void
288{
289 NS_LOG_FUNCTION(this);
290
291 if (m_qSize > m_nBuckets * 2 && m_nBuckets < 32768)
292 {
293 Resize(m_nBuckets * 2);
294 }
295}
296
297void
299{
300 NS_LOG_FUNCTION(this);
301
302 if (m_qSize < m_nBuckets / 2)
303 {
304 Resize(m_nBuckets / 2);
305 }
306}
307
308uint64_t
310{
311 NS_LOG_FUNCTION(this);
312
313 if (m_qSize < 2)
314 {
315 return 1;
316 }
317 uint32_t nSamples;
318 if (m_qSize <= 5)
319 {
320 nSamples = m_qSize;
321 }
322 else
323 {
324 nSamples = 5 + m_qSize / 10;
325 }
326 if (nSamples > 25)
327 {
328 nSamples = 25;
329 }
330
331 // we gather the first nSamples from the queue
332 std::list<Scheduler::Event> samples;
333 // save state
334 uint32_t lastBucket = m_lastBucket;
335 uint64_t bucketTop = m_bucketTop;
336 uint64_t lastPrio = m_lastPrio;
337
338 // gather requested events
339 for (uint32_t i = 0; i < nSamples; i++)
340 {
341 samples.push_back(DoRemoveNext());
342 }
343 // put them back
344 for (std::list<Scheduler::Event>::const_iterator i = samples.begin(); i != samples.end(); ++i)
345 {
346 DoInsert(*i);
347 }
348
349 // restore state.
350 m_lastBucket = lastBucket;
351 m_bucketTop = bucketTop;
352 m_lastPrio = lastPrio;
353
354 // finally calculate inter-time average over samples.
355 uint64_t totalSeparation = 0;
356 std::list<Scheduler::Event>::const_iterator end = samples.end();
357 std::list<Scheduler::Event>::const_iterator cur = samples.begin();
358 std::list<Scheduler::Event>::const_iterator next = cur;
359 next++;
360 while (next != end)
361 {
362 totalSeparation += next->key.m_ts - cur->key.m_ts;
363 cur++;
364 next++;
365 }
366 uint64_t twiceAvg = totalSeparation / (nSamples - 1) * 2;
367 totalSeparation = 0;
368 cur = samples.begin();
369 next = cur;
370 next++;
371 while (next != end)
372 {
373 uint64_t diff = next->key.m_ts - cur->key.m_ts;
374 if (diff <= twiceAvg)
375 {
376 totalSeparation += diff;
377 }
378 cur++;
379 next++;
380 }
381
382 totalSeparation *= 3;
383 totalSeparation = std::max(totalSeparation, (uint64_t)1);
384 return totalSeparation;
385}
386
387void
388CalendarScheduler::DoResize(uint32_t newSize, uint64_t newWidth)
389{
390 NS_LOG_FUNCTION(this << newSize << newWidth);
391
392 Bucket* oldBuckets = m_buckets;
393 uint32_t oldNBuckets = m_nBuckets;
394 Init(newSize, newWidth, m_lastPrio);
395
396 for (uint32_t i = 0; i < oldNBuckets; i++)
397 {
398 Bucket::iterator end = oldBuckets[i].end();
399 for (Bucket::iterator j = oldBuckets[i].begin(); j != end; ++j)
400 {
401 DoInsert(*j);
402 }
403 }
404 delete[] oldBuckets;
405}
406
407void
409{
410 NS_LOG_FUNCTION(this << newSize);
411
412 // PrintInfo ();
413 uint64_t newWidth = CalculateNewWidth();
414 DoResize(newSize, newWidth);
415}
416
417} // namespace ns3
NS_ASSERT() and NS_ASSERT_MSG() macro definitions.
ns3::BooleanValue attribute value declarations.
ns3::CalendarScheduler class declaration.
AttributeValue implementation for Boolean.
Definition: boolean.h:37
a calendar queue event scheduler
bool m_reverse
Bucket ordering.
uint64_t CalculateNewWidth()
Compute the new bucket size, based on up to the first 25 entries.
uint32_t m_nBuckets
Number of buckets in the array.
bool(* Order)(const EventKey &newEvent, const EventKey &it)
Ordering function to identify the insertion point, according to m_reverse.
void PrintInfo()
Print the configuration and bucket size distribution.
uint32_t m_qSize
Number of events in queue.
Scheduler::Event &(* NextEvent)(Bucket &bucket)
Get the next event from the bucket, according to m_reverse.
void Remove(const Scheduler::Event &ev) override
Remove a specific event from the event list.
void Init(uint32_t nBuckets, uint64_t width, uint64_t startPrio)
Initialize the calendar queue.
void ResizeDown()
Halve the number of buckets if necessary.
uint32_t Hash(uint64_t key) const
Hash the dimensionless time to a bucket.
void Insert(const Scheduler::Event &ev) override
Insert a new Event in the schedule.
void DoInsert(const Scheduler::Event &ev)
Insert a new event in to the correct bucket.
uint64_t m_bucketTop
Priority at the top of the bucket from which last event was dequeued.
std::list< Scheduler::Event > Bucket
Calendar bucket type: a list of Events.
~CalendarScheduler() override
Destructor.
void DoResize(uint32_t newSize, uint64_t newWidth)
Resize the number of buckets and width.
Scheduler::Event PeekNext() const override
Get a pointer to the next event.
Scheduler::Event RemoveNext() override
Remove the earliest event from the event list.
Scheduler::Event DoRemoveNext()
Remove the earliest event.
uint32_t m_lastBucket
Bucket index from which the last event was dequeued.
void SetReverse(bool reverse)
Set the insertion order.
void Resize(uint32_t newSize)
Resize to a new number of buckets, with automatically computed width.
bool IsEmpty() const override
Test if the schedule is empty.
uint64_t m_lastPrio
The priority of the last event removed.
uint64_t m_width
Duration of a bucket, in dimensionless time units.
void ResizeUp()
Double the number of buckets if necessary.
Bucket * m_buckets
Array of buckets.
void(* Pop)(Bucket &)
Pop the next event from the bucket, according to m_reverse.
static TypeId GetTypeId()
Register this type.
Maintain the event list.
Definition: scheduler.h:157
a unique identifier for an interface.
Definition: type-id.h:59
@ ATTR_CONSTRUCT
The attribute can be written at construction-time.
Definition: type-id.h:66
TypeId SetParent(TypeId tid)
Set the parent TypeId.
Definition: type-id.cc:936
ns3::EventImpl declarations.
#define NS_ASSERT(condition)
At runtime, in debugging builds, if this condition is not true, the program prints the source file,...
Definition: assert.h:66
Ptr< const AttributeAccessor > MakeBooleanAccessor(T1 a1)
Definition: boolean.h:86
Ptr< const AttributeChecker > MakeBooleanChecker()
Definition: boolean.cc:124
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition: log.h:202
#define NS_LOG_LOGIC(msg)
Use NS_LOG to output a message of level LOG_LOGIC.
Definition: log.h:282
#define NS_LOG_FUNCTION(parameters)
If log level LOG_FUNCTION is enabled, this macro will output all input parameters separated by ",...
#define NS_OBJECT_ENSURE_REGISTERED(type)
Register an Object subclass with the TypeId system.
Definition: object-base.h:46
Debug message logging.
Every class exported by the ns3 library is enclosed in the ns3 namespace.
Scheduler event.
Definition: scheduler.h:184
EventKey key
Key for sorting and ordering Events.
Definition: scheduler.h:186
EventImpl * impl
Pointer to the event implementation.
Definition: scheduler.h:185
Structure for sorting and comparing Events.
Definition: scheduler.h:170
uint32_t m_context
Event context.
Definition: scheduler.h:173
uint64_t m_ts
Event time stamp.
Definition: scheduler.h:171
uint32_t m_uid
Event unique id.
Definition: scheduler.h:172
ns3::TypeId declaration; inline and template implementations.