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