2002/0330/port/edf.c (diff list | history)

2002/0315/sys/src/9/port/edf.c:5,11 – 2002/0316/sys/src/9/port/edf.c:5,11 (short | long)
2002/0315		#include "dat.h" #include "fns.h" #include "../port/error.h" #include "../port/devsched.h"
2002/0316		#include "../port/devrealtime.h"
2002/0315		#include "../port/edf.h" /* debugging */
2002/0315/sys/src/9/port/edf.c:68,74 – 2002/0316/sys/src/9/port/edf.c:68,74
2002/0315		/* Running/Preempted EDF tasks, head running, one stack per processor */ Taskq edfstack[MAXMACH]; void (*devsched)(Task*, Ticks, int);
2002/0316		void (*devrt)(Task*, Ticks, int);
2002/0315		static void edf_intr(Ureg*, Cycintr*); static void edf_resched(Task *t);
2002/0315/sys/src/9/port/edf.c:115,130 – 2002/0316/sys/src/9/port/edf.c:115,130
2002/0315		{ Taskq *q; DENTER("%.*sedfpush, %s, %d\n", ind, tabs, edf_statename[t->state], t->runq.n);
2002/0316		DENTER("%.*s%d edfpush, %s, %d\n", ind, tabs, m->machno, edf_statename[t->state], t->runq.n);
2002/0315		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);
2002/0316		if(devrt) devrt(q->head, now, SPreempt);
2002/0315		} t->rnext = q->head; if(devsched) devsched(t, now, SRun);
2002/0316		if(devrt) devrt(t, now, SRun);
2002/0315		q->head = t; DLEAVE; }
2002/0315/sys/src/9/port/edf.c:135,141 – 2002/0316/sys/src/9/port/edf.c:135,141
2002/0315		Task *t; Taskq *q; DENTER("%.*sedfpop\n", ind, tabs);
2002/0316		DENTER("%.*s%d edfpop\n", ind, tabs, m->machno);
2002/0315		q = edfstack + m->machno; if (t = q->head){ assert(t->state == EdfRunning);
2002/0315/sys/src/9/port/edf.c:144,150 – 2002/0316/sys/src/9/port/edf.c:144,150
2002/0315		if (q->head){ assert(q->head->state == EdfPreempted); q->head->state = EdfRunning; if(devsched) devsched(q->head, now, SRun);
2002/0316		if(devrt) devrt(q->head, now, SRun);
2002/0315		} } DLEAVE;
2002/0315/sys/src/9/port/edf.c:157,163 – 2002/0316/sys/src/9/port/edf.c:157,163
2002/0315		Task *tt, **ttp; ilock(q); DENTER("%.*sedfenqueue, %s, %d\n", ind, tabs, edf_statename[t->state], t->runq.n);
2002/0316		DENTER("%.*s%d edfenqueue, %s, %d\n", ind, tabs, m->machno, edf_statename[t->state], t->runq.n);
2002/0315		t->rnext = nil; if (q->head == nil) { q->head = t;
2002/0315/sys/src/9/port/edf.c:188,194 – 2002/0316/sys/src/9/port/edf.c:188,194
2002/0315		{ Task *t; DENTER("%.*sedfdequeue\n", ind, tabs);
2002/0316		DENTER("%.*s%d edfdequeue\n", ind, tabs, m->machno);
2002/0315		ilock(q); if (t = q->head){ q->head = t->rnext;
2002/0315/sys/src/9/port/edf.c:205,211 – 2002/0316/sys/src/9/port/edf.c:205,211
2002/0315		Task **tp; ilock(q); DENTER("%.*sedfqremove, %s, %d\n", ind, tabs, edf_statename[t->state], t->runq.n);
2002/0316		DENTER("%.*s%d edfqremove, %s, %d\n", ind, tabs, m->machno, edf_statename[t->state], t->runq.n);
2002/0315		for (tp = &q->head; *tp; tp = &(*tp)->rnext){ if (*tp == t){ *tp = t->rnext;
2002/0315/sys/src/9/port/edf.c:226,232 – 2002/0316/sys/src/9/port/edf.c:226,232
2002/0315		/* 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);
2002/0316		DENTER("%.*s%d edf_block, %s, %d\n", ind, tabs, m->machno, edf_statename[t->state], t->runq.n);
2002/0315		assert(t); assert(t->state == EdfRunning);
2002/0315/sys/src/9/port/edf.c:239,245 – 2002/0316/sys/src/9/port/edf.c:239,245
2002/0315		pt = edfpop(); assert(pt == t); t->state = EdfBlocked; if(devsched) devsched(t, now, SBlock);
2002/0316		if(devrt) devrt(t, now, SBlock);
2002/0315		DLEAVE; iunlock(&edflock); }
2002/0315/sys/src/9/port/edf.c:250,256 – 2002/0316/sys/src/9/port/edf.c:250,256
2002/0315		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);
2002/0316		DENTER("%.*s%d edfdeadline, %s, %d\n", ind, tabs, m->machno, edf_statename[p->task->state], p->task->runq.n);
2002/0315		SET(nt); if (p){ nt = p->task;
2002/0315/sys/src/9/port/edf.c:260,266 – 2002/0316/sys/src/9/port/edf.c:260,266
2002/0315		t = edfpop(); if(p != nil && nt != t){ DPRINT("%.*sedfdeadline, %s, %d\n", ind, tabs, edf_statename[p->task->state], p->task->runq.n);
2002/0316		DPRINT("%.*s%d edfdeadline, %s, %d\n", ind, tabs, m->machno, edf_statename[p->task->state], p->task->runq.n);
2002/0315		iunlock(&edflock); assert(0 && p == nil || nt == t); }
2002/0315/sys/src/9/port/edf.c:267,273 – 2002/0316/sys/src/9/port/edf.c:267,273
2002/0315		t->d = now; t->state = EdfDeadline; if(devsched) devsched(t, now, why);
2002/0316		if(devrt) devrt(t, now, why);
2002/0315		edf_resched(t); DLEAVE; }
2002/0315/sys/src/9/port/edf.c:275,281 – 2002/0316/sys/src/9/port/edf.c:275,281
2002/0315		void edf_deadline(Proc *p) { DENTER("%.*sedf_deadline\n", ind, tabs);
2002/0316		DENTER("%.*s%d edf_deadline\n", ind, tabs, m->machno);
2002/0315		/* Task has reached its deadline */ ilock(&edflock); now = fastticks(nil);
2002/0315/sys/src/9/port/edf.c:291,296 – 2002/0316/sys/src/9/port/edf.c:291,309
2002/0315		if (t->state != EdfExpelled) return "task state"; /* should never happen */
2002/0316		/* 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";
2002/0315		qlock(&edfschedlock); if (err = edf_testschedulability(t)){ qunlock(&edfschedlock);
2002/0315/sys/src/9/port/edf.c:297,317 – 2002/0316/sys/src/9/port/edf.c:310,331
2002/0315		return err; } ilock(&edflock); DENTER("%.*sedf_admit, %s, %d\n", ind, tabs, edf_statename[t->state], t->runq.n);
2002/0316		DENTER("%.*s%d edf_admit, %s, %d\n", ind, tabs, m->machno, edf_statename[t->state], t->runq.n);
2002/0315		now = fastticks(nil); t->state = EdfAdmitted;
2002/0316		if(devrt) devrt(t, t->d, SAdmit);
2002/0315		if (up->task == t){ DPRINT("%.*sedf_admitting self\n", ind, tabs);
2002/0316		DPRINT("%.*s%d edf_admitting self\n", ind, tabs, m->machno);
2002/0315		/* 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);
2002/0316		if(devrt) devrt(t, t->d, SDeadline);
2002/0315		t->S = t->C; t->scheduled = now; t->state = EdfRunning; if(devsched) devsched(t, now, SRun);
2002/0316		if(devrt) devrt(t, now, SRun);
2002/0315		setΔ(); assert(t->runq.n > 0 || (up && up->task == t)); edfpush(t);
2002/0315/sys/src/9/port/edf.c:342,348 – 2002/0316/sys/src/9/port/edf.c:356,362
2002/0315		qlock(&edfschedlock); ilock(&edflock); DENTER("%.*sedf_expel, %s, %d\n", ind, tabs, edf_statename[t->state], t->runq.n);
2002/0316		DENTER("%.*s%d edf_expel, %s, %d\n", ind, tabs, m->machno, edf_statename[t->state], t->runq.n);
2002/0315		now = fastticks(nil); switch(t->state){ case EdfUnused:
2002/0315/sys/src/9/port/edf.c:378,384 – 2002/0316/sys/src/9/port/edf.c:392,398
2002/0315		break; } t->state = EdfExpelled; if(devsched) devsched(t, now, SExpel);
2002/0316		if(devrt) devrt(t, now, SExpel);
2002/0315		setΔ(); DLEAVE; iunlock(&edflock);
2002/0315/sys/src/9/port/edf.c:432,438 – 2002/0316/sys/src/9/port/edf.c:446,452
2002/0315		Ticks ticks; Task *t; DENTER("%.*sedf_setclock\n", ind, tabs);
2002/0316		DENTER("%.*s%d edf_setclock\n", ind, tabs, m->machno);
2002/0315		ticks = ~0ULL; if ((t = qwaitrelease.head) && t->r < ticks) ticks = t->r;
2002/0315/sys/src/9/port/edf.c:447,465 – 2002/0316/sys/src/9/port/edf.c:461,479
2002/0315		return; } if (schedpoint.when){ DPRINT("%.*scycintrdel %T\n", ind, tabs, ticks2time(schedpoint.when));
2002/0316		DPRINT("%.*s%d cycintrdel %T\n", ind, tabs, m->machno, ticks2time(schedpoint.when));
2002/0315		cycintrdel(&schedpoint); schedpoint.when = 0; } if (ticks <= now){ DPRINT("%.*sedf_timer: %T too late\n", ind, tabs, ticks2time(now-ticks));
2002/0316		DPRINT("%.*s%d edf_timer: %T too late\n", ind, tabs, m->machno, ticks2time(now-ticks));
2002/0315		ticks = now; } if (ticks != ~0ULL) { DPRINT("%.*sprogram timer in %T\n", ind, tabs, ticks2time(ticks-now));
2002/0316		DPRINT("%.*s%d program timer in %T\n", ind, tabs, m->machno, ticks2time(ticks-now));
2002/0315		schedpoint.when = ticks; cycintradd(&schedpoint); DPRINT("%.*scycintradd %T\n", ind, tabs, ticks2time(schedpoint.when-now));
2002/0316		DPRINT("%.*s%d cycintradd %T\n", ind, tabs, m->machno, ticks2time(schedpoint.when-now));
2002/0315		} clockintrsched(); DLEAVE;
2002/0315/sys/src/9/port/edf.c:469,475 – 2002/0316/sys/src/9/port/edf.c:483,489
2002/0315		edf_intr(Ureg *, Cycintr *cy) { DENTER("%.*sedf_intr\n", ind, tabs);
2002/0316		DENTER("%.*s%d edf_intr\n", ind, tabs, m->machno);
2002/0315		/* Timer interrupt * Timed events are: * 1. release a task (look in qwaitrelease)
2002/0315/sys/src/9/port/edf.c:497,509 – 2002/0316/sys/src/9/port/edf.c:511,523
2002/0315		Task *t; Proc **pp; DPRINT("%.*sedf_bury\n", ind, tabs);
2002/0316		DPRINT("%.*s%d edf_bury\n", ind, tabs, m->machno);
2002/0315		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);
2002/0316		DPRINT("%.*s%d edf bury race, pid %lud\n", ind, tabs, m->machno, p->pid);
2002/0315		return; } assert(edfstack[m->machno].head == t);
2002/0315/sys/src/9/port/edf.c:520,526 – 2002/0316/sys/src/9/port/edf.c:534,540
2002/0315		assert(t->runq.head == nil); t->state = EdfIdle; } if(devsched) devsched(t, now, SBlock);
2002/0316		if(devrt) devrt(t, now, SBlock);
2002/0315		p->task = nil; iunlock(&edflock); }
2002/0315/sys/src/9/port/edf.c:531,541 – 2002/0316/sys/src/9/port/edf.c:545,555
2002/0315		Task *t; ilock(&edflock); DENTER("%.*sedf_ready, %s, %d\n", ind, tabs, edf_statename[p->task->state], p->task->runq.n);
2002/0316		DENTER("%.*s%d edf_ready, %s, %d\n", ind, tabs, m->machno, edf_statename[p->task->state], p->task->runq.n);
2002/0315		if ((t = p->task) == nil){ /* Must be a race */ iunlock(&edflock); DPRINT("%.*sedf ready race, pid %lud\n", ind, tabs, p->pid);
2002/0316		DPRINT("%.*s%d edf ready race, pid %lud\n", ind, tabs, m->machno, p->pid);
2002/0315		return; } p->rnext = 0;
2002/0315/sys/src/9/port/edf.c:562,573 – 2002/0316/sys/src/9/port/edf.c:576,587
2002/0315		{ Task *xt; DENTER("%.*sedf_resched, %s, %d\n", ind, tabs, edf_statename[t->state], t->runq.n);
2002/0316		DENTER("%.*s%d edf_resched, %s, %d\n", ind, tabs, m->machno, edf_statename[t->state], t->runq.n);
2002/0315		if (t->nproc == 0){ /* No member processes */ if (t->state > EdfIdle){ t->state = EdfIdle; if(devsched) devsched(t, now, SBlock);
2002/0316		if(devrt) devrt(t, now, SBlock);
2002/0315		} DLEAVE; return;
2002/0315/sys/src/9/port/edf.c:574,586 – 2002/0316/sys/src/9/port/edf.c:588,600
2002/0315		} if (t->runq.n == 0 && (up == nil || up->task != t)){ /* Member processes but none runnable */ DPRINT("%.*sedf_resched, nothing runnable\n", ind, tabs);
2002/0316		DPRINT("%.*s%d edf_resched, nothing runnable\n", ind, tabs, m->machno);
2002/0315		if (t->state == EdfRunning) edfpop(); if (t->state >= EdfIdle && t->state != EdfBlocked){ t->state = EdfBlocked; if(devsched) devsched(t, now, SBlock);
2002/0316		if(devrt) devrt(t, now, SBlock);
2002/0315		} DLEAVE; return;
2002/0315/sys/src/9/port/edf.c:590,596 – 2002/0316/sys/src/9/port/edf.c:604,610
2002/0315		switch (t->state){ case EdfUnused: iprint("%.*sattempt to schedule unused task\n", ind, tabs);
2002/0316		iprint("%.*s%d attempt to schedule unused task\n", ind, tabs, m->machno);
2002/0315		case EdfExpelled: DLEAVE; return; /* Not admitted */
2002/0315/sys/src/9/port/edf.c:619,625 – 2002/0316/sys/src/9/port/edf.c:633,639
2002/0315		case EdfRunning: if (t->r <= now){ if (t->t < now){ DPRINT("%.*sedf_resched, rerelease\n", ind, tabs);
2002/0316		DPRINT("%.*s%d edf_resched, rerelease\n", ind, tabs, m->machno);
2002/0315		/* Period passed, rerelease */ t->r = now; xt = edfpop();
2002/0315/sys/src/9/port/edf.c:630,636 – 2002/0316/sys/src/9/port/edf.c:644,650
2002/0315		} if (now < t->d){ if (t->S > 0){ DPRINT("%.*sedf_resched, resume\n", ind, tabs);
2002/0316		DPRINT("%.*s%d edf_resched, resume\n", ind, tabs, m->machno);
2002/0315		/* Running, not yet at deadline, leave it */ DLEAVE; return;
2002/0315/sys/src/9/port/edf.c:640,646 – 2002/0316/sys/src/9/port/edf.c:654,660
2002/0315		/* Released, but deadline is past, release at t->t */ t->r = t->t; } DPRINT("%.*sedf_resched, schedule release\n", ind, tabs);
2002/0316		DPRINT("%.*s%d edf_resched, schedule release\n", ind, tabs, m->machno);
2002/0315		xt = edfpop(); assert(xt == t); edfenqueue(&qwaitrelease, t);
2002/0315/sys/src/9/port/edf.c:651,657 – 2002/0316/sys/src/9/port/edf.c:665,671
2002/0315		case EdfDeadline: if (t->r <= now){ if (t->t < now){ DPRINT("%.*sedf_resched, rerelease\n", ind, tabs);
2002/0316		DPRINT("%.*s%d edf_resched, rerelease\n", ind, tabs, m->machno);
2002/0315		/* Period passed, rerelease */ t->r = now; edf_release(t);
2002/0315/sys/src/9/port/edf.c:660,670 – 2002/0316/sys/src/9/port/edf.c:674,684
2002/0315		} if (now < t->d && (t->flags & Useblocking) == 0){ if (t->S > 0){ DPRINT("%.*sedf_resched, resume\n", ind, tabs);
2002/0316		DPRINT("%.*s%d edf_resched, resume\n", ind, tabs, m->machno);
2002/0315		/* Released, not yet at deadline, release (again) */ t->state = EdfReleased; edfenqueue(&qreleased, t); if(devsched) devsched(t, now, SResume);
2002/0316		if(devrt) devrt(t, now, SResume);
2002/0315		DLEAVE; return; }else
2002/0315/sys/src/9/port/edf.c:673,679 – 2002/0316/sys/src/9/port/edf.c:687,693
2002/0315		/* Released, but deadline is past, release at t->t */ t->r = t->t; } DPRINT("%.*sedf_resched, schedule release\n", ind, tabs);
2002/0316		DPRINT("%.*s%d edf_resched, schedule release\n", ind, tabs, m->machno);
2002/0315		edfenqueue(&qwaitrelease, t); t->state = EdfAwaitrelease; edf_setclock();
2002/0315/sys/src/9/port/edf.c:685,699 – 2002/0316/sys/src/9/port/edf.c:699,713
2002/0315		void edf_release(Task *t) { DENTER("%.*sedf_release, %s, %d\n", ind, tabs, edf_statename[t->state], t->runq.n);
2002/0316		DENTER("%.*s%d edf_release, %s, %d\n", ind, tabs, m->machno, edf_statename[t->state], t->runq.n);
2002/0315		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);
2002/0316		if(devrt) devrt(t, t->d, SDeadline);
2002/0315		t->S = t->C; t->state = EdfReleased; edfenqueue(&qreleased, t); if(devsched) devsched(t, now, SRelease);
2002/0316		if(devrt) devrt(t, now, SRelease);
2002/0315		edf_setclock(); DLEAVE; }
2002/0315/sys/src/9/port/edf.c:727,733 – 2002/0316/sys/src/9/port/edf.c:741,747
2002/0315		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);
2002/0316		DPRINT("%.*s%d edf_runproc: released\n", ind, tabs, m->machno);
2002/0315		edfdequeue(&qreleased); assert(nt->runq.n >= 1); edfpush(nt);
2002/0315/sys/src/9/port/edf.c:735,741 – 2002/0316/sys/src/9/port/edf.c:749,755
2002/0315		t = nt; t->scheduled = now; }else{ DPRINT("%.*sedf_runproc: current\n", ind, tabs);
2002/0316		DPRINT("%.*s%d edf_runproc: current\n", ind, tabs, m->machno);
2002/0315		} assert (t->runq.n);
2002/0316/sys/src/9/port/edf.c:777,782 – 2002/0319/sys/src/9/port/edf.c:777,784 (short | long)
2002/0315		int edf_waitlock(Lock *l) {
2002/0319		Task *t;
2002/0315		iprint("edf_waitlock\n"); ilock(&waitlock); /* can't afford normal locks here */ if (l->key == 0){
2002/0319/sys/src/9/port/edf.c:72,79 – 2002/0320/sys/src/9/port/edf.c:72,79 (short | long)
2002/0315		static void edf_intr(Ureg*, Cycintr*); static void edf_resched(Task *t); static void setΔ(void); static void testΔ(Task *thetask);
2002/0320		static void setdelta(void); static void testdelta(Task *thetask);
2002/0315		static char * edf_testschedulability(Task *thetask); static void edf_setclock(void);
2002/0319/sys/src/9/port/edf.c:226,235 – 2002/0320/sys/src/9/port/edf.c:226,239
2002/0315		/* The current proc has blocked */ ilock(&edflock); t = p->task;
2002/0320		assert(t); if (t->state != EdfRunning){ /* called by a proc just joining the task */ iunlock(&edflock); return; }
2002/0316		DENTER("%.*s%d edf_block, %s, %d\n", ind, tabs, m->machno, edf_statename[t->state], t->runq.n);
2002/0315		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);
2002/0319/sys/src/9/port/edf.c:255,266 – 2002/0320/sys/src/9/port/edf.c:259,269
2002/0315		if (p){ nt = p->task; assert(nt); assert(nt->state == EdfRunning); } t = edfpop(); if(p != nil && nt != t){
2002/0316		DPRINT("%.*s%d edfdeadline, %s, %d\n", ind, tabs, m->machno, edf_statename[p->task->state], p->task->runq.n);
2002/0320		iprint("edfdeadline, %s, %d\n", edf_statename[p->task->state], p->task->runq.n);
2002/0315		iunlock(&edflock); assert(0 && p == nil || nt == t); }
2002/0319/sys/src/9/port/edf.c:326,332 – 2002/0320/sys/src/9/port/edf.c:329,335
2002/0315		t->scheduled = now; t->state = EdfRunning;
2002/0316		if(devrt) devrt(t, now, SRun);
2002/0315		setΔ();
2002/0320		setdelta();
2002/0315		assert(t->runq.n > 0 || (up && up->task == t)); edfpush(t); edf_setclock();
2002/0319/sys/src/9/port/edf.c:336,342 – 2002/0320/sys/src/9/port/edf.c:339,345
2002/0315		t->state = EdfAdmitted; t->r = now; edf_release(t); setΔ();
2002/0320		setdelta();
2002/0315		edf_resched(t); }else{ edfenqueue(&qadmit, t);
2002/0319/sys/src/9/port/edf.c:393,399 – 2002/0320/sys/src/9/port/edf.c:396,402
2002/0315		} t->state = EdfExpelled;
2002/0316		if(devrt) devrt(t, now, SExpel);
2002/0315		setΔ();
2002/0320		setdelta();
2002/0315		DLEAVE; iunlock(&edflock); qunlock(&edfschedlock);
2002/0319/sys/src/9/port/edf.c:739,745 – 2002/0320/sys/src/9/port/edf.c:742,748
2002/0315		return nil; } DENTER("edf_runproc %lud\n", nilcount); if (nt && (t == nil || (nt->D < t->Δ && nt->d < t->d))){
2002/0320		if (nt && (t == nil || (nt->d < t->d && nt->D < t->Delta))){
2002/0315		/* released task is better than current */
2002/0316		DPRINT("%.*s%d edf_runproc: released\n", ind, tabs, m->machno);
2002/0315		edfdequeue(&qreleased);
2002/0319/sys/src/9/port/edf.c:777,784 – 2002/0320/sys/src/9/port/edf.c:780,785
2002/0315		int edf_waitlock(Lock *l) {
2002/0319		Task *t;
2002/0315		iprint("edf_waitlock\n"); ilock(&waitlock); /* can't afford normal locks here */ if (l->key == 0){
2002/0319/sys/src/9/port/edf.c:820,826 – 2002/0320/sys/src/9/port/edf.c:821,827
2002/0315		/* Schedulability testing and its supporting routines */ static void setΔ(void)
2002/0320		setdelta(void)
2002/0315		{ Resource *r, **rr; Task **tt, *t;
2002/0319/sys/src/9/port/edf.c:828,850 – 2002/0320/sys/src/9/port/edf.c:829,851
2002/0315		for (r = resources; r < resources + nelem(resources); r++){ if (r->name == nil) continue; r->Δ = ~0LL;
2002/0320		r->Delta = ~0LL;
2002/0315		for (tt = r->tasks; tt < r->tasks + nelem(r->tasks); tt++) if (*tt && (*tt)->D < r->Δ) r->Δ = (*tt)->D;
2002/0320		if (*tt && (*tt)->D < r->Delta) r->Delta = (*tt)->D;
2002/0315		} for (t = tasks; t < tasks + nelem(tasks); t++){ if (t->state < EdfIdle) continue; t->Δ = t->D;
2002/0320		t->Delta = t->D;
2002/0315		for (rr = t->res; rr < t->res + nelem(t->res); rr++) if (*rr && (*rr)->Δ < t->Δ) t->Δ = (*rr)->Δ;
2002/0320		if (*rr && (*rr)->Delta < t->Delta) t->Delta = (*rr)->Delta;
2002/0315		} } static void testΔ(Task *thetask)
2002/0320		testdelta(Task *thetask)
2002/0315		{ Resource *r, **rr; Task **tt, *t;
2002/0319/sys/src/9/port/edf.c:852,869 – 2002/0320/sys/src/9/port/edf.c:853,870
2002/0315		for (r = resources; r < resources + nelem(resources); r++){ if (r->name == nil) continue; r->testΔ = ~0ULL;
2002/0320		r->testDelta = ~0ULL;
2002/0315		for (tt = r->tasks; tt < r->tasks + nelem(r->tasks); tt++) if (*tt && (*tt)->D < r->testΔ) r->testΔ = (*tt)->D;
2002/0320		if (*tt && (*tt)->D < r->testDelta) r->testDelta = (*tt)->D;
2002/0315		} for (t = tasks; t < tasks + nelem(tasks); t++){ if (t->state <= EdfExpelled && t != thetask) continue; t->testΔ = t->D;
2002/0320		t->testDelta = t->D;
2002/0315		for (rr = t->res; rr < t->res + nelem(t->res); rr++) if (*rr && (*rr)->testΔ < t->testΔ) t->testΔ = (*rr)->testΔ;
2002/0320		if (*rr && (*rr)->testDelta < t->testDelta) t->testDelta = (*rr)->testDelta;
2002/0315		} }
2002/0319/sys/src/9/port/edf.c:877,883 – 2002/0320/sys/src/9/port/edf.c:878,884
2002/0315		for (t = tasks; t < tasks + Maxtasks; t++){ if (t->state <= EdfExpelled && t != thetask) continue; if (t->testΔ <= ticks && ticks < t->D && Cb < t->C)
2002/0320		if (t->testDelta <= ticks && ticks < t->D && Cb < t->C)
2002/0315		Cb = t->C; } return Cb;
2002/0319/sys/src/9/port/edf.c:917,923 – 2002/0320/sys/src/9/port/edf.c:918,924
2002/0315		int steps; /* initialize */ testΔ(thetask);
2002/0320		testdelta(thetask);
2002/0315		if (thetask && (thetask->flags & Verbose)) pprint("schedulability test\n"); qschedulability = nil;
2002/0319/sys/src/9/port/edf.c:986,991 – 2002/0320/sys/src/9/port/edf.c:987,994
2002/0315		ticks2time(Ticks ticks) { assert(ticks >= 0);
2002/0320		if (fasthz == 0) fastticks(&fasthz);
2002/0315		return uvmuldiv(ticks, Onesecond, fasthz); }
2002/0320/sys/src/9/port/edf.c:258,264 – 2002/0321/sys/src/9/port/edf.c:258,265 (short | long)
2002/0315		SET(nt); if (p){ nt = p->task; assert(nt);
2002/0321		if (nt == nil || nt->state != EdfRunning) return;
2002/0315		} t = edfpop();
2002/0321/sys/src/9/port/edf.c:10,20 – 2002/0322/sys/src/9/port/edf.c:10,16 (short | long)
2002/0315		/* 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",
2002/0321/sys/src/9/port/edf.c:115,121 – 2002/0322/sys/src/9/port/edf.c:111,117
2002/0315		{ Taskq *q;
2002/0316		DENTER("%.*s%d edfpush, %s, %d\n", ind, tabs, m->machno, edf_statename[t->state], t->runq.n);
2002/0322		DPRINT("%d edfpush, %s, %d\n", m->machno, edf_statename[t->state], t->runq.n);
2002/0315		q = edfstack + m->machno; assert(t->runq.n || (up && up->task == t)); if (q->head){
2002/0321/sys/src/9/port/edf.c:126,132 – 2002/0322/sys/src/9/port/edf.c:122,127
2002/0315		t->rnext = q->head;
2002/0316		if(devrt) devrt(t, now, SRun);
2002/0315		q->head = t; DLEAVE; } static Task*
2002/0321/sys/src/9/port/edf.c:135,141 – 2002/0322/sys/src/9/port/edf.c:130,136
2002/0315		Task *t; Taskq *q;
2002/0316		DENTER("%.*s%d edfpop\n", ind, tabs, m->machno);
2002/0322		DPRINT("%d edfpop\n", m->machno);
2002/0315		q = edfstack + m->machno; if (t = q->head){ assert(t->state == EdfRunning);
2002/0321/sys/src/9/port/edf.c:147,153 – 2002/0322/sys/src/9/port/edf.c:142,147
2002/0316		if(devrt) devrt(q->head, now, SRun);
2002/0315		} } DLEAVE; return t; }
2002/0321/sys/src/9/port/edf.c:157,167 – 2002/0322/sys/src/9/port/edf.c:151,160
2002/0315		Task *tt, **ttp; ilock(q);
2002/0316		DENTER("%.*s%d edfenqueue, %s, %d\n", ind, tabs, m->machno, edf_statename[t->state], t->runq.n);
2002/0322		DPRINT("%d edfenqueue, %s, %d\n", m->machno, edf_statename[t->state], t->runq.n);
2002/0315		t->rnext = nil; if (q->head == nil) { q->head = t; DLEAVE; iunlock(q); return t; }
2002/0321/sys/src/9/port/edf.c:178,184 – 2002/0322/sys/src/9/port/edf.c:171,176
2002/0315		tt->rnext = t; if (t != q->head) t = nil; DLEAVE; iunlock(q); return t; }
2002/0321/sys/src/9/port/edf.c:188,194 – 2002/0322/sys/src/9/port/edf.c:180,186
2002/0315		{ Task *t;
2002/0316		DENTER("%.*s%d edfdequeue\n", ind, tabs, m->machno);
2002/0322		DPRINT("%d edfdequeue\n", m->machno);
2002/0315		ilock(q); if (t = q->head){ q->head = t->rnext;
2002/0321/sys/src/9/port/edf.c:195,201 – 2002/0322/sys/src/9/port/edf.c:187,192
2002/0315		t->rnext = nil; } iunlock(q); DLEAVE; return t; }
2002/0321/sys/src/9/port/edf.c:205,220 – 2002/0322/sys/src/9/port/edf.c:196,209
2002/0315		Task **tp; ilock(q);
2002/0316		DENTER("%.*s%d edfqremove, %s, %d\n", ind, tabs, m->machno, edf_statename[t->state], t->runq.n);
2002/0322		DPRINT("%d edfqremove, %s, %d\n", m->machno, edf_statename[t->state], t->runq.n);
2002/0315		for (tp = &q->head; *tp; tp = &(*tp)->rnext){ if (*tp == t){ *tp = t->rnext; DLEAVE; iunlock(q); return; } } DLEAVE; iunlock(q); }
2002/0321/sys/src/9/port/edf.c:232,243 – 2002/0322/sys/src/9/port/edf.c:221,231
2002/0320		iunlock(&edflock); return; }
2002/0316		DENTER("%.*s%d edf_block, %s, %d\n", ind, tabs, m->machno, edf_statename[t->state], t->runq.n);
2002/0322		DPRINT("%d edf_block, %s, %d\n", m->machno, edf_statename[t->state], t->runq.n);
2002/0315		if (t->runq.n){ /* There's another runnable proc in the running task, leave task where it is */ iunlock(&edflock); DLEAVE; return; } pt = edfpop();
2002/0321/sys/src/9/port/edf.c:244,250 – 2002/0322/sys/src/9/port/edf.c:232,237
2002/0315		assert(pt == t); t->state = EdfBlocked;
2002/0316		if(devrt) devrt(t, now, SBlock);
2002/0315		DLEAVE; iunlock(&edflock); }
2002/0321/sys/src/9/port/edf.c:254,260 – 2002/0322/sys/src/9/port/edf.c:241,247
2002/0315		Task *t, *nt; /* Task has reached its deadline, lock must be held */
2002/0316		DENTER("%.*s%d edfdeadline, %s, %d\n", ind, tabs, m->machno, edf_statename[p->task->state], p->task->runq.n);
2002/0322		DPRINT("%d edfdeadline, %s, %d\n", m->machno, edf_statename[p->task->state], p->task->runq.n);
2002/0315		SET(nt); if (p){ nt = p->task;
2002/0321/sys/src/9/port/edf.c:273,291 – 2002/0322/sys/src/9/port/edf.c:260,276
2002/0315		t->state = EdfDeadline;
2002/0316		if(devrt) devrt(t, now, why);
2002/0315		edf_resched(t); DLEAVE; } void edf_deadline(Proc *p) {
2002/0316		DENTER("%.*s%d edf_deadline\n", ind, tabs, m->machno);
2002/0322		DPRINT("%d edf_deadline\n", m->machno);
2002/0315		/* Task has reached its deadline */ ilock(&edflock); now = fastticks(nil); edfdeadline(p, SYield); iunlock(&edflock); DLEAVE; } char *
2002/0321/sys/src/9/port/edf.c:314,326 – 2002/0322/sys/src/9/port/edf.c:299,311
2002/0315		return err; } ilock(&edflock);
2002/0316		DENTER("%.*s%d edf_admit, %s, %d\n", ind, tabs, m->machno, edf_statename[t->state], t->runq.n);
2002/0322		DPRINT("%d edf_admit, %s, %d\n", m->machno, edf_statename[t->state], t->runq.n);
2002/0315		now = fastticks(nil); t->state = EdfAdmitted;
2002/0316		if(devrt) devrt(t, t->d, SAdmit);
2002/0315		if (up->task == t){
2002/0316		DPRINT("%.*s%d edf_admitting self\n", ind, tabs, m->machno);
2002/0322		DPRINT("%d edf_admitting self\n", m->machno);
2002/0315		/* Admitting self, fake reaching deadline */ t->r = now; t->t = now + t->T;
2002/0321/sys/src/9/port/edf.c:347,353 – 2002/0322/sys/src/9/port/edf.c:332,337
2002/0315		} } } DLEAVE; iunlock(&edflock); qunlock(&edfschedlock); return nil;
2002/0321/sys/src/9/port/edf.c:360,372 – 2002/0322/sys/src/9/port/edf.c:344,355
2002/0315		qlock(&edfschedlock); ilock(&edflock);
2002/0316		DENTER("%.*s%d edf_expel, %s, %d\n", ind, tabs, m->machno, edf_statename[t->state], t->runq.n);
2002/0322		DPRINT("%d edf_expel, %s, %d\n", m->machno, edf_statename[t->state], t->runq.n);
2002/0315		now = fastticks(nil); switch(t->state){ case EdfUnused: case EdfExpelled: /* That was easy */ DLEAVE; iunlock(&edflock); qunlock(&edfschedlock); return;
2002/0321/sys/src/9/port/edf.c:398,404 – 2002/0322/sys/src/9/port/edf.c:381,386
2002/0315		t->state = EdfExpelled;
2002/0316		if(devrt) devrt(t, now, SExpel);
2002/0320		setdelta();
2002/0315		DLEAVE; iunlock(&edflock); qunlock(&edfschedlock); return;
2002/0321/sys/src/9/port/edf.c:450,456 – 2002/0322/sys/src/9/port/edf.c:432,438
2002/0315		Ticks ticks; Task *t;
2002/0316		DENTER("%.*s%d edf_setclock\n", ind, tabs, m->machno);
2002/0322		DPRINT("%d edf_setclock\n", m->machno);
2002/0315		ticks = ~0ULL; if ((t = qwaitrelease.head) && t->r < ticks) ticks = t->r;
2002/0321/sys/src/9/port/edf.c:461,486 – 2002/0322/sys/src/9/port/edf.c:443,466
2002/0315		ticks = now + t->S; } if (schedpoint.when > now && schedpoint.when <= ticks){ DLEAVE; return; } if (schedpoint.when){
2002/0316		DPRINT("%.*s%d cycintrdel %T\n", ind, tabs, m->machno, ticks2time(schedpoint.when));
2002/0322		DPRINT("%d cycintrdel %T\n", m->machno, ticks2time(schedpoint.when));
2002/0315		cycintrdel(&schedpoint); schedpoint.when = 0; } if (ticks <= now){
2002/0316		DPRINT("%.*s%d edf_timer: %T too late\n", ind, tabs, m->machno, ticks2time(now-ticks));
2002/0322		DPRINT("%d edf_timer: %T too late\n", m->machno, ticks2time(now-ticks));
2002/0315		ticks = now; } if (ticks != ~0ULL) {
2002/0316		DPRINT("%.*s%d program timer in %T\n", ind, tabs, m->machno, ticks2time(ticks-now));
2002/0322		DPRINT("%d program timer in %T\n", m->machno, ticks2time(ticks-now));
2002/0315		schedpoint.when = ticks; cycintradd(&schedpoint);
2002/0316		DPRINT("%.*s%d cycintradd %T\n", ind, tabs, m->machno, ticks2time(schedpoint.when-now));
2002/0322		DPRINT("%d cycintradd %T\n", m->machno, ticks2time(schedpoint.when-now));
2002/0315		} clockintrsched(); DLEAVE; } static void
2002/0321/sys/src/9/port/edf.c:487,493 – 2002/0322/sys/src/9/port/edf.c:467,473
2002/0315		edf_intr(Ureg *, Cycintr *cy) {
2002/0316		DENTER("%.*s%d edf_intr\n", ind, tabs, m->machno);
2002/0322		DPRINT("%d edf_intr\n", m->machno);
2002/0315		/* Timer interrupt * Timed events are: * 1. release a task (look in qwaitrelease)
2002/0321/sys/src/9/port/edf.c:504,510 – 2002/0322/sys/src/9/port/edf.c:484,489
2002/0315		edf_timer(); edf_setclock(); iunlock(&edflock); DLEAVE; sched(); splhi(); }
2002/0321/sys/src/9/port/edf.c:515,527 – 2002/0322/sys/src/9/port/edf.c:494,506
2002/0315		Task *t; Proc **pp;
2002/0316		DPRINT("%.*s%d edf_bury\n", ind, tabs, m->machno);
2002/0322		DPRINT("%d edf_bury\n", m->machno);
2002/0315		ilock(&edflock); now = fastticks(nil); if ((t = p->task) == nil){ /* race condition? */ iunlock(&edflock);
2002/0316		DPRINT("%.*s%d edf bury race, pid %lud\n", ind, tabs, m->machno, p->pid);
2002/0322		DPRINT("%d edf bury race, pid %lud\n", m->machno, p->pid);
2002/0315		return; } assert(edfstack[m->machno].head == t);
2002/0321/sys/src/9/port/edf.c:549,559 – 2002/0322/sys/src/9/port/edf.c:528,538
2002/0315		Task *t; ilock(&edflock);
2002/0316		DENTER("%.*s%d edf_ready, %s, %d\n", ind, tabs, m->machno, edf_statename[p->task->state], p->task->runq.n);
2002/0322		DPRINT("%d edf_ready, %s, %d\n", m->machno, edf_statename[p->task->state], p->task->runq.n);
2002/0315		if ((t = p->task) == nil){ /* Must be a race */ iunlock(&edflock);
2002/0316		DPRINT("%.*s%d edf ready race, pid %lud\n", ind, tabs, m->machno, p->pid);
2002/0322		DPRINT("%d edf ready race, pid %lud\n", m->machno, p->pid);
2002/0315		return; } p->rnext = 0;
2002/0321/sys/src/9/port/edf.c:571,577 – 2002/0322/sys/src/9/port/edf.c:550,555
2002/0315		now = fastticks(nil); edf_resched(t); } DLEAVE; iunlock(&edflock); }
2002/0321/sys/src/9/port/edf.c:580,586 – 2002/0322/sys/src/9/port/edf.c:558,564
2002/0315		{ Task *xt;
2002/0316		DENTER("%.*s%d edf_resched, %s, %d\n", ind, tabs, m->machno, edf_statename[t->state], t->runq.n);
2002/0322		DPRINT("%d edf_resched, %s, %d\n", m->machno, edf_statename[t->state], t->runq.n);
2002/0315		if (t->nproc == 0){ /* No member processes */ if (t->state > EdfIdle){
2002/0321/sys/src/9/port/edf.c:587,598 – 2002/0322/sys/src/9/port/edf.c:565,575
2002/0315		t->state = EdfIdle;
2002/0316		if(devrt) devrt(t, now, SBlock);
2002/0315		} DLEAVE; return; } if (t->runq.n == 0 && (up == nil || up->task != t)){ /* Member processes but none runnable */
2002/0316		DPRINT("%.*s%d edf_resched, nothing runnable\n", ind, tabs, m->machno);
2002/0322		DPRINT("%d edf_resched, nothing runnable\n", m->machno);
2002/0315		if (t->state == EdfRunning) edfpop();
2002/0321/sys/src/9/port/edf.c:600,606 – 2002/0322/sys/src/9/port/edf.c:577,582
2002/0315		t->state = EdfBlocked;
2002/0316		if(devrt) devrt(t, now, SBlock);
2002/0315		} DLEAVE; return; }
2002/0321/sys/src/9/port/edf.c:608,616 – 2002/0322/sys/src/9/port/edf.c:584,591
2002/0315		switch (t->state){ case EdfUnused:
2002/0316		iprint("%.*s%d attempt to schedule unused task\n", ind, tabs, m->machno);
2002/0322		iprint("%d attempt to schedule unused task\n", m->machno);
2002/0315		case EdfExpelled: DLEAVE; return; /* Not admitted */ case EdfIdle: /* task was idle, schedule release now or later */
2002/0321/sys/src/9/port/edf.c:630,636 – 2002/0322/sys/src/9/port/edf.c:605,610
2002/0315		case EdfAdmitted: /* test whether task can be started */ if (edfstack[m->machno].head != nil){ DLEAVE; return; } /* fall through */
2002/0321/sys/src/9/port/edf.c:637,656 – 2002/0322/sys/src/9/port/edf.c:611,628
2002/0315		case EdfRunning: if (t->r <= now){ if (t->t < now){
2002/0316		DPRINT("%.*s%d edf_resched, rerelease\n", ind, tabs, m->machno);
2002/0322		DPRINT("%d edf_resched, rerelease\n", m->machno);
2002/0315		/* Period passed, rerelease */ t->r = now; xt = edfpop(); assert(xt == t); edf_release(t); DLEAVE; return; } if (now < t->d){ if (t->S > 0){
2002/0316		DPRINT("%.*s%d edf_resched, resume\n", ind, tabs, m->machno);
2002/0322		DPRINT("%d edf_resched, resume\n", m->machno);
2002/0315		/* Running, not yet at deadline, leave it */ DLEAVE; return; }else t->d = now;
2002/0321/sys/src/9/port/edf.c:658,664 – 2002/0322/sys/src/9/port/edf.c:630,636
2002/0315		/* Released, but deadline is past, release at t->t */ t->r = t->t; }
2002/0316		DPRINT("%.*s%d edf_resched, schedule release\n", ind, tabs, m->machno);
2002/0322		DPRINT("%d edf_resched, schedule release\n", m->machno);
2002/0315		xt = edfpop(); assert(xt == t); edfenqueue(&qwaitrelease, t);
2002/0321/sys/src/9/port/edf.c:669,689 – 2002/0322/sys/src/9/port/edf.c:641,659
2002/0315		case EdfDeadline: if (t->r <= now){ if (t->t < now){
2002/0316		DPRINT("%.*s%d edf_resched, rerelease\n", ind, tabs, m->machno);
2002/0322		DPRINT("%d edf_resched, rerelease\n", m->machno);
2002/0315		/* Period passed, rerelease */ t->r = now; edf_release(t); DLEAVE; return; } if (now < t->d && (t->flags & Useblocking) == 0){ if (t->S > 0){
2002/0316		DPRINT("%.*s%d edf_resched, resume\n", ind, tabs, m->machno);
2002/0322		DPRINT("%d edf_resched, resume\n", m->machno);
2002/0315		/* Released, not yet at deadline, release (again) */ t->state = EdfReleased; edfenqueue(&qreleased, t);
2002/0316		if(devrt) devrt(t, now, SResume);
2002/0315		DLEAVE; return; }else t->d = now;
2002/0321/sys/src/9/port/edf.c:691,709 – 2002/0322/sys/src/9/port/edf.c:661,678
2002/0315		/* Released, but deadline is past, release at t->t */ t->r = t->t; }
2002/0316		DPRINT("%.*s%d edf_resched, schedule release\n", ind, tabs, m->machno);
2002/0322		DPRINT("%d edf_resched, schedule release\n", m->machno);
2002/0315		edfenqueue(&qwaitrelease, t); t->state = EdfAwaitrelease; edf_setclock(); break; } DLEAVE; } void edf_release(Task *t) {
2002/0316		DENTER("%.*s%d edf_release, %s, %d\n", ind, tabs, m->machno, edf_statename[t->state], t->runq.n);
2002/0322		DPRINT("%d edf_release, %s, %d\n", m->machno, edf_statename[t->state], t->runq.n);
2002/0315		assert(t->runq.n > 0 || (up && up->task == t)); t->t = t->r + t->T; t->d = t->r + t->D;
2002/0321/sys/src/9/port/edf.c:713,719 – 2002/0322/sys/src/9/port/edf.c:682,687
2002/0315		edfenqueue(&qreleased, t);
2002/0316		if(devrt) devrt(t, now, SRelease);
2002/0315		edf_setclock(); DLEAVE; } Proc *
2002/0321/sys/src/9/port/edf.c:728,734 – 2002/0322/sys/src/9/port/edf.c:696,701
2002/0315		/* 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 */
2002/0321/sys/src/9/port/edf.c:742,751 – 2002/0322/sys/src/9/port/edf.c:709,718
2002/0315		iunlock(&edflock); return nil; } DENTER("edf_runproc %lud\n", nilcount);
2002/0322		DPRINT("edf_runproc %lud\n", nilcount);
2002/0320		if (nt && (t == nil || (nt->d < t->d && nt->D < t->Delta))){
2002/0315		/* released task is better than current */
2002/0316		DPRINT("%.*s%d edf_runproc: released\n", ind, tabs, m->machno);
2002/0322		DPRINT("%d edf_runproc: released\n", m->machno);
2002/0315		edfdequeue(&qreleased); assert(nt->runq.n >= 1); edfpush(nt);
2002/0321/sys/src/9/port/edf.c:753,759 – 2002/0322/sys/src/9/port/edf.c:720,726
2002/0315		t = nt; t->scheduled = now; }else{
2002/0316		DPRINT("%.*s%d edf_runproc: current\n", ind, tabs, m->machno);
2002/0322		DPRINT("%d edf_runproc: current\n", m->machno);
2002/0315		} assert (t->runq.n);
2002/0321/sys/src/9/port/edf.c:771,777 – 2002/0322/sys/src/9/port/edf.c:738,743
2002/0315		p->movetime = MACHP(0)->ticks + HZ/10; p->mp = MACHP(m->machno); edf_setclock(); DLEAVE; iunlock(&edflock); return p; }
2002/0321/sys/src/9/port/edf.c:781,787 – 2002/0322/sys/src/9/port/edf.c:747,752
2002/0315		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 */
2002/0321/sys/src/9/port/edf.c:802,808 – 2002/0322/sys/src/9/port/edf.c:767,772
2002/0315		{ Proc *p; iprint("edf_releaselock\n"); ilock(&waitlock); /* can't afford normal locks here */ if(l->edfwaiting == nil){ iunlock(&waitlock);
2002/0322/sys/src/9/port/edf.c:26,32 – 2002/0327/sys/src/9/port/edf.c:26,34 (short | long)
2002/0315		[EdfDeadline] = "Deadline", }; static Cycintr schedpoint; /* First scheduling point */
2002/0327		static Cycintr cycdeadline; /* Time of next deadline */ static Cycintr cycrelease; /* Time of next release */
2002/0315		static Ticks utilization; /* Current utilization */ static int initialized; static uvlong fasthz;
2002/0322/sys/src/9/port/edf.c:66,77 – 2002/0327/sys/src/9/port/edf.c:68,79
2002/0315
2002/0316		void (*devrt)(Task*, Ticks, int);
2002/0315		static void edf_intr(Ureg*, Cycintr*);
2002/0327		static void edfdeadlineintr(Ureg*, Cycintr*);
2002/0315		static void edf_resched(Task *t);
2002/0320		static void setdelta(void); static void testdelta(Task *thetask);
2002/0315		static char * edf_testschedulability(Task *thetask); static void edf_setclock(void);
2002/0327		static void edfreleaseintr(void);
2002/0315		void edf_init(void)
2002/0322/sys/src/9/port/edf.c:84,92 – 2002/0327/sys/src/9/port/edf.c:86,97
2002/0315		return; } fastticks(&fasthz); schedpoint.f = edf_intr; schedpoint.a = &schedpoint; schedpoint.when = 0;
2002/0327		cycdeadline.f = edfdeadlineintr; cycdeadline.a = &cycdeadline; cycdeadline.when = 0; cycrelease.f = edfreleaseintr; cycrelease.a = &cycrelease; cycrelease.when = 0;
2002/0315		initialized = 1; iunlock(&edflock); }
2002/0322/sys/src/9/port/edf.c:190,196 – 2002/0327/sys/src/9/port/edf.c:195,201
2002/0315		return t; } static void
2002/0327		static Task*
2002/0315		edfqremove(Taskq *q, Task *t) { Task **tp;
2002/0322/sys/src/9/port/edf.c:200,213 – 2002/0327/sys/src/9/port/edf.c:205,256
2002/0315		for (tp = &q->head; *tp; tp = &(*tp)->rnext){ if (*tp == t){ *tp = t->rnext;
2002/0327		t = (tp == &q->head) ? q->head : nil;
2002/0315		iunlock(q); return;
2002/0327		return t;
2002/0315		} } iunlock(q); }
2002/0327
2002/0315		void
2002/0327		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
2002/0315		edf_block(Proc *p) { Task *t, *pt;
2002/0322/sys/src/9/port/edf.c:255,261 – 2002/0327/sys/src/9/port/edf.c:298,308
2002/0315		iunlock(&edflock); assert(0 && p == nil || nt == t); }
2002/0327		if (cycdeadline.when){ cycintrdel(&cycdeadline); cycdeadline.when = 0; clockintrsched(); }
2002/0315		t->d = now; t->state = EdfDeadline;
2002/0316		if(devrt) devrt(t, now, why);
2002/0322/sys/src/9/port/edf.c:318,324 – 2002/0327/sys/src/9/port/edf.c:365,370
2002/0320		setdelta();
2002/0315		assert(t->runq.n > 0 || (up && up->task == t)); edfpush(t); edf_setclock(); }else{ if (t->runq.n){ if (edfstack[m->machno].head == nil){
2002/0322/sys/src/9/port/edf.c:358,364 – 2002/0327/sys/src/9/port/edf.c:404,411
2002/0315		/* Just reset state */ break; case EdfAwaitrelease: edfqremove(&qwaitrelease, t);
2002/0327		if (edfqremove(&qwaitrelease, t)) edfreleasetimer();
2002/0315		break; case EdfReleased: edfqremove(&qreleased, t);
2002/0322/sys/src/9/port/edf.c:387,397 – 2002/0327/sys/src/9/port/edf.c:434,474
2002/0315		} static void edf_timer(void)
2002/0327		edfreleaseintr(void)
2002/0315		{
2002/0327		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) {
2002/0315		Ticks used; Task *t;
2002/0327		DPRINT("%d edfdeadlineintr\n", m->machno); /* Task reached deadline */ now = fastticks(nil); if(active.exiting) return; ilock(&edflock);
2002/0315		// If up is not set, we're running inside the scheduler // for non-real-time processes. if (up && isedf(up)) {
2002/0322/sys/src/9/port/edf.c:418,488 – 2002/0327/sys/src/9/port/edf.c:495,500
2002/0315		} } }                  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;
2002/0322		DPRINT("%d edf_setclock\n", m->machno);
2002/0315		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){ return; } if (schedpoint.when){
2002/0322		DPRINT("%d cycintrdel %T\n", m->machno, ticks2time(schedpoint.when));
2002/0315		cycintrdel(&schedpoint); schedpoint.when = 0; } if (ticks <= now){
2002/0322		DPRINT("%d edf_timer: %T too late\n", m->machno, ticks2time(now-ticks));
2002/0315		ticks = now; } if (ticks != ~0ULL) {
2002/0322		DPRINT("%d program timer in %T\n", m->machno, ticks2time(ticks-now));
2002/0315		schedpoint.when = ticks; cycintradd(&schedpoint);
2002/0322		DPRINT("%d cycintradd %T\n", m->machno, ticks2time(schedpoint.when-now));
2002/0315		} clockintrsched(); }                  static void edf_intr(Ureg *, Cycintr *cy) {
2002/0322		DPRINT("%d edf_intr\n", m->machno);
2002/0315		/* 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); sched(); splhi();
2002/0322/sys/src/9/port/edf.c:630,641 – 2002/0327/sys/src/9/port/edf.c:642,650
2002/0315		/* Released, but deadline is past, release at t->t */ t->r = t->t; }
2002/0322		DPRINT("%d edf_resched, schedule release\n", m->machno);
2002/0315		xt = edfpop(); assert(xt == t); edfenqueue(&qwaitrelease, t); t->state = EdfAwaitrelease; edf_setclock();
2002/0327		schedrelease(t);
2002/0315		break; case EdfBlocked: case EdfDeadline:
2002/0322/sys/src/9/port/edf.c:661,670 – 2002/0327/sys/src/9/port/edf.c:670,676
2002/0315		/* Released, but deadline is past, release at t->t */ t->r = t->t; }
2002/0322		DPRINT("%d edf_resched, schedule release\n", m->machno);
2002/0315		edfenqueue(&qwaitrelease, t); t->state = EdfAwaitrelease; edf_setclock();
2002/0327		schedrelease(t);
2002/0315		break; } }
2002/0322/sys/src/9/port/edf.c:681,687 – 2002/0327/sys/src/9/port/edf.c:687,692
2002/0315		t->state = EdfReleased; edfenqueue(&qreleased, t);
2002/0316		if(devrt) devrt(t, now, SRelease);
2002/0315		edf_setclock(); } Proc *
2002/0322/sys/src/9/port/edf.c:691,697 – 2002/0327/sys/src/9/port/edf.c:696,702
2002/0315		Task *t, *nt; Proc *p; // Ticks when;
2002/0327		Ticks when;
2002/0315		static ulong nilcount; /* Figure out if the current proc should be preempted*/
2002/0322/sys/src/9/port/edf.c:737,743 – 2002/0327/sys/src/9/port/edf.c:742,769
2002/0315		if(p->mp != MACHP(m->machno)) p->movetime = MACHP(0)->ticks + HZ/10; p->mp = MACHP(m->machno); edf_setclock();
2002/0327		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();
2002/0315		iunlock(&edflock); return p; }
2002/0327/sys/src/9/port/edf.c:33,40 – 2002/0328/sys/src/9/port/edf.c:33,39 (short | long)
2002/0315		static int initialized; static uvlong fasthz; static Ticks now; QLock edfschedlock; /* schedulability, held for */
2002/0328		QLock edfschedlock;
2002/0315		Lock edflock; Task tasks[Maxtasks];
2002/0327/sys/src/9/port/edf.c:68,79 – 2002/0328/sys/src/9/port/edf.c:67,78
2002/0315
2002/0316		void (*devrt)(Task*, Ticks, int);
2002/0315
2002/0327		static void edfdeadlineintr(Ureg*, Cycintr*);
2002/0315		static void edf_resched(Task *t);
2002/0320		static void setdelta(void); static void testdelta(Task *thetask);
2002/0315		static char * edf_testschedulability(Task *thetask);
2002/0327		static void edfreleaseintr(void);
2002/0328		static void edfreleaseintr(Ureg *, Cycintr *cy); static void edfdeadlineintr(Ureg*, Cycintr*);
2002/0315		void edf_init(void)
2002/0327/sys/src/9/port/edf.c:211,216 – 2002/0328/sys/src/9/port/edf.c:210,216
2002/0315		} } iunlock(q);
2002/0328		return nil;
2002/0315		}
2002/0327
2002/0327/sys/src/9/port/edf.c:219,256 – 2002/0328/sys/src/9/port/edf.c:219,237
2002/0327		{ Task *t; t = qwaitrelease.head; DPRINT("edf_schedrelease clock\n"); if (cycrelease.when == t->r)
2002/0328		if ((t = qwaitrelease.head) == nil)
2002/0327		return; if (cycrelease.when){ DPRINT("%d cycintrdel %T\n", m->machno, ticks2time(cycrelease.when));
2002/0328		DPRINT("edfreleasetimer clock\n"); if (cycrelease.when)
2002/0327		cycintrdel(&cycrelease); } cycrelease.when = t->r; if (cycrelease.when <= now){ DPRINT("%d edf_timer: %T too late\n", m->machno, ticks2time(now-ticks));
2002/0328		if (cycrelease.when <= now)
2002/0327		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
2002/0315		edf_block(Proc *p) { Task *t, *pt;
2002/0327/sys/src/9/port/edf.c:434,452 – 2002/0328/sys/src/9/port/edf.c:415,437
2002/0315		} static void
2002/0327		edfreleaseintr(void)
2002/0328		edfreleaseintr(Ureg*, Cycintr*)
2002/0315		{
2002/0327		Task *t; now = fastticks(nil);
2002/0328		DPRINT("%d edfreleaseintr\n", m->machno);
2002/0327
2002/0328		cycrelease.when = 0;
2002/0327		if(active.exiting) return; ilock(&edflock);
2002/0328		now = fastticks(nil);
2002/0327		while((t = qwaitrelease.head) && t->r <= now){ /* There's something waiting to be released and its time has come */ edfdequeue(&qwaitrelease);
2002/0328		edfreleasetimer();
2002/0327		edf_release(t); } iunlock(&edflock);
2002/0327/sys/src/9/port/edf.c:455,470 – 2002/0328/sys/src/9/port/edf.c:440,456
2002/0327		} static void edfdeadlineintr(Ureg *, Cycintr *cy)
2002/0328		edfdeadlineintr(Ureg*, Cycintr*)
2002/0327		{
2002/0328		/* Task reached deadline */
2002/0315		Ticks used; Task *t;
2002/0327		DPRINT("%d edfdeadlineintr\n", m->machno); /* Task reached deadline */ now = fastticks(nil);
2002/0328		cycdeadline.when = 0;
2002/0327		if(active.exiting) return;
2002/0327/sys/src/9/port/edf.c:472,477 – 2002/0328/sys/src/9/port/edf.c:458,465
2002/0315		// If up is not set, we're running inside the scheduler // for non-real-time processes. if (up && isedf(up)) {
2002/0328		now = fastticks(nil);
2002/0315		t = up->task; assert(t->scheduled > 0);
2002/0327/sys/src/9/port/edf.c:644,650 – 2002/0328/sys/src/9/port/edf.c:632,640
2002/0315		} xt = edfpop(); assert(xt == t);
2002/0327		schedrelease(t);
2002/0328		t->state = EdfAwaitrelease; if (edfenqueue(&qwaitrelease, t)) edfreleasetimer();
2002/0315		break; case EdfBlocked: case EdfDeadline:
2002/0327/sys/src/9/port/edf.c:670,676 – 2002/0328/sys/src/9/port/edf.c:660,668
2002/0315		/* Released, but deadline is past, release at t->t */ t->r = t->t; }
2002/0327		schedrelease(t);
2002/0328		t->state = EdfAwaitrelease; if (edfenqueue(&qwaitrelease, t)) edfreleasetimer();
2002/0315		break; } }
2002/0327/sys/src/9/port/edf.c:747,813 – 2002/0328/sys/src/9/port/edf.c:739,761
2002/0327		if (t->d < when) when = t->d;
2002/0328		if (when < now){ DPRINT("%d edf_timer: %T too late\n", m->machno, ticks2time(now-when)); when = now; }
2002/0327		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();
2002/0315		iunlock(&edflock); return p; }                  static Lock waitlock;                  int edf_waitlock(Lock *l) { 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;                  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 */
2002/0328/sys/src/9/port/edf.c:29,35 – 2002/0329/sys/src/9/port/edf.c:29,34 (short | long)
2002/0327		static Cycintr cycdeadline; /* Time of next deadline */ static Cycintr cycrelease; /* Time of next release */
2002/0315		static Ticks utilization; /* Current utilization */ static int initialized; static uvlong fasthz; static Ticks now;
2002/0328/sys/src/9/port/edf.c:154,165 – 2002/0329/sys/src/9/port/edf.c:153,162
2002/0315		{ Task *tt, **ttp; ilock(q);
2002/0322		DPRINT("%d edfenqueue, %s, %d\n", m->machno, edf_statename[t->state], t->runq.n);
2002/0315		t->rnext = nil; if (q->head == nil) { q->head = t; iunlock(q); return t; } SET(tt);
2002/0328/sys/src/9/port/edf.c:175,181 – 2002/0329/sys/src/9/port/edf.c:172,177
2002/0315		tt->rnext = t; if (t != q->head) t = nil; iunlock(q); return t; }
2002/0328/sys/src/9/port/edf.c:185,196 – 2002/0329/sys/src/9/port/edf.c:181,190
2002/0315		Task *t;
2002/0322		DPRINT("%d edfdequeue\n", m->machno);
2002/0315		ilock(q); if (t = q->head){ q->head = t->rnext; t->rnext = nil; } iunlock(q); return t; }
2002/0328/sys/src/9/port/edf.c:199,215 – 2002/0329/sys/src/9/port/edf.c:193,206
2002/0315		{ Task **tp; ilock(q);
2002/0322		DPRINT("%d edfqremove, %s, %d\n", m->machno, edf_statename[t->state], t->runq.n);
2002/0315		for (tp = &q->head; *tp; tp = &(*tp)->rnext){ if (*tp == t){ *tp = t->rnext;
2002/0327		t = (tp == &q->head) ? q->head : nil;
2002/0315		iunlock(q);
2002/0327		return t;
2002/0315		} } iunlock(q);
2002/0328		return nil;
2002/0315		}
2002/0328/sys/src/9/port/edf.c:482,487 – 2002/0329/sys/src/9/port/edf.c:473,480
2002/0315		} } }
2002/0329		if (up->nlocks) iprint("have %lud locks at deadline\n", up->nlocks);
2002/0315		} iunlock(&edflock); sched();
2002/0329/sys/src/9/port/edf.c:412,418 – 2002/0330/sys/src/9/port/edf.c:412,420 (short | long)
2002/0327
2002/0328		DPRINT("%d edfreleaseintr\n", m->machno);
2002/0327
2002/0330		cycintrdel(&cycrelease);
2002/0328		cycrelease.when = 0;
2002/0330		clockintrsched();
2002/0328
2002/0327		if(active.exiting) return;
2002/0329/sys/src/9/port/edf.c:440,446 – 2002/0330/sys/src/9/port/edf.c:442,450
2002/0315
2002/0327		DPRINT("%d edfdeadlineintr\n", m->machno);
2002/0330		cycintrdel(&cycdeadline);
2002/0328		cycdeadline.when = 0;
2002/0330		clockintrsched();
2002/0328
2002/0327		if(active.exiting) return;
2002/0330/sys/src/9/port/edf.c:477,484 – 2002/0404/sys/src/9/port/edf.c:477,482 (short | long)
2002/0315		} } }
2002/0329		if (up->nlocks) iprint("have %lud locks at deadline\n", up->nlocks);
2002/0315		} iunlock(&edflock); sched();
2002/0330/sys/src/9/port/edf.c:869,875 – 2002/0404/sys/src/9/port/edf.c:867,872
2002/0315		} H=0; G=0; ticks = 0; for(steps = 0; steps < Maxsteps; steps++){ t = qschedulability; qschedulability = t->testnext;
2002/0404/sys/src/9/port/edf.c:26,33 – 2002/0405/sys/src/9/port/edf.c:26,33 (short | long)
2002/0315		[EdfDeadline] = "Deadline", };
2002/0327		static Cycintr cycdeadline; /* Time of next deadline */ static Cycintr cycrelease; /* Time of next release */
2002/0405		static Timer cycdeadline; /* Time of next deadline */ static Timer cycrelease; /* Time of next release */
2002/0327
2002/0315		static int initialized; static uvlong fasthz;
2002/0404/sys/src/9/port/edf.c:70,77 – 2002/0405/sys/src/9/port/edf.c:70,77
2002/0320		static void setdelta(void); static void testdelta(Task *thetask);
2002/0315		static char * edf_testschedulability(Task *thetask);
2002/0328		static void edfreleaseintr(Ureg *, Cycintr *cy); static void edfdeadlineintr(Ureg*, Cycintr*);
2002/0405		static void edfreleaseintr(Ureg *, Timer *cy); static void edfdeadlineintr(Ureg*, Timer*);
2002/0315		void edf_init(void)
2002/0404/sys/src/9/port/edf.c:214,224 – 2002/0405/sys/src/9/port/edf.c:214,224
2002/0327		return;
2002/0328		DPRINT("edfreleasetimer clock\n"); if (cycrelease.when)
2002/0327		cycintrdel(&cycrelease);
2002/0405		timerdel(&cycrelease);
2002/0327		cycrelease.when = t->r;
2002/0328		if (cycrelease.when <= now)
2002/0327		cycrelease.when = now; cycintradd(&cycrelease);
2002/0405		timeradd(&cycrelease);
2002/0327		clockintrsched(); }
2002/0404/sys/src/9/port/edf.c:271,277 – 2002/0405/sys/src/9/port/edf.c:271,277
2002/0315		assert(0 && p == nil || nt == t); }
2002/0327		if (cycdeadline.when){ cycintrdel(&cycdeadline);
2002/0405		timerdel(&cycdeadline);
2002/0327		cycdeadline.when = 0; clockintrsched(); }
2002/0404/sys/src/9/port/edf.c:406,418 – 2002/0405/sys/src/9/port/edf.c:406,418
2002/0315		} static void
2002/0328		edfreleaseintr(Ureg*, Cycintr*)
2002/0405		edfreleaseintr(Ureg*, Timer*)
2002/0315		{
2002/0327		Task *t;
2002/0328		DPRINT("%d edfreleaseintr\n", m->machno);
2002/0327
2002/0330		cycintrdel(&cycrelease);
2002/0405		timerdel(&cycrelease);
2002/0328		cycrelease.when = 0;
2002/0330		clockintrsched();
2002/0328
2002/0404/sys/src/9/port/edf.c:433,439 – 2002/0405/sys/src/9/port/edf.c:433,439
2002/0327		} static void
2002/0328		edfdeadlineintr(Ureg*, Cycintr*)
2002/0405		edfdeadlineintr(Ureg*, Timer*)
2002/0327		{
2002/0328		/* Task reached deadline */
2002/0404/sys/src/9/port/edf.c:442,448 – 2002/0405/sys/src/9/port/edf.c:442,448
2002/0315
2002/0327		DPRINT("%d edfdeadlineintr\n", m->machno);
2002/0330		cycintrdel(&cycdeadline);
2002/0405		timerdel(&cycdeadline);
2002/0328		cycdeadline.when = 0;
2002/0330		clockintrsched();
2002/0328
2002/0404/sys/src/9/port/edf.c:743,752 – 2002/0405/sys/src/9/port/edf.c:743,752
2002/0327		iunlock(&edflock); return p; } cycintrdel(&cycdeadline);
2002/0405		timerdel(&cycdeadline);
2002/0327		} cycdeadline.when = when; cycintradd(&cycdeadline);
2002/0405		timeradd(&cycdeadline);
2002/0327		clockintrsched();
2002/0315		iunlock(&edflock); return p;
2002/0405/sys/src/9/port/edf.c:12,18 – 2002/0410/sys/src/9/port/edf.c:12,18 (short | long)
2002/0315		int edfprint = 0; #define DPRINT if(edfprint)iprint char *edf_statename[] = {
2002/0410		char *edfstatename[] = {
2002/0315		[EdfUnused] = "Unused", [EdfExpelled] = "Expelled", [EdfAdmitted] = "Admitted",
2002/0405/sys/src/9/port/edf.c:26,33 – 2002/0410/sys/src/9/port/edf.c:26,33
2002/0315		[EdfDeadline] = "Deadline", };
2002/0405		static Timer cycdeadline; /* Time of next deadline */ static Timer cycrelease; /* Time of next release */
2002/0410		static Timer deadlinetimer[MAXMACH]; /* Time of next deadline */ static Timer releasetimer[MAXMACH]; /* Time of next release */
2002/0327
2002/0315		static int initialized; static uvlong fasthz;
2002/0405/sys/src/9/port/edf.c:39,45 – 2002/0410/sys/src/9/port/edf.c:39,45
2002/0315		int ntasks; Resource resources[Maxresources]; int nresources; int edf_stateupdate;
2002/0410		int edfstateupdate;
2002/0315		enum{ Deadline, /* Invariant for schedulability test: Deadline < Release */
2002/0405/sys/src/9/port/edf.c:58,81 – 2002/0410/sys/src/9/port/edf.c:58,80
2002/0315		/* 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];
2002/0316		void (*devrt)(Task*, Ticks, int);
2002/0315		static void edf_resched(Task *t);
2002/0410		static void edfresched(Task *t);
2002/0320		static void setdelta(void); static void testdelta(Task *thetask);
2002/0315		static char * edf_testschedulability(Task *thetask);
2002/0405		static void edfreleaseintr(Ureg *, Timer *cy); static void edfdeadlineintr(Ureg*, Timer*);
2002/0410		static char * edftestschedulability(Task *thetask);
2002/0315		void edf_init(void)
2002/0410		edfinit(void)
2002/0315		{
2002/0410		int i;
2002/0315		if (initialized) return; ilock(&edflock);
2002/0405/sys/src/9/port/edf.c:84,95 – 2002/0410/sys/src/9/port/edf.c:83,96
2002/0315		return; } fastticks(&fasthz);
2002/0327		cycdeadline.f = edfdeadlineintr; cycdeadline.a = &cycdeadline; cycdeadline.when = 0; cycrelease.f = edfreleaseintr; cycrelease.a = &cycrelease; cycrelease.when = 0;
2002/0410		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; }
2002/0315		initialized = 1; iunlock(&edflock); }
2002/0405/sys/src/9/port/edf.c:101,107 – 2002/0410/sys/src/9/port/edf.c:102,108
2002/0315		} int edf_anyready(void)
2002/0410		edfanyready(void)
2002/0315		{ /* If any edf tasks (with runnable procs in them) are released, * at least one of them must be on the stack
2002/0405/sys/src/9/port/edf.c:114,120 – 2002/0410/sys/src/9/port/edf.c:115,121
2002/0315		{ Taskq *q;
2002/0322		DPRINT("%d edfpush, %s, %d\n", m->machno, edf_statename[t->state], t->runq.n);
2002/0410		DPRINT("%d edfpush, %s, %d\n", m->machno, edfstatename[t->state], t->runq.n);
2002/0315		q = edfstack + m->machno; assert(t->runq.n || (up && up->task == t)); if (q->head){
2002/0405/sys/src/9/port/edf.c:153,159 – 2002/0410/sys/src/9/port/edf.c:154,160
2002/0315		{ Task *tt, **ttp;
2002/0322		DPRINT("%d edfenqueue, %s, %d\n", m->machno, edf_statename[t->state], t->runq.n);
2002/0410		DPRINT("%d edfenqueue, %s, %d\n", m->machno, edfstatename[t->state], t->runq.n);
2002/0315		t->rnext = nil; if (q->head == nil) { q->head = t;
2002/0405/sys/src/9/port/edf.c:193,199 – 2002/0410/sys/src/9/port/edf.c:194,200
2002/0315		{ Task **tp;
2002/0322		DPRINT("%d edfqremove, %s, %d\n", m->machno, edf_statename[t->state], t->runq.n);
2002/0410		DPRINT("%d edfqremove, %s, %d\n", m->machno, edfstatename[t->state], t->runq.n);
2002/0315		for (tp = &q->head; *tp; tp = &(*tp)->rnext){ if (*tp == t){ *tp = t->rnext;
2002/0405/sys/src/9/port/edf.c:213,229 – 2002/0410/sys/src/9/port/edf.c:214,229
2002/0328		if ((t = qwaitrelease.head) == nil)
2002/0327		return;
2002/0328		DPRINT("edfreleasetimer clock\n"); if (cycrelease.when)
2002/0405		timerdel(&cycrelease);
2002/0327		cycrelease.when = t->r;
2002/0328		if (cycrelease.when <= now)
2002/0327		cycrelease.when = now;
2002/0405		timeradd(&cycrelease);
2002/0327		clockintrsched();
2002/0410		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]);
2002/0327		} void
2002/0315		edf_block(Proc *p)
2002/0410		edfblock(Proc *p)
2002/0315		{ Task *t, *pt;
2002/0405/sys/src/9/port/edf.c:236,242 – 2002/0410/sys/src/9/port/edf.c:236,242
2002/0320		iunlock(&edflock); return; }
2002/0322		DPRINT("%d edf_block, %s, %d\n", m->machno, edf_statename[t->state], t->runq.n);
2002/0410		DPRINT("%d edfblock, %s, %d\n", m->machno, edfstatename[t->state], t->runq.n);
2002/0315		if (t->runq.n){ /* There's another runnable proc in the running task, leave task where it is */
2002/0405/sys/src/9/port/edf.c:251,262 – 2002/0410/sys/src/9/port/edf.c:251,262
2002/0315		} static void edfdeadline(Proc *p, SEvent why)
2002/0410		deadline(Proc *p, SEvent why)
2002/0315		{ Task *t, *nt; /* Task has reached its deadline, lock must be held */
2002/0322		DPRINT("%d edfdeadline, %s, %d\n", m->machno, edf_statename[p->task->state], p->task->runq.n);
2002/0410		DPRINT("%d deadline, %s, %d\n", m->machno, edfstatename[p->task->state], p->task->runq.n);
2002/0315		SET(nt); if (p){ nt = p->task;
2002/0405/sys/src/9/port/edf.c:266,299 – 2002/0410/sys/src/9/port/edf.c:266,298
2002/0315		t = edfpop(); if(p != nil && nt != t){
2002/0320		iprint("edfdeadline, %s, %d\n", edf_statename[p->task->state], p->task->runq.n);
2002/0410		iprint("deadline, %s, %d\n", edfstatename[p->task->state], p->task->runq.n);
2002/0315		iunlock(&edflock); assert(0 && p == nil || nt == t); }
2002/0327		if (cycdeadline.when){
2002/0405		timerdel(&cycdeadline);
2002/0327		cycdeadline.when = 0; clockintrsched();
2002/0410		if (deadlinetimer[m->machno].when){ timerdel(&deadlinetimer[m->machno]); deadlinetimer[m->machno].when = 0;
2002/0327		}
2002/0315		t->d = now; t->state = EdfDeadline;
2002/0316		if(devrt) devrt(t, now, why);
2002/0315		edf_resched(t);
2002/0410		edfresched(t);
2002/0315		} void edf_deadline(Proc *p)
2002/0410		edfdeadline(Proc *p)
2002/0315		{
2002/0322		DPRINT("%d edf_deadline\n", m->machno);
2002/0410		DPRINT("%d edfdeadline\n", m->machno);
2002/0315		/* Task has reached its deadline */ ilock(&edflock); now = fastticks(nil); edfdeadline(p, SYield);
2002/0410		deadline(p, SYield);
2002/0315		iunlock(&edflock); } char * edf_admit(Task *t)
2002/0410		edfadmit(Task *t)
2002/0315		{ char *err;
2002/0405/sys/src/9/port/edf.c:313,330 – 2002/0410/sys/src/9/port/edf.c:312,329
2002/0316		return "C > D";
2002/0315		qlock(&edfschedlock); if (err = edf_testschedulability(t)){
2002/0410		if (err = edftestschedulability(t)){
2002/0315		qunlock(&edfschedlock); return err; } ilock(&edflock);
2002/0322		DPRINT("%d edf_admit, %s, %d\n", m->machno, edf_statename[t->state], t->runq.n);
2002/0410		DPRINT("%d edfadmit, %s, %d\n", m->machno, edfstatename[t->state], t->runq.n);
2002/0315		now = fastticks(nil); t->state = EdfAdmitted;
2002/0316		if(devrt) devrt(t, t->d, SAdmit);
2002/0315		if (up->task == t){
2002/0322		DPRINT("%d edf_admitting self\n", m->machno);
2002/0410		DPRINT("%d edfadmitting self\n", m->machno);
2002/0315		/* Admitting self, fake reaching deadline */ t->r = now; t->t = now + t->T;
2002/0405/sys/src/9/port/edf.c:337,352 – 2002/0410/sys/src/9/port/edf.c:336,353
2002/0320		setdelta();
2002/0315		assert(t->runq.n > 0 || (up && up->task == t)); edfpush(t);
2002/0410		if (deadlinetimer[m->machno].when) timerdel(&deadlinetimer[m->machno]); deadlinetimer[m->machno].when = t->d; timeradd(&deadlinetimer[m->machno]);
2002/0315		}else{ if (t->runq.n){ if (edfstack[m->machno].head == nil){ t->state = EdfAdmitted; t->r = now; edf_release(t);
2002/0410		edfrelease(t);
2002/0320		setdelta();
2002/0315		edf_resched(t); }else{ edfenqueue(&qadmit, t);
2002/0410		edfresched(t);
2002/0315		} } }
2002/0405/sys/src/9/port/edf.c:356,368 – 2002/0410/sys/src/9/port/edf.c:357,369
2002/0315		} void edf_expel(Task *t)
2002/0410		edfexpel(Task *t)
2002/0315		{ Task *tt; qlock(&edfschedlock); ilock(&edflock);
2002/0322		DPRINT("%d edf_expel, %s, %d\n", m->machno, edf_statename[t->state], t->runq.n);
2002/0410		DPRINT("%d edfexpel, %s, %d\n", m->machno, edfstatename[t->state], t->runq.n);
2002/0315		now = fastticks(nil); switch(t->state){ case EdfUnused:
2002/0405/sys/src/9/port/edf.c:412,420 – 2002/0410/sys/src/9/port/edf.c:413,420
2002/0327
2002/0328		DPRINT("%d edfreleaseintr\n", m->machno);
2002/0327
2002/0405		timerdel(&cycrelease);
2002/0328		cycrelease.when = 0;
2002/0330		clockintrsched();
2002/0410		timerdel(&releasetimer[m->machno]); releasetimer[m->machno].when = 0;
2002/0328
2002/0327		if(active.exiting) return;
2002/0405/sys/src/9/port/edf.c:425,431 – 2002/0410/sys/src/9/port/edf.c:425,431
2002/0327		/* There's something waiting to be released and its time has come */ edfdequeue(&qwaitrelease);
2002/0328		edfreleasetimer();
2002/0327		edf_release(t);
2002/0410		edfrelease(t);
2002/0327		} iunlock(&edflock); sched();
2002/0405/sys/src/9/port/edf.c:442,450 – 2002/0410/sys/src/9/port/edf.c:442,449
2002/0315
2002/0327		DPRINT("%d edfdeadlineintr\n", m->machno);
2002/0405		timerdel(&cycdeadline);
2002/0328		cycdeadline.when = 0;
2002/0330		clockintrsched();
2002/0410		timerdel(&deadlinetimer[m->machno]); deadlinetimer[m->machno].when = 0;
2002/0328
2002/0327		if(active.exiting) return;
2002/0405/sys/src/9/port/edf.c:469,479 – 2002/0410/sys/src/9/port/edf.c:468,478
2002/0315		if (t->d <= now || t->S == 0LL){ /* Task has reached its deadline/slice, remove from queue */ edfdeadline(up, SSlice);
2002/0410		deadline(up, SSlice);
2002/0315		while (t = edfstack[m->machno].head){ if (now < t->d) break; edfdeadline(nil, SSlice);
2002/0410		deadline(nil, SSlice);
2002/0315		} } }
2002/0405/sys/src/9/port/edf.c:484,495 – 2002/0410/sys/src/9/port/edf.c:483,494
2002/0315		} void edf_bury(Proc *p)
2002/0410		edfbury(Proc *p)
2002/0315		{ Task *t; Proc **pp;
2002/0322		DPRINT("%d edf_bury\n", m->machno);
2002/0410		DPRINT("%d edfbury\n", m->machno);
2002/0315		ilock(&edflock); now = fastticks(nil); if ((t = p->task) == nil){
2002/0405/sys/src/9/port/edf.c:518,529 – 2002/0410/sys/src/9/port/edf.c:517,528
2002/0315		} void edf_ready(Proc *p)
2002/0410		edfready(Proc *p)
2002/0315		{ Task *t; ilock(&edflock);
2002/0322		DPRINT("%d edf_ready, %s, %d\n", m->machno, edf_statename[p->task->state], p->task->runq.n);
2002/0410		DPRINT("%d edfready, %s, %d\n", m->machno, edfstatename[p->task->state], p->task->runq.n);
2002/0315		if ((t = p->task) == nil){ /* Must be a race */ iunlock(&edflock);
2002/0405/sys/src/9/port/edf.c:543,559 – 2002/0410/sys/src/9/port/edf.c:542,558
2002/0315		/* first proc to become runnable in this task */ now = fastticks(nil); edf_resched(t);
2002/0410		edfresched(t);
2002/0315		} iunlock(&edflock); } static void edf_resched(Task *t)
2002/0410		edfresched(Task *t)
2002/0315		{ Task *xt;
2002/0322		DPRINT("%d edf_resched, %s, %d\n", m->machno, edf_statename[t->state], t->runq.n);
2002/0410		DPRINT("%d edfresched, %s, %d\n", m->machno, edfstatename[t->state], t->runq.n);
2002/0315		if (t->nproc == 0){ /* No member processes */ if (t->state > EdfIdle){
2002/0405/sys/src/9/port/edf.c:564,570 – 2002/0410/sys/src/9/port/edf.c:563,569
2002/0315		} if (t->runq.n == 0 && (up == nil || up->task != t)){ /* Member processes but none runnable */
2002/0322		DPRINT("%d edf_resched, nothing runnable\n", m->machno);
2002/0410		DPRINT("%d edfresched, nothing runnable\n", m->machno);
2002/0315		if (t->state == EdfRunning) edfpop();
2002/0405/sys/src/9/port/edf.c:589,595 – 2002/0410/sys/src/9/port/edf.c:588,594
2002/0315		t->t = now + t->T; t->r = t->t; } edf_release(t);
2002/0410		edfrelease(t);
2002/0315		break; case EdfAwaitrelease: case EdfReleased:
2002/0405/sys/src/9/port/edf.c:606,622 – 2002/0410/sys/src/9/port/edf.c:605,621
2002/0315		case EdfRunning: if (t->r <= now){ if (t->t < now){
2002/0322		DPRINT("%d edf_resched, rerelease\n", m->machno);
2002/0410		DPRINT("%d edfresched, rerelease\n", m->machno);
2002/0315		/* Period passed, rerelease */ t->r = now; xt = edfpop(); assert(xt == t); edf_release(t);
2002/0410		edfrelease(t);
2002/0315		return; } if (now < t->d){ if (t->S > 0){
2002/0322		DPRINT("%d edf_resched, resume\n", m->machno);
2002/0410		DPRINT("%d edfresched, resume\n", m->machno);
2002/0315		/* Running, not yet at deadline, leave it */ return; }else
2002/0405/sys/src/9/port/edf.c:635,649 – 2002/0410/sys/src/9/port/edf.c:634,648
2002/0315		case EdfDeadline: if (t->r <= now){ if (t->t < now){
2002/0322		DPRINT("%d edf_resched, rerelease\n", m->machno);
2002/0410		DPRINT("%d edfresched, rerelease\n", m->machno);
2002/0315		/* Period passed, rerelease */ t->r = now; edf_release(t);
2002/0410		edfrelease(t);
2002/0315		return; } if (now < t->d && (t->flags & Useblocking) == 0){ if (t->S > 0){
2002/0322		DPRINT("%d edf_resched, resume\n", m->machno);
2002/0410		DPRINT("%d edfresched, resume\n", m->machno);
2002/0315		/* Released, not yet at deadline, release (again) */ t->state = EdfReleased; edfenqueue(&qreleased, t);
2002/0405/sys/src/9/port/edf.c:663,671 – 2002/0410/sys/src/9/port/edf.c:662,670
2002/0315		} void edf_release(Task *t)
2002/0410		edfrelease(Task *t)
2002/0315		{
2002/0322		DPRINT("%d edf_release, %s, %d\n", m->machno, edf_statename[t->state], t->runq.n);
2002/0410		DPRINT("%d edfrelease, %s, %d\n", m->machno, edfstatename[t->state], t->runq.n);
2002/0315		assert(t->runq.n > 0 || (up && up->task == t)); t->t = t->r + t->T; t->d = t->r + t->D;
2002/0405/sys/src/9/port/edf.c:677,690 – 2002/0410/sys/src/9/port/edf.c:676,690
2002/0315		} Proc * edf_runproc(void)
2002/0410		edfrunproc(void)
2002/0315		{ /* Return an edf proc to run or nil */ Task *t, *nt;
2002/0410		Task *t, *nt, *xt;
2002/0315		Proc *p;
2002/0327		Ticks when;
2002/0315		static ulong nilcount;
2002/0410		int i;
2002/0315		/* Figure out if the current proc should be preempted*/ ilock(&edflock);
2002/0405/sys/src/9/port/edf.c:701,710 – 2002/0410/sys/src/9/port/edf.c:701,725
2002/0315		iunlock(&edflock); return nil; }
2002/0322		DPRINT("edf_runproc %lud\n", nilcount);
2002/0410		DPRINT("edfrunproc %lud\n", nilcount);
2002/0320		if (nt && (t == nil || (nt->d < t->d && nt->D < t->Delta))){
2002/0410		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; } } }
2002/0315		/* released task is better than current */
2002/0322		DPRINT("%d edf_runproc: released\n", m->machno);
2002/0410		DPRINT("%d edfrunproc: released\n", m->machno);
2002/0315		edfdequeue(&qreleased); assert(nt->runq.n >= 1); edfpush(nt);
2002/0405/sys/src/9/port/edf.c:712,720 – 2002/0410/sys/src/9/port/edf.c:727,735
2002/0315		t = nt; t->scheduled = now; }else{
2002/0322		DPRINT("%d edf_runproc: current\n", m->machno);
2002/0410		DPRINT("%d edfrunproc: current\n", m->machno);
2002/0315		}
2002/0410		runt:
2002/0315		assert (t->runq.n); /* Get first proc off t's run queue
2002/0405/sys/src/9/port/edf.c:735,753 – 2002/0410/sys/src/9/port/edf.c:750,767
2002/0327		when = t->d;
2002/0328		if (when < now){ DPRINT("%d edf_timer: %T too late\n", m->machno, ticks2time(now-when));
2002/0410		DPRINT("%d edftimer: %T too late\n", m->machno, ticks2time(now-when));
2002/0328		when = now; }
2002/0327		if (cycdeadline.when){ if(cycdeadline.when == when){
2002/0410		if (deadlinetimer[m->machno].when){ if(deadlinetimer[m->machno].when == when){
2002/0327		iunlock(&edflock); return p; }
2002/0405		timerdel(&cycdeadline);
2002/0410		timerdel(&deadlinetimer[m->machno]);
2002/0327		} cycdeadline.when = when;
2002/0405		timeradd(&cycdeadline);
2002/0327		clockintrsched();
2002/0410		deadlinetimer[m->machno].when = when; timeradd(&deadlinetimer[m->machno]);
2002/0315		iunlock(&edflock); return p; }
2002/0405/sys/src/9/port/edf.c:845,851 – 2002/0410/sys/src/9/port/edf.c:859,865
2002/0315		} static char * edf_testschedulability(Task *thetask)
2002/0410		edftestschedulability(Task *thetask)
2002/0315		{ Task *t; Ticks H, G, Cb, ticks;
2002/0410/sys/src/9/port/edf.c:104,113 – 2002/0411/sys/src/9/port/edf.c:104,110 (short | long)
2002/0315		int
2002/0410		edfanyready(void)
2002/0315		{ /* 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;
2002/0411		return edfstack[m->machno].head || qreleased.head;
2002/0315		} static void
2002/0410/sys/src/9/port/edf.c:686,691 – 2002/0411/sys/src/9/port/edf.c:683,693
2002/0315		static ulong nilcount;
2002/0410		int i;
2002/0315
2002/0411		if (edfstack[m->machno].head == nil && qreleased.head== nil){ // quick way out nilcount++; return nil; }
2002/0315		/* Figure out if the current proc should be preempted*/ ilock(&edflock); now = fastticks(nil);
2002/0411/sys/src/9/port/edf.c:40,45 – 2002/0420/sys/src/9/port/edf.c:40,46 (short | long)
2002/0315		Resource resources[Maxresources]; int nresources;
2002/0410		int edfstateupdate;
2002/0420		int misseddeadlines;
2002/0315		enum{ Deadline, /* Invariant for schedulability test: Deadline < Release */
2002/0411/sys/src/9/port/edf.c:465,470 – 2002/0420/sys/src/9/port/edf.c:466,473
2002/0315		if (t->d <= now || t->S == 0LL){ /* Task has reached its deadline/slice, remove from queue */
2002/0420		if (t->S > 0LL) misseddeadlines++;
2002/0410		deadline(up, SSlice);
2002/0315		while (t = edfstack[m->machno].head){ if (now < t->d)
2002/0420/sys/src/9/port/edf.c:252,257 – 2002/0503/sys/src/9/port/edf.c:252,258 (short | long)
2002/0410		deadline(Proc *p, SEvent why)
2002/0315		{ Task *t, *nt;
2002/0503		Ticks used;
2002/0315		/* Task has reached its deadline, lock must be held */
2002/0410		DPRINT("%d deadline, %s, %d\n", m->machno, edfstatename[p->task->state], p->task->runq.n);
2002/0420/sys/src/9/port/edf.c:272,277 – 2002/0503/sys/src/9/port/edf.c:273,283
2002/0410		timerdel(&deadlinetimer[m->machno]); deadlinetimer[m->machno].when = 0;
2002/0327		}
2002/0503		used = now - t->scheduled; t->S -= used; t->scheduled = now; t->total += used; t->aged = (t->aged*31 + t->C - t->S) >> 5;
2002/0315		t->d = now; t->state = EdfDeadline;
2002/0316		if(devrt) devrt(t, now, why);
2002/0420/sys/src/9/port/edf.c:330,335 – 2002/0503/sys/src/9/port/edf.c:336,342
2002/0315		t->S = t->C; t->scheduled = now; t->state = EdfRunning;
2002/0503		t->periods++;
2002/0316		if(devrt) devrt(t, now, SRun);
2002/0320		setdelta();
2002/0315		assert(t->runq.n > 0 || (up && up->task == t));
2002/0420/sys/src/9/port/edf.c:457,462 – 2002/0503/sys/src/9/port/edf.c:464,470
2002/0315		used = now - t->scheduled; t->scheduled = now;
2002/0503		t->total += used;
2002/0315		if (t->r < now){ if (t->S <= used)
2002/0420/sys/src/9/port/edf.c:466,473 – 2002/0503/sys/src/9/port/edf.c:474,483
2002/0315		if (t->d <= now || t->S == 0LL){ /* Task has reached its deadline/slice, remove from queue */
2002/0420		if (t->S > 0LL)
2002/0503		if (t->d <= now){ t->missed++;
2002/0420		misseddeadlines++;
2002/0503		}
2002/0410		deadline(up, SSlice);
2002/0315		while (t = edfstack[m->machno].head){ if (now < t->d)
2002/0420/sys/src/9/port/edf.c:728,736 – 2002/0503/sys/src/9/port/edf.c:738,746
2002/0315		edfdequeue(&qreleased); assert(nt->runq.n >= 1); edfpush(nt); nt->state = EdfRunning; t = nt; t->scheduled = now;
2002/0503		t->periods++;
2002/0315		}else{
2002/0410		DPRINT("%d edfrunproc: current\n", m->machno);
2002/0315		}
2002/0420/sys/src/9/port/edf.c:741,746 – 2002/0503/sys/src/9/port/edf.c:751,757
2002/0315		* No need to lock runq, edflock always held to access runq */ t->state = EdfRunning;
2002/0503		t->periods++;
2002/0315		p = t->runq.head; if ((t->runq.head = p->rnext) == nil) t->runq.tail = nil;
2002/0503/sys/src/9/port/edf.c:49,54 – 2002/0704/sys/src/9/port/edf.c:49,55 (short | long)
2002/0315		static int earlierrelease(Task *t1, Task *t2) {return t1->r < t2->r;} static int earlierdeadline(Task *t1, Task *t2) {return t1->d < t2->d;}
2002/0704		static void edfrelease(Task *t);
2002/0315		/* Tasks waiting for release, head earliest release time */ Taskq qwaitrelease = {{0}, nil, earlierrelease};
2002/0503/sys/src/9/port/edf.c:71,77 – 2002/0704/sys/src/9/port/edf.c:72,78
2002/0405		static void edfdeadlineintr(Ureg*, Timer*);
2002/0410		static char * edftestschedulability(Task *thetask);
2002/0315		void
2002/0704		static void
2002/0410		edfinit(void)
2002/0315		{
2002/0410		int i;
2002/0503/sys/src/9/port/edf.c:96,108 – 2002/0704/sys/src/9/port/edf.c:97,109
2002/0315		iunlock(&edflock); } int
2002/0704		static int
2002/0315		isedf(Proc *p) { return p && p->task && p->task->state >= EdfIdle; } int
2002/0704		static int
2002/0410		edfanyready(void)
2002/0315		{
2002/0411		return edfstack[m->machno].head || qreleased.head;
2002/0503/sys/src/9/port/edf.c:220,226 – 2002/0704/sys/src/9/port/edf.c:221,227
2002/0410		timeradd(&releasetimer[m->machno]);
2002/0327		} void
2002/0704		static void
2002/0410		edfblock(Proc *p)
2002/0315		{ Task *t, *pt;
2002/0503/sys/src/9/port/edf.c:284,290 – 2002/0704/sys/src/9/port/edf.c:285,291
2002/0410		edfresched(t);
2002/0315		} void
2002/0704		static void
2002/0410		edfdeadline(Proc *p)
2002/0315		{
2002/0410		DPRINT("%d edfdeadline\n", m->machno);
2002/0503/sys/src/9/port/edf.c:295,301 – 2002/0704/sys/src/9/port/edf.c:296,302
2002/0315		iunlock(&edflock); } char *
2002/0704		static char *
2002/0410		edfadmit(Task *t)
2002/0315		{ char *err;
2002/0503/sys/src/9/port/edf.c:361,367 – 2002/0704/sys/src/9/port/edf.c:362,368
2002/0315		return nil; } void
2002/0704		static void
2002/0410		edfexpel(Task *t)
2002/0315		{ Task *tt;
2002/0503/sys/src/9/port/edf.c:492,498 – 2002/0704/sys/src/9/port/edf.c:493,499
2002/0315		splhi(); } void
2002/0704		static void
2002/0410		edfbury(Proc *p)
2002/0315		{ Task *t;
2002/0503/sys/src/9/port/edf.c:526,532 – 2002/0704/sys/src/9/port/edf.c:527,533
2002/0315		iunlock(&edflock); } void
2002/0704		static void
2002/0410		edfready(Proc *p)
2002/0315		{ Task *t;
2002/0503/sys/src/9/port/edf.c:671,677 – 2002/0704/sys/src/9/port/edf.c:672,678
2002/0315		} } void
2002/0704		static void
2002/0410		edfrelease(Task *t)
2002/0315		{
2002/0410		DPRINT("%d edfrelease, %s, %d\n", m->machno, edfstatename[t->state], t->runq.n);
2002/0503/sys/src/9/port/edf.c:685,691 – 2002/0704/sys/src/9/port/edf.c:686,692
2002/0316		if(devrt) devrt(t, now, SRelease);
2002/0315		} Proc *
2002/0704		static Proc *
2002/0410		edfrunproc(void)
2002/0315		{ /* Return an edf proc to run or nil */
2002/0503/sys/src/9/port/edf.c:961,963 – 2002/0704/sys/src/9/port/edf.c:962,977
2002/0315		assert(time >= 0); return uvmuldiv(time, fasthz, Onesecond); }
2002/0704		Edfinterface realedf = { .isedf = isedf, .edfbury = edfbury, .edfanyready = edfanyready, .edfready = edfready, .edfrunproc = edfrunproc, .edfblock = edfblock, .edfinit = edfinit, .edfexpel = edfexpel, .edfadmit = edfadmit, .edfdeadline = edfdeadline, };
2002/0704/sys/src/9/port/edf.c:32,44 – 2002/0831/sys/src/9/port/edf.c:32,43 (short | long)
2002/0315		static int initialized; static uvlong fasthz; static Ticks now;
2002/0831		/* Edfschedlock protects modification of sched params, including resources */
2002/0328		QLock edfschedlock;
2002/0315		Lock edflock; Task tasks[Maxtasks]; int ntasks; Resource resources[Maxresources]; int nresources;
2002/0831		Head tasks; Head resources;
2002/0410		int edfstateupdate;
2002/0420		int misseddeadlines;
2002/0315
2002/0704/sys/src/9/port/edf.c:301,306 – 2002/0831/sys/src/9/port/edf.c:300,306
2002/0315		{ char *err;
2002/0831		/* Called with edfschedlock held */
2002/0315		if (t->state != EdfExpelled) return "task state"; /* should never happen */
2002/0316
2002/0704/sys/src/9/port/edf.c:316,327 – 2002/0831/sys/src/9/port/edf.c:316,326
2002/0316		if (t->C > t->D) return "C > D";
2002/0315		qlock(&edfschedlock);
2002/0410		if (err = edftestschedulability(t)){
2002/0315		qunlock(&edfschedlock); return err; } ilock(&edflock);
2002/0831		qunlock(&edfschedlock);
2002/0410		DPRINT("%d edfadmit, %s, %d\n", m->machno, edfstatename[t->state], t->runq.n);
2002/0315		now = fastticks(nil);
2002/0704/sys/src/9/port/edf.c:358,364 – 2002/0831/sys/src/9/port/edf.c:357,363
2002/0315		} } iunlock(&edflock); qunlock(&edfschedlock);
2002/0831		qlock(&edfschedlock);
2002/0315		return nil; }
2002/0704/sys/src/9/port/edf.c:367,373 – 2002/0831/sys/src/9/port/edf.c:366,372
2002/0315		{ Task *tt; qlock(&edfschedlock);
2002/0831		/* Called with edfschedlock held */
2002/0315		ilock(&edflock);
2002/0410		DPRINT("%d edfexpel, %s, %d\n", m->machno, edfstatename[t->state], t->runq.n);
2002/0315		now = fastticks(nil);
2002/0704/sys/src/9/port/edf.c:376,382 – 2002/0831/sys/src/9/port/edf.c:375,380
2002/0315		case EdfExpelled: /* That was easy */ iunlock(&edflock); qunlock(&edfschedlock); return; case EdfAdmitted: case EdfIdle:
2002/0704/sys/src/9/port/edf.c:408,414 – 2002/0831/sys/src/9/port/edf.c:406,411
2002/0316		if(devrt) devrt(t, now, SExpel);
2002/0320		setdelta();
2002/0315		iunlock(&edflock); qunlock(&edfschedlock); return; }
2002/0704/sys/src/9/port/edf.c:497,503 – 2002/0831/sys/src/9/port/edf.c:494,499
2002/0410		edfbury(Proc *p)
2002/0315		{ Task *t; Proc **pp;
2002/0410		DPRINT("%d edfbury\n", m->machno);
2002/0315		ilock(&edflock);
2002/0704/sys/src/9/port/edf.c:509,524 – 2002/0831/sys/src/9/port/edf.c:505,516
2002/0315		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; }
2002/0831		delist(&t->procs, p);
2002/0315		if (t->runq.head == nil){ edfpop(); t->state = EdfBlocked; } if (t->nproc == 0){
2002/0831		if (t->procs.n == 0){
2002/0315		assert(t->runq.head == nil); t->state = EdfIdle; }
2002/0704/sys/src/9/port/edf.c:564,570 – 2002/0831/sys/src/9/port/edf.c:556,562
2002/0315		Task *xt;
2002/0410		DPRINT("%d edfresched, %s, %d\n", m->machno, edfstatename[t->state], t->runq.n);
2002/0315		if (t->nproc == 0){
2002/0831		if (t->procs.n == 0){
2002/0315		/* No member processes */ if (t->state > EdfIdle){ t->state = EdfIdle;
2002/0704/sys/src/9/port/edf.c:788,811 – 2002/0831/sys/src/9/port/edf.c:780,812
2002/0315		static void
2002/0320		setdelta(void)
2002/0315		{ Resource *r, **rr; Task **tt, *t;
2002/0831		Resource *r; Task *t; List *lr, *lt;
2002/0315		for (r = resources; r < resources + nelem(resources); r++){ if (r->name == nil) continue;
2002/0831		for (lr = resources.next; lr; lr = lr->next){ r = lr->i; assert(r);
2002/0320		r->Delta = ~0LL;
2002/0315		for (tt = r->tasks; tt < r->tasks + nelem(r->tasks); tt++)
2002/0320		if (*tt && (*tt)->D < r->Delta) r->Delta = (*tt)->D;
2002/0831		for (lt = r->tasks.next; lt; lt = lt->next){ t = lt->i; assert(t); if (t->D < r->Delta) r->Delta = t->D; }
2002/0315		} for (t = tasks; t < tasks + nelem(tasks); t++){
2002/0831		for (lt = tasks.next; lt ; lt = lt->next){ t = lt->i; assert(t);
2002/0315		if (t->state < EdfIdle) continue;
2002/0320		t->Delta = t->D;
2002/0315		for (rr = t->res; rr < t->res + nelem(t->res); rr++)
2002/0320		if (*rr && (*rr)->Delta < t->Delta) t->Delta = (*rr)->Delta;
2002/0831		for (lr = t->res.next; lr; lr = lr->next){ r = lr->i; assert(r); if (r->Delta < t->Delta) t->Delta = r->Delta; }
2002/0315		} }
2002/0704/sys/src/9/port/edf.c:812,835 – 2002/0831/sys/src/9/port/edf.c:813,845
2002/0315		static void
2002/0320		testdelta(Task *thetask)
2002/0315		{ Resource *r, **rr; Task **tt, *t;
2002/0831		Resource *r; Task *t; List *lr, *lt;
2002/0315		for (r = resources; r < resources + nelem(resources); r++){ if (r->name == nil) continue;
2002/0831		for (lr = resources.next; lr; lr = lr->next){ r = lr->i; assert(r);
2002/0320		r->testDelta = ~0ULL;
2002/0315		for (tt = r->tasks; tt < r->tasks + nelem(r->tasks); tt++)
2002/0320		if (*tt && (*tt)->D < r->testDelta) r->testDelta = (*tt)->D;
2002/0831		for (lt = r->tasks.next; lt; lt = lt->next){ t = lt->i; assert(t); if (t->D < r->testDelta) r->testDelta = t->D; }
2002/0315		} for (t = tasks; t < tasks + nelem(tasks); t++){
2002/0831		for (lt = tasks.next; lt ; lt = lt->next){ t = lt->i; assert(t);
2002/0315		if (t->state <= EdfExpelled && t != thetask) continue;
2002/0320		t->testDelta = t->D;
2002/0315		for (rr = t->res; rr < t->res + nelem(t->res); rr++)
2002/0320		if (*rr && (*rr)->testDelta < t->testDelta) t->testDelta = (*rr)->testDelta;
2002/0831		for (lr = t->res.next; lr; lr = lr->next){ r = lr->i; assert(r); if (r->testDelta < t->testDelta) t->testDelta = r->testDelta; }
2002/0315		} }
2002/0704/sys/src/9/port/edf.c:838,846 – 2002/0831/sys/src/9/port/edf.c:848,859
2002/0315		{ Task *t; Ticks Cb;
2002/0831		List *lt;
2002/0315		Cb = 0; for (t = tasks; t < tasks + Maxtasks; t++){
2002/0831		for (lt = tasks.next; lt ; lt = lt->next){ t = lt->i; assert(t);
2002/0315		if (t->state <= EdfExpelled && t != thetask) continue;
2002/0320		if (t->testDelta <= ticks && ticks < t->D && Cb < t->C)
2002/0704/sys/src/9/port/edf.c:881,886 – 2002/0831/sys/src/9/port/edf.c:894,900
2002/0315		Task *t; Ticks H, G, Cb, ticks; int steps;
2002/0831		List *l;
2002/0315		/* initialize */
2002/0320		testdelta(thetask);
2002/0704/sys/src/9/port/edf.c:887,899 – 2002/0831/sys/src/9/port/edf.c:901,915
2002/0315		if (thetask && (thetask->flags & Verbose)) pprint("schedulability test\n"); qschedulability = nil; for (t = tasks; t < tasks + Maxtasks; t++){
2002/0831		for (l = tasks.next; l; l = l->next){ t = l->i; assert(t);
2002/0315		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);
2002/0831		pprint("\tInit: enqueue task %lud\n", t->taskno);
2002/0315		testenq(t); } H=0;
2002/0704/sys/src/9/port/edf.c:908,914 – 2002/0831/sys/src/9/port/edf.c:924,930
2002/0315		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,
2002/0831		steps, ticks2time(ticks), t->taskno,
2002/0315		ticks2time(t->C), ticks2time(H), ticks2time(Cb)); if (H+Cb>ticks) return "not schedulable";
2002/0704/sys/src/9/port/edf.c:919,925 – 2002/0831/sys/src/9/port/edf.c:935,941
2002/0315		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,
2002/0831		steps, ticks2time(ticks), t->taskno,
2002/0315		ticks2time(t->C), ticks2time(G)); if(ticks && G <= ticks) return nil;
2002/0831/sys/src/9/port/edf.c:733,739 – 2002/0912/sys/src/9/port/edf.c:733,738 (short | long)
2002/0315		edfpush(nt); t = nt; t->scheduled = now;
2002/0503		t->periods++;
2002/0315		}else{
2002/0410		DPRINT("%d edfrunproc: current\n", m->machno);
2002/0315		}
2002/0912/sys/src/9/port/edf.c:5,12 – 2002/0927/sys/src/9/port/edf.c:5,11 (short | long)
2002/0315		#include "dat.h" #include "fns.h" #include "../port/error.h"
2002/0316		#include "../port/devrealtime.h"
2002/0315		#include "../port/edf.h"
2002/0927		#include "../port/realtime.h"
2002/0315		/* debugging */ int edfprint = 0;
2002/0912/sys/src/9/port/edf.c:30,36 – 2002/0927/sys/src/9/port/edf.c:29,34
2002/0410		static Timer releasetimer[MAXMACH]; /* Time of next release */
2002/0327
2002/0315		static int initialized; static uvlong fasthz; static Ticks now;
2002/0831		/* Edfschedlock protects modification of sched params, including resources */
2002/0328		QLock edfschedlock;
2002/0912/sys/src/9/port/edf.c:62,67 – 2002/0927/sys/src/9/port/edf.c:60,67
2002/0315		/* Running/Preempted EDF tasks, head running, one stack per processor */ Taskq edfstack[MAXMACH];
2002/0927		static Task *qschedulability;
2002/0316		void (*devrt)(Task*, Ticks, int);
2002/0315
2002/0410		static void edfresched(Task *t);
2002/0912/sys/src/9/port/edf.c:83,89 – 2002/0927/sys/src/9/port/edf.c:83,88
2002/0315		iunlock(&edflock); return; } fastticks(&fasthz);
2002/0410		for (i = 0; i < conf.nmach; i++){ deadlinetimer[i].f = edfdeadlineintr; deadlinetimer[i].a = &deadlinetimer[i];
2002/0912/sys/src/9/port/edf.c:298,304 – 2002/0927/sys/src/9/port/edf.c:297,305
2002/0704		static char *
2002/0410		edfadmit(Task *t)
2002/0315		{ char *err;
2002/0927		char *err, *p; static char csndump[512]; CSN *c;
2002/0315
2002/0831		/* Called with edfschedlock held */
2002/0315		if (t->state != EdfExpelled)
2002/0912/sys/src/9/port/edf.c:316,326 – 2002/0927/sys/src/9/port/edf.c:317,335
2002/0316		if (t->C > t->D) return "C > D";
2002/0927		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);
2002/0410		if (err = edftestschedulability(t)){
2002/0315		return err; } ilock(&edflock);
2002/0831		qunlock(&edfschedlock);
2002/0410		DPRINT("%d edfadmit, %s, %d\n", m->machno, edfstatename[t->state], t->runq.n);
2002/0315		now = fastticks(nil);
2002/0912/sys/src/9/port/edf.c:339,344 – 2002/0927/sys/src/9/port/edf.c:348,357
2002/0503		t->periods++;
2002/0316		if(devrt) devrt(t, now, SRun);
2002/0320		setdelta();
2002/0927		for (c = (CSN*)t->csns.next; c; c = (CSN*)c->next){ DEBUG("admit csn: C=%T\n", ticks2time(c->C)); c->S = c->C; }
2002/0315		assert(t->runq.n > 0 || (up && up->task == t)); edfpush(t);
2002/0410		if (deadlinetimer[m->machno].when)
2002/0912/sys/src/9/port/edf.c:357,363 – 2002/0927/sys/src/9/port/edf.c:370,375
2002/0315		} } iunlock(&edflock);
2002/0831		qlock(&edfschedlock);
2002/0315		return nil; }
2002/0912/sys/src/9/port/edf.c:413,418 – 2002/0927/sys/src/9/port/edf.c:425,431
2002/0405		edfreleaseintr(Ureg*, Timer*)
2002/0315		{
2002/0327		Task *t;
2002/0927		extern int panicking;
2002/0327
2002/0328		DPRINT("%d edfreleaseintr\n", m->machno);
2002/0327
2002/0912/sys/src/9/port/edf.c:419,425 – 2002/0927/sys/src/9/port/edf.c:432,438
2002/0410		timerdel(&releasetimer[m->machno]); releasetimer[m->machno].when = 0;
2002/0328
2002/0327		if(active.exiting)
2002/0927		if(panicking || active.exiting)
2002/0327		return; ilock(&edflock);
2002/0912/sys/src/9/port/edf.c:442,447 – 2002/0927/sys/src/9/port/edf.c:455,464
2002/0328
2002/0315		Ticks used; Task *t;
2002/0927		Resource *r; char buf[128]; int noted; extern int panicking;
2002/0315
2002/0327		DPRINT("%d edfdeadlineintr\n", m->machno);
2002/0912/sys/src/9/port/edf.c:448,459 – 2002/0927/sys/src/9/port/edf.c:465,477
2002/0410		timerdel(&deadlinetimer[m->machno]); deadlinetimer[m->machno].when = 0;
2002/0328
2002/0327		if(active.exiting)
2002/0927		if(panicking || active.exiting)
2002/0327		return; ilock(&edflock);
2002/0315		// If up is not set, we're running inside the scheduler // for non-real-time processes.
2002/0927		// for non-real-time processes. noted = 0;
2002/0315		if (up && isedf(up)) {
2002/0328		now = fastticks(nil);
2002/0912/sys/src/9/port/edf.c:465,476 – 2002/0927/sys/src/9/port/edf.c:483,508
2002/0503		t->total += used;
2002/0315		if (t->r < now){ if (t->S <= used)
2002/0927		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){
2002/0315		t->S = 0LL; else
2002/0927		if (!noted){ noted++; snprint(buf, sizeof buf, "sys: deadline miss: runtime"); } }else
2002/0315		t->S -= used;                  if (t->d <= now || t->S == 0LL){
2002/0927		if (t->d <= now || t->S == 0LL || t->curcsn == 0LL){
2002/0315		/* Task has reached its deadline/slice, remove from queue */
2002/0503		if (t->d <= now){ t->missed++;
2002/0912/sys/src/9/port/edf.c:477,482 – 2002/0927/sys/src/9/port/edf.c:509,515
2002/0420		misseddeadlines++;
2002/0503		}
2002/0410		deadline(up, SSlice);
2002/0927
2002/0315		while (t = edfstack[m->machno].head){ if (now < t->d) break;
2002/0912/sys/src/9/port/edf.c:486,491 – 2002/0927/sys/src/9/port/edf.c:519,526
2002/0315		} } iunlock(&edflock);
2002/0927		if (noted) postnote(up, 1, buf, NUser);
2002/0315		sched(); splhi(); }
2002/0912/sys/src/9/port/edf.c:667,672 – 2002/0927/sys/src/9/port/edf.c:702,709
2002/0704		static void
2002/0410		edfrelease(Task *t)
2002/0315		{
2002/0927		CSN *c;
2002/0410		DPRINT("%d edfrelease, %s, %d\n", m->machno, edfstatename[t->state], t->runq.n);
2002/0315		assert(t->runq.n > 0 || (up && up->task == t)); t->t = t->r + t->T;
2002/0912/sys/src/9/port/edf.c:673,678 – 2002/0927/sys/src/9/port/edf.c:710,719
2002/0315		t->d = t->r + t->D;
2002/0316		if(devrt) devrt(t, t->d, SDeadline);
2002/0315		t->S = t->C;
2002/0927		for (c = (CSN*)t->csns.next; c; c = (CSN*)c->next){ DEBUG("release csn: C=%T\n", ticks2time(c->C)); c->S = c->C; }
2002/0315		t->state = EdfReleased; edfenqueue(&qreleased, t);
2002/0316		if(devrt) devrt(t, now, SRelease);
2002/0912/sys/src/9/port/edf.c:781,809 – 2002/0927/sys/src/9/port/edf.c:822,865
2002/0315		{
2002/0831		Resource *r; Task *t; List *lr, *lt;
2002/0927		int R; List *lr, *l; TaskLink *lt; CSN *c;
2002/0315
2002/0831		for (lr = resources.next; lr; lr = lr->next){ r = lr->i; assert(r);
2002/0320		r->Delta = ~0LL;
2002/0831		for (lt = r->tasks.next; lt; lt = lt->next){
2002/0927		r->Delta = Infinity; R = 1; for (lt = (TaskLink*)r->tasks.next; lt; lt = (TaskLink*)lt->next){
2002/0831		t = lt->i; assert(t); if (t->D < r->Delta)
2002/0927		if (t->D < r->Delta){
2002/0831		r->Delta = t->D;
2002/0927		} if (lt->R == 0){ R = 0; }
2002/0831		}
2002/0927		if (R) r->Delta = Infinity; /* Read-only resource, no exclusion */
2002/0315		}
2002/0831		for (lt = tasks.next; lt ; lt = lt->next){ t = lt->i;
2002/0927		/* Enumerate the critical sections */ for (l = tasks.next; l ; l = l->next){ t = l->i;
2002/0831		assert(t);
2002/0315		if (t->state < EdfIdle)
2002/0927		if (t->state <= EdfExpelled)
2002/0315		continue;
2002/0320		t->Delta = t->D;
2002/0831		for (lr = t->res.next; lr; lr = lr->next){ r = lr->i;
2002/0927		t->Delta = Infinity; for (c = (CSN*)t->csns.next; c; c = (CSN*)c->next){ r = c->i;
2002/0831		assert(r); if (r->Delta < t->Delta)
2002/0927		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)
2002/0831		t->Delta = r->Delta; }
2002/0315		}
2002/0912/sys/src/9/port/edf.c:814,868 – 2002/0927/sys/src/9/port/edf.c:870,973
2002/0315		{
2002/0831		Resource *r; Task *t; List *lr, *lt;
2002/0927		int R; List *lr, *l; TaskLink *lt; CSN *c;
2002/0315
2002/0831		for (lr = resources.next; lr; lr = lr->next){ r = lr->i; assert(r);
2002/0320		r->testDelta = ~0ULL;
2002/0831		for (lt = r->tasks.next; lt; lt = lt->next){
2002/0927		DEBUG("Resource %s: ", r->name); r->testDelta = Infinity; R = 1; for (lt = (TaskLink*)r->tasks.next; lt; lt = (TaskLink*)lt->next){
2002/0831		t = lt->i; assert(t); if (t->D < r->testDelta)
2002/0927		if (t->D < r->testDelta){
2002/0831		r->testDelta = t->D;
2002/0927		DEBUG("%d→%T ", t->taskno, ticks2time(t->D)); } if (lt->R == 0){ DEBUG("%d→X ", t->taskno); R = 0; }
2002/0831		}
2002/0927		if (R) r->testDelta = Infinity; /* Read-only resource, no exclusion */ DEBUG("tΔ = %T\n", ticks2time(r->testDelta));
2002/0315		}
2002/0831		for (lt = tasks.next; lt ; lt = lt->next){ t = lt->i;
2002/0927		/* Enumerate the critical sections */ for (l = tasks.next; l ; l = l->next){ t = l->i;
2002/0831		assert(t);
2002/0315		if (t->state <= EdfExpelled && t != thetask) continue;
2002/0320		t->testDelta = t->D;
2002/0831		for (lr = t->res.next; lr; lr = lr->next){ r = lr->i;
2002/0927		t->testDelta = Infinity; for (c = (CSN*)t->csns.next; c; c = (CSN*)c->next){ r = c->i;
2002/0831		assert(r); if (r->testDelta < t->testDelta)
2002/0927		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)
2002/0831		t->testDelta = r->testDelta;
2002/0927		DEBUG("Task %d Resource %s: tΔ = %T\n", t->taskno, r->name, ticks2time(r->testDelta));
2002/0831		}
2002/0315		} } static Ticks blockcost(Ticks ticks, Task *thetask)
2002/0927		blockcost(Ticks ticks, Task *task, Task *thetask)
2002/0315		{
2002/0927		Ticks Cb, Cbt; List *l; Resource *r; CSN *c, *lc; int R;
2002/0315		Task *t; Ticks Cb;
2002/0831		List *lt;
2002/0315		Cb = 0;
2002/0831		for (lt = tasks.next; lt ; lt = lt->next){ t = lt->i; assert(t);
2002/0315		if (t->state <= EdfExpelled && t != thetask) continue;
2002/0320		if (t->testDelta <= ticks && ticks < t->D && Cb < t->C)
2002/0315		Cb = t->C;
2002/0927		/* 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, ");
2002/0315		}
2002/0927		DEBUG("Cb = %T\n", ticks2time(Cb));
2002/0315		return Cb; } static Task *qschedulability;                  static void testenq(Task *t) {
2002/0912/sys/src/9/port/edf.c:898,904 – 2002/0927/sys/src/9/port/edf.c:1003,1009
2002/0315		/* initialize */
2002/0320		testdelta(thetask);
2002/0315		if (thetask && (thetask->flags & Verbose)) pprint("schedulability test\n");
2002/0927		pprint("schedulability test for task %d\n", thetask->taskno);
2002/0315		qschedulability = nil;
2002/0831		for (l = tasks.next; l; l = l->next){ t = l->i;
2002/0912/sys/src/9/port/edf.c:908,914 – 2002/0927/sys/src/9/port/edf.c:1013,1019
2002/0315		t->testtype = Release; t->testtime = 0; if (thetask && (thetask->flags & Verbose))
2002/0831		pprint("\tInit: enqueue task %lud\n", t->taskno);
2002/0927		pprint("\tInit: enqueue task %d\n", t->taskno);
2002/0315		testenq(t); } H=0;
2002/0912/sys/src/9/port/edf.c:920,932 – 2002/0927/sys/src/9/port/edf.c:1025,1041
2002/0315		switch (t->testtype){ case Deadline: H += t->C; Cb = blockcost(ticks, thetask);
2002/0927		Cb = blockcost(ticks, t, thetask);
2002/0315		if (thetask && (thetask->flags & Verbose)) pprint("\tStep %3d, Ticks %T, task %lud, deadline, H += %T → %T, Cb = %T\n",
2002/0927		pprint("\tStep %3d, Ticks %T, task %d, deadline, H += %T → %T, Cb = %T\n",
2002/0831		steps, ticks2time(ticks), t->taskno,
2002/0315		ticks2time(t->C), ticks2time(H), ticks2time(Cb)); if (H+Cb>ticks)
2002/0927		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));
2002/0315		return "not schedulable";
2002/0927		}
2002/0315		t->testtime += t->T - t->D; t->testtype = Release; testenq(t);
2002/0912/sys/src/9/port/edf.c:933,943 – 2002/0927/sys/src/9/port/edf.c:1042,1056
2002/0315		break; case Release: if (thetask && (thetask->flags & Verbose)) pprint("\tStep %3d, Ticks %T, task %lud, release, G %T, C%T\n",
2002/0927		pprint("\tStep %3d, Ticks %T, task %d, release, G %T, C%T\n",
2002/0831		steps, ticks2time(ticks), t->taskno,
2002/0315		ticks2time(t->C), ticks2time(G)); if(ticks && G <= ticks)
2002/0927		if(ticks && G <= ticks){ if (thetask && (thetask->flags & Verbose)) pprint("task %d schedulable: G=%T <= ticks=%T\n", thetask->taskno, ticks2time(G), ticks2time(ticks));
2002/0315		return nil;
2002/0927		}
2002/0315		G += t->C; t->testtime += t->D; t->testtype = Deadline;
2002/0912/sys/src/9/port/edf.c:950,981 – 2002/0927/sys/src/9/port/edf.c:1063,1126
2002/0315		return "probably not schedulable"; } static uvlong uvmuldiv(uvlong x, ulong num, ulong den)
2002/0927		static void resacquire(Task *t, CSN *c)
2002/0315		{ /* multiply, then divide, avoiding overflow */ uvlong hi;
2002/0927		Ticks now, when, used;
2002/0315		hi = (x & 0xffffffff00000000LL) >> 32; x &= 0xffffffffLL; hi *= num; return (x*num + (hi%den << 32)) / den + (hi/den << 32);
2002/0927		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 */
2002/0315		} Time ticks2time(Ticks ticks)
2002/0927		static void resrelease(Task *t)
2002/0315		{ assert(ticks >= 0);
2002/0320		if (fasthz == 0) fastticks(&fasthz);
2002/0315		return uvmuldiv(ticks, Onesecond, fasthz); }
2002/0927		Ticks now, when, used; CSN *c;
2002/0315		Ticks time2ticks(Time time) { assert(time >= 0); return uvmuldiv(time, fasthz, Onesecond);
2002/0927		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);
2002/0315		}
2002/0704		Edfinterface realedf = {
2002/0912/sys/src/9/port/edf.c:989,992 – 2002/0927/sys/src/9/port/edf.c:1134,1139
2002/0704		.edfexpel = edfexpel, .edfadmit = edfadmit, .edfdeadline = edfdeadline,
2002/0927		.resacquire = resacquire, .resrelease = resrelease,
2002/0704		};
2002/0927/sys/src/9/port/edf.c:64,75 – 2002/1001/sys/src/9/port/edf.c:64,76 (short | long)
2002/0927
2002/0316		void (*devrt)(Task*, Ticks, int);
2002/0315
2002/0410		static void edfresched(Task *t);
2002/1001		static void edfresched(Task*);
2002/0320		static void setdelta(void); static void testdelta(Task *thetask);
2002/0405		static void edfreleaseintr(Ureg *, Timer *cy);
2002/1001		static void testdelta(Task*); static void edfreleaseintr(Ureg*, Timer*);
2002/0405		static void edfdeadlineintr(Ureg*, Timer*);
2002/0410		static char * edftestschedulability(Task *thetask);
2002/1001		static char * edftestschedulability(Task*); static void resrelease(Task*);
2002/0315
2002/0704		static void
2002/0410		edfinit(void)
2002/0927/sys/src/9/port/edf.c:449,455 – 2002/1001/sys/src/9/port/edf.c:450,456
2002/0327		} static void
2002/0405		edfdeadlineintr(Ureg*, Timer*)
2002/1001		edfdeadlineintr(Ureg*, Timer *timer)
2002/0327		{
2002/0328		/* Task reached deadline */
2002/0927/sys/src/9/port/edf.c:462,469 – 2002/1001/sys/src/9/port/edf.c:463,470
2002/0315
2002/0327		DPRINT("%d edfdeadlineintr\n", m->machno);
2002/0410		timerdel(&deadlinetimer[m->machno]); deadlinetimer[m->machno].when = 0;
2002/1001		if (timer) timer->when = 0;
2002/0328
2002/0927		if(panicking || active.exiting)
2002/0327		return;
2002/0927/sys/src/9/port/edf.c:486,491 – 2002/1001/sys/src/9/port/edf.c:487,493
2002/0927		if (t->curcsn){ if (t->curcsn->S <= used){ t->curcsn->S = 0LL;
2002/1001		resrelease(t);
2002/0927		r = t->curcsn->i; noted++; snprint(buf, sizeof buf, "sys: deadline miss: resource %s", r->name);
2002/0927/sys/src/9/port/edf.c:1083,1088 – 2002/1001/sys/src/9/port/edf.c:1085,1091
2002/0927		} t->Delta = c->Delta; t->curcsn = c;
2002/1001		if(devrt) devrt(t, now, SResacq);
2002/0927		/* priority is going up, no need to reschedule */
2002/0315		}
2002/0927/sys/src/9/port/edf.c:1113,1118 – 2002/1001/sys/src/9/port/edf.c:1116,1122
2002/0927		}else t->Delta = Infinity; c->S = 0LL; /* don't allow reuse */
2002/1001		if(devrt) devrt(t, now, SResrel);
2002/0927		if (deadlinetimer[m->machno].when) timerdel(&deadlinetimer[m->machno]); deadlinetimer[m->machno].when = when;
2002/1001/sys/src/9/port/edf.c:5,11 – 2002/1119/sys/src/9/port/edf.c:5,12 (short | long)
2002/0315		#include "dat.h" #include "fns.h" #include "../port/error.h"
2002/0927		#include "../port/realtime.h"
2002/1119		#include "realtime.h" #include "../port/edf.h"
2002/0315		/* debugging */ int edfprint = 0;
2002/1119/sys/src/9/port/edf.c:738,743 – 2002/1217/sys/src/9/port/edf.c:738,744 (short | long)
2002/0411		nilcount++; return nil; }
2002/1217
2002/0315		/* Figure out if the current proc should be preempted*/ ilock(&edflock); now = fastticks(nil);
2002/1119/sys/src/9/port/edf.c:773,779 – 2002/1217/sys/src/9/port/edf.c:774,780
2002/0315		/* released task is better than current */
2002/0410		DPRINT("%d edfrunproc: released\n", m->machno);
2002/0315		edfdequeue(&qreleased); assert(nt->runq.n >= 1);
2002/1217		assert(nt->runq.n >= 1 || (up && up->task == nt));
2002/0315		edfpush(nt); t = nt; t->scheduled = now;
2002/1217/sys/src/9/port/edf.c:213,220 – 2002/1218/sys/src/9/port/edf.c:213,218 (short | long)
2002/0328		if ((t = qwaitrelease.head) == nil)
2002/0327		return;
2002/0328		DPRINT("edfreleasetimer clock\n");
2002/0410		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;
2002/1217/sys/src/9/port/edf.c:356,363 – 2002/1218/sys/src/9/port/edf.c:354,359
2002/0927		}
2002/0315		assert(t->runq.n > 0 || (up && up->task == t)); edfpush(t);
2002/0410		if (deadlinetimer[m->machno].when) timerdel(&deadlinetimer[m->machno]); deadlinetimer[m->machno].when = t->d; timeradd(&deadlinetimer[m->machno]);
2002/0315		}else{
2002/1217/sys/src/9/port/edf.c:478,483 – 2002/1218/sys/src/9/port/edf.c:474,481
2002/0328		now = fastticks(nil);
2002/0315		t = up->task;
2002/1218		assert(t->state == EdfRunning);
2002/0315		assert(t->scheduled > 0); used = now - t->scheduled;
2002/1217/sys/src/9/port/edf.c:806,817 – 2002/1218/sys/src/9/port/edf.c:804,812
2002/0410		DPRINT("%d edftimer: %T too late\n", m->machno, ticks2time(now-when));
2002/0328		when = now; }
2002/0410		if (deadlinetimer[m->machno].when){ if(deadlinetimer[m->machno].when == when){
2002/0327		iunlock(&edflock); return p; }
2002/0410		timerdel(&deadlinetimer[m->machno]);
2002/1218		if(deadlinetimer[m->machno].when == when){ iunlock(&edflock); return p;
2002/0327		}
2002/0410		deadlinetimer[m->machno].when = when; timeradd(&deadlinetimer[m->machno]);
2002/1217/sys/src/9/port/edf.c:1081,1087 – 2002/1218/sys/src/9/port/edf.c:1076,1081
2002/0927		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]); }
2002/1217/sys/src/9/port/edf.c:1119,1126 – 2002/1218/sys/src/9/port/edf.c:1113,1118
2002/0927		t->Delta = Infinity; c->S = 0LL; /* don't allow reuse */
2002/1001		if(devrt) devrt(t, now, SResrel);
2002/0927		if (deadlinetimer[m->machno].when) timerdel(&deadlinetimer[m->machno]); deadlinetimer[m->machno].when = when; timeradd(&deadlinetimer[m->machno]);
2002/1218/sys/src/9/port/edf.c:427,440 – 2002/1219/sys/src/9/port/edf.c:427,437 (short | long)
2002/0327
2002/0328		DPRINT("%d edfreleaseintr\n", m->machno);
2002/0327
2002/0410		timerdel(&releasetimer[m->machno]); releasetimer[m->machno].when = 0;
2002/0328
2002/0927		if(panicking || active.exiting)
2002/0327		return; ilock(&edflock);
2002/0328		now = fastticks(nil);
2002/1219		ilock(&edflock);
2002/0327		while((t = qwaitrelease.head) && t->r <= now){ /* There's something waiting to be released and its time has come */ edfdequeue(&qwaitrelease);
2002/1218/sys/src/9/port/edf.c:447,453 – 2002/1219/sys/src/9/port/edf.c:444,450
2002/0327		} static void
2002/1001		edfdeadlineintr(Ureg*, Timer *timer)
2002/1219		edfdeadlineintr(Ureg*, Timer *)
2002/0327		{
2002/0328		/* Task reached deadline */
2002/1218/sys/src/9/port/edf.c:460,478 – 2002/1219/sys/src/9/port/edf.c:457,471
2002/0315
2002/0327		DPRINT("%d edfdeadlineintr\n", m->machno);
2002/1001		if (timer) timer->when = 0;
2002/0328
2002/0927		if(panicking || active.exiting)
2002/0327		return;
2002/1219		now = fastticks(nil);
2002/0327		ilock(&edflock);
2002/0315		// If up is not set, we're running inside the scheduler
2002/0927		// for non-real-time processes. noted = 0;
2002/0315		if (up && isedf(up)) {
2002/0328		now = fastticks(nil);
2002/0315		t = up->task;
2002/1218		assert(t->state == EdfRunning);
2002/1218/sys/src/9/port/edf.c:1075,1081 – 2002/1219/sys/src/9/port/edf.c:1068,1074
2002/0927		if (t->curcsn) t->curcsn->S -= used; when = now + c->S; if (when < deadlinetimer[m->machno].when){
2002/1219		if (deadlinetimer[m->machno].when == 0 || when < deadlinetimer[m->machno].when){
2002/0927		deadlinetimer[m->machno].when = when; timeradd(&deadlinetimer[m->machno]); }
2002/1219/sys/src/9/port/edf.c:514,520 – 2003/0201/sys/src/9/port/edf.c:514,520 (short | long)
2002/0315		} iunlock(&edflock);
2002/0927		if (noted) postnote(up, 1, buf, NUser);
2003/0201		postnote(up, 0, buf, NUser);
2002/0315		sched(); splhi(); }