A Discrete-Event Network Simulator
Home
Tutorials ▼
English
Documentation ▼
Installation
Manual
Models
Contributing
Wiki
Development ▼
API Docs
Issue Tracker
Merge Requests
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
24
namespace
ns3
25
{
26
27
class
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
*/
145
class
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
*/
228
inline
bool
229
operator==
(
const
Scheduler::EventKey
& a,
const
Scheduler::EventKey
& b)
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
*/
242
inline
bool
243
operator!=
(
const
Scheduler::EventKey
& a,
const
Scheduler::EventKey
& b)
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
*/
261
inline
bool
262
operator<
(
const
Scheduler::EventKey
& a,
const
Scheduler::EventKey
& b)
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
*/
274
inline
bool
275
operator>
(
const
Scheduler::EventKey
& a,
const
Scheduler::EventKey
& b)
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
*/
287
inline
bool
288
operator==
(
const
Scheduler::Event
& a,
const
Scheduler::Event
& b)
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
*/
300
inline
bool
301
operator!=
(
const
Scheduler::Event
& a,
const
Scheduler::Event
& b)
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
*/
313
inline
bool
314
operator<
(
const
Scheduler::Event
& a,
const
Scheduler::Event
& b)
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
*/
326
inline
bool
327
operator>
(
const
Scheduler::Event
& a,
const
Scheduler::Event
& b)
328
{
329
return
a.
key
> b.
key
;
330
}
331
332
}
// namespace ns3
333
334
#endif
/* SCHEDULER_H */
ns3::EventImpl
A simulation event.
Definition
event-impl.h:35
ns3::Object
A base class which provides memory management and object aggregation.
Definition
object.h:78
ns3::Scheduler
Maintain the event list.
Definition
scheduler.h:146
ns3::Scheduler::~Scheduler
~Scheduler() override=0
Destructor.
Definition
scheduler.cc:27
ns3::Scheduler::IsEmpty
virtual bool IsEmpty() const =0
Test if the schedule is empty.
ns3::Scheduler::GetTypeId
static TypeId GetTypeId()
Register this type.
Definition
scheduler.cc:33
ns3::Scheduler::Remove
virtual void Remove(const Event &ev)=0
Remove a specific event from the event list.
ns3::Scheduler::PeekNext
virtual Event PeekNext() const =0
Get a pointer to the next event.
ns3::Scheduler::Insert
virtual void Insert(const Event &ev)=0
Insert a new Event in the schedule.
ns3::Scheduler::RemoveNext
virtual Event RemoveNext()=0
Remove the earliest event from the event list.
ns3::TypeId
a unique identifier for an interface.
Definition
type-id.h:48
uint32_t
ns3::operator>
bool operator>(const Length &left, const Length &right)
Check if left has a value greater than right.
Definition
length.cc:410
ns3
Every class exported by the ns3 library is enclosed in the ns3 namespace.
ns3::operator!=
bool operator!=(Callback< R, Args... > a, Callback< R, Args... > b)
Inequality test.
Definition
callback.h:658
ns3::operator==
bool operator==(const EventId &a, const EventId &b)
Definition
event-id.h:155
ns3::operator<
bool operator<(const EventId &a, const EventId &b)
Definition
event-id.h:168
object.h
ns3::Object class declaration, which is the root of the Object hierarchy and Aggregation.
ns3::Scheduler::Event
Scheduler event.
Definition
scheduler.h:173
ns3::Scheduler::Event::key
EventKey key
Key for sorting and ordering Events.
Definition
scheduler.h:175
ns3::Scheduler::Event::impl
EventImpl * impl
Pointer to the event implementation.
Definition
scheduler.h:174
ns3::Scheduler::EventKey
Structure for sorting and comparing Events.
Definition
scheduler.h:159
ns3::Scheduler::EventKey::m_context
uint32_t m_context
Event context.
Definition
scheduler.h:162
ns3::Scheduler::EventKey::m_ts
uint64_t m_ts
Event time stamp.
Definition
scheduler.h:160
ns3::Scheduler::EventKey::m_uid
uint32_t m_uid
Event unique id.
Definition
scheduler.h:161
src
core
model
scheduler.h
Generated on Fri Nov 8 2024 13:58:59 for ns-3 by
1.11.0