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