ia64/xen-unstable

view xen/common/sched_sedf.c @ 9289:2162e1356bee

Fix 64-bit build.

Signed-off-by: Keir Fraser <keir@xensource.com>
author kaf24@firebug.cl.cam.ac.uk
date Wed Mar 15 12:40:42 2006 +0100 (2006-03-15)
parents be669c4b1e6b
children 03d7b5b2c212
line source
1 /******************************************************************************
2 * Simple EDF scheduler for xen
3 *
4 * by Stephan Diestelhorst (C) 2004 Cambridge University
5 * based on code by Mark Williamson (C) 2004 Intel Research Cambridge
6 */
8 #include <xen/lib.h>
9 #include <xen/sched.h>
10 #include <xen/sched-if.h>
11 #include <public/sched_ctl.h>
12 #include <xen/timer.h>
13 #include <xen/softirq.h>
14 #include <xen/time.h>
16 /*verbosity settings*/
17 #define SEDFLEVEL 0
18 #define PRINT(_f, _a...) \
19 if ((_f)<=SEDFLEVEL) printk(_a );
21 #ifndef NDEBUG
22 #define SEDF_STATS
23 #define CHECK(_p) if ( !(_p) ) \
24 { printk("Check '%s' failed, line %d, file %s\n", #_p , __LINE__,\
25 __FILE__);}
26 #else
27 #define CHECK(_p) ((void)0)
28 #endif
30 /*various ways of unblocking domains*/
31 #define UNBLOCK_ISOCHRONOUS_EDF 1
32 #define UNBLOCK_EDF 2
33 #define UNBLOCK_ATROPOS 3
34 #define UNBLOCK_SHORT_RESUME 4
35 #define UNBLOCK_BURST 5
36 #define UNBLOCK_EXTRA_SUPPORT 6
37 #define UNBLOCK UNBLOCK_EXTRA_SUPPORT
39 /*various ways of treating extra-time*/
40 #define EXTRA_OFF 1
41 #define EXTRA_ROUNDR 2
42 #define EXTRA_SLICE_WEIGHT 3
43 #define EXTRA_BLOCK_WEIGHT 4
45 #define EXTRA EXTRA_BLOCK_WEIGHT
47 #define EXTRA_NONE (0)
48 #define EXTRA_AWARE (1)
49 #define EXTRA_RUN_PEN (2)
50 #define EXTRA_RUN_UTIL (4)
51 #define EXTRA_WANT_PEN_Q (8)
52 #define EXTRA_PEN_Q (0)
53 #define EXTRA_UTIL_Q (1)
54 #define SEDF_ASLEEP (16)
56 #define EXTRA_QUANTUM (MICROSECS(500))
57 #define WEIGHT_PERIOD (MILLISECS(100))
58 #define WEIGHT_SAFETY (MILLISECS(5))
60 /* FIXME: need to validate that these are sane */
61 #define PERIOD_MAX ULONG_MAX
62 #define PERIOD_MIN (MICROSECS(10))
63 #define SLICE_MAX ULONG_MAX
64 #define SLICE_MIN (MICROSECS(5))
66 #define IMPLY(a, b) (!(a) || (b))
67 #define EQ(a, b) ((!!(a)) == (!!(b)))
70 struct sedf_dom_info {
71 struct domain *domain;
72 };
73 struct sedf_vcpu_info
74 {
75 struct vcpu *vcpu;
76 struct list_head list;
77 struct list_head extralist[2];
79 /*Parameters for EDF*/
80 s_time_t period; /*=(relative deadline)*/
81 s_time_t slice; /*=worst case execution time*/
83 /*Advaced Parameters*/
84 /*Latency Scaling*/
85 s_time_t period_orig;
86 s_time_t slice_orig;
87 s_time_t latency;
89 /*status of domain*/
90 int status;
91 /*weights for "Scheduling for beginners/ lazy/ etc." ;)*/
92 short weight;
93 short extraweight;
94 /*Bookkeeping*/
95 s_time_t deadl_abs;
96 s_time_t sched_start_abs;
97 s_time_t cputime;
98 /* times the domain un-/blocked */
99 s_time_t block_abs;
100 s_time_t unblock_abs;
102 /*scores for {util, block penalty}-weighted extratime distribution*/
103 int score[2];
104 s_time_t short_block_lost_tot;
106 /*Statistics*/
107 s_time_t extra_time_tot;
109 #ifdef SEDF_STATS
110 s_time_t block_time_tot;
111 s_time_t penalty_time_tot;
112 int block_tot;
113 int short_block_tot;
114 int long_block_tot;
115 int short_cont;
116 int pen_extra_blocks;
117 int pen_extra_slices;
118 #endif
119 };
121 struct sedf_cpu_info {
122 struct list_head runnableq;
123 struct list_head waitq;
124 struct list_head extraq[2];
125 s_time_t current_slice_expires;
126 };
128 #define EDOM_INFO(d) ((struct sedf_vcpu_info *)((d)->sched_priv))
129 #define CPU_INFO(cpu) ((struct sedf_cpu_info *)schedule_data[cpu].sched_priv)
130 #define LIST(d) (&EDOM_INFO(d)->list)
131 #define EXTRALIST(d,i) (&(EDOM_INFO(d)->extralist[i]))
132 #define RUNQ(cpu) (&CPU_INFO(cpu)->runnableq)
133 #define WAITQ(cpu) (&CPU_INFO(cpu)->waitq)
134 #define EXTRAQ(cpu,i) (&(CPU_INFO(cpu)->extraq[i]))
135 #define IDLETASK(cpu) ((struct vcpu *)schedule_data[cpu].idle)
137 #define PERIOD_BEGIN(inf) ((inf)->deadl_abs - (inf)->period)
139 #define MIN(x,y) (((x)<(y))?(x):(y))
140 #define DIV_UP(x,y) (((x) + (y) - 1) / y)
142 #define extra_runs(inf) ((inf->status) & 6)
143 #define extra_get_cur_q(inf) (((inf->status & 6) >> 1)-1)
144 #define sedf_runnable(edom) (!(EDOM_INFO(edom)->status & SEDF_ASLEEP))
147 static void sedf_dump_cpu_state(int i);
149 static inline int extraq_on(struct vcpu *d, int i) {
150 return ((EXTRALIST(d,i)->next != NULL) &&
151 (EXTRALIST(d,i)->next != EXTRALIST(d,i)));
152 }
154 static inline void extraq_add_head(struct vcpu *d, int i)
155 {
156 list_add(EXTRALIST(d,i), EXTRAQ(d->processor,i));
157 ASSERT(extraq_on(d, i));
158 }
160 static inline void extraq_add_tail(struct vcpu *d, int i)
161 {
162 list_add_tail(EXTRALIST(d,i), EXTRAQ(d->processor,i));
163 ASSERT(extraq_on(d, i));
164 }
166 static inline void extraq_del(struct vcpu *d, int i)
167 {
168 struct list_head *list = EXTRALIST(d,i);
169 ASSERT(extraq_on(d,i));
170 PRINT(3, "Removing domain %i.%i from L%i extraq\n", d->domain->domain_id,
171 d->vcpu_id, i);
172 list_del(list);
173 list->next = NULL;
174 ASSERT(!extraq_on(d, i));
175 }
177 /* adds a domain to the queue of processes which are aware of extra time. List
178 is sorted by score, where a lower score means higher priority for an extra
179 slice. It also updates the score, by simply subtracting a fixed value from
180 each entry, in order to avoid overflow. The algorithm works by simply
181 charging each domain that recieved extratime with an inverse of its weight.
182 */
183 static inline void extraq_add_sort_update(struct vcpu *d, int i, int sub) {
184 struct list_head *cur;
185 struct sedf_vcpu_info *curinf;
187 ASSERT(!extraq_on(d,i));
188 PRINT(3, "Adding domain %i.%i (score= %i, short_pen= %"PRIi64")"
189 " to L%i extraq\n",
190 d->domain->domain_id, d->vcpu_id, EDOM_INFO(d)->score[i],
191 EDOM_INFO(d)->short_block_lost_tot, i);
192 /*iterate through all elements to find our "hole" and on our way
193 update all the other scores*/
194 list_for_each(cur,EXTRAQ(d->processor,i)){
195 curinf = list_entry(cur,struct sedf_vcpu_info,extralist[i]);
196 curinf->score[i] -= sub;
197 if (EDOM_INFO(d)->score[i] < curinf->score[i])
198 break;
199 else
200 PRINT(4,"\tbehind domain %i.%i (score= %i)\n",
201 curinf->vcpu->domain->domain_id,
202 curinf->vcpu->vcpu_id, curinf->score[i]);
203 }
204 /*cur now contains the element, before which we'll enqueue*/
205 PRINT(3, "\tlist_add to %p\n", cur->prev);
206 list_add(EXTRALIST(d,i),cur->prev);
208 /*continue updating the extraq*/
209 if ((cur != EXTRAQ(d->processor,i)) && sub)
210 for (cur = cur->next; cur != EXTRAQ(d->processor,i);
211 cur = cur-> next) {
212 curinf = list_entry(cur,struct sedf_vcpu_info,
213 extralist[i]);
214 curinf->score[i] -= sub;
215 PRINT(4, "\tupdating domain %i.%i (score= %u)\n",
216 curinf->vcpu->domain->domain_id,
217 curinf->vcpu->vcpu_id, curinf->score[i]);
218 }
219 ASSERT(extraq_on(d,i));
220 }
221 static inline void extraq_check(struct vcpu *d) {
222 if (extraq_on(d, EXTRA_UTIL_Q)) {
223 PRINT(2,"Dom %i.%i is on L1 extraQ\n",d->domain->domain_id, d->vcpu_id);
224 if (!(EDOM_INFO(d)->status & EXTRA_AWARE) &&
225 !extra_runs(EDOM_INFO(d))) {
226 extraq_del(d, EXTRA_UTIL_Q);
227 PRINT(2,"Removed dom %i.%i from L1 extraQ\n",
228 d->domain->domain_id, d->vcpu_id);
229 }
230 } else {
231 PRINT(2,"Dom %i.%i is NOT on L1 extraQ\n",d->domain->domain_id,
232 d->vcpu_id);
233 if ((EDOM_INFO(d)->status & EXTRA_AWARE) && sedf_runnable(d))
234 {
235 #if (EXTRA == EXTRA_ROUNDR)
236 extraq_add_tail(d, EXTRA_UTIL_Q);
237 #elif (EXTRA == EXTRA_SLICE_WEIGHT || \
238 EXTRA == EXTRA_BLOCK_WEIGHT)
239 extraq_add_sort_update(d, EXTRA_UTIL_Q, 0);
240 #elif
241 ;
242 #endif
243 PRINT(2,"Added dom %i.%i to L1 extraQ\n",d->domain->domain_id,
244 d->vcpu_id);
245 }
246 }
247 }
249 static inline void extraq_check_add_unblocked(struct vcpu *d,
250 int priority) {
251 struct sedf_vcpu_info *inf = EDOM_INFO(d);
252 if (inf->status & EXTRA_AWARE)
253 #if (EXTRA == EXTRA_ROUNDR)
254 if (priority)
255 extraq_add_head(d,EXTRA_UTIL_Q);
256 else
257 extraq_add_tail(d,EXTRA_UTIL_Q);
258 #elif (EXTRA == EXTRA_SLICE_WEIGHT \
259 || EXTRA == EXTRA_BLOCK_WEIGHT)
260 /*put in on the weighted extraq,
261 without updating any scores*/
262 extraq_add_sort_update(d, EXTRA_UTIL_Q, 0);
263 #else
264 ;
265 #endif
266 }
268 static inline int __task_on_queue(struct vcpu *d) {
269 return (((LIST(d))->next != NULL) && (LIST(d)->next != LIST(d)));
270 }
271 static inline void __del_from_queue(struct vcpu *d)
272 {
273 struct list_head *list = LIST(d);
274 ASSERT(__task_on_queue(d));
275 PRINT(3,"Removing domain %i.%i (bop= %"PRIu64") from runq/waitq\n",
276 d->domain->domain_id, d->vcpu_id, PERIOD_BEGIN(EDOM_INFO(d)));
277 list_del(list);
278 list->next = NULL;
279 ASSERT(!__task_on_queue(d));
280 }
282 typedef int(*list_comparer)(struct list_head* el1, struct list_head* el2);
284 static inline void list_insert_sort(struct list_head *list,
285 struct list_head *element, list_comparer comp) {
286 struct list_head *cur;
287 /*iterate through all elements to find our "hole"*/
288 list_for_each(cur,list){
289 if (comp(element, cur) < 0)
290 break;
291 }
292 /*cur now contains the element, before which we'll enqueue*/
293 PRINT(3,"\tlist_add to %p\n",cur->prev);
294 list_add(element, cur->prev);
295 }
296 #define DOMAIN_COMPARER(name, field, comp1, comp2) \
297 int name##_comp(struct list_head* el1, struct list_head* el2) \
298 { \
299 struct sedf_vcpu_info *d1, *d2; \
300 d1 = list_entry(el1,struct sedf_vcpu_info, field); \
301 d2 = list_entry(el2,struct sedf_vcpu_info, field); \
302 if ((comp1) == (comp2)) \
303 return 0; \
304 if ((comp1) < (comp2)) \
305 return -1; \
306 else \
307 return 1; \
308 }
309 /* adds a domain to the queue of processes which wait for the beginning of the
310 next period; this list is therefore sortet by this time, which is simply
311 absol. deadline - period
312 */
313 DOMAIN_COMPARER(waitq, list, PERIOD_BEGIN(d1), PERIOD_BEGIN(d2))
314 static inline void __add_to_waitqueue_sort(struct vcpu *d) {
315 ASSERT(!__task_on_queue(d));
316 PRINT(3,"Adding domain %i.%i (bop= %"PRIu64") to waitq\n",
317 d->domain->domain_id, d->vcpu_id, PERIOD_BEGIN(EDOM_INFO(d)));
318 list_insert_sort(WAITQ(d->processor), LIST(d), waitq_comp);
319 ASSERT(__task_on_queue(d));
320 }
322 /* adds a domain to the queue of processes which have started their current
323 period and are runnable (i.e. not blocked, dieing,...). The first element
324 on this list is running on the processor, if the list is empty the idle
325 task will run. As we are implementing EDF, this list is sorted by deadlines.
326 */
327 DOMAIN_COMPARER(runq, list, d1->deadl_abs, d2->deadl_abs)
328 static inline void __add_to_runqueue_sort(struct vcpu *d) {
329 PRINT(3,"Adding domain %i.%i (deadl= %"PRIu64") to runq\n",
330 d->domain->domain_id, d->vcpu_id, EDOM_INFO(d)->deadl_abs);
331 list_insert_sort(RUNQ(d->processor), LIST(d), runq_comp);
332 }
335 /* Allocates memory for per domain private scheduling data*/
336 static int sedf_alloc_task(struct vcpu *d)
337 {
338 PRINT(2, "sedf_alloc_task was called, domain-id %i.%i\n",
339 d->domain->domain_id, d->vcpu_id);
341 if ( d->domain->sched_priv == NULL )
342 {
343 d->domain->sched_priv = xmalloc(struct sedf_dom_info);
344 if ( d->domain->sched_priv == NULL )
345 return -1;
346 memset(d->domain->sched_priv, 0, sizeof(struct sedf_dom_info));
347 }
349 if ( (d->sched_priv = xmalloc(struct sedf_vcpu_info)) == NULL )
350 return -1;
352 memset(d->sched_priv, 0, sizeof(struct sedf_vcpu_info));
354 return 0;
355 }
358 /* Setup the sedf_dom_info */
359 static void sedf_add_task(struct vcpu *d)
360 {
361 struct sedf_vcpu_info *inf = EDOM_INFO(d);
362 inf->vcpu = d;
364 PRINT(2,"sedf_add_task was called, domain-id %i.%i\n",d->domain->domain_id,
365 d->vcpu_id);
367 /* Allocate per-CPU context if this is the first domain to be added. */
368 if ( unlikely(schedule_data[d->processor].sched_priv == NULL) )
369 {
370 schedule_data[d->processor].sched_priv =
371 xmalloc(struct sedf_cpu_info);
372 BUG_ON(schedule_data[d->processor].sched_priv == NULL);
373 memset(CPU_INFO(d->processor), 0, sizeof(*CPU_INFO(d->processor)));
374 INIT_LIST_HEAD(WAITQ(d->processor));
375 INIT_LIST_HEAD(RUNQ(d->processor));
376 INIT_LIST_HEAD(EXTRAQ(d->processor,EXTRA_PEN_Q));
377 INIT_LIST_HEAD(EXTRAQ(d->processor,EXTRA_UTIL_Q));
378 }
380 if ( d->domain->domain_id == 0 )
381 {
382 /*set dom0 to something useful to boot the machine*/
383 inf->period = MILLISECS(20);
384 inf->slice = MILLISECS(15);
385 inf->latency = 0;
386 inf->deadl_abs = 0;
387 inf->status = EXTRA_AWARE | SEDF_ASLEEP;
388 }
389 else
390 {
391 /*other domains run in best effort mode*/
392 inf->period = WEIGHT_PERIOD;
393 inf->slice = 0;
394 inf->deadl_abs = 0;
395 inf->latency = 0;
396 inf->status = EXTRA_AWARE | SEDF_ASLEEP;
397 inf->extraweight = 1;
398 }
400 inf->period_orig = inf->period; inf->slice_orig = inf->slice;
401 INIT_LIST_HEAD(&(inf->list));
402 INIT_LIST_HEAD(&(inf->extralist[EXTRA_PEN_Q]));
403 INIT_LIST_HEAD(&(inf->extralist[EXTRA_UTIL_Q]));
405 if ( !is_idle_vcpu(d) )
406 {
407 extraq_check(d);
408 }
409 else
410 {
411 EDOM_INFO(d)->deadl_abs = 0;
412 EDOM_INFO(d)->status &= ~SEDF_ASLEEP;
413 }
414 }
416 /* Frees memory used by domain info */
417 static void sedf_free_task(struct domain *d)
418 {
419 int i;
421 PRINT(2,"sedf_free_task was called, domain-id %i\n",d->domain_id);
423 ASSERT(d->sched_priv != NULL);
424 xfree(d->sched_priv);
426 for ( i = 0; i < MAX_VIRT_CPUS; i++ )
427 {
428 if ( d->vcpu[i] )
429 {
430 ASSERT(d->vcpu[i]->sched_priv != NULL);
431 xfree(d->vcpu[i]->sched_priv);
432 }
433 }
434 }
436 /*
437 * Handles the rescheduling & bookkeeping of domains running in their
438 * guaranteed timeslice.
439 */
440 static void desched_edf_dom(s_time_t now, struct vcpu* d)
441 {
442 struct sedf_vcpu_info* inf = EDOM_INFO(d);
443 /*current domain is running in real time mode*/
445 ASSERT(__task_on_queue(d));
446 /*update the domains cputime*/
447 inf->cputime += now - inf->sched_start_abs;
449 /*scheduling decisions, which don't remove the running domain
450 from the runq*/
451 if ( (inf->cputime < inf->slice) && sedf_runnable(d) )
452 return;
454 __del_from_queue(d);
456 /*manage bookkeeping (i.e. calculate next deadline,
457 memorize overun-time of slice) of finished domains*/
458 if ( inf->cputime >= inf->slice )
459 {
460 inf->cputime -= inf->slice;
462 if ( inf->period < inf->period_orig )
463 {
464 /*this domain runs in latency scaling or burst mode*/
465 #if (UNBLOCK == UNBLOCK_BURST)
466 /*if we are runnig in burst scaling wait for two periods
467 before scaling periods up again*/
468 if ( (now - inf->unblock_abs) >= (2 * inf->period) )
469 #endif
470 {
471 inf->period *= 2; inf->slice *= 2;
472 if ( (inf->period > inf->period_orig) ||
473 (inf->slice > inf->slice_orig) )
474 {
475 /*reset slice & period*/
476 inf->period = inf->period_orig;
477 inf->slice = inf->slice_orig;
478 }
479 }
480 }
481 /*set next deadline*/
482 inf->deadl_abs += inf->period;
483 }
485 /*add a runnable domain to the waitqueue*/
486 if ( sedf_runnable(d) )
487 {
488 __add_to_waitqueue_sort(d);
489 }
490 else
491 {
492 /*we have a blocked realtime task -> remove it from exqs too*/
493 #if (EXTRA > EXTRA_OFF)
494 #if (EXTRA == EXTRA_BLOCK_WEIGHT)
495 if ( extraq_on(d, EXTRA_PEN_Q) )
496 extraq_del(d, EXTRA_PEN_Q);
497 #endif
498 if ( extraq_on(d, EXTRA_UTIL_Q) )
499 extraq_del(d, EXTRA_UTIL_Q);
500 #endif
501 }
503 ASSERT(EQ(sedf_runnable(d), __task_on_queue(d)));
504 ASSERT(IMPLY(extraq_on(d, EXTRA_UTIL_Q) || extraq_on(d, EXTRA_PEN_Q),
505 sedf_runnable(d)));
506 }
509 /* Update all elements on the queues */
510 static void update_queues(
511 s_time_t now, struct list_head *runq, struct list_head *waitq)
512 {
513 struct list_head *cur, *tmp;
514 struct sedf_vcpu_info *curinf;
516 PRINT(3,"Updating waitq..\n");
518 /*check for the first elements of the waitqueue, whether their
519 next period has already started*/
520 list_for_each_safe(cur, tmp, waitq) {
521 curinf = list_entry(cur, struct sedf_vcpu_info, list);
522 PRINT(4,"\tLooking @ dom %i.%i\n",
523 curinf->vcpu->domain->domain_id, curinf->vcpu->vcpu_id);
524 if ( PERIOD_BEGIN(curinf) <= now )
525 {
526 __del_from_queue(curinf->vcpu);
527 __add_to_runqueue_sort(curinf->vcpu);
528 }
529 else
530 break;
531 }
533 PRINT(3,"Updating runq..\n");
535 /*process the runq, find domains that are on
536 the runqueue which shouldn't be there*/
537 list_for_each_safe(cur, tmp, runq) {
538 curinf = list_entry(cur,struct sedf_vcpu_info,list);
539 PRINT(4,"\tLooking @ dom %i.%i\n",
540 curinf->vcpu->domain->domain_id, curinf->vcpu->vcpu_id);
542 if ( unlikely(curinf->slice == 0) )
543 {
544 /*ignore domains with empty slice*/
545 PRINT(4,"\tUpdating zero-slice domain %i.%i\n",
546 curinf->vcpu->domain->domain_id,
547 curinf->vcpu->vcpu_id);
548 __del_from_queue(curinf->vcpu);
550 /*move them to their next period*/
551 curinf->deadl_abs += curinf->period;
552 /*ensure that the start of the next period is in the future*/
553 if ( unlikely(PERIOD_BEGIN(curinf) < now) )
554 {
555 curinf->deadl_abs +=
556 (DIV_UP(now - PERIOD_BEGIN(curinf),
557 curinf->period)) * curinf->period;
558 }
559 /*and put them back into the queue*/
560 __add_to_waitqueue_sort(curinf->vcpu);
561 continue;
562 }
564 if ( unlikely((curinf->deadl_abs < now) ||
565 (curinf->cputime > curinf->slice)) )
566 {
567 /*we missed the deadline or the slice was
568 already finished... might hapen because
569 of dom_adj.*/
570 PRINT(4,"\tDomain %i.%i exceeded it's deadline/"
571 "slice (%"PRIu64" / %"PRIu64") now: %"PRIu64
572 " cputime: %"PRIu64"\n",
573 curinf->vcpu->domain->domain_id,
574 curinf->vcpu->vcpu_id,
575 curinf->deadl_abs, curinf->slice, now,
576 curinf->cputime);
577 __del_from_queue(curinf->vcpu);
578 /*common case: we miss one period!*/
579 curinf->deadl_abs += curinf->period;
581 /*if we are still behind: modulo arithmetic,
582 force deadline to be in future and
583 aligned to period borders!*/
584 if (unlikely(curinf->deadl_abs < now))
585 curinf->deadl_abs +=
586 DIV_UP(now - curinf->deadl_abs,
587 curinf->period) * curinf->period;
588 if (unlikely(curinf->deadl_abs < now))
589 printk("Fatal scheduler error: %"PRIu64" %"PRIu64" %"PRIu64
590 " diff=%"PRIu64"\n",
591 curinf->deadl_abs, now, curinf->period,
592 now - curinf->deadl_abs);
593 ASSERT(curinf->deadl_abs >= now);
594 /*give a fresh slice*/
595 curinf->cputime = 0;
596 if (PERIOD_BEGIN(curinf) > now)
597 __add_to_waitqueue_sort(curinf->vcpu);
598 else
599 __add_to_runqueue_sort(curinf->vcpu);
600 }
601 else
602 break;
603 }
604 PRINT(3,"done updating the queues\n");
605 }
608 #if (EXTRA > EXTRA_OFF)
609 /* removes a domain from the head of the according extraQ and
610 requeues it at a specified position:
611 round-robin extratime: end of extraQ
612 weighted ext.: insert in sorted list by score
613 if the domain is blocked / has regained its short-block-loss
614 time it is not put on any queue */
615 static void desched_extra_dom(s_time_t now, struct vcpu* d)
616 {
617 struct sedf_vcpu_info *inf = EDOM_INFO(d);
618 int i = extra_get_cur_q(inf);
620 #if (EXTRA == EXTRA_SLICE_WEIGHT || EXTRA == EXTRA_BLOCK_WEIGHT)
621 unsigned long oldscore;
622 #endif
623 ASSERT(extraq_on(d, i));
624 /*unset all running flags*/
625 inf->status &= ~(EXTRA_RUN_PEN | EXTRA_RUN_UTIL);
626 /*fresh slice for the next run*/
627 inf->cputime = 0;
628 /*accumulate total extratime*/
629 inf->extra_time_tot += now - inf->sched_start_abs;
630 /*remove extradomain from head of the queue*/
631 extraq_del(d, i);
633 #if (EXTRA == EXTRA_ROUNDR)
634 if ( sedf_runnable(d) && (inf->status & EXTRA_AWARE) )
635 /*add to the tail if it is runnable => round-robin*/
636 extraq_add_tail(d, EXTRA_UTIL_Q);
637 #elif (EXTRA == EXTRA_SLICE_WEIGHT || EXTRA == EXTRA_BLOCK_WEIGHT)
638 /*update the score*/
639 oldscore = inf->score[i];
640 #if (EXTRA == EXTRA_BLOCK_WEIGHT)
641 if ( i == EXTRA_PEN_Q )
642 {
643 /*domain was running in L0 extraq*/
644 /*reduce block lost, probably more sophistication here!*/
645 /*inf->short_block_lost_tot -= EXTRA_QUANTUM;*/
646 inf->short_block_lost_tot -= now - inf->sched_start_abs;
647 PRINT(3,"Domain %i.%i: Short_block_loss: %"PRIi64"\n",
648 inf->vcpu->domain->domain_id, inf->vcpu->vcpu_id,
649 inf->short_block_lost_tot);
650 if (inf->short_block_lost_tot <= 0) {
651 PRINT(4,"Domain %i.%i compensated short block loss!\n",
652 inf->vcpu->domain->domain_id, inf->vcpu->vcpu_id);
653 /*we have (over-)compensated our block penalty*/
654 inf->short_block_lost_tot = 0;
655 /*we don't want a place on the penalty queue anymore!*/
656 inf->status &= ~EXTRA_WANT_PEN_Q;
657 goto check_extra_queues;
658 }
659 /*we have to go again for another try in the block-extraq,
660 the score is not used incremantally here, as this is
661 already done by recalculating the block_lost*/
662 inf->score[EXTRA_PEN_Q] = (inf->period << 10) /
663 inf->short_block_lost_tot;
664 oldscore = 0;
665 }
666 else
667 #endif
668 {
669 /*domain was running in L1 extraq => score is inverse of
670 utilization and is used somewhat incremental!*/
671 if ( !inf->extraweight )
672 /*NB: use fixed point arithmetic with 10 bits*/
673 inf->score[EXTRA_UTIL_Q] = (inf->period << 10) /
674 inf->slice;
675 else
676 /*conversion between realtime utilisation and extrawieght:
677 full (ie 100%) utilization is equivalent to 128 extraweight*/
678 inf->score[EXTRA_UTIL_Q] = (1<<17) / inf->extraweight;
679 }
681 check_extra_queues:
682 /* Adding a runnable domain to the right queue and removing blocked ones*/
683 if ( sedf_runnable(d) )
684 {
685 /*add according to score: weighted round robin*/
686 if (((inf->status & EXTRA_AWARE) && (i == EXTRA_UTIL_Q)) ||
687 ((inf->status & EXTRA_WANT_PEN_Q) && (i == EXTRA_PEN_Q)))
688 extraq_add_sort_update(d, i, oldscore);
689 }
690 else
691 {
692 /*remove this blocked domain from the waitq!*/
693 __del_from_queue(d);
694 #if (EXTRA == EXTRA_BLOCK_WEIGHT)
695 /*make sure that we remove a blocked domain from the other
696 extraq too*/
697 if ( i == EXTRA_PEN_Q )
698 {
699 if ( extraq_on(d, EXTRA_UTIL_Q) )
700 extraq_del(d, EXTRA_UTIL_Q);
701 }
702 else
703 {
704 if ( extraq_on(d, EXTRA_PEN_Q) )
705 extraq_del(d, EXTRA_PEN_Q);
706 }
707 #endif
708 }
709 #endif
710 ASSERT(EQ(sedf_runnable(d), __task_on_queue(d)));
711 ASSERT(IMPLY(extraq_on(d, EXTRA_UTIL_Q) || extraq_on(d, EXTRA_PEN_Q),
712 sedf_runnable(d)));
713 }
714 #endif
717 static struct task_slice sedf_do_extra_schedule(
718 s_time_t now, s_time_t end_xt, struct list_head *extraq[], int cpu)
719 {
720 struct task_slice ret;
721 struct sedf_vcpu_info *runinf;
722 ASSERT(end_xt > now);
724 /* Enough time left to use for extratime? */
725 if ( end_xt - now < EXTRA_QUANTUM )
726 goto return_idle;
728 #if (EXTRA == EXTRA_BLOCK_WEIGHT)
729 if ( !list_empty(extraq[EXTRA_PEN_Q]) )
730 {
731 /*we still have elements on the level 0 extraq
732 => let those run first!*/
733 runinf = list_entry(extraq[EXTRA_PEN_Q]->next,
734 struct sedf_vcpu_info, extralist[EXTRA_PEN_Q]);
735 runinf->status |= EXTRA_RUN_PEN;
736 ret.task = runinf->vcpu;
737 ret.time = EXTRA_QUANTUM;
738 #ifdef SEDF_STATS
739 runinf->pen_extra_slices++;
740 #endif
741 }
742 else
743 #endif
744 {
745 if ( !list_empty(extraq[EXTRA_UTIL_Q]) )
746 {
747 /*use elements from the normal extraqueue*/
748 runinf = list_entry(extraq[EXTRA_UTIL_Q]->next,
749 struct sedf_vcpu_info,
750 extralist[EXTRA_UTIL_Q]);
751 runinf->status |= EXTRA_RUN_UTIL;
752 ret.task = runinf->vcpu;
753 ret.time = EXTRA_QUANTUM;
754 }
755 else
756 goto return_idle;
757 }
759 ASSERT(ret.time > 0);
760 ASSERT(sedf_runnable(ret.task));
761 return ret;
763 return_idle:
764 ret.task = IDLETASK(cpu);
765 ret.time = end_xt - now;
766 ASSERT(ret.time > 0);
767 ASSERT(sedf_runnable(ret.task));
768 return ret;
769 }
772 /* Main scheduling function
773 Reasons for calling this function are:
774 -timeslice for the current period used up
775 -domain on waitqueue has started it's period
776 -and various others ;) in general: determine which domain to run next*/
777 static struct task_slice sedf_do_schedule(s_time_t now)
778 {
779 int cpu = smp_processor_id();
780 struct list_head *runq = RUNQ(cpu);
781 struct list_head *waitq = WAITQ(cpu);
782 #if (EXTRA > EXTRA_OFF)
783 struct sedf_vcpu_info *inf = EDOM_INFO(current);
784 struct list_head *extraq[] = {
785 EXTRAQ(cpu, EXTRA_PEN_Q), EXTRAQ(cpu, EXTRA_UTIL_Q)};
786 #endif
787 struct sedf_vcpu_info *runinf, *waitinf;
788 struct task_slice ret;
790 /*idle tasks don't need any of the following stuf*/
791 if ( is_idle_vcpu(current) )
792 goto check_waitq;
794 /* create local state of the status of the domain, in order to avoid
795 inconsistent state during scheduling decisions, because data for
796 vcpu_runnable is not protected by the scheduling lock!*/
797 if ( !vcpu_runnable(current) )
798 inf->status |= SEDF_ASLEEP;
800 if ( inf->status & SEDF_ASLEEP )
801 inf->block_abs = now;
803 #if (EXTRA > EXTRA_OFF)
804 if ( unlikely(extra_runs(inf)) )
805 {
806 /*special treatment of domains running in extra time*/
807 desched_extra_dom(now, current);
808 }
809 else
810 #endif
811 {
812 desched_edf_dom(now, current);
813 }
814 check_waitq:
815 update_queues(now, runq, waitq);
817 /*now simply pick the first domain from the runqueue, which has the
818 earliest deadline, because the list is sorted*/
820 if ( !list_empty(runq) )
821 {
822 runinf = list_entry(runq->next,struct sedf_vcpu_info,list);
823 ret.task = runinf->vcpu;
824 if ( !list_empty(waitq) )
825 {
826 waitinf = list_entry(waitq->next,
827 struct sedf_vcpu_info,list);
828 /*rerun scheduler, when scheduled domain reaches it's
829 end of slice or the first domain from the waitqueue
830 gets ready*/
831 ret.time = MIN(now + runinf->slice - runinf->cputime,
832 PERIOD_BEGIN(waitinf)) - now;
833 }
834 else
835 {
836 ret.time = runinf->slice - runinf->cputime;
837 }
838 CHECK(ret.time > 0);
839 goto sched_done;
840 }
842 if ( !list_empty(waitq) )
843 {
844 waitinf = list_entry(waitq->next,struct sedf_vcpu_info, list);
845 /*we could not find any suitable domain
846 => look for domains that are aware of extratime*/
847 #if (EXTRA > EXTRA_OFF)
848 ret = sedf_do_extra_schedule(now, PERIOD_BEGIN(waitinf),
849 extraq, cpu);
850 #else
851 ret.task = IDLETASK(cpu);
852 ret.time = PERIOD_BEGIN(waitinf) - now;
853 #endif
854 CHECK(ret.time > 0);
855 }
856 else
857 {
858 /*this could probably never happen, but one never knows...*/
859 /*it can... imagine a second CPU, which is pure scifi ATM,
860 but one never knows ;)*/
861 ret.task = IDLETASK(cpu);
862 ret.time = SECONDS(1);
863 }
865 sched_done:
866 /*TODO: Do something USEFUL when this happens and find out, why it
867 still can happen!!!*/
868 if ( ret.time < 0)
869 {
870 printk("Ouch! We are seriously BEHIND schedule! %"PRIi64"\n",
871 ret.time);
872 ret.time = EXTRA_QUANTUM;
873 }
875 EDOM_INFO(ret.task)->sched_start_abs = now;
876 CHECK(ret.time > 0);
877 ASSERT(sedf_runnable(ret.task));
878 CPU_INFO(cpu)->current_slice_expires = now + ret.time;
879 return ret;
880 }
883 static void sedf_sleep(struct vcpu *d)
884 {
885 PRINT(2,"sedf_sleep was called, domain-id %i.%i\n",
886 d->domain->domain_id, d->vcpu_id);
888 if ( is_idle_vcpu(d) )
889 return;
891 EDOM_INFO(d)->status |= SEDF_ASLEEP;
893 if ( schedule_data[d->processor].curr == d )
894 {
895 cpu_raise_softirq(d->processor, SCHEDULE_SOFTIRQ);
896 }
897 else
898 {
899 if ( __task_on_queue(d) )
900 __del_from_queue(d);
901 #if (EXTRA > EXTRA_OFF)
902 if ( extraq_on(d, EXTRA_UTIL_Q) )
903 extraq_del(d, EXTRA_UTIL_Q);
904 #endif
905 #if (EXTRA == EXTRA_BLOCK_WEIGHT)
906 if ( extraq_on(d, EXTRA_PEN_Q) )
907 extraq_del(d, EXTRA_PEN_Q);
908 #endif
909 }
910 }
913 /* This function wakes up a domain, i.e. moves them into the waitqueue
914 * things to mention are: admission control is taking place nowhere at
915 * the moment, so we can't be sure, whether it is safe to wake the domain
916 * up at all. Anyway, even if it is safe (total cpu usage <=100%) there are
917 * some considerations on when to allow the domain to wake up and have it's
918 * first deadline...
919 * I detected 3 cases, which could describe the possible behaviour of the
920 * scheduler,
921 * and I'll try to make them more clear:
922 *
923 * 1. Very conservative
924 * -when a blocked domain unblocks, it is allowed to start execution at
925 * the beginning of the next complete period
926 * (D..deadline, R..running, B..blocking/sleeping, U..unblocking/waking up
927 *
928 * DRRB_____D__U_____DRRRRR___D________ ...
929 *
930 * -this causes the domain to miss a period (and a deadlline)
931 * -doesn't disturb the schedule at all
932 * -deadlines keep occuring isochronous
933 *
934 * 2. Conservative Part 1: Short Unblocking
935 * -when a domain unblocks in the same period as it was blocked it
936 * unblocks and may consume the rest of it's original time-slice minus
937 * the time it was blocked
938 * (assume period=9, slice=5)
939 *
940 * DRB_UR___DRRRRR___D...
941 *
942 * -this also doesn't disturb scheduling, but might lead to the fact, that
943 * the domain can't finish it's workload in the period
944 * -in addition to that the domain can be treated prioritised when
945 * extratime is available
946 * -addition: experiments have shown that this may have a HUGE impact on
947 * performance of other domains, becaus it can lead to excessive context
948 * switches
950 * Part2: Long Unblocking
951 * Part 2a
952 * -it is obvious that such accounting of block time, applied when
953 * unblocking is happening in later periods, works fine aswell
954 * -the domain is treated as if it would have been running since the start
955 * of its new period
956 *
957 * DRB______D___UR___D...
958 *
959 * Part 2b
960 * -if one needs the full slice in the next period, it is necessary to
961 * treat the unblocking time as the start of the new period, i.e. move
962 * the deadline further back (later)
963 * -this doesn't disturb scheduling as well, because for EDF periods can
964 * be treated as minimal inter-release times and scheduling stays
965 * correct, when deadlines are kept relative to the time the process
966 * unblocks
967 *
968 * DRB______D___URRRR___D...<prev [Thread] next>
969 * (D) <- old deadline was here
970 * -problem: deadlines don't occur isochronous anymore
971 * Part 2c (Improved Atropos design)
972 * -when a domain unblocks it is given a very short period (=latency hint)
973 * and slice length scaled accordingly
974 * -both rise again to the original value (e.g. get doubled every period)
975 *
976 * 3. Unconservative (i.e. incorrect)
977 * -to boost the performance of I/O dependent domains it would be possible
978 * to put the domain into the runnable queue immediately, and let it run
979 * for the remainder of the slice of the current period
980 * (or even worse: allocate a new full slice for the domain)
981 * -either behaviour can lead to missed deadlines in other domains as
982 * opposed to approaches 1,2a,2b
983 */
984 #if (UNBLOCK <= UNBLOCK_SHORT_RESUME)
985 static void unblock_short_vcons(struct sedf_vcpu_info* inf, s_time_t now)
986 {
987 inf->deadl_abs += inf->period;
988 inf->cputime = 0;
989 }
990 #endif
992 #if (UNBLOCK == UNBLOCK_SHORT_RESUME)
993 static void unblock_short_cons(struct sedf_vcpu_info* inf, s_time_t now)
994 {
995 /*treat blocked time as consumed by the domain*/
996 inf->cputime += now - inf->block_abs;
997 if ( (inf->cputime + EXTRA_QUANTUM) > inf->slice )
998 {
999 /*we don't have a reasonable amount of time in
1000 our slice left :( => start in next period!*/
1001 unblock_short_vcons(inf, now);
1003 #ifdef SEDF_STATS
1004 else
1005 inf->short_cont++;
1006 #endif
1008 #endif
1010 static void unblock_short_extra_support(
1011 struct sedf_vcpu_info* inf, s_time_t now)
1013 /*this unblocking scheme tries to support the domain, by assigning it
1014 a priority in extratime distribution according to the loss of time
1015 in this slice due to blocking*/
1016 s_time_t pen;
1018 /*no more realtime execution in this period!*/
1019 inf->deadl_abs += inf->period;
1020 if ( likely(inf->block_abs) )
1022 //treat blocked time as consumed by the domain*/
1023 /*inf->cputime += now - inf->block_abs;*/
1024 /*penalty is time the domain would have
1025 had if it continued to run */
1026 pen = (inf->slice - inf->cputime);
1027 if ( pen < 0 )
1028 pen = 0;
1029 /*accumulate all penalties over the periods*/
1030 /*inf->short_block_lost_tot += pen;*/
1031 /*set penalty to the current value*/
1032 inf->short_block_lost_tot = pen;
1033 /*not sure which one is better.. but seems to work well...*/
1035 if ( inf->short_block_lost_tot )
1037 inf->score[0] = (inf->period << 10) /
1038 inf->short_block_lost_tot;
1039 #ifdef SEDF_STATS
1040 inf->pen_extra_blocks++;
1041 #endif
1042 if ( extraq_on(inf->vcpu, EXTRA_PEN_Q) )
1043 /*remove domain for possible resorting!*/
1044 extraq_del(inf->vcpu, EXTRA_PEN_Q);
1045 else
1046 /*remember that we want to be on the penalty q
1047 so that we can continue when we (un-)block
1048 in penalty-extratime*/
1049 inf->status |= EXTRA_WANT_PEN_Q;
1051 /*(re-)add domain to the penalty extraq*/
1052 extraq_add_sort_update(inf->vcpu, EXTRA_PEN_Q, 0);
1056 /*give it a fresh slice in the next period!*/
1057 inf->cputime = 0;
1061 #if (UNBLOCK == UNBLOCK_ISOCHRONOUS_EDF)
1062 static void unblock_long_vcons(struct sedf_vcpu_info* inf, s_time_t now)
1064 /* align to next future period */
1065 inf->deadl_abs += (DIV_UP(now - inf->deadl_abs, inf->period) +1)
1066 * inf->period;
1067 inf->cputime = 0;
1069 #endif
1072 #if 0
1073 static void unblock_long_cons_a (struct sedf_vcpu_info* inf, s_time_t now)
1075 /*treat the time the domain was blocked in the
1076 CURRENT period as consumed by the domain*/
1077 inf->cputime = (now - inf->deadl_abs) % inf->period;
1078 if ( (inf->cputime + EXTRA_QUANTUM) > inf->slice )
1080 /*we don't have a reasonable amount of time in our slice
1081 left :( => start in next period!*/
1082 unblock_long_vcons(inf, now);
1085 #endif
1088 static void unblock_long_cons_b(struct sedf_vcpu_info* inf,s_time_t now)
1090 /*Conservative 2b*/
1091 /*Treat the unblocking time as a start of a new period */
1092 inf->deadl_abs = now + inf->period;
1093 inf->cputime = 0;
1097 #if (UNBLOCK == UNBLOCK_ATROPOS)
1098 static void unblock_long_cons_c(struct sedf_vcpu_info* inf,s_time_t now)
1100 if ( likely(inf->latency) )
1102 /*scale the slice and period accordingly to the latency hint*/
1103 /*reduce period temporarily to the latency hint*/
1104 inf->period = inf->latency;
1105 /*this results in max. 4s slice/period length*/
1106 ASSERT((inf->period < ULONG_MAX)
1107 && (inf->slice_orig < ULONG_MAX));
1108 /*scale slice accordingly, so that utilisation stays the same*/
1109 inf->slice = (inf->period * inf->slice_orig)
1110 / inf->period_orig;
1111 inf->deadl_abs = now + inf->period;
1112 inf->cputime = 0;
1114 else
1116 /*we don't have a latency hint.. use some other technique*/
1117 unblock_long_cons_b(inf, now);
1120 #endif
1123 #if (UNBLOCK == UNBLOCK_BURST)
1124 /*a new idea of dealing with short blocks: burst period scaling*/
1125 static void unblock_short_burst(struct sedf_vcpu_info* inf, s_time_t now)
1127 /*treat blocked time as consumed by the domain*/
1128 inf->cputime += now - inf->block_abs;
1130 if ( (inf->cputime + EXTRA_QUANTUM) <= inf->slice )
1132 /*if we can still use some time in the current slice
1133 then use it!*/
1134 #ifdef SEDF_STATS
1135 /*we let the domain run in the current period*/
1136 inf->short_cont++;
1137 #endif
1139 else
1141 /*we don't have a reasonable amount of time in
1142 our slice left => switch to burst mode*/
1143 if ( likely(inf->unblock_abs) )
1145 /*set the period-length to the current blocking
1146 interval, possible enhancements: average over last
1147 blocking intervals, user-specified minimum,...*/
1148 inf->period = now - inf->unblock_abs;
1149 /*check for overflow on multiplication*/
1150 ASSERT((inf->period < ULONG_MAX)
1151 && (inf->slice_orig < ULONG_MAX));
1152 /*scale slice accordingly, so that utilisation
1153 stays the same*/
1154 inf->slice = (inf->period * inf->slice_orig)
1155 / inf->period_orig;
1156 /*set new (shorter) deadline*/
1157 inf->deadl_abs += inf->period;
1159 else
1161 /*in case we haven't unblocked before
1162 start in next period!*/
1163 inf->cputime=0;
1164 inf->deadl_abs += inf->period;
1168 inf->unblock_abs = now;
1172 static void unblock_long_burst(struct sedf_vcpu_info* inf, s_time_t now)
1174 if ( unlikely(inf->latency && (inf->period > inf->latency)) )
1176 /*scale the slice and period accordingly to the latency hint*/
1177 inf->period = inf->latency;
1178 /*check for overflows on multiplication*/
1179 ASSERT((inf->period < ULONG_MAX)
1180 && (inf->slice_orig < ULONG_MAX));
1181 /*scale slice accordingly, so that utilisation stays the same*/
1182 inf->slice = (inf->period * inf->slice_orig)
1183 / inf->period_orig;
1184 inf->deadl_abs = now + inf->period;
1185 inf->cputime = 0;
1187 else
1189 /*we don't have a latency hint.. or we are currently in
1190 "burst mode": use some other technique
1191 NB: this should be in fact the normal way of operation,
1192 when we are in sync with the device!*/
1193 unblock_long_cons_b(inf, now);
1196 inf->unblock_abs = now;
1198 #endif /* UNBLOCK == UNBLOCK_BURST */
1201 #define DOMAIN_EDF 1
1202 #define DOMAIN_EXTRA_PEN 2
1203 #define DOMAIN_EXTRA_UTIL 3
1204 #define DOMAIN_IDLE 4
1205 static inline int get_run_type(struct vcpu* d)
1207 struct sedf_vcpu_info* inf = EDOM_INFO(d);
1208 if (is_idle_vcpu(d))
1209 return DOMAIN_IDLE;
1210 if (inf->status & EXTRA_RUN_PEN)
1211 return DOMAIN_EXTRA_PEN;
1212 if (inf->status & EXTRA_RUN_UTIL)
1213 return DOMAIN_EXTRA_UTIL;
1214 return DOMAIN_EDF;
1218 /*Compares two domains in the relation of whether the one is allowed to
1219 interrupt the others execution.
1220 It returns true (!=0) if a switch to the other domain is good.
1221 Current Priority scheme is as follows:
1222 EDF > L0 (penalty based) extra-time >
1223 L1 (utilization) extra-time > idle-domain
1224 In the same class priorities are assigned as following:
1225 EDF: early deadline > late deadline
1226 L0 extra-time: lower score > higher score*/
1227 static inline int should_switch(struct vcpu *cur,
1228 struct vcpu *other,
1229 s_time_t now)
1231 struct sedf_vcpu_info *cur_inf, *other_inf;
1232 cur_inf = EDOM_INFO(cur);
1233 other_inf = EDOM_INFO(other);
1235 /*check whether we need to make an earlier sched-decision*/
1236 if (PERIOD_BEGIN(other_inf) <
1237 CPU_INFO(other->processor)->current_slice_expires)
1238 return 1;
1239 /*no timing-based switches need to be taken into account here*/
1240 switch (get_run_type(cur)) {
1241 case DOMAIN_EDF:
1242 /* do not interrupt a running EDF domain */
1243 return 0;
1244 case DOMAIN_EXTRA_PEN:
1245 /*check whether we also want
1246 the L0 ex-q with lower score*/
1247 if ((other_inf->status & EXTRA_WANT_PEN_Q)
1248 && (other_inf->score[EXTRA_PEN_Q] <
1249 cur_inf->score[EXTRA_PEN_Q]))
1250 return 1;
1251 else return 0;
1252 case DOMAIN_EXTRA_UTIL:
1253 /*check whether we want the L0 extraq, don't
1254 switch if both domains want L1 extraq */
1255 if (other_inf->status & EXTRA_WANT_PEN_Q)
1256 return 1;
1257 else return 0;
1258 case DOMAIN_IDLE:
1259 return 1;
1261 return 1;
1264 void sedf_wake(struct vcpu *d)
1266 s_time_t now = NOW();
1267 struct sedf_vcpu_info* inf = EDOM_INFO(d);
1269 PRINT(3, "sedf_wake was called, domain-id %i.%i\n",d->domain->domain_id,
1270 d->vcpu_id);
1272 if ( unlikely(is_idle_vcpu(d)) )
1273 return;
1275 if ( unlikely(__task_on_queue(d)) )
1277 PRINT(3,"\tdomain %i.%i is already in some queue\n",
1278 d->domain->domain_id, d->vcpu_id);
1279 return;
1282 ASSERT(!sedf_runnable(d));
1283 inf->status &= ~SEDF_ASLEEP;
1284 ASSERT(!extraq_on(d, EXTRA_UTIL_Q));
1285 ASSERT(!extraq_on(d, EXTRA_PEN_Q));
1287 if ( unlikely(inf->deadl_abs == 0) )
1289 /*initial setup of the deadline*/
1290 inf->deadl_abs = now + inf->slice;
1293 PRINT(3, "waking up domain %i.%i (deadl= %"PRIu64" period= %"PRIu64
1294 "now= %"PRIu64")\n",
1295 d->domain->domain_id, d->vcpu_id, inf->deadl_abs, inf->period, now);
1297 #ifdef SEDF_STATS
1298 inf->block_tot++;
1299 #endif
1301 if ( unlikely(now < PERIOD_BEGIN(inf)) )
1303 PRINT(4,"extratime unblock\n");
1304 /* unblocking in extra-time! */
1305 #if (EXTRA == EXTRA_BLOCK_WEIGHT)
1306 if ( inf->status & EXTRA_WANT_PEN_Q )
1308 /*we have a domain that wants compensation
1309 for block penalty and did just block in
1310 its compensation time. Give it another
1311 chance!*/
1312 extraq_add_sort_update(d, EXTRA_PEN_Q, 0);
1314 #endif
1315 extraq_check_add_unblocked(d, 0);
1317 else
1319 if ( now < inf->deadl_abs )
1321 PRINT(4,"short unblocking\n");
1322 /*short blocking*/
1323 #ifdef SEDF_STATS
1324 inf->short_block_tot++;
1325 #endif
1326 #if (UNBLOCK <= UNBLOCK_ATROPOS)
1327 unblock_short_vcons(inf, now);
1328 #elif (UNBLOCK == UNBLOCK_SHORT_RESUME)
1329 unblock_short_cons(inf, now);
1330 #elif (UNBLOCK == UNBLOCK_BURST)
1331 unblock_short_burst(inf, now);
1332 #elif (UNBLOCK == UNBLOCK_EXTRA_SUPPORT)
1333 unblock_short_extra_support(inf, now);
1334 #endif
1336 extraq_check_add_unblocked(d, 1);
1338 else
1340 PRINT(4,"long unblocking\n");
1341 /*long unblocking*/
1342 #ifdef SEDF_STATS
1343 inf->long_block_tot++;
1344 #endif
1345 #if (UNBLOCK == UNBLOCK_ISOCHRONOUS_EDF)
1346 unblock_long_vcons(inf, now);
1347 #elif (UNBLOCK == UNBLOCK_EDF \
1348 || UNBLOCK == UNBLOCK_EXTRA_SUPPORT)
1349 unblock_long_cons_b(inf, now);
1350 #elif (UNBLOCK == UNBLOCK_ATROPOS)
1351 unblock_long_cons_c(inf, now);
1352 #elif (UNBLOCK == UNBLOCK_SHORT_RESUME)
1353 unblock_long_cons_b(inf, now);
1354 #elif (UNBLOCK == UNBLOCK_BURST)
1355 unblock_long_burst(inf, now);
1356 #endif
1358 extraq_check_add_unblocked(d, 1);
1362 PRINT(3, "woke up domain %i.%i (deadl= %"PRIu64" period= %"PRIu64
1363 "now= %"PRIu64")\n",
1364 d->domain->domain_id, d->vcpu_id, inf->deadl_abs,
1365 inf->period, now);
1367 if ( PERIOD_BEGIN(inf) > now )
1369 __add_to_waitqueue_sort(d);
1370 PRINT(3,"added to waitq\n");
1372 else
1374 __add_to_runqueue_sort(d);
1375 PRINT(3,"added to runq\n");
1378 #ifdef SEDF_STATS
1379 /*do some statistics here...*/
1380 if ( inf->block_abs != 0 )
1382 inf->block_time_tot += now - inf->block_abs;
1383 inf->penalty_time_tot +=
1384 PERIOD_BEGIN(inf) + inf->cputime - inf->block_abs;
1386 #endif
1388 /*sanity check: make sure each extra-aware domain IS on the util-q!*/
1389 ASSERT(IMPLY(inf->status & EXTRA_AWARE, extraq_on(d, EXTRA_UTIL_Q)));
1390 ASSERT(__task_on_queue(d));
1391 /*check whether the awakened task needs to invoke the do_schedule
1392 routine. Try to avoid unnecessary runs but:
1393 Save approximation: Always switch to scheduler!*/
1394 ASSERT(d->processor >= 0);
1395 ASSERT(d->processor < NR_CPUS);
1396 ASSERT(schedule_data[d->processor].curr);
1398 if ( should_switch(schedule_data[d->processor].curr, d, now) )
1399 cpu_raise_softirq(d->processor, SCHEDULE_SOFTIRQ);
1403 static int sedf_set_affinity(struct vcpu *v, cpumask_t *affinity)
1405 if ( v == current )
1406 return cpu_isset(v->processor, *affinity) ? 0 : -EBUSY;
1408 vcpu_pause(v);
1409 v->cpu_affinity = *affinity;
1410 v->processor = first_cpu(v->cpu_affinity);
1411 vcpu_unpause(v);
1413 return 0;
1417 /* Print a lot of useful information about a domains in the system */
1418 static void sedf_dump_domain(struct vcpu *d)
1420 printk("%i.%i has=%c ", d->domain->domain_id, d->vcpu_id,
1421 test_bit(_VCPUF_running, &d->vcpu_flags) ? 'T':'F');
1422 printk("p=%"PRIu64" sl=%"PRIu64" ddl=%"PRIu64" w=%hu"
1423 " sc=%i xtr(%s)=%"PRIu64" ew=%hu",
1424 EDOM_INFO(d)->period, EDOM_INFO(d)->slice, EDOM_INFO(d)->deadl_abs,
1425 EDOM_INFO(d)->weight,
1426 EDOM_INFO(d)->score[EXTRA_UTIL_Q],
1427 (EDOM_INFO(d)->status & EXTRA_AWARE) ? "yes" : "no",
1428 EDOM_INFO(d)->extra_time_tot, EDOM_INFO(d)->extraweight);
1430 #ifdef SEDF_STATS
1431 if ( EDOM_INFO(d)->block_time_tot != 0 )
1432 printf(" pen=%"PRIu64"%%", (EDOM_INFO(d)->penalty_time_tot * 100) /
1433 EDOM_INFO(d)->block_time_tot);
1434 if ( EDOM_INFO(d)->block_tot != 0 )
1435 printf("\n blks=%u sh=%u (%u%%) (shc=%u (%u%%) shex=%i "\
1436 "shexsl=%i) l=%u (%u%%) avg: b=%"PRIu64" p=%"PRIu64"",
1437 EDOM_INFO(d)->block_tot, EDOM_INFO(d)->short_block_tot,
1438 (EDOM_INFO(d)->short_block_tot * 100)
1439 / EDOM_INFO(d)->block_tot, EDOM_INFO(d)->short_cont,
1440 (EDOM_INFO(d)->short_cont * 100) / EDOM_INFO(d)->block_tot,
1441 EDOM_INFO(d)->pen_extra_blocks,
1442 EDOM_INFO(d)->pen_extra_slices,
1443 EDOM_INFO(d)->long_block_tot,
1444 (EDOM_INFO(d)->long_block_tot * 100) / EDOM_INFO(d)->block_tot,
1445 (EDOM_INFO(d)->block_time_tot) / EDOM_INFO(d)->block_tot,
1446 (EDOM_INFO(d)->penalty_time_tot) / EDOM_INFO(d)->block_tot);
1447 #endif
1448 printf("\n");
1452 /* dumps all domains on hte specified cpu */
1453 static void sedf_dump_cpu_state(int i)
1455 struct list_head *list, *queue, *tmp;
1456 struct sedf_vcpu_info *d_inf;
1457 struct domain *d;
1458 struct vcpu *ed;
1459 int loop = 0;
1461 printk("now=%"PRIu64"\n",NOW());
1462 queue = RUNQ(i);
1463 printk("RUNQ rq %lx n: %lx, p: %lx\n", (unsigned long)queue,
1464 (unsigned long) queue->next, (unsigned long) queue->prev);
1465 list_for_each_safe ( list, tmp, queue )
1467 printk("%3d: ",loop++);
1468 d_inf = list_entry(list, struct sedf_vcpu_info, list);
1469 sedf_dump_domain(d_inf->vcpu);
1472 queue = WAITQ(i); loop = 0;
1473 printk("\nWAITQ rq %lx n: %lx, p: %lx\n", (unsigned long)queue,
1474 (unsigned long) queue->next, (unsigned long) queue->prev);
1475 list_for_each_safe ( list, tmp, queue )
1477 printk("%3d: ",loop++);
1478 d_inf = list_entry(list, struct sedf_vcpu_info, list);
1479 sedf_dump_domain(d_inf->vcpu);
1482 queue = EXTRAQ(i,EXTRA_PEN_Q); loop = 0;
1483 printk("\nEXTRAQ (penalty) rq %lx n: %lx, p: %lx\n",
1484 (unsigned long)queue, (unsigned long) queue->next,
1485 (unsigned long) queue->prev);
1486 list_for_each_safe ( list, tmp, queue )
1488 d_inf = list_entry(list, struct sedf_vcpu_info,
1489 extralist[EXTRA_PEN_Q]);
1490 printk("%3d: ",loop++);
1491 sedf_dump_domain(d_inf->vcpu);
1494 queue = EXTRAQ(i,EXTRA_UTIL_Q); loop = 0;
1495 printk("\nEXTRAQ (utilization) rq %lx n: %lx, p: %lx\n",
1496 (unsigned long)queue, (unsigned long) queue->next,
1497 (unsigned long) queue->prev);
1498 list_for_each_safe ( list, tmp, queue )
1500 d_inf = list_entry(list, struct sedf_vcpu_info,
1501 extralist[EXTRA_UTIL_Q]);
1502 printk("%3d: ",loop++);
1503 sedf_dump_domain(d_inf->vcpu);
1506 loop = 0;
1507 printk("\nnot on Q\n");
1509 for_each_domain ( d )
1511 for_each_vcpu(d, ed)
1513 if ( !__task_on_queue(ed) && (ed->processor == i) )
1515 printk("%3d: ",loop++);
1516 sedf_dump_domain(ed);
1523 /* Adjusts periods and slices of the domains accordingly to their weights. */
1524 static int sedf_adjust_weights(struct sched_adjdom_cmd *cmd)
1526 struct vcpu *p;
1527 struct domain *d;
1528 int sumw[NR_CPUS];
1529 s_time_t sumt[NR_CPUS];
1530 int cpu;
1532 for ( cpu = 0; cpu < NR_CPUS; cpu++ )
1534 sumw[cpu] = 0;
1535 sumt[cpu] = 0;
1538 /* sum up all weights */
1539 for_each_domain( d )
1541 for_each_vcpu( d, p )
1543 if ( EDOM_INFO(p)->weight )
1545 sumw[p->processor] += EDOM_INFO(p)->weight;
1547 else
1549 /*don't modify domains who don't have a weight, but sum
1550 up the time they need, projected to a WEIGHT_PERIOD,
1551 so that this time is not given to the weight-driven
1552 domains*/
1553 /*check for overflows*/
1554 ASSERT((WEIGHT_PERIOD < ULONG_MAX)
1555 && (EDOM_INFO(p)->slice_orig < ULONG_MAX));
1556 sumt[p->processor] +=
1557 (WEIGHT_PERIOD * EDOM_INFO(p)->slice_orig) /
1558 EDOM_INFO(p)->period_orig;
1563 /* adjust all slices (and periods) to the new weight */
1564 for_each_domain( d )
1566 for_each_vcpu ( d, p )
1568 if ( EDOM_INFO(p)->weight )
1570 EDOM_INFO(p)->period_orig =
1571 EDOM_INFO(p)->period = WEIGHT_PERIOD;
1572 EDOM_INFO(p)->slice_orig =
1573 EDOM_INFO(p)->slice =
1574 (EDOM_INFO(p)->weight *
1575 (WEIGHT_PERIOD - WEIGHT_SAFETY - sumt[p->processor])) /
1576 sumw[p->processor];
1581 return 0;
1585 /* set or fetch domain scheduling parameters */
1586 static int sedf_adjdom(struct domain *p, struct sched_adjdom_cmd *cmd)
1588 struct vcpu *v;
1590 PRINT(2,"sedf_adjdom was called, domain-id %i new period %"PRIu64" "\
1591 "new slice %"PRIu64"\nlatency %"PRIu64" extra:%s\n",
1592 p->domain_id, cmd->u.sedf.period, cmd->u.sedf.slice,
1593 cmd->u.sedf.latency, (cmd->u.sedf.extratime)?"yes":"no");
1595 if ( cmd->direction == SCHED_INFO_PUT )
1597 /*check for sane parameters*/
1598 if (!cmd->u.sedf.period && !cmd->u.sedf.weight)
1599 return -EINVAL;
1600 if (cmd->u.sedf.weight) {
1601 if ((cmd->u.sedf.extratime & EXTRA_AWARE) &&
1602 (! cmd->u.sedf.period)) {
1603 /*weight driven domains with xtime ONLY!*/
1604 for_each_vcpu(p, v) {
1605 EDOM_INFO(v)->extraweight = cmd->u.sedf.weight;
1606 EDOM_INFO(v)->weight = 0;
1607 EDOM_INFO(v)->slice = 0;
1608 EDOM_INFO(v)->period = WEIGHT_PERIOD;
1610 } else {
1611 /*weight driven domains with real-time execution*/
1612 for_each_vcpu(p, v)
1613 EDOM_INFO(v)->weight = cmd->u.sedf.weight;
1616 else {
1617 /*time driven domains*/
1618 for_each_vcpu(p, v) {
1619 /*
1620 * Sanity checking: note that disabling extra weight requires
1621 * that we set a non-zero slice.
1622 */
1623 if ( (cmd->u.sedf.period > PERIOD_MAX) ||
1624 (cmd->u.sedf.period < PERIOD_MIN) ||
1625 (cmd->u.sedf.slice > SLICE_MAX) ||
1626 (cmd->u.sedf.slice < SLICE_MIN) ||
1627 (cmd->u.sedf.slice > cmd->u.sedf.period) )
1628 return -EINVAL;
1629 EDOM_INFO(v)->weight = 0;
1630 EDOM_INFO(v)->extraweight = 0;
1631 EDOM_INFO(v)->period_orig =
1632 EDOM_INFO(v)->period = cmd->u.sedf.period;
1633 EDOM_INFO(v)->slice_orig =
1634 EDOM_INFO(v)->slice = cmd->u.sedf.slice;
1637 if (sedf_adjust_weights(cmd))
1638 return -EINVAL;
1640 for_each_vcpu(p, v) {
1641 EDOM_INFO(v)->status =
1642 (EDOM_INFO(v)->status &
1643 ~EXTRA_AWARE) | (cmd->u.sedf.extratime & EXTRA_AWARE);
1644 EDOM_INFO(v)->latency = cmd->u.sedf.latency;
1645 extraq_check(v);
1648 else if ( cmd->direction == SCHED_INFO_GET )
1650 cmd->u.sedf.period = EDOM_INFO(p->vcpu[0])->period;
1651 cmd->u.sedf.slice = EDOM_INFO(p->vcpu[0])->slice;
1652 cmd->u.sedf.extratime = EDOM_INFO(p->vcpu[0])->status
1653 & EXTRA_AWARE;
1654 cmd->u.sedf.latency = EDOM_INFO(p->vcpu[0])->latency;
1655 cmd->u.sedf.weight = EDOM_INFO(p->vcpu[0])->weight;
1657 PRINT(2,"sedf_adjdom_finished\n");
1658 return 0;
1661 struct scheduler sched_sedf_def = {
1662 .name = "Simple EDF Scheduler",
1663 .opt_name = "sedf",
1664 .sched_id = SCHED_SEDF,
1666 .alloc_task = sedf_alloc_task,
1667 .add_task = sedf_add_task,
1668 .free_task = sedf_free_task,
1669 .do_schedule = sedf_do_schedule,
1670 .dump_cpu_state = sedf_dump_cpu_state,
1671 .sleep = sedf_sleep,
1672 .wake = sedf_wake,
1673 .adjdom = sedf_adjdom,
1674 .set_affinity = sedf_set_affinity
1675 };
1677 /*
1678 * Local variables:
1679 * mode: C
1680 * c-set-style: "BSD"
1681 * c-basic-offset: 4
1682 * tab-width: 4
1683 * indent-tabs-mode: nil
1684 * End:
1685 */