ia64/xen-unstable

view xen/common/sched_sedf.c @ 11128:f2f584093379

[POWERPC] Update .hgignore
Signed-off-by: Hollis Blanchard <hollisb@us.ibm.com>
author kfraser@localhost.localdomain
date Tue Aug 15 10:38:59 2006 +0100 (2006-08-15)
parents 5e8c254c9dcd
children 88e6bd5e2b54
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 do { \
20 if ( (_f) <= SEDFLEVEL ) \
21 printk(_a ); \
22 } while ( 0 )
24 #ifndef NDEBUG
25 #define SEDF_STATS
26 #define CHECK(_p) \
27 do { \
28 if ( !(_p) ) \
29 printk("Check '%s' failed, line %d, file %s\n", \
30 #_p , __LINE__, __FILE__); \
31 } while ( 0 )
32 #else
33 #define CHECK(_p) ((void)0)
34 #endif
36 #define EXTRA_NONE (0)
37 #define EXTRA_AWARE (1)
38 #define EXTRA_RUN_PEN (2)
39 #define EXTRA_RUN_UTIL (4)
40 #define EXTRA_WANT_PEN_Q (8)
41 #define EXTRA_PEN_Q (0)
42 #define EXTRA_UTIL_Q (1)
43 #define SEDF_ASLEEP (16)
45 #define EXTRA_QUANTUM (MICROSECS(500))
46 #define WEIGHT_PERIOD (MILLISECS(100))
47 #define WEIGHT_SAFETY (MILLISECS(5))
49 #define PERIOD_MAX MILLISECS(10000) /* 10s */
50 #define PERIOD_MIN (MICROSECS(10)) /* 10us */
51 #define SLICE_MIN (MICROSECS(5)) /* 5us */
53 #define IMPLY(a, b) (!(a) || (b))
54 #define EQ(a, b) ((!!(a)) == (!!(b)))
57 struct sedf_dom_info {
58 struct domain *domain;
59 };
61 struct sedf_vcpu_info {
62 struct vcpu *vcpu;
63 struct list_head list;
64 struct list_head extralist[2];
66 /*Parameters for EDF*/
67 s_time_t period; /*=(relative deadline)*/
68 s_time_t slice; /*=worst case execution time*/
70 /*Advaced Parameters*/
71 /*Latency Scaling*/
72 s_time_t period_orig;
73 s_time_t slice_orig;
74 s_time_t latency;
76 /*status of domain*/
77 int status;
78 /*weights for "Scheduling for beginners/ lazy/ etc." ;)*/
79 short weight;
80 short extraweight;
81 /*Bookkeeping*/
82 s_time_t deadl_abs;
83 s_time_t sched_start_abs;
84 s_time_t cputime;
85 /* times the domain un-/blocked */
86 s_time_t block_abs;
87 s_time_t unblock_abs;
89 /*scores for {util, block penalty}-weighted extratime distribution*/
90 int score[2];
91 s_time_t short_block_lost_tot;
93 /*Statistics*/
94 s_time_t extra_time_tot;
96 #ifdef SEDF_STATS
97 s_time_t block_time_tot;
98 s_time_t penalty_time_tot;
99 int block_tot;
100 int short_block_tot;
101 int long_block_tot;
102 int short_cont;
103 int pen_extra_blocks;
104 int pen_extra_slices;
105 #endif
106 };
108 struct sedf_cpu_info {
109 struct list_head runnableq;
110 struct list_head waitq;
111 struct list_head extraq[2];
112 s_time_t current_slice_expires;
113 };
115 #define EDOM_INFO(d) ((struct sedf_vcpu_info *)((d)->sched_priv))
116 #define CPU_INFO(cpu) \
117 ((struct sedf_cpu_info *)per_cpu(schedule_data, cpu).sched_priv)
118 #define LIST(d) (&EDOM_INFO(d)->list)
119 #define EXTRALIST(d,i) (&(EDOM_INFO(d)->extralist[i]))
120 #define RUNQ(cpu) (&CPU_INFO(cpu)->runnableq)
121 #define WAITQ(cpu) (&CPU_INFO(cpu)->waitq)
122 #define EXTRAQ(cpu,i) (&(CPU_INFO(cpu)->extraq[i]))
123 #define IDLETASK(cpu) ((struct vcpu *)per_cpu(schedule_data, cpu).idle)
125 #define PERIOD_BEGIN(inf) ((inf)->deadl_abs - (inf)->period)
127 #define MIN(x,y) (((x)<(y))?(x):(y))
128 #define DIV_UP(x,y) (((x) + (y) - 1) / y)
130 #define extra_runs(inf) ((inf->status) & 6)
131 #define extra_get_cur_q(inf) (((inf->status & 6) >> 1)-1)
132 #define sedf_runnable(edom) (!(EDOM_INFO(edom)->status & SEDF_ASLEEP))
135 static void sedf_dump_cpu_state(int i);
137 static inline int extraq_on(struct vcpu *d, int i)
138 {
139 return ((EXTRALIST(d,i)->next != NULL) &&
140 (EXTRALIST(d,i)->next != EXTRALIST(d,i)));
141 }
143 static inline void extraq_add_head(struct vcpu *d, int i)
144 {
145 list_add(EXTRALIST(d,i), EXTRAQ(d->processor,i));
146 ASSERT(extraq_on(d, i));
147 }
149 static inline void extraq_add_tail(struct vcpu *d, int i)
150 {
151 list_add_tail(EXTRALIST(d,i), EXTRAQ(d->processor,i));
152 ASSERT(extraq_on(d, i));
153 }
155 static inline void extraq_del(struct vcpu *d, int i)
156 {
157 struct list_head *list = EXTRALIST(d,i);
158 ASSERT(extraq_on(d,i));
159 PRINT(3, "Removing domain %i.%i from L%i extraq\n",
160 d->domain->domain_id, d->vcpu_id, i);
161 list_del(list);
162 list->next = NULL;
163 ASSERT(!extraq_on(d, i));
164 }
166 /* adds a domain to the queue of processes which are aware of extra time. List
167 is sorted by score, where a lower score means higher priority for an extra
168 slice. It also updates the score, by simply subtracting a fixed value from
169 each entry, in order to avoid overflow. The algorithm works by simply
170 charging each domain that recieved extratime with an inverse of its weight.
171 */
172 static inline void extraq_add_sort_update(struct vcpu *d, int i, int sub)
173 {
174 struct list_head *cur;
175 struct sedf_vcpu_info *curinf;
177 ASSERT(!extraq_on(d,i));
179 PRINT(3, "Adding domain %i.%i (score= %i, short_pen= %"PRIi64")"
180 " to L%i extraq\n",
181 d->domain->domain_id, d->vcpu_id, EDOM_INFO(d)->score[i],
182 EDOM_INFO(d)->short_block_lost_tot, i);
184 /*
185 * Iterate through all elements to find our "hole" and on our way
186 * update all the other scores.
187 */
188 list_for_each ( cur, EXTRAQ(d->processor, i) )
189 {
190 curinf = list_entry(cur,struct sedf_vcpu_info,extralist[i]);
191 curinf->score[i] -= sub;
192 if ( EDOM_INFO(d)->score[i] < curinf->score[i] )
193 break;
194 PRINT(4,"\tbehind domain %i.%i (score= %i)\n",
195 curinf->vcpu->domain->domain_id,
196 curinf->vcpu->vcpu_id, curinf->score[i]);
197 }
199 /* cur now contains the element, before which we'll enqueue. */
200 PRINT(3, "\tlist_add to %p\n", cur->prev);
201 list_add(EXTRALIST(d,i),cur->prev);
203 /* Continue updating the extraq. */
204 if ( (cur != EXTRAQ(d->processor,i)) && sub )
205 {
206 for ( cur = cur->next; cur != EXTRAQ(d->processor,i); cur = cur->next )
207 {
208 curinf = list_entry(cur,struct sedf_vcpu_info, extralist[i]);
209 curinf->score[i] -= sub;
210 PRINT(4, "\tupdating domain %i.%i (score= %u)\n",
211 curinf->vcpu->domain->domain_id,
212 curinf->vcpu->vcpu_id, curinf->score[i]);
213 }
214 }
216 ASSERT(extraq_on(d,i));
217 }
218 static inline void extraq_check(struct vcpu *d)
219 {
220 if ( extraq_on(d, EXTRA_UTIL_Q) )
221 {
222 PRINT(2,"Dom %i.%i is on L1 extraQ\n",
223 d->domain->domain_id, d->vcpu_id);
225 if ( !(EDOM_INFO(d)->status & EXTRA_AWARE) &&
226 !extra_runs(EDOM_INFO(d)) )
227 {
228 extraq_del(d, EXTRA_UTIL_Q);
229 PRINT(2,"Removed dom %i.%i from L1 extraQ\n",
230 d->domain->domain_id, d->vcpu_id);
231 }
232 }
233 else
234 {
235 PRINT(2, "Dom %i.%i is NOT on L1 extraQ\n",
236 d->domain->domain_id,
237 d->vcpu_id);
239 if ( (EDOM_INFO(d)->status & EXTRA_AWARE) && sedf_runnable(d) )
240 {
241 extraq_add_sort_update(d, EXTRA_UTIL_Q, 0);
242 PRINT(2,"Added dom %i.%i to L1 extraQ\n",
243 d->domain->domain_id, d->vcpu_id);
244 }
245 }
246 }
248 static inline void extraq_check_add_unblocked(struct vcpu *d, int priority)
249 {
250 struct sedf_vcpu_info *inf = EDOM_INFO(d);
252 if ( inf->status & EXTRA_AWARE )
253 /* Put on the weighted extraq without updating any scores. */
254 extraq_add_sort_update(d, EXTRA_UTIL_Q, 0);
255 }
257 static inline int __task_on_queue(struct vcpu *d)
258 {
259 return (((LIST(d))->next != NULL) && (LIST(d)->next != LIST(d)));
260 }
262 static inline void __del_from_queue(struct vcpu *d)
263 {
264 struct list_head *list = LIST(d);
265 ASSERT(__task_on_queue(d));
266 PRINT(3,"Removing domain %i.%i (bop= %"PRIu64") from runq/waitq\n",
267 d->domain->domain_id, d->vcpu_id, PERIOD_BEGIN(EDOM_INFO(d)));
268 list_del(list);
269 list->next = NULL;
270 ASSERT(!__task_on_queue(d));
271 }
273 typedef int(*list_comparer)(struct list_head* el1, struct list_head* el2);
275 static inline void list_insert_sort(
276 struct list_head *list, struct list_head *element, list_comparer comp)
277 {
278 struct list_head *cur;
280 /* Iterate through all elements to find our "hole". */
281 list_for_each( cur, list )
282 if ( comp(element, cur) < 0 )
283 break;
285 /* cur now contains the element, before which we'll enqueue. */
286 PRINT(3,"\tlist_add to %p\n",cur->prev);
287 list_add(element, cur->prev);
288 }
290 #define DOMAIN_COMPARER(name, field, comp1, comp2) \
291 int name##_comp(struct list_head* el1, struct list_head* el2) \
292 { \
293 struct sedf_vcpu_info *d1, *d2; \
294 d1 = list_entry(el1,struct sedf_vcpu_info, field); \
295 d2 = list_entry(el2,struct sedf_vcpu_info, field); \
296 if ( (comp1) == (comp2) ) \
297 return 0; \
298 if ( (comp1) < (comp2) ) \
299 return -1; \
300 else \
301 return 1; \
302 }
304 /* adds a domain to the queue of processes which wait for the beginning of the
305 next period; this list is therefore sortet by this time, which is simply
306 absol. deadline - period
307 */
308 DOMAIN_COMPARER(waitq, list, PERIOD_BEGIN(d1), PERIOD_BEGIN(d2));
309 static inline void __add_to_waitqueue_sort(struct vcpu *v)
310 {
311 ASSERT(!__task_on_queue(v));
312 PRINT(3,"Adding domain %i.%i (bop= %"PRIu64") to waitq\n",
313 v->domain->domain_id, v->vcpu_id, PERIOD_BEGIN(EDOM_INFO(v)));
314 list_insert_sort(WAITQ(v->processor), LIST(v), waitq_comp);
315 ASSERT(__task_on_queue(v));
316 }
318 /* adds a domain to the queue of processes which have started their current
319 period and are runnable (i.e. not blocked, dieing,...). The first element
320 on this list is running on the processor, if the list is empty the idle
321 task will run. As we are implementing EDF, this list is sorted by deadlines.
322 */
323 DOMAIN_COMPARER(runq, list, d1->deadl_abs, d2->deadl_abs);
324 static inline void __add_to_runqueue_sort(struct vcpu *v)
325 {
326 PRINT(3,"Adding domain %i.%i (deadl= %"PRIu64") to runq\n",
327 v->domain->domain_id, v->vcpu_id, EDOM_INFO(v)->deadl_abs);
328 list_insert_sort(RUNQ(v->processor), LIST(v), runq_comp);
329 }
332 static int sedf_init_vcpu(struct vcpu *v)
333 {
334 struct sedf_vcpu_info *inf;
336 if ( v->domain->sched_priv == NULL )
337 {
338 v->domain->sched_priv = xmalloc(struct sedf_dom_info);
339 if ( v->domain->sched_priv == NULL )
340 return -1;
341 memset(v->domain->sched_priv, 0, sizeof(struct sedf_dom_info));
342 }
344 if ( (v->sched_priv = xmalloc(struct sedf_vcpu_info)) == NULL )
345 return -1;
346 memset(v->sched_priv, 0, sizeof(struct sedf_vcpu_info));
348 inf = EDOM_INFO(v);
349 inf->vcpu = v;
351 /* Allocate per-CPU context if this is the first domain to be added. */
352 if ( unlikely(per_cpu(schedule_data, v->processor).sched_priv == NULL) )
353 {
354 per_cpu(schedule_data, v->processor).sched_priv =
355 xmalloc(struct sedf_cpu_info);
356 BUG_ON(per_cpu(schedule_data, v->processor).sched_priv == NULL);
357 memset(CPU_INFO(v->processor), 0, sizeof(*CPU_INFO(v->processor)));
358 INIT_LIST_HEAD(WAITQ(v->processor));
359 INIT_LIST_HEAD(RUNQ(v->processor));
360 INIT_LIST_HEAD(EXTRAQ(v->processor,EXTRA_PEN_Q));
361 INIT_LIST_HEAD(EXTRAQ(v->processor,EXTRA_UTIL_Q));
362 }
364 /* Every VCPU gets an equal share of extratime by default. */
365 inf->deadl_abs = 0;
366 inf->latency = 0;
367 inf->status = EXTRA_AWARE | SEDF_ASLEEP;
368 inf->extraweight = 1;
370 if ( v->domain->domain_id == 0 )
371 {
372 /* Domain0 gets 75% guaranteed (15ms every 20ms). */
373 inf->period = MILLISECS(20);
374 inf->slice = MILLISECS(15);
375 }
376 else
377 {
378 /* Best-effort extratime only. */
379 inf->period = WEIGHT_PERIOD;
380 inf->slice = 0;
381 }
383 inf->period_orig = inf->period; inf->slice_orig = inf->slice;
384 INIT_LIST_HEAD(&(inf->list));
385 INIT_LIST_HEAD(&(inf->extralist[EXTRA_PEN_Q]));
386 INIT_LIST_HEAD(&(inf->extralist[EXTRA_UTIL_Q]));
388 if ( !is_idle_vcpu(v) )
389 {
390 extraq_check(v);
391 }
392 else
393 {
394 EDOM_INFO(v)->deadl_abs = 0;
395 EDOM_INFO(v)->status &= ~SEDF_ASLEEP;
396 }
398 return 0;
399 }
401 static void sedf_destroy_domain(struct domain *d)
402 {
403 int i;
405 xfree(d->sched_priv);
407 for ( i = 0; i < MAX_VIRT_CPUS; i++ )
408 if ( d->vcpu[i] )
409 xfree(d->vcpu[i]->sched_priv);
410 }
412 /*
413 * Handles the rescheduling & bookkeeping of domains running in their
414 * guaranteed timeslice.
415 */
416 static void desched_edf_dom(s_time_t now, struct vcpu* d)
417 {
418 struct sedf_vcpu_info* inf = EDOM_INFO(d);
420 /* Current domain is running in real time mode. */
421 ASSERT(__task_on_queue(d));
423 /* Update the domain's cputime. */
424 inf->cputime += now - inf->sched_start_abs;
426 /*
427 * Scheduling decisions which don't remove the running domain from the
428 * runq.
429 */
430 if ( (inf->cputime < inf->slice) && sedf_runnable(d) )
431 return;
433 __del_from_queue(d);
435 /*
436 * Manage bookkeeping (i.e. calculate next deadline, memorise
437 * overrun-time of slice) of finished domains.
438 */
439 if ( inf->cputime >= inf->slice )
440 {
441 inf->cputime -= inf->slice;
443 if ( inf->period < inf->period_orig )
444 {
445 /* This domain runs in latency scaling or burst mode. */
446 inf->period *= 2;
447 inf->slice *= 2;
448 if ( (inf->period > inf->period_orig) ||
449 (inf->slice > inf->slice_orig) )
450 {
451 /* Reset slice and period. */
452 inf->period = inf->period_orig;
453 inf->slice = inf->slice_orig;
454 }
455 }
457 /* Set next deadline. */
458 inf->deadl_abs += inf->period;
459 }
461 /* Add a runnable domain to the waitqueue. */
462 if ( sedf_runnable(d) )
463 {
464 __add_to_waitqueue_sort(d);
465 }
466 else
467 {
468 /* We have a blocked realtime task -> remove it from exqs too. */
469 if ( extraq_on(d, EXTRA_PEN_Q) )
470 extraq_del(d, EXTRA_PEN_Q);
471 if ( extraq_on(d, EXTRA_UTIL_Q) )
472 extraq_del(d, EXTRA_UTIL_Q);
473 }
475 ASSERT(EQ(sedf_runnable(d), __task_on_queue(d)));
476 ASSERT(IMPLY(extraq_on(d, EXTRA_UTIL_Q) || extraq_on(d, EXTRA_PEN_Q),
477 sedf_runnable(d)));
478 }
481 /* Update all elements on the queues */
482 static void update_queues(
483 s_time_t now, struct list_head *runq, struct list_head *waitq)
484 {
485 struct list_head *cur, *tmp;
486 struct sedf_vcpu_info *curinf;
488 PRINT(3,"Updating waitq..\n");
490 /*
491 * Check for the first elements of the waitqueue, whether their
492 * next period has already started.
493 */
494 list_for_each_safe ( cur, tmp, waitq )
495 {
496 curinf = list_entry(cur, struct sedf_vcpu_info, list);
497 PRINT(4,"\tLooking @ dom %i.%i\n",
498 curinf->vcpu->domain->domain_id, curinf->vcpu->vcpu_id);
499 if ( PERIOD_BEGIN(curinf) > now )
500 break;
501 __del_from_queue(curinf->vcpu);
502 __add_to_runqueue_sort(curinf->vcpu);
503 }
505 PRINT(3,"Updating runq..\n");
507 /* Process the runq, find domains that are on the runq that shouldn't. */
508 list_for_each_safe ( cur, tmp, runq )
509 {
510 curinf = list_entry(cur,struct sedf_vcpu_info,list);
511 PRINT(4,"\tLooking @ dom %i.%i\n",
512 curinf->vcpu->domain->domain_id, curinf->vcpu->vcpu_id);
514 if ( unlikely(curinf->slice == 0) )
515 {
516 /* Ignore domains with empty slice. */
517 PRINT(4,"\tUpdating zero-slice domain %i.%i\n",
518 curinf->vcpu->domain->domain_id,
519 curinf->vcpu->vcpu_id);
520 __del_from_queue(curinf->vcpu);
522 /* Move them to their next period. */
523 curinf->deadl_abs += curinf->period;
525 /* Ensure that the start of the next period is in the future. */
526 if ( unlikely(PERIOD_BEGIN(curinf) < now) )
527 curinf->deadl_abs +=
528 (DIV_UP(now - PERIOD_BEGIN(curinf),
529 curinf->period)) * curinf->period;
531 /* Put them back into the queue. */
532 __add_to_waitqueue_sort(curinf->vcpu);
533 }
534 else if ( unlikely((curinf->deadl_abs < now) ||
535 (curinf->cputime > curinf->slice)) )
536 {
537 /*
538 * We missed the deadline or the slice was already finished.
539 * Might hapen because of dom_adj.
540 */
541 PRINT(4,"\tDomain %i.%i exceeded it's deadline/"
542 "slice (%"PRIu64" / %"PRIu64") now: %"PRIu64
543 " cputime: %"PRIu64"\n",
544 curinf->vcpu->domain->domain_id,
545 curinf->vcpu->vcpu_id,
546 curinf->deadl_abs, curinf->slice, now,
547 curinf->cputime);
548 __del_from_queue(curinf->vcpu);
550 /* Common case: we miss one period. */
551 curinf->deadl_abs += curinf->period;
553 /*
554 * If we are still behind: modulo arithmetic, force deadline
555 * to be in future and aligned to period borders.
556 */
557 if ( unlikely(curinf->deadl_abs < now) )
558 curinf->deadl_abs +=
559 DIV_UP(now - curinf->deadl_abs,
560 curinf->period) * curinf->period;
561 ASSERT(curinf->deadl_abs >= now);
563 /* Give a fresh slice. */
564 curinf->cputime = 0;
565 if ( PERIOD_BEGIN(curinf) > now )
566 __add_to_waitqueue_sort(curinf->vcpu);
567 else
568 __add_to_runqueue_sort(curinf->vcpu);
569 }
570 else
571 break;
572 }
574 PRINT(3,"done updating the queues\n");
575 }
578 /* removes a domain from the head of the according extraQ and
579 requeues it at a specified position:
580 round-robin extratime: end of extraQ
581 weighted ext.: insert in sorted list by score
582 if the domain is blocked / has regained its short-block-loss
583 time it is not put on any queue */
584 static void desched_extra_dom(s_time_t now, struct vcpu *d)
585 {
586 struct sedf_vcpu_info *inf = EDOM_INFO(d);
587 int i = extra_get_cur_q(inf);
588 unsigned long oldscore;
590 ASSERT(extraq_on(d, i));
592 /* Unset all running flags. */
593 inf->status &= ~(EXTRA_RUN_PEN | EXTRA_RUN_UTIL);
594 /* Fresh slice for the next run. */
595 inf->cputime = 0;
596 /* Accumulate total extratime. */
597 inf->extra_time_tot += now - inf->sched_start_abs;
598 /* Remove extradomain from head of the queue. */
599 extraq_del(d, i);
601 /* Update the score. */
602 oldscore = inf->score[i];
603 if ( i == EXTRA_PEN_Q )
604 {
605 /*domain was running in L0 extraq*/
606 /*reduce block lost, probably more sophistication here!*/
607 /*inf->short_block_lost_tot -= EXTRA_QUANTUM;*/
608 inf->short_block_lost_tot -= now - inf->sched_start_abs;
609 PRINT(3,"Domain %i.%i: Short_block_loss: %"PRIi64"\n",
610 inf->vcpu->domain->domain_id, inf->vcpu->vcpu_id,
611 inf->short_block_lost_tot);
612 #if 0
613 /*
614 * KAF: If we don't exit short-blocking state at this point
615 * domain0 can steal all CPU for up to 10 seconds before
616 * scheduling settles down (when competing against another
617 * CPU-bound domain). Doing this seems to make things behave
618 * nicely. Noone gets starved by default.
619 */
620 if ( inf->short_block_lost_tot <= 0 )
621 #endif
622 {
623 PRINT(4,"Domain %i.%i compensated short block loss!\n",
624 inf->vcpu->domain->domain_id, inf->vcpu->vcpu_id);
625 /*we have (over-)compensated our block penalty*/
626 inf->short_block_lost_tot = 0;
627 /*we don't want a place on the penalty queue anymore!*/
628 inf->status &= ~EXTRA_WANT_PEN_Q;
629 goto check_extra_queues;
630 }
632 /*we have to go again for another try in the block-extraq,
633 the score is not used incremantally here, as this is
634 already done by recalculating the block_lost*/
635 inf->score[EXTRA_PEN_Q] = (inf->period << 10) /
636 inf->short_block_lost_tot;
637 oldscore = 0;
638 }
639 else
640 {
641 /*domain was running in L1 extraq => score is inverse of
642 utilization and is used somewhat incremental!*/
643 if ( !inf->extraweight )
644 /*NB: use fixed point arithmetic with 10 bits*/
645 inf->score[EXTRA_UTIL_Q] = (inf->period << 10) /
646 inf->slice;
647 else
648 /*conversion between realtime utilisation and extrawieght:
649 full (ie 100%) utilization is equivalent to 128 extraweight*/
650 inf->score[EXTRA_UTIL_Q] = (1<<17) / inf->extraweight;
651 }
653 check_extra_queues:
654 /* Adding a runnable domain to the right queue and removing blocked ones*/
655 if ( sedf_runnable(d) )
656 {
657 /*add according to score: weighted round robin*/
658 if (((inf->status & EXTRA_AWARE) && (i == EXTRA_UTIL_Q)) ||
659 ((inf->status & EXTRA_WANT_PEN_Q) && (i == EXTRA_PEN_Q)))
660 extraq_add_sort_update(d, i, oldscore);
661 }
662 else
663 {
664 /*remove this blocked domain from the waitq!*/
665 __del_from_queue(d);
666 /*make sure that we remove a blocked domain from the other
667 extraq too*/
668 if ( i == EXTRA_PEN_Q )
669 {
670 if ( extraq_on(d, EXTRA_UTIL_Q) )
671 extraq_del(d, EXTRA_UTIL_Q);
672 }
673 else
674 {
675 if ( extraq_on(d, EXTRA_PEN_Q) )
676 extraq_del(d, EXTRA_PEN_Q);
677 }
678 }
680 ASSERT(EQ(sedf_runnable(d), __task_on_queue(d)));
681 ASSERT(IMPLY(extraq_on(d, EXTRA_UTIL_Q) || extraq_on(d, EXTRA_PEN_Q),
682 sedf_runnable(d)));
683 }
686 static struct task_slice sedf_do_extra_schedule(
687 s_time_t now, s_time_t end_xt, struct list_head *extraq[], int cpu)
688 {
689 struct task_slice ret;
690 struct sedf_vcpu_info *runinf;
691 ASSERT(end_xt > now);
693 /* Enough time left to use for extratime? */
694 if ( end_xt - now < EXTRA_QUANTUM )
695 goto return_idle;
697 if ( !list_empty(extraq[EXTRA_PEN_Q]) )
698 {
699 /*we still have elements on the level 0 extraq
700 => let those run first!*/
701 runinf = list_entry(extraq[EXTRA_PEN_Q]->next,
702 struct sedf_vcpu_info, extralist[EXTRA_PEN_Q]);
703 runinf->status |= EXTRA_RUN_PEN;
704 ret.task = runinf->vcpu;
705 ret.time = EXTRA_QUANTUM;
706 #ifdef SEDF_STATS
707 runinf->pen_extra_slices++;
708 #endif
709 }
710 else
711 {
712 if ( !list_empty(extraq[EXTRA_UTIL_Q]) )
713 {
714 /*use elements from the normal extraqueue*/
715 runinf = list_entry(extraq[EXTRA_UTIL_Q]->next,
716 struct sedf_vcpu_info,
717 extralist[EXTRA_UTIL_Q]);
718 runinf->status |= EXTRA_RUN_UTIL;
719 ret.task = runinf->vcpu;
720 ret.time = EXTRA_QUANTUM;
721 }
722 else
723 goto return_idle;
724 }
726 ASSERT(ret.time > 0);
727 ASSERT(sedf_runnable(ret.task));
728 return ret;
730 return_idle:
731 ret.task = IDLETASK(cpu);
732 ret.time = end_xt - now;
733 ASSERT(ret.time > 0);
734 ASSERT(sedf_runnable(ret.task));
735 return ret;
736 }
739 /* Main scheduling function
740 Reasons for calling this function are:
741 -timeslice for the current period used up
742 -domain on waitqueue has started it's period
743 -and various others ;) in general: determine which domain to run next*/
744 static struct task_slice sedf_do_schedule(s_time_t now)
745 {
746 int cpu = smp_processor_id();
747 struct list_head *runq = RUNQ(cpu);
748 struct list_head *waitq = WAITQ(cpu);
749 struct sedf_vcpu_info *inf = EDOM_INFO(current);
750 struct list_head *extraq[] = {
751 EXTRAQ(cpu, EXTRA_PEN_Q), EXTRAQ(cpu, EXTRA_UTIL_Q)};
752 struct sedf_vcpu_info *runinf, *waitinf;
753 struct task_slice ret;
755 /*idle tasks don't need any of the following stuf*/
756 if ( is_idle_vcpu(current) )
757 goto check_waitq;
759 /* create local state of the status of the domain, in order to avoid
760 inconsistent state during scheduling decisions, because data for
761 vcpu_runnable is not protected by the scheduling lock!*/
762 if ( !vcpu_runnable(current) )
763 inf->status |= SEDF_ASLEEP;
765 if ( inf->status & SEDF_ASLEEP )
766 inf->block_abs = now;
768 if ( unlikely(extra_runs(inf)) )
769 {
770 /*special treatment of domains running in extra time*/
771 desched_extra_dom(now, current);
772 }
773 else
774 {
775 desched_edf_dom(now, current);
776 }
777 check_waitq:
778 update_queues(now, runq, waitq);
780 /*now simply pick the first domain from the runqueue, which has the
781 earliest deadline, because the list is sorted*/
783 if ( !list_empty(runq) )
784 {
785 runinf = list_entry(runq->next,struct sedf_vcpu_info,list);
786 ret.task = runinf->vcpu;
787 if ( !list_empty(waitq) )
788 {
789 waitinf = list_entry(waitq->next,
790 struct sedf_vcpu_info,list);
791 /*rerun scheduler, when scheduled domain reaches it's
792 end of slice or the first domain from the waitqueue
793 gets ready*/
794 ret.time = MIN(now + runinf->slice - runinf->cputime,
795 PERIOD_BEGIN(waitinf)) - now;
796 }
797 else
798 {
799 ret.time = runinf->slice - runinf->cputime;
800 }
801 CHECK(ret.time > 0);
802 goto sched_done;
803 }
805 if ( !list_empty(waitq) )
806 {
807 waitinf = list_entry(waitq->next,struct sedf_vcpu_info, list);
808 /*we could not find any suitable domain
809 => look for domains that are aware of extratime*/
810 ret = sedf_do_extra_schedule(now, PERIOD_BEGIN(waitinf),
811 extraq, cpu);
812 CHECK(ret.time > 0);
813 }
814 else
815 {
816 /*this could probably never happen, but one never knows...*/
817 /*it can... imagine a second CPU, which is pure scifi ATM,
818 but one never knows ;)*/
819 ret.task = IDLETASK(cpu);
820 ret.time = SECONDS(1);
821 }
823 sched_done:
824 /*TODO: Do something USEFUL when this happens and find out, why it
825 still can happen!!!*/
826 if ( ret.time < 0)
827 {
828 printk("Ouch! We are seriously BEHIND schedule! %"PRIi64"\n",
829 ret.time);
830 ret.time = EXTRA_QUANTUM;
831 }
833 EDOM_INFO(ret.task)->sched_start_abs = now;
834 CHECK(ret.time > 0);
835 ASSERT(sedf_runnable(ret.task));
836 CPU_INFO(cpu)->current_slice_expires = now + ret.time;
837 return ret;
838 }
841 static void sedf_sleep(struct vcpu *d)
842 {
843 PRINT(2,"sedf_sleep was called, domain-id %i.%i\n",
844 d->domain->domain_id, d->vcpu_id);
846 if ( is_idle_vcpu(d) )
847 return;
849 EDOM_INFO(d)->status |= SEDF_ASLEEP;
851 if ( per_cpu(schedule_data, d->processor).curr == d )
852 {
853 cpu_raise_softirq(d->processor, SCHEDULE_SOFTIRQ);
854 }
855 else
856 {
857 if ( __task_on_queue(d) )
858 __del_from_queue(d);
859 if ( extraq_on(d, EXTRA_UTIL_Q) )
860 extraq_del(d, EXTRA_UTIL_Q);
861 if ( extraq_on(d, EXTRA_PEN_Q) )
862 extraq_del(d, EXTRA_PEN_Q);
863 }
864 }
867 /* This function wakes up a domain, i.e. moves them into the waitqueue
868 * things to mention are: admission control is taking place nowhere at
869 * the moment, so we can't be sure, whether it is safe to wake the domain
870 * up at all. Anyway, even if it is safe (total cpu usage <=100%) there are
871 * some considerations on when to allow the domain to wake up and have it's
872 * first deadline...
873 * I detected 3 cases, which could describe the possible behaviour of the
874 * scheduler,
875 * and I'll try to make them more clear:
876 *
877 * 1. Very conservative
878 * -when a blocked domain unblocks, it is allowed to start execution at
879 * the beginning of the next complete period
880 * (D..deadline, R..running, B..blocking/sleeping, U..unblocking/waking up
881 *
882 * DRRB_____D__U_____DRRRRR___D________ ...
883 *
884 * -this causes the domain to miss a period (and a deadlline)
885 * -doesn't disturb the schedule at all
886 * -deadlines keep occuring isochronous
887 *
888 * 2. Conservative Part 1: Short Unblocking
889 * -when a domain unblocks in the same period as it was blocked it
890 * unblocks and may consume the rest of it's original time-slice minus
891 * the time it was blocked
892 * (assume period=9, slice=5)
893 *
894 * DRB_UR___DRRRRR___D...
895 *
896 * -this also doesn't disturb scheduling, but might lead to the fact, that
897 * the domain can't finish it's workload in the period
898 * -in addition to that the domain can be treated prioritised when
899 * extratime is available
900 * -addition: experiments have shown that this may have a HUGE impact on
901 * performance of other domains, becaus it can lead to excessive context
902 * switches
903 *
904 * Part2: Long Unblocking
905 * Part 2a
906 * -it is obvious that such accounting of block time, applied when
907 * unblocking is happening in later periods, works fine aswell
908 * -the domain is treated as if it would have been running since the start
909 * of its new period
910 *
911 * DRB______D___UR___D...
912 *
913 * Part 2b
914 * -if one needs the full slice in the next period, it is necessary to
915 * treat the unblocking time as the start of the new period, i.e. move
916 * the deadline further back (later)
917 * -this doesn't disturb scheduling as well, because for EDF periods can
918 * be treated as minimal inter-release times and scheduling stays
919 * correct, when deadlines are kept relative to the time the process
920 * unblocks
921 *
922 * DRB______D___URRRR___D...<prev [Thread] next>
923 * (D) <- old deadline was here
924 * -problem: deadlines don't occur isochronous anymore
925 * Part 2c (Improved Atropos design)
926 * -when a domain unblocks it is given a very short period (=latency hint)
927 * and slice length scaled accordingly
928 * -both rise again to the original value (e.g. get doubled every period)
929 *
930 * 3. Unconservative (i.e. incorrect)
931 * -to boost the performance of I/O dependent domains it would be possible
932 * to put the domain into the runnable queue immediately, and let it run
933 * for the remainder of the slice of the current period
934 * (or even worse: allocate a new full slice for the domain)
935 * -either behaviour can lead to missed deadlines in other domains as
936 * opposed to approaches 1,2a,2b
937 */
938 static void unblock_short_extra_support(
939 struct sedf_vcpu_info* inf, s_time_t now)
940 {
941 /*this unblocking scheme tries to support the domain, by assigning it
942 a priority in extratime distribution according to the loss of time
943 in this slice due to blocking*/
944 s_time_t pen;
946 /*no more realtime execution in this period!*/
947 inf->deadl_abs += inf->period;
948 if ( likely(inf->block_abs) )
949 {
950 //treat blocked time as consumed by the domain*/
951 /*inf->cputime += now - inf->block_abs;*/
952 /*penalty is time the domain would have
953 had if it continued to run */
954 pen = (inf->slice - inf->cputime);
955 if ( pen < 0 )
956 pen = 0;
957 /*accumulate all penalties over the periods*/
958 /*inf->short_block_lost_tot += pen;*/
959 /*set penalty to the current value*/
960 inf->short_block_lost_tot = pen;
961 /*not sure which one is better.. but seems to work well...*/
963 if ( inf->short_block_lost_tot )
964 {
965 inf->score[0] = (inf->period << 10) /
966 inf->short_block_lost_tot;
967 #ifdef SEDF_STATS
968 inf->pen_extra_blocks++;
969 #endif
970 if ( extraq_on(inf->vcpu, EXTRA_PEN_Q) )
971 /*remove domain for possible resorting!*/
972 extraq_del(inf->vcpu, EXTRA_PEN_Q);
973 else
974 /*remember that we want to be on the penalty q
975 so that we can continue when we (un-)block
976 in penalty-extratime*/
977 inf->status |= EXTRA_WANT_PEN_Q;
979 /*(re-)add domain to the penalty extraq*/
980 extraq_add_sort_update(inf->vcpu, EXTRA_PEN_Q, 0);
981 }
982 }
984 /*give it a fresh slice in the next period!*/
985 inf->cputime = 0;
986 }
989 static void unblock_long_cons_b(struct sedf_vcpu_info* inf,s_time_t now)
990 {
991 /*Conservative 2b*/
992 /*Treat the unblocking time as a start of a new period */
993 inf->deadl_abs = now + inf->period;
994 inf->cputime = 0;
995 }
998 #define DOMAIN_EDF 1
999 #define DOMAIN_EXTRA_PEN 2
1000 #define DOMAIN_EXTRA_UTIL 3
1001 #define DOMAIN_IDLE 4
1002 static inline int get_run_type(struct vcpu* d)
1004 struct sedf_vcpu_info* inf = EDOM_INFO(d);
1005 if (is_idle_vcpu(d))
1006 return DOMAIN_IDLE;
1007 if (inf->status & EXTRA_RUN_PEN)
1008 return DOMAIN_EXTRA_PEN;
1009 if (inf->status & EXTRA_RUN_UTIL)
1010 return DOMAIN_EXTRA_UTIL;
1011 return DOMAIN_EDF;
1015 /*Compares two domains in the relation of whether the one is allowed to
1016 interrupt the others execution.
1017 It returns true (!=0) if a switch to the other domain is good.
1018 Current Priority scheme is as follows:
1019 EDF > L0 (penalty based) extra-time >
1020 L1 (utilization) extra-time > idle-domain
1021 In the same class priorities are assigned as following:
1022 EDF: early deadline > late deadline
1023 L0 extra-time: lower score > higher score*/
1024 static inline int should_switch(struct vcpu *cur,
1025 struct vcpu *other,
1026 s_time_t now)
1028 struct sedf_vcpu_info *cur_inf, *other_inf;
1029 cur_inf = EDOM_INFO(cur);
1030 other_inf = EDOM_INFO(other);
1032 /* Check whether we need to make an earlier scheduling decision. */
1033 if ( PERIOD_BEGIN(other_inf) <
1034 CPU_INFO(other->processor)->current_slice_expires )
1035 return 1;
1037 /* No timing-based switches need to be taken into account here. */
1038 switch ( get_run_type(cur) )
1040 case DOMAIN_EDF:
1041 /* Do not interrupt a running EDF domain. */
1042 return 0;
1043 case DOMAIN_EXTRA_PEN:
1044 /* Check whether we also want the L0 ex-q with lower score. */
1045 return ((other_inf->status & EXTRA_WANT_PEN_Q) &&
1046 (other_inf->score[EXTRA_PEN_Q] <
1047 cur_inf->score[EXTRA_PEN_Q]));
1048 case DOMAIN_EXTRA_UTIL:
1049 /* Check whether we want the L0 extraq. Don't
1050 * switch if both domains want L1 extraq.
1051 */
1052 return !!(other_inf->status & EXTRA_WANT_PEN_Q);
1053 case DOMAIN_IDLE:
1054 return 1;
1057 return 1;
1060 void sedf_wake(struct vcpu *d)
1062 s_time_t now = NOW();
1063 struct sedf_vcpu_info* inf = EDOM_INFO(d);
1065 PRINT(3, "sedf_wake was called, domain-id %i.%i\n",d->domain->domain_id,
1066 d->vcpu_id);
1068 if ( unlikely(is_idle_vcpu(d)) )
1069 return;
1071 if ( unlikely(__task_on_queue(d)) )
1073 PRINT(3,"\tdomain %i.%i is already in some queue\n",
1074 d->domain->domain_id, d->vcpu_id);
1075 return;
1078 ASSERT(!sedf_runnable(d));
1079 inf->status &= ~SEDF_ASLEEP;
1080 ASSERT(!extraq_on(d, EXTRA_UTIL_Q));
1081 ASSERT(!extraq_on(d, EXTRA_PEN_Q));
1083 if ( unlikely(inf->deadl_abs == 0) )
1085 /*initial setup of the deadline*/
1086 inf->deadl_abs = now + inf->slice;
1089 PRINT(3, "waking up domain %i.%i (deadl= %"PRIu64" period= %"PRIu64
1090 "now= %"PRIu64")\n",
1091 d->domain->domain_id, d->vcpu_id, inf->deadl_abs, inf->period, now);
1093 #ifdef SEDF_STATS
1094 inf->block_tot++;
1095 #endif
1097 if ( unlikely(now < PERIOD_BEGIN(inf)) )
1099 PRINT(4,"extratime unblock\n");
1100 /* unblocking in extra-time! */
1101 if ( inf->status & EXTRA_WANT_PEN_Q )
1103 /*we have a domain that wants compensation
1104 for block penalty and did just block in
1105 its compensation time. Give it another
1106 chance!*/
1107 extraq_add_sort_update(d, EXTRA_PEN_Q, 0);
1109 extraq_check_add_unblocked(d, 0);
1111 else
1113 if ( now < inf->deadl_abs )
1115 PRINT(4,"short unblocking\n");
1116 /*short blocking*/
1117 #ifdef SEDF_STATS
1118 inf->short_block_tot++;
1119 #endif
1120 unblock_short_extra_support(inf, now);
1122 extraq_check_add_unblocked(d, 1);
1124 else
1126 PRINT(4,"long unblocking\n");
1127 /*long unblocking*/
1128 #ifdef SEDF_STATS
1129 inf->long_block_tot++;
1130 #endif
1131 unblock_long_cons_b(inf, now);
1133 extraq_check_add_unblocked(d, 1);
1137 PRINT(3, "woke up domain %i.%i (deadl= %"PRIu64" period= %"PRIu64
1138 "now= %"PRIu64")\n",
1139 d->domain->domain_id, d->vcpu_id, inf->deadl_abs,
1140 inf->period, now);
1142 if ( PERIOD_BEGIN(inf) > now )
1144 __add_to_waitqueue_sort(d);
1145 PRINT(3,"added to waitq\n");
1147 else
1149 __add_to_runqueue_sort(d);
1150 PRINT(3,"added to runq\n");
1153 #ifdef SEDF_STATS
1154 /*do some statistics here...*/
1155 if ( inf->block_abs != 0 )
1157 inf->block_time_tot += now - inf->block_abs;
1158 inf->penalty_time_tot +=
1159 PERIOD_BEGIN(inf) + inf->cputime - inf->block_abs;
1161 #endif
1163 /*sanity check: make sure each extra-aware domain IS on the util-q!*/
1164 ASSERT(IMPLY(inf->status & EXTRA_AWARE, extraq_on(d, EXTRA_UTIL_Q)));
1165 ASSERT(__task_on_queue(d));
1166 /*check whether the awakened task needs to invoke the do_schedule
1167 routine. Try to avoid unnecessary runs but:
1168 Save approximation: Always switch to scheduler!*/
1169 ASSERT(d->processor >= 0);
1170 ASSERT(d->processor < NR_CPUS);
1171 ASSERT(per_cpu(schedule_data, d->processor).curr);
1173 if ( should_switch(per_cpu(schedule_data, d->processor).curr, d, now) )
1174 cpu_raise_softirq(d->processor, SCHEDULE_SOFTIRQ);
1178 static int sedf_set_affinity(struct vcpu *v, cpumask_t *affinity)
1180 if ( v == current )
1181 return cpu_isset(v->processor, *affinity) ? 0 : -EBUSY;
1183 vcpu_pause(v);
1184 v->cpu_affinity = *affinity;
1185 v->processor = first_cpu(v->cpu_affinity);
1186 vcpu_unpause(v);
1188 return 0;
1192 /* Print a lot of useful information about a domains in the system */
1193 static void sedf_dump_domain(struct vcpu *d)
1195 printk("%i.%i has=%c ", d->domain->domain_id, d->vcpu_id,
1196 test_bit(_VCPUF_running, &d->vcpu_flags) ? 'T':'F');
1197 printk("p=%"PRIu64" sl=%"PRIu64" ddl=%"PRIu64" w=%hu"
1198 " sc=%i xtr(%s)=%"PRIu64" ew=%hu",
1199 EDOM_INFO(d)->period, EDOM_INFO(d)->slice, EDOM_INFO(d)->deadl_abs,
1200 EDOM_INFO(d)->weight,
1201 EDOM_INFO(d)->score[EXTRA_UTIL_Q],
1202 (EDOM_INFO(d)->status & EXTRA_AWARE) ? "yes" : "no",
1203 EDOM_INFO(d)->extra_time_tot, EDOM_INFO(d)->extraweight);
1205 #ifdef SEDF_STATS
1206 if ( EDOM_INFO(d)->block_time_tot != 0 )
1207 printf(" pen=%"PRIu64"%%", (EDOM_INFO(d)->penalty_time_tot * 100) /
1208 EDOM_INFO(d)->block_time_tot);
1209 if ( EDOM_INFO(d)->block_tot != 0 )
1210 printf("\n blks=%u sh=%u (%u%%) (shc=%u (%u%%) shex=%i "\
1211 "shexsl=%i) l=%u (%u%%) avg: b=%"PRIu64" p=%"PRIu64"",
1212 EDOM_INFO(d)->block_tot, EDOM_INFO(d)->short_block_tot,
1213 (EDOM_INFO(d)->short_block_tot * 100)
1214 / EDOM_INFO(d)->block_tot, EDOM_INFO(d)->short_cont,
1215 (EDOM_INFO(d)->short_cont * 100) / EDOM_INFO(d)->block_tot,
1216 EDOM_INFO(d)->pen_extra_blocks,
1217 EDOM_INFO(d)->pen_extra_slices,
1218 EDOM_INFO(d)->long_block_tot,
1219 (EDOM_INFO(d)->long_block_tot * 100) / EDOM_INFO(d)->block_tot,
1220 (EDOM_INFO(d)->block_time_tot) / EDOM_INFO(d)->block_tot,
1221 (EDOM_INFO(d)->penalty_time_tot) / EDOM_INFO(d)->block_tot);
1222 #endif
1223 printf("\n");
1227 /* dumps all domains on hte specified cpu */
1228 static void sedf_dump_cpu_state(int i)
1230 struct list_head *list, *queue, *tmp;
1231 struct sedf_vcpu_info *d_inf;
1232 struct domain *d;
1233 struct vcpu *ed;
1234 int loop = 0;
1236 printk("now=%"PRIu64"\n",NOW());
1237 queue = RUNQ(i);
1238 printk("RUNQ rq %lx n: %lx, p: %lx\n", (unsigned long)queue,
1239 (unsigned long) queue->next, (unsigned long) queue->prev);
1240 list_for_each_safe ( list, tmp, queue )
1242 printk("%3d: ",loop++);
1243 d_inf = list_entry(list, struct sedf_vcpu_info, list);
1244 sedf_dump_domain(d_inf->vcpu);
1247 queue = WAITQ(i); loop = 0;
1248 printk("\nWAITQ rq %lx n: %lx, p: %lx\n", (unsigned long)queue,
1249 (unsigned long) queue->next, (unsigned long) queue->prev);
1250 list_for_each_safe ( list, tmp, queue )
1252 printk("%3d: ",loop++);
1253 d_inf = list_entry(list, struct sedf_vcpu_info, list);
1254 sedf_dump_domain(d_inf->vcpu);
1257 queue = EXTRAQ(i,EXTRA_PEN_Q); loop = 0;
1258 printk("\nEXTRAQ (penalty) rq %lx n: %lx, p: %lx\n",
1259 (unsigned long)queue, (unsigned long) queue->next,
1260 (unsigned long) queue->prev);
1261 list_for_each_safe ( list, tmp, queue )
1263 d_inf = list_entry(list, struct sedf_vcpu_info,
1264 extralist[EXTRA_PEN_Q]);
1265 printk("%3d: ",loop++);
1266 sedf_dump_domain(d_inf->vcpu);
1269 queue = EXTRAQ(i,EXTRA_UTIL_Q); loop = 0;
1270 printk("\nEXTRAQ (utilization) rq %lx n: %lx, p: %lx\n",
1271 (unsigned long)queue, (unsigned long) queue->next,
1272 (unsigned long) queue->prev);
1273 list_for_each_safe ( list, tmp, queue )
1275 d_inf = list_entry(list, struct sedf_vcpu_info,
1276 extralist[EXTRA_UTIL_Q]);
1277 printk("%3d: ",loop++);
1278 sedf_dump_domain(d_inf->vcpu);
1281 loop = 0;
1282 printk("\nnot on Q\n");
1284 for_each_domain ( d )
1286 for_each_vcpu(d, ed)
1288 if ( !__task_on_queue(ed) && (ed->processor == i) )
1290 printk("%3d: ",loop++);
1291 sedf_dump_domain(ed);
1298 /* Adjusts periods and slices of the domains accordingly to their weights. */
1299 static int sedf_adjust_weights(struct sched_adjdom_cmd *cmd)
1301 struct vcpu *p;
1302 struct domain *d;
1303 int sumw[NR_CPUS];
1304 s_time_t sumt[NR_CPUS];
1305 int cpu;
1307 for ( cpu = 0; cpu < NR_CPUS; cpu++ )
1309 sumw[cpu] = 0;
1310 sumt[cpu] = 0;
1313 /* Sum across all weights. */
1314 for_each_domain( d )
1316 for_each_vcpu( d, p )
1318 if ( EDOM_INFO(p)->weight )
1320 sumw[p->processor] += EDOM_INFO(p)->weight;
1322 else
1324 /*don't modify domains who don't have a weight, but sum
1325 up the time they need, projected to a WEIGHT_PERIOD,
1326 so that this time is not given to the weight-driven
1327 domains*/
1328 /*check for overflows*/
1329 ASSERT((WEIGHT_PERIOD < ULONG_MAX)
1330 && (EDOM_INFO(p)->slice_orig < ULONG_MAX));
1331 sumt[p->processor] +=
1332 (WEIGHT_PERIOD * EDOM_INFO(p)->slice_orig) /
1333 EDOM_INFO(p)->period_orig;
1338 /* Adjust all slices (and periods) to the new weight. */
1339 for_each_domain( d )
1341 for_each_vcpu ( d, p )
1343 if ( EDOM_INFO(p)->weight )
1345 EDOM_INFO(p)->period_orig =
1346 EDOM_INFO(p)->period = WEIGHT_PERIOD;
1347 EDOM_INFO(p)->slice_orig =
1348 EDOM_INFO(p)->slice =
1349 (EDOM_INFO(p)->weight *
1350 (WEIGHT_PERIOD - WEIGHT_SAFETY - sumt[p->processor])) /
1351 sumw[p->processor];
1356 return 0;
1360 /* set or fetch domain scheduling parameters */
1361 static int sedf_adjdom(struct domain *p, struct sched_adjdom_cmd *cmd)
1363 struct vcpu *v;
1365 PRINT(2,"sedf_adjdom was called, domain-id %i new period %"PRIu64" "
1366 "new slice %"PRIu64"\nlatency %"PRIu64" extra:%s\n",
1367 p->domain_id, cmd->u.sedf.period, cmd->u.sedf.slice,
1368 cmd->u.sedf.latency, (cmd->u.sedf.extratime)?"yes":"no");
1370 if ( cmd->direction == SCHED_INFO_PUT )
1372 /* Check for sane parameters. */
1373 if ( !cmd->u.sedf.period && !cmd->u.sedf.weight )
1374 return -EINVAL;
1375 if ( cmd->u.sedf.weight )
1377 if ( (cmd->u.sedf.extratime & EXTRA_AWARE) &&
1378 (!cmd->u.sedf.period) )
1380 /* Weight-driven domains with extratime only. */
1381 for_each_vcpu ( p, v )
1383 EDOM_INFO(v)->extraweight = cmd->u.sedf.weight;
1384 EDOM_INFO(v)->weight = 0;
1385 EDOM_INFO(v)->slice = 0;
1386 EDOM_INFO(v)->period = WEIGHT_PERIOD;
1389 else
1391 /* Weight-driven domains with real-time execution. */
1392 for_each_vcpu ( p, v )
1393 EDOM_INFO(v)->weight = cmd->u.sedf.weight;
1396 else
1398 /* Time-driven domains. */
1399 for_each_vcpu ( p, v )
1401 /*
1402 * Sanity checking: note that disabling extra weight requires
1403 * that we set a non-zero slice.
1404 */
1405 if ( (cmd->u.sedf.period > PERIOD_MAX) ||
1406 (cmd->u.sedf.period < PERIOD_MIN) ||
1407 (cmd->u.sedf.slice > cmd->u.sedf.period) ||
1408 (cmd->u.sedf.slice < SLICE_MIN) )
1409 return -EINVAL;
1410 EDOM_INFO(v)->weight = 0;
1411 EDOM_INFO(v)->extraweight = 0;
1412 EDOM_INFO(v)->period_orig =
1413 EDOM_INFO(v)->period = cmd->u.sedf.period;
1414 EDOM_INFO(v)->slice_orig =
1415 EDOM_INFO(v)->slice = cmd->u.sedf.slice;
1419 if ( sedf_adjust_weights(cmd) )
1420 return -EINVAL;
1422 for_each_vcpu ( p, v )
1424 EDOM_INFO(v)->status =
1425 (EDOM_INFO(v)->status &
1426 ~EXTRA_AWARE) | (cmd->u.sedf.extratime & EXTRA_AWARE);
1427 EDOM_INFO(v)->latency = cmd->u.sedf.latency;
1428 extraq_check(v);
1431 else if ( cmd->direction == SCHED_INFO_GET )
1433 if ( p->vcpu[0] == NULL )
1434 return -EINVAL;
1435 cmd->u.sedf.period = EDOM_INFO(p->vcpu[0])->period;
1436 cmd->u.sedf.slice = EDOM_INFO(p->vcpu[0])->slice;
1437 cmd->u.sedf.extratime = EDOM_INFO(p->vcpu[0])->status & EXTRA_AWARE;
1438 cmd->u.sedf.latency = EDOM_INFO(p->vcpu[0])->latency;
1439 cmd->u.sedf.weight = EDOM_INFO(p->vcpu[0])->weight;
1442 PRINT(2,"sedf_adjdom_finished\n");
1443 return 0;
1446 struct scheduler sched_sedf_def = {
1447 .name = "Simple EDF Scheduler",
1448 .opt_name = "sedf",
1449 .sched_id = SCHED_SEDF,
1451 .init_vcpu = sedf_init_vcpu,
1452 .destroy_domain = sedf_destroy_domain,
1454 .do_schedule = sedf_do_schedule,
1455 .dump_cpu_state = sedf_dump_cpu_state,
1456 .sleep = sedf_sleep,
1457 .wake = sedf_wake,
1458 .adjdom = sedf_adjdom,
1459 .set_affinity = sedf_set_affinity
1460 };
1462 /*
1463 * Local variables:
1464 * mode: C
1465 * c-set-style: "BSD"
1466 * c-basic-offset: 4
1467 * tab-width: 4
1468 * indent-tabs-mode: nil
1469 * End:
1470 */