ia64/xen-unstable

view xen/common/sched_sedf.c @ 6538:84ee014ebd41

Merge xen-vtx-unstable.hg
author adsharma@los-vmm.sc.intel.com
date Wed Aug 17 12:34:38 2005 -0800 (2005-08-17)
parents 23979fb12c49 f294acb25858
children 99914b54f7bf
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/ac_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 #define IMPLY(a, b) (!(a) || (b))
61 #define EQ(a, b) ((!!(a)) == (!!(b)))
64 struct sedf_dom_info {
65 struct domain *domain;
66 };
67 struct sedf_vcpu_info
68 {
69 struct vcpu *vcpu;
70 struct list_head list;
71 struct list_head extralist[2];
73 /*Parameters for EDF*/
74 s_time_t period; /*=(relative deadline)*/
75 s_time_t slice; /*=worst case execution time*/
77 /*Advaced Parameters*/
78 /*Latency Scaling*/
79 s_time_t period_orig;
80 s_time_t slice_orig;
81 s_time_t latency;
83 /*status of domain*/
84 int status;
85 /*weights for "Scheduling for beginners/ lazy/ etc." ;)*/
86 short weight;
87 short extraweight;
88 /*Bookkeeping*/
89 s_time_t deadl_abs;
90 s_time_t sched_start_abs;
91 s_time_t cputime;
92 /* times the domain un-/blocked */
93 s_time_t block_abs;
94 s_time_t unblock_abs;
96 /*scores for {util, block penalty}-weighted extratime distribution*/
97 int score[2];
98 s_time_t short_block_lost_tot;
100 /*Statistics*/
101 s_time_t extra_time_tot;
103 #ifdef SEDF_STATS
104 s_time_t block_time_tot;
105 s_time_t penalty_time_tot;
106 int block_tot;
107 int short_block_tot;
108 int long_block_tot;
109 int short_cont;
110 int pen_extra_blocks;
111 int pen_extra_slices;
112 #endif
113 };
115 struct sedf_cpu_info {
116 struct list_head runnableq;
117 struct list_head waitq;
118 struct list_head extraq[2];
119 s_time_t current_slice_expires;
120 };
122 #define EDOM_INFO(d) ((struct sedf_vcpu_info *)((d)->sched_priv))
123 #define CPU_INFO(cpu) ((struct sedf_cpu_info *)schedule_data[cpu].sched_priv)
124 #define LIST(d) (&EDOM_INFO(d)->list)
125 #define EXTRALIST(d,i) (&(EDOM_INFO(d)->extralist[i]))
126 #define RUNQ(cpu) (&CPU_INFO(cpu)->runnableq)
127 #define WAITQ(cpu) (&CPU_INFO(cpu)->waitq)
128 #define EXTRAQ(cpu,i) (&(CPU_INFO(cpu)->extraq[i]))
129 #define IDLETASK(cpu) ((struct vcpu *)schedule_data[cpu].idle)
131 #define PERIOD_BEGIN(inf) ((inf)->deadl_abs - (inf)->period)
133 #define MIN(x,y) (((x)<(y))?(x):(y))
134 #define DIV_UP(x,y) (((x) + (y) - 1) / y)
136 #define extra_runs(inf) ((inf->status) & 6)
137 #define extra_get_cur_q(inf) (((inf->status & 6) >> 1)-1)
138 #define sedf_runnable(edom) (!(EDOM_INFO(edom)->status & SEDF_ASLEEP))
141 static void sedf_dump_cpu_state(int i);
143 static inline int extraq_on(struct vcpu *d, int i) {
144 return ((EXTRALIST(d,i)->next != NULL) &&
145 (EXTRALIST(d,i)->next != EXTRALIST(d,i)));
146 }
148 static inline void extraq_add_head(struct vcpu *d, int i)
149 {
150 list_add(EXTRALIST(d,i), EXTRAQ(d->processor,i));
151 ASSERT(extraq_on(d, i));
152 }
154 static inline void extraq_add_tail(struct vcpu *d, int i)
155 {
156 list_add_tail(EXTRALIST(d,i), EXTRAQ(d->processor,i));
157 ASSERT(extraq_on(d, i));
158 }
160 static inline void extraq_del(struct vcpu *d, int i)
161 {
162 struct list_head *list = EXTRALIST(d,i);
163 ASSERT(extraq_on(d,i));
164 PRINT(3, "Removing domain %i.%i from L%i extraq\n", d->domain->domain_id,
165 d->vcpu_id, i);
166 list_del(list);
167 list->next = NULL;
168 ASSERT(!extraq_on(d, i));
169 }
171 /* adds a domain to the queue of processes which are aware of extra time. List
172 is sorted by score, where a lower score means higher priority for an extra
173 slice. It also updates the score, by simply subtracting a fixed value from
174 each entry, in order to avoid overflow. The algorithm works by simply
175 charging each domain that recieved extratime with an inverse of its weight.
176 */
177 static inline void extraq_add_sort_update(struct vcpu *d, int i, int sub) {
178 struct list_head *cur;
179 struct sedf_vcpu_info *curinf;
181 ASSERT(!extraq_on(d,i));
182 PRINT(3, "Adding domain %i.%i (score= %i, short_pen= %"PRIi64")"
183 " to L%i extraq\n",
184 d->domain->domain_id, d->vcpu_id, EDOM_INFO(d)->score[i],
185 EDOM_INFO(d)->short_block_lost_tot, i);
186 /*iterate through all elements to find our "hole" and on our way
187 update all the other scores*/
188 list_for_each(cur,EXTRAQ(d->processor,i)){
189 curinf = list_entry(cur,struct sedf_vcpu_info,extralist[i]);
190 curinf->score[i] -= sub;
191 if (EDOM_INFO(d)->score[i] < curinf->score[i])
192 break;
193 else
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 }
198 /*cur now contains the element, before which we'll enqueue*/
199 PRINT(3, "\tlist_add to %p\n", cur->prev);
200 list_add(EXTRALIST(d,i),cur->prev);
202 /*continue updating the extraq*/
203 if ((cur != EXTRAQ(d->processor,i)) && sub)
204 for (cur = cur->next; cur != EXTRAQ(d->processor,i);
205 cur = cur-> next) {
206 curinf = list_entry(cur,struct sedf_vcpu_info,
207 extralist[i]);
208 curinf->score[i] -= sub;
209 PRINT(4, "\tupdating domain %i.%i (score= %u)\n",
210 curinf->vcpu->domain->domain_id,
211 curinf->vcpu->vcpu_id, curinf->score[i]);
212 }
213 ASSERT(extraq_on(d,i));
214 }
215 static inline void extraq_check(struct vcpu *d) {
216 if (extraq_on(d, EXTRA_UTIL_Q)) {
217 PRINT(2,"Dom %i.%i is on L1 extraQ\n",d->domain->domain_id, d->vcpu_id);
218 if (!(EDOM_INFO(d)->status & EXTRA_AWARE) &&
219 !extra_runs(EDOM_INFO(d))) {
220 extraq_del(d, EXTRA_UTIL_Q);
221 PRINT(2,"Removed dom %i.%i from L1 extraQ\n",
222 d->domain->domain_id, d->vcpu_id);
223 }
224 } else {
225 PRINT(2,"Dom %i.%i is NOT on L1 extraQ\n",d->domain->domain_id,
226 d->vcpu_id);
227 if ((EDOM_INFO(d)->status & EXTRA_AWARE) && sedf_runnable(d))
228 {
229 #if (EXTRA == EXTRA_ROUNDR)
230 extraq_add_tail(d, EXTRA_UTIL_Q);
231 #elif (EXTRA == EXTRA_SLICE_WEIGHT || \
232 EXTRA == EXTRA_BLOCK_WEIGHT)
233 extraq_add_sort_update(d, EXTRA_UTIL_Q, 0);
234 #elif
235 ;
236 #endif
237 PRINT(2,"Added dom %i.%i to L1 extraQ\n",d->domain->domain_id,
238 d->vcpu_id);
239 }
240 }
241 }
243 static inline void extraq_check_add_unblocked(struct vcpu *d,
244 int priority) {
245 struct sedf_vcpu_info *inf = EDOM_INFO(d);
246 if (inf->status & EXTRA_AWARE)
247 #if (EXTRA == EXTRA_ROUNDR)
248 if (priority)
249 extraq_add_head(d,EXTRA_UTIL_Q);
250 else
251 extraq_add_tail(d,EXTRA_UTIL_Q);
252 #elif (EXTRA == EXTRA_SLICE_WEIGHT \
253 || EXTRA == EXTRA_BLOCK_WEIGHT)
254 /*put in on the weighted extraq,
255 without updating any scores*/
256 extraq_add_sort_update(d, EXTRA_UTIL_Q, 0);
257 #else
258 ;
259 #endif
260 }
262 static inline int __task_on_queue(struct vcpu *d) {
263 return (((LIST(d))->next != NULL) && (LIST(d)->next != LIST(d)));
264 }
265 static inline void __del_from_queue(struct vcpu *d)
266 {
267 struct list_head *list = LIST(d);
268 ASSERT(__task_on_queue(d));
269 PRINT(3,"Removing domain %i.%i (bop= %"PRIu64") from runq/waitq\n",
270 d->domain->domain_id, d->vcpu_id, PERIOD_BEGIN(EDOM_INFO(d)));
271 list_del(list);
272 list->next = NULL;
273 ASSERT(!__task_on_queue(d));
274 }
276 typedef int(*list_comparer)(struct list_head* el1, struct list_head* el2);
278 static inline void list_insert_sort(struct list_head *list,
279 struct list_head *element, list_comparer comp) {
280 struct list_head *cur;
281 /*iterate through all elements to find our "hole"*/
282 list_for_each(cur,list){
283 if (comp(element, cur) < 0)
284 break;
285 }
286 /*cur now contains the element, before which we'll enqueue*/
287 PRINT(3,"\tlist_add to %p\n",cur->prev);
288 list_add(element, cur->prev);
289 }
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 }
303 /* adds a domain to the queue of processes which wait for the beginning of the
304 next period; this list is therefore sortet by this time, which is simply
305 absol. deadline - period
306 */
307 DOMAIN_COMPARER(waitq, list, PERIOD_BEGIN(d1), PERIOD_BEGIN(d2))
308 static inline void __add_to_waitqueue_sort(struct vcpu *d) {
309 ASSERT(!__task_on_queue(d));
310 PRINT(3,"Adding domain %i.%i (bop= %"PRIu64") to waitq\n",
311 d->domain->domain_id, d->vcpu_id, PERIOD_BEGIN(EDOM_INFO(d)));
312 list_insert_sort(WAITQ(d->processor), LIST(d), waitq_comp);
313 ASSERT(__task_on_queue(d));
314 }
316 /* adds a domain to the queue of processes which have started their current
317 period and are runnable (i.e. not blocked, dieing,...). The first element
318 on this list is running on the processor, if the list is empty the idle
319 task will run. As we are implementing EDF, this list is sorted by deadlines.
320 */
321 DOMAIN_COMPARER(runq, list, d1->deadl_abs, d2->deadl_abs)
322 static inline void __add_to_runqueue_sort(struct vcpu *d) {
323 PRINT(3,"Adding domain %i.%i (deadl= %"PRIu64") to runq\n",
324 d->domain->domain_id, d->vcpu_id, EDOM_INFO(d)->deadl_abs);
325 list_insert_sort(RUNQ(d->processor), LIST(d), runq_comp);
326 }
328 /* Allocates memory for per domain private scheduling data*/
329 static int sedf_alloc_task(struct vcpu *d) {
330 PRINT(2,"sedf_alloc_task was called, domain-id %i.%i\n",d->domain->domain_id,
331 d->vcpu_id);
332 if (d->domain->sched_priv == NULL) {
333 if ((d->domain->sched_priv =
334 xmalloc(struct sedf_dom_info)) == NULL )
335 return -1;
336 memset(d->domain->sched_priv, 0, sizeof(struct sedf_dom_info));
337 }
338 if ((d->sched_priv = xmalloc(struct sedf_vcpu_info)) == NULL )
339 return -1;
340 memset(d->sched_priv, 0, sizeof(struct sedf_vcpu_info));
341 return 0;
342 }
344 /* Setup the sedf_dom_info */
345 static void sedf_add_task(struct vcpu *d)
346 {
347 struct sedf_vcpu_info *inf = EDOM_INFO(d);
348 inf->vcpu = d;
350 PRINT(2,"sedf_add_task was called, domain-id %i.%i\n",d->domain->domain_id,
351 d->vcpu_id);
353 /* Allocate per-CPU context if this is the first domain to be added. */
354 if ( unlikely(schedule_data[d->processor].sched_priv == NULL) )
355 {
356 schedule_data[d->processor].sched_priv =
357 xmalloc(struct sedf_cpu_info);
358 BUG_ON(schedule_data[d->processor].sched_priv == NULL);
359 memset(CPU_INFO(d->processor), 0, sizeof(*CPU_INFO(d->processor)));
360 INIT_LIST_HEAD(WAITQ(d->processor));
361 INIT_LIST_HEAD(RUNQ(d->processor));
362 INIT_LIST_HEAD(EXTRAQ(d->processor,EXTRA_PEN_Q));
363 INIT_LIST_HEAD(EXTRAQ(d->processor,EXTRA_UTIL_Q));
364 }
366 if (d->domain->domain_id==0) {
367 /*set dom0 to something useful to boot the machine*/
368 inf->period = MILLISECS(20);
369 inf->slice = MILLISECS(15);
370 inf->latency = 0;
371 inf->deadl_abs = 0;
372 inf->status = EXTRA_AWARE | SEDF_ASLEEP;
373 } else {
374 /*other domains run in best effort mode*/
375 inf->period = WEIGHT_PERIOD;
376 inf->slice = 0;
377 inf->deadl_abs = 0;
378 inf->latency = 0;
379 inf->status = EXTRA_AWARE | SEDF_ASLEEP;
380 inf->extraweight = 1;
381 }
382 inf->period_orig = inf->period; inf->slice_orig = inf->slice;
383 INIT_LIST_HEAD(&(inf->list));
384 INIT_LIST_HEAD(&(inf->extralist[EXTRA_PEN_Q]));
385 INIT_LIST_HEAD(&(inf->extralist[EXTRA_UTIL_Q]));
387 if (!is_idle_task(d->domain)) {
388 extraq_check(d);
389 } else {
390 EDOM_INFO(d)->deadl_abs = 0;
391 EDOM_INFO(d)->status &= ~SEDF_ASLEEP;
392 }
393 }
395 /* Frees memory used by domain info */
396 static void sedf_free_task(struct domain *d)
397 {
398 int i;
399 PRINT(2,"sedf_free_task was called, domain-id %i\n",d->domain_id);
400 ASSERT(d->sched_priv != NULL);
401 xfree(d->sched_priv);
403 for (i = 0; i < MAX_VIRT_CPUS; i++)
404 if ( d->vcpu[i] ) {
405 ASSERT(d->vcpu[i]->sched_priv != NULL);
406 xfree(d->vcpu[i]->sched_priv);
407 }
408 }
410 /* handles the rescheduling, bookkeeping of domains running in their realtime-time :)*/
411 static inline void desched_edf_dom (s_time_t now, struct vcpu* d) {
412 struct sedf_vcpu_info* inf = EDOM_INFO(d);
413 /*current domain is running in real time mode*/
415 ASSERT(__task_on_queue(d));
416 /*update the domains cputime*/
417 inf->cputime += now - inf->sched_start_abs;
419 /*scheduling decisions, which don't remove the running domain
420 from the runq*/
421 if ((inf->cputime < inf->slice) && sedf_runnable(d))
422 return;
424 __del_from_queue(d);
426 /*manage bookkeeping (i.e. calculate next deadline,
427 memorize overun-time of slice) of finished domains*/
428 if (inf->cputime >= inf->slice) {
429 inf->cputime -= inf->slice;
431 if (inf->period < inf->period_orig) {
432 /*this domain runs in latency scaling or burst mode*/
433 #if (UNBLOCK == UNBLOCK_BURST)
434 /*if we are runnig in burst scaling wait for two periods
435 before scaling periods up again*/
436 if (now - inf->unblock_abs >= 2 * inf->period)
437 #endif
438 {
439 inf->period *= 2; inf->slice *= 2;
440 if ((inf->period > inf->period_orig) ||
441 (inf->slice > inf->slice_orig)) {
442 /*reset slice & period*/
443 inf->period = inf->period_orig;
444 inf->slice = inf->slice_orig;
445 }
446 }
447 }
448 /*set next deadline*/
449 inf->deadl_abs += inf->period;
450 }
452 /*add a runnable domain to the waitqueue*/
453 if (sedf_runnable(d))
454 __add_to_waitqueue_sort(d);
455 else {
456 /*we have a blocked realtime task -> remove it from exqs too*/
457 #if (EXTRA > EXTRA_OFF)
458 #if (EXTRA == EXTRA_BLOCK_WEIGHT)
459 if (extraq_on(d, EXTRA_PEN_Q)) extraq_del(d, EXTRA_PEN_Q);
460 #endif
461 if (extraq_on(d, EXTRA_UTIL_Q)) extraq_del(d, EXTRA_UTIL_Q);
462 #endif
463 }
464 ASSERT(EQ(sedf_runnable(d), __task_on_queue(d)));
465 ASSERT(IMPLY(extraq_on(d, EXTRA_UTIL_Q) || extraq_on(d, EXTRA_PEN_Q),
466 sedf_runnable(d)));
467 }
469 /* Update all elements on the queues */
470 static inline void update_queues(s_time_t now, struct list_head* runq,
471 struct list_head* waitq) {
472 struct list_head *cur,*tmp;
473 struct sedf_vcpu_info *curinf;
475 PRINT(3,"Updating waitq..\n");
476 /*check for the first elements of the waitqueue, whether their
477 next period has already started*/
478 list_for_each_safe(cur, tmp, waitq) {
479 curinf = list_entry(cur, struct sedf_vcpu_info, list);
480 PRINT(4,"\tLooking @ dom %i.%i\n",
481 curinf->vcpu->domain->domain_id, curinf->vcpu->vcpu_id);
482 if (PERIOD_BEGIN(curinf) <= now) {
483 __del_from_queue(curinf->vcpu);
484 __add_to_runqueue_sort(curinf->vcpu);
485 }
486 else
487 break;
488 }
490 PRINT(3,"Updating runq..\n");
491 /*process the runq, find domains that are on
492 the runqueue which shouldn't be there*/
493 list_for_each_safe(cur, tmp, runq) {
494 curinf = list_entry(cur,struct sedf_vcpu_info,list);
495 PRINT(4,"\tLooking @ dom %i.%i\n",
496 curinf->vcpu->domain->domain_id, curinf->vcpu->vcpu_id);
497 if (unlikely(curinf->slice == 0)) {
498 /*ignore domains with empty slice*/
499 PRINT(4,"\tUpdating zero-slice domain %i.%i\n",
500 curinf->vcpu->domain->domain_id,
501 curinf->vcpu->vcpu_id);
502 __del_from_queue(curinf->vcpu);
504 /*move them to their next period*/
505 curinf->deadl_abs += curinf->period;
506 /*and put them back into the queue*/
507 __add_to_waitqueue_sort(curinf->vcpu);
508 continue;
509 }
510 if (unlikely((curinf->deadl_abs < now) ||
511 (curinf->cputime > curinf->slice))) {
512 /*we missed the deadline or the slice was
513 already finished... might hapen because
514 of dom_adj.*/
515 PRINT(4,"\tDomain %i.%i exceeded it's deadline/"
516 "slice (%"PRIu64" / %"PRIu64") now: %"PRIu64
517 " cputime: %"PRIu64"\n",
518 curinf->vcpu->domain->domain_id,
519 curinf->vcpu->vcpu_id,
520 curinf->deadl_abs, curinf->slice, now,
521 curinf->cputime);
522 __del_from_queue(curinf->vcpu);
523 /*common case: we miss one period!*/
524 curinf->deadl_abs += curinf->period;
526 /*if we are still behind: modulo arithmetic,
527 force deadline to be in future and
528 aligned to period borders!*/
529 if (unlikely(curinf->deadl_abs < now))
530 curinf->deadl_abs +=
531 DIV_UP(now - curinf->deadl_abs,
532 curinf->period) * curinf->period;
533 ASSERT(curinf->deadl_abs > now);
534 /*give a fresh slice*/
535 curinf->cputime = 0;
536 if (PERIOD_BEGIN(curinf) > now)
537 __add_to_waitqueue_sort(curinf->vcpu);
538 else
539 __add_to_runqueue_sort(curinf->vcpu);
540 }
541 else
542 break;
543 }
544 PRINT(3,"done updating the queues\n");
545 }
547 #if (EXTRA > EXTRA_OFF)
548 /* removes a domain from the head of the according extraQ and
549 requeues it at a specified position:
550 round-robin extratime: end of extraQ
551 weighted ext.: insert in sorted list by score
552 if the domain is blocked / has regained its short-block-loss
553 time it is not put on any queue */
554 static inline void desched_extra_dom(s_time_t now, struct vcpu* d) {
555 struct sedf_vcpu_info *inf = EDOM_INFO(d);
556 int i = extra_get_cur_q(inf);
558 #if (EXTRA == EXTRA_SLICE_WEIGHT || EXTRA == EXTRA_BLOCK_WEIGHT)
559 unsigned long oldscore;
560 #endif
561 ASSERT(extraq_on(d, i));
562 /*unset all running flags*/
563 inf->status &= ~(EXTRA_RUN_PEN | EXTRA_RUN_UTIL);
564 /*fresh slice for the next run*/
565 inf->cputime = 0;
566 /*accumulate total extratime*/
567 inf->extra_time_tot += now - inf->sched_start_abs;
568 /*remove extradomain from head of the queue*/
569 extraq_del(d, i);
571 #if (EXTRA == EXTRA_ROUNDR)
572 if (sedf_runnable(d) && (inf->status & EXTRA_AWARE))
573 /*add to the tail if it is runnable => round-robin*/
574 extraq_add_tail(d, EXTRA_UTIL_Q);
575 #elif (EXTRA == EXTRA_SLICE_WEIGHT || EXTRA == EXTRA_BLOCK_WEIGHT)
576 /*update the score*/
577 oldscore = inf->score[i];
578 #if (EXTRA == EXTRA_BLOCK_WEIGHT)
579 if (i == EXTRA_PEN_Q) {
580 /*domain was running in L0 extraq*/
581 /*reduce block lost, probably more sophistication here!*/
582 /*inf->short_block_lost_tot -= EXTRA_QUANTUM;*/
583 inf->short_block_lost_tot -= now - inf->sched_start_abs;
584 PRINT(3,"Domain %i.%i: Short_block_loss: %"PRIi64"\n",
585 inf->vcpu->domain->domain_id, inf->vcpu->vcpu_id,
586 inf->short_block_lost_tot);
587 if (inf->short_block_lost_tot <= 0) {
588 PRINT(4,"Domain %i.%i compensated short block loss!\n",
589 inf->vcpu->domain->domain_id, inf->vcpu->vcpu_id);
590 /*we have (over-)compensated our block penalty*/
591 inf->short_block_lost_tot = 0;
592 /*we don't want a place on the penalty queue anymore!*/
593 inf->status &= ~EXTRA_WANT_PEN_Q;
594 goto check_extra_queues;
595 }
596 /*we have to go again for another try in the block-extraq,
597 the score is not used incremantally here, as this is
598 already done by recalculating the block_lost*/
599 inf->score[EXTRA_PEN_Q] = (inf->period << 10) /
600 inf->short_block_lost_tot;
601 oldscore = 0;
602 } else
603 #endif
604 {
605 /*domain was running in L1 extraq => score is inverse of
606 utilization and is used somewhat incremental!*/
607 if (!inf->extraweight)
608 /*NB: use fixed point arithmetic with 10 bits*/
609 inf->score[EXTRA_UTIL_Q] = (inf->period << 10) /
610 inf->slice;
611 else
612 /*conversion between realtime utilisation and extrawieght:
613 full (ie 100%) utilization is equivalent to 128 extraweight*/
614 inf->score[EXTRA_UTIL_Q] = (1<<17) / inf->extraweight;
615 }
616 check_extra_queues:
617 /* Adding a runnable domain to the right queue and removing blocked ones*/
618 if (sedf_runnable(d)) {
619 /*add according to score: weighted round robin*/
620 if (((inf->status & EXTRA_AWARE) && (i == EXTRA_UTIL_Q)) ||
621 ((inf->status & EXTRA_WANT_PEN_Q) && (i == EXTRA_PEN_Q)))
622 extraq_add_sort_update(d, i, oldscore);
623 }
624 else {
625 /*remove this blocked domain from the waitq!*/
626 __del_from_queue(d);
627 #if (EXTRA == EXTRA_BLOCK_WEIGHT)
628 /*make sure that we remove a blocked domain from the other
629 extraq too*/
630 if (i == EXTRA_PEN_Q) {
631 if (extraq_on(d, EXTRA_UTIL_Q)) extraq_del(d, EXTRA_UTIL_Q);
632 } else {
633 if (extraq_on(d, EXTRA_PEN_Q)) extraq_del(d, EXTRA_PEN_Q);
634 }
635 #endif
636 }
637 #endif
638 ASSERT(EQ(sedf_runnable(d), __task_on_queue(d)));
639 ASSERT(IMPLY(extraq_on(d, EXTRA_UTIL_Q) || extraq_on(d, EXTRA_PEN_Q),
640 sedf_runnable(d)));
641 }
642 #endif
644 static inline struct task_slice sedf_do_extra_schedule (s_time_t now,
645 s_time_t end_xt, struct list_head *extraq[], int cpu) {
646 struct task_slice ret;
647 struct sedf_vcpu_info *runinf;
649 /* Enough time left to use for extratime? */
650 if (end_xt - now < EXTRA_QUANTUM)
651 goto return_idle;
652 #if (EXTRA == EXTRA_BLOCK_WEIGHT)
653 if (!list_empty(extraq[EXTRA_PEN_Q])) {
654 /*we still have elements on the level 0 extraq
655 => let those run first!*/
656 runinf = list_entry(extraq[EXTRA_PEN_Q]->next,
657 struct sedf_vcpu_info, extralist[EXTRA_PEN_Q]);
658 runinf->status |= EXTRA_RUN_PEN;
659 ret.task = runinf->vcpu;
660 ret.time = EXTRA_QUANTUM;
661 #ifdef SEDF_STATS
662 runinf->pen_extra_slices++;
663 #endif
664 } else
665 #endif
666 if (!list_empty(extraq[EXTRA_UTIL_Q])) {
667 /*use elements from the normal extraqueue*/
668 runinf = list_entry(extraq[EXTRA_UTIL_Q]->next,
669 struct sedf_vcpu_info,
670 extralist[EXTRA_UTIL_Q]);
671 runinf->status |= EXTRA_RUN_UTIL;
672 ret.task = runinf->vcpu;
673 ret.time = EXTRA_QUANTUM;
674 }
675 else
676 goto return_idle;
678 ASSERT(ret.time > 0);
679 ASSERT(sedf_runnable(ret.task));
680 return ret;
682 return_idle:
683 ret.task = IDLETASK(cpu);
684 ret.time = end_xt - now;
685 ASSERT(ret.time > 0);
686 ASSERT(sedf_runnable(ret.task));
687 return ret;
688 }
689 /* Main scheduling function
690 Reasons for calling this function are:
691 -timeslice for the current period used up
692 -domain on waitqueue has started it's period
693 -and various others ;) in general: determine which domain to run next*/
694 static struct task_slice sedf_do_schedule(s_time_t now)
695 {
696 int cpu = current->processor;
697 struct list_head *runq = RUNQ(cpu);
698 struct list_head *waitq = WAITQ(cpu);
699 #if (EXTRA > EXTRA_OFF)
700 struct sedf_vcpu_info *inf = EDOM_INFO(current);
701 struct list_head *extraq[] = {EXTRAQ(cpu, EXTRA_PEN_Q),
702 EXTRAQ(cpu, EXTRA_UTIL_Q)};
703 #endif
704 struct task_slice ret;
705 /*int i = 0;*/
706 /*idle tasks don't need any of the following stuf*/
707 if (is_idle_task(current->domain))
708 goto check_waitq;
710 /* create local state of the status of the domain, in order to avoid
711 inconsistent state during scheduling decisions, because data for
712 domain_runnable is not protected by the scheduling lock!*/
713 if(!domain_runnable(current))
714 inf->status |= SEDF_ASLEEP;
716 if (inf->status & SEDF_ASLEEP)
717 inf->block_abs = now;
719 #if (EXTRA > EXTRA_OFF)
720 if (unlikely(extra_runs(inf))) {
721 /*special treatment of domains running in extra time*/
722 desched_extra_dom(now, current);
723 }
724 else
725 #endif
726 {
727 desched_edf_dom(now, current);
728 }
729 check_waitq:
730 update_queues(now, runq, waitq);
732 /*now simply pick the first domain from the runqueue, which has the
733 earliest deadline, because the list is sorted*/
734 struct sedf_vcpu_info *runinf, *waitinf;
736 if (!list_empty(runq)) {
737 runinf = list_entry(runq->next,struct sedf_vcpu_info,list);
738 ret.task = runinf->vcpu;
739 if (!list_empty(waitq)) {
740 waitinf = list_entry(waitq->next,
741 struct sedf_vcpu_info,list);
742 /*rerun scheduler, when scheduled domain reaches it's
743 end of slice or the first domain from the waitqueue
744 gets ready*/
745 ret.time = MIN(now + runinf->slice - runinf->cputime,
746 PERIOD_BEGIN(waitinf)) - now;
747 }
748 else {
749 ret.time = runinf->slice - runinf->cputime;
750 }
751 CHECK(ret.time > 0);
752 goto sched_done;
753 }
755 if (!list_empty(waitq)) {
756 waitinf = list_entry(waitq->next,struct sedf_vcpu_info, list);
757 /*we could not find any suitable domain
758 => look for domains that are aware of extratime*/
759 #if (EXTRA > EXTRA_OFF)
760 ret = sedf_do_extra_schedule(now, PERIOD_BEGIN(waitinf),
761 extraq, cpu);
762 #else
763 ret.task = IDLETASK(cpu);
764 ret.time = PERIOD_BEGIN(waitinf) - now;
765 #endif
766 CHECK(ret.time > 0);
767 }
768 else {
769 /*this could probably never happen, but one never knows...*/
770 /*it can... imagine a second CPU, which is pure scifi ATM,
771 but one never knows ;)*/
772 ret.task = IDLETASK(cpu);
773 ret.time = SECONDS(1);
774 }
776 sched_done:
777 /*TODO: Do something USEFUL when this happens and find out, why it
778 still can happen!!!*/
779 if (ret.time<0) {
780 printk("Ouch! We are seriously BEHIND schedule! %"PRIi64"\n",
781 ret.time);
782 ret.time = EXTRA_QUANTUM;
783 }
784 EDOM_INFO(ret.task)->sched_start_abs = now;
785 CHECK(ret.time > 0);
786 ASSERT(sedf_runnable(ret.task));
787 CPU_INFO(cpu)->current_slice_expires = now + ret.time;
788 return ret;
789 }
791 static void sedf_sleep(struct vcpu *d) {
792 PRINT(2,"sedf_sleep was called, domain-id %i.%i\n",d->domain->domain_id, d->vcpu_id);
794 if (is_idle_task(d->domain))
795 return;
797 EDOM_INFO(d)->status |= SEDF_ASLEEP;
799 if ( test_bit(_VCPUF_running, &d->vcpu_flags) ) {
800 cpu_raise_softirq(d->processor, SCHEDULE_SOFTIRQ);
801 }
802 else {
803 if ( __task_on_queue(d) )
804 __del_from_queue(d);
805 #if (EXTRA > EXTRA_OFF)
806 if (extraq_on(d, EXTRA_UTIL_Q))
807 extraq_del(d, EXTRA_UTIL_Q);
808 #endif
809 #if (EXTRA == EXTRA_BLOCK_WEIGHT)
810 if (extraq_on(d, EXTRA_PEN_Q))
811 extraq_del(d, EXTRA_PEN_Q);
812 #endif
813 }
814 }
816 /* This function wakes up a domain, i.e. moves them into the waitqueue
817 * things to mention are: admission control is taking place nowhere at
818 * the moment, so we can't be sure, whether it is safe to wake the domain
819 * up at all. Anyway, even if it is safe (total cpu usage <=100%) there are
820 * some considerations on when to allow the domain to wake up and have it's
821 * first deadline...
822 * I detected 3 cases, which could describe the possible behaviour of the
823 * scheduler,
824 * and I'll try to make them more clear:
825 *
826 * 1. Very conservative
827 * -when a blocked domain unblocks, it is allowed to start execution at
828 * the beginning of the next complete period
829 * (D..deadline, R..running, B..blocking/sleeping, U..unblocking/waking up
830 *
831 * DRRB_____D__U_____DRRRRR___D________ ...
832 *
833 * -this causes the domain to miss a period (and a deadlline)
834 * -doesn't disturb the schedule at all
835 * -deadlines keep occuring isochronous
836 *
837 * 2. Conservative Part 1: Short Unblocking
838 * -when a domain unblocks in the same period as it was blocked it
839 * unblocks and may consume the rest of it's original time-slice minus
840 * the time it was blocked
841 * (assume period=9, slice=5)
842 *
843 * DRB_UR___DRRRRR___D...
844 *
845 * -this also doesn't disturb scheduling, but might lead to the fact, that
846 * the domain can't finish it's workload in the period
847 * -in addition to that the domain can be treated prioritised when
848 * extratime is available
849 * -addition: experiments hve shown that this may have a HUGE impact on
850 * performance of other domains, becaus it can lead to excessive context
851 * switches
853 * Part2: Long Unblocking
854 * Part 2a
855 * -it is obvious that such accounting of block time, applied when
856 * unblocking is happening in later periods, works fine aswell
857 * -the domain is treated as if it would have been running since the start
858 * of its new period
859 *
860 * DRB______D___UR___D...
861 *
862 * Part 2b
863 * -if one needs the full slice in the next period, it is necessary to
864 * treat the unblocking time as the start of the new period, i.e. move
865 * the deadline further back (later)
866 * -this doesn't disturb scheduling as well, because for EDF periods can
867 * be treated as minimal inter-release times and scheduling stays
868 * correct, when deadlines are kept relative to the time the process
869 * unblocks
870 *
871 * DRB______D___URRRR___D...<prev [Thread] next>
872 * (D) <- old deadline was here
873 * -problem: deadlines don't occur isochronous anymore
874 * Part 2c (Improved Atropos design)
875 * -when a domain unblocks it is given a very short period (=latency hint)
876 * and slice length scaled accordingly
877 * -both rise again to the original value (e.g. get doubled every period)
878 *
879 * 3. Unconservative (i.e. incorrect)
880 * -to boost the performance of I/O dependent domains it would be possible
881 * to put the domain into the runnable queue immediately, and let it run
882 * for the remainder of the slice of the current period
883 * (or even worse: allocate a new full slice for the domain)
884 * -either behaviour can lead to missed deadlines in other domains as
885 * opposed to approaches 1,2a,2b
886 */
887 static inline void unblock_short_vcons
888 (struct sedf_vcpu_info* inf, s_time_t now) {
889 inf->deadl_abs += inf->period;
890 inf->cputime = 0;
891 }
893 static inline void unblock_short_cons(struct sedf_vcpu_info* inf, s_time_t now)
894 {
895 /*treat blocked time as consumed by the domain*/
896 inf->cputime += now - inf->block_abs;
897 if (inf->cputime + EXTRA_QUANTUM > inf->slice) {
898 /*we don't have a reasonable amount of time in
899 our slice left :( => start in next period!*/
900 unblock_short_vcons(inf, now);
901 }
902 #ifdef SEDF_STATS
903 else
904 inf->short_cont++;
905 #endif
906 }
907 static inline void unblock_short_extra_support (struct sedf_vcpu_info* inf,
908 s_time_t now) {
909 /*this unblocking scheme tries to support the domain, by assigning it
910 a priority in extratime distribution according to the loss of time
911 in this slice due to blocking*/
912 s_time_t pen;
914 /*no more realtime execution in this period!*/
915 inf->deadl_abs += inf->period;
916 if (likely(inf->block_abs)) {
917 //treat blocked time as consumed by the domain*/
918 /*inf->cputime += now - inf->block_abs;*/
919 /*penalty is time the domain would have
920 had if it continued to run */
921 pen = (inf->slice - inf->cputime);
922 if (pen < 0) pen = 0;
923 /*accumulate all penalties over the periods*/
924 /*inf->short_block_lost_tot += pen;*/
925 /*set penalty to the current value*/
926 inf->short_block_lost_tot = pen;
927 /*not sure which one is better.. but seems to work well...*/
929 if (inf->short_block_lost_tot) {
930 inf->score[0] = (inf->period << 10) /
931 inf->short_block_lost_tot;
932 #ifdef SEDF_STATS
933 inf->pen_extra_blocks++;
934 #endif
935 if (extraq_on(inf->vcpu, EXTRA_PEN_Q))
936 /*remove domain for possible resorting!*/
937 extraq_del(inf->vcpu, EXTRA_PEN_Q);
938 else
939 /*remember that we want to be on the penalty q
940 so that we can continue when we (un-)block
941 in penalty-extratime*/
942 inf->status |= EXTRA_WANT_PEN_Q;
944 /*(re-)add domain to the penalty extraq*/
945 extraq_add_sort_update(inf->vcpu, EXTRA_PEN_Q, 0);
946 }
947 }
948 /*give it a fresh slice in the next period!*/
949 inf->cputime = 0;
950 }
951 static inline void unblock_long_vcons(struct sedf_vcpu_info* inf, s_time_t now)
952 {
953 /* align to next future period */
954 inf->deadl_abs += (DIV_UP(now - inf->deadl_abs, inf->period) +1)
955 * inf->period;
956 inf->cputime = 0;
957 }
959 static inline void unblock_long_cons_a (struct sedf_vcpu_info* inf,
960 s_time_t now) {
961 /*treat the time the domain was blocked in the
962 CURRENT period as consumed by the domain*/
963 inf->cputime = (now - inf->deadl_abs) % inf->period;
964 if (inf->cputime + EXTRA_QUANTUM > inf->slice) {
965 /*we don't have a reasonable amount of time in our slice
966 left :( => start in next period!*/
967 unblock_long_vcons(inf, now);
968 }
969 }
970 static inline void unblock_long_cons_b(struct sedf_vcpu_info* inf,s_time_t now) {
971 /*Conservative 2b*/
972 /*Treat the unblocking time as a start of a new period */
973 inf->deadl_abs = now + inf->period;
974 inf->cputime = 0;
975 }
976 static inline void unblock_long_cons_c(struct sedf_vcpu_info* inf,s_time_t now) {
977 if (likely(inf->latency)) {
978 /*scale the slice and period accordingly to the latency hint*/
979 /*reduce period temporarily to the latency hint*/
980 inf->period = inf->latency;
981 /*this results in max. 4s slice/period length*/
982 ASSERT((inf->period < ULONG_MAX)
983 && (inf->slice_orig < ULONG_MAX));
984 /*scale slice accordingly, so that utilisation stays the same*/
985 inf->slice = (inf->period * inf->slice_orig)
986 / inf->period_orig;
987 inf->deadl_abs = now + inf->period;
988 inf->cputime = 0;
989 }
990 else {
991 /*we don't have a latency hint.. use some other technique*/
992 unblock_long_cons_b(inf, now);
993 }
994 }
995 /*a new idea of dealing with short blocks: burst period scaling*/
996 static inline void unblock_short_burst(struct sedf_vcpu_info* inf, s_time_t now)
997 {
998 /*treat blocked time as consumed by the domain*/
999 inf->cputime += now - inf->block_abs;
1001 if (inf->cputime + EXTRA_QUANTUM <= inf->slice) {
1002 /*if we can still use some time in the current slice
1003 then use it!*/
1004 #ifdef SEDF_STATS
1005 /*we let the domain run in the current period*/
1006 inf->short_cont++;
1007 #endif
1009 else {
1010 /*we don't have a reasonable amount of time in
1011 our slice left => switch to burst mode*/
1012 if (likely(inf->unblock_abs)) {
1013 /*set the period-length to the current blocking
1014 interval, possible enhancements: average over last
1015 blocking intervals, user-specified minimum,...*/
1016 inf->period = now - inf->unblock_abs;
1017 /*check for overflow on multiplication*/
1018 ASSERT((inf->period < ULONG_MAX)
1019 && (inf->slice_orig < ULONG_MAX));
1020 /*scale slice accordingly, so that utilisation
1021 stays the same*/
1022 inf->slice = (inf->period * inf->slice_orig)
1023 / inf->period_orig;
1024 /*set new (shorter) deadline*/
1025 inf->deadl_abs += inf->period;
1027 else {
1028 /*in case we haven't unblocked before
1029 start in next period!*/
1030 inf->cputime=0;
1031 inf->deadl_abs += inf->period;
1034 inf->unblock_abs = now;
1036 static inline void unblock_long_burst(struct sedf_vcpu_info* inf, s_time_t now) {
1037 if (unlikely(inf->latency && (inf->period > inf->latency))) {
1038 /*scale the slice and period accordingly to the latency hint*/
1039 inf->period = inf->latency;
1040 /*check for overflows on multiplication*/
1041 ASSERT((inf->period < ULONG_MAX)
1042 && (inf->slice_orig < ULONG_MAX));
1043 /*scale slice accordingly, so that utilisation stays the same*/
1044 inf->slice = (inf->period * inf->slice_orig)
1045 / inf->period_orig;
1046 inf->deadl_abs = now + inf->period;
1047 inf->cputime = 0;
1049 else {
1050 /*we don't have a latency hint.. or we are currently in
1051 "burst mode": use some other technique
1052 NB: this should be in fact the normal way of operation,
1053 when we are in sync with the device!*/
1054 unblock_long_cons_b(inf, now);
1056 inf->unblock_abs = now;
1059 #define DOMAIN_EDF 1
1060 #define DOMAIN_EXTRA_PEN 2
1061 #define DOMAIN_EXTRA_UTIL 3
1062 #define DOMAIN_IDLE 4
1063 static inline int get_run_type(struct vcpu* d) {
1064 struct sedf_vcpu_info* inf = EDOM_INFO(d);
1065 if (is_idle_task(d->domain))
1066 return DOMAIN_IDLE;
1067 if (inf->status & EXTRA_RUN_PEN)
1068 return DOMAIN_EXTRA_PEN;
1069 if (inf->status & EXTRA_RUN_UTIL)
1070 return DOMAIN_EXTRA_UTIL;
1071 return DOMAIN_EDF;
1073 /*Compares two domains in the relation of whether the one is allowed to
1074 interrupt the others execution.
1075 It returns true (!=0) if a switch to the other domain is good.
1076 Current Priority scheme is as follows:
1077 EDF > L0 (penalty based) extra-time >
1078 L1 (utilization) extra-time > idle-domain
1079 In the same class priorities are assigned as following:
1080 EDF: early deadline > late deadline
1081 L0 extra-time: lower score > higher score*/
1082 static inline int should_switch(struct vcpu* cur,
1083 struct vcpu* other, s_time_t now) {
1084 struct sedf_vcpu_info *cur_inf, *other_inf;
1085 cur_inf = EDOM_INFO(cur);
1086 other_inf = EDOM_INFO(other);
1088 /*check whether we need to make an earlier sched-decision*/
1089 if (PERIOD_BEGIN(other_inf) <
1090 CPU_INFO(other->processor)->current_slice_expires)
1091 return 1;
1092 /*no timing-based switches need to be taken into account here*/
1093 switch (get_run_type(cur)) {
1094 case DOMAIN_EDF:
1095 /* do not interrupt a running EDF domain */
1096 return 0;
1097 case DOMAIN_EXTRA_PEN:
1098 /*check whether we also want
1099 the L0 ex-q with lower score*/
1100 if ((other_inf->status & EXTRA_WANT_PEN_Q)
1101 && (other_inf->score[EXTRA_PEN_Q] <
1102 cur_inf->score[EXTRA_PEN_Q]))
1103 return 1;
1104 else return 0;
1105 case DOMAIN_EXTRA_UTIL:
1106 /*check whether we want the L0 extraq, don't
1107 switch if both domains want L1 extraq */
1108 if (other_inf->status & EXTRA_WANT_PEN_Q)
1109 return 1;
1110 else return 0;
1111 case DOMAIN_IDLE:
1112 return 1;
1114 return 1;
1116 void sedf_wake(struct vcpu *d) {
1117 s_time_t now = NOW();
1118 struct sedf_vcpu_info* inf = EDOM_INFO(d);
1120 PRINT(3, "sedf_wake was called, domain-id %i.%i\n",d->domain->domain_id,
1121 d->vcpu_id);
1123 if (unlikely(is_idle_task(d->domain)))
1124 return;
1126 if ( unlikely(__task_on_queue(d)) ) {
1127 PRINT(3,"\tdomain %i.%i is already in some queue\n",
1128 d->domain->domain_id, d->vcpu_id);
1129 return;
1131 ASSERT(!sedf_runnable(d));
1132 inf->status &= ~SEDF_ASLEEP;
1133 ASSERT(!extraq_on(d, EXTRA_UTIL_Q));
1134 ASSERT(!extraq_on(d, EXTRA_PEN_Q));
1136 if (unlikely(inf->deadl_abs == 0))
1137 /*initial setup of the deadline*/
1138 inf->deadl_abs = now + inf->slice;
1140 PRINT(3,"waking up domain %i.%i (deadl= %"PRIu64" period= %"PRIu64" "\
1141 "now= %"PRIu64")\n", d->domain->domain_id, d->vcpu_id, inf->deadl_abs,
1142 inf->period, now);
1143 #ifdef SEDF_STATS
1144 inf->block_tot++;
1145 #endif
1146 if (unlikely(now < PERIOD_BEGIN(inf))) {
1147 PRINT(4,"extratime unblock\n");
1148 /* unblocking in extra-time! */
1149 #if (EXTRA == EXTRA_BLOCK_WEIGHT)
1150 if (inf->status & EXTRA_WANT_PEN_Q) {
1151 /*we have a domain that wants compensation
1152 for block penalty and did just block in
1153 its compensation time. Give it another
1154 chance!*/
1155 extraq_add_sort_update(d, EXTRA_PEN_Q, 0);
1157 #endif
1158 extraq_check_add_unblocked(d, 0);
1160 else {
1161 if (now < inf->deadl_abs) {
1162 PRINT(4,"short unblocking\n");
1163 /*short blocking*/
1164 #ifdef SEDF_STATS
1165 inf->short_block_tot++;
1166 #endif
1167 #if (UNBLOCK <= UNBLOCK_ATROPOS)
1168 unblock_short_vcons(inf, now);
1169 #elif (UNBLOCK == UNBLOCK_SHORT_RESUME)
1170 unblock_short_cons(inf, now);
1171 #elif (UNBLOCK == UNBLOCK_BURST)
1172 unblock_short_burst(inf, now);
1173 #elif (UNBLOCK == UNBLOCK_EXTRA_SUPPORT)
1174 unblock_short_extra_support(inf, now);
1175 #endif
1177 extraq_check_add_unblocked(d, 1);
1179 else {
1180 PRINT(4,"long unblocking\n");
1181 /*long unblocking*/
1182 #ifdef SEDF_STATS
1183 inf->long_block_tot++;
1184 #endif
1185 #if (UNBLOCK == UNBLOCK_ISOCHRONOUS_EDF)
1186 unblock_long_vcons(inf, now);
1187 #elif (UNBLOCK == UNBLOCK_EDF \
1188 || UNBLOCK == UNBLOCK_EXTRA_SUPPORT)
1189 unblock_long_cons_b(inf, now);
1190 #elif (UNBLOCK == UNBLOCK_ATROPOS)
1191 unblock_long_cons_c(inf, now);
1192 #elif (UNBLOCK == UNBLOCK_SHORT_RESUME)
1193 unblock_long_cons_b(inf, now);
1194 /*unblock_short_cons_c(inf, now);*/
1195 #elif (UNBLOCK == UNBLOCK_BURST)
1196 unblock_long_burst(inf, now);
1197 #endif
1199 extraq_check_add_unblocked(d, 1);
1202 PRINT(3,"woke up domain %i.%i (deadl= %"PRIu64" period= %"PRIu64" "\
1203 "now= %"PRIu64")\n", d->domain->domain_id, d->vcpu_id, inf->deadl_abs,
1204 inf->period, now);
1205 if (PERIOD_BEGIN(inf) > now) {
1206 __add_to_waitqueue_sort(d);
1207 PRINT(3,"added to waitq\n");
1209 else {
1210 __add_to_runqueue_sort(d);
1211 PRINT(3,"added to runq\n");
1214 #ifdef SEDF_STATS
1215 /*do some statistics here...*/
1216 if (inf->block_abs != 0) {
1217 inf->block_time_tot += now - inf->block_abs;
1218 inf->penalty_time_tot +=
1219 PERIOD_BEGIN(inf) + inf->cputime - inf->block_abs;
1221 #endif
1222 /*sanity check: make sure each extra-aware domain IS on the util-q!*/
1223 ASSERT(IMPLY(inf->status & EXTRA_AWARE, extraq_on(d, EXTRA_UTIL_Q)));
1224 ASSERT(__task_on_queue(d));
1225 /*check whether the awakened task needs to invoke the do_schedule
1226 routine. Try to avoid unnecessary runs but:
1227 Save approximation: Always switch to scheduler!*/
1228 ASSERT(d->processor >= 0);
1229 ASSERT(d->processor < NR_CPUS);
1230 ASSERT(schedule_data[d->processor].curr);
1231 if (should_switch(schedule_data[d->processor].curr, d, now))
1232 cpu_raise_softirq(d->processor, SCHEDULE_SOFTIRQ);
1235 /*Print a lot of use-{full, less} information about a domains in the system*/
1236 static void sedf_dump_domain(struct vcpu *d) {
1237 printk("%i.%i has=%c ", d->domain->domain_id, d->vcpu_id,
1238 test_bit(_VCPUF_running, &d->vcpu_flags) ? 'T':'F');
1239 printk("p=%"PRIu64" sl=%"PRIu64" ddl=%"PRIu64" w=%hu c=%"PRIu64" sc=%i xtr(%s)=%"PRIu64" ew=%hu",
1240 EDOM_INFO(d)->period, EDOM_INFO(d)->slice, EDOM_INFO(d)->deadl_abs,
1241 EDOM_INFO(d)->weight, d->cpu_time, EDOM_INFO(d)->score[EXTRA_UTIL_Q],
1242 (EDOM_INFO(d)->status & EXTRA_AWARE) ? "yes" : "no",
1243 EDOM_INFO(d)->extra_time_tot, EDOM_INFO(d)->extraweight);
1244 if (d->cpu_time !=0)
1245 printf(" (%"PRIu64"%%)", (EDOM_INFO(d)->extra_time_tot * 100)
1246 / d->cpu_time);
1247 #ifdef SEDF_STATS
1248 if (EDOM_INFO(d)->block_time_tot!=0)
1249 printf(" pen=%"PRIu64"%%", (EDOM_INFO(d)->penalty_time_tot * 100) /
1250 EDOM_INFO(d)->block_time_tot);
1251 if (EDOM_INFO(d)->block_tot!=0)
1252 printf("\n blks=%u sh=%u (%u%%) (shc=%u (%u%%) shex=%i "\
1253 "shexsl=%i) l=%u (%u%%) avg: b=%"PRIu64" p=%"PRIu64"",
1254 EDOM_INFO(d)->block_tot, EDOM_INFO(d)->short_block_tot,
1255 (EDOM_INFO(d)->short_block_tot * 100)
1256 / EDOM_INFO(d)->block_tot, EDOM_INFO(d)->short_cont,
1257 (EDOM_INFO(d)->short_cont * 100) / EDOM_INFO(d)->block_tot,
1258 EDOM_INFO(d)->pen_extra_blocks,
1259 EDOM_INFO(d)->pen_extra_slices,
1260 EDOM_INFO(d)->long_block_tot,
1261 (EDOM_INFO(d)->long_block_tot * 100) / EDOM_INFO(d)->block_tot,
1262 (EDOM_INFO(d)->block_time_tot) / EDOM_INFO(d)->block_tot,
1263 (EDOM_INFO(d)->penalty_time_tot) / EDOM_INFO(d)->block_tot);
1264 #endif
1265 printf("\n");
1268 /*dumps all domains on hte specified cpu*/
1269 static void sedf_dump_cpu_state(int i)
1271 struct list_head *list, *queue, *tmp;
1272 struct sedf_vcpu_info *d_inf;
1273 struct domain *d;
1274 struct vcpu *ed;
1275 int loop = 0;
1277 printk("now=%"PRIu64"\n",NOW());
1278 queue = RUNQ(i);
1279 printk("RUNQ rq %lx n: %lx, p: %lx\n", (unsigned long)queue,
1280 (unsigned long) queue->next, (unsigned long) queue->prev);
1281 list_for_each_safe ( list, tmp, queue ) {
1282 printk("%3d: ",loop++);
1283 d_inf = list_entry(list, struct sedf_vcpu_info, list);
1284 sedf_dump_domain(d_inf->vcpu);
1287 queue = WAITQ(i); loop = 0;
1288 printk("\nWAITQ rq %lx n: %lx, p: %lx\n", (unsigned long)queue,
1289 (unsigned long) queue->next, (unsigned long) queue->prev);
1290 list_for_each_safe ( list, tmp, queue ) {
1291 printk("%3d: ",loop++);
1292 d_inf = list_entry(list, struct sedf_vcpu_info, list);
1293 sedf_dump_domain(d_inf->vcpu);
1296 queue = EXTRAQ(i,EXTRA_PEN_Q); loop = 0;
1297 printk("\nEXTRAQ (penalty) rq %lx n: %lx, p: %lx\n",
1298 (unsigned long)queue, (unsigned long) queue->next,
1299 (unsigned long) queue->prev);
1300 list_for_each_safe ( list, tmp, queue ) {
1301 d_inf = list_entry(list, struct sedf_vcpu_info,
1302 extralist[EXTRA_PEN_Q]);
1303 printk("%3d: ",loop++);
1304 sedf_dump_domain(d_inf->vcpu);
1307 queue = EXTRAQ(i,EXTRA_UTIL_Q); loop = 0;
1308 printk("\nEXTRAQ (utilization) rq %lx n: %lx, p: %lx\n",
1309 (unsigned long)queue, (unsigned long) queue->next,
1310 (unsigned long) queue->prev);
1311 list_for_each_safe ( list, tmp, queue ) {
1312 d_inf = list_entry(list, struct sedf_vcpu_info,
1313 extralist[EXTRA_UTIL_Q]);
1314 printk("%3d: ",loop++);
1315 sedf_dump_domain(d_inf->vcpu);
1318 loop = 0;
1319 printk("\nnot on Q\n");
1320 for_each_domain(d)
1321 for_each_vcpu(d, ed)
1323 if (!__task_on_queue(ed) && (ed->processor == i)) {
1324 printk("%3d: ",loop++);
1325 sedf_dump_domain(ed);
1329 /*Adjusts periods and slices of the domains accordingly to their weights*/
1330 static inline int sedf_adjust_weights(struct sched_adjdom_cmd *cmd) {
1331 struct vcpu *p;
1332 struct domain *d;
1333 int sumw[NR_CPUS];
1334 s_time_t sumt[NR_CPUS];
1335 int cpu;
1337 for (cpu=0; cpu < NR_CPUS; cpu++) {
1338 sumw[cpu] = 0;
1339 sumt[cpu] = 0;
1341 /*sum up all weights*/
1342 for_each_domain(d)
1343 for_each_vcpu(d, p) {
1344 if (EDOM_INFO(p)->weight)
1345 sumw[p->processor] += EDOM_INFO(p)->weight;
1346 else {
1347 /*don't modify domains who don't have a weight, but sum
1348 up the time they need, projected to a WEIGHT_PERIOD,
1349 so that this time is not given to the weight-driven
1350 domains*/
1351 /*check for overflows*/
1352 ASSERT((WEIGHT_PERIOD < ULONG_MAX)
1353 && (EDOM_INFO(p)->slice_orig < ULONG_MAX));
1354 sumt[p->processor] +=
1355 (WEIGHT_PERIOD * EDOM_INFO(p)->slice_orig) /
1356 EDOM_INFO(p)->period_orig;
1359 /*adjust all slices (and periods) to the new weight*/
1360 for_each_domain(d)
1361 for_each_vcpu(d, p) {
1362 if (EDOM_INFO(p)->weight) {
1363 EDOM_INFO(p)->period_orig =
1364 EDOM_INFO(p)->period = WEIGHT_PERIOD;
1365 EDOM_INFO(p)->slice_orig =
1366 EDOM_INFO(p)->slice =
1367 (EDOM_INFO(p)->weight *
1368 (WEIGHT_PERIOD - WEIGHT_SAFETY - sumt[p->processor])) /
1369 sumw[p->processor];
1372 return 0;
1375 /* set or fetch domain scheduling parameters */
1376 static int sedf_adjdom(struct domain *p, struct sched_adjdom_cmd *cmd) {
1377 struct vcpu *v;
1379 PRINT(2,"sedf_adjdom was called, domain-id %i new period %"PRIu64" "\
1380 "new slice %"PRIu64"\nlatency %"PRIu64" extra:%s\n",
1381 p->domain_id, cmd->u.sedf.period, cmd->u.sedf.slice,
1382 cmd->u.sedf.latency, (cmd->u.sedf.extratime)?"yes":"no");
1383 if ( cmd->direction == SCHED_INFO_PUT )
1385 /*check for sane parameters*/
1386 if (!cmd->u.sedf.period && !cmd->u.sedf.weight)
1387 return -EINVAL;
1388 if (cmd->u.sedf.weight) {
1389 if ((cmd->u.sedf.extratime & EXTRA_AWARE) &&
1390 (! cmd->u.sedf.period)) {
1391 /*weight driven domains with xtime ONLY!*/
1392 for_each_vcpu(p, v) {
1393 EDOM_INFO(v)->extraweight = cmd->u.sedf.weight;
1394 EDOM_INFO(v)->weight = 0;
1395 EDOM_INFO(v)->slice = 0;
1396 EDOM_INFO(v)->period = WEIGHT_PERIOD;
1398 } else {
1399 /*weight driven domains with real-time execution*/
1400 for_each_vcpu(p, v)
1401 EDOM_INFO(v)->weight = cmd->u.sedf.weight;
1404 else {
1405 /*time driven domains*/
1406 for_each_vcpu(p, v) {
1407 /* sanity checking! */
1408 if(cmd->u.sedf.slice > cmd->u.sedf.period )
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;
1418 if (sedf_adjust_weights(cmd))
1419 return -EINVAL;
1421 for_each_vcpu(p, v) {
1422 EDOM_INFO(v)->status =
1423 (EDOM_INFO(v)->status &
1424 ~EXTRA_AWARE) | (cmd->u.sedf.extratime & EXTRA_AWARE);
1425 EDOM_INFO(v)->latency = cmd->u.sedf.latency;
1426 extraq_check(v);
1429 else if ( cmd->direction == SCHED_INFO_GET )
1431 cmd->u.sedf.period = EDOM_INFO(p->vcpu[0])->period;
1432 cmd->u.sedf.slice = EDOM_INFO(p->vcpu[0])->slice;
1433 cmd->u.sedf.extratime = EDOM_INFO(p->vcpu[0])->status
1434 & EXTRA_AWARE;
1435 cmd->u.sedf.latency = EDOM_INFO(p->vcpu[0])->latency;
1436 cmd->u.sedf.weight = EDOM_INFO(p->vcpu[0])->weight;
1438 PRINT(2,"sedf_adjdom_finished\n");
1439 return 0;
1442 struct scheduler sched_sedf_def = {
1443 .name = "Simple EDF Scheduler",
1444 .opt_name = "sedf",
1445 .sched_id = SCHED_SEDF,
1447 .alloc_task = sedf_alloc_task,
1448 .add_task = sedf_add_task,
1449 .free_task = sedf_free_task,
1450 .do_schedule = sedf_do_schedule,
1451 .dump_cpu_state = sedf_dump_cpu_state,
1452 .sleep = sedf_sleep,
1453 .wake = sedf_wake,
1454 .adjdom = sedf_adjdom,
1455 };