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