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