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