direct-io.hg

view xen/common/sched_sedf.c @ 5517:10e9028c8e3d

bitkeeper revision 1.1718.1.10 (42b7b19aqOS_1M8I4pIOFjiTPYWV-g)

Merge bk://xenbits.xensource.com/xen-unstable.bk
into spot.cl.cam.ac.uk:C:/Documents and Settings/iap10/xen-unstable.bk
author iap10@spot.cl.cam.ac.uk
date Tue Jun 21 06:20:10 2005 +0000 (2005-06-21)
parents 8651a99cdc09
children 8a8b8087b083 a83ac0806d6b
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_NONE | SEDF_ASLEEP;/*EXTRA_AWARE; */
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 /*give a domain w/ exweight = 1 as much as a domain with
613 util = 1/128*/
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 | EXTRA_WANT_PEN_Q))
621 extraq_add_sort_update(d, i, oldscore);
622 }
623 else {
624 /*remove this blocked domain from the waitq!*/
625 __del_from_queue(d);
626 #if (EXTRA == EXTRA_BLOCK_WEIGHT)
627 /*make sure that we remove a blocked domain from the other
628 extraq too*/
629 if (i == EXTRA_PEN_Q) {
630 if (extraq_on(d, EXTRA_UTIL_Q))
631 extraq_del(d, EXTRA_UTIL_Q);
632 }
633 else {
634 if (extraq_on(d, EXTRA_PEN_Q))
635 extraq_del(d, EXTRA_PEN_Q);
636 }
637 #endif
638 }
639 #endif
640 ASSERT(EQ(sedf_runnable(d), __task_on_queue(d)));
641 ASSERT(IMPLY(extraq_on(d, EXTRA_UTIL_Q) || extraq_on(d, EXTRA_PEN_Q),
642 sedf_runnable(d)));
643 }
644 #endif
646 static inline struct task_slice sedf_do_extra_schedule (s_time_t now,
647 s_time_t end_xt, struct list_head *extraq[], int cpu) {
648 struct task_slice ret;
649 struct sedf_vcpu_info *runinf;
651 /* Enough time left to use for extratime? */
652 if (end_xt - now < EXTRA_QUANTUM)
653 goto return_idle;
654 #if (EXTRA == EXTRA_BLOCK_WEIGHT)
655 if (!list_empty(extraq[EXTRA_PEN_Q])) {
656 /*we still have elements on the level 0 extraq
657 => let those run first!*/
658 runinf = list_entry(extraq[EXTRA_PEN_Q]->next,
659 struct sedf_vcpu_info, extralist[EXTRA_PEN_Q]);
660 runinf->status |= EXTRA_RUN_PEN;
661 ret.task = runinf->vcpu;
662 ret.time = EXTRA_QUANTUM;
663 #ifdef SEDF_STATS
664 runinf->pen_extra_slices++;
665 #endif
666 } else
667 #endif
668 if (!list_empty(extraq[EXTRA_UTIL_Q])) {
669 /*use elements from the normal extraqueue*/
670 runinf = list_entry(extraq[EXTRA_UTIL_Q]->next,
671 struct sedf_vcpu_info, extralist[EXTRA_UTIL_Q]);
672 runinf->status |= EXTRA_RUN_UTIL;
673 ret.task = runinf->vcpu;
674 ret.time = EXTRA_QUANTUM;
675 }
676 else
677 goto return_idle;
679 ASSERT(ret.time > 0);
680 ASSERT(sedf_runnable(ret.task));
681 return ret;
683 return_idle:
684 ret.task = IDLETASK(cpu);
685 ret.time = end_xt - now;
686 ASSERT(ret.time > 0);
687 ASSERT(sedf_runnable(ret.task));
688 return ret;
689 }
690 /* Main scheduling function
691 Reasons for calling this function are:
692 -timeslice for the current period used up
693 -domain on waitqueue has started it's period
694 -and various others ;) in general: determine which domain to run next*/
695 static struct task_slice sedf_do_schedule(s_time_t now)
696 {
697 int cpu = current->processor;
698 struct list_head *runq = RUNQ(cpu);
699 struct list_head *waitq = WAITQ(cpu);
700 #if (EXTRA > EXTRA_OFF)
701 struct sedf_vcpu_info *inf = EDOM_INFO(current);
702 struct list_head *extraq[] = {EXTRAQ(cpu, EXTRA_PEN_Q),
703 EXTRAQ(cpu, EXTRA_UTIL_Q)};
704 #endif
705 struct task_slice ret;
706 /*int i = 0;*/
707 /*idle tasks don't need any of the following stuf*/
708 if (is_idle_task(current->domain))
709 goto check_waitq;
711 /* create local state of the status of the domain, in order to avoid
712 inconsistent state during scheduling decisions, because data for
713 domain_runnable is not protected by the scheduling lock!*/
714 if(!domain_runnable(current))
715 inf->status |= SEDF_ASLEEP;
717 if (inf->status & SEDF_ASLEEP)
718 inf->block_abs = now;
720 #if (EXTRA > EXTRA_OFF)
721 if (unlikely(extra_runs(inf))) {
722 /*special treatment of domains running in extra time*/
723 desched_extra_dom(now, current);
724 }
725 else
726 #endif
727 {
728 desched_edf_dom(now, current);
729 }
730 check_waitq:
731 update_queues(now, runq, waitq);
733 /*now simply pick the first domain from the runqueue, which has the
734 earliest deadline, because the list is sorted*/
735 struct sedf_vcpu_info *runinf, *waitinf;
737 if (!list_empty(runq)) {
738 runinf = list_entry(runq->next,struct sedf_vcpu_info,list);
739 ret.task = runinf->vcpu;
740 if (!list_empty(waitq)) {
741 waitinf = list_entry(waitq->next,
742 struct sedf_vcpu_info,list);
743 /*rerun scheduler, when scheduled domain reaches it's
744 end of slice or the first domain from the waitqueue
745 gets ready*/
746 ret.time = MIN(now + runinf->slice - runinf->cputime,
747 PERIOD_BEGIN(waitinf)) - now;
748 }
749 else {
750 ret.time = runinf->slice - runinf->cputime;
751 }
752 CHECK(ret.time > 0);
753 goto sched_done;
754 }
756 if (!list_empty(waitq)) {
757 waitinf = list_entry(waitq->next,struct sedf_vcpu_info, list);
758 /*we could not find any suitable domain
759 => look for domains that are aware of extratime*/
760 #if (EXTRA > EXTRA_OFF)
761 ret = sedf_do_extra_schedule(now, PERIOD_BEGIN(waitinf),
762 extraq, cpu);
763 #else
764 ret.task = IDLETASK(cpu);
765 ret.time = PERIOD_BEGIN(waitinf) - now;
766 #endif
767 CHECK(ret.time > 0);
768 }
769 else {
770 /*this could probably never happen, but one never knows...*/
771 /*it can... imagine a second CPU, which is pure scifi ATM,
772 but one never knows ;)*/
773 ret.task = IDLETASK(cpu);
774 ret.time = SECONDS(1);
775 }
777 sched_done:
778 /*TODO: Do something USEFUL when this happens and find out, why it
779 still can happen!!!*/
780 if (ret.time<0) {
781 printk("Ouch! We are seriously BEHIND schedule! %"PRIi64"\n",
782 ret.time);
783 ret.time = EXTRA_QUANTUM;
784 }
785 EDOM_INFO(ret.task)->sched_start_abs = now;
786 CHECK(ret.time > 0);
787 ASSERT(sedf_runnable(ret.task));
788 CPU_INFO(cpu)->current_slice_expires = now + ret.time;
789 return ret;
790 }
792 static void sedf_sleep(struct vcpu *d) {
793 PRINT(2,"sedf_sleep was called, domain-id %i.%i\n",d->domain->domain_id, d->vcpu_id);
795 if (is_idle_task(d->domain))
796 return;
798 EDOM_INFO(d)->status |= SEDF_ASLEEP;
800 if ( test_bit(_VCPUF_running, &d->vcpu_flags) ) {
801 cpu_raise_softirq(d->processor, SCHEDULE_SOFTIRQ);
802 }
803 else {
804 if ( __task_on_queue(d) )
805 __del_from_queue(d);
806 #if (EXTRA > EXTRA_OFF)
807 if (extraq_on(d, EXTRA_UTIL_Q))
808 extraq_del(d, EXTRA_UTIL_Q);
809 #endif
810 #if (EXTRA == EXTRA_BLOCK_WEIGHT)
811 if (extraq_on(d, EXTRA_PEN_Q))
812 extraq_del(d, EXTRA_PEN_Q);
813 #endif
814 }
815 }
817 /* This function wakes up a domain, i.e. moves them into the waitqueue
818 * things to mention are: admission control is taking place nowhere at
819 * the moment, so we can't be sure, whether it is safe to wake the domain
820 * up at all. Anyway, even if it is safe (total cpu usage <=100%) there are
821 * some considerations on when to allow the domain to wake up and have it's
822 * first deadline...
823 * I detected 3 cases, which could describe the possible behaviour of the
824 * scheduler,
825 * and I'll try to make them more clear:
826 *
827 * 1. Very conservative
828 * -when a blocked domain unblocks, it is allowed to start execution at
829 * the beginning of the next complete period
830 * (D..deadline, R..running, B..blocking/sleeping, U..unblocking/waking up
831 *
832 * DRRB_____D__U_____DRRRRR___D________ ...
833 *
834 * -this causes the domain to miss a period (and a deadlline)
835 * -doesn't disturb the schedule at all
836 * -deadlines keep occuring isochronous
837 *
838 * 2. Conservative Part 1: Short Unblocking
839 * -when a domain unblocks in the same period as it was blocked it
840 * unblocks and may consume the rest of it's original time-slice minus
841 * the time it was blocked
842 * (assume period=9, slice=5)
843 *
844 * DRB_UR___DRRRRR___D...
845 *
846 * -this also doesn't disturb scheduling, but might lead to the fact, that
847 * the domain can't finish it's workload in the period
848 * -in addition to that the domain can be treated prioritised when
849 * extratime is available
850 * -addition: experiments hve shown that this may have a HUGE impact on
851 * performance of other domains, becaus it can lead to excessive context
852 * switches
854 * Part2: Long Unblocking
855 * Part 2a
856 * -it is obvious that such accounting of block time, applied when
857 * unblocking is happening in later periods, works fine aswell
858 * -the domain is treated as if it would have been running since the start
859 * of its new period
860 *
861 * DRB______D___UR___D...
862 *
863 * Part 2b
864 * -if one needs the full slice in the next period, it is necessary to
865 * treat the unblocking time as the start of the new period, i.e. move
866 * the deadline further back (later)
867 * -this doesn't disturb scheduling as well, because for EDF periods can
868 * be treated as minimal inter-release times and scheduling stays
869 * correct, when deadlines are kept relative to the time the process
870 * unblocks
871 *
872 * DRB______D___URRRR___D...<prev [Thread] next>
873 * (D) <- old deadline was here
874 * -problem: deadlines don't occur isochronous anymore
875 * Part 2c (Improved Atropos design)
876 * -when a domain unblocks it is given a very short period (=latency hint)
877 * and slice length scaled accordingly
878 * -both rise again to the original value (e.g. get doubled every period)
879 *
880 * 3. Unconservative (i.e. incorrect)
881 * -to boost the performance of I/O dependent domains it would be possible
882 * to put the domain into the runnable queue immediately, and let it run
883 * for the remainder of the slice of the current period
884 * (or even worse: allocate a new full slice for the domain)
885 * -either behaviour can lead to missed deadlines in other domains as
886 * opposed to approaches 1,2a,2b
887 */
888 static inline void unblock_short_vcons
889 (struct sedf_vcpu_info* inf, s_time_t now) {
890 inf->deadl_abs += inf->period;
891 inf->cputime = 0;
892 }
894 static inline void unblock_short_cons(struct sedf_vcpu_info* inf, s_time_t now)
895 {
896 /*treat blocked time as consumed by the domain*/
897 inf->cputime += now - inf->block_abs;
898 if (inf->cputime + EXTRA_QUANTUM > inf->slice) {
899 /*we don't have a reasonable amount of time in
900 our slice left :( => start in next period!*/
901 unblock_short_vcons(inf, now);
902 }
903 #ifdef SEDF_STATS
904 else
905 inf->short_cont++;
906 #endif
907 }
908 static inline void unblock_short_extra_support (struct sedf_vcpu_info* inf,
909 s_time_t now) {
910 /*this unblocking scheme tries to support the domain, by assigning it
911 a priority in extratime distribution according to the loss of time
912 in this slice due to blocking*/
913 s_time_t pen;
915 /*no more realtime execution in this period!*/
916 inf->deadl_abs += inf->period;
917 if (likely(inf->block_abs)) {
918 //treat blocked time as consumed by the domain*/
919 /*inf->cputime += now - inf->block_abs;*/
920 /*penalty is time the domain would have
921 had if it continued to run */
922 pen = (inf->slice - inf->cputime);
923 if (pen < 0) pen = 0;
924 /*accumulate all penalties over the periods*/
925 /*inf->short_block_lost_tot += pen;*/
926 /*set penalty to the current value*/
927 inf->short_block_lost_tot = pen;
928 /*not sure which one is better.. but seems to work well...*/
930 if (inf->short_block_lost_tot) {
931 inf->score[0] = (inf->period << 10) /
932 inf->short_block_lost_tot;
933 #ifdef SEDF_STATS
934 inf->pen_extra_blocks++;
935 #endif
936 if (extraq_on(inf->vcpu, EXTRA_PEN_Q))
937 /*remove domain for possible resorting!*/
938 extraq_del(inf->vcpu, EXTRA_PEN_Q);
939 else
940 /*remember that we want to be on the penalty q
941 so that we can continue when we (un-)block
942 in penalty-extratime*/
943 inf->status |= EXTRA_WANT_PEN_Q;
945 /*(re-)add domain to the penalty extraq*/
946 extraq_add_sort_update(inf->vcpu,
947 EXTRA_PEN_Q, 0);
948 }
949 }
950 /*give it a fresh slice in the next period!*/
951 inf->cputime = 0;
952 }
953 static inline void unblock_long_vcons(struct sedf_vcpu_info* inf, s_time_t now)
954 {
955 /* align to next future period */
956 inf->deadl_abs += (DIV_UP(now - inf->deadl_abs, inf->period) +1)
957 * inf->period;
958 inf->cputime = 0;
959 }
961 static inline void unblock_long_cons_a (struct sedf_vcpu_info* inf,
962 s_time_t now) {
963 /*treat the time the domain was blocked in the
964 CURRENT period as consumed by the domain*/
965 inf->cputime = (now - inf->deadl_abs) % inf->period;
966 if (inf->cputime + EXTRA_QUANTUM > inf->slice) {
967 /*we don't have a reasonable amount of time in our slice
968 left :( => start in next period!*/
969 unblock_long_vcons(inf, now);
970 }
971 }
972 static inline void unblock_long_cons_b(struct sedf_vcpu_info* inf,s_time_t now) {
973 /*Conservative 2b*/
974 /*Treat the unblocking time as a start of a new period */
975 inf->deadl_abs = now + inf->period;
976 inf->cputime = 0;
977 }
978 static inline void unblock_long_cons_c(struct sedf_vcpu_info* inf,s_time_t now) {
979 if (likely(inf->latency)) {
980 /*scale the slice and period accordingly to the latency hint*/
981 /*reduce period temporarily to the latency hint*/
982 inf->period = inf->latency;
983 /*this results in max. 4s slice/period length*/
984 ASSERT((inf->period < ULONG_MAX)
985 && (inf->slice_orig < ULONG_MAX));
986 /*scale slice accordingly, so that utilisation stays the same*/
987 inf->slice = (inf->period * inf->slice_orig)
988 / inf->period_orig;
989 inf->deadl_abs = now + inf->period;
990 inf->cputime = 0;
991 }
992 else {
993 /*we don't have a latency hint.. use some other technique*/
994 unblock_long_cons_b(inf, now);
995 }
996 }
997 /*a new idea of dealing with short blocks: burst period scaling*/
998 static inline void unblock_short_burst(struct sedf_vcpu_info* inf, s_time_t now)
999 {
1000 /*treat blocked time as consumed by the domain*/
1001 inf->cputime += now - inf->block_abs;
1003 if (inf->cputime + EXTRA_QUANTUM <= inf->slice) {
1004 /*if we can still use some time in the current slice
1005 then use it!*/
1006 #ifdef SEDF_STATS
1007 /*we let the domain run in the current period*/
1008 inf->short_cont++;
1009 #endif
1011 else {
1012 /*we don't have a reasonable amount of time in
1013 our slice left => switch to burst mode*/
1014 if (likely(inf->unblock_abs)) {
1015 /*set the period-length to the current blocking
1016 interval, possible enhancements: average over last
1017 blocking intervals, user-specified minimum,...*/
1018 inf->period = now - inf->unblock_abs;
1019 /*check for overflow on multiplication*/
1020 ASSERT((inf->period < ULONG_MAX)
1021 && (inf->slice_orig < ULONG_MAX));
1022 /*scale slice accordingly, so that utilisation
1023 stays the same*/
1024 inf->slice = (inf->period * inf->slice_orig)
1025 / inf->period_orig;
1026 /*set new (shorter) deadline*/
1027 inf->deadl_abs += inf->period;
1029 else {
1030 /*in case we haven't unblocked before
1031 start in next period!*/
1032 inf->cputime=0;
1033 inf->deadl_abs += inf->period;
1036 inf->unblock_abs = now;
1038 static inline void unblock_long_burst(struct sedf_vcpu_info* inf, s_time_t now) {
1039 if (unlikely(inf->latency && (inf->period > inf->latency))) {
1040 /*scale the slice and period accordingly to the latency hint*/
1041 inf->period = inf->latency;
1042 /*check for overflows on multiplication*/
1043 ASSERT((inf->period < ULONG_MAX)
1044 && (inf->slice_orig < ULONG_MAX));
1045 /*scale slice accordingly, so that utilisation stays the same*/
1046 inf->slice = (inf->period * inf->slice_orig)
1047 / inf->period_orig;
1048 inf->deadl_abs = now + inf->period;
1049 inf->cputime = 0;
1051 else {
1052 /*we don't have a latency hint.. or we are currently in
1053 "burst mode": use some other technique
1054 NB: this should be in fact the normal way of operation,
1055 when we are in sync with the device!*/
1056 unblock_long_cons_b(inf, now);
1058 inf->unblock_abs = now;
1061 #define DOMAIN_EDF 1
1062 #define DOMAIN_EXTRA_PEN 2
1063 #define DOMAIN_EXTRA_UTIL 3
1064 #define DOMAIN_IDLE 4
1065 static inline int get_run_type(struct vcpu* d) {
1066 struct sedf_vcpu_info* inf = EDOM_INFO(d);
1067 if (is_idle_task(d->domain))
1068 return DOMAIN_IDLE;
1069 if (inf->status & EXTRA_RUN_PEN)
1070 return DOMAIN_EXTRA_PEN;
1071 if (inf->status & EXTRA_RUN_UTIL)
1072 return DOMAIN_EXTRA_UTIL;
1073 return DOMAIN_EDF;
1075 /*Compares two domains in the relation of whether the one is allowed to
1076 interrupt the others execution.
1077 It returns true (!=0) if a switch to the other domain is good.
1078 Current Priority scheme is as follows:
1079 EDF > L0 (penalty based) extra-time >
1080 L1 (utilization) extra-time > idle-domain
1081 In the same class priorities are assigned as following:
1082 EDF: early deadline > late deadline
1083 L0 extra-time: lower score > higher score*/
1084 static inline int should_switch(struct vcpu* cur,
1085 struct vcpu* other, s_time_t now) {
1086 struct sedf_vcpu_info *cur_inf, *other_inf;
1087 cur_inf = EDOM_INFO(cur);
1088 other_inf = EDOM_INFO(other);
1090 /*check whether we need to make an earlier sched-decision*/
1091 if (PERIOD_BEGIN(other_inf) <
1092 CPU_INFO(other->processor)->current_slice_expires)
1093 return 1;
1094 /*no timing-based switches need to be taken into account here*/
1095 switch (get_run_type(cur)) {
1096 case DOMAIN_EDF:
1097 /* do not interrupt a running EDF domain */
1098 return 0;
1099 case DOMAIN_EXTRA_PEN:
1100 /*check whether we also want
1101 the L0 ex-q with lower score*/
1102 if ((other_inf->status & EXTRA_WANT_PEN_Q)
1103 && (other_inf->score[EXTRA_PEN_Q] <
1104 cur_inf->score[EXTRA_PEN_Q]))
1105 return 1;
1106 else return 0;
1107 case DOMAIN_EXTRA_UTIL:
1108 /*check whether we want the L0 extraq, don't
1109 switch if both domains want L1 extraq */
1110 if (other_inf->status & EXTRA_WANT_PEN_Q)
1111 return 1;
1112 else return 0;
1113 case DOMAIN_IDLE:
1114 return 1;
1116 return 1;
1118 void sedf_wake(struct vcpu *d) {
1119 s_time_t now = NOW();
1120 struct sedf_vcpu_info* inf = EDOM_INFO(d);
1122 PRINT(3, "sedf_wake was called, domain-id %i.%i\n",d->domain->domain_id, d->vcpu_id);
1124 if (unlikely(is_idle_task(d->domain)))
1125 return;
1127 if ( unlikely(__task_on_queue(d)) ) {
1128 PRINT(3,"\tdomain %i.%i is already in some queue\n",
1129 d->domain->domain_id, d->vcpu_id);
1130 return;
1132 ASSERT(!sedf_runnable(d));
1133 inf->status &= ~SEDF_ASLEEP;
1134 ASSERT(!extraq_on(d, EXTRA_UTIL_Q));
1135 ASSERT(!extraq_on(d, EXTRA_PEN_Q));
1137 if (unlikely(inf->deadl_abs == 0))
1138 /*initial setup of the deadline*/
1139 inf->deadl_abs = now + inf->slice;
1141 PRINT(3,"waking up domain %i.%i (deadl= %"PRIu64" period= %"PRIu64" "\
1142 "now= %"PRIu64")\n", d->domain->domain_id, d->vcpu_id, inf->deadl_abs,
1143 inf->period, now);
1144 #ifdef SEDF_STATS
1145 inf->block_tot++;
1146 #endif
1147 if (unlikely(now < PERIOD_BEGIN(inf))) {
1148 PRINT(4,"extratime unblock\n");
1149 /* unblocking in extra-time! */
1150 #if (EXTRA == EXTRA_BLOCK_WEIGHT)
1151 if (inf->status & EXTRA_WANT_PEN_Q) {
1152 /*we have a domain that wants compensation
1153 for block penalty and did just block in
1154 its compensation time. Give it another
1155 chance!*/
1156 extraq_add_sort_update(d, EXTRA_PEN_Q, 0);
1158 #endif
1159 extraq_check_add_unblocked(d, 0);
1161 else {
1162 if (now < inf->deadl_abs) {
1163 PRINT(4,"short unblocking\n");
1164 /*short blocking*/
1165 #ifdef SEDF_STATS
1166 inf->short_block_tot++;
1167 #endif
1168 #if (UNBLOCK <= UNBLOCK_ATROPOS)
1169 unblock_short_vcons(inf, now);
1170 #elif (UNBLOCK == UNBLOCK_SHORT_RESUME)
1171 unblock_short_cons(inf, now);
1172 #elif (UNBLOCK == UNBLOCK_BURST)
1173 unblock_short_burst(inf, now);
1174 #elif (UNBLOCK == UNBLOCK_EXTRA_SUPPORT)
1175 unblock_short_extra_support(inf, now);
1176 #endif
1178 extraq_check_add_unblocked(d, 1);
1180 else {
1181 PRINT(4,"long unblocking\n");
1182 /*long unblocking*/
1183 #ifdef SEDF_STATS
1184 inf->long_block_tot++;
1185 #endif
1186 #if (UNBLOCK == UNBLOCK_ISOCHRONOUS_EDF)
1187 unblock_long_vcons(inf, now);
1188 #elif (UNBLOCK == UNBLOCK_EDF \
1189 || UNBLOCK == UNBLOCK_EXTRA_SUPPORT)
1190 unblock_long_cons_b(inf, now);
1191 #elif (UNBLOCK == UNBLOCK_ATROPOS)
1192 unblock_long_cons_c(inf, now);
1193 #elif (UNBLOCK == UNBLOCK_SHORT_RESUME)
1194 unblock_long_cons_b(inf, now);
1195 /*unblock_short_cons_c(inf, now);*/
1196 #elif (UNBLOCK == UNBLOCK_BURST)
1197 unblock_long_burst(inf, now);
1198 #endif
1200 extraq_check_add_unblocked(d, 1);
1203 PRINT(3,"woke up domain %i.%i (deadl= %"PRIu64" period= %"PRIu64" "\
1204 "now= %"PRIu64")\n", d->domain->domain_id, d->vcpu_id, inf->deadl_abs,
1205 inf->period, now);
1206 if (PERIOD_BEGIN(inf) > now) {
1207 __add_to_waitqueue_sort(d);
1208 PRINT(3,"added to waitq\n");
1210 else {
1211 __add_to_runqueue_sort(d);
1212 PRINT(3,"added to runq\n");
1215 #ifdef SEDF_STATS
1216 /*do some statistics here...*/
1217 if (inf->block_abs != 0) {
1218 inf->block_time_tot += now - inf->block_abs;
1219 inf->penalty_time_tot +=
1220 PERIOD_BEGIN(inf) + inf->cputime - inf->block_abs;
1222 #endif
1223 /*sanity check: make sure each extra-aware domain IS on the util-q!*/
1224 ASSERT(IMPLY(inf->status & EXTRA_AWARE, extraq_on(d, EXTRA_UTIL_Q)));
1225 ASSERT(__task_on_queue(d));
1226 /*check whether the awakened task needs to invoke the do_schedule
1227 routine. Try to avoid unnecessary runs but:
1228 Save approximation: Always switch to scheduler!*/
1229 if (should_switch(schedule_data[d->processor].curr, d, now))
1230 cpu_raise_softirq(d->processor, SCHEDULE_SOFTIRQ);
1233 /*Print a lot of use-{full, less} information about a domains in the system*/
1234 static void sedf_dump_domain(struct vcpu *d) {
1235 printk("%i.%i has=%c ", d->domain->domain_id, d->vcpu_id,
1236 test_bit(_VCPUF_running, &d->vcpu_flags) ? 'T':'F');
1237 printk("p=%"PRIu64" sl=%"PRIu64" ddl=%"PRIu64" w=%hu c=%"PRIu64" sc=%i xtr(%s)=%"PRIu64" ew=%hu",
1238 EDOM_INFO(d)->period, EDOM_INFO(d)->slice, EDOM_INFO(d)->deadl_abs,
1239 EDOM_INFO(d)->weight, d->cpu_time, EDOM_INFO(d)->score[EXTRA_UTIL_Q],
1240 (EDOM_INFO(d)->status & EXTRA_AWARE) ? "yes" : "no",
1241 EDOM_INFO(d)->extra_time_tot, EDOM_INFO(d)->extraweight);
1242 if (d->cpu_time !=0)
1243 printf(" (%"PRIu64"%%)", (EDOM_INFO(d)->extra_time_tot * 100)
1244 / d->cpu_time);
1245 #ifdef SEDF_STATS
1246 if (EDOM_INFO(d)->block_time_tot!=0)
1247 printf(" pen=%"PRIu64"%%", (EDOM_INFO(d)->penalty_time_tot * 100) /
1248 EDOM_INFO(d)->block_time_tot);
1249 if (EDOM_INFO(d)->block_tot!=0)
1250 printf("\n blks=%u sh=%u (%u%%) (shc=%u (%u%%) shex=%i "\
1251 "shexsl=%i) l=%u (%u%%) avg: b=%"PRIu64" p=%"PRIu64"",
1252 EDOM_INFO(d)->block_tot, EDOM_INFO(d)->short_block_tot,
1253 (EDOM_INFO(d)->short_block_tot * 100)
1254 / EDOM_INFO(d)->block_tot, EDOM_INFO(d)->short_cont,
1255 (EDOM_INFO(d)->short_cont * 100) / EDOM_INFO(d)->block_tot,
1256 EDOM_INFO(d)->pen_extra_blocks,
1257 EDOM_INFO(d)->pen_extra_slices,
1258 EDOM_INFO(d)->long_block_tot,
1259 (EDOM_INFO(d)->long_block_tot * 100) / EDOM_INFO(d)->block_tot,
1260 (EDOM_INFO(d)->block_time_tot) / EDOM_INFO(d)->block_tot,
1261 (EDOM_INFO(d)->penalty_time_tot) / EDOM_INFO(d)->block_tot);
1262 #endif
1263 printf("\n");
1266 /*dumps all domains on hte specified cpu*/
1267 static void sedf_dump_cpu_state(int i)
1269 struct list_head *list, *queue, *tmp;
1270 struct sedf_vcpu_info *d_inf;
1271 struct domain *d;
1272 struct vcpu *ed;
1273 int loop = 0;
1275 printk("now=%"PRIu64"\n",NOW());
1276 queue = RUNQ(i);
1277 printk("RUNQ rq %lx n: %lx, p: %lx\n", (unsigned long)queue,
1278 (unsigned long) queue->next, (unsigned long) queue->prev);
1279 list_for_each_safe ( list, tmp, queue ) {
1280 printk("%3d: ",loop++);
1281 d_inf = list_entry(list, struct sedf_vcpu_info, list);
1282 sedf_dump_domain(d_inf->vcpu);
1285 queue = WAITQ(i); loop = 0;
1286 printk("\nWAITQ rq %lx n: %lx, p: %lx\n", (unsigned long)queue,
1287 (unsigned long) queue->next, (unsigned long) queue->prev);
1288 list_for_each_safe ( list, tmp, queue ) {
1289 printk("%3d: ",loop++);
1290 d_inf = list_entry(list, struct sedf_vcpu_info, list);
1291 sedf_dump_domain(d_inf->vcpu);
1294 queue = EXTRAQ(i,EXTRA_PEN_Q); loop = 0;
1295 printk("\nEXTRAQ (penalty) rq %lx n: %lx, p: %lx\n",
1296 (unsigned long)queue, (unsigned long) queue->next,
1297 (unsigned long) queue->prev);
1298 list_for_each_safe ( list, tmp, queue ) {
1299 d_inf = list_entry(list, struct sedf_vcpu_info,
1300 extralist[EXTRA_PEN_Q]);
1301 printk("%3d: ",loop++);
1302 sedf_dump_domain(d_inf->vcpu);
1305 queue = EXTRAQ(i,EXTRA_UTIL_Q); loop = 0;
1306 printk("\nEXTRAQ (utilization) rq %lx n: %lx, p: %lx\n",
1307 (unsigned long)queue, (unsigned long) queue->next,
1308 (unsigned long) queue->prev);
1309 list_for_each_safe ( list, tmp, queue ) {
1310 d_inf = list_entry(list, struct sedf_vcpu_info,
1311 extralist[EXTRA_UTIL_Q]);
1312 printk("%3d: ",loop++);
1313 sedf_dump_domain(d_inf->vcpu);
1316 loop = 0;
1317 printk("\nnot on Q\n");
1318 for_each_domain(d)
1319 for_each_vcpu(d, ed)
1321 if (!__task_on_queue(ed) && (ed->processor == i)) {
1322 printk("%3d: ",loop++);
1323 sedf_dump_domain(ed);
1327 /*Adjusts periods and slices of the domains accordingly to their weights*/
1328 static inline int sedf_adjust_weights(struct sched_adjdom_cmd *cmd) {
1329 struct vcpu *p;
1330 struct domain *d;
1331 int sumw[NR_CPUS];
1332 s_time_t sumt[NR_CPUS];
1333 int cpu;
1335 for (cpu=0; cpu < NR_CPUS; cpu++) {
1336 sumw[cpu] = 0;
1337 sumt[cpu] = 0;
1339 /*sum up all weights*/
1340 for_each_domain(d)
1341 for_each_vcpu(d, p) {
1342 if (EDOM_INFO(p)->weight)
1343 sumw[p->processor] += EDOM_INFO(p)->weight;
1344 else {
1345 /*don't modify domains who don't have a weight, but sum
1346 up the time they need, projected to a WEIGHT_PERIOD,
1347 so that this time is not given to the weight-driven
1348 domains*/
1349 /*check for overflows*/
1350 ASSERT((WEIGHT_PERIOD < ULONG_MAX)
1351 && (EDOM_INFO(p)->slice_orig < ULONG_MAX));
1352 sumt[p->processor] +=
1353 (WEIGHT_PERIOD * EDOM_INFO(p)->slice_orig) /
1354 EDOM_INFO(p)->period_orig;
1357 /*adjust all slices (and periods) to the new weight*/
1358 for_each_domain(d)
1359 for_each_vcpu(d, p) {
1360 if (EDOM_INFO(p)->weight) {
1361 EDOM_INFO(p)->period_orig =
1362 EDOM_INFO(p)->period = WEIGHT_PERIOD;
1363 EDOM_INFO(p)->slice_orig =
1364 EDOM_INFO(p)->slice =
1365 (EDOM_INFO(p)->weight *
1366 (WEIGHT_PERIOD - WEIGHT_SAFETY - sumt[p->processor])) /
1367 sumw[p->processor];
1370 return 0;
1373 /* set or fetch domain scheduling parameters */
1374 static int sedf_adjdom(struct domain *p, struct sched_adjdom_cmd *cmd) {
1375 struct vcpu *v;
1377 PRINT(2,"sedf_adjdom was called, domain-id %i new period %"PRIu64" "\
1378 "new slice %"PRIu64"\nlatency %"PRIu64" extra:%s\n",
1379 p->domain_id, cmd->u.sedf.period, cmd->u.sedf.slice,
1380 cmd->u.sedf.latency, (cmd->u.sedf.extratime)?"yes":"no");
1381 if ( cmd->direction == SCHED_INFO_PUT )
1383 /*check for sane parameters*/
1384 if (!cmd->u.sedf.period && !cmd->u.sedf.weight)
1385 return -EINVAL;
1386 if (cmd->u.sedf.weight) {
1387 if ((cmd->u.sedf.extratime & EXTRA_AWARE) &&
1388 (! cmd->u.sedf.period)) {
1389 /*weight driven domains with xtime ONLY!*/
1390 for_each_vcpu(p, v) {
1391 EDOM_INFO(v)->extraweight = cmd->u.sedf.weight;
1392 EDOM_INFO(v)->weight = 0;
1393 EDOM_INFO(v)->slice = 0;
1394 EDOM_INFO(v)->period = WEIGHT_PERIOD;
1396 } else {
1397 /*weight driven domains with real-time execution*/
1398 for_each_vcpu(p, v)
1399 EDOM_INFO(v)->weight = cmd->u.sedf.weight;
1402 else {
1403 /*time driven domains*/
1404 for_each_vcpu(p, v) {
1405 /* sanity checking! */
1406 if(cmd->u.sedf.slice > cmd->u.sedf.period )
1407 return -EINVAL;
1408 EDOM_INFO(v)->weight = 0;
1409 EDOM_INFO(v)->extraweight = 0;
1410 EDOM_INFO(v)->period_orig =
1411 EDOM_INFO(v)->period = cmd->u.sedf.period;
1412 EDOM_INFO(v)->slice_orig =
1413 EDOM_INFO(v)->slice = cmd->u.sedf.slice;
1416 if (sedf_adjust_weights(cmd))
1417 return -EINVAL;
1419 for_each_vcpu(p, v) {
1420 EDOM_INFO(v)->status =
1421 (EDOM_INFO(v)->status &
1422 ~EXTRA_AWARE) | (cmd->u.sedf.extratime & EXTRA_AWARE);
1423 EDOM_INFO(v)->latency = cmd->u.sedf.latency;
1424 extraq_check(v);
1427 else if ( cmd->direction == SCHED_INFO_GET )
1429 cmd->u.sedf.period = EDOM_INFO(p->vcpu[0])->period;
1430 cmd->u.sedf.slice = EDOM_INFO(p->vcpu[0])->slice;
1431 cmd->u.sedf.extratime = EDOM_INFO(p->vcpu[0])->status
1432 & EXTRA_AWARE;
1433 cmd->u.sedf.latency = EDOM_INFO(p->vcpu[0])->latency;
1434 cmd->u.sedf.weight = EDOM_INFO(p->vcpu[0])->weight;
1436 PRINT(2,"sedf_adjdom_finished\n");
1437 return 0;
1440 struct scheduler sched_sedf_def = {
1441 .name = "Simple EDF Scheduler",
1442 .opt_name = "sedf",
1443 .sched_id = SCHED_SEDF,
1445 .alloc_task = sedf_alloc_task,
1446 .add_task = sedf_add_task,
1447 .free_task = sedf_free_task,
1448 .do_schedule = sedf_do_schedule,
1449 .dump_cpu_state = sedf_dump_cpu_state,
1450 .sleep = sedf_sleep,
1451 .wake = sedf_wake,
1452 .adjdom = sedf_adjdom,
1453 };