43eec415f05003a01c3f7f2e66e1068b98ba123f
[barrelfish] / kernel / schedule_rbed.c
1 /**
2  * \file
3  * \brief Kernel scheduling policy: Rate-Based Earliest Deadline (RBED)
4  *
5  * The algorithm is described in the paper "Dynamic Integrated
6  * Scheduling of Hard Real-Time, Soft Real-Time and Non-Real-Time
7  * Processes" by Scott A. Brandt of UC Santa Cruz.
8  *
9  * Note that while in the paper real number arithmetic is used on some
10  * variables, we employ fixed-point integer arithmetic within #SPECTRUM
11  * in these cases.
12  */
13
14 /*
15  * Copyright (c) 2007, 2008, 2009, 2010, 2013, ETH Zurich.
16  * All rights reserved.
17  *
18  * This file is distributed under the terms in the attached LICENSE file.
19  * If you do not find this file, copies can be found by writing to:
20  * ETH Zurich D-INFK, Universitaetstr. 6, CH-8092 Zurich. Attn: Systems Group.
21  */
22
23 /**
24  * Implementation Notes
25  *
26  * real-time tasks:
27  *  the behaviour of real-time tasks is characterized by four parameters: wcet
28  *  (worst case execution time), period, (relative) deadline, and
29  *  release_time.  Besides release_time, the values of these parameters are
30  *  not changed by the scheduler. RT tasks are considered to be periodic. Note
31  *  that the interpretation of the parameters is a little different than the
32  *  original RBED paper.
33  *
34  *  ->release_time is the time that the task is ready to be scheduled. RT tasks
35  *  with ->release_time in the future are not effectively considered to be on
36  *  the runqueue and are ignored by the scheduler.  In order to meet its
37  *  deadline the task needs to be scheduled no later than ->release_time +
38  *  deadline - wcet. EDF guarantees this property, as long as the utilization
39  *  rate is <= 1.
40  *
41  *  The execution of an rt task for a particular period ends either when: (a)
42  *  the task runs outs of budget (->etime >= ->wcet), or (b) the task yields
43  *  using scheduler_yield(). When this happens the task's ->etime is reset to
44  *  0, while ->release_time is increased by ->period. Note that
45  *  scheduler_remove() does not finalize the current period of the task. Also,
46  *  note that depending on ->period, there might be a case that an rt task is
47  *  not executed, even if the CPU is idle.
48  *
49  * best-effort tasks:
50  *  for best-effort tasks the scheduler is responsible to assigns proper values
51  *  the RT parameters. Also, To prioritize between BE tasks, the scheduler uses
52  *  ->weight.
53  */
54
55 #include <limits.h>
56 #ifndef SCHEDULER_SIMULATOR
57 #       include <kernel.h>
58 #       include <dispatch.h>
59 #       include <trace/trace.h>
60 #       include <trace_definitions/trace_defs.h>
61 #       include <timer.h> // update_sched_timer
62 #       include <kcb.h>
63 #include <systime.h>
64 #endif
65
66 #define SPECTRUM        1000000
67
68 /**
69  * Minimum resource rate reserved for best-effort processes, in #SPECTRUM.
70  * We set this to 10%.
71  */
72 #define BETA            (SPECTRUM / 10)
73
74 #define MAX(a, b)       ((a) > (b) ? (a) : (b))
75 #define MIN(a, b)       ((a) < (b) ? (a) : (b))
76
77
78 // queue_tail has to be global, as its used from assembly
79 // this is always kept in sync with kcb_current->queue_tail
80 struct dcb *queue_tail = NULL;
81
82 /// Last (currently) scheduled task, for accounting purposes
83 static struct dcb *lastdisp = NULL;
84
85 /**
86  * \brief Returns whether dcb is in scheduling queue.
87  * \param dcb   Pointer to DCB to check.
88  * \return True if in queue, false otherwise.
89  */
90 static inline bool in_queue(struct dcb *dcb)
91 {
92     return dcb->next != NULL || kcb_current->queue_tail == dcb;
93 }
94
95 static inline unsigned int u_target(struct dcb *dcb)
96 {
97     return (dcb->wcet * SPECTRUM) / dcb->period;
98 }
99
100 static inline unsigned int u_actual_srt(struct dcb *dcb)
101 {
102     if(u_target(dcb) != 0) {
103         return MIN(u_target(dcb), (1 - BETA - kcb_current->u_hrt) / (kcb_current->u_srt / u_target(dcb)));
104     } else {
105         return 0;
106     }
107 }
108
109 static inline systime_t deadline(struct dcb *dcb)
110 {
111     return dcb->release_time + dcb->deadline;
112 }
113
114 static void queue_insert(struct dcb *dcb)
115 {
116     // Empty queue case
117     if(kcb_current->queue_head == NULL) {
118         assert(kcb_current->queue_tail == NULL);
119         kcb_current->queue_head = kcb_current->queue_tail = queue_tail = dcb;
120         return;
121     }
122
123     /* Insert into priority queue (this is doing EDF). We insert at
124      * the tail of a train of tasks with equal deadlines, as well as
125      * equal release times for best-effort tasks, so that trains of
126      * best-effort tasks with equal deadlines (and those released at
127      * the same time) get scheduled in a round-robin fashion. The
128      * release time equality check is important, as best-effort tasks
129      * have lazily allocated deadlines. In some circumstances (like
130      * when another task blocks), this might otherwise cause a wrong
131      * yielding behavior when old deadlines are encountered.
132      */
133     struct dcb *prev = NULL;
134     for(struct dcb *i = kcb_current->queue_head; i != NULL; prev = i, i = i->next) {
135         // Skip over equal, smaller release times if best-effort
136         if(dcb->type == TASK_TYPE_BEST_EFFORT &&
137            dcb->release_time >= i->release_time) {
138             continue;
139         }
140
141         // Skip over equal deadlines
142         if(deadline(dcb) >= deadline(i)) {
143             continue;
144         }
145
146         dcb->next = i;
147         if(prev == NULL) {      // Insert before head
148             kcb_current->queue_head = dcb;
149         } else {                // Insert inside queue
150             prev->next = dcb;
151         }
152
153         return;
154     }
155
156     // Insert after queue tail
157     kcb_current->queue_tail->next = dcb;
158     kcb_current->queue_tail = queue_tail = dcb;
159 }
160
161 /**
162  * \brief Remove 'dcb' from scheduler ring.
163  *
164  * Removes dispatcher 'dcb' from the scheduler ring. If it was not in
165  * the ring, this function is a no-op. The postcondition for this
166  * function is that dcb is not in the ring.
167  *
168  * \param dcb   Pointer to DCB to remove.
169  */
170 static void queue_remove(struct dcb *dcb)
171 {
172     // No-op if not in scheduler ring
173     if(!in_queue(dcb)) {
174         return;
175     }
176
177     if(dcb == kcb_current->queue_head) {
178         kcb_current->queue_head = dcb->next;
179         if(kcb_current->queue_head == NULL) {
180             kcb_current->queue_tail = queue_tail =  NULL;
181         }
182
183         goto out;
184     }
185
186     for(struct dcb *i = kcb_current->queue_head; i != NULL; i = i->next) {
187         if(i->next == dcb) {
188             i->next = i->next->next;
189             if(kcb_current->queue_tail == dcb) {
190                 kcb_current->queue_tail = queue_tail = i;
191             }
192             break;
193         }
194     }
195
196  out:
197     dcb->next = NULL;
198 }
199
200 #if 0
201 /**
202  * \brief (Re-)Sort the scheduler priority queue.
203  */
204 static void queue_sort(void)
205 {
206  start_over:
207     for(struct dcb *i = queue_head; i != NULL && i->next != NULL; i = i->next) {
208         if(deadline(i) > deadline(i->next)) {
209             // Gotta re-sort
210             queue_remove(i);
211             queue_insert(i);
212             goto start_over;
213         }
214     }
215 }
216
217 static void queue_reset(void)
218 {
219     for(struct dcb *i = queue_head; i != NULL; i = i->next) {
220         if(i->type == TASK_TYPE_BEST_EFFORT) {
221             i->release_time = kernel_now;
222         }
223     }
224 }
225 #endif
226
227 /**
228  * \brief Allocates resources for tasks.
229  *
230  * \param dcb   Pointer to dcb to allocate resources for.
231  *
232  * \return u_actual for 'dcb' in percent.
233  */
234 static unsigned int do_resource_allocation(struct dcb *dcb)
235 {
236     unsigned int u_actual;
237
238     switch(dcb->type) {
239     case TASK_TYPE_HARD_REALTIME:
240         u_actual = u_target(dcb);
241         break;
242
243     case TASK_TYPE_SOFT_REALTIME:
244         u_actual = u_actual_srt(dcb);
245         break;
246
247     case TASK_TYPE_BEST_EFFORT:
248         assert(kcb_current->w_be > 0 && kcb_current->n_be > 0);
249         assert(dcb->weight < UINT_MAX / SPECTRUM);
250         u_actual = (MAX(BETA, SPECTRUM - kcb_current->u_hrt - kcb_current->u_srt) * dcb->weight) / kcb_current->w_be;
251         dcb->deadline = dcb->period = kcb_current->n_be * kernel_timeslice;
252         break;
253
254     default:
255         panic("Unknown task type %d!", dcb->type);
256         break;
257     }
258
259     return u_actual;
260 }
261
262 #if 0
263 // XXX: Don't understand this yet
264 static void adjust_weights(void)
265 {
266     // No runnable best-effort tasks have a positive weight
267     if(w_be == 0) {
268         // Re-assign weights
269         for(struct dcb *i = queue_head; i != NULL; i = i->next) {
270             if(i->type != TASK_TYPE_BEST_EFFORT) {
271                 continue;
272             }
273
274             i->weight = 1;
275             w_be++;
276         }
277     }
278 }
279 #endif
280
281 static void set_best_effort_wcet(struct dcb *dcb)
282 {
283     unsigned int u_actual = do_resource_allocation(dcb);
284     systime_t wcet_undiv = (kcb_current->n_be * kernel_timeslice * u_actual);
285
286     // Assert we are never overloaded
287     assert(kcb_current->u_hrt + kcb_current->u_srt + u_actual <= SPECTRUM);
288
289     // Divide with proper rounding
290     dcb->wcet = (wcet_undiv + SPECTRUM / 2) / SPECTRUM;
291 }
292
293 /**
294  * \brief Scheduler policy.
295  *
296  * \return Next DCB to schedule or NULL if wait for interrupts.
297  */
298 struct dcb *schedule(void)
299 {
300     struct dcb *todisp;
301     systime_t now = systime_now();
302
303     // Assert we are never overloaded
304     assert(kcb_current->u_hrt + kcb_current->u_srt + BETA <= SPECTRUM);
305
306     // Update executed time of last dispatched task
307     if(lastdisp != NULL) {
308         assert(lastdisp->last_dispatch <= now);
309         if(lastdisp->release_time <= now) {
310             lastdisp->etime += now -
311                 MAX(lastdisp->last_dispatch, lastdisp->release_time);
312         }
313     }
314
315  start_over:
316     todisp = kcb_current->queue_head;
317
318 #ifndef SCHEDULER_SIMULATOR
319 #define PRINT_NAME(d) \
320     do { \
321         if (!(d) || !(d)->disp) { \
322             debug(SUBSYS_DISPATCH, "todisp == NULL\n"); \
323             break; \
324         } \
325         struct dispatcher_shared_generic *dst = \
326             get_dispatcher_shared_generic(d->disp); \
327         debug(SUBSYS_DISPATCH, "looking at '%s', release_time=%lu, kernel_now=%zu\n", \
328                 dst->name, d->release_time, now); \
329     }while(0)
330 #else
331 #define PRINT_NAME(d) do{}while(0)
332 #endif
333
334     // Skip over all tasks released in the future, they're technically not
335     // in the schedule yet. We just have them to reduce book-keeping.
336     while(todisp != NULL && todisp->release_time > now) {
337         PRINT_NAME(todisp);
338         todisp = todisp->next;
339     }
340 #undef PRINT_NAME
341
342     // nothing to dispatch
343     if(todisp == NULL) {
344 #ifndef SCHEDULER_SIMULATOR
345         debug(SUBSYS_DISPATCH, "schedule: no dcb runnable\n");
346 #endif
347         lastdisp = NULL;
348         return NULL;
349     }
350
351     // Lazy resource allocation for best-effort processes
352     if(todisp->type == TASK_TYPE_BEST_EFFORT) {
353         set_best_effort_wcet(todisp);
354
355         /* We might've shortened the deadline into the past (eg. when
356          * another BE task was removed while we already ran well into
357          * our timeslice). In that case we need to re-release.
358          */
359         if(deadline(todisp) < now) {
360             todisp->release_time = now;
361         }
362     }
363
364     // Assert we never miss a hard deadline
365     if(todisp->type == TASK_TYPE_HARD_REALTIME && now > deadline(todisp)) {
366         panic("Missed hard deadline: now = %zu, deadline = %lu", now,
367               deadline(todisp));
368         assert(false && "HRT task missed a dead line!");
369     }
370
371     // Deadline's can't be in the past (or EDF wouldn't work properly)
372     assert(deadline(todisp) >= now);
373
374     // Dispatch first guy in schedule if not over budget
375     if(todisp->etime < todisp->wcet) {
376         todisp->last_dispatch = now;
377
378         // If nothing changed, run whatever ran last (task might have
379         // yielded to another), unless it is blocked
380         if(lastdisp == todisp && dcb_current != NULL && in_queue(dcb_current)) {
381             /* trace_event(TRACE_SUBSYS_KERNEL, TRACE_EVENT_KERNEL_SCHED_CURRENT, */
382             /*             (uint32_t)(lvaddr_t)dcb_current & 0xFFFFFFFF); */
383             return dcb_current;
384         }
385
386         /* trace_event(TRACE_SUBSYS_KERNEL, TRACE_EVENT_KERNEL_SCHED_SCHEDULE, */
387         /*             (uint32_t)(lvaddr_t)todisp & 0xFFFFFFFF); */
388
389         // Remember who we run next
390         lastdisp = todisp;
391         #ifdef CONFIG_ONESHOT_TIMER
392         // we might be able to do better than that...
393         // (e.g., check if there is only one task in the queue)
394         update_sched_timer(now + (todisp->wcet - todisp->etime));
395         #endif
396         return todisp;
397     }
398
399     /* we selected a task that is over budget. do the necessary bookkeeping, put
400      * it back on the queue and re-select a task */
401
402     // Best-effort task consumed WCET
403     // XXX: Don't understand this yet
404 #if 0
405     if(todisp->type == TASK_TYPE_BEST_EFFORT) {
406         w_be -= todisp->weight;
407         todisp->weight = 0;
408         adjust_weights();
409     }
410 #endif
411
412     // Update periodic task and re-sort into run-queue
413     struct dcb *dcb = todisp;
414     queue_remove(todisp);
415     if(dcb->type != TASK_TYPE_BEST_EFFORT) {
416         if(now > dcb->release_time) {
417             dcb->release_time += dcb->period;
418         }
419     } else {
420         dcb->release_time = now;
421     }
422     dcb->etime = 0;
423     queue_insert(dcb);
424     lastdisp = NULL;
425
426     goto start_over;
427 }
428
429 void schedule_now(struct dcb *dcb)
430 {
431     systime_t now = systime_now();
432     if (dcb->release_time >= now) {
433         dcb->release_time = now;
434     }
435     dcb->deadline = 1;
436 }
437
438 void make_runnable(struct dcb *dcb)
439 {
440     systime_t now = systime_now();
441
442     // No-Op if already in schedule
443     if(in_queue(dcb)) {
444         return;
445     }
446
447     trace_event(TRACE_SUBSYS_KERNEL, TRACE_EVENT_KERNEL_SCHED_MAKE_RUNNABLE,
448                 (uint32_t)(lvaddr_t)dcb & 0xFFFFFFFF);
449
450     // Keep counters up to date
451     switch(dcb->type) {
452     case TASK_TYPE_BEST_EFFORT:
453         if(dcb->weight == 0) {
454             dcb->weight = 1;
455         } else {
456             // XXX: Don't understand this yet
457 #if 0
458             // Give blocked processes a boost
459             dcb->weight = dcb->weight / 2 + 6;
460 #endif
461         }
462         kcb_current->w_be += dcb->weight;
463         kcb_current->n_be++;
464         dcb->deadline = dcb->period = kcb_current->n_be * kernel_timeslice;
465         dcb->release_time = now;
466         /* queue_sort(); */
467         break;
468
469     case TASK_TYPE_SOFT_REALTIME:
470         panic("Unimplemented!");
471         break;
472
473     case TASK_TYPE_HARD_REALTIME:
474         kcb_current->u_hrt += u_target(dcb);
475         break;
476
477     default:
478         panic("Unknown task type %d", dcb->type);
479         break;
480     }
481
482     // Never overload the scheduler
483     if(kcb_current->u_hrt + kcb_current->u_srt + BETA > SPECTRUM) {
484         panic("RBED scheduler overload (loaded %d%%)!",
485               (kcb_current->u_hrt + kcb_current->u_srt + BETA) / (SPECTRUM / 100));
486     }
487
488     if(dcb->release_time < now) {
489         panic("Released in the past! now = %zu, release_time = %lu\n",
490               now, dcb->release_time);
491     }
492     /* assert(dcb->release_time >= kernel_now); */
493     dcb->etime = 0;
494     queue_insert(dcb);
495 }
496
497 /**
498  * \brief Remove 'dcb' from scheduler ring.
499  *
500  * Removes dispatcher 'dcb' from the scheduler ring. If it was not in
501  * the ring, this function is a no-op. The postcondition for this
502  * function is that dcb is not in the ring.
503  *
504  * \param dcb   Pointer to DCB to remove.
505  */
506 void scheduler_remove(struct dcb *dcb)
507 {
508     // No-Op if not in schedule
509     if(!in_queue(dcb)) {
510         return;
511     }
512
513     queue_remove(dcb);
514
515     trace_event(TRACE_SUBSYS_KERNEL, TRACE_EVENT_KERNEL_SCHED_REMOVE,
516                 (uint32_t)(lvaddr_t)dcb & 0xFFFFFFFF);
517
518     // Update counters
519     switch(dcb->type) {
520     case TASK_TYPE_BEST_EFFORT:
521         kcb_current->w_be -= dcb->weight;
522         kcb_current->n_be--;
523         /* queue_sort(); */
524         /* adjust_weights(); */
525         break;
526
527     case TASK_TYPE_SOFT_REALTIME:
528         panic("Unimplemented!");
529         break;
530
531     case TASK_TYPE_HARD_REALTIME:
532         kcb_current->u_hrt -= u_target(dcb);
533         break;
534     }
535 }
536
537 /**
538  * \brief Yield 'dcb' for the rest of the current timeslice.
539  *
540  * Re-sorts 'dcb' into the scheduler queue with its release time increased by
541  * the timeslice period. It is an error to yield a dispatcher not in the
542  * scheduler queue.
543  *
544  * \param dcb   Pointer to DCB to remove.
545  */
546 void scheduler_yield(struct dcb *dcb)
547 {
548     systime_t now = systime_now();
549     // For tasks not running yet, yield is a no-op
550     if(!in_queue(dcb) || dcb->release_time > now) {
551         return;
552     }
553
554     /* trace_event(TRACE_SUBSYS_KERNEL, TRACE_EVENT_KERNEL_SCHED_YIELD, */
555     /*             (uint32_t)(lvaddr_t)dcb & 0xFFFFFFFF); */
556
557     queue_remove(dcb);
558     switch(dcb->type) {
559     case TASK_TYPE_HARD_REALTIME:
560     case TASK_TYPE_SOFT_REALTIME:
561         dcb->release_time += dcb->period;
562         break;
563
564     case TASK_TYPE_BEST_EFFORT:
565         // Shuffle us around one time
566         dcb->release_time = now;
567         break;
568     }
569     dcb->etime = 0;
570     lastdisp = NULL;    // Don't account for us anymore
571     queue_insert(dcb);
572 }
573
574 #ifndef SCHEDULER_SIMULATOR
575 void scheduler_reset_time(void)
576 {
577     trace_event(TRACE_SUBSYS_KERNEL, TRACE_EVENT_KERNEL_TIMER_SYNC, 0);
578
579     // XXX: Currently, we just re-release everything now
580     struct kcb *k = kcb_current;
581     do {
582         printk(LOG_NOTE, "clearing kcb %p\n", k);
583         for(struct dcb *i = k->queue_head; i != NULL; i = i->next) {
584             i->release_time = 0;
585             i->etime = 0;
586             i->last_dispatch = 0;
587         }
588         k = k->next;
589     }while(k && k!=kcb_current);
590
591     // Forget all accounting information
592     lastdisp = NULL;
593 }
594
595 void scheduler_convert(void)
596 {
597     enum sched_state from = kcb_current->sched;
598     switch (from) {
599         case SCHED_RBED:
600             // do nothing
601             break;
602         case SCHED_RR:
603         {
604             // initialize RBED fields
605             // make all tasks best effort
606             struct dcb *tmp = NULL;
607             printf("kcb_current: %p\n", kcb_current);
608             printf("kcb_current->ring_current: %p\n", kcb_current->ring_current);
609             printf("kcb_current->ring_current->prev: %p\n", kcb_current->ring_current->prev);
610             struct dcb *i = kcb_current->ring_current;
611             do {
612                 printf("converting %p\n", i);
613                 i->type = TASK_TYPE_BEST_EFFORT;
614                 tmp = i->next;
615                 i->next = i->prev = NULL;
616                 make_runnable(i);
617                 i = tmp;
618             } while (i != kcb_current->ring_current);
619             for (i = kcb_current->queue_head; i; i=i->next) {
620                 printf("%p (-> %p)\n", i, i->next);
621             }
622             break;
623         }
624         default:
625             printf("don't know how to convert %d to RBED state\n", from);
626             break;
627     }
628 }
629
630 void scheduler_restore_state(void)
631 {
632     // clear time slices
633     scheduler_reset_time();
634 }
635 #endif