A Discrete-Event Network Simulator
Home
Tutorials ▼
English
Portuguese
Docs ▼
Wiki
Manual
Models
Develop ▼
API
Bugs
API
Main Page
Related Pages
Modules
Namespaces
Classes
Files
File List
File Members
All
Classes
Namespaces
Files
Functions
Variables
Typedefs
Enumerations
Enumerator
Properties
Friends
Macros
Groups
Pages
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
29
namespace
ns3 {
30
31
NS_LOG_COMPONENT_DEFINE
(
"CalendarScheduler"
);
32
33
NS_OBJECT_ENSURE_REGISTERED
(CalendarScheduler);
34
35
TypeId
36
CalendarScheduler::GetTypeId
(
void
)
37
{
38
static
TypeId
tid =
TypeId
(
"ns3::CalendarScheduler"
)
39
.
SetParent
<
Scheduler
> ()
40
.AddConstructor<CalendarScheduler> ()
41
;
42
return
tid;
43
}
44
45
CalendarScheduler::CalendarScheduler
()
46
{
47
NS_LOG_FUNCTION
(
this
);
48
Init
(2, 1, 0);
49
m_qSize
= 0;
50
}
51
CalendarScheduler::~CalendarScheduler
()
52
{
53
NS_LOG_FUNCTION
(
this
);
54
delete
[]
m_buckets
;
55
m_buckets
= 0;
56
}
57
void
58
CalendarScheduler::Init
(uint32_t nBuckets,
59
uint64_t width,
60
uint64_t startPrio)
61
{
62
NS_LOG_FUNCTION
(
this
<< nBuckets << width << startPrio);
63
m_buckets
=
new
Bucket
[nBuckets];
64
m_nBuckets
= nBuckets;
65
m_width
= width;
66
m_lastPrio
= startPrio;
67
m_lastBucket
=
Hash
(startPrio);
68
m_bucketTop
= (startPrio / width + 1) * width;
69
}
70
void
71
CalendarScheduler::PrintInfo
(
void
)
72
{
73
NS_LOG_FUNCTION
(
this
);
74
75
std::cout <<
"nBuckets="
<<
m_nBuckets
<<
", width="
<<
m_width
<< std::endl;
76
std::cout <<
"Bucket Distribution "
;
77
for
(uint32_t i = 0; i <
m_nBuckets
; i++)
78
{
79
std::cout <<
m_buckets
[i].size () <<
" "
;
80
}
81
std::cout << std::endl;
82
}
83
uint32_t
84
CalendarScheduler::Hash
(uint64_t ts)
const
85
{
86
NS_LOG_FUNCTION
(
this
);
87
88
uint32_t bucket = (ts /
m_width
) %
m_nBuckets
;
89
return
bucket;
90
}
91
92
void
93
CalendarScheduler::DoInsert
(
const
Event
&ev)
94
{
95
NS_LOG_FUNCTION
(
this
<< ev.
key
.
m_ts
<< ev.
key
.
m_uid
);
96
// calculate bucket index.
97
uint32_t bucket =
Hash
(ev.
key
.
m_ts
);
98
NS_LOG_LOGIC
(
"insert in bucket="
<< bucket);
99
100
// insert in bucket list.
101
Bucket::iterator end =
m_buckets
[bucket].end ();
102
for
(Bucket::iterator i =
m_buckets
[bucket].begin (); i != end; ++i)
103
{
104
if
(ev.
key
< i->key)
105
{
106
m_buckets
[bucket].insert (i, ev);
107
return
;
108
}
109
}
110
m_buckets
[bucket].push_back (ev);
111
}
112
113
void
114
CalendarScheduler::Insert
(
const
Event
&ev)
115
{
116
NS_LOG_FUNCTION
(
this
<< &ev);
117
DoInsert
(ev);
118
m_qSize
++;
119
ResizeUp
();
120
}
121
bool
122
CalendarScheduler::IsEmpty
(
void
)
const
123
{
124
NS_LOG_FUNCTION
(
this
);
125
return
m_qSize
== 0;
126
}
127
Scheduler::Event
128
CalendarScheduler::PeekNext
(
void
)
const
129
{
130
NS_LOG_FUNCTION
(
this
);
131
NS_ASSERT
(!
IsEmpty
());
132
uint32_t i =
m_lastBucket
;
133
uint64_t bucketTop =
m_bucketTop
;
134
Scheduler::Event
minEvent;
135
minEvent.
impl
= 0;
136
minEvent.
key
.
m_ts
= ~0;
137
minEvent.
key
.
m_uid
= ~0;
138
minEvent.
key
.
m_context
= 0;
139
do
140
{
141
if
(!
m_buckets
[i].
empty
())
142
{
143
Scheduler::Event
next =
m_buckets
[i].front ();
144
if
(next.
key
.
m_ts
< bucketTop)
145
{
146
return
next;
147
}
148
if
(next.
key
< minEvent.
key
)
149
{
150
minEvent = next;
151
}
152
}
153
i++;
154
i %=
m_nBuckets
;
155
bucketTop +=
m_width
;
156
}
157
while
(i !=
m_lastBucket
);
158
159
return
minEvent;
160
}
161
162
Scheduler::Event
163
CalendarScheduler::DoRemoveNext
(
void
)
164
{
165
NS_LOG_FUNCTION
(
this
);
166
167
uint32_t i =
m_lastBucket
;
168
uint64_t bucketTop =
m_bucketTop
;
169
int32_t minBucket = -1;
170
Scheduler::EventKey
minKey;
171
NS_ASSERT
(!
IsEmpty
());
172
minKey.
m_ts
= uint64_t(-int64_t(1));
173
minKey.
m_uid
= 0;
174
minKey.
m_context
= 0xffffffff;
175
do
176
{
177
if
(!
m_buckets
[i].
empty
())
178
{
179
Scheduler::Event
next =
m_buckets
[i].front ();
180
if
(next.
key
.
m_ts
< bucketTop)
181
{
182
m_lastBucket
= i;
183
m_lastPrio
= next.
key
.
m_ts
;
184
m_bucketTop
= bucketTop;
185
m_buckets
[i].pop_front ();
186
return
next;
187
}
188
if
(next.
key
< minKey)
189
{
190
minKey = next.
key
;
191
minBucket = i;
192
}
193
}
194
i++;
195
i %=
m_nBuckets
;
196
bucketTop +=
m_width
;
197
}
198
while
(i !=
m_lastBucket
);
199
200
m_lastPrio
= minKey.
m_ts
;
201
m_lastBucket
=
Hash
(minKey.
m_ts
);
202
m_bucketTop
= (minKey.
m_ts
/
m_width
+ 1) *
m_width
;
203
Scheduler::Event
next =
m_buckets
[minBucket].front();
204
m_buckets
[minBucket].pop_front ();
205
206
return
next;
207
}
208
209
Scheduler::Event
210
CalendarScheduler::RemoveNext
(
void
)
211
{
212
NS_LOG_FUNCTION
(
this
<<
m_lastBucket
<<
m_bucketTop
);
213
NS_ASSERT
(!
IsEmpty
());
214
215
Scheduler::Event
ev =
DoRemoveNext
();
216
NS_LOG_LOGIC
(
"remove ts="
<< ev.
key
.
m_ts
<<
217
", key="
<< ev.
key
.
m_uid
<<
218
", from bucket="
<<
m_lastBucket
);
219
m_qSize
--;
220
ResizeDown
();
221
return
ev;
222
}
223
224
void
225
CalendarScheduler::Remove
(
const
Event
&ev)
226
{
227
NS_LOG_FUNCTION
(
this
<< &ev);
228
NS_ASSERT
(!
IsEmpty
());
229
// bucket index of event
230
uint32_t bucket =
Hash
(ev.
key
.
m_ts
);
231
232
Bucket::iterator end =
m_buckets
[bucket].end ();
233
for
(Bucket::iterator i =
m_buckets
[bucket].begin (); i != end; ++i)
234
{
235
if
(i->key.m_uid == ev.
key
.
m_uid
)
236
{
237
NS_ASSERT
(ev.
impl
== i->impl);
238
m_buckets
[bucket].erase (i);
239
240
m_qSize
--;
241
ResizeDown
();
242
return
;
243
}
244
}
245
NS_ASSERT
(
false
);
246
}
247
248
void
249
CalendarScheduler::ResizeUp
(
void
)
250
{
251
NS_LOG_FUNCTION
(
this
);
252
253
if
(
m_qSize
>
m_nBuckets
* 2
254
&&
m_nBuckets
< 32768)
255
{
256
Resize
(
m_nBuckets
* 2);
257
}
258
}
259
void
260
CalendarScheduler::ResizeDown
(
void
)
261
{
262
NS_LOG_FUNCTION
(
this
);
263
264
if
(
m_qSize
<
m_nBuckets
/ 2)
265
{
266
Resize
(
m_nBuckets
/ 2);
267
}
268
}
269
270
uint32_t
271
CalendarScheduler::CalculateNewWidth
(
void
)
272
{
273
NS_LOG_FUNCTION
(
this
);
274
275
if
(
m_qSize
< 2)
276
{
277
return
1;
278
}
279
uint32_t nSamples;
280
if
(
m_qSize
<= 5)
281
{
282
nSamples =
m_qSize
;
283
}
284
else
285
{
286
nSamples = 5 +
m_qSize
/ 10;
287
}
288
if
(nSamples > 25)
289
{
290
nSamples = 25;
291
}
292
293
// we gather the first nSamples from the queue
294
std::list<Scheduler::Event> samples;
295
// save state
296
uint32_t lastBucket =
m_lastBucket
;
297
uint64_t bucketTop =
m_bucketTop
;
298
uint64_t lastPrio =
m_lastPrio
;
299
300
// gather requested events
301
for
(uint32_t i = 0; i < nSamples; i++)
302
{
303
samples.push_back (
DoRemoveNext
());
304
}
305
// put them back
306
for
(std::list<Scheduler::Event>::const_iterator i = samples.begin ();
307
i != samples.end (); ++i)
308
{
309
DoInsert
(*i);
310
}
311
312
// restore state.
313
m_lastBucket
= lastBucket;
314
m_bucketTop
= bucketTop;
315
m_lastPrio
= lastPrio;
316
317
// finally calculate inter-time average over samples.
318
uint64_t totalSeparation = 0;
319
std::list<Scheduler::Event>::const_iterator end = samples.end ();
320
std::list<Scheduler::Event>::const_iterator cur = samples.begin ();
321
std::list<Scheduler::Event>::const_iterator next = cur;
322
next++;
323
while
(next != end)
324
{
325
totalSeparation += next->key.m_ts - cur->key.m_ts;
326
cur++;
327
next++;
328
}
329
uint64_t twiceAvg = totalSeparation / (nSamples - 1) * 2;
330
totalSeparation = 0;
331
cur = samples.begin ();
332
next = cur;
333
next++;
334
while
(next != end)
335
{
336
uint64_t diff = next->key.m_ts - cur->key.m_ts;
337
if
(diff <= twiceAvg)
338
{
339
totalSeparation += diff;
340
}
341
cur++;
342
next++;
343
}
344
345
totalSeparation *= 3;
346
totalSeparation = std::max (totalSeparation, (uint64_t)1);
347
return
totalSeparation;
348
}
349
void
350
CalendarScheduler::DoResize
(uint32_t newSize, uint32_t newWidth)
351
{
352
NS_LOG_FUNCTION
(
this
<< newSize << newWidth);
353
354
Bucket
*oldBuckets =
m_buckets
;
355
uint32_t oldNBuckets =
m_nBuckets
;
356
Init
(newSize, newWidth,
m_lastPrio
);
357
358
for
(uint32_t i = 0; i < oldNBuckets; i++)
359
{
360
Bucket::iterator end = oldBuckets[i].end ();
361
for
(Bucket::iterator j = oldBuckets[i].begin (); j != end; ++j)
362
{
363
DoInsert
(*j);
364
}
365
}
366
delete
[] oldBuckets;
367
}
368
void
369
CalendarScheduler::Resize
(uint32_t newSize)
370
{
371
NS_LOG_FUNCTION
(
this
<< newSize);
372
373
// PrintInfo ();
374
uint32_t newWidth =
CalculateNewWidth
();
375
DoResize
(newSize, newWidth);
376
}
377
378
}
// namespace ns3
src
core
model
calendar-scheduler.cc
Generated on Fri Aug 30 2013 01:42:46 for ns-3 by
1.8.1.2