scheduler.cc

可以在ns-2中进行仿真的SPIN路由协议的源码

	Event** buckets_;
	int qsize_;
	double max_;

	virtual void reinit(int nbuck, double bwidth, double start);
	virtual void resize(int newsize);
	virtual double newwidth();

private:
	virtual void insert2(Event*);

};

static class CalendarSchedulerClass : public TclClass {
public:
	CalendarSchedulerClass() : TclClass("Scheduler/Calendar") {}
	TclObject* create(int /* argc */, const char*const* /* argv */) {
		return (new CalendarScheduler);
	}
} class_calendar_sched;

CalendarScheduler::CalendarScheduler() {
	reinit(2, 1.0, 0.0);
	resizeenabled_ = 1;
	max_ = 0.0;
}

CalendarScheduler::~CalendarScheduler() {
	delete [] buckets_;
	qsize_ = 0;
}

void CalendarScheduler::insert(Event* e)
{

	/* (e->time_ * oneonwidth) needs to be less than the
	 * largest integer on the machine for the mapping
	 * of time to bucket to work properly.  if it is not
	 * we force a resize() where we reset the width.
	 */
	if (e->time_ > max_) {
		max_ = e->time_;
		if (e->time_ * oneonwidth_ > ULONG_MAX) {
			resize(nbuckets_);
		}
	}
	// bucket number and address
	int i = (int)(((long)(e->time_ * oneonwidth_)) & buckbits_); 
	Event** p = buckets_ + i;

	// insert event in stable time sorted order
	while ((*p != NULL) && (e->time_ >= (*p)->time_))
		p = &(*p)->next_;

	e->next_ = *p;
	*p = e;

	if (++qsize_ > top_threshold_)
		resize(2*nbuckets_);
}

Event*
CalendarScheduler::deque()
{
	if (qsize_ == 0)
		return NULL;
	int i = lastbucket_;

	// check for an event this `year'
	do {
		Event* e = buckets_[i];
		if ((e != NULL) && (e->time_ < buckettop_)) {
			buckets_[i] = e->next_;
			lastbucket_ = i;
			last_clock_ = e->time_;
			if (--qsize_ < bot_threshold_)
				resize(nbuckets_/2);
			return e;
		} else {
			if (++i == nbuckets_)
				i = 0;
			buckettop_ += width_;
		}
	} while (i != lastbucket_);

	// or direct search for the minimum event
	int pos = 0;
	Event* min;
	do {
		min = buckets_[pos++];
	} while (min == NULL);
	pos--;

	int k;
	for (k = pos+1; k < nbuckets_; k++) {
		Event* e = buckets_[k];
		if ((e != NULL) && (e->time_ < min->time_)) {
			min = e; pos = k;
		}
	}

	// adjust year and resume
	lastbucket_ = pos;
	last_clock_ = min->time_;
	unsigned long n = (unsigned long)(min->time_ * oneonwidth_);
	buckettop_ = (n + 1) * width_ + 0.5 * width_;

	return deque();
}

void CalendarScheduler::reinit(int nbuck, double bwidth, double start)
{
	buckets_ = new Event*[nbuck];
	memset(buckets_, 0, sizeof(Event*)*nbuck);
	width_ = bwidth;
	oneonwidth_ = 1.0 / width_;
	nbuckets_ = nbuck;
	buckbits_ = nbuck-1;
	qsize_ = 0;
	last_clock_ = start;
	long n = (long)(start * oneonwidth_);
	lastbucket_ = n % nbuck;
	buckettop_ = (n + 1) * width_ + 0.5 * width_;
	bot_threshold_ = nbuck / 2 - 2;
	top_threshold_ = 2 * nbuck;
}

void CalendarScheduler::resize(int newsize)
{
	if (!resizeenabled_) return;
	resizeenabled_ = 0;
	double bwidth = newwidth();
	Event** oldb = buckets_;
	int oldn = nbuckets_;

	// copy events to new buckets
	reinit(newsize, bwidth, clock_);
	int i;
	for (i = oldn-1; i >= 0; i--) {
		Event* e = oldb[i];
		while (e != NULL) {
			Event* en = e->next_;
			insert(e);
			e = en;
		}
	}
	delete [] oldb;
	resizeenabled_ = 1;
}

#define MIN_WIDTH (1.0e-6)
#define MAX_HOLD  25

double
CalendarScheduler::newwidth()
{
	static Event* hold[MAX_HOLD];
	int nsamples;

	if (qsize_ < 2) return 1.0;
	if (qsize_ < 5) nsamples = qsize_;
	else nsamples = 5 + qsize_ / 10;
	if (nsamples > MAX_HOLD) nsamples = MAX_HOLD;

	// dequue and requeue sample events to gauge width
	double olp = clock_;
	double olt = buckettop_;
	int olb = lastbucket_;
	for (int i = 0; i < nsamples; i++) hold[i] = deque();
	// insert in the inverse order and using insert2 to take care of same-time events.
	for (int j = nsamples-1; j >= 0; j--) insert2(hold[j]);
	clock_ = olp;
	buckettop_ = olt;
	lastbucket_ = olb;

	// try to work out average cluster separation
	double asep = (hold[nsamples-1]->time_ - hold[0]->time_) / (nsamples-1);
	double asep2 = 0.0;
	double min = (clock_ + 1.0) * MIN_WIDTH; 
	int count = 0;

	for (int k = 1; k < nsamples; k++) {
		double diff = hold[k]->time_ - hold[k-1]->time_;
		if (diff < 2.0*asep) { asep2 += diff; count++; }
	}

	// but don't let things get too small for numerical stability
	double nw = count ? 3.0*(asep2/count) : asep;
	if (nw < min) nw = min;

	/* need to make sure that time_/width_ can be represented as
	 * an int.  see the comment at the start of insert().
	 */
	if (max_/nw > ULONG_MAX) {
		nw = max_/ULONG_MAX;
	}
	return nw;
}

