## diffname port/edf.c 2002/0315
## diff -e /dev/null /n/emeliedump/2002/0315/sys/src/9/port/edf.c
0a
/* EDF scheduling */
#include	"u.h"
#include	"../port/lib.h"
#include	"mem.h"
#include	"dat.h"
#include	"fns.h"
#include	"../port/error.h"
#include	"../port/devsched.h"
#include	"../port/edf.h"

/* debugging */
int			edfprint = 0;
char			tabs[16] = "																";
int			ind;
#define DPRINT	if(edfprint)iprint
#define DENTER	ind++;if(edfprint)iprint
#define DLEAVE	ind--

char *edf_statename[] = {
	[EdfUnused] =		"Unused",
	[EdfExpelled] =		"Expelled",
	[EdfAdmitted] =	"Admitted",
	[EdfIdle] =			"Idle",
	[EdfAwaitrelease] =	"Awaitrelease",
	[EdfReleased] =		"Released",
	[EdfRunning] =		"Running",
	[EdfExtra] =		"Extra",
	[EdfPreempted] =	"Preempted",
	[EdfBlocked] =		"Blocked",
	[EdfDeadline] =		"Deadline",
};

static Cycintr	schedpoint;		/* First scheduling point */
static Ticks	utilization;		/* Current utilization */
static int		initialized;
static uvlong	fasthz;	
static Ticks	now;
QLock		edfschedlock;		/* schedulability, held for
							 */
Lock			edflock;

Task			tasks[Maxtasks];
int			ntasks;
Resource		resources[Maxresources];
int			nresources;
int			edf_stateupdate;

enum{
	Deadline,	/* Invariant for schedulability test: Deadline < Release */
	Release,
};

static int earlierrelease(Task *t1, Task *t2) {return t1->r < t2->r;}
static int earlierdeadline(Task *t1, Task *t2) {return t1->d < t2->d;}

/* Tasks waiting for release, head earliest release time */
Taskq		qwaitrelease =	{{0}, nil, earlierrelease};

/* Released tasks waiting to run, head earliest deadline */
Taskq		qreleased	=	{{0}, nil, earlierdeadline};

/* Exhausted EDF tasks, append at end */
Taskq		qextratime;

/* Tasks admitted waiting for first release */
Taskq		qadmit;

/* Running/Preempted EDF tasks, head running, one stack per processor */
Taskq		edfstack[MAXMACH];

void (*devsched)(Task*, Ticks, int);

static void		edf_intr(Ureg*, Cycintr*);
static void		edf_resched(Task *t);
static void		setΔ(void);
static void		testΔ(Task *thetask);
static char *	edf_testschedulability(Task *thetask);
static void		edf_setclock(void);

void
edf_init(void)
{
	if (initialized)
		return;
	ilock(&edflock);
	if (initialized){
		iunlock(&edflock);
		return;
	}
	fastticks(&fasthz);
	schedpoint.f = edf_intr;
	schedpoint.a = &schedpoint;
	schedpoint.when = 0;
	initialized = 1;
	iunlock(&edflock);
}

int
isedf(Proc *p)
{
	return p && p->task && p->task->state >= EdfIdle;
}

int
edf_anyready(void)
{
	/* If any edf tasks (with runnable procs in them) are released,
	 * at least one of them must be on the stack
	 */
	return edfstack[m->machno].head != nil;
}

static void
edfpush(Task *t)
{
	Taskq *q;

	DENTER("%.*sedfpush, %s, %d\n", ind, tabs, edf_statename[t->state], t->runq.n);
	q = edfstack + m->machno;
	assert(t->runq.n || (up && up->task == t));
	if (q->head){
		assert(q->head->state == EdfRunning);
		q->head->state = EdfPreempted;
		if(devsched) devsched(q->head, now, SPreempt);
	}
	t->rnext = q->head;
	if(devsched) devsched(t, now, SRun);
	q->head = t;
	DLEAVE;
}

static Task*
edfpop(void)
{
	Task *t;
	Taskq *q;

	DENTER("%.*sedfpop\n", ind, tabs);
	q = edfstack + m->machno;
	if (t = q->head){
		assert(t->state == EdfRunning);
		q->head = t->rnext;
		t->rnext = nil;
		if (q->head){
			assert(q->head->state == EdfPreempted);
			q->head->state = EdfRunning;
			if(devsched) devsched(q->head, now, SRun);
		}
	}
	DLEAVE;
	return t;
}

static Task*
edfenqueue(Taskq *q, Task *t)
{
	Task *tt, **ttp;

	ilock(q);
	DENTER("%.*sedfenqueue, %s, %d\n", ind, tabs, edf_statename[t->state], t->runq.n);
	t->rnext = nil;
	if (q->head == nil) {
		q->head = t;
		DLEAVE;
		iunlock(q);
		return t;
	}
	SET(tt);
	for (ttp = &q->head; *ttp; ttp = &tt->rnext) {
		tt = *ttp;
		if (q->before && q->before(t, tt)) {
			t->rnext = tt;
			*ttp = t;
			break;
		}
	}
	if (*ttp == nil)
		tt->rnext = t;
	if (t != q->head)
		t = nil;
	DLEAVE;
	iunlock(q);
	return t;
}

static Task*
edfdequeue(Taskq *q)
{
	Task *t;

	DENTER("%.*sedfdequeue\n", ind, tabs);
	ilock(q);
	if (t = q->head){
		q->head = t->rnext;
		t->rnext = nil;
	}
	iunlock(q);
	DLEAVE;
	return t;
}

static void
edfqremove(Taskq *q, Task *t)
{
	Task **tp;

	ilock(q);
	DENTER("%.*sedfqremove, %s, %d\n", ind, tabs, edf_statename[t->state], t->runq.n);
	for (tp = &q->head; *tp; tp = &(*tp)->rnext){
		if (*tp == t){
			*tp = t->rnext;
			DLEAVE;
			iunlock(q);
			return;
		}
	}
	DLEAVE;
	iunlock(q);
}

void
edf_block(Proc *p)
{
	Task *t, *pt;

	/* The current proc has blocked */
	ilock(&edflock);
	t = p->task;
	DENTER("%.*sedf_block, %s, %d\n", ind, tabs, edf_statename[t->state], t->runq.n);

	assert(t);
	assert(t->state == EdfRunning);
	if (t->runq.n){
		/* There's another runnable proc in the running task, leave task where it is */
		iunlock(&edflock);
		DLEAVE;
		return;
	}
	pt = edfpop();
	assert(pt == t);
	t->state = EdfBlocked;
	if(devsched) devsched(t, now, SBlock);
	DLEAVE;
	iunlock(&edflock);
}

static void
edfdeadline(Proc *p, SEvent why)
{
	Task *t, *nt;

	/* Task has reached its deadline, lock must be held */
	DENTER("%.*sedfdeadline, %s, %d\n", ind, tabs, edf_statename[p->task->state], p->task->runq.n);
	SET(nt);
	if (p){
		nt = p->task;
		assert(nt);
		assert(nt->state == EdfRunning);
	}
	t = edfpop();

	if(p != nil && nt != t){
		DPRINT("%.*sedfdeadline, %s, %d\n", ind, tabs, edf_statename[p->task->state], p->task->runq.n);
		iunlock(&edflock);
		assert(0 && p == nil || nt == t);
	}

	t->d = now;
	t->state = EdfDeadline;
	if(devsched) devsched(t, now, why);
	edf_resched(t);
	DLEAVE;
}

void
edf_deadline(Proc *p)
{
	DENTER("%.*sedf_deadline\n", ind, tabs);
	/* Task has reached its deadline */
	ilock(&edflock);
	now = fastticks(nil);
	edfdeadline(p, SYield);
	iunlock(&edflock);
	DLEAVE;
}

char *
edf_admit(Task *t)
{
	char *err;

	if (t->state != EdfExpelled)
		return "task state";	/* should never happen */
	qlock(&edfschedlock);
	if (err = edf_testschedulability(t)){
		qunlock(&edfschedlock);
		return err;
	}
	ilock(&edflock);
	DENTER("%.*sedf_admit, %s, %d\n", ind, tabs, edf_statename[t->state], t->runq.n);
	now = fastticks(nil);

	t->state = EdfAdmitted;
	if (up->task == t){
		DPRINT("%.*sedf_admitting self\n", ind, tabs);
		/* Admitting self, fake reaching deadline */
		t->r = now;
		t->t = now + t->T;
		t->d = now + t->D;
		if(devsched) devsched(t, t->d, SDeadline);
		t->S = t->C;
		t->scheduled = now;
		t->state = EdfRunning;
		if(devsched) devsched(t, now, SRun);
		setΔ();
		assert(t->runq.n > 0 || (up && up->task == t));
		edfpush(t);
		edf_setclock();
	}else{
		if (t->runq.n){
			if (edfstack[m->machno].head == nil){
				t->state = EdfAdmitted;
				t->r = now;
				edf_release(t);
				setΔ();
				edf_resched(t);
			}else{
				edfenqueue(&qadmit, t);
			}
		}
	}
	DLEAVE;
	iunlock(&edflock);
	qunlock(&edfschedlock);
	return nil;
}

