A Discrete-Event Network Simulator
API
Loading...
Searching...
No Matches
calendar-scheduler.h
Go to the documentation of this file.
1/*
2 * Copyright (c) 2009 INRIA
3 *
4 * SPDX-License-Identifier: GPL-2.0-only
5 *
6 * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
7 * Author: Alexander Krotov <krotov@iitp.ru>
8 */
9
10#ifndef CALENDAR_SCHEDULER_H
11#define CALENDAR_SCHEDULER_H
12
13#include "scheduler.h"
14
15#include <list>
16#include <stdint.h>
17
18/**
19 * \file
20 * \ingroup scheduler
21 * ns3::CalendarScheduler class declaration.
22 */
23
24namespace ns3
25{
26
27class EventImpl;
28
29/**
30 * \ingroup scheduler
31 * \brief a calendar queue event scheduler
32 *
33 * This event scheduler is a direct implementation of the algorithm
34 * known as a calendar queue, first published in 1988 in
35 * ["Calendar Queues: A Fast O(1) Priority Queue Implementation for
36 * the Simulation Event Set Problem" by Randy Brown][Brown]. There are many
37 * refinements published later but this class implements
38 * the original algorithm (to the best of my knowledge).
39 *
40 * [Brown]: https://doi.org/10.1145/63039.63045 "Brown"
41 *
42 * This class uses a vector of buckets; each bucket covers a uniform
43 * time span. The bucket index for an event with timestamp `ts` is
44 * `(ts / m_width) % m_nBuckets`. This class automatically adjusts
45 * the number of buckets to keep the average occupancy around 2.
46 * Buckets themselves are implemented as a `std::list<>`, and events are
47 * kept sorted within the buckets.
48 *
49 * \par Time Complexity
50 *
51 * Operation | Amortized %Time | Reason
52 * :----------- | :-------------- | :-----
53 * Insert() | ~Constant | Ordering within bucket; possible resize
54 * IsEmpty() | Constant | Explicit queue size
55 * PeekNext() | ~Constant | Search buckets
56 * Remove() | ~Constant | Search within bucket; possible resize
57 * RemoveNext() | ~Constant | Search buckets; possible resize
58 *
59 * \par Memory Complexity
60 *
61 * Category | Memory | Reason
62 * :-------- | :------------------------------- | :-----
63 * Overhead | 2 x `sizeof (*)` + `size_t`<br/>(24 bytes) | `std::list`
64 * Per Event | 2 x `sizeof (*)` | `std::list`
65 *
66 * \note
67 * This queue is much slower than I expected (much slower than the
68 * std::map queue) and this seems to be because the original resizing policy
69 * is horribly bad. This is most likely the reason why there have been
70 * so many variations published which all slightly tweak the resizing
71 * heuristics to obtain a better distribution of events across buckets.
72 *
73 * \note While inserion sort is not discussed in the original article, its
74 * implementation appears to dramatically affect performance.
75 * The default implementation sorts buckets in increasing (chronological)
76 * order. The alternative, sorting buckets in decreasing order,
77 * was adopted in NS-2 because they observed that new events were
78 * more likely to be later than already scheduled events.
79 * In this case sorting buckets in reverse chronological order
80 * reduces enqueue time.
81 */
83{
84 public:
85 /**
86 * Register this type.
87 * \return The object TypeId.
88 */
89 static TypeId GetTypeId();
90
91 /** Constructor. */
93 /** Destructor. */
94 ~CalendarScheduler() override;
95
96 // Inherited
97 void Insert(const Scheduler::Event& ev) override;
98 bool IsEmpty() const override;
99 Scheduler::Event PeekNext() const override;
100 Scheduler::Event RemoveNext() override;
101 void Remove(const Scheduler::Event& ev) override;
102
103 private:
104 /** Double the number of buckets if necessary. */
105 void ResizeUp();
106 /** Halve the number of buckets if necessary. */
107 void ResizeDown();
108 /**
109 * Resize to a new number of buckets, with automatically computed width.
110 *
111 * \param [in] newSize The new number of buckets.
112 */
113 void Resize(uint32_t newSize);
114 /**
115 * Compute the new bucket size, based on up to the first 25 entries.
116 *
117 * \returns The new width.
118 */
119 uint64_t CalculateNewWidth();
120 /**
121 * Initialize the calendar queue.
122 *
123 * \param [in] nBuckets The number of buckets.
124 * \param [in] width The bucket size, in dimensionless time units.
125 * \param [in] startPrio The starting time.
126 */
127 void Init(uint32_t nBuckets, uint64_t width, uint64_t startPrio);
128 /**
129 * Hash the dimensionless time to a bucket.
130 *
131 * \param [in] key The dimensionless time.
132 * \returns The bucket index.
133 */
134 inline uint32_t Hash(uint64_t key) const;
135 /** Print the configuration and bucket size distribution. */
136 void PrintInfo();
137 /**
138 * Resize the number of buckets and width.
139 *
140 * \param [in] newSize The number of buckets.
141 * \param [in] newWidth The size of the new buckets.
142 */
143 void DoResize(uint32_t newSize, uint64_t newWidth);
144 /**
145 * Remove the earliest event.
146 *
147 * \returns The earliest event.
148 */
150 /**
151 * Insert a new event in to the correct bucket.
152 *
153 * \param [in] ev The new Event.
154 */
155 void DoInsert(const Scheduler::Event& ev);
156
157 /** Calendar bucket type: a list of Events. */
158 typedef std::list<Scheduler::Event> Bucket;
159
160 /** Array of buckets. */
162 /** Number of buckets in the array. */
164 /** Duration of a bucket, in dimensionless time units. */
165 uint64_t m_width;
166 /** Bucket index from which the last event was dequeued. */
168 /** Priority at the top of the bucket from which last event was dequeued. */
169 uint64_t m_bucketTop;
170 /** The priority of the last event removed. */
171 uint64_t m_lastPrio;
172 /** Number of events in queue. */
174
175 /**
176 * Set the insertion order.
177 *
178 * This can only be used at construction, as invoked by the
179 * Attribute Reverse.
180 *
181 * \param [in] reverse If \c true, store events in *decreasing*
182 * time stamp order.
183 */
184 void SetReverse(bool reverse);
185 /**
186 * Get the next event from the bucket, according to \c m_reverse.
187 * \param [in] bucket The bucket to draw from.
188 * \return The next event from the \c bucket.
189 */
190 Scheduler::Event& (*NextEvent)(Bucket& bucket);
191 /**
192 * Ordering function to identify the insertion point, according to \c m_reverse.
193 * \param [in] newEvent The new event being inserted.
194 * \param [in] it The current position in the bucket being examined.
195 * \return \c true if the \c newEvent belongs before \c it.
196 */
197 bool (*Order)(const EventKey& newEvent, const EventKey& it);
198 /**
199 * Pop the next event from the bucket, according to \c m_reverse.
200 * \param [in] bucket The bucket to pop from.
201 */
202 void (*Pop)(Bucket&);
203 /**
204 * Bucket ordering.
205 * If \c false (default), store events in increasing time stamp order.
206 * If \c true, store events in *decreasing* time stamp order.
207 */
208 bool m_reverse = false;
209};
210
211} // namespace ns3
212
213#endif /* CALENDAR_SCHEDULER_H */
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.
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:146
a unique identifier for an interface.
Definition type-id.h:48
Every class exported by the ns3 library is enclosed in the ns3 namespace.
ns3::Scheduler abstract base class, ns3::Scheduler::Event and ns3::Scheduler::EventKey declarations.
Scheduler event.
Definition scheduler.h:173
Structure for sorting and comparing Events.
Definition scheduler.h:159