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