void
edf_expel(Task *t)
{
	Task *tt;

	qlock(&edfschedlock);
	ilock(&edflock);
	DENTER("%.*sedf_expel, %s, %d\n", ind, tabs, edf_statename[t->state], t->runq.n);
	now = fastticks(nil);
	switch(t->state){
	case EdfUnused:
	case EdfExpelled:
		/* That was easy */
		DLEAVE;
		iunlock(&edflock);
		qunlock(&edfschedlock);
		return;
	case EdfAdmitted:
	case EdfIdle:
		/* Just reset state */
		break;
	case EdfAwaitrelease:
		edfqremove(&qwaitrelease, t);
		break;
	case EdfReleased:
		edfqremove(&qreleased, t);
		break;
	case EdfRunning:
		/* Task must be expelling itself */
		tt = edfpop();
		assert(t == tt);
		break;
	case EdfExtra:
		edfqremove(&qextratime, t);
		break;
	case EdfPreempted:
		edfqremove(edfstack + m->machno, t);
		break;
	case EdfBlocked:
	case EdfDeadline:
		break;
	}
	t->state = EdfExpelled;
	if(devsched) devsched(t, now, SExpel);
	setΔ();
	DLEAVE;
	iunlock(&edflock);
	qunlock(&edfschedlock);
	return;
}

static void
edf_timer(void)
{
	Ticks used;
	Task *t;

	// If up is not set, we're running inside the scheduler
	// for non-real-time processes. 
	if (up && isedf(up)) {
		t = up->task;
		assert(t->scheduled > 0);
	
		used = now - t->scheduled;
		t->scheduled = now;

		if (t->r < now){
			if (t->S <= used)
				t->S = 0LL;
			else
				t->S -= used;
	
			if (t->d <= now || t->S == 0LL){
				/* Task has reached its deadline/slice, remove from queue */
				edfdeadline(up, SSlice);
				while (t = edfstack[m->machno].head){
					if (now < t->d)
						break;
					edfdeadline(nil, SSlice);
				}	
			}
		}
	}

	while((t = qwaitrelease.head) && t->r <= now){
		/* There's something waiting to be released and its time has come */
		edfdequeue(&qwaitrelease);
		edf_release(t);
	}
}

static void
edf_setclock(void)
{
	Ticks ticks;
	Task *t;

	DENTER("%.*sedf_setclock\n", ind, tabs);
	ticks = ~0ULL;
	if ((t = qwaitrelease.head) && t->r < ticks)
		ticks = t->r;
	if (t = edfstack[m->machno].head){
		if (t->d < ticks)
			ticks = t->d;
		if (now + t->S < ticks)
			ticks = now + t->S;
	}
	if (schedpoint.when > now && schedpoint.when <= ticks){
		DLEAVE;
		return;
	}
	if (schedpoint.when){
		DPRINT("%.*scycintrdel %T\n", ind, tabs, ticks2time(schedpoint.when));
		cycintrdel(&schedpoint);
		schedpoint.when = 0;
	}
	if (ticks <= now){
		DPRINT("%.*sedf_timer: %T too late\n", ind, tabs, ticks2time(now-ticks));
		ticks = now;
	}
	if (ticks != ~0ULL) {
		DPRINT("%.*sprogram timer in %T\n", ind, tabs, ticks2time(ticks-now));
		schedpoint.when = ticks;
		cycintradd(&schedpoint);
		DPRINT("%.*scycintradd %T\n", ind, tabs, ticks2time(schedpoint.when-now));
	}
	clockintrsched();
	DLEAVE;
}
	
static void
edf_intr(Ureg *, Cycintr *cy)
{

	DENTER("%.*sedf_intr\n", ind, tabs);
	/* Timer interrupt
	 * Timed events are:
	 * 1. release a task (look in qwaitrelease)
	 * 2. task reaches deadline
	 */
	now = fastticks(nil);

	assert(cy == &schedpoint && schedpoint.when <= now);

	if(active.exiting)
		return;

	ilock(&edflock);
	edf_timer();
	edf_setclock();
	iunlock(&edflock);
	DLEAVE;
	sched();
	splhi();
}

void
edf_bury(Proc *p)
{
	Task *t;
	Proc **pp;

	DPRINT("%.*sedf_bury\n", ind, tabs);
	ilock(&edflock);
	now = fastticks(nil);
	if ((t = p->task) == nil){
		/* race condition? */
		iunlock(&edflock);
		DPRINT("%.*sedf bury race, pid %lud\n", ind, tabs, p->pid);
		return;
	}
	assert(edfstack[m->machno].head == t);
	for (pp = t->procs; pp < t->procs + nelem(t->procs); pp++)
		if (*pp == p){
			t->nproc--;
			*pp = nil;
		}
	if (t->runq.head == nil){
		edfpop();
		t->state = EdfBlocked;
	}
	if (t->nproc == 0){
		assert(t->runq.head == nil);
		t->state = EdfIdle;
	}
	if(devsched) devsched(t, now, SBlock);
	p->task = nil;
	iunlock(&edflock);
}

void
edf_ready(Proc *p)
{
	Task *t;

	ilock(&edflock);
	DENTER("%.*sedf_ready, %s, %d\n", ind, tabs, edf_statename[p->task->state], p->task->runq.n);
	if ((t = p->task) == nil){
		/* Must be a race */
		iunlock(&edflock);
		DPRINT("%.*sedf ready race, pid %lud\n", ind, tabs, p->pid);
		return;
	}
	p->rnext = 0;
	p->readytime = m->ticks;
	p->state = Ready;
	t->runq.n++;
	if(t->runq.tail){
		t->runq.tail->rnext = p;
		t->runq.tail = p;
	}else{
		t->runq.head = p;
		t->runq.tail = p;

		/* first proc to become runnable in this task */
		now = fastticks(nil);
		edf_resched(t);
	}
	DLEAVE;
	iunlock(&edflock);
}

static void
edf_resched(Task *t)
{
	Task *xt;

	DENTER("%.*sedf_resched, %s, %d\n", ind, tabs, edf_statename[t->state], t->runq.n);
	if (t->nproc == 0){
		/* No member processes */
		if (t->state > EdfIdle){
			t->state = EdfIdle;
			if(devsched) devsched(t, now, SBlock);
		}
		DLEAVE;
		return;
	}
	if (t->runq.n == 0 && (up == nil || up->task != t)){
		/* Member processes but none runnable */
		DPRINT("%.*sedf_resched, nothing runnable\n", ind, tabs);
		if (t->state == EdfRunning)
			edfpop();

		if (t->state >= EdfIdle && t->state != EdfBlocked){
			t->state = EdfBlocked;
			if(devsched) devsched(t, now, SBlock);
		}
		DLEAVE;
		return;
	}

	/* There are runnable processes */

	switch (t->state){
	case EdfUnused:
		iprint("%.*sattempt to schedule unused task\n", ind, tabs);
	case EdfExpelled:
		DLEAVE;
		return;	/* Not admitted */
	case EdfIdle:
		/* task was idle, schedule release now or later */
		if (t->r < now){
			if (t->t < now)
				t->t = now + t->T;
			t->r = t->t;
		}
		edf_release(t);
		break;
	case EdfAwaitrelease:
	case EdfReleased:
	case EdfExtra:
	case EdfPreempted:
		/* dealt with by timer */
		break;
	case EdfAdmitted:
		/* test whether task can be started */
		if (edfstack[m->machno].head != nil){
			DLEAVE;
			return;
		}
		/* fall through */
	case EdfRunning:
		if (t->r <= now){
			if (t->t < now){
				DPRINT("%.*sedf_resched, rerelease\n", ind, tabs);
				/* Period passed, rerelease */
				t->r = now;
				xt = edfpop();
				assert(xt == t);
				edf_release(t);
				DLEAVE;
				return;
			}
			if (now < t->d){
				if (t->S > 0){
					DPRINT("%.*sedf_resched, resume\n", ind, tabs);
					/* Running, not yet at deadline, leave it */
					DLEAVE;
					return;
				}else
					t->d = now;
			}
			/* Released, but deadline is past, release at t->t */
			t->r = t->t;
		}
		DPRINT("%.*sedf_resched, schedule release\n", ind, tabs);
		xt = edfpop();
		assert(xt == t);
		edfenqueue(&qwaitrelease, t);
		t->state = EdfAwaitrelease;
		edf_setclock();
		break;
	case EdfBlocked:
	case EdfDeadline:
		if (t->r <= now){
			if (t->t < now){
				DPRINT("%.*sedf_resched, rerelease\n", ind, tabs);
				/* Period passed, rerelease */
				t->r = now;
				edf_release(t);
				DLEAVE;
				return;
			}
			if (now < t->d && (t->flags & Useblocking) == 0){
				if (t->S > 0){
					DPRINT("%.*sedf_resched, resume\n", ind, tabs);
					/* Released, not yet at deadline, release (again) */
					t->state = EdfReleased;
					edfenqueue(&qreleased, t);
					if(devsched) devsched(t, now, SResume);
					DLEAVE;
					return;
				}else
					t->d = now;
			}
			/* Released, but deadline is past, release at t->t */
			t->r = t->t;
		}
		DPRINT("%.*sedf_resched, schedule release\n", ind, tabs);
		edfenqueue(&qwaitrelease, t);
		t->state = EdfAwaitrelease;
		edf_setclock();
		break;
	}
	DLEAVE;
}

