开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > Windows编程 > 通讯编程 > 查看源码
scheduler.cc
资源名称：ns-allinone-2.33.tar.gz　[点击查看]
上传用户：rrhhcc
上传日期：2015-12-11
资源大小：54129k
文件大小：26k
源码类别：

通讯编程

开发平台：

Visual C++

scheduler.cc：源码内容
  1. /* -*- Mode:C++; c-basic-offset:8; tab-width:8; indent-tabs-mode:t -*- */
  2. /*
  3.  * Copyright (c) 1994 Regents of the University of California.
  4.  * All rights reserved.
  5.  *
  6.  * Redistribution and use in source and binary forms, with or without
  7.  * modification, are permitted provided that the following conditions
  8.  * are met:
  9.  * 1. Redistributions of source code must retain the above copyright
  10.  *    notice, this list of conditions and the following disclaimer.
  11.  * 2. Redistributions in binary form must reproduce the above copyright
  12.  *    notice, this list of conditions and the following disclaimer in the
  13.  *    documentation and/or other materials provided with the distribution.
  14.  * 3. All advertising materials mentioning features or use of this software
  15.  *    must display the following acknowledgement:
  16.  * This product includes software developed by the Computer Systems
  17.  * Engineering Group at Lawrence Berkeley Laboratory.
  18.  * 4. Neither the name of the University nor of the Laboratory may be used
  19.  *    to endorse or promote products derived from this software without
  20.  *    specific prior written permission.
  21.  *
  22.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  23.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  24.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  25.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  26.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  27.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  28.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  29.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  30.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  31.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32.  * SUCH DAMAGE.
  33.  *
  34.  * @(#) $Header: /cvsroot/nsnam/ns-2/common/scheduler.cc,v 1.75 2007/12/04 19:59:31 seashadow Exp $
  35.  */
  37. #ifndef lint
  38. static const char rcsid[] =
  39.     "@(#) $Header: /cvsroot/nsnam/ns-2/common/scheduler.cc,v 1.75 2007/12/04 19:59:31 seashadow Exp $ (LBL)";
  40. #endif
  42. #include <stdlib.h>
  43. #include <limits.h>
  44. #include <math.h>
  46. #include "config.h"
  47. #include "scheduler.h"
  48. #include "packet.h"
  51. #ifdef MEMDEBUG_SIMULATIONS
  52. #include "mem-trace.h"
  53. #endif
  55. Scheduler* Scheduler::instance_;
  56. scheduler_uid_t Scheduler::uid_ = 1;
  58. // class AtEvent : public Event {
  59. // public:
  60. //  char* proc_;
  61. // };
  63. Scheduler::Scheduler() : clock_(SCHED_START), halted_(0)
  64. {
  65. }
  67. Scheduler::~Scheduler(){
  68. instance_ = NULL ;
  69. }
  71. /*
  72.  * Schedule an event delay time units into the future.
  73.  * The event will be dispatched to the specified handler.
  74.  * We use a relative time to avoid the problem of scheduling
  75.  * something in the past.
  76.  *
  77.  * Scheduler::schedule does a fair amount of error checking
  78.  * because debugging problems when events are triggered
  79.  * is much harder (because we've lost all context about who did
  80.  * the scheduling).
  81.  */
  82. void 
  83. Scheduler::schedule(Handler* h, Event* e, double delay)
  84. {
  85. // handler should ALWAYS be set... if it's not, it's a bug in the caller
  86. if (!h) {
  87. fprintf(stderr,
  88. "Scheduler: attempt to schedule an event with a NULL handler."
  89. "  Don't DO that.n");
  90. abort();
  91. };
  93. if (e->uid_ > 0) {
  94. printf("Scheduler: Event UID not valid!nn");
  95. abort();
  96. }
  98. if (delay < 0) {
  99. // You probably don't want to do this
  100. // (it probably represents a bug in your simulation).
  101. fprintf(stderr, 
  102. "warning: ns Scheduler::schedule: scheduling eventnt"
  103. "with negative delay (%f) at time %f.n", delay, clock_);
  104. }
  106. if (uid_ < 0) {
  107. fprintf(stderr, "Scheduler: UID space exhausted!n");
  108. abort();
  109. }
  110. e->uid_ = uid_++;
  111. e->handler_ = h;
  112. double t = clock_ + delay;
  114. e->time_ = t;
  115. insert(e);
  116. }
  118. void
  119. Scheduler::run()
  120. {
  121. instance_ = this;
  122. Event *p;
  123. /*
  124.  * The order is significant: if halted_ is checked later,
  125.  * event p could be lost when the simulator resumes.
  126.  * Patch by Thomas Kaemer <Thomas.Kaemer@eas.iis.fhg.de>.
  127.  */
  128. while (!halted_ && (p = deque())) {
  129. dispatch(p, p->time_);
  130. }
  131. }
  133. /*
  134.  * dispatch a single simulator event by setting the system
  135.  * virtul clock to the event's timestamp and calling its handler.
  136.  * Note that the event may have side effects of placing other items
  137.  * in the scheduling queue
  138.  */
  140. void
  141. Scheduler::dispatch(Event* p, double t)
  142. {
  143. if (t < clock_) {
  144. fprintf(stderr, "ns: scheduler going backwards in time from %f to %f.n", clock_, t);
  145. abort();
  146. }
  148. clock_ = t;
  149. p->uid_ = -p->uid_; // being dispatched
  150. p->handler_->handle(p); // dispatch
  151. }
  153. void
  154. Scheduler::dispatch(Event* p)
  155. {
  156. dispatch(p, p->time_);
  157. }
  159. class AtEvent : public Event {
  160. public:
  161. AtEvent() : proc_(0) {
  162. }
  163. ~AtEvent() {
  164. if (proc_) delete [] proc_;
  165. }
  166. char* proc_;
  167. };
  169. class AtHandler : public Handler {
  170. public:
  171. void handle(Event* event);
  172. } at_handler;
  174. void 
  175. AtHandler::handle(Event* e)
  176. {
  177. AtEvent* at = (AtEvent*)e;
  178. Tcl::instance().eval(at->proc_);
  179. delete at;
  180. }
  182. void
  183. Scheduler::reset()
  184. {
  185. clock_ = SCHED_START;
  186. }
  188. int 
  189. Scheduler::command(int argc, const char*const* argv)
  190. {
  191. Tcl& tcl = Tcl::instance();
  192. if (instance_ == 0)
  193. instance_ = this;
  194. if (argc == 2) {
  195. if (strcmp(argv[1], "run") == 0) {
  196. /* set global to 0 before calling object reset methods */
  197. reset(); // sets clock to zero
  198. run();
  199. return (TCL_OK);
  200. } else if (strcmp(argv[1], "now") == 0) {
  201. sprintf(tcl.buffer(), "%.17g", clock());
  202. tcl.result(tcl.buffer());
  203. return (TCL_OK);
  204. } else if (strcmp(argv[1], "resume") == 0) {
  205. halted_ = 0;
  206. run();
  207. return (TCL_OK);
  208. } else if (strcmp(argv[1], "halt") == 0) {
  209. halted_ = 1;
  210. return (TCL_OK);
  212. } else if (strcmp(argv[1], "clearMemTrace") == 0) {
  213. #ifdef MEMDEBUG_SIMULATIONS
  214. extern MemTrace *globalMemTrace;
  215. if (globalMemTrace)
  216. globalMemTrace->diff("Sim.");
  217. #endif
  218. return (TCL_OK);
  219. } else if (strcmp(argv[1], "is-running") == 0) {
  220. sprintf(tcl.buffer(), "%d", !halted_);
  221. return (TCL_OK);
  222. } else if (strcmp(argv[1], "dumpq") == 0) {
  223. if (!halted_) {
  224. fprintf(stderr, "Scheduler: dumpq only allowed while haltedn");
  225. tcl.result("0");
  226. return (TCL_ERROR);
  227. }
  228. dumpq();
  229. return (TCL_OK);
  230. }
  231. } else if (argc == 3) {
  232. if (strcmp(argv[1], "at") == 0 ||
  233.     strcmp(argv[1], "cancel") == 0) {
  234. Event* p = lookup(STRTOUID(argv[2]));
  235. if (p != 0) {
  236. /*XXX make sure it really is an atevent*/
  237. cancel(p);
  238. AtEvent* ae = (AtEvent*)p;
  239. delete ae;
  240. }
  241. } else if (strcmp(argv[1], "at-now") == 0) {
  242. const char* proc = argv[2];
  244. // "at [$ns now]" may not work because of tcl's 
  245. // string number resolution
  246. AtEvent* e = new AtEvent;
  247. int n = strlen(proc);
  248. e->proc_ = new char[n + 1];
  249. strcpy(e->proc_, proc);
  250. schedule(&at_handler, e, 0);
  251. sprintf(tcl.buffer(), UID_PRINTF_FORMAT, e->uid_);
  252. tcl.result(tcl.buffer());
  253. }
  254. return (TCL_OK);
  255. } else if (argc == 4) {
  256. if (strcmp(argv[1], "at") == 0) {
  257. /* t < 0 means relative time: delay = -t */
  258. double delay, t = atof(argv[2]);
  259. const char* proc = argv[3];
  261. AtEvent* e = new AtEvent;
  262. int n = strlen(proc);
  263. e->proc_ = new char[n + 1];
  264. strcpy(e->proc_, proc);
  265. delay = (t < 0) ? -t : t - clock();
  266. if (delay < 0) {
  267. tcl.result("can't schedule command in past");
  268. return (TCL_ERROR);
  269. }
  270. schedule(&at_handler, e, delay);
  271. sprintf(tcl.buffer(), UID_PRINTF_FORMAT, e->uid_);
  272. tcl.result(tcl.buffer());
  273. return (TCL_OK);
  274. }
  275. }
  276. return (TclObject::command(argc, argv));
  277. }
  279. void
  280. Scheduler::dumpq()
  281. {
  282. Event *p;
  284. printf("Contents of scheduler queue (events) [cur time: %f]---n",
  285. clock());
  286. while ((p = deque()) != NULL) {
  287. printf("t:%f uid: ", p->time_);
  288. printf(UID_PRINTF_FORMAT, p->uid_);
  289. printf(" handler: %pn", reinterpret_cast<void *>(p->handler_) );
  290. }
  291. }
  293. static class ListSchedulerClass : public TclClass {
  294. public:
  295. ListSchedulerClass() : TclClass("Scheduler/List") {}
  296. TclObject* create(int /* argc */, const char*const* /* argv */) {
  297. return (new ListScheduler);
  298. }
  299. } class_list_sched;
  301. void 
  302. ListScheduler::insert(Event* e)
  303. {
  304. double t = e->time_;
  305. Event** p;
  306. for (p = &queue_; *p != 0; p = &(*p)->next_)
  307. if (t < (*p)->time_)
  308. break;
  309. e->next_ = *p;
  310. *p = e;
  311. }
  313. /*
  314.  * Cancel an event.  It is an error to call this routine
  315.  * when the event is not actually in the queue.  The caller
  316.  * must free the event if necessary; this routine only removes
  317.  * it from the scheduler queue.
  318.  */
  319. void 
  320. ListScheduler::cancel(Event* e)
  321. {
  322. Event** p;
  323. if (e->uid_ <= 0) // event not in queue
  324. return;
  325. for (p = &queue_; *p != e; p = &(*p)->next_)
  326. if (*p == 0)
  327. abort();
  329. *p = (*p)->next_;
  330. e->uid_ = - e->uid_;
  331. }
  333. Event* 
  334. ListScheduler::lookup(scheduler_uid_t uid)
  335. {
  336. Event* e;
  337. for (e = queue_; e != 0; e = e->next_)
  338. if (e->uid_ == uid)
  339. break;
  340. return (e);
  341. }
  344. Event*
  345. ListScheduler::deque()
  346. { 
  347. Event* e = queue_;
  348. if (e)
  349. queue_ = e->next_;
  350. return (e);
  351. }
  353. #include "heap.h"
  355. Heap::Heap(int size)
  356. : h_s_key(0), h_size(0), h_maxsize(size), h_iter(0)
  357. {
  358. h_elems = new Heap_elem[h_maxsize];
  359. memset(h_elems, 0, h_maxsize*sizeof(Heap_elem));
  360. //for (unsigned int i = 0; i < h_maxsize; i++)
  361. // h_elems[i].he_elem = 0;
  362. }
  364. Heap::~Heap()
  365. {
  366. delete [] h_elems;
  367. }
  369. /*
  370.  * int heap_member(Heap *h, void *elem): O(n) algorithm.
  371.  *
  372.  * Returns index(elem in h->he_elems[]) + 1,
  373.  * if elem in h->he_elems[],
  374.  * 0, otherwise.
  375.  * External callers should just test for zero, or non-zero.
  376.  * heap_delete() uses this routine to find an element in the heap.
  377.  */
  378. int
  379. Heap::heap_member(void* elem)
  380. {
  381. unsigned int i;
  382. Heap::Heap_elem* he;
  383. for (i = 0, he = h_elems; i < h_size; i++, he++)
  384. if (he->he_elem == elem)
  385. return ++i;
  386. return 0;
  387. }
  389. /*
  390.  * int heap_delete(Heap *h, void *elem): O(n) algorithm
  391.  *
  392.  * Returns 1 for success, 0 otherwise.
  393.  *
  394.  * find elem in h->h_elems[] using heap_member()
  395.  *
  396.  * To actually remove the element from the tree, first swap it to the
  397.  * root (similar to the procedure applied when inserting a new
  398.  * element, but no key comparisons--just get it to the root).
  399.  *
  400.  * Then call heap_extract_min() to remove it & fix the tree.
  401.  *  This process is not the most efficient, but we do not
  402.  * particularily care about how fast heap_delete() is.
  403.  * Besides, heap_member() is already O(n), 
  404.  * and is the dominating cost.
  405.  *
  406.  * Actually remove the element by calling heap_extract_min().
  407.  *  The key that is now at the root is not necessarily the
  408.  * minimum, but heap_extract_min() does not care--it just
  409.  * removes the root.
  410.  */
  411. int
  412. Heap::heap_delete(void* elem)
  413. {
  414. int i;
  415. if ((i = heap_member(elem)) == 0)
  416. return 0;
  417. for (--i; i; i = parent(i)) {
  418. swap(i, parent(i));
  419. }
  420. (void) heap_extract_min();
  421. return 1;
  422. }
  424. /*
  425.  * void heap_insert(Heap *h, heap_key_t *key, void *elem)
  426.  *
  427.  * Insert <key, elem> into heap h.
  428.  * Adjust heap_size if we hit the limit.
  429.  * 
  430.  * i := heap_size(h)
  431.  * heap_size := heap_size + 1
  432.  * while (i > 0 and key < h[Parent(i)])
  433.  * do h[i] := h[Parent(i)]
  434.  * i := Parent(i)
  435.  * h[i] := key
  436.  */
  437. void
  438. Heap::heap_insert(heap_key_t key, void* elem) 
  439. {
  440. unsigned int i, par;
  441. if (h_maxsize == h_size) { /* Adjust heap_size */
  442. unsigned int osize = h_maxsize;
  443. Heap::Heap_elem *he_old = h_elems;
  444. h_maxsize *= 2;
  445. h_elems = new Heap::Heap_elem[h_maxsize];
  446. memcpy(h_elems, he_old, osize*sizeof(Heap::Heap_elem));
  447. delete []he_old;
  448. }
  450. i = h_size++;
  451. par = parent(i);
  452. while ((i > 0) && 
  453.        (KEY_LESS_THAN(key, h_s_key,
  454.       h_elems[par].he_key, h_elems[par].he_s_key))) {
  455. h_elems[i] = h_elems[par];
  456. i = par;
  457. par = parent(i);
  458. }
  459. h_elems[i].he_key  = key;
  460. h_elems[i].he_s_key= h_s_key++;
  461. h_elems[i].he_elem = elem;
  462. return;
  463. }
  465. /*
  466.  * void *heap_extract_min(Heap *h)
  467.  *
  468.  * Returns the smallest element in the heap, if it exists.
  469.  * NULL otherwise.
  470.  *
  471.  * if heap_size[h] == 0
  472.  * return NULL
  473.  * min := h[0]
  474.  * heap_size[h] := heap_size[h] - 1   # C array indices start at 0
  475.  * h[0] := h[heap_size[h]]
  476.  * Heapify:
  477.  * i := 0
  478.  * while (i < heap_size[h])
  479.  * do l = HEAP_LEFT(i)
  480.  * r = HEAP_RIGHT(i)
  481.  * if (r < heap_size[h])
  482.  * # right child exists =>
  483.  * #       left child exists
  484.  * then if (h[l] < h[r])
  485.  * then try := l
  486.  * else try := r
  487.  * else
  488.  * if (l < heap_size[h])
  489.  * then try := l
  490.  * else try := i
  491.  * if (h[try] < h[i])
  492.  * then HEAP_SWAP(h[i], h[try])
  493.  * i := try
  494.  * else break
  495.  * done
  496.  */
  497. void*
  498. Heap::heap_extract_min()
  499. {
  500. void* min;   /* return value */
  501. unsigned int i;
  502. unsigned int l, r, x;
  504. if (h_size == 0)
  505. return 0;
  506. min = h_elems[0].he_elem;
  507. h_elems[0] = h_elems[--h_size];
  508. // Heapify:
  509. i = 0;
  510. while (i < h_size) {
  511. l = left(i);
  512. r = right(i);
  513. if (r < h_size) {
  514. if (KEY_LESS_THAN(h_elems[l].he_key, h_elems[l].he_s_key,
  515.   h_elems[r].he_key, h_elems[r].he_s_key))
  516. x= l;
  517. else
  518. x= r;
  519. } else
  520. x = (l < h_size ? l : i);
  521. if ((x != i) && 
  522.     (KEY_LESS_THAN(h_elems[x].he_key, h_elems[x].he_s_key,
  523.    h_elems[i].he_key, h_elems[i].he_s_key))) {
  524. swap(i, x);
  525. i = x;
  526. } else {
  527. break;
  528. }
  529. }
  530. return min;
  531. }
  534. static class HeapSchedulerClass : public TclClass {
  535. public:
  536. HeapSchedulerClass() : TclClass("Scheduler/Heap") {}
  537. TclObject* create(int /* argc */, const char*const* /* argv */) {
  538. return (new HeapScheduler);
  539. }
  540. } class_heap_sched;
  542. Event* 
  543. HeapScheduler::lookup(scheduler_uid_t uid)
  544. {
  545. Event* e;
  547. for (e = (Event*) hp_->heap_iter_init(); e;
  548.      e = (Event*) hp_->heap_iter())
  549. if (e->uid_ == uid)
  550. break;
  551. return e;
  552. }
  554. Event*
  555. HeapScheduler::deque()
  556. {
  557. return ((Event*) hp_->heap_extract_min());
  558. }
  560. /*
  561.  * Calendar queue scheduler contributed by
  562.  * David Wetherall <djw@juniper.lcs.mit.edu>
  563.  * March 18, 1997.
  564.  *
  565.  * A calendar queue basically hashes events into buckets based on
  566.  * arrival time.
  567.  *
  568.  * See R.Brown. "Calendar queues: A fast O(1) priority queue implementation 
  569.  *  for the simulation event set problem." 
  570.  *  Comm. of ACM, 31(10):1220-1227, Oct 1988
  571.  */
  573. #define CALENDAR_HASH(t) ((int)fmod((t)/width_, nbuckets_))
  575. static class CalendarSchedulerClass : public TclClass {
  576. public:
  577. CalendarSchedulerClass() : TclClass("Scheduler/Calendar") {}
  578. TclObject* create(int /* argc */, const char*const* /* argv */) {
  579. return (new CalendarScheduler);
  580. }
  581. } class_calendar_sched;
  583. CalendarScheduler::CalendarScheduler() : cal_clock_(clock_) {
  584. bind("adjust_new_width_interval_", &adjust_new_width_interval_);
  585. bind("min_bin_width_", &min_bin_width_);
  586. if (adjust_new_width_interval_) {
  587. avg_gap_ = -2;
  588. last_time_ = -2;
  589. gap_num_ = 0;
  590. head_search_ = 0;
  591. insert_search_ = 0; 
  592. round_num_ = 0; 
  593. time_to_newwidth = adjust_new_width_interval_;
  594. }
  595. reinit(4, 1.0, cal_clock_);
  596. }
  598. CalendarScheduler::~CalendarScheduler() {
  599. // XXX free events?
  600. delete [] buckets_;
  601. qsize_ = 0;
  602. stat_qsize_ = 0;
  603. }
  605. void 
  606. CalendarScheduler::insert(Event* e)
  607. {
  608. int i;
  609. double newtime = e->time_;
  610. if (cal_clock_ > newtime) {
  611. // may happen in RT scheduler
  612. cal_clock_ = newtime;
  613. i = lastbucket_ = CALENDAR_HASH(cal_clock_);
  614. } else
  615. i = CALENDAR_HASH(newtime);
  617. Bucket* current=(&buckets_[i]);
  618. Event *head = current->list_;
  619. Event *after=0;
  621. if (!head) {
  622. current->list_ = e;
  623. e->next_ = e->prev_ = e;
  624. ++stat_qsize_; 
  625. ++(current->count_);
  626. } else {
  627. insert_search_++;
  628. if (newtime < head->time_) {
  629. //  e-> head -> ...
  630. e->next_ = head;
  631. e->prev_ = head->prev_;
  632. e->prev_->next_ = e;
  633. head->prev_ = e;
  634. current->list_ = e;
  635.                         ++stat_qsize_;
  636.                         ++(current->count_);
  637. } else {
  638.                         for (after = head->prev_; newtime < after->time_; after = after->prev_) { insert_search_++; };
  639. //...-> after -> e -> ...
  640. e->next_ = after->next_;
  641. e->prev_ = after;
  642. e->next_->prev_ = e;
  643. after->next_ = e;
  644. if (after->time_ < newtime) {
  645. //unique timing
  646. ++stat_qsize_; 
  647. ++(current->count_);
  648. }
  649. }
  650. }
  651. ++qsize_;
  652. //assert(e == buckets_[i].list_ ||  e->prev_->time_ <= e->time_);
  653. //assert(e == buckets_[i].list_->prev_ || e->next_->time_ >= e->time_);
  655.    if (stat_qsize_ > top_threshold_) {
  656.    resize(nbuckets_ << 1, cal_clock_);
  657. return;
  658. }
  659. }
  661. void 
  662. CalendarScheduler::insert2(Event* e)
  663. {
  664. // Same as insert, but for inserts e *before* any same-time-events, if
  665. //   there should be any.  Since it is used only by CalendarScheduler::newwidth(),
  666. //   some important checks present in insert() need not be performed.
  668. int i = CALENDAR_HASH(e->time_);
  669. Event *head = buckets_[i].list_;
  670. Event *before=0;
  671. if (!head) {
  672. buckets_[i].list_ = e;
  673. e->next_ = e->prev_ = e;
  674. ++stat_qsize_; 
  675. ++buckets_[i].count_;
  676. } else {
  677. bool newhead;
  678. if (e->time_ > head->prev_->time_) { //strict LIFO, so > and not >=
  679. // insert at the tail
  680. before = head;
  681. newhead = false;
  682. } else {
  683. // insert event in time sorted order, LIFO for sim-time events
  684. for (before = head; e->time_ > before->time_; before = before->next_)
  685. ;
  686. newhead = (before == head);
  687. }
  689. e->next_ = before;
  690. e->prev_ = before->prev_;
  691. before->prev_ = e;
  692. e->prev_->next_ = e;
  693. if (newhead) {
  694. buckets_[i].list_ = e;
  695. //assert(e->time_ <= e->next_->time_);
  696. }
  698. if (e != e->next_ && e->next_->time_ != e->time_) {
  699. // unique timing
  700. ++stat_qsize_; 
  701. ++buckets_[i].count_;
  702. }
  703. }
  704. //assert(e == buckets_[i].list_ ||  e->prev_->time_ <= e->time_);
  705. //assert(e == buckets_[i].list_->prev_ || e->next_->time_ >= e->time_);
  707. ++qsize_;
  708. // no need to check resizing
  709. }
  711. const Event*
  712. CalendarScheduler::head()
  713. {
  714. if (qsize_ == 0)
  715. return NULL;
  717. int l = -1, i = lastbucket_;
  718. int lastbucket_dec = (lastbucket_) ? lastbucket_ - 1 : nbuckets_ - 1;
  719. double diff;
  720. Event *e, *min_e = NULL;
  721. #define CAL_DEQUEUE(x) 
  722. do { 
  723. head_search_++;
  724. if ((e = buckets_[i].list_) != NULL) {
  725. diff = e->time_ - cal_clock_;
  726. if (diff < diff##x##_) {
  727. l = i;
  728. goto found_l;
  729. }
  730. if (min_e == NULL || min_e->time_ > e->time_) {
  731. min_e = e;
  732. l = i;
  733. }
  734. }
  735. if (++i == nbuckets_) i = 0;
  736. } while (0)
  737.  
  738. // CAL_DEQUEUE applied successively will find the event to
  739. // dequeue (within one year) and keep track of the
  740. // minimum-priority event seen so far; the argument controls
  741. // the criteria used to decide whether the event should be
  742. // considered `within one year'.  Importantly, the number of
  743. // buckets should not be less than 4.
  744. CAL_DEQUEUE(0); 
  745. CAL_DEQUEUE(1); 
  746. for (; i != lastbucket_dec; ) {
  747. CAL_DEQUEUE(2);
  748. }
  749. // one last bucket is left unchecked - take the minimum
  750. // [could have done CAL_DEQUEUE(3) with diff3_ = bwidth*(nbuck*3/2-1)]
  751. e = buckets_[i].list_;
  752. if (min_e != NULL && 
  753.     (e == NULL || min_e->time_ < e->time_))
  754. e = min_e;
  755. else {
  756. //assert(e);
  757. l = i;
  758. }
  759.  found_l:
  760. //assert(buckets_[l].count_ >= 0);
  761. //assert(buckets_[l].list_ == e);
  763. /* l is the index of the bucket to dequeue, e is the event */
  764. /* 
  765.  * still want to advance lastbucket_ and cal_clock_ to save
  766.  * time when deque() follows. 
  767.  */
  768. assert (l != -1);
  769. lastbucket_ = l;
  770.   cal_clock_  = e->time_;
  772. return e;
  773. }
  775. Event* 
  776. CalendarScheduler::deque()
  777. {
  778. Event *e = const_cast<Event *>(head());
  780. if (!e)
  781. return 0;
  783. if (adjust_new_width_interval_) {
  784. if (last_time_< 0) last_time_ = e->time_;
  785. else 
  786. {
  787. gap_num_ ++;
  788. if (gap_num_ >= qsize_ ) {
  789.                  double tt_gap_ = e->time_ - last_time_;
  790. avg_gap_ = tt_gap_ / gap_num_;
  791.                          gap_num_ = 0;
  792.                          last_time_ = e->time_;
  793. round_num_ ++;
  794. if ((round_num_ > 20) &&
  795.    (( head_search_> (insert_search_<<1))
  796.   ||( insert_search_> (head_search_<<1)) )) 
  797. {
  798. resize(nbuckets_, cal_clock_);
  799. round_num_ = 0;
  800. } else {
  801.                                  if (round_num_ > 100) {
  802.                                          round_num_ = 0;
  803.                                          head_search_ = 0;
  804.                                         insert_search_ = 0;
  805.                                  }
  806. }
  807. }
  808. }
  809. };
  811. int l = lastbucket_;
  813. // update stats and unlink
  814. if (e->next_ == e || e->next_->time_ != e->time_) {
  815. --stat_qsize_;
  816. //assert(stat_qsize_ >= 0);
  817. --buckets_[l].count_;
  818. //assert(buckets_[l].count_ >= 0);
  820. }
  821. --qsize_;
  823. if (e->next_ == e)
  824. buckets_[l].list_ = 0;
  825. else {
  826. e->next_->prev_ = e->prev_;
  827. e->prev_->next_ = e->next_;
  828. buckets_[l].list_ = e->next_;
  829. }
  831. e->next_ = e->prev_ = NULL;
  834. //if (buckets_[l].count_ == 0)
  835. // assert(buckets_[l].list_ == 0);
  837.   if (stat_qsize_ < bot_threshold_) {
  838. resize(nbuckets_ >> 1, cal_clock_);
  839. }
  841. return e;
  842. }
  844. void 
  845. CalendarScheduler::reinit(int nbuck, double bwidth, double start)
  846. {
  847. buckets_ = new Bucket[nbuck];
  849. memset(buckets_, 0, sizeof(Bucket)*nbuck); //faster than ctor
  851. width_ = bwidth;
  852. nbuckets_ = nbuck;
  853. qsize_ = 0;
  854. stat_qsize_ = 0;
  856. lastbucket_ =  CALENDAR_HASH(start);
  858. diff0_ = bwidth*nbuck/2;
  859. diff1_ = diff0_ + bwidth;
  860. diff2_ = bwidth*nbuck;
  861. //diff3_ = bwidth*(nbuck*3/2-1);
  863. bot_threshold_ = (nbuck >> 1) - 2;
  864. top_threshold_ = (nbuck << 1);
  865. }
  867. void 
  868. CalendarScheduler::resize(int newsize, double start)
  869. {
  870. double bwidth;
  871. if (newsize == nbuckets_) {
  872. /* we resize for bwidth*/
  873. if (head_search_) bwidth = head_search_; else bwidth = 1;
  874. if (insert_search_) bwidth = bwidth / insert_search_;
  875. bwidth = sqrt (bwidth) * width_;
  876.   if (bwidth < min_bin_width_) {
  877.   if (time_to_newwidth>0) {
  878.   time_to_newwidth --;
  879.           head_search_ = 0;
  880.           insert_search_ = 0;
  881.   round_num_ = 0;
  882.   return; //failed to adjust bwidth
  883.   } else {
  884. // We have many (adjust_new_width_interval_) times failure in adjusting bwidth.
  885. // should do a reshuffle with newwidth 
  886.   bwidth = newwidth(newsize);
  887.   }
  888.   };
  889. //snoopy queue calculation
  890. } else {
  891. /* we resize for size */
  892. bwidth = newwidth(newsize);
  893. if (newsize < 4)
  894. newsize = 4;
  895. }
  897. Bucket *oldb = buckets_;
  898. int oldn = nbuckets_;
  900. reinit(newsize, bwidth, start);
  902. // copy events to new buckets
  903. int i;
  905. for (i = 0; i < oldn; ++i) {
  906. // we can do inserts faster, if we use insert2, but to
  907. // preserve FIFO, we have to start from the end of
  908. // each bucket and use insert2
  909. if  (oldb[i].list_) {
  910. Event *tail = oldb[i].list_->prev_;
  911. Event *e = tail; 
  912. do {
  913. Event* ep = e->prev_;
  914. e->next_ = e->prev_ = 0;
  915. insert2(e);
  916. e = ep;
  917. } while (e != tail);
  918. }
  919. }
  920.         head_search_ = 0;
  921.         insert_search_ = 0;
  922. round_num_ = 0;
  923.         delete [] oldb;
  924. }
  926. // take samples from the most populated bucket.
  927. double
  928. CalendarScheduler::newwidth(int newsize)
  929. {
  930. if (adjust_new_width_interval_) {
  931. time_to_newwidth = adjust_new_width_interval_;
  932. if (avg_gap_ > 0) return avg_gap_*4.0;
  933. }
  934. int i;
  935. int max_bucket = 0; // index of the fullest bucket
  936. for (i = 1; i < nbuckets_; ++i) {
  937. if (buckets_[i].count_ > buckets_[max_bucket].count_)
  938. max_bucket = i;
  939. }
  940. int nsamples = buckets_[max_bucket].count_;
  942. if (nsamples <= 4) return width_;
  944. double nw = buckets_[max_bucket].list_->prev_->time_ 
  945. - buckets_[max_bucket].list_->time_;
  946. assert(nw > 0);
  948. nw /= ((newsize < nsamples) ? newsize : nsamples); // min (newsize, nsamples)
  949. nw *= 4.0;
  951. return nw;
  952. }
  954. /*
  955.  * Cancel an event.  It is an error to call this routine
  956.  * when the event is not actually in the queue.  The caller
  957.  * must free the event if necessary; this routine only removes
  958.  * it from the scheduler queue.
  959.  *
  960.  */
  961. void 
  962. CalendarScheduler::cancel(Event* e)
  963. {
  964. if (e->uid_ <= 0) // event not in queue
  965. return;
  967. int i = CALENDAR_HASH(e->time_);
  969. assert(e->prev_->next_ == e);
  970. assert(e->next_->prev_ == e);
  972. if (e->next_ == e || 
  973.     (e->next_->time_ != e->time_ &&
  974.     (e->prev_->time_ != e->time_))) { 
  975. --stat_qsize_;
  976. assert(stat_qsize_ >= 0);
  977. --buckets_[i].count_;
  978. assert(buckets_[i].count_ >= 0);
  979. }
  981. if (e->next_ == e) {
  982. assert(buckets_[i].list_ == e);
  983. buckets_[i].list_ = 0;
  984. } else {
  985. e->next_->prev_ = e->prev_;
  986. e->prev_->next_ = e->next_;
  987. if (buckets_[i].list_ == e)
  988. buckets_[i].list_ = e->next_;
  989. }
  991. if (buckets_[i].count_ == 0)
  992. assert(buckets_[i].list_ == 0);
  994. e->uid_ = -e->uid_;
  995. e->next_ = e->prev_ = NULL;
  997. --qsize_;
  999. return;
  1000. }
  1002. Event * 
  1003. CalendarScheduler::lookup(scheduler_uid_t uid)
  1004. {
  1005. for (int i = 0; i < nbuckets_; i++) {
  1006. Event* head =  buckets_[i].list_;
  1007. Event* p = head;
  1008. if (p) {
  1009. do {
  1010. if (p->uid_== uid) 
  1011. return p;
  1012. p = p->next_;
  1013. } while (p != head);
  1014. }
  1015. }
  1016. return NULL;
  1017. }
  1019. #ifndef WIN32
  1020. #include <sys/time.h>
  1021. #endif
  1023. class RealTimeScheduler : public CalendarScheduler {
  1024. public:
  1025. RealTimeScheduler();
  1026. virtual void run();
  1027. double start() const { return start_; }
  1028. virtual void reset();
  1029. protected:
  1030. void sync() { clock_ = tod(); }
  1031. double tod();
  1032. double slop_; // allowed drift between real-time and virt time
  1033. double start_; // starting time
  1034. };
  1036. static class RealTimeSchedulerClass : public TclClass {
  1037. public:
  1038. RealTimeSchedulerClass() : TclClass("Scheduler/RealTime") {}
  1039. TclObject* create(int /* argc */, const char*const* /* argv */) {
  1040. return (new RealTimeScheduler);
  1041. }
  1042. } class_realtime_sched;
  1044. RealTimeScheduler::RealTimeScheduler() : start_(0.0)
  1045. {
  1046. bind("maxslop_", &slop_);
  1047. }
  1049. double
  1050. RealTimeScheduler::tod()
  1051. {
  1052. timeval tv;
  1053. gettimeofday(&tv, 0);
  1054. double s = tv.tv_sec;
  1055. s += (1e-6 * tv.tv_usec);
  1056. return (s - start_);
  1057. }
  1059. void
  1060. RealTimeScheduler::reset()
  1061. {
  1062. clock_ = SCHED_START;
  1063. start_ = tod();
  1064. }
  1066. void 
  1067. RealTimeScheduler::run()
  1068. { 
  1069. static const double RTSCHEDULER_MINWAIT = 1.0e-3; // don't wait for less
  1070. const Event *p;
  1072. /*XXX*/
  1073. instance_ = this;
  1075. while (!halted_) {
  1076. clock_ = tod();
  1077. p = head();
  1078. if (p && (clock_ - p->time_) > slop_) {
  1079. fprintf(stderr,
  1080. "RealTimeScheduler: warning: slop "
  1081. "%f exceeded limit %f [clock_:%f, p->time_:%f]n",
  1082. clock_ - p->time_, slop_, clock_, p->time_);
  1083. }
  1084. // handle "old events"
  1085. while (p && p->time_ <= clock_) {
  1087. dispatch(deque(), clock_);
  1088. if (halted_)
  1089. return;
  1090. p = head();
  1091. clock_ = tod();
  1092. }
  1094. if (!p) {
  1095. // blocking wait for TCL events
  1096. Tcl_WaitForEvent(0); // no sim events, wait forever
  1097. clock_ = tod();
  1098. } else {
  1099. double diff = p->time_ - clock_;
  1100. // blocking wait only if there is enough time
  1101. if (diff > RTSCHEDULER_MINWAIT) {
  1102. Tcl_Time to;
  1103. to.sec = long(diff);
  1104. to.usec = long(1e6*(diff - to.sec));
  1105. Tcl_WaitForEvent(&to);    // block
  1106. clock_ = tod();
  1107. }
  1108. }
  1109. Tcl_DoOneEvent(TCL_DONT_WAIT);
  1110. }
  1111. // we reach here only if halted
  1112. }