edf.c 13 KB

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