A Discrete-Event Network Simulator
API
Loading...
Searching...
No Matches
scheduler.h
Go to the documentation of this file.
1/*
2 * Copyright (c) 2005 INRIA
3 *
4 * SPDX-License-Identifier: GPL-2.0-only
5 *
6 * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
7 */
8
9#ifndef SCHEDULER_H
10#define SCHEDULER_H
11
12#include "object.h"
13
14#include <stdint.h>
15
16/**
17 * \file
18 * \ingroup scheduler
19 * \ingroup events
20 * ns3::Scheduler abstract base class, ns3::Scheduler::Event and
21 * ns3::Scheduler::EventKey declarations.
22 */
23
24namespace ns3
25{
26
27class EventImpl;
28
29/**
30 * \ingroup core
31 * \defgroup scheduler Scheduler and Events
32 * \brief Manage the event list by creating and scheduling events.
33 */
34/**
35 * \ingroup scheduler
36 * \defgroup events Events
37 */
38/**
39 * \ingroup scheduler
40 * \brief Maintain the event list
41 *
42 *
43 * In ns-3 the Scheduler manages the future event list. There are several
44 * different Scheduler implementations with different time and space tradeoffs.
45 * Which one is "best" depends in part on the characteristics
46 * of the model being executed. For optimized production work common
47 * practice is to benchmark each Scheduler on the model of interest.
48 * The utility program utils/bench-scheduler.cc can do simple benchmarking
49 * of each SchedulerImpl against an exponential or user-provided
50 * event time distribution.
51 *
52 * The most important Scheduler functions for time performance are (usually)
53 * Scheduler::Insert (for new events) and Scheduler::RemoveNext (for pulling
54 * off the next event to execute). Simulator::Cancel is usually
55 * implemented by simply setting a bit on the Event, but leaving it in the
56 * Scheduler; the Simulator just skips those events as they are encountered.
57 *
58 * For models which need a large event list the Scheduler overhead
59 * and per-event memory cost could also be important. Some models
60 * rely heavily on Scheduler::Cancel, however, and these might benefit
61 * from using Scheduler::Remove instead, to reduce the size of the event
62 * list, at the time cost of actually removing events from the list.
63 *
64 * A summary of the main characteristics
65 * of each SchedulerImpl is provided below. See the individual
66 * Scheduler pages for details on the complexity of the other API calls.
67 * (Memory overheads assume pointers and `std::size_t` are both 8 bytes.)
68 *
69 * <table class="markdownTable">
70 * <tr class="markdownTableHead">
71 * <th class="markdownTableHeadCenter" colspan="2"> %Scheduler Type </th>
72 * <th class="markdownTableHeadCenter" colspan="4">Complexity</th>
73 * </tr>
74 * <tr class="markdownTableHead">
75 * <th class="markdownTableHeadLeft" rowspan="2"> %SchedulerImpl </th>
76 * <th class="markdownTableHeadLeft" rowspan="2"> Method </th>
77 * <th class="markdownTableHeadCenter" colspan="2"> %Time </th>
78 * <th class="markdownTableHeadCenter" colspan="2"> Space</th>
79 * </tr>
80 * <tr class="markdownTableHead">
81 * <th class="markdownTableHeadLeft"> %Insert()</th>
82 * <th class="markdownTableHeadLeft"> %RemoveNext()</th>
83 * <th class="markdownTableHeadLeft"> Overhead</th>
84 * <th class="markdownTableHeadLeft"> Per %Event</th>
85 * </tr>
86 * <tr class="markdownTableBody">
87 * <td class="markdownTableBodyLeft"> CalendarScheduler </td>
88 * <td class="markdownTableBodyLeft"> `<std::list> []` </td>
89 * <td class="markdownTableBodyLeft"> Constant </td>
90 * <td class="markdownTableBodyLeft"> Constant </td>
91 * <td class="markdownTableBodyLeft"> 24 bytes </td>
92 * <td class="markdownTableBodyLeft"> 16 bytes </td>
93 * </tr>
94 * <tr class="markdownTableBody">
95 * <td class="markdownTableBodyLeft"> HeapScheduler </td>
96 * <td class="markdownTableBodyLeft"> Heap on `std::vector` </td>
97 * <td class="markdownTableBodyLeft"> Logarithmic </td>
98 * <td class="markdownTableBodyLeft"> Logarithmic </td>
99 * <td class="markdownTableBodyLeft"> 24 bytes </td>
100 * <td class="markdownTableBodyLeft"> 0 </td>
101 * </tr>
102 * <tr class="markdownTableBody">
103 * <td class="markdownTableBodyLeft"> ListScheduler </td>
104 * <td class="markdownTableBodyLeft"> `std::list` </td>
105 * <td class="markdownTableBodyLeft"> Linear </td>
106 * <td class="markdownTableBodyLeft"> Constant </td>
107 * <td class="markdownTableBodyLeft"> 24 bytes </td>
108 * <td class="markdownTableBodyLeft"> 16 bytes </td>
109 * </tr>
110 * <tr class="markdownTableBody">
111 * <td class="markdownTableBodyLeft"> MapScheduler </td>
112 * <td class="markdownTableBodyLeft"> `std::map` </td>
113 * <td class="markdownTableBodyLeft"> Logarithmic </td>
114 * <td class="markdownTableBodyLeft"> Constant </td>
115 * <td class="markdownTableBodyLeft"> 40 bytes </td>
116 * <td class="markdownTableBodyLeft"> 32 bytes </td>
117 * </tr>
118 * <tr class="markdownTableBody">
119 * <td class="markdownTableBodyLeft"> PriorityQueueScheduler </td>
120 * <td class="markdownTableBodyLeft"> `std::priority_queue<,std::vector>` </td>
121 * <td class="markdownTableBodyLeft"> Logarithmic </td>
122 * <td class="markdownTableBodyLeft"> Logarithmic </td>
123 * <td class="markdownTableBodyLeft"> 24 bytes </td>
124 * <td class="markdownTableBodyLeft"> 0 </td>
125 * </tr>
126 * </table>
127 *
128 * It is possible to change the Scheduler choice during a simulation,
129 * via Simulator::SetScheduler.
130 *
131 * The Scheduler base class specifies the interface used to maintain the
132 * event list. If you want to provide a new event list scheduler,
133 * you need to create a subclass of this base class and implement
134 * all the pure virtual methods defined here.
135 *
136 * The only tricky aspect of this API is the memory management of
137 * the EventImpl pointer which is a member of the Event data structure.
138 * The lifetime of this pointer is assumed to always be longer than
139 * the lifetime of the Scheduler class which means that the caller
140 * is responsible for ensuring that this invariant holds through
141 * calling EventId::Ref and SimpleRefCount::Unref at the right time.
142 * Typically, EventId::Ref is called before Insert and SimpleRefCount::Unref is called
143 * after a call to one of the Remove methods.
144 */
145class Scheduler : public Object
146{
147 public:
148 /**
149 * Register this type.
150 * \return The object TypeId.
151 */
152 static TypeId GetTypeId();
153
154 /**
155 * \ingroup events
156 * Structure for sorting and comparing Events.
157 */
158 struct EventKey
159 {
160 uint64_t m_ts; /**< Event time stamp. */
161 uint32_t m_uid; /**< Event unique id. */
162 uint32_t m_context; /**< Event context. */
163 };
164
165 /**
166 * \ingroup events
167 * Scheduler event.
168 *
169 * An Event consists of an EventKey, used for maintaining the schedule,
170 * and an EventImpl which is the actual implementation.
171 */
172 struct Event
173 {
174 EventImpl* impl; /**< Pointer to the event implementation. */
175 EventKey key; /**< Key for sorting and ordering Events. */
176 };
177
178 /** Destructor. */
179 ~Scheduler() override = 0;
180
181 /**
182 * Insert a new Event in the schedule.
183 *
184 * \param [in] ev Event to store in the event list
185 */
186 virtual void Insert(const Event& ev) = 0;
187 /**
188 * Test if the schedule is empty.
189 *
190 * \returns \c true if the event list is empty and \c false otherwise.
191 */
192 virtual bool IsEmpty() const = 0;
193 /**
194 * Get a pointer to the next event.
195 *
196 * This method cannot be invoked if the list is empty.
197 *
198 * \returns A pointer to the next earliest event. The caller
199 * takes ownership of the returned pointer.
200 */
201 virtual Event PeekNext() const = 0;
202 /**
203 * Remove the earliest event from the event list.
204 *
205 * This method cannot be invoked if the list is empty.
206 *
207 * \return The Event.
208 */
209 virtual Event RemoveNext() = 0;
210 /**
211 * Remove a specific event from the event list.
212 *
213 * This method cannot be invoked if the list is empty.
214 *
215 * \param [in] ev The event to remove
216 */
217 virtual void Remove(const Event& ev) = 0;
218};
219
220/**
221 * \ingroup events
222 * Compare (equal) two events by EventKey.
223 *
224 * \param [in] a The first event.
225 * \param [in] b The second event.
226 * \returns \c true if \c a != \c b
227 */
228inline bool
230{
231 return a.m_uid == b.m_uid;
232}
233
234/**
235 * \ingroup events
236 * Compare (not equal) two events by EventKey.
237 *
238 * \param [in] a The first event.
239 * \param [in] b The second event.
240 * \returns \c true if \c a != \c b
241 */
242inline bool
244{
245 return a.m_uid != b.m_uid;
246}
247
248/**
249 * \ingroup events
250 * Compare (less than) two events by EventKey.
251 *
252 * Note the invariants which this function must provide:
253 * - irreflexibility: f (x,x) is false
254 * - antisymmetry: f(x,y) = !f(y,x)
255 * - transitivity: f(x,y) and f(y,z) => f(x,z)
256 *
257 * \param [in] a The first event.
258 * \param [in] b The second event.
259 * \returns \c true if \c a < \c b
260 */
261inline bool
263{
264 return (a.m_ts < b.m_ts || (a.m_ts == b.m_ts && a.m_uid < b.m_uid));
265}
266
267/**
268 * Compare (greater than) two events by EventKey.
269 *
270 * \param [in] a The first event.
271 * \param [in] b The second event.
272 * \returns \c true if \c a > \c b
273 */
274inline bool
276{
277 return (a.m_ts > b.m_ts || (a.m_ts == b.m_ts && a.m_uid > b.m_uid));
278}
279
280/**
281 * Compare (equal) two events by Event.
282 *
283 * \param [in] a The first event.
284 * \param [in] b The second event.
285 * \returns \c true if \c a == \c b
286 */
287inline bool
289{
290 return a.key == b.key;
291}
292
293/**
294 * Compare (not equal) two events by Event.
295 *
296 * \param [in] a The first event.
297 * \param [in] b The second event.
298 * \returns \c true if \c a != \c b
299 */
300inline bool
302{
303 return a.key != b.key;
304}
305
306/**
307 * Compare (less than) two events by Event.
308 *
309 * \param [in] a The first event.
310 * \param [in] b The second event.
311 * \returns \c true if \c a < \c b
312 */
313inline bool
315{
316 return a.key < b.key;
317}
318
319/**
320 * Compare (greater than) two events by Event.
321 *
322 * \param [in] a The first event.
323 * \param [in] b The second event.
324 * \returns \c true if \c a > \c b
325 */
326inline bool
328{
329 return a.key > b.key;
330}
331
332} // namespace ns3
333
334#endif /* SCHEDULER_H */
A simulation event.
Definition event-impl.h:35
A base class which provides memory management and object aggregation.
Definition object.h:78
Maintain the event list.
Definition scheduler.h:146
~Scheduler() override=0
Destructor.
Definition scheduler.cc:27
virtual bool IsEmpty() const =0
Test if the schedule is empty.
static TypeId GetTypeId()
Register this type.
Definition scheduler.cc:33
virtual void Remove(const Event &ev)=0
Remove a specific event from the event list.
virtual Event PeekNext() const =0
Get a pointer to the next event.
virtual void Insert(const Event &ev)=0
Insert a new Event in the schedule.
virtual Event RemoveNext()=0
Remove the earliest event from the event list.
a unique identifier for an interface.
Definition type-id.h:48
bool operator>(const Length &left, const Length &right)
Check if left has a value greater than right.
Definition length.cc:410
Every class exported by the ns3 library is enclosed in the ns3 namespace.
bool operator!=(Callback< R, Args... > a, Callback< R, Args... > b)
Inequality test.
Definition callback.h:658
bool operator==(const EventId &a, const EventId &b)
Definition event-id.h:155
bool operator<(const EventId &a, const EventId &b)
Definition event-id.h:168
ns3::Object class declaration, which is the root of the Object hierarchy and Aggregation.
Scheduler event.
Definition scheduler.h:173
EventKey key
Key for sorting and ordering Events.
Definition scheduler.h:175
EventImpl * impl
Pointer to the event implementation.
Definition scheduler.h:174
Structure for sorting and comparing Events.
Definition scheduler.h:159
uint32_t m_context
Event context.
Definition scheduler.h:162
uint64_t m_ts
Event time stamp.
Definition scheduler.h:160
uint32_t m_uid
Event unique id.
Definition scheduler.h:161