void
edf_release(Task *t)
{
	DENTER("%.*sedf_release, %s, %d\n", ind, tabs, edf_statename[t->state], t->runq.n);
	assert(t->runq.n > 0 || (up && up->task == t));
	t->t = t->r + t->T;
	t->d = t->r + t->D;
	if(devsched) devsched(t, t->d, SDeadline);
	t->S = t->C;
	t->state = EdfReleased;
	edfenqueue(&qreleased, t);
	if(devsched) devsched(t, now, SRelease);
	edf_setclock();
	DLEAVE;
}

Proc *
edf_runproc(void)
{
	/* Return an edf proc to run or nil */
	
	Task *t, *nt;
	Proc *p;
//	Ticks when;
	static ulong nilcount;

	/* Figure out if the current proc should be preempted*/
	ilock(&edflock);
	assert(ind < nelem(tabs));
	now = fastticks(nil);

	/* first candidate is at the top of the stack of running procs */
	t = edfstack[m->machno].head;

	/* check out head of the release queue for a proc with a better deadline */
	nt = qreleased.head;

	if (t == nil && nt == nil){
		nilcount++;
		iunlock(&edflock);
		return nil;
	}
	DENTER("edf_runproc %lud\n", nilcount);
	if (nt && (t == nil || (nt->D < t->Δ && nt->d < t->d))){
		/* released task is better than current */
		DPRINT("%.*sedf_runproc: released\n", ind, tabs);
		edfdequeue(&qreleased);
		assert(nt->runq.n >= 1);
		edfpush(nt);
		nt->state = EdfRunning;
		t = nt;
		t->scheduled = now;
	}else{
		DPRINT("%.*sedf_runproc: current\n", ind, tabs);
	}

	assert (t->runq.n);

	/* Get first proc off t's run queue
	 * No need to lock runq, edflock always held to access runq
	 */
	t->state = EdfRunning;
	p = t->runq.head;
	if ((t->runq.head = p->rnext) == nil)
		t->runq.tail = nil;
	t->runq.n--;
	p->state = Scheding;
	if(p->mp != MACHP(m->machno))
		p->movetime = MACHP(0)->ticks + HZ/10;
	p->mp = MACHP(m->machno);
	edf_setclock();
	DLEAVE;
	iunlock(&edflock);
	return p;
}

static Lock	waitlock;

int
edf_waitlock(Lock *l)
{
	iprint("edf_waitlock\n");
	ilock(&waitlock);	/* can't afford normal locks here */
	if (l->key == 0){
		/* race on lock, don't block, just return */
		iunlock(&waitlock);
		return 0;
	}
	edf_block(up);
	up->rnext = l->edfwaiting;	/* enqueue on lock */
	l->edfwaiting = up;
	up->state = Scheding;
	up->lockwait = l;
	iunlock(&waitlock);
	return 1;
}

void
edf_releaselock(Lock *l)
{
	Proc *p;

	iprint("edf_releaselock\n");
	ilock(&waitlock);	/* can't afford normal locks here */
	if(l->edfwaiting == nil){
		iunlock(&waitlock);
		return;
	}
	p = l->edfwaiting;
	l->edfwaiting = p->rnext;
	assert(p->lockwait == l);
	if(p->state != Scheding)
		print("edf_releaselock: %s %lud %s\n", p->text, p->pid, statename[p->state]);
	p->lockwait = nil;
	iunlock(&waitlock);
	edf_ready(p);
}


/* Schedulability testing and its supporting routines */

static void
setΔ(void)
{
	Resource *r, **rr;
	Task **tt, *t;

	for (r = resources; r < resources + nelem(resources); r++){
		if (r->name == nil)
			continue;
		r->Δ = ~0LL;
		for (tt = r->tasks; tt < r->tasks + nelem(r->tasks); tt++)
			if (*tt && (*tt)->D < r->Δ)
				r->Δ = (*tt)->D;
	}
	for (t = tasks; t < tasks + nelem(tasks); t++){
		if (t->state < EdfIdle)
			continue;
		t->Δ = t->D;
		for (rr = t->res; rr < t->res + nelem(t->res); rr++)
			if (*rr && (*rr)->Δ < t->Δ)
				t->Δ = (*rr)->Δ;
	}
}

static void
testΔ(Task *thetask)
{
	Resource *r, **rr;
	Task **tt, *t;

	for (r = resources; r < resources + nelem(resources); r++){
		if (r->name == nil)
			continue;
		r->testΔ = ~0ULL;
		for (tt = r->tasks; tt < r->tasks + nelem(r->tasks); tt++)
			if (*tt && (*tt)->D < r->testΔ)
				r->testΔ = (*tt)->D;
	}
	for (t = tasks; t < tasks + nelem(tasks); t++){
		if (t->state <= EdfExpelled && t != thetask)
			continue;
		t->testΔ = t->D;
		for (rr = t->res; rr < t->res + nelem(t->res); rr++)
			if (*rr && (*rr)->testΔ < t->testΔ)
				t->testΔ = (*rr)->testΔ;
	}
}

static Ticks
blockcost(Ticks ticks, Task *thetask)
{
	Task *t;
	Ticks Cb;

	Cb = 0;
	for (t = tasks; t < tasks + Maxtasks; t++){
		if (t->state <= EdfExpelled && t != thetask)
			continue;
		if (t->testΔ <= ticks && ticks < t->D && Cb < t->C)
			Cb = t->C;
	}
	return Cb;
}

static Task *qschedulability;

static void
testenq(Task *t)
{
	Task *tt, **ttp;

	t->testnext = nil;
	if (qschedulability == nil) {
		qschedulability = t;
		return;
	}
	SET(tt);
	for (ttp = &qschedulability; *ttp; ttp = &tt->testnext) {
		tt = *ttp;
		if (t->testtime < tt->testtime
		|| (t->testtime == tt->testtime && t->testtype < tt->testtype)){
			t->testnext = tt;
			*ttp = t;
			return;
		}
	}
	assert(tt->testnext == nil);
	tt->testnext = t;
}

static char *
edf_testschedulability(Task *thetask)
{
	Task *t;
	Ticks H, G, Cb, ticks;
	int steps;

	/* initialize */
	testΔ(thetask);
	if (thetask && (thetask->flags & Verbose))
		pprint("schedulability test\n");
	qschedulability = nil;
	for (t = tasks; t < tasks + Maxtasks; t++){
		if (t->state <= EdfExpelled && t != thetask)
			continue;
		t->testtype = Release;
		t->testtime = 0;
		if (thetask && (thetask->flags & Verbose))
			pprint("\tInit: enqueue task %lud\n", t - tasks);
		testenq(t);
	}
	H=0;
	G=0;
	ticks = 0;
	for(steps = 0; steps < Maxsteps; steps++){
		t = qschedulability;
		qschedulability = t->testnext;
		ticks = t->testtime;
		switch (t->testtype){
		case Deadline:
			H += t->C;
			Cb = blockcost(ticks, thetask);
			if (thetask && (thetask->flags & Verbose))
				pprint("\tStep %3d, Ticks %T, task %lud, deadline, H += %T → %T, Cb = %T\n",
					steps, ticks2time(ticks), t - tasks,
					ticks2time(t->C), ticks2time(H), ticks2time(Cb));
			if (H+Cb>ticks)
				return "not schedulable";
			t->testtime += t->T - t->D;
			t->testtype = Release;
			testenq(t);
			break;
		case Release:
			if (thetask && (thetask->flags & Verbose))
				pprint("\tStep %3d, Ticks %T, task %lud, release, G  %T, C%T\n",
					steps, ticks2time(ticks), t - tasks,
					ticks2time(t->C), ticks2time(G));
			if(ticks && G <= ticks)
				return nil;
			G += t->C;
			t->testtime += t->D;
			t->testtype = Deadline;
			testenq(t);
			break;
		default:
			assert(0);
		}
	}
	return "probably not schedulable";
}