/*
 * Cancel an event.  It is an error to call this routine
 * when the event is not actually in the queue.  The caller
 * must free the event if necessary; this routine only removes
 * it from the scheduler queue.
 */
void CalendarScheduler::cancel(Event* e)
{
	int i = (int)(((long)(e->time_ * oneonwidth_)) & buckbits_);

	if (e->uid_ <= 0)	// event not in queue
		return;
	for (Event** p = buckets_ + i; (*p) != NULL; p = &(*p)->next_)
		if ((*p) == e) {
			(*p) = (*p)->next_;
			e->uid_ = - e->uid_;
			qsize_--;
			return;
		}
	abort();
}

Event* CalendarScheduler::lookup(int uid)
{
	for (int i = 0; i < nbuckets_; i++)
		for (Event* p = buckets_[i]; p != NULL; p = p->next_)
			if (p->uid_== uid) return p;
	return NULL;
}

void CalendarScheduler::insert2(Event* e)
{
	// Same as insert, but for inserts e *before* any same-time-events, if
	//   there should be any.  Since it is used only by CalendarScheduler::newwidth(),
	//   some important checks present in insert() need not be performed.

	// bucket number and address
	int i = (int)(((long)(e->time_ * oneonwidth_)) & buckbits_); 
	Event** p = buckets_ + i;

	// insert event in stable time sorted order
	while ((*p != NULL) && (e->time_ > (*p)->time_)) // > instead of >=!
		p = &(*p)->next_;

	e->next_ = *p;
	*p = e;
	++qsize_;
}

#ifndef WIN32
#include <sys/time.h>
#endif

/*
 * Really should instance the list/calendar/heap discipline
 * inside a RealTimeScheduler or VirtualTimeScheduler
 */

#ifdef notyet
class RealTimeScheduler : public CalendarScheduler {
#endif

class RealTimeScheduler : public ListScheduler {
public:
	RealTimeScheduler();
	virtual void run();
	double start() const { return start_; }
protected:
	void sync() { clock_ = tod(); }
	int rwait(double);	// sleep
	double tod();
	double slop_;	// allowed drift between real-time and virt time
	double start_;	// starting time
};

static class RealTimeSchedulerClass : public TclClass {
public:
	RealTimeSchedulerClass() : TclClass("Scheduler/RealTime") {}
	TclObject* create(int /* argc */, const char*const* /* argv */) {
		return (new RealTimeScheduler);
	}
} class_realtime_sched;

RealTimeScheduler::RealTimeScheduler() : start_(0.0)
{
	start_ = tod();
	bind("maxslop_", &slop_);
}

double
RealTimeScheduler::tod()
{
	timeval tv;
	gettimeofday(&tv, 0);
	double s = tv.tv_sec;
	s += (1e-6 * tv.tv_usec);
	return (s - start_);
}

// XXX not used?
// static void nullTimer(ClientData)
// {
// }

void RealTimeScheduler::run()
{ 
	Event *p;
	double now;

	/*XXX*/
	instance_ = this;

	while (!halted_) {
		now = tod();
		if ((clock_ - now) > slop_) {
			fprintf(stderr, "RealTimeScheduler: warning: slop %f exceeded limit %f\n",
				(clock_ - now), slop_);
		}

		//
		// first handle any "old events"
		//

		while ((p = deque()) != NULL && (p->time_ <= now)) {
			dispatch(p);
		}

		//
		// now handle a "future event", if there is one
		//
		if (p != NULL) {
			int rval = rwait(p->time_);
			if (rval < 0) {
				fprintf(stderr, "RTScheduler: wait problem\n");
				abort();
			} else if (rval == 0) {
				//
				// proper time to dispatch sim event... do so
				//
				dispatch(p, clock_);
			} else {
				//
				// there was a simulator event which fired, and
				// may have added something to the queue, which
				// could cause our event p to not be the next,
				// so put p back into the event queue and cont
				//
				insert(p);
			}
			continue;
		}

		//
		// no sim events to handle at all, check with tcl
		//
		sync();
		Tcl_DoOneEvent(TCL_DONT_WAIT);
	}

	return;	// we reach here only if halted
}

/*
 * wait until the specified amount has elapsed, or a tcl event has happened,
 * whichever comes first.  Return 1 if a tcl event happened, 0 if the
 * deadline has been reached, or -1 on error (shouldn't happen).
 */

int
RealTimeScheduler::rwait(double deadline)
{
	while (1) {
		sync();
		if (Tcl_DoOneEvent(TCL_DONT_WAIT) == 1)
			return (1);
		if (deadline <= tod())
			return 0;
	}
	return -1;
}