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