static uvlong
uvmuldiv(uvlong x, ulong num, ulong den)
{
	/* multiply, then divide, avoiding overflow */
	uvlong hi;

	hi = (x & 0xffffffff00000000LL) >> 32;
	x &= 0xffffffffLL;
	hi *= num;
	return (x*num + (hi%den << 32)) / den + (hi/den << 32);
}

Time
ticks2time(Ticks ticks)
{
	assert(ticks >= 0);
	return uvmuldiv(ticks, Onesecond, fasthz);
}

Ticks
time2ticks(Time time)
{
	assert(time >= 0);
	return uvmuldiv(time, fasthz, Onesecond);
}
.
## diffname port/edf.c 2002/0316
## diff -e /n/emeliedump/2002/0315/sys/src/9/port/edf.c /n/emeliedump/2002/0316/sys/src/9/port/edf.c
738c
		DPRINT("%.*s%d edf_runproc: current\n", ind, tabs, m->machno);
.
730c
		DPRINT("%.*s%d edf_runproc: released\n", ind, tabs, m->machno);
.
696c
	if(devrt) devrt(t, now, SRelease);
.
692c
	if(devrt) devrt(t, t->d, SDeadline);
.
688c
	DENTER("%.*s%d edf_release, %s, %d\n", ind, tabs, m->machno, edf_statename[t->state], t->runq.n);
.
676c
		DPRINT("%.*s%d edf_resched, schedule release\n", ind, tabs, m->machno);
.
667c
					if(devrt) devrt(t, now, SResume);
.
663c
					DPRINT("%.*s%d edf_resched, resume\n", ind, tabs, m->machno);
.
654c
				DPRINT("%.*s%d edf_resched, rerelease\n", ind, tabs, m->machno);
.
643c
		DPRINT("%.*s%d edf_resched, schedule release\n", ind, tabs, m->machno);
.
633c
					DPRINT("%.*s%d edf_resched, resume\n", ind, tabs, m->machno);
.
622c
				DPRINT("%.*s%d edf_resched, rerelease\n", ind, tabs, m->machno);
.
593c
		iprint("%.*s%d attempt to schedule unused task\n", ind, tabs, m->machno);
.
583c
			if(devrt) devrt(t, now, SBlock);
.
577c
		DPRINT("%.*s%d edf_resched, nothing runnable\n", ind, tabs, m->machno);
.
570c
			if(devrt) devrt(t, now, SBlock);
.
565c
	DENTER("%.*s%d edf_resched, %s, %d\n", ind, tabs, m->machno, edf_statename[t->state], t->runq.n);
.
538c
		DPRINT("%.*s%d edf ready race, pid %lud\n", ind, tabs, m->machno, p->pid);
.
534c
	DENTER("%.*s%d edf_ready, %s, %d\n", ind, tabs, m->machno, edf_statename[p->task->state], p->task->runq.n);
.
523c
	if(devrt) devrt(t, now, SBlock);
.
506c
		DPRINT("%.*s%d edf bury race, pid %lud\n", ind, tabs, m->machno, p->pid);
.
500c
	DPRINT("%.*s%d edf_bury\n", ind, tabs, m->machno);
.
472c
	DENTER("%.*s%d edf_intr\n", ind, tabs, m->machno);
.
462c
		DPRINT("%.*s%d cycintradd %T\n", ind, tabs, m->machno, ticks2time(schedpoint.when-now));
.
459c
		DPRINT("%.*s%d program timer in %T\n", ind, tabs, m->machno, ticks2time(ticks-now));
.
455c
		DPRINT("%.*s%d edf_timer: %T too late\n", ind, tabs, m->machno, ticks2time(now-ticks));
.
450c
		DPRINT("%.*s%d cycintrdel %T\n", ind, tabs, m->machno, ticks2time(schedpoint.when));
.
435c
	DENTER("%.*s%d edf_setclock\n", ind, tabs, m->machno);
.
381c
	if(devrt) devrt(t, now, SExpel);
.
345c
	DENTER("%.*s%d edf_expel, %s, %d\n", ind, tabs, m->machno, edf_statename[t->state], t->runq.n);
.
314c
		if(devrt) devrt(t, now, SRun);
.
310c
		if(devrt) devrt(t, t->d, SDeadline);
.
305c
		DPRINT("%.*s%d edf_admitting self\n", ind, tabs, m->machno);
.
303a
	if(devrt) devrt(t, t->d, SAdmit);
.
300c
	DENTER("%.*s%d edf_admit, %s, %d\n", ind, tabs, m->machno, edf_statename[t->state], t->runq.n);
.
293a

	/* simple sanity checks */
	if (t->T == 0)
		return "T not set";
	if (t->C == 0)
		return "C not set";
	if (t->D > t->T)
		return "D > T";
	if (t->D == 0)	/* if D is not set, set it to T */
		t->D = t->T;
	if (t->C > t->D)
		return "C > D";

.
278c
	DENTER("%.*s%d edf_deadline\n", ind, tabs, m->machno);
.
270c
	if(devrt) devrt(t, now, why);
.
263c
		DPRINT("%.*s%d edfdeadline, %s, %d\n", ind, tabs, m->machno, edf_statename[p->task->state], p->task->runq.n);
.
253c
	DENTER("%.*s%d edfdeadline, %s, %d\n", ind, tabs, m->machno, edf_statename[p->task->state], p->task->runq.n);
.
242c
	if(devrt) devrt(t, now, SBlock);
.
229c
	DENTER("%.*s%d edf_block, %s, %d\n", ind, tabs, m->machno, edf_statename[t->state], t->runq.n);
.
208c
	DENTER("%.*s%d edfqremove, %s, %d\n", ind, tabs, m->machno, edf_statename[t->state], t->runq.n);
.
191c
	DENTER("%.*s%d edfdequeue\n", ind, tabs, m->machno);
.
160c
	DENTER("%.*s%d edfenqueue, %s, %d\n", ind, tabs, m->machno, edf_statename[t->state], t->runq.n);
.
147c
			if(devrt) devrt(q->head, now, SRun);
.
138c
	DENTER("%.*s%d edfpop\n", ind, tabs, m->machno);
.
127c
	if(devrt) devrt(t, now, SRun);
.
124c
		if(devrt) devrt(q->head, now, SPreempt);
.
118c
	DENTER("%.*s%d edfpush, %s, %d\n", ind, tabs, m->machno, edf_statename[t->state], t->runq.n);
.
71c
void (*devrt)(Task*, Ticks, int);
.
8c
#include	"../port/devrealtime.h"
.
## diffname port/edf.c 2002/0319
## diff -e /n/emeliedump/2002/0316/sys/src/9/port/edf.c /n/emeliedump/2002/0319/sys/src/9/port/edf.c
779a
	Task *t;

.
## diffname port/edf.c 2002/0320
## diff -e /n/emeliedump/2002/0319/sys/src/9/port/edf.c /n/emeliedump/2002/0320/sys/src/9/port/edf.c
988a
	if (fasthz == 0)
		fastticks(&fasthz);
.
920c
	testdelta(thetask);
.
880c
		if (t->testDelta <= ticks && ticks < t->D && Cb < t->C)
.
865,866c
			if (*rr && (*rr)->testDelta < t->testDelta)
				t->testDelta = (*rr)->testDelta;
.
863c
		t->testDelta = t->D;
.
857,858c
			if (*tt && (*tt)->D < r->testDelta)
				r->testDelta = (*tt)->D;
.
855c
		r->testDelta = ~0ULL;
.
847c
testdelta(Task *thetask)
.
841,842c
			if (*rr && (*rr)->Delta < t->Delta)
				t->Delta = (*rr)->Delta;
.
839c
		t->Delta = t->D;
.
833,834c
			if (*tt && (*tt)->D < r->Delta)
				r->Delta = (*tt)->D;
.
831c
		r->Delta = ~0LL;
