xref: /plan9/sys/src/9/port/edf.c (revision e06f534bbaa4097bc6f4764ef1dd2dc3338fbd40) 
1 /* EDF scheduling */
2 #include	<u.h>
3 #include	"../port/lib.h"
4 #include	"mem.h"
5 #include	"dat.h"
6 #include	"fns.h"
7 #include	"../port/error.h"
8 #include	"../port/edf.h"
9 #include	<trace.h>
10 
11 /* debugging */
12 int	edfprint = 0;
13 #define DPRINT	if(edfprint)print
14 
15 static long	now;	/* Low order 32 bits of time in µs */
16 extern ulong	delayedscheds;
17 extern Schedq	runq[Nrq];
18 extern int	nrdy;
19 extern ulong	runvec;
20 
21 /* Statistics stuff */
22 ulong		nilcount;
23 ulong		scheds;
24 long		edfruntime;
25 ulong		edfnrun;
26 int		misseddeadlines;
27 
28 /* Edfschedlock protects modification of admission params */
29 int		edfinited;
30 QLock		edfschedlock;
31 static Lock	thelock;
32 
33 enum{
34 	Dl,	/* Invariant for schedulability test: Dl < Rl */
35 	Rl,
36 };
37 
38 static char *testschedulability(Proc*);
39 static Proc *qschedulability;
40 
41 enum {
42 	Onemicrosecond =	1,
43 	Onemillisecond =	1000,
44 	Onesecond =		1000000,
45 	OneRound = 		Onemillisecond/2,
46 };
47 
48 static int
49 timeconv(Fmt *f)
50 {
51 	char buf[128], *sign;
52 	vlong t;
53 
54 	buf[0] = 0;
55 	switch(f->r) {
56 	case 'U':
57 		t = va_arg(f->args, uvlong);
58 		break;
59 	case 't':	// vlong in nanoseconds
60 		t = va_arg(f->args, long);
61 		break;
62 	default:
63 		return fmtstrcpy(f, "(timeconv)");
64 	}
65 	if (t < 0) {
66 		sign = "-";
67 		t = -t;
68 	}
69 	else
70 		sign = "";
71 	if (t > Onesecond){
72 		t += OneRound;
73 		sprint(buf, "%s%d.%.3ds", sign, (int)(t / Onesecond), (int)(t % Onesecond)/Onemillisecond);
74 	}else if (t > Onemillisecond)
75 		sprint(buf, "%s%d.%.3dms", sign, (int)(t / Onemillisecond), (int)(t % Onemillisecond));
76 	else
77 		sprint(buf, "%s%dµs", sign, (int)t);
78 	return fmtstrcpy(f, buf);
79 }
80 
81 /*
82 uvlong x;
83 ulong xpc;
84 */
85 
86 Edf*
87 edflock(Proc *p)
88 {
89 	Edf *e;
90 
91 	if (p->edf == nil)
92 		return nil;
93 	ilock(&thelock);
94 	if ((e = p->edf) && (e->flags & Admitted)){
95 /*
96 		cycles(&x);
97 		xpc = getcallerpc(&p);
98 */
99 		now = fastticks2us(fastticks(nil));
100 		return e;
101 	}
102 	iunlock(&thelock);
103 	return nil;
104 }
105 
106 void
107 edfunlock(void)
108 {
109 /*
110 	uvlong y;
111 	ulong n, upc;
112 	cycles(&y);
113 	upc = 0;
114 	if((n = y - x) > 500000) upc = xpc;
115 */
116 
117 	edfruntime += todget(nil) - now;
118 	edfnrun++;
119 	iunlock(&thelock);
120 /*
121 	if(upc)
122 		print("edfunlock %ld 0x%lux\n", n, upc);
123 */
124 }
125 
126 void
127 edfinit(Proc*p)
128 {
129 	if(!edfinited){
130 		fmtinstall('t', timeconv);
131 		edfinited++;
132 	}
133 	now = fastticks2us(fastticks(nil));
134 	DPRINT("%t edfinit %lud[%s]\n", now, p->pid, statename[p->state]);
135 	p->edf = malloc(sizeof(Edf));
136 	if(p->edf == nil)
137 		error(Enomem);
138 	return;
139 }
140 
141 static void
142 deadlineintr(Ureg*, Timer *t)
143 {
144 	/* Proc reached deadline */
145 	extern int panicking;
146 	Proc *p;
147 	void (*pt)(Proc*, int, vlong);
148 
149 	if(panicking || active.exiting)
150 		return;
151 
152 	p = t->ta;
153 	now = fastticks2us(fastticks(nil));
154 	DPRINT("%t deadlineintr %lud[%s]\n", now, p->pid, statename[p->state]);
155 	/* If we're interrupting something other than the proc pointed to by t->a,
156 	 * we've already achieved recheduling, so we need not do anything
157 	 * Otherwise, we must cause a reschedule, but if we call sched()
158 	 * here directly, the timer interrupt routine will not finish its business
159 	 * Instead, we cause the resched to happen when the interrupted proc
160 	 * returns to user space
161 	 */
162 	if (p == up){
163 		pt = proctrace;
164 		if(up->trace && pt)
165 			pt(up, SInts, 0);
166 		up->delaysched++;
167  		delayedscheds++;
168 	}
169 }
170 
171 static void
172 release(Proc *p)
173 {
174 	/* Called with edflock held */
175 	Edf *e;
176 	void (*pt)(Proc*, int, vlong);
177 	long n;
178 	vlong nowns;
179 
180 	e = p->edf;
181 	e->flags &= ~Yield;
182 	if (e->d - now < 0){
183 		e->periods++;
184 		e->r = now;
185 		if ((e->flags & Sporadic) == 0){
186 			/*
187 			 * Non sporadic processes stay true to their period;
188 			 * calculate next release time.
189 			 * Second test limits duration of while loop.
190 			 */
191 			if((n = now - e->t) > 0){
192 				if(n < e->T)
193 					e->t += e->T;
194 				else
195 					e->t = now + e->T - (n % e->T);
196 			}
197 		}else{
198 			/* Sporadic processes may not be released earlier than
199 			 * one period after this release
200 			 */
201 			e->t = e->r + e->T;
202 		}
203 		e->d = e->r + e->D;
204 		e->S = e->C;
205 		DPRINT("%t release %lud[%s], r=%t, d=%t, t=%t, S=%t\n",
206 			now, p->pid, statename[p->state], e->r, e->d, e->t, e->S);
207 		if (pt = proctrace){
208 			nowns = todget(nil);
209 			pt(p, SRelease, nowns);
210 			pt(p, SDeadline, nowns + 1000LL*e->D);
211 		}
212 	}else{
213 		DPRINT("%t release %lud[%s], too late t=%t, called from 0x%lux\n",
214 			now, p->pid, statename[p->state], e->t, getcallerpc(&p));
215 	}
216 }
217 
218 static void
219 releaseintr(Ureg*, Timer *t)
220 {
221 	Proc *p;
222 	extern int panicking;
223 	Schedq *rq;
224 
225 	if(panicking || active.exiting)
226 		return;
227 
228 	p = t->ta;
229 	if((edflock(p)) == nil)
230 		return;
231 	DPRINT("%t releaseintr %lud[%s]\n", now, p->pid, statename[p->state]);
232 	switch(p->state){
233 	default:
234 		edfunlock();
235 		return;
236 	case Ready:
237 		/* remove proc from current runq */
238 		rq = &runq[p->priority];
239 		if (dequeueproc(rq, p) != p){
240 			DPRINT("releaseintr: can't find proc or lock race\n");
241 			release(p);	/* It'll start best effort */
242 			edfunlock();
243 			return;
244 		}
245 		p->state = Waitrelease;
246 		/* fall through */
247 	case Waitrelease:
248 		release(p);
249 		edfunlock();
250 		ready(p);
251 		if (up){
252 			up->delaysched++;
253 			delayedscheds++;
254 		}
255 		return;
256 	case Running:
257 		release(p);
258 		edfrun(p, 1);
259 		break;
260 	case Wakeme:
261 		release(p);
262 		edfunlock();
263 		if (p->trend)
264 			wakeup(p->trend);
265 		p->trend = nil;
266 		if (up){
267 			up->delaysched++;
268 			delayedscheds++;
269 		}
270 		return;
271 	}
272 	edfunlock();
273 }
274 
275 void
276 edfrecord(Proc *p)
277 {
278 	long used;
279 	Edf *e;
280 	void (*pt)(Proc*, int, vlong);
281 
282 	if((e = edflock(p)) == nil)
283 		return;
284 	used = now - e->s;
285 	if (e->d - now <= 0)
286 		e->edfused += used;
287 	else
288 		e->extraused += used;
289 	if (e->S > 0){
290 		if(e->S <= used){
291 			if(pt = proctrace)
292 				pt(p, SSlice, 0);
293 			DPRINT("%t edfrecord slice used up\n", now);
294 			e->d = now;
295 			e->S = 0;
296 		}else
297 			e->S -= used;
298 	}
299 	e->s = now;
300 	edfunlock();
301 }
302 
303 void
304 edfrun(Proc *p, int edfpri)
305 {
306 	Edf *e;
307 	void (*pt)(Proc*, int, vlong);
308 	long tns;
309 
310 	e = p->edf;
311 	/* Called with edflock held */
312 	if(edfpri){
313 		tns = e->d - now;
314 		if (tns <= 0 || e->S == 0){
315 			/* Deadline reached or resources exhausted,
316 			 * deschedule forthwith
317 			 */
318 			p->delaysched++;
319  			delayedscheds++;
320 			e->s = now;
321 			return;
322 		}
323 		if(e->S < tns)
324 			tns = e->S;
325 		e->tns = 1000LL * tns;
326 		if(e->tt == nil || e->tf != deadlineintr){
327 			DPRINT("%t edfrun, deadline=%t\n", now, tns);
328 		}else{
329 			DPRINT("v");
330 		}
331 		if(p->trace && (pt = proctrace))
332 			pt(p, SInte, todget(nil) + e->tns);
333 		e->tmode = Trelative;
334 		e->tf = deadlineintr;
335 		e->ta = p;
336 		timeradd(e);
337 	}else{
338 		DPRINT("<");
339 	}
340 	e->s = now;
341 }
342 
343 char *
344 edfadmit(Proc *p)
345 {
346 	char *err;
347 	Edf *e;
348 	int i;
349 	Proc *r;
350 	void (*pt)(Proc*, int, vlong);
351 	long tns;
352 
353 	e = p->edf;
354 	if (e->flags & Admitted)
355 		return "task state";	/* should never happen */
356 
357 	/* simple sanity checks */
358 	if (e->T == 0)
359 		return "T not set";
360 	if (e->C == 0)
361 		return "C not set";
362 	if (e->D > e->T)
363 		return "D > T";
364 	if (e->D == 0)	/* if D is not set, set it to T */
365 		e->D = e->T;
366 	if (e->C > e->D)
367 		return "C > D";
368 
369 	qlock(&edfschedlock);
370 	if (err = testschedulability(p)){
371 		qunlock(&edfschedlock);
372 		return err;
373 	}
374 	e->flags |= Admitted;
375 
376 	edflock(p);
377 
378 	if(pt = proctrace)
379 		pt(p, SAdmit, 0);
380 
381 	/* Look for another proc with the same period to synchronize to */
382 	SET(r);
383 	for(i=0; i<conf.nproc; i++) {
384 		r = proctab(i);
385 		if(r->state == Dead || r == p)
386 			continue;
387 		if (r->edf == nil || (r->edf->flags & Admitted) == 0)
388 			continue;
389 		if (r->edf->T == e->T)
390 				break;
391 	}
392 	if (i == conf.nproc){
393 		/* Can't synchronize to another proc, release now */
394 		e->t = now;
395 		e->d = 0;
396 		release(p);
397 		if (p == up){
398 			DPRINT("%t edfadmit self %lud[%s], release now: r=%t d=%t t=%t\n",
399 				now, p->pid, statename[p->state], e->r, e->d, e->t);
400 			/* We're already running */
401 			edfrun(p, 1);
402 		}else{
403 			/* We're releasing another proc */
404 			DPRINT("%t edfadmit other %lud[%s], release now: r=%t d=%t t=%t\n",
405 				now, p->pid, statename[p->state], e->r, e->d, e->t);
406 			p->ta = p;
407 			edfunlock();
408 			qunlock(&edfschedlock);
409 			releaseintr(nil, p);
410 			return nil;
411 		}
412 	}else{
413 		/* Release in synch to something else */
414 		e->t = r->edf->t;
415 		if (p == up){
416 			DPRINT("%t edfadmit self %lud[%s], release at %t\n",
417 				now, p->pid, statename[p->state], e->t);
418 			edfunlock();
419 			qunlock(&edfschedlock);
420 			return nil;
421 		}else{
422 			DPRINT("%t edfadmit other %lud[%s], release at %t\n",
423 				now, p->pid, statename[p->state], e->t);
424 			if(e->tt == nil){
425 				e->tf = releaseintr;
426 				e->ta = p;
427 				tns = e->t - now;
428 				if(tns < 20)
429 					tns = 20;
430 				e->tns = 1000LL * tns;
431 				e->tmode = Trelative;
432 				timeradd(e);
433 			}
434 		}
435 	}
436 	edfunlock();
437 	qunlock(&edfschedlock);
438 	return nil;
439 }
440 
441 void
442 edfstop(Proc *p)
443 {
444 	Edf *e;
445 	void (*pt)(Proc*, int, vlong);
446 
447 	if (e = edflock(p)){
448 		DPRINT("%t edfstop %lud[%s]\n", now, p->pid, statename[p->state]);
449 		if(pt = proctrace)
450 			pt(p, SExpel, 0);
451 		e->flags &= ~Admitted;
452 		if(e->tt)
453 			timerdel(e);
454 		edfunlock();
455 	}
456 }
457 
458 static int
459 yfn(void *)
460 {
461 	now = fastticks2us(fastticks(nil));
462 	return up->trend == nil || now - up->edf->r >= 0;
463 }
464 
465 void
466 edfyield(void)
467 {
468 	/* sleep until next release */
469 	Edf *e;
470 	void (*pt)(Proc*, int, vlong);
471 	long n;
472 
473 	if((e = edflock(up)) == nil)
474 		return;
475 	if(pt = proctrace)
476 		pt(up, SYield, 0);
477 	if((n = now - e->t) > 0){
478 		if(n < e->T)
479 			e->t += e->T;
480 		else
481 			e->t = now + e->T - (n % e->T);
482 	}
483 	e->r = e->t;
484 	e->flags |= Yield;
485 	e->d = now;
486 	if (up->tt == nil){
487 		n = e->t - now;
488 		if(n < 20)
489 			n = 20;
490 		up->tns = 1000LL * n;
491 		up->tf = releaseintr;
492 		up->tmode = Trelative;
493 		up->ta = up;
494 		up->trend = &up->sleep;
495 		timeradd(up);
496 	}else if(up->tf != releaseintr)
497 		print("edfyield: surprise! 0x%lux\n", up->tf);
498 	edfunlock();
499 	sleep(&up->sleep, yfn, nil);
500 }
501 
502 int
503 edfready(Proc *p)
504 {
505 	Edf *e;
506 	Schedq *rq;
507 	Proc *l, *pp;
508 	void (*pt)(Proc*, int, vlong);
509 	long n;
510 
511 	if((e = edflock(p)) == nil)
512 		return 0;
513 	if(e->d - now <= 0){
514 		/* past deadline, arrange for next release */
515 		if((e->flags & Sporadic) == 0){
516 			/*
517 			 * Non sporadic processes stay true to their period;
518 			 * calculate next release time.
519 			 */
520 			if((n = now - e->t) > 0){
521 				if(n < e->T)
522 					e->t += e->T;
523 				else
524 					e->t = now + e->T - (n % e->T);
525 			}
526 		}
527 		if(now - e->t < 0){
528 			/* Next release is in the future, schedule it */
529 			if(e->tt == nil || e->tf != releaseintr){
530 				n = e->t - now;
531 				if(n < 20)
532 					n = 20;
533 				e->tns = 1000LL * n;
534 				e->tmode = Trelative;
535 				e->tf = releaseintr;
536 				e->ta = p;
537 				timeradd(e);
538 				DPRINT("%t edfready %lud[%s], release=%t\n",
539 					now, p->pid, statename[p->state], e->t);
540 			}
541 			if(p->state == Running && (e->flags & (Yield|Yieldonblock)) == 0 && (e->flags & Extratime)){
542 				/* If we were running, we've overrun our CPU allocation
543 				 * or missed the deadline, continue running best-effort at low priority
544 				 * Otherwise we were blocked.  If we don't yield on block, we continue
545 				 * best effort
546 				 */
547 				DPRINT(">");
548 				p->basepri = PriExtra;
549 				p->fixedpri = 1;
550 				edfunlock();
551 				return 0;	/* Stick on runq[PriExtra] */
552 			}
553 			DPRINT("%t edfready %lud[%s] wait release at %t\n",
554 				now, p->pid, statename[p->state], e->t);
555 			p->state = Waitrelease;
556 			edfunlock();
557 			return 1;	/* Make runnable later */
558 		}
559 		DPRINT("%t edfready %lud %s release now\n", now, p->pid, statename[p->state]);
560 		/* release now */
561 		release(p);
562 	}
563 	edfunlock();
564 	DPRINT("^");
565 	rq = &runq[PriEdf];
566 	/* insert in queue in earliest deadline order */
567 	lock(runq);
568 	l = nil;
569 	for(pp = rq->head; pp; pp = pp->rnext){
570 		if(pp->edf->d > e->d)
571 			break;
572 		l = pp;
573 	}
574 	p->rnext = pp;
575 	if (l == nil)
576 		rq->head = p;
577 	else
578 		l->rnext = p;
579 	if(pp == nil)
580 		rq->tail = p;
581 	rq->n++;
582 	nrdy++;
583 	runvec |= 1 << PriEdf;
584 	p->priority = PriEdf;
585 	p->readytime = m->ticks;
586 	p->state = Ready;
587 	unlock(runq);
588 	if(pt = proctrace)
589 		pt(p, SReady, 0);
590 	return 1;
591 }
592 
593 
594 static void
595 testenq(Proc *p)
596 {
597 	Proc *xp, **xpp;
598 	Edf *e;
599 
600 	e = p->edf;
601 	e->testnext = nil;
602 	if (qschedulability == nil) {
603 		qschedulability = p;
604 		return;
605 	}
606 	SET(xp);
607 	for (xpp = &qschedulability; *xpp; xpp = &xp->edf->testnext) {
608 		xp = *xpp;
609 		if (e->testtime - xp->edf->testtime < 0
610 		|| (e->testtime == xp->edf->testtime && e->testtype < xp->edf->testtype)){
611 			e->testnext = xp;
612 			*xpp = p;
613 			return;
614 		}
615 	}
616 	assert(xp->edf->testnext == nil);
617 	xp->edf->testnext = p;
618 }
619 
620 static char *
621 testschedulability(Proc *theproc)
622 {
623 	Proc *p;
624 	long H, G, Cb, ticks;
625 	int steps, i;
626 
627 	/* initialize */
628 	DPRINT("schedulability test %lud\n", theproc->pid);
629 	qschedulability = nil;
630 	for(i=0; i<conf.nproc; i++) {
631 		p = proctab(i);
632 		if(p->state == Dead)
633 			continue;
634 		if ((p->edf == nil || (p->edf->flags & Admitted) == 0) && p != theproc)
635 			continue;
636 		p->edf->testtype = Rl;
637 		p->edf->testtime = 0;
638 		DPRINT("\tInit: edfenqueue %lud\n", p->pid);
639 		testenq(p);
640 	}
641 	H=0;
642 	G=0;
643 	for(steps = 0; steps < Maxsteps; steps++){
644 		p = qschedulability;
645 		qschedulability = p->edf->testnext;
646 		ticks = p->edf->testtime;
647 		switch (p->edf->testtype){
648 		case Dl:
649 			H += p->edf->C;
650 			Cb = 0;
651 			DPRINT("\tStep %3d, Ticks %t, pid %lud, deadline, H += %t → %t, Cb = %t\n",
652 				steps, ticks, p->pid, p->edf->C, H, Cb);
653 			if (H+Cb>ticks){
654 				DPRINT("not schedulable\n");
655 				return "not schedulable";
656 			}
657 			p->edf->testtime += p->edf->T - p->edf->D;
658 			p->edf->testtype = Rl;
659 			testenq(p);
660 			break;
661 		case Rl:
662 			DPRINT("\tStep %3d, Ticks %t, pid %lud, release, G  %t, C%t\n",
663 				steps, ticks, p->pid, p->edf->C, G);
664 			if(ticks && G <= ticks){
665 				DPRINT("schedulable\n");
666 				return nil;
667 			}
668 			G += p->edf->C;
669 			p->edf->testtime += p->edf->D;
670 			p->edf->testtype = Dl;
671 			testenq(p);
672 			break;
673 		default:
674 			assert(0);
675 		}
676 	}
677 	DPRINT("probably not schedulable\n");
678 	return "probably not schedulable";
679 }
680