.
823c
setdelta(void)
.
780,781d
742c
	if (nt && (t == nil || (nt->d < t->d && nt->D < t->Delta))){
.
396c
	setdelta();
.
339c
				setdelta();
.
329c
		setdelta();
.
263c
		iprint("edfdeadline, %s, %d\n", edf_statename[p->task->state], p->task->runq.n);
.
258d
231,232d
228a
	assert(t);
	if (t->state != EdfRunning){
		/* called by a proc just joining the task */
		iunlock(&edflock);
		return;
	}
.
75,76c
static void		setdelta(void);
static void		testdelta(Task *thetask);
.
## diffname port/edf.c 2002/0321
## diff -e /n/emeliedump/2002/0320/sys/src/9/port/edf.c /n/emeliedump/2002/0321/sys/src/9/port/edf.c
261c
		if (nt == nil || nt->state != EdfRunning)
			return;
.
## diffname port/edf.c 2002/0322
## diff -e /n/emeliedump/2002/0321/sys/src/9/port/edf.c /n/emeliedump/2002/0322/sys/src/9/port/edf.c
805d
784d
774d
756c
		DPRINT("%d edf_runproc: current\n", m->machno);
.
748c
		DPRINT("%d edf_runproc: released\n", m->machno);
.
745c
	DPRINT("edf_runproc %lud\n", nilcount);
.
731d
716d
706c
	DPRINT("%d edf_release, %s, %d\n", m->machno, edf_statename[t->state], t->runq.n);
.
700d
694c
		DPRINT("%d edf_resched, schedule release\n", m->machno);
.
686d
681c
					DPRINT("%d edf_resched, resume\n", m->machno);
.
676d
672c
				DPRINT("%d edf_resched, rerelease\n", m->machno);
.
661c
		DPRINT("%d edf_resched, schedule release\n", m->machno);
.
653d
651c
					DPRINT("%d edf_resched, resume\n", m->machno);
.
646d
640c
				DPRINT("%d edf_resched, rerelease\n", m->machno);
.
633d
613d
611c
		iprint("%d attempt to schedule unused task\n", m->machno);
.
603d
595c
		DPRINT("%d edf_resched, nothing runnable\n", m->machno);
.
590d
583c
	DPRINT("%d edf_resched, %s, %d\n", m->machno, edf_statename[t->state], t->runq.n);
.
574d
556c
		DPRINT("%d edf ready race, pid %lud\n", m->machno, p->pid);
.
552c
	DPRINT("%d edf_ready, %s, %d\n", m->machno, edf_statename[p->task->state], p->task->runq.n);
.
524c
		DPRINT("%d edf bury race, pid %lud\n", m->machno, p->pid);
.
518c
	DPRINT("%d edf_bury\n", m->machno);
.
507d
490c
	DPRINT("%d edf_intr\n", m->machno);
.
483d
480c
		DPRINT("%d cycintradd %T\n", m->machno, ticks2time(schedpoint.when-now));
.
477c
		DPRINT("%d program timer in %T\n", m->machno, ticks2time(ticks-now));
.
473c
		DPRINT("%d edf_timer: %T too late\n", m->machno, ticks2time(now-ticks));
.
468c
		DPRINT("%d cycintrdel %T\n", m->machno, ticks2time(schedpoint.when));
.
464d
453c
	DPRINT("%d edf_setclock\n", m->machno);
.
401d
369d
363c
	DPRINT("%d edf_expel, %s, %d\n", m->machno, edf_statename[t->state], t->runq.n);
.
350d
323c
		DPRINT("%d edf_admitting self\n", m->machno);
.
317c
	DPRINT("%d edf_admit, %s, %d\n", m->machno, edf_statename[t->state], t->runq.n);
.
288d
282c
	DPRINT("%d edf_deadline\n", m->machno);
.
276d
257c
	DPRINT("%d edfdeadline, %s, %d\n", m->machno, edf_statename[p->task->state], p->task->runq.n);
.
247d
240d
235c
	DPRINT("%d edf_block, %s, %d\n", m->machno, edf_statename[t->state], t->runq.n);
.
217d
212d
208c
	DPRINT("%d edfqremove, %s, %d\n", m->machno, edf_statename[t->state], t->runq.n);
.
198d
191c
	DPRINT("%d edfdequeue\n", m->machno);
.
181d
164d
160c
	DPRINT("%d edfenqueue, %s, %d\n", m->machno, edf_statename[t->state], t->runq.n);
.
150d
138c
	DPRINT("%d edfpop\n", m->machno);
.
129d
118c
	DPRINT("%d edfpush, %s, %d\n", m->machno, edf_statename[t->state], t->runq.n);
.
16,17d
13,14d
## diffname port/edf.c 2002/0327
## diff -e /n/emeliedump/2002/0322/sys/src/9/port/edf.c /n/emeliedump/2002/0327/sys/src/9/port/edf.c
740c

	when = now + t->S;
	if (t->d < when)
		when = t->d;

	if (cycdeadline.when){
		if(cycdeadline.when == when){
			iunlock(&edflock);
			return p;
		}
		DPRINT("%d cycintrdel %T\n", m->machno, ticks2time(cycdeadline.when));
		cycintrdel(&cycdeadline);
	}
	if (when <= now){
		DPRINT("%d edf_timer: %T too late\n", m->machno, ticks2time(now-when));
		when = now;
	}
	DPRINT("%d program timer in %T\n", m->machno, ticks2time(when-now));
	cycdeadline.when = when;
	cycintradd(&cycdeadline);
	DPRINT("%d cycintradd %T\n", m->machno, ticks2time(cycdeadline.when-now));
	clockintrsched();
.
694c
	Ticks when;
.
684d
664,667c
		schedrelease(t);
.
636,638c
		schedrelease(t);
.
633d
421,485d
394a
	DPRINT("%d edfdeadlineintr\n", m->machno);
	/* Task reached deadline
	 */
	now = fastticks(nil);

	if(active.exiting)
		return;

	ilock(&edflock);
.
391a
	Task *t;

	now = fastticks(nil);

	if(active.exiting)
		return;

	ilock(&edflock);
	while((t = qwaitrelease.head) && t->r <= now){
		/* There's something waiting to be released and its time has come */
		edfdequeue(&qwaitrelease);
		edf_release(t);
	}
	iunlock(&edflock);
	sched();
	splhi();
}

static void
edfdeadlineintr(Ureg *, Cycintr *cy)
{
.
390c
edfreleaseintr(void)
.
361c
		if (edfqremove(&qwaitrelease, t))
			edfreleasetimer();
.
321d
258c
	if (cycdeadline.when){
		cycintrdel(&cycdeadline);
		cycdeadline.when = 0;
		clockintrsched();
	}
.
210a
edfreleasetimer(void)
{
	Task *t;

	t = qwaitrelease.head;
	DPRINT("edf_schedrelease clock\n");
	if (cycrelease.when == t->r)
		return;
	if (cycrelease.when){
		DPRINT("%d cycintrdel %T\n", m->machno, ticks2time(cycrelease.when));
		cycintrdel(&cycrelease);
	}
	cycrelease.when = t->r;
	if (cycrelease.when <= now){
		DPRINT("%d edf_timer: %T too late\n", m->machno, ticks2time(now-ticks));
		cycrelease.when = now;
	}
	DPRINT("%d program timer in %T\n", m->machno, ticks2time(ticks-now));
	cycintradd(&cycrelease);
	DPRINT("%d cycintradd %T\n", m->machno, ticks2time(cycrelease.when-now));
	clockintrsched();
}

void
edf_schedrelease(Task *t)
{
	Ticks ticks;

	DPRINT("%d edf_schedrelease\n", m->machno);
	/* Schedule a task for release */
	t->state = EdfAwaitrelease;
	if (edfenqueue(&qwaitrelease, t))
		edfreleasetimer();
}

void
.
209a
			
.
204c
			return t;
.
202a
			t = (tp == &q->head) ? q->head : nil;
.
193c
static Task*
.
87,89c
	cycdeadline.f = edfdeadlineintr;
	cycdeadline.a = &cycdeadline;
	cycdeadline.when = 0;
	cycrelease.f = edfreleaseintr;
	cycrelease.a = &cycrelease;
	cycrelease.when = 0;
.
74c
static void		edfreleaseintr(void);
.
69c
static void		edfdeadlineintr(Ureg*, Cycintr*);
.
29c
static Cycintr	cycdeadline;		/* Time of next deadline */
static Cycintr	cycrelease;		/* Time of next release */

.
## diffname port/edf.c 2002/0328
## diff -e /n/emeliedump/2002/0327/sys/src/9/port/edf.c /n/emeliedump/2002/0328/sys/src/9/port/edf.c
770,810d
765d
758,762d
755d
749a
	if (when < now){
		DPRINT("%d edf_timer: %T too late\n", m->machno, ticks2time(now-when));
		when = now;
	}
.
673c
		t->state = EdfAwaitrelease;
		if (edfenqueue(&qwaitrelease, t))
			edfreleasetimer();
.
647c
		t->state = EdfAwaitrelease;
		if (edfenqueue(&qwaitrelease, t))
			edfreleasetimer();
.
474a
		now = fastticks(nil);

.
467a
	cycdeadline.when = 0;

.
464,466d
459a
	/* Task reached deadline */

.
458c
edfdeadlineintr(Ureg*, Cycintr*)
.
449a
		edfreleasetimer();
.
446a
	now = fastticks(nil);
.
442a
	cycrelease.when = 0;

.
441c
	DPRINT("%d edfreleaseintr\n", m->machno);
.
437c
edfreleaseintr(Ureg*, Cycintr*)
.
242,253d
237d
234,235d
231,232c
	if (cycrelease.when <= now)
.
229d
226,227c
	DPRINT("edfreleasetimer clock\n");
	if (cycrelease.when)
.
222,224c
	if ((t = qwaitrelease.head) == nil)
.
213a
	return nil;
.
76c
static void		edfreleaseintr(Ureg *, Cycintr *cy);
static void		edfdeadlineintr(Ureg*, Cycintr*);
.
71d
36,37c
QLock		edfschedlock;
.
## diffname port/edf.c 2002/0329
## diff -e /n/emeliedump/2002/0328/sys/src/9/port/edf.c /n/emeliedump/2002/0329/sys/src/9/port/edf.c
484a
		if (up->nlocks)
			iprint("have %lud locks at deadline\n", up->nlocks);
.
212d
208d
202d
193d
188d
178d
162d
157d
32d
## diffname port/edf.c 2002/0330
## diff -e /n/emeliedump/2002/0329/sys/src/9/port/edf.c /n/emeliedump/2002/0330/sys/src/9/port/edf.c
443a
	clockintrsched();
.
442a
	cycintrdel(&cycdeadline);
.
415a
	clockintrsched();
.
414a
	cycintrdel(&cycrelease);
.
## diffname port/edf.c 2002/0404
## diff -e /n/emeliedump/2002/0330/sys/src/9/port/edf.c /n/emeliedump/2002/0404/sys/src/9/port/edf.c
872d
480,481d
## diffname port/edf.c 2002/0405
## diff -e /n/emeliedump/2002/0404/sys/src/9/port/edf.c /n/emeliedump/2002/0405/sys/src/9/port/edf.c
749c
	timeradd(&cycdeadline);
.
746c
		timerdel(&cycdeadline);
.
445c
	timerdel(&cycdeadline);
.
436c
edfdeadlineintr(Ureg*, Timer*)
.
415c
	timerdel(&cycrelease);
.
409c
edfreleaseintr(Ureg*, Timer*)
.
274c
		timerdel(&cycdeadline);
.
221c
	timeradd(&cycrelease);
.
217c
		timerdel(&cycrelease);
.
73,74c
static void		edfreleaseintr(Ureg *, Timer *cy);
static void		edfdeadlineintr(Ureg*, Timer*);
.
29,30c
static Timer	cycdeadline;		/* Time of next deadline */
static Timer	cycrelease;		/* Time of next release */
.
## diffname port/edf.c 2002/0410
## diff -e /n/emeliedump/2002/0405/sys/src/9/port/edf.c /n/emeliedump/2002/0410/sys/src/9/port/edf.c
848c
edftestschedulability(Task *thetask)
.
748,750c
	deadlinetimer[m->machno].when = when;
	timeradd(&deadlinetimer[m->machno]);
.
746c
		timerdel(&deadlinetimer[m->machno]);
.
741,742c
	if (deadlinetimer[m->machno].when){
		if(deadlinetimer[m->machno].when == when){
.
738c
		DPRINT("%d edftimer: %T too late\n", m->machno, ticks2time(now-when));
.
717c
runt:
.
715c
		DPRINT("%d edfrunproc: current\n", m->machno);
.
707c
		DPRINT("%d edfrunproc: released\n", m->machno);
.
705a
		if (conf.nmach > 1){
			for (i = 0; i < conf.nmach; i++){
				if (i == m->machno)
					continue;
				xt = edfstack[i].head;
				if (xt && xt->Delta <= nt->D){
					DPRINT("%d edfrunproc: interprocessor conflict, run current\n", m->machno);
					if (t)
						goto runt;
					nilcount++;
					iunlock(&edflock);
					return nil;
				}
			}
		}
.
704c
	DPRINT("edfrunproc %lud\n", nilcount);
.
687a
	int i;
.
684c
	Task *t, *nt, *xt;
.
680c
edfrunproc(void)
.
668c
	DPRINT("%d edfrelease, %s, %d\n", m->machno, edfstatename[t->state], t->runq.n);
.
666c
edfrelease(Task *t)
.
646c
					DPRINT("%d edfresched, resume\n", m->machno);
.
641c
				edfrelease(t);
.
638c
				DPRINT("%d edfresched, rerelease\n", m->machno);
.
619c
					DPRINT("%d edfresched, resume\n", m->machno);
.
614c
				edfrelease(t);
.
609c
				DPRINT("%d edfresched, rerelease\n", m->machno);
.
592c
		edfrelease(t);
.
567c
		DPRINT("%d edfresched, nothing runnable\n", m->machno);
.
556c
	DPRINT("%d edfresched, %s, %d\n", m->machno, edfstatename[t->state], t->runq.n);
.
552c
edfresched(Task *t)
.
546c
		edfresched(t);
.
526c
	DPRINT("%d edfready, %s, %d\n", m->machno, edfstatename[p->task->state], p->task->runq.n);
.
521c
edfready(Proc *p)
.
492c
	DPRINT("%d edfbury\n", m->machno);
.
487c
edfbury(Proc *p)
.
476c
					deadline(nil, SSlice);
.
472c
				deadline(up, SSlice);
.
445,447c
	timerdel(&deadlinetimer[m->machno]);
	deadlinetimer[m->machno].when = 0;
.
428c
		edfrelease(t);
.
415,417c
	timerdel(&releasetimer[m->machno]);
	releasetimer[m->machno].when = 0;
.
365c
	DPRINT("%d edfexpel, %s, %d\n", m->machno, edfstatename[t->state], t->runq.n);
.
359c
edfexpel(Task *t)
.
347,349c
				edfresched(t);
.
345c
				edfrelease(t);
.
339a
		if (deadlinetimer[m->machno].when)
			timerdel(&deadlinetimer[m->machno]);
		deadlinetimer[m->machno].when = t->d;
		timeradd(&deadlinetimer[m->machno]);
.
327c
		DPRINT("%d edfadmitting self\n", m->machno);
.
321c
	DPRINT("%d edfadmit, %s, %d\n", m->machno, edfstatename[t->state], t->runq.n);
.
316c
	if (err = edftestschedulability(t)){
.
296c
edfadmit(Task *t)
.
291c
	deadline(p, SYield);
.
287c
	DPRINT("%d edfdeadline\n", m->machno);
.
285c
edfdeadline(Proc *p)
.
281c
	edfresched(t);
.
273,276c
	if (deadlinetimer[m->machno].when){
		timerdel(&deadlinetimer[m->machno]);
		deadlinetimer[m->machno].when = 0;
.
269c
		iprint("deadline, %s, %d\n", edfstatename[p->task->state], p->task->runq.n);
.
259c
	DPRINT("%d deadline, %s, %d\n", m->machno, edfstatename[p->task->state], p->task->runq.n);
.
254c
deadline(Proc *p, SEvent why)
.
239c
	DPRINT("%d edfblock, %s, %d\n", m->machno, edfstatename[t->state], t->runq.n);
.
226c
edfblock(Proc *p)
.
216,222c
	if (releasetimer[m->machno].when)
		timerdel(&releasetimer[m->machno]);
	releasetimer[m->machno].when = t->r;
	if (releasetimer[m->machno].when <= now)
		releasetimer[m->machno].when = now;
	timeradd(&releasetimer[m->machno]);
.
196c
	DPRINT("%d edfqremove, %s, %d\n", m->machno, edfstatename[t->state], t->runq.n);
.
156c
	DPRINT("%d edfenqueue, %s, %d\n", m->machno, edfstatename[t->state], t->runq.n);
.
117c
	DPRINT("%d edfpush, %s, %d\n", m->machno, edfstatename[t->state], t->runq.n);
.
104c
edfanyready(void)
.
87,92c
	for (i = 0; i < conf.nmach; i++){
		deadlinetimer[i].f = edfdeadlineintr;
		deadlinetimer[i].a = &deadlinetimer[i];
		deadlinetimer[i].when = 0;
		releasetimer[i].f = edfreleaseintr;
		releasetimer[i].a = &releasetimer[i];
		releasetimer[i].when = 0;
	}
.
78a
	int i;

.
77c
edfinit(void)
.
74a
static char *	edftestschedulability(Task *thetask);
.
72d
69c
static void		edfresched(Task *t);
.
61,63d
42c
int			edfstateupdate;
.
29,30c
static Timer	deadlinetimer[MAXMACH];	/* Time of next deadline */
static Timer	releasetimer[MAXMACH];		/* Time of next release */
.
15c
char *edfstatename[] = {
.
## diffname port/edf.c 2002/0411
## diff -e /n/emeliedump/2002/0410/sys/src/9/port/edf.c /n/emeliedump/2002/0411/sys/src/9/port/edf.c
688a
	if (edfstack[m->machno].head == nil && qreleased.head== nil){
		// quick way out
		nilcount++;
		return nil;
	}
.
107,110c
	return edfstack[m->machno].head || qreleased.head;
.
## diffname port/edf.c 2002/0420
## diff -e /n/emeliedump/2002/0411/sys/src/9/port/edf.c /n/emeliedump/2002/0420/sys/src/9/port/edf.c
467a
				if (t->S > 0LL)
					misseddeadlines++;
.
42a
int			misseddeadlines;
.
## diffname port/edf.c 2002/0503
## diff -e /n/emeliedump/2002/0420/sys/src/9/port/edf.c /n/emeliedump/2002/0503/sys/src/9/port/edf.c
743a
	t->periods++;
.
733a
		t->periods++;
.
731d
470a
				}
.
469c
				if (t->d <= now){
					t->missed++;
.
459a
		t->total += used;
.
332a
		t->periods++;
.
274a
	used = now - t->scheduled;
	t->S -= used;
	t->scheduled = now;
	t->total += used;
	t->aged = (t->aged*31 + t->C - t->S) >> 5;
.
254a
	Ticks used;
.
## diffname port/edf.c 2002/0704
## diff -e /n/emeliedump/2002/0503/sys/src/9/port/edf.c /n/emeliedump/2002/0704/sys/src/9/port/edf.c
963a

Edfinterface realedf = {
	.isedf		= isedf,
	.edfbury		= edfbury,
	.edfanyready	= edfanyready,
	.edfready		= edfready,
	.edfrunproc	= edfrunproc,
	.edfblock		= edfblock,
	.edfinit		= edfinit,
	.edfexpel		= edfexpel,
	.edfadmit		= edfadmit,
	.edfdeadline	= edfdeadline,
};
.
688c
static Proc *
.
674c
static void
.
529c
static void
.
495c
static void
.
364c
static void
.
298c
static char *
.
287c
static void
.
223c
static void
.
105c
static int
.
99c
static int
.
74c
static void
.
51a
static void	edfrelease(Task *t);
.
## diffname port/edf.c 2002/0831
## diff -e /n/emeliedump/2002/0704/sys/src/9/port/edf.c /n/emeliedump/2002/0831/sys/src/9/port/edf.c
922c
					steps, ticks2time(ticks), t->taskno,
.
911c
					steps, ticks2time(ticks), t->taskno,
.
896c
			pprint("\tInit: enqueue task %lud\n", t->taskno);
.
890c
	for (l = tasks.next; l; l = l->next){
		t = l->i;
		assert(t);
.
883a
	List *l;
.
843c
	for (lt = tasks.next; lt ; lt = lt->next){
		t = lt->i;
		assert(t);
.
840a
	List *lt;
.
830,832c
		for (lr = t->res.next; lr; lr = lr->next){
			r = lr->i;
			assert(r);
			if (r->testDelta < t->testDelta)
				t->testDelta = r->testDelta;
		}
.
826c
	for (lt = tasks.next; lt ; lt = lt->next){
		t = lt->i;
		assert(t);
.
822,824c
		for (lt = r->tasks.next; lt; lt = lt->next){
			t = lt->i;
			assert(t);
			if (t->D < r->testDelta)
				r->testDelta = t->D;
		}
.
818,820c
	for (lr = resources.next; lr; lr = lr->next){
		r = lr->i;
		assert(r);
.
815,816c
	Resource *r;
	Task *t;
	List *lr, *lt;
.
806,808c
		for (lr = t->res.next; lr; lr = lr->next){
			r = lr->i;
			assert(r);
			if (r->Delta < t->Delta)
				t->Delta = r->Delta;
		}
.
802c
	for (lt = tasks.next; lt ; lt = lt->next){
		t = lt->i;
		assert(t);
.
798,800c
		for (lt = r->tasks.next; lt; lt = lt->next){
			t = lt->i;
			assert(t);
			if (t->D < r->Delta)
				r->Delta = t->D;
		}
.
794,796c
	for (lr = resources.next; lr; lr = lr->next){
		r = lr->i;
		assert(r);
.
791,792c
	Resource *r;
	Task *t;
	List *lr, *lt;
.
567c
	if (t->procs.n == 0){
.
521c
	if (t->procs.n == 0){
.
512,516c
	delist(&t->procs, p);
.
500d
411d
379d
370c
	/* Called with edfschedlock held */
.
361c
	qlock(&edfschedlock);
.
324a
	qunlock(&edfschedlock);
.
321d
319d
303a
	/* Called with edfschedlock held */
.
38,41c
Head		tasks;
Head		resources;
.
34a
/* Edfschedlock protects modification of sched params, including resources */
.
## diffname port/edf.c 2002/0912
## diff -e /n/emeliedump/2002/0831/sys/src/9/port/edf.c /n/emeliedump/2002/0912/sys/src/9/port/edf.c
736d
## diffname port/edf.c 2002/0927
## diff -e /n/emeliedump/2002/0912/sys/src/9/port/edf.c /n/emeliedump/2002/0927/sys/src/9/port/edf.c
991a
	.resacquire	= resacquire,
	.resrelease	= resrelease,
.
974,978c
	c = t->curcsn;
	assert(c);
	t->curcsn = c->p;
	now = fastticks(nil);
	used = now - t->scheduled;
	t->scheduled = now;
	t->total += used;
	t->S -= used;
	c->S -= used;
	if (now + t->S > t->d)
		when = t->d;
	else
		when = now + t->S;
	if (t->curcsn){
		t->curcsn->S -= c->S;	/* the sins of the fathers shall be visited upon the children */
		t->Delta = t->curcsn->Delta;
		if (when > now + t->curcsn->S)
			when = now + t->curcsn->S;
	}else
		t->Delta = Infinity;
	c->S = 0LL;	/* don't allow reuse */
	if (deadlinetimer[m->machno].when)
		timerdel(&deadlinetimer[m->machno]);
	deadlinetimer[m->machno].when = when;
	timeradd(&deadlinetimer[m->machno]);

	qunlock(&edfschedlock);
	sched();	/* reschedule */
	qlock(&edfschedlock);
.
968,972c
	Ticks now, when, used;
	CSN *c;
.
965,966c
static void
resrelease(Task *t)
.
959,962c
	now = fastticks(nil);
	used = now - t->scheduled;
	t->scheduled = now;
	t->total += used;
	t->S -= used;
	if (t->curcsn)
		t->curcsn->S -= used;
	when = now + c->S;
	if (when < deadlinetimer[m->machno].when){
		timerdel(&deadlinetimer[m->machno]);
		deadlinetimer[m->machno].when = when;
		timeradd(&deadlinetimer[m->machno]);
	}
	t->Delta = c->Delta;
	t->curcsn = c;
	/* priority is going up, no need to reschedule */
.
956,957c
	Ticks now, when, used;
.
953,954c
static void
resacquire(Task *t, CSN *c)
.
940a
			}
.
939c
			if(ticks && G <= ticks){
				if (thetask && (thetask->flags & Verbose))
					pprint("task %d schedulable: G=%T <= ticks=%T\n",
						thetask->taskno, ticks2time(G), ticks2time(ticks));
.
936c
				pprint("\tStep %3d, Ticks %T, task %d, release, G  %T, C%T\n",
.
929a
			}
.
928c
			if (H+Cb>ticks){
				if (thetask && (thetask->flags & Verbose))
					pprint("task %d not schedulable: H=%T + Cb=%T > ticks=%T\n",
						thetask->taskno, ticks2time(H), ticks2time(Cb), ticks2time(ticks));
.
925c
				pprint("\tStep %3d, Ticks %T, task %d, deadline, H += %T → %T, Cb = %T\n",
.
923c
			Cb = blockcost(ticks, t, thetask);
.
911c
			pprint("\tInit: enqueue task %d\n", t->taskno);
.
901c
		pprint("schedulability test for task %d\n", thetask->taskno);
.
864,865d
860a
	DEBUG("Cb = %T\n", ticks2time(Cb));
.
853,859c
	/* for each resource in task t, find all CSNs that refer to the
	 * resource.  If their Δ <= ticks < D and c->C > current CB
	 * Cb = c->C
	 */
	DEBUG("blockcost task %d: ", task->taskno);
	for (c = (CSN*)task->csns.next; c; c = (CSN*)c->next){
		r = c->i;
		assert(r);

		DEBUG("%s ", r->name);
		Cbt = Cb;
		R = 1;	/* R == 1: resource is only used in read-only mode  */
		for (l = tasks.next; l; l = l->next){
			t = l->i;
			if (t->state <= EdfExpelled && t != thetask)
				continue;	/* csn belongs to an irrelevant task */
			for (lc = (CSN*)t->csns.next; lc; lc = (CSN*)lc->next){
				if (lc->i != r)
					continue;	/* wrong resource */
				if (lc->R == 0)
					R = 0;	/* Resource is used in exclusive mode */
				DEBUG("(%T≤%T<%T: %T) ",
					ticks2time(lc->testDelta), ticks2time(ticks), ticks2time(t->D),
					ticks2time(lc->C));
				if (lc->testDelta <= ticks && ticks < t->D && Cbt < lc->C)
					Cbt = lc->C;
			}
		}
		if (R == 0){
			DEBUG("%T, ", ticks2time(Cbt));
			Cb = Cbt;
		}
		DEBUG("ro, ");
.
849,850d
847a
	Ticks Cb, Cbt;
	List *l;
	Resource *r;
	CSN *c, *lc;
	int R;
.
846c
blockcost(Ticks ticks, Task *task, Task *thetask)
.
840a
			DEBUG("Task %d Resource %s: tΔ = %T\n",
				t->taskno, r->name, ticks2time(r->testDelta));
.
839c
			c->testDelta = r->testDelta;
			if (c->p && c->p->testDelta < c->testDelta)
				c->testDelta = c->p->testDelta;
			if (c->C == t->C && r->testDelta < t->testDelta)
.
835,837c
		t->testDelta = Infinity;
		for (c = (CSN*)t->csns.next; c; c = (CSN*)c->next){
			r = c->i;
.
830,831c

	/* Enumerate the critical sections */
	for (l = tasks.next; l ; l = l->next){
		t = l->i;
.
828a
		if (R)
			r->testDelta = Infinity;	/* Read-only resource, no exclusion */
		DEBUG("tΔ = %T\n", ticks2time(r->testDelta));
.
827a
				DEBUG("%d→%T ", t->taskno, ticks2time(t->D));
			}
			if (lt->R == 0){
				DEBUG("%d→X ", t->taskno);
				R = 0;
			}
.
826c
			if (t->D < r->testDelta){
.
822,823c
		DEBUG("Resource %s: ", r->name);
		r->testDelta = Infinity;
		R = 1;
		for (lt = (TaskLink*)r->tasks.next; lt; lt = (TaskLink*)lt->next){
.
817c
	int R;
	List *lr, *l;
	TaskLink *lt;
	CSN *c;
.
806c
			c->Delta = r->Delta;
			if (c->p && c->p->Delta < c->Delta)
				c->Delta = c->p->Delta;
			if (c->C == t->C && r->Delta < t->Delta)
.
802,804c
		t->Delta = Infinity;
		for (c = (CSN*)t->csns.next; c; c = (CSN*)c->next){
			r = c->i;
.
800c
		if (t->state <= EdfExpelled)
.
797,798c

	/* Enumerate the critical sections */
	for (l = tasks.next; l ; l = l->next){
		t = l->i;
.
795a
		if (R)
			r->Delta = Infinity;	/* Read-only resource, no exclusion */
.
794a
			}
			if (lt->R == 0){
				R = 0;
			}
.
793c
			if (t->D < r->Delta){
.
789,790c
		r->Delta = Infinity;
		R = 1;
		for (lt = (TaskLink*)r->tasks.next; lt; lt = (TaskLink*)lt->next){
.
784c
	int R;
	List *lr, *l;
	TaskLink *lt;
	CSN *c;
.
675a
	for (c = (CSN*)t->csns.next; c; c = (CSN*)c->next){
		DEBUG("release csn: C=%T\n", ticks2time(c->C));
		c->S = c->C;
	}
.
669a
	CSN *c;

.
488a
	if (noted)
		postnote(up, 1, buf, NUser);
.
479a

.
472,473c

			if (t->d <= now || t->S == 0LL || t->curcsn == 0LL){
.
470c
				if (!noted){
					noted++;
					snprint(buf, sizeof buf, "sys: deadline miss: runtime");
				}
			}else
.
468c
			if (t->curcsn){
				if (t->curcsn->S <= used){
					t->curcsn->S = 0LL;
					r = t->curcsn->i;
					noted++;
					snprint(buf, sizeof buf, "sys: deadline miss: resource %s", r->name);
				}else
					t->curcsn->S -= used;
			}

			if (t->S <= used){
.
456c
	// for non-real-time processes.
	noted = 0;
.
451c
	if(panicking || active.exiting)
.
444a
	Resource *r;
	char buf[128];
	int noted;
	extern int panicking;
.
422c
	if(panicking || active.exiting)
.
415a
	extern int panicking;
.
360d
341a
		for (c = (CSN*)t->csns.next; c; c = (CSN*)c->next){
			DEBUG("admit csn: C=%T\n", ticks2time(c->C));
			c->S = c->C;
		}
.
323d
318a
	resourcetimes(t, &t->csns);

	DEBUG("task %d: T %T, C %T, D %T, tΔ %T\n",
		t->taskno, ticks2time(t->T), ticks2time(t->C),
		ticks2time(t->D), ticks2time(t->testDelta));
	p = seprintresources(csndump, csndump+sizeof csndump);
	seprintcsn(p, csndump+sizeof csndump, &t->csns);
	DEBUG("%s\n", csndump);

.
301c
	char *err, *p;
	static char csndump[512];
	CSN *c;
.
86d
64a
static Task *qschedulability;

.
33d
8,9c
#include	"../port/realtime.h"
.
## diffname port/edf.c 2002/1001
## diff -e /n/emeliedump/2002/0927/sys/src/9/port/edf.c /n/emeliedump/2002/1001/sys/src/9/port/edf.c
1115a
	if(devrt) devrt(t, now, SResrel);
.
1085a
	if(devrt) devrt(t, now, SResacq);
.
488a
					resrelease(t);
.
465,466c
	if (timer)
		timer->when = 0;
.
452c
edfdeadlineintr(Ureg*, Timer *timer)
.
72c
static char *	edftestschedulability(Task*);
static void		resrelease(Task*);
.
69,70c
static void		testdelta(Task*);
static void		edfreleaseintr(Ureg*, Timer*);
.
67c
static void		edfresched(Task*);
.
## diffname port/edf.c 2002/1119
## diff -e /n/emeliedump/2002/1001/sys/src/9/port/edf.c /n/emeliedump/2002/1119/sys/src/9/port/edf.c
8c
#include	"realtime.h"
#include	"../port/edf.h"
.
## diffname port/edf.c 2002/1217
## diff -e /n/emeliedump/2002/1119/sys/src/9/port/edf.c /n/emeliedump/2002/1217/sys/src/9/port/edf.c
776c
		assert(nt->runq.n >= 1 || (up && up->task == nt));
.
740a

.
## diffname port/edf.c 2002/1218
## diff -e /n/emeliedump/2002/1217/sys/src/9/port/edf.c /n/emeliedump/2002/1218/sys/src/9/port/edf.c
1122,1123d
1084d
809,814c
	if(deadlinetimer[m->machno].when == when){
		iunlock(&edflock);
		return p;
.
480a

		assert(t->state == EdfRunning);
.
359,360d
216,217d
## diffname port/edf.c 2002/1219
## diff -e /n/emeliedump/2002/1218/sys/src/9/port/edf.c /n/emeliedump/2002/1219/sys/src/9/port/edf.c
1078c
	if (deadlinetimer[m->machno].when == 0 || when < deadlinetimer[m->machno].when){
.
474,475d
468a
	now = fastticks(nil);
.
463,465d
450c
edfdeadlineintr(Ureg*, Timer *)
.
437a
	ilock(&edflock);
.
436d
430,432d
## diffname port/edf.c 2003/0201
## diff -e /n/emeliedump/2002/1219/sys/src/9/port/edf.c /n/emeliedump/2003/0201/sys/src/9/port/edf.c
517c
		postnote(up, 0, buf, NUser);
.