ia64/xen-unstable
changeset 4413:af870801ba62
bitkeeper revision 1.1159.170.108 (424c8327NU4_W8SWKkWXALwnntcq3g)
mainly layout changes, but also minor bugfixes along my way
mainly layout changes, but also minor bugfixes along my way
| author | sd386@font.cl.cam.ac.uk |
|---|---|
| date | Thu Mar 31 23:09:27 2005 +0000 (2005-03-31) |
| parents | 046ad36e241a |
| children | e9a82c51b1fc |
| files | xen/common/sched_sedf.c |
line diff
1.1 --- a/xen/common/sched_sedf.c Tue Mar 29 15:57:43 2005 +0000 1.2 +++ b/xen/common/sched_sedf.c Thu Mar 31 23:09:27 2005 +0000 1.3 @@ -13,9 +13,9 @@ 1.4 #include <xen/time.h> 1.5 #include <xen/slab.h> 1.6 1.7 -//#include <xen/adv_sched_hist.h> 1.8 +/*#include <xen/adv_sched_hist.h>*/ 1.9 1.10 -//verbosity settings 1.11 +/*verbosity settings*/ 1.12 #define SEDFLEVEL 0 1.13 #define PRINT(_f, _a...) \ 1.14 if ((_f)<=SEDFLEVEL) printk(_a ); 1.15 @@ -24,7 +24,7 @@ if ((_f)<=SEDFLEVEL) printk(_a ); 1.16 #define SEDF_STATS 1.17 #endif 1.18 1.19 -//various ways of unblocking domains 1.20 +/*various ways of unblocking domains*/ 1.21 #define UNBLOCK_ISOCHRONOUS_EDF 1 1.22 #define UNBLOCK_EDF 2 1.23 #define UNBLOCK_ATROPOS 3 1.24 @@ -33,7 +33,7 @@ if ((_f)<=SEDFLEVEL) printk(_a ); 1.25 #define UNBLOCK_EXTRA_SUPPORT 6 1.26 #define UNBLOCK UNBLOCK_EXTRA_SUPPORT 1.27 1.28 -//various ways of treating extra-time 1.29 +/*various ways of treating extra-time*/ 1.30 #define EXTRA_OFF 1 1.31 #define EXTRA_ROUNDR 2 1.32 #define EXTRA_SLICE_WEIGHT 3 1.33 @@ -63,29 +63,35 @@ struct sedf_dom_info 1.34 struct list_head list; 1.35 struct list_head extralist[2]; 1.36 1.37 - //Parameters for EDF 1.38 - s_time_t period; //=(relative deadline) 1.39 - s_time_t slice; //=worst case execution time 1.40 + /*Parameters for EDF*/ 1.41 + s_time_t period; /*=(relative deadline)*/ 1.42 + s_time_t slice; /*=worst case execution time*/ 1.43 1.44 - //Advaced Parameters 1.45 - //Latency Scaling 1.46 + /*Advaced Parameters*/ 1.47 + /*Latency Scaling*/ 1.48 s_time_t period_orig; 1.49 s_time_t slice_orig; 1.50 s_time_t latency; 1.51 1.52 - short extra; //extra-time status of domain 1.53 - short weight; //weights for "Scheduling for beginners/ lazy/ etc." ;) 1.54 + /*extra-time status of domain*/ 1.55 + short extra; 1.56 + /*weights for "Scheduling for beginners/ lazy/ etc." ;)*/ 1.57 + short weight; 1.58 1.59 - //Bookkeeping 1.60 + /*Bookkeeping*/ 1.61 s_time_t absdead; 1.62 s_time_t sched_start; 1.63 s_time_t cputime; 1.64 - s_time_t absblock; 1.65 - s_time_t absunblock; //time the domain unblocked, used by burst mode to determine unblocking intervals 1.66 - int score[2]; //scores for {util, block penalty}-weighted extratime distribution 1.67 + s_time_t absblock; 1.68 + 1.69 + /*time the domain unblocked, used to determine unblocking intervals*/ 1.70 + s_time_t absunblock; 1.71 + 1.72 + /*scores for {util, block penalty}-weighted extratime distribution*/ 1.73 + int score[2]; 1.74 s_time_t short_block_lost_tot; 1.75 1.76 - //Statistics 1.77 + /*Statistics*/ 1.78 s_time_t extra_time_tot; 1.79 1.80 #ifdef SEDF_STATS 1.81 @@ -107,7 +113,7 @@ struct sedf_cpu_info { 1.82 }; 1.83 1.84 #define DOM_INFO(d) ((struct sedf_dom_info *)((d)->sched_priv)) 1.85 -#define CPU_INFO(cpu) ((struct sedf_cpu_info *)schedule_data[cpu].sched_priv) 1.86 +#define CPU_INFO(cpu) ((struct sedf_cpu_info *)schedule_data[cpu].sched_priv) 1.87 #define LIST(d) (&DOM_INFO(d)->list) 1.88 #define EXTRALIST(d,i) (&(DOM_INFO(d)->extralist[i])) 1.89 #define RUNQ(cpu) (&CPU_INFO(cpu)->runnableq) 1.90 @@ -125,7 +131,8 @@ static xmem_cache_t *dom_info_cache; 1.91 static void sedf_dump_cpu_state(int i); 1.92 1.93 static inline int extraq_on(struct domain *d, int i) { 1.94 - return ((EXTRALIST(d,i)->next != NULL) && (EXTRALIST(d,i)->next != EXTRALIST(d,i))); 1.95 + return ((EXTRALIST(d,i)->next != NULL) && 1.96 + (EXTRALIST(d,i)->next != EXTRALIST(d,i))); 1.97 } 1.98 1.99 static inline void extraq_add_head(struct domain *d, int i) 1.100 @@ -142,7 +149,8 @@ static inline void extraq_del(struct dom 1.101 { 1.102 struct list_head *list = EXTRALIST(d,i); 1.103 /*if (!extraq_on(d,i)) { 1.104 - PRINT(0,"extraq_del: domain %i is NOT on L%i extraq! HALTING\n",d->id,i); 1.105 + PRINT(0,"extraq_del: domain %i is NOT on L%i extraq "\ 1.106 + "HALTING\n",d->id,i); 1.107 sedf_dump_cpu_state(0);(*((int*)0))++; 1.108 }*/ 1.109 PRINT(3, "Removing domain %i from L%i extraq\n", d->id,i); 1.110 @@ -150,55 +158,67 @@ static inline void extraq_del(struct dom 1.111 list->next = NULL; 1.112 } 1.113 1.114 -/* adds a domain to the queue of processes which are aware of extra time. List is sorted by score, 1.115 - where a lower score means higher priority for an extra slice. It also updates the score, by simply subtracting 1.116 - a fixed value from each entry, in order to avoid overflow. The algorithm works by simply charging each domain 1.117 - that recieved extratime with an inverse of its weight. 1.118 +/* adds a domain to the queue of processes which are aware of extra time. List 1.119 + is sorted by score, where a lower score means higher priority for an extra 1.120 + slice. It also updates the score, by simply subtracting a fixed value from 1.121 + each entry, in order to avoid overflow. The algorithm works by simply 1.122 + charging each domain that recieved extratime with an inverse of its weight. 1.123 */ 1.124 static inline void extraq_add_sort_update(struct domain *d, int i, int sub) { 1.125 struct list_head *cur; 1.126 struct sedf_dom_info *curinf; 1.127 1.128 /*if (extraq_on(d,i)) { 1.129 - PRINT(0,"extraq_add_sort_update: domain %i is already on L%i extraq! HALTING\n",d->id,i); 1.130 + PRINT(0,"extraq_add_sort_update: domain %i is already on "\ 1.131 + "L%i extraq! HALTING\n",d->id,i); 1.132 sedf_dump_cpu_state(0);(*((int*)0))++; 1.133 }*/ 1.134 - PRINT(3, "Adding domain %i (score= %i, short_pen= %lli) to L%i extraq\n", d->id, 1.135 - DOM_INFO(d)->score[i], DOM_INFO(d)->short_block_lost_tot, i); 1.136 - //iterate through all elements to find our "hole" and on our way update all the other scores 1.137 + PRINT(3, "Adding domain %i (score= %i, short_pen= %lli) to L%i "\ 1.138 + "extraq\n", d->id, DOM_INFO(d)->score[i], 1.139 + DOM_INFO(d)->short_block_lost_tot, i); 1.140 + /*iterate through all elements to find our "hole" and on our way 1.141 + update all the other scores*/ 1.142 list_for_each(cur,EXTRAQ(d->processor,i)){ 1.143 - curinf = list_entry(cur,struct sedf_dom_info,extralist[i]); 1.144 + curinf = list_entry(cur,struct sedf_dom_info,extralist[i]); 1.145 curinf->score[i] -= sub; 1.146 if (DOM_INFO(d)->score[i] < curinf->score[i]) 1.147 break; 1.148 else 1.149 - PRINT(4,"\tbehind domain %i (score= %i)\n", curinf->owner->id, curinf->score[i]); 1.150 + PRINT(4,"\tbehind domain %i (score= %i)\n", 1.151 + curinf->owner->id, curinf->score[i]); 1.152 } 1.153 - //cur now contains the element, before which we'll enq ueue 1.154 + /*cur now contains the element, before which we'll enqueue*/ 1.155 PRINT(3, "\tlist_add to %x\n", cur->prev); 1.156 list_add(EXTRALIST(d,i),cur->prev); 1.157 1.158 - //continue updating the extraq 1.159 - if ((cur != EXTRAQ(d->processor,i)) && sub) 1.160 - for (cur = cur->next; cur != EXTRAQ(d->processor,i); cur = cur-> next) { 1.161 - curinf = list_entry(cur,struct sedf_dom_info,extralist[i]); 1.162 + /*continue updating the extraq*/ 1.163 + if ((cur != EXTRAQ(d->processor,i)) && sub) 1.164 + for (cur = cur->next; cur != EXTRAQ(d->processor,i); 1.165 + cur = cur-> next) { 1.166 + curinf = list_entry(cur,struct sedf_dom_info, 1.167 + extralist[i]); 1.168 curinf->score[i] -= sub; 1.169 - PRINT(4, "\tupdating domain %i (score= %llu)\n", curinf->owner->id, curinf->score[i]); 1.170 + PRINT(4, "\tupdating domain %i (score= %llu)\n", 1.171 + curinf->owner->id, curinf->score[i]); 1.172 } 1.173 } 1.174 static inline void extraq_check(struct domain *d) { 1.175 if (extraq_on(d, EXTRA_UTIL_Q)) { 1.176 PRINT(2,"Dom %i is on extraQ\n",d->id); 1.177 - if (!(DOM_INFO(d)->extra & EXTRA_AWARE) && !extra_runs(DOM_INFO(d))) { 1.178 + if (!(DOM_INFO(d)->extra & EXTRA_AWARE) && 1.179 + !extra_runs(DOM_INFO(d))) { 1.180 extraq_del(d, EXTRA_UTIL_Q); 1.181 PRINT(2,"Removed dom %i from L1 extraQ\n",d->id); 1.182 } 1.183 } else { 1.184 PRINT(2,"Dom %i is NOT on L1 extraQ\n",d->id); 1.185 - if ((DOM_INFO(d)->extra & EXTRA_AWARE) && domain_runnable(d)) { 1.186 + if ((DOM_INFO(d)->extra & EXTRA_AWARE) && domain_runnable(d)) 1.187 + { 1.188 #if (EXTRA == EXTRA_ROUNDR) 1.189 - extraq_add_tail(d, EXTRA_UTIL_Q); //Favour domains which got short unblocked 1.190 - #elif (EXTRA == EXTRA_SLICE_WEIGHT || EXTRA == EXTRA_BLOCK_WEIGHT) 1.191 + /*Favour domains which got short unblocked*/ 1.192 + extraq_add_tail(d, EXTRA_UTIL_Q); 1.193 + #elif (EXTRA == EXTRA_SLICE_WEIGHT || \ 1.194 + EXTRA == EXTRA_BLOCK_WEIGHT) 1.195 extraq_add_sort_update(d, EXTRA_UTIL_Q, 0); 1.196 #elif 1.197 ; 1.198 @@ -210,52 +230,61 @@ static inline void extraq_check(struct d 1.199 static inline void __del_from_queue(struct domain *d) 1.200 { 1.201 struct list_head *list = LIST(d); 1.202 - PRINT(3,"Removing domain %i (bop= %llu) from runq/waitq\n",d->id,PERIOD_BEGIN(DOM_INFO(d))); 1.203 + PRINT(3,"Removing domain %i (bop= %llu) from runq/waitq\n", d->id, 1.204 + PERIOD_BEGIN(DOM_INFO(d))); 1.205 list_del(list); 1.206 list->next = NULL; 1.207 } 1.208 1.209 -/* adds a domain to the queue of processes which wait for the beginning of the next period 1.210 - * this list is therefore sortet by this time, which is simply absol. deadline - period 1.211 +/* adds a domain to the queue of processes which wait for the beginning of the 1.212 + next period; this list is therefore sortet by this time, which is simply 1.213 + absol. deadline - period 1.214 */ 1.215 static inline void __add_to_waitqueue_sort(struct domain *d) { 1.216 struct list_head *cur; 1.217 struct sedf_dom_info *curinf; 1.218 1.219 - PRINT(3,"Adding domain %i (bop= %llu) to waitq\n",d->id,PERIOD_BEGIN(DOM_INFO(d))); 1.220 - //iterate through all elements to find our "hole" 1.221 + PRINT(3,"Adding domain %i (bop= %llu) to waitq\n", d->id, 1.222 + PERIOD_BEGIN(DOM_INFO(d))); 1.223 + 1.224 + /*iterate through all elements to find our "hole"*/ 1.225 list_for_each(cur,WAITQ(d->processor)){ 1.226 curinf = list_entry(cur,struct sedf_dom_info,list); 1.227 if (PERIOD_BEGIN(DOM_INFO(d)) < PERIOD_BEGIN(curinf)) 1.228 break; 1.229 else 1.230 - PRINT(4,"\tbehind domain %i (bop= %llu)\n",curinf->owner->id,PERIOD_BEGIN(curinf)); 1.231 + PRINT(4,"\tbehind domain %i (bop= %llu)\n", 1.232 + curinf->owner->id, PERIOD_BEGIN(curinf)); 1.233 } 1.234 - //cur now contains the element, before which we'll enqueue 1.235 + /*cur now contains the element, before which we'll enqueue*/ 1.236 PRINT(3,"\tlist_add to %x\n",cur->prev); 1.237 list_add(LIST(d),cur->prev); 1.238 1.239 } 1.240 1.241 -/* adds a domain to the queue of processes which have started their current period and are 1.242 - * runnable (i.e. not blocked, dieing,...). The first element on this list is running on the processor, 1.243 - * if the list is empty the idle task will run. As we are implementing EDF, this list is sorted by 1.244 - * deadlines. 1.245 +/* adds a domain to the queue of processes which have started their current 1.246 + period and are runnable (i.e. not blocked, dieing,...). The first element 1.247 + on this list is running on the processor, if the list is empty the idle 1.248 + task will run. As we are implementing EDF, this list is sorted by deadlines. 1.249 */ 1.250 static inline void __add_to_runqueue_sort(struct domain *d) { 1.251 struct list_head *cur; 1.252 struct sedf_dom_info *curinf; 1.253 1.254 - PRINT(3,"Adding domain %i (deadl= %llu) to runq\n",d->id,DOM_INFO(d)->absdead); 1.255 - //iterate through all elements to find our "hole" 1.256 - list_for_each(cur,RUNQ(d->processor)){ 1.257 - curinf = list_entry(cur,struct sedf_dom_info,list); 1.258 + PRINT(3,"Adding domain %i (deadl= %llu) to runq\n", d->id, 1.259 + DOM_INFO(d)->absdead); 1.260 + 1.261 + /*iterate through all elements to find our "hole"*/ 1.262 + list_for_each(cur, RUNQ(d->processor)) { 1.263 + curinf = list_entry(cur, struct sedf_dom_info, list); 1.264 if (DOM_INFO(d)->absdead < curinf->absdead) 1.265 break; 1.266 else 1.267 - PRINT(4,"\tbehind domain %i (deadl= %llu)\n",curinf->owner->id,curinf->absdead); 1.268 + PRINT(4,"\tbehind domain %i (deadl= %llu)\n", 1.269 + curinf->owner->id, curinf->absdead); 1.270 } 1.271 - //cur now contains the element, before which we'll enqueue 1.272 + 1.273 + /*cur now contains the element, before which we'll enqueue*/ 1.274 PRINT(3,"\tlist_add to %x\n",cur->prev); 1.275 list_add(LIST(d),cur->prev); 1.276 1.277 @@ -270,7 +299,8 @@ static int sedf_init_scheduler() { 1.278 PRINT(2,"sedf_init_scheduler was called\n"); 1.279 1.280 for ( i = 0; i < NR_CPUS; i++ ) { 1.281 - schedule_data[i].sched_priv = xmalloc(sizeof(struct sedf_cpu_info)); 1.282 + schedule_data[i].sched_priv = 1.283 + xmalloc(sizeof(struct sedf_cpu_info)); 1.284 if ( schedule_data[i].sched_priv == NULL ) 1.285 return -1; 1.286 INIT_LIST_HEAD(WAITQ(i)); 1.287 @@ -278,14 +308,15 @@ static int sedf_init_scheduler() { 1.288 INIT_LIST_HEAD(EXTRAQ(i,EXTRA_PEN_Q)); 1.289 INIT_LIST_HEAD(EXTRAQ(i,EXTRA_UTIL_Q)); 1.290 } 1.291 - dom_info_cache = xmem_cache_create("SEDF dom info", sizeof(struct sedf_dom_info), 0, 0, 0, NULL); 1.292 + dom_info_cache = xmem_cache_create("SEDF dom info", 1.293 + sizeof(struct sedf_dom_info), 0, 0, 0, NULL); 1.294 if ( dom_info_cache == NULL ) 1.295 { 1.296 printk("Could not allocate SLAB cache.\n"); 1.297 return -1; 1.298 } 1.299 1.300 - return 0; 1.301 + return 0; 1.302 } 1.303 1.304 /* Allocates memory for per domain private scheduling data*/ 1.305 @@ -300,21 +331,20 @@ static int sedf_alloc_task(struct domain 1.306 /* Setup the sedf_dom_info */ 1.307 static void sedf_add_task(struct domain *d) 1.308 { 1.309 - //s_time_t now=NOW(); 1.310 struct sedf_dom_info *inf=DOM_INFO(d); 1.311 inf->owner = d; 1.312 1.313 PRINT(2,"sedf_add_task was called, domain-id %i\n",d->id); 1.314 if (d->id==0) { 1.315 - //set dom0 to something useful to boot the machine 1.316 + /*set dom0 to something useful to boot the machine*/ 1.317 inf->period = MILLISECS(20); 1.318 inf->slice = MILLISECS(15); 1.319 inf->latency = 0; 1.320 inf->absdead = 0; 1.321 - inf->extra = EXTRA_NONE;//EXTRA_AWARE; 1.322 + inf->extra = EXTRA_NONE;/*EXTRA_AWARE; */ 1.323 } 1.324 else { 1.325 - //other domains run in best effort mode 1.326 + /*other domains run in best effort mode*/ 1.327 inf->period = MILLISECS(20); 1.328 inf->slice = 0; 1.329 inf->absdead = 0; 1.330 @@ -344,50 +374,64 @@ static int sedf_init_idle_task(struct do 1.331 sedf_add_task(d); 1.332 DOM_INFO(d)->absdead = 0; 1.333 set_bit(DF_RUNNING, &d->flags); 1.334 - //the idle task doesn't have to turn up on any list... 1.335 + /*the idle task doesn't have to turn up on any list...*/ 1.336 return 0; 1.337 } 1.338 1.339 /* handles the rescheduling, bookkeeping of domains running in their realtime-time :)*/ 1.340 static inline void desched_edf_dom (s_time_t now, struct domain* d) { 1.341 struct sedf_dom_info* inf = DOM_INFO(d); 1.342 + /*current domain is running in real time mode*/ 1.343 1.344 - //current domain is running in real time mode 1.345 - inf->cputime += now - inf->sched_start; //update the domains cputime 1.346 - if ((inf->cputime < inf->slice) && domain_runnable(d)) //scheduling decisions, which don't remove the running domain from the runq 1.347 - return; //there is nothing to do with the running task 1.348 + /*update the domains cputime*/ 1.349 + inf->cputime += now - inf->sched_start; 1.350 + 1.351 + /*scheduling decisions, which don't remove the running domain 1.352 + from the runq*/ 1.353 + if ((inf->cputime < inf->slice) && domain_runnable(d)) 1.354 + return; 1.355 1.356 __del_from_queue(d); 1.357 /*if (__task_on_queue(current)) { 1.358 - PRINT(0,"domain %i was removed but still on run/waitq => HALT\n",current->id); 1.359 + PRINT(0,"domain %i was removed but still on run/waitq => "\ 1.360 + "HALT\n",current->id); 1.361 sedf_dump_cpu_state(0);(*((int*)0))++; 1.362 }*/ 1.363 1.364 - //manage bookkeeping (i.e. calculate next deadline, memorize overun time of slice) of finished domains 1.365 + /*manage bookkeeping (i.e. calculate next deadline, 1.366 + memorize overun-time of slice) of finished domains*/ 1.367 if (inf->cputime >= inf->slice) { 1.368 inf->cputime -= inf->slice; 1.369 1.370 if (inf->period < inf->period_orig) { 1.371 - //this domain runs in latency scaling or burst mode 1.372 + /*this domain runs in latency scaling or burst mode*/ 1.373 #if (UNBLOCK == UNBLOCK_BURST) 1.374 if (now - inf->absunblock >= 2 * inf->period) 1.375 #endif 1.376 { 1.377 inf->period *= 2; inf->slice *= 2; 1.378 - if ((inf->period > inf->period_orig) || (inf->slice > inf->slice_orig)) { 1.379 - inf->period = inf->period_orig; //update the domains cputime 1.380 + if ((inf->period > inf->period_orig) || 1.381 + (inf->slice > inf->slice_orig)) { 1.382 + /*reset slice & period*/ 1.383 + inf->period = inf->period_orig; 1.384 inf->slice = inf->slice_orig; 1.385 } 1.386 } 1.387 } 1.388 - inf->absdead += inf->period; //set next deadline 1.389 + /*set next deadline*/ 1.390 + inf->absdead += inf->period; 1.391 } 1.392 - //if (inf->absdead<now); 1.393 - //printk("Domain %i exceeded it't deadline!!!! (now: %llu ddl: %llu)\n",current->id,now,inf->absdead); 1.394 - if (domain_runnable(d)) //add a runnable domain to the waitqueue 1.395 + /*if (inf->absdead<now) 1.396 + printk("Domain %i exceeded it't deadline!!!! "\ 1.397 + "(now: %llu ddl: %llu)\n", current->id, now, 1.398 + inf->absdead);*/ 1.399 + 1.400 + /*add a runnable domain to the waitqueue*/ 1.401 + if (domain_runnable(d)) 1.402 __add_to_waitqueue_sort(d); 1.403 else { 1.404 - inf->absblock = now; //we have a blocked realtime task 1.405 + /*we have a blocked realtime task*/ 1.406 + inf->absblock = now; 1.407 #if (EXTRA > EXTRA_OFF) 1.408 #if (EXTRA == EXTRA_BLOCK_WEIGHT) 1.409 if (extraq_on(d,EXTRA_PEN_Q)) extraq_del(d,EXTRA_PEN_Q); 1.410 @@ -398,15 +442,17 @@ static inline void desched_edf_dom (s_ti 1.411 } 1.412 1.413 /* Update all elements on the queues */ 1.414 -static inline void update_queues(s_time_t now, struct list_head* runq, struct list_head* waitq) { 1.415 +static inline void update_queues( 1.416 +s_time_t now, struct list_head* runq, struct list_head* waitq) { 1.417 struct list_head *cur,*tmp; 1.418 struct sedf_dom_info *curinf; 1.419 1.420 PRINT(3,"Updating waitq..\n"); 1.421 - //check for the first elements of the waitqueue, whether their next period has already started 1.422 - list_for_each_safe(cur,tmp,waitq) { 1.423 - curinf = list_entry(cur,struct sedf_dom_info,list); 1.424 - PRINT(4,"\tLooking @ dom %i\n",curinf->owner->id); 1.425 + /*check for the first elements of the waitqueue, whether their 1.426 + next period has already started*/ 1.427 + list_for_each_safe(cur, tmp, waitq) { 1.428 + curinf = list_entry(cur, struct sedf_dom_info, list); 1.429 + PRINT(4,"\tLooking @ dom %i\n", curinf->owner->id); 1.430 if (PERIOD_BEGIN(curinf) <= now) { 1.431 __del_from_queue(curinf->owner); 1.432 __add_to_runqueue_sort(curinf->owner); 1.433 @@ -416,29 +462,51 @@ static inline void update_queues(s_time_ 1.434 } 1.435 1.436 PRINT(3,"Updating runq..\n"); 1.437 - //process the runq, find domains that are on the runqueue which shouldn't be there 1.438 - list_for_each_safe(cur,tmp,runq) { 1.439 + /*process the runq, find domains that are on 1.440 + the runqueue which shouldn't be there*/ 1.441 + list_for_each_safe(cur, tmp, runq) { 1.442 curinf = list_entry(cur,struct sedf_dom_info,list); 1.443 - PRINT(4,"\tLooking @ dom %i\n",curinf->owner->id); 1.444 - if (unlikely(curinf->slice == 0)) { //ignore domains with empty slice 1.445 - PRINT(4,"\tUpdating zero-slice domain %i\n",curinf->owner->id); 1.446 + PRINT(4,"\tLooking @ dom %i\n", curinf->owner->id); 1.447 + if (unlikely(curinf->slice == 0)) { 1.448 + /*ignore domains with empty slice*/ 1.449 + PRINT(4,"\tUpdating zero-slice domain %i\n", 1.450 + curinf->owner->id); 1.451 __del_from_queue(curinf->owner); 1.452 - curinf->absdead += curinf->period; //move to their next period 1.453 - __add_to_waitqueue_sort(curinf->owner); //and put them back into the queue 1.454 + 1.455 + /*move them to their next period*/ 1.456 + curinf->absdead += curinf->period; 1.457 + /*and put them back into the queue*/ 1.458 + __add_to_waitqueue_sort(curinf->owner); 1.459 } 1.460 else { 1.461 - if (unlikely((curinf->absdead < now) || (curinf->cputime > curinf->slice))) { 1.462 - //we missed the deadline or the slice was already finished... might hapen because of dom_adj. 1.463 - //printk("Ouch! Domain %i missed deadline %llu\n",curinf->owner->id,curinf->absdead); 1.464 - PRINT(4,"\tDomain %i exceeded it's deadline/slice (%llu / %llu) now: %llu cputime: %llu\n", 1.465 - curinf->owner->id, curinf->absdead, curinf->slice, now, curinf->cputime); 1.466 + if (unlikely((curinf->absdead < now) || 1.467 + (curinf->cputime > curinf->slice))) { 1.468 + /*we missed the deadline or the slice was 1.469 + already finished... might hapen because 1.470 + of dom_adj.*/ 1.471 + PRINT(4,"\tDomain %i exceeded it's deadline/"\ 1.472 + "slice (%llu / %llu) now: %llu "\ 1.473 + "cputime: %llu\n", curinf->owner->id, 1.474 + curinf->absdead, curinf->slice, now, 1.475 + curinf->cputime); 1.476 __del_from_queue(curinf->owner); 1.477 - curinf->absdead += curinf->period; //common case: we miss one period! 1.478 + /*common case: we miss one period!*/ 1.479 + curinf->absdead += curinf->period; 1.480 + 1.481 + /*if we are still behind: modulo arithmetic, 1.482 + force deadline to be in future and 1.483 + aligned to period borders!*/ 1.484 if (unlikely(curinf->absdead < now)) 1.485 - curinf->absdead += DIV_UP(now - curinf->absdead, curinf->period) * curinf->period; 1.486 - //force start of period to be in future and aligned to period borders! 1.487 - curinf->cputime = 0; //give a fresh slice 1.488 - __add_to_runqueue_sort(curinf->owner); 1.489 + curinf->absdead += 1.490 + DIV_UP(now - curinf->absdead, 1.491 + curinf->period) * curinf->period; 1.492 + 1.493 + /*give a fresh slice*/ 1.494 + curinf->cputime = 0; 1.495 + if (PERIOD_BEGIN(curinf) < now) 1.496 + __add_to_waitqueue_sort(curinf->owner); 1.497 + else 1.498 + __add_to_runqueue_sort(curinf->owner); 1.499 } 1.500 else 1.501 break; 1.502 @@ -448,10 +516,12 @@ static inline void update_queues(s_time_ 1.503 } 1.504 1.505 #if (EXTRA > EXTRA_OFF) 1.506 -/*removes a domain from the head of the according extraQ and requeues it at a specified position: 1.507 - round-robin extratime: end of extraQ 1.508 - weighted ext.: insert in sorted list by score 1.509 - if the domain is blocked / has regained its short-block-loss time it is not put on any queue*/ 1.510 +/* removes a domain from the head of the according extraQ and 1.511 + requeues it at a specified position: 1.512 + round-robin extratime: end of extraQ 1.513 + weighted ext.: insert in sorted list by score 1.514 + if the domain is blocked / has regained its short-block-loss 1.515 + time it is not put on any queue */ 1.516 static inline void desched_extra_dom(s_time_t now, struct domain* d) { 1.517 struct sedf_dom_info *inf = DOM_INFO(d); 1.518 int i = extra_get_cur_q(inf); 1.519 @@ -459,66 +529,92 @@ static inline void desched_extra_dom(s_t 1.520 #if (EXTRA == EXTRA_SLICE_WEIGHT || EXTRA == EXTRA_BLOCK_WEIGHT) 1.521 unsigned long oldscore; 1.522 #endif 1.523 - 1.524 - inf->extra &= ~(EXTRA_RUN_PEN | EXTRA_RUN_UTIL); //unset all running flags 1.525 - inf->cputime = 0; //fresh slice for the next run 1.526 - inf->extra_time_tot += now - inf->sched_start; //accumulate total extratime 1.527 - extraq_del(d, i); //remove extradomain from head of the queue 1.528 + 1.529 + /*unset all running flags*/ 1.530 + inf->extra &= ~(EXTRA_RUN_PEN | EXTRA_RUN_UTIL); 1.531 + /*fresh slice for the next run*/ 1.532 + inf->cputime = 0; 1.533 + /*accumulate total extratime*/ 1.534 + inf->extra_time_tot += now - inf->sched_start; 1.535 + /*remove extradomain from head of the queue*/ 1.536 + extraq_del(d, i); 1.537 1.538 #if (EXTRA == EXTRA_ROUNDR) 1.539 if (domain_runnable(d)) 1.540 - extraq_add_tail(d, EXTRA_UTIL_Q); //and add to the tail if it is runnable => round-robin 1.541 + /*add to the tail if it is runnable => round-robin*/ 1.542 + extraq_add_tail(d, EXTRA_UTIL_Q); 1.543 #elif (EXTRA == EXTRA_SLICE_WEIGHT || EXTRA == EXTRA_BLOCK_WEIGHT) 1.544 - oldscore = inf->score[i]; //update the score 1.545 + /*update the score*/ 1.546 + oldscore = inf->score[i]; 1.547 #if (EXTRA == EXTRA_BLOCK_WEIGHT) 1.548 if (i == EXTRA_PEN_Q) { 1.549 - //domain was running in L0 extraq 1.550 - //inf->short_block_lost_tot -= EXTRA_QUANTUM; //reduce block lost, probably more sophistication here! 1.551 + /*domain was running in L0 extraq*/ 1.552 + /*reduce block lost, probably more sophistication here!*/ 1.553 + /*inf->short_block_lost_tot -= EXTRA_QUANTUM;*/ 1.554 inf->short_block_lost_tot -= now - inf->sched_start; 1.555 - PRINT(3,"Domain %i: Short_block_lost: %lli\n",inf->owner->id,inf->short_block_lost_tot); 1.556 + PRINT(3,"Domain %i: Short_block_lost: %lli\n", 1.557 + inf->owner->id, inf->short_block_lost_tot); 1.558 if (inf->short_block_lost_tot <= 0) { 1.559 PRINT(4,"Domain %i compensated short block loss!\n"); 1.560 - inf->short_block_lost_tot = 0; //we have (over-)compensated our block penalty 1.561 - inf->extra &= ~EXTRA_WANT_PEN_Q; //we don't want a place on the penalty queue anymore! 1.562 - return; //do not add us on this block extraq again! 1.563 + /*we have (over-)compensated our block penalty*/ 1.564 + inf->short_block_lost_tot = 0; 1.565 + /*we don't want a place on the penalty queue anymore!*/ 1.566 + inf->extra &= ~EXTRA_WANT_PEN_Q; 1.567 + /*do not add us on this block extraq again!*/ 1.568 + return; 1.569 } 1.570 - //we have to go again for another try in the block-extraq 1.571 - inf->score[EXTRA_PEN_Q] = (inf->period << 10) / inf->short_block_lost_tot; 1.572 + /*we have to go again for another try in the block-extraq, 1.573 + the score is not used incremantally here, as this is 1.574 + already done by recalculating the block_lost*/ 1.575 + inf->score[EXTRA_PEN_Q] = (inf->period << 10) / 1.576 + inf->short_block_lost_tot; 1.577 oldscore = 0; 1.578 } else 1.579 #endif 1.580 { 1.581 - //domain was running in L1 extraq => score is inverse of utilization and is used somewhat incremental! 1.582 + /*domain was running in L1 extraq => score is inverse of 1.583 + utilization and is used somewhat incremental!*/ 1.584 if (inf->slice) 1.585 - inf->score[EXTRA_UTIL_Q] = (inf->period << 10) / inf->slice;//use fixed point arithmetic with 10 bits 1.586 + /*NB: use fixed point arithmetic with 10 bits*/ 1.587 + inf->score[EXTRA_UTIL_Q] = (inf->period << 10) / 1.588 + inf->slice; 1.589 else 1.590 + /*set best effort domains to the maximum value*/ 1.591 inf->score[EXTRA_UTIL_Q] = 2^10; 1.592 } 1.593 if (domain_runnable(d)) 1.594 - extraq_add_sort_update(d, i, oldscore); //add according to score: weighted round robin 1.595 + /*add according to score: weighted round robin*/ 1.596 + extraq_add_sort_update(d, i, oldscore); 1.597 else { 1.598 inf->absblock = now; 1.599 /*if (!__task_on_queue(d)) 1.600 - printf("Oops... We attempt to remove d %i from the waitq, but it is not on :(\n",d->id);*/ 1.601 - __del_from_queue(d); //also remove this blocked domain from the waitq! 1.602 - //make sure that we remove a blocked domain from the other extraq aswell (this caused hours of debugging!) 1.603 + printf("Oops... We attempt to remove d %i from the "\ 1.604 + "waitq, but it is not on :(\n",d->id);*/ 1.605 + /*remove this blocked domain from the waitq!*/ 1.606 + __del_from_queue(d); 1.607 + /*make sure that we remove a blocked domain from the other 1.608 + extraq aswell (this caused hours of debugging!)*/ 1.609 #if (EXTRA == EXTRA_BLOCK_WEIGHT) 1.610 if (i == EXTRA_PEN_Q) { 1.611 - if (extraq_on(d,EXTRA_UTIL_Q)) extraq_del(d,EXTRA_UTIL_Q); 1.612 + if (extraq_on(d,EXTRA_UTIL_Q)) 1.613 + extraq_del(d,EXTRA_UTIL_Q); 1.614 } 1.615 else { 1.616 - if (extraq_on(d,EXTRA_PEN_Q)) extraq_del(d,EXTRA_PEN_Q); 1.617 + if (extraq_on(d,EXTRA_PEN_Q)) 1.618 + extraq_del(d,EXTRA_PEN_Q); 1.619 } 1.620 #endif 1.621 } 1.622 #endif 1.623 /*if (!domain_runnable(d)) { 1.624 if (extraq_on(d,EXTRA_UTIL_Q)) { 1.625 - PRINT(0,"domain %i is blocked but still on L1 xq=> HALT\n",d->id); 1.626 + PRINT(0,"domain %i is blocked but still on L1 "\ 1.627 + "xq=> HALT\n",d->id); 1.628 sedf_dump_cpu_state(0);(*((int*)0))++; 1.629 } 1.630 if (__task_on_queue(d)) { 1.631 - PRINT(0,"domain %i is blocked but still on run/waitq=> HALT\n",d->id); 1.632 + PRINT(0,"domain %i is blocked but still on run/waitq"\ 1.633 + "=> HALT\n",d->id); 1.634 sedf_dump_cpu_state(0);(*((int*)0))++; 1.635 } 1.636 }*/ 1.637 @@ -526,27 +622,31 @@ static inline void desched_extra_dom(s_t 1.638 #endif 1.639 1.640 1.641 -static inline task_slice_t sedf_do_extra_schedule(s_time_t now, s_time_t end_xt, struct list_head *extraq[], int cpu) { 1.642 +static inline task_slice_t sedf_do_extra_schedule 1.643 +(s_time_t now, s_time_t end_xt, struct list_head *extraq[], int cpu) { 1.644 task_slice_t ret; 1.645 struct sedf_dom_info *runinf; 1.646 - //TODO write this stuff as a loop 1.647 1.648 if (end_xt - now < EXTRA_QUANTUM) 1.649 goto return_idle; 1.650 - 1.651 +#if (EXTRA == EXTRA_BLOCK_WEIGHT) 1.652 if (!list_empty(extraq[EXTRA_PEN_Q])) { 1.653 - //we still have elements on the level 0 extraq => let those run first! 1.654 - runinf = list_entry(extraq[EXTRA_PEN_Q]->next, struct sedf_dom_info, extralist[EXTRA_PEN_Q]); 1.655 + /*we still have elements on the level 0 extraq 1.656 + => let those run first!*/ 1.657 + runinf = list_entry(extraq[EXTRA_PEN_Q]->next, 1.658 + struct sedf_dom_info, extralist[EXTRA_PEN_Q]); 1.659 runinf->extra |= EXTRA_RUN_PEN; 1.660 ret.task = runinf->owner; 1.661 ret.time = EXTRA_QUANTUM; 1.662 #ifdef SEDF_STATS 1.663 runinf->pen_extra_slices++; 1.664 #endif 1.665 - } 1.666 - else if (!list_empty(extraq[EXTRA_UTIL_Q])) { 1.667 - //use elements from the normal extraqueue 1.668 - runinf = list_entry(extraq[EXTRA_UTIL_Q]->next,struct sedf_dom_info,extralist[EXTRA_UTIL_Q]); 1.669 + } else 1.670 +#endif 1.671 + if (!list_empty(extraq[EXTRA_UTIL_Q])) { 1.672 + /*use elements from the normal extraqueue*/ 1.673 + runinf = list_entry(extraq[EXTRA_UTIL_Q]->next, 1.674 + struct sedf_dom_info,extralist[EXTRA_UTIL_Q]); 1.675 runinf->extra |= EXTRA_RUN_UTIL; 1.676 ret.task = runinf->owner; 1.677 ret.time = EXTRA_QUANTUM; 1.678 @@ -562,10 +662,10 @@ return_idle: 1.679 return ret; 1.680 } 1.681 /* Main scheduling function 1.682 - * Reasons for calling this function are: 1.683 - * -timeslice for the current period used up 1.684 - * -domain on waitqueue has started it's period 1.685 - * -and various others ;) in general: determine which domain to run next*/ 1.686 + Reasons for calling this function are: 1.687 + -timeslice for the current period used up 1.688 + -domain on waitqueue has started it's period 1.689 + -and various others ;) in general: determine which domain to run next*/ 1.690 static task_slice_t sedf_do_schedule(s_time_t now) 1.691 { 1.692 int cpu = current->processor; 1.693 @@ -573,48 +673,56 @@ static task_slice_t sedf_do_schedule(s_t 1.694 struct list_head *waitq = WAITQ(cpu); 1.695 #if (EXTRA > EXTRA_OFF) 1.696 struct sedf_dom_info *inf = DOM_INFO(current); 1.697 - struct list_head *extraq[] = {EXTRAQ(cpu,EXTRA_PEN_Q),EXTRAQ(cpu, EXTRA_UTIL_Q)}; 1.698 + struct list_head *extraq[] = {EXTRAQ(cpu,EXTRA_PEN_Q), 1.699 + EXTRAQ(cpu, EXTRA_UTIL_Q)}; 1.700 #endif 1.701 task_slice_t ret; 1.702 - //int i = 0; 1.703 - //idle tasks don't need any of the following stuf 1.704 + /*int i = 0;*/ 1.705 + /*idle tasks don't need any of the following stuf*/ 1.706 if (is_idle_task(current)) 1.707 - goto check_waitq; //idle task doesn't get moved around on any queues 1.708 + goto check_waitq; 1.709 1.710 #if (EXTRA > EXTRA_OFF) 1.711 if (unlikely(extra_runs(inf))) { 1.712 - //i=1; 1.713 - desched_extra_dom(now, current); //special treatment of domains running in extra time 1.714 + /*i=1;*/ 1.715 + /*special treatment of domains running in extra time*/ 1.716 + desched_extra_dom(now, current); 1.717 } 1.718 else 1.719 #endif 1.720 { 1.721 - //i=2; 1.722 + /*i=2;*/ 1.723 desched_edf_dom(now, current); 1.724 } 1.725 /*if (!domain_runnable(current)) { 1.726 if (extraq_on(current,EXTRA_UTIL_Q)) { 1.727 - PRINT(0,"domain %i is blocked but still on L1 xq branch %i=> HALT\n",current->id,i); 1.728 + PRINT(0,"domain %i is blocked but still on L1 xq"\ 1.729 + " branch %i=> HALT\n", current->id, i); 1.730 sedf_dump_cpu_state(0);(*((int*)0))++; 1.731 } 1.732 if (__task_on_queue(current)) { 1.733 - PRINT(0,"domain %i is blocked but still on run/waitq branch %i=> HALT\n",current->id,i); 1.734 + PRINT(0,"domain %i is blocked but still on run/waitq"\ 1.735 + " branch %i=> HALT\n",current->id,i); 1.736 sedf_dump_cpu_state(0);(*((int*)0))++; 1.737 } 1.738 }*/ 1.739 check_waitq: 1.740 update_queues(now, runq, waitq); 1.741 1.742 - //now simply pick the first domain from the runqueue 1.743 + /*now simply pick the first domain from the runqueue*/ 1.744 struct sedf_dom_info *runinf, *waitinf; 1.745 1.746 if (!list_empty(runq)) { 1.747 runinf = list_entry(runq->next,struct sedf_dom_info,list); 1.748 ret.task = runinf->owner; 1.749 if (!list_empty(waitq)) { 1.750 - //rerun scheduler, when scheduled domain reaches it's end of slice or the first domain from the waitqueue gets ready 1.751 - waitinf = list_entry(waitq->next,struct sedf_dom_info,list); 1.752 - ret.time = MIN(now + runinf->slice - runinf->cputime,PERIOD_BEGIN(waitinf)) - now; 1.753 + waitinf = list_entry(waitq->next, 1.754 + struct sedf_dom_info,list); 1.755 + /*rerun scheduler, when scheduled domain reaches it's 1.756 + end of slice or the first domain from the waitqueue 1.757 + gets ready*/ 1.758 + ret.time = MIN(now + runinf->slice - runinf->cputime, 1.759 + PERIOD_BEGIN(waitinf)) - now; 1.760 } 1.761 else { 1.762 ret.time = runinf->slice - runinf->cputime; 1.763 @@ -624,25 +732,30 @@ check_waitq: 1.764 1.765 if (!list_empty(waitq)) { 1.766 waitinf = list_entry(waitq->next,struct sedf_dom_info,list); 1.767 - //we could not find any suitable domain => look for domains that are aware of extratime 1.768 + /*we could not find any suitable domain 1.769 + => look for domains that are aware of extratime*/ 1.770 #if (EXTRA > EXTRA_OFF) 1.771 - ret = sedf_do_extra_schedule(now, PERIOD_BEGIN(waitinf), extraq, cpu); 1.772 + ret = sedf_do_extra_schedule(now, PERIOD_BEGIN(waitinf), 1.773 + extraq, cpu); 1.774 #else 1.775 ret.task = IDLETASK(cpu); 1.776 ret.time = PERIOD_BEGIN(waitinf) - now; 1.777 #endif 1.778 } 1.779 else { 1.780 - //this could probably never happen, but one never knows... 1.781 - //it can... imagine a second CPU, which is pure scifi ATM, but one never knows ;) 1.782 + /*this could probably never happen, but one never knows...*/ 1.783 + /*it can... imagine a second CPU, which is pure scifi ATM, 1.784 + but one never knows ;)*/ 1.785 ret.task = IDLETASK(cpu); 1.786 ret.time = SECONDS(1); 1.787 } 1.788 1.789 sched_done: 1.790 - //TODO: Do something USEFUL when this happens and find out, why it still can happen!!! 1.791 + /*TODO: Do something USEFUL when this happens and find out, why it 1.792 + still can happen!!!*/ 1.793 if (ret.time<0) { 1.794 - printk("Ouch! We are seriously BEHIND schedule! %lli\n",ret.time); 1.795 + printk("Ouch! We are seriously BEHIND schedule! %lli\n", 1.796 + ret.time); 1.797 ret.time = EXTRA_QUANTUM; 1.798 } 1.799 DOM_INFO(ret.task)->sched_start=now; 1.800 @@ -671,13 +784,14 @@ static void sedf_sleep(struct domain *d) 1.801 } 1.802 } 1.803 1.804 -/* This function wakes ifup a domain, i.e. moves them into the waitqueue 1.805 +/* This function wakes up a domain, i.e. moves them into the waitqueue 1.806 * things to mention are: admission control is taking place nowhere at 1.807 * the moment, so we can't be sure, whether it is safe to wake the domain 1.808 * up at all. Anyway, even if it is safe (total cpu usage <=100%) there are 1.809 * some considerations on when to allow the domain to wake up and have it's 1.810 * first deadline... 1.811 - * I detected 3 cases, which could describe the possible behaviour of the scheduler, 1.812 + * I detected 3 cases, which could describe the possible behaviour of the 1.813 + * scheduler, 1.814 * and I'll try to make them more clear: 1.815 * 1.816 * 1. Very conservative 1.817 @@ -692,150 +806,221 @@ static void sedf_sleep(struct domain *d) 1.818 * -deadlines keep occuring isochronous 1.819 * 1.820 * 2. Conservative Part 1: Short Unblocking 1.821 - * -when a domain unblocks in the same period as it was blocked it unblocks and 1.822 - * may consume the rest of it's original time-slice minus the time it was blocked 1.823 + * -when a domain unblocks in the same period as it was blocked it 1.824 + * unblocks and may consume the rest of it's original time-slice minus 1.825 + * the time it was blocked 1.826 * (assume period=9, slice=5) 1.827 * 1.828 * DRB_UR___DRRRRR___D... 1.829 * 1.830 - * -this also doesn't disturb scheduling, but might lead to the fact, that the domain 1.831 - * can't finish it's workload in the period 1.832 - * -in addition to that the domain can be treated prioritised when extratime is available 1.833 - * 1.834 + * -this also doesn't disturb scheduling, but might lead to the fact, that 1.835 + * the domain can't finish it's workload in the period 1.836 + * -in addition to that the domain can be treated prioritised when 1.837 + * extratime is available 1.838 + * -addition: experiments hve shown that this may have a HUGE impact on 1.839 + * performance of other domains, becaus it can lead to excessive context 1.840 + * switches 1.841 + 1.842 * Part2: Long Unblocking 1.843 * Part 2a 1.844 - * -it is obvious that such behaviour, applied when then unblocking is happening in 1.845 - * later periods, works fine aswell 1.846 - * -the domain is treated as if it would have been running since the start of its new period 1.847 + * -it is obvious that such accounting of block time, applied when 1.848 + * unblocking is happening in later periods, works fine aswell 1.849 + * -the domain is treated as if it would have been running since the start 1.850 + * of its new period 1.851 * 1.852 * DRB______D___UR___D... 1.853 * 1.854 * Part 2b 1.855 - * -if one needs the full slice in the next period, it is necessary to treat the unblocking 1.856 - * time as the start of the new period, i.e. move the deadline further back (later) 1.857 - * -this doesn't disturb scheduling as well, because for EDF periods can be treated as minimal 1.858 - * inter-release times and scheduling stays correct, when deadlines are kept relative to the time 1.859 - * the process unblocks 1.860 + * -if one needs the full slice in the next period, it is necessary to 1.861 + * treat the unblocking time as the start of the new period, i.e. move 1.862 + * the deadline further back (later) 1.863 + * -this doesn't disturb scheduling as well, because for EDF periods can 1.864 + * be treated as minimal inter-release times and scheduling stays 1.865 + * correct, when deadlines are kept relative to the time the process 1.866 + * unblocks 1.867 * 1.868 - * DRB______D___URRRR___D... 1.869 - * (D) 1.870 + * DRB______D___URRRR___D...<prev [Thread] next> 1.871 + * (D) <- old deadline was here 1.872 * -problem: deadlines don't occur isochronous anymore 1.873 * Part 2c (Improved Atropos design) 1.874 - * -when a domain unblocks it is given a very short period (=latency hint) and slice length scaled 1.875 - * accordingly 1.876 + * -when a domain unblocks it is given a very short period (=latency hint) 1.877 + * and slice length scaled accordingly 1.878 * -both rise again to the original value (e.g. get doubled every period) 1.879 * 1.880 * 3. Unconservative (i.e. incorrect) 1.881 - * -to boost the performance of I/O dependent domains it would be possible to put the domain into 1.882 - * the runnable queue immediately, and let it run for the remainder of the slice of the current period 1.883 + * -to boost the performance of I/O dependent domains it would be possible 1.884 + * to put the domain into the runnable queue immediately, and let it run 1.885 + * for the remainder of the slice of the current period 1.886 * (or even worse: allocate a new full slice for the domain) 1.887 - * -either behaviour can lead to missed deadlines in other domains as opposed to approaches 1,2a,2b 1.888 + * -either behaviour can lead to missed deadlines in other domains as 1.889 + * opposed to approaches 1,2a,2b 1.890 */ 1.891 -static inline void unblock_short_vcons(struct sedf_dom_info* inf, s_time_t now) { 1.892 +static inline void unblock_short_vcons 1.893 +(struct sedf_dom_info* inf, s_time_t now) { 1.894 inf->absdead += inf->period; 1.895 inf->cputime = 0; 1.896 } 1.897 1.898 -static inline void unblock_short_cons(struct sedf_dom_info* inf, s_time_t now) { 1.899 - inf->cputime += now - inf->absblock; //treat blocked time as consumed by the domain 1.900 +static inline void unblock_short_cons(struct sedf_dom_info* inf, s_time_t now) 1.901 +{ 1.902 + /*treat blocked time as consumed by the domain*/ 1.903 + inf->cputime += now - inf->absblock; 1.904 if (inf->cputime + EXTRA_QUANTUM > inf->slice) { 1.905 - //we don't have a reasonable amount of time in our slice left :( 1.906 - unblock_short_vcons(inf, now); //start in next period! 1.907 + /*we don't have a reasonable amount of time in 1.908 + our slice left :( => start in next period!*/ 1.909 + unblock_short_vcons(inf, now); 1.910 } 1.911 #ifdef SEDF_STATS 1.912 else 1.913 - inf->short_cont++; //we let the domain run in the current period 1.914 + inf->short_cont++; 1.915 #endif 1.916 } 1.917 -static inline void unblock_short_extra_support(struct sedf_dom_info* inf, s_time_t now) { 1.918 - /*this unblocking scheme tries to support the domain, by assigning it a priority in extratime distribution 1.919 - according to the loss of time in this slice due to blocking*/ 1.920 +static inline void unblock_short_extra_support (struct sedf_dom_info* inf, 1.921 + s_time_t now) { 1.922 + /*this unblocking scheme tries to support the domain, by assigning it 1.923 + a priority in extratime distribution according to the loss of time 1.924 + in this slice due to blocking*/ 1.925 s_time_t pen; 1.926 - inf->absdead += inf->period; //no more realtime execution in this period! 1.927 + 1.928 + /*no more realtime execution in this period!*/ 1.929 + inf->absdead += inf->period; 1.930 if (likely(inf->absblock)) { 1.931 - //inf->cputime += now - inf->absblock; //treat blocked time as consumed by the domain 1.932 + //treat blocked time as consumed by the domain*/ 1.933 + /*inf->cputime += now - inf->absblock;*/ 1.934 pen = (inf->slice - inf->cputime); 1.935 if (pen < 0) pen = 0; 1.936 - //inf->short_block_lost_tot += pen; //calc. penalty because of that 1.937 - inf->short_block_lost_tot = pen; //set penalty to the current value 1.938 - //not sure which one is better.. but seems to work well... 1.939 + /*accumulate all penalties over the periods*/ 1.940 + /*inf->short_block_lost_tot += pen;*/ 1.941 + /*set penalty to the current value*/ 1.942 + inf->short_block_lost_tot = pen; 1.943 + /*not sure which one is better.. but seems to work well...*/ 1.944 1.945 if (inf->short_block_lost_tot) { 1.946 - inf->score[0] = (inf->period << 10) / inf->short_block_lost_tot; 1.947 + inf->score[0] = (inf->period << 10) / 1.948 + inf->short_block_lost_tot; 1.949 #ifdef SEDF_STATS 1.950 inf->pen_extra_blocks++; 1.951 #endif 1.952 if (extraq_on(inf->owner, EXTRA_PEN_Q)) 1.953 - extraq_del(inf->owner, EXTRA_PEN_Q); //remove domain for possible resorting! 1.954 - else //remember that we want to be on the penalty queue, 1.955 - inf->extra |= EXTRA_WANT_PEN_Q; //so that we can continue when we (un-)blocked in pen-ext. 1.956 - extraq_add_sort_update(inf->owner, EXTRA_PEN_Q, 0); //(re-)add domain to the penalty extraq 1.957 + /*remove domain for possible resorting!*/ 1.958 + extraq_del(inf->owner, EXTRA_PEN_Q); 1.959 + else 1.960 + /*remember that we want to be on the penalty q 1.961 + so that we can continue when we (un-)block 1.962 + in penalty-extratime*/ 1.963 + inf->extra |= EXTRA_WANT_PEN_Q; 1.964 + 1.965 + /*(re-)add domain to the penalty extraq*/ 1.966 + extraq_add_sort_update(inf->owner, 1.967 + EXTRA_PEN_Q, 0); 1.968 } 1.969 } 1.970 - inf->cputime = 0; //give it a fresh slice in the next period! 1.971 + /*give it a fresh slice in the next period!*/ 1.972 + inf->cputime = 0; 1.973 } 1.974 -static inline void unblock_long_vcons(struct sedf_dom_info* inf, s_time_t now) { 1.975 - inf->absdead += ((now - inf->absdead) / inf->period + 1) * inf->period; //very conservative 1.976 +static inline void unblock_long_vcons(struct sedf_dom_info* inf, s_time_t now) 1.977 +{ 1.978 + /* align to next future period */ 1.979 + inf->absdead += ((now - inf->absdead) / inf->period + 1) 1.980 + * inf->period; 1.981 inf->cputime = 0; 1.982 } 1.983 1.984 -static inline void unblock_long_cons_a(struct sedf_dom_info* inf, s_time_t now) { 1.985 - inf->cputime = (now - inf->absdead) % inf->period; //treat the time the domain was blocked in the CURRENT 1.986 - //period as consumed by the domain 1.987 +static inline void unblock_long_cons_a (struct sedf_dom_info* inf, 1.988 + s_time_t now) { 1.989 + /*treat the time the domain was blocked in the 1.990 + CURRENT period as consumed by the domain*/ 1.991 + inf->cputime = (now - inf->absdead) % inf->period; 1.992 if (inf->cputime + EXTRA_QUANTUM > inf->slice) { 1.993 - //we don't have a reasonable amount of time in our slice left :( 1.994 - unblock_long_vcons(inf, now); //start in next period! 1.995 + /*we don't have a reasonable amount of time in our slice 1.996 + left :( => start in next period!*/ 1.997 + unblock_long_vcons(inf, now); 1.998 } 1.999 } 1.1000 static inline void unblock_long_cons_b(struct sedf_dom_info* inf,s_time_t now) { 1.1001 - inf->absdead = now + inf->period; //Conservative 2b 1.1002 + /*Conservative 2b*/ 1.1003 + /*Treat the unblocking time as a start of a new period */ 1.1004 + inf->absdead = now + inf->period; 1.1005 inf->cputime = 0; 1.1006 } 1.1007 static inline void unblock_long_cons_c(struct sedf_dom_info* inf,s_time_t now) { 1.1008 if (likely(inf->latency)) { 1.1009 - //scale the slice and period accordingly to the latency hint 1.1010 - inf->period = inf->latency; //reduce period temporarily to the latency hint 1.1011 - ASSERT((inf->period < ULONG_MAX) && (inf->slice_orig < ULONG_MAX)); //this results in max. 4s slice/period length 1.1012 - inf->slice = (inf->period * inf->slice_orig) / inf->period_orig; //scale slice accordingly, so that utilisation stays the same 1.1013 + /*scale the slice and period accordingly to the latency hint*/ 1.1014 + /*reduce period temporarily to the latency hint*/ 1.1015 + inf->period = inf->latency; 1.1016 + /*this results in max. 4s slice/period length*/ 1.1017 + ASSERT((inf->period < ULONG_MAX) 1.1018 + && (inf->slice_orig < ULONG_MAX)); 1.1019 + /*scale slice accordingly, so that utilisation stays the same*/ 1.1020 + inf->slice = (inf->period * inf->slice_orig) 1.1021 + / inf->period_orig; 1.1022 + inf->absdead = now + inf->period; 1.1023 + inf->cputime = 0; 1.1024 } 1.1025 else { 1.1026 - //we don't have a latency hint.. use some other technique 1.1027 + /*we don't have a latency hint.. use some other technique*/ 1.1028 unblock_long_cons_b(inf, now); 1.1029 } 1.1030 } 1.1031 -//a new idea of dealing with short blocks: burst period scaling 1.1032 -static inline void unblock_short_burst(struct sedf_dom_info* inf, s_time_t now) { 1.1033 - inf->cputime += now - inf->absblock; //treat blocked time as consumed by the domain 1.1034 +/*a new idea of dealing with short blocks: burst period scaling*/ 1.1035 +static inline void unblock_short_burst(struct sedf_dom_info* inf, s_time_t now) 1.1036 +{ 1.1037 + /*treat blocked time as consumed by the domain*/ 1.1038 + inf->cputime += now - inf->absblock; 1.1039 1.1040 if (inf->cputime + EXTRA_QUANTUM <= inf->slice) { 1.1041 + /*if we can still use some time in the current slice 1.1042 + then use it!*/ 1.1043 #ifdef SEDF_STATS 1.1044 - inf->short_cont++; //we let the domain run in the current period 1.1045 + /*we let the domain run in the current period*/ 1.1046 + inf->short_cont++; 1.1047 #endif 1.1048 } 1.1049 else { 1.1050 - //we don't have a reasonable amount of time in our slice left => switch to burst mode 1.1051 + /*we don't have a reasonable amount of time in 1.1052 + our slice left => switch to burst mode*/ 1.1053 if (likely(inf->absunblock)) { 1.1054 - inf->period = now - inf->absunblock; //set the period-length to the current blocking interval 1.1055 - ASSERT((inf->period < ULONG_MAX) && (inf->slice_orig < ULONG_MAX));//this results in max. 4s slice/period length 1.1056 - inf->slice = (inf->period * inf->slice_orig) / inf->period_orig;//scale slice accordingly, so that utilisation stays the same 1.1057 + /*set the period-length to the current blocking 1.1058 + interval, possible enhancements: average over last 1.1059 + blocking intervals, user-specified minimum,...*/ 1.1060 + inf->period = now - inf->absunblock; 1.1061 + /*check for overflow on multiplication*/ 1.1062 + ASSERT((inf->period < ULONG_MAX) 1.1063 + && (inf->slice_orig < ULONG_MAX)); 1.1064 + /*scale slice accordingly, so that utilisation 1.1065 + stays the same*/ 1.1066 + inf->slice = (inf->period * inf->slice_orig) 1.1067 + / inf->period_orig; 1.1068 + /*set new (shorter) deadline*/ 1.1069 + inf->absdead += inf->period; 1.1070 } 1.1071 else { 1.1072 - inf->cputime=0; //in Case we haven't unblocked before 1.1073 - inf->absdead += inf->period; //start in next period! 1.1074 + /*in case we haven't unblocked before 1.1075 + start in next period!*/ 1.1076 + inf->cputime=0; 1.1077 + inf->absdead += inf->period; 1.1078 } 1.1079 } 1.1080 inf->absunblock = now; 1.1081 } 1.1082 static inline void unblock_long_burst(struct sedf_dom_info* inf,s_time_t now) { 1.1083 if (unlikely(inf->latency && (inf->period > inf->latency))) { 1.1084 - //sclae the slice and period accordingly to the latency hint 1.1085 - inf->period = inf->latency; //reduce period temporarily to the latency hint 1.1086 - ASSERT((inf->period < ULONG_MAX) && (inf->slice_orig < ULONG_MAX)); //this results in max. 4s slice/period length 1.1087 - inf->slice = (inf->period * inf->slice_orig) / inf->period_orig; //scale slice accordingly, so that utilisation stays the same 1.1088 + /*scale the slice and period accordingly to the latency hint*/ 1.1089 + inf->period = inf->latency; 1.1090 + /*check for overflows on multiplication*/ 1.1091 + ASSERT((inf->period < ULONG_MAX) 1.1092 + && (inf->slice_orig < ULONG_MAX)); 1.1093 + /*scale slice accordingly, so that utilisation stays the same*/ 1.1094 + inf->slice = (inf->period * inf->slice_orig) 1.1095 + / inf->period_orig; 1.1096 + inf->absdead = now + inf->period; 1.1097 + inf->cputime = 0; 1.1098 } 1.1099 else { 1.1100 - //we don't have a latency hint.. or we are currently in "burst mode": use some other technique 1.1101 - //this should be in fact the normal way of operation, when we are in sync with the device! 1.1102 + /*we don't have a latency hint.. or we are currently in 1.1103 + "burst mode": use some other technique 1.1104 + NB: this should be in fact the normal way of operation, 1.1105 + when we are in sync with the device!*/ 1.1106 unblock_long_cons_b(inf, now); 1.1107 } 1.1108 inf->absunblock = now; 1.1109 @@ -855,34 +1040,42 @@ static inline int get_run_type(struct do 1.1110 return DOMAIN_EXTRA_UTIL; 1.1111 return DOMAIN_EDF; 1.1112 } 1.1113 -/*Compares two domains in the relation of whether the one is allowed to interrupt the others execution. 1.1114 +/*Compares two domains in the relation of whether the one is allowed to 1.1115 + interrupt the others execution. 1.1116 It returns true (!=0) if a switch to the other domain is good. 1.1117 Current Priority scheme is as follows: 1.1118 - EDF > L0 (penalty based) extra-time > L1 (utilization) extra-time > idle-domain 1.1119 + EDF > L0 (penalty based) extra-time > 1.1120 + L1 (utilization) extra-time > idle-domain 1.1121 In the same class priorities are assigned as following: 1.1122 EDF: early deadline > late deadline 1.1123 L0 extra-time: lower score > higher score*/ 1.1124 -static inline int should_switch(struct domain* cur, struct domain* other, s_time_t now) { 1.1125 +static inline int should_switch(struct domain* cur, struct domain* other, 1.1126 + s_time_t now) { 1.1127 struct sedf_dom_info *cur_inf, *other_inf; 1.1128 cur_inf = DOM_INFO(cur); 1.1129 other_inf = DOM_INFO(other); 1.1130 1.1131 + /*check whether we need to make an earlier sched-decision*/ 1.1132 + if ((PERIOD_BEGIN(other_inf) < 1.1133 + schedule_data[other->processor].s_timer.expires)) 1.1134 + return 1; 1.1135 + /*no timing-based switches need to be taken into account here*/ 1.1136 switch (get_run_type(cur)) { 1.1137 case DOMAIN_EDF: 1.1138 - //check whether we need to make an earlier sched-decision 1.1139 - if ((PERIOD_BEGIN(other_inf) < schedule_data[other->processor].s_timer.expires)) 1.1140 - return 1; 1.1141 - else return 0; 1.1142 + /* do not interrupt a running EDF domain */ 1.1143 + return 0; 1.1144 case DOMAIN_EXTRA_PEN: 1.1145 - //check whether we need an earlier decision or we also want the L0 ex-q with lower score 1.1146 - if ((PERIOD_BEGIN(other_inf) < schedule_data[other->processor].s_timer.expires) 1.1147 - || ((other_inf->extra & EXTRA_WANT_PEN_Q) && (other_inf->score[EXTRA_PEN_Q] < cur_inf->score[EXTRA_PEN_Q]))) 1.1148 + /*check whether we also want 1.1149 + the L0 ex-q with lower score*/ 1.1150 + if ((other_inf->extra & EXTRA_WANT_PEN_Q) 1.1151 + && (other_inf->score[EXTRA_PEN_Q] < 1.1152 + cur_inf->score[EXTRA_PEN_Q])) 1.1153 return 1; 1.1154 else return 0; 1.1155 case DOMAIN_EXTRA_UTIL: 1.1156 - //check whether we need an earlier decision or we want the L0 extraq, don't switch if both domains want L1 extraq 1.1157 - if ((PERIOD_BEGIN(other_inf) < schedule_data[other->processor].s_timer.expires) 1.1158 - || (other_inf->extra & EXTRA_WANT_PEN_Q)) 1.1159 + /*check whether we want the L0 extraq, don't 1.1160 + switch if both domains want L1 extraq */ 1.1161 + if (other_inf->extra & EXTRA_WANT_PEN_Q) 1.1162 return 1; 1.1163 else return 0; 1.1164 case DOMAIN_IDLE: 1.1165 @@ -890,7 +1083,6 @@ static inline int should_switch(struct d 1.1166 } 1.1167 } 1.1168 void sedf_wake(struct domain *d) { 1.1169 - //for the first try just implement the "very conservative" way of waking domains up 1.1170 s_time_t now = NOW(); 1.1171 struct sedf_dom_info* inf = DOM_INFO(d); 1.1172 1.1173 @@ -907,35 +1099,44 @@ void sedf_wake(struct domain *d) { 1.1174 PRINT(3,"\tdomain %i is already in the extraQ\n",d->id); 1.1175 } 1.1176 if (unlikely(inf->absdead == 0)) 1.1177 - inf->absdead = now + inf->slice; //initial setup of the deadline 1.1178 + /*initial setup of the deadline*/ 1.1179 + inf->absdead = now + inf->slice; 1.1180 1.1181 - PRINT(3,"waking up domain %i (deadl= %llu period= %llu now= %llu)\n",d->id,inf->absdead,inf->period,now); 1.1182 + PRINT(3,"waking up domain %i (deadl= %llu period= %llu "\ 1.1183 + "now= %llu)\n",d->id,inf->absdead,inf->period,now); 1.1184 #ifdef SEDF_STATS 1.1185 inf->block_tot++; 1.1186 #endif 1.1187 if (unlikely(now< PERIOD_BEGIN(inf))) { 1.1188 PRINT(4,"extratime unblock\n"); 1.1189 - //this might happen, imagine unblocking in extra-time! 1.1190 + /*this might happen, imagine unblocking in extra-time!*/ 1.1191 #if (EXTRA == EXTRA_BLOCK_WEIGHT) 1.1192 - if (inf->extra & EXTRA_WANT_PEN_Q) { //we have a domain that wants compensation 1.1193 + if (inf->extra & EXTRA_WANT_PEN_Q) { 1.1194 + /*we have a domain that wants compensation 1.1195 + for block penalty and did just block in 1.1196 + its compensation time. Give it another 1.1197 + chance!*/ 1.1198 extraq_add_sort_update(d, EXTRA_PEN_Q, 0); 1.1199 - } /*else*/ 1.1200 + } 1.1201 #endif 1.1202 if (inf->extra & EXTRA_AWARE) 1.1203 #if (EXTRA == EXTRA_ROUNDR) 1.1204 - extraq_add_tail(d,EXTRA_UTIL_Q); //SD: Could extraq_add_head be better? 1.1205 - #elif (EXTRA == EXTRA_SLICE_WEIGHT || EXTRA == EXTRA_BLOCK_WEIGHT) 1.1206 - extraq_add_sort_update(d, EXTRA_UTIL_Q, 0); //put in on the weighted extraq 1.1207 + extraq_add_tail(d,EXTRA_UTIL_Q); 1.1208 + #elif (EXTRA == EXTRA_SLICE_WEIGHT \ 1.1209 + || EXTRA == EXTRA_BLOCK_WEIGHT) 1.1210 + /*put in on the weighted extraq, 1.1211 + without updating any scores*/ 1.1212 + extraq_add_sort_update(d, EXTRA_UTIL_Q, 0); 1.1213 #else 1.1214 ; 1.1215 #endif 1.1216 - //else 1.1217 - //This is very very unlikely, ie. might even be an error?! 1.1218 + /*else*/ 1.1219 + /*This is very very unlikely, ie. might even be an error?!*/ 1.1220 } 1.1221 else { 1.1222 if (now < inf->absdead) { 1.1223 PRINT(4,"short unblocking\n"); 1.1224 - //short blocking 1.1225 + /*short blocking*/ 1.1226 #ifdef SEDF_STATS 1.1227 inf->short_block_tot++; 1.1228 #endif 1.1229 @@ -953,27 +1154,29 @@ void sedf_wake(struct domain *d) { 1.1230 #if (EXTRA == EXTRA_OFF) 1.1231 ; 1.1232 #elif (EXTRA == EXTRA_ROUNDR) 1.1233 - extraq_add_head(d, EXTRA_UTIL_Q); //Favour domains which got short unblocked 1.1234 - #elif (EXTRA == EXTRA_SLICE_WEIGHT || EXTRA == EXTRA_BLOCK_WEIGHT) 1.1235 + /*Favour domains which got short unblocked*/ 1.1236 + extraq_add_head(d, EXTRA_UTIL_Q); 1.1237 + #elif (EXTRA == EXTRA_SLICE_WEIGHT \ 1.1238 + || EXTRA == EXTRA_BLOCK_WEIGHT) 1.1239 extraq_add_sort_update(d, EXTRA_UTIL_Q, 0); 1.1240 #endif 1.1241 } 1.1242 else { 1.1243 PRINT(4,"long unblocking\n"); 1.1244 - //long blocking 1.1245 + /*long unblocking*/ 1.1246 #ifdef SEDF_STATS 1.1247 inf->long_block_tot++; 1.1248 #endif 1.1249 - //PRINT(3,"old=%llu ",inf->absdead); 1.1250 #if (UNBLOCK == UNBLOCK_ISOCHRONOUS_EDF) 1.1251 unblock_long_vcons(inf, now); 1.1252 - #elif (UNBLOCK == UNBLOCK_EDF || UNBLOCK == UNBLOCK_EXTRA_SUPPORT) 1.1253 + #elif (UNBLOCK == UNBLOCK_EDF \ 1.1254 + || UNBLOCK == UNBLOCK_EXTRA_SUPPORT) 1.1255 unblock_long_cons_b(inf, now); 1.1256 #elif (UNBLOCK == UNBLOCK_ATROPOS) 1.1257 unblock_long_cons_c(inf, now); 1.1258 #elif (UNBLOCK == UNBLOCK_SHORT_RESUME) 1.1259 unblock_long_cons_b(inf, now); 1.1260 - //unblock_short_cons_c(inf, now); 1.1261 + /*unblock_short_cons_c(inf, now);*/ 1.1262 #elif (UNBLOCK == UNBLOCK_BURST) 1.1263 unblock_long_burst(inf, now); 1.1264 #endif 1.1265 @@ -983,35 +1186,37 @@ void sedf_wake(struct domain *d) { 1.1266 ; 1.1267 #elif (EXTRA == EXTRA_ROUNDR) 1.1268 extraq_add_head(d, EXTRA_UTIL_Q); 1.1269 - #elif (EXTRA == EXTRA_SLICE_WEIGHT || EXTRA == EXTRA_BLOCK_WEIGHT) 1.1270 - //PRINT(2,"now try to add domain %i to the extra_util_q\n",d->id); 1.1271 + #elif (EXTRA == EXTRA_SLICE_WEIGHT \ 1.1272 + || EXTRA == EXTRA_BLOCK_WEIGHT) 1.1273 extraq_add_sort_update(d, EXTRA_UTIL_Q, 0); 1.1274 - //PRINT(2,"added domain\n"); 1.1275 #endif 1.1276 } 1.1277 1.1278 } 1.1279 } 1.1280 - PRINT(3,"woke up domain %i (deadl= %llu period= %llu now= %llu)\n",d->id,inf->absdead,inf->period,now); 1.1281 + PRINT(3,"woke up domain %i (deadl= %llu period= %llu "\ 1.1282 + "now= %llu)\n",d->id,inf->absdead,inf->period,now); 1.1283 __add_to_waitqueue_sort(d); 1.1284 PRINT(3,"added to waitq\n"); 1.1285 1.1286 #ifdef SEDF_STATS 1.1287 - //do some statistics here... 1.1288 + /*do some statistics here...*/ 1.1289 if (inf->absblock != 0) { 1.1290 inf->block_time_tot += now - inf->absblock; 1.1291 - inf->penalty_time_tot += PERIOD_BEGIN(inf) + inf->cputime - inf->absblock; 1.1292 + inf->penalty_time_tot += 1.1293 + PERIOD_BEGIN(inf) + inf->cputime - inf->absblock; 1.1294 } 1.1295 #endif 1.1296 - //sanity check: make sure each extra-aware domain IS on the util-q! 1.1297 + /*sanity check: make sure each extra-aware domain IS on the util-q!*/ 1.1298 /*if (inf->extra & EXTRA_AWARE) { 1.1299 if (!extraq_on(d, EXTRA_UTIL_Q)) 1.1300 - printf("sedf_wake: domain %i is extra-aware, but NOT on L1 extraq!\n",d->id); 1.1301 + printf("sedf_wake: domain %i is extra-aware, "\ 1.1302 + "but NOT on L1 extraq!\n",d->id); 1.1303 }*/ 1.1304 1.1305 - //check whether the awakened task needs to get scheduled before the next sched. decision 1.1306 - //and check, whether we are idling and this domain is extratime aware 1.1307 - //Save approximation: Always switch to scheduler! 1.1308 + /*check whether the awakened task needs to invoke the do_schedule 1.1309 + routine. Try to avoid unnecessary runs but: 1.1310 + Save approximation: Always switch to scheduler!*/ 1.1311 if (should_switch(schedule_data[d->processor].curr, d, now)){ 1.1312 #ifdef ADV_SCHED_HISTO 1.1313 adv_sched_hist_start(d->processor); 1.1314 @@ -1025,21 +1230,30 @@ static void sedf_dump_domain(struct doma 1.1315 printk("%u has=%c ", d->id, 1.1316 test_bit(DF_RUNNING, &d->flags) ? 'T':'F'); 1.1317 printk("p=%llu sl=%llu ddl=%llu w=%hu c=%llu sc=%i xtr(%s)=%llu", 1.1318 - DOM_INFO(d)->period, DOM_INFO(d)->slice, DOM_INFO(d)->absdead, DOM_INFO(d)->weight, d->cpu_time, 1.1319 - DOM_INFO(d)->score[EXTRA_UTIL_Q], (DOM_INFO(d)->extra & EXTRA_AWARE) ? "yes" : "no", DOM_INFO(d)->extra_time_tot); 1.1320 + DOM_INFO(d)->period, DOM_INFO(d)->slice, DOM_INFO(d)->absdead, 1.1321 + DOM_INFO(d)->weight, d->cpu_time, DOM_INFO(d)->score[EXTRA_UTIL_Q], 1.1322 + (DOM_INFO(d)->extra & EXTRA_AWARE) ? "yes" : "no", 1.1323 + DOM_INFO(d)->extra_time_tot); 1.1324 if (d->cpu_time !=0) 1.1325 - printf(" (%lu%)", (DOM_INFO(d)->extra_time_tot * 100) / d->cpu_time); 1.1326 + printf(" (%lu%)", (DOM_INFO(d)->extra_time_tot * 100) 1.1327 + / d->cpu_time); 1.1328 #ifdef SEDF_STATS 1.1329 if (DOM_INFO(d)->block_time_tot!=0) 1.1330 - printf(" pen=%lu%", (DOM_INFO(d)->penalty_time_tot * 100) / DOM_INFO(d)->block_time_tot); 1.1331 + printf(" pen=%lu%", (DOM_INFO(d)->penalty_time_tot * 100) / 1.1332 + DOM_INFO(d)->block_time_tot); 1.1333 if (DOM_INFO(d)->block_tot!=0) 1.1334 - printf("\n blks=%lu sh=%lu (%lu%) (shc=%lu (%lu%) shex=%i shexsl=%i) l=%lu (%lu%) avg: b=%llu p=%llu", DOM_INFO(d)->block_tot, 1.1335 - DOM_INFO(d)->short_block_tot, (DOM_INFO(d)->short_block_tot * 100) / DOM_INFO(d)->block_tot, 1.1336 - DOM_INFO(d)->short_cont, (DOM_INFO(d)->short_cont * 100) / DOM_INFO(d)->block_tot, 1.1337 - DOM_INFO(d)->pen_extra_blocks, DOM_INFO(d)->pen_extra_slices, 1.1338 - DOM_INFO(d)->long_block_tot, (DOM_INFO(d)->long_block_tot * 100) / DOM_INFO(d)->block_tot, 1.1339 - (DOM_INFO(d)->block_time_tot) / DOM_INFO(d)->block_tot, 1.1340 - (DOM_INFO(d)->penalty_time_tot) / DOM_INFO(d)->block_tot); 1.1341 + printf("\n blks=%lu sh=%lu (%lu%) (shc=%lu (%lu%) shex=%i "\ 1.1342 + "shexsl=%i) l=%lu (%lu%) avg: b=%llu p=%llu", 1.1343 + DOM_INFO(d)->block_tot, DOM_INFO(d)->short_block_tot, 1.1344 + (DOM_INFO(d)->short_block_tot * 100) 1.1345 + / DOM_INFO(d)->block_tot, DOM_INFO(d)->short_cont, 1.1346 + (DOM_INFO(d)->short_cont * 100) / DOM_INFO(d)->block_tot, 1.1347 + DOM_INFO(d)->pen_extra_blocks, 1.1348 + DOM_INFO(d)->pen_extra_slices, 1.1349 + DOM_INFO(d)->long_block_tot, 1.1350 + (DOM_INFO(d)->long_block_tot * 100) / DOM_INFO(d)->block_tot, 1.1351 + (DOM_INFO(d)->block_time_tot) / DOM_INFO(d)->block_tot, 1.1352 + (DOM_INFO(d)->penalty_time_tot) / DOM_INFO(d)->block_tot); 1.1353 #endif 1.1354 printf("\n"); 1.1355 } 1.1356 @@ -1072,19 +1286,23 @@ static void sedf_dump_cpu_state(int i) 1.1357 } 1.1358 1.1359 queue = EXTRAQ(i,EXTRA_PEN_Q); loop = 0; 1.1360 - printk("\nEXTRAQ (penalty) rq %lx n: %lx, p: %lx\n", (unsigned long)queue, 1.1361 - (unsigned long) queue->next, (unsigned long) queue->prev); 1.1362 + printk("\nEXTRAQ (penalty) rq %lx n: %lx, p: %lx\n", 1.1363 + (unsigned long)queue, (unsigned long) queue->next, 1.1364 + (unsigned long) queue->prev); 1.1365 list_for_each_safe ( list, tmp, queue ) { 1.1366 - d_inf = list_entry(list, struct sedf_dom_info, extralist[EXTRA_PEN_Q]); 1.1367 + d_inf = list_entry(list, struct sedf_dom_info, 1.1368 + extralist[EXTRA_PEN_Q]); 1.1369 printk("%3d: ",loop++); 1.1370 sedf_dump_domain(d_inf->owner); 1.1371 } 1.1372 1.1373 queue = EXTRAQ(i,EXTRA_UTIL_Q); loop = 0; 1.1374 - printk("\nEXTRAQ (utilization) rq %lx n: %lx, p: %lx\n", (unsigned long)queue, 1.1375 - (unsigned long) queue->next, (unsigned long) queue->prev); 1.1376 + printk("\nEXTRAQ (utilization) rq %lx n: %lx, p: %lx\n", 1.1377 + (unsigned long)queue, (unsigned long) queue->next, 1.1378 + (unsigned long) queue->prev); 1.1379 list_for_each_safe ( list, tmp, queue ) { 1.1380 - d_inf = list_entry(list, struct sedf_dom_info, extralist[EXTRA_UTIL_Q]); 1.1381 + d_inf = list_entry(list, struct sedf_dom_info, 1.1382 + extralist[EXTRA_UTIL_Q]); 1.1383 printk("%3d: ",loop++); 1.1384 sedf_dump_domain(d_inf->owner); 1.1385 } 1.1386 @@ -1098,8 +1316,9 @@ static void sedf_dump_cpu_state(int i) 1.1387 } 1.1388 } 1.1389 } 1.1390 -//Adjusts periods and slices of the domains accordingly to their weights 1.1391 -static inline int sedf_adjust_weights(struct domain *p, struct sched_adjdom_cmd *cmd) { 1.1392 +/*Adjusts periods and slices of the domains accordingly to their weights*/ 1.1393 +static inline int sedf_adjust_weights(struct domain *p, 1.1394 +struct sched_adjdom_cmd *cmd) { 1.1395 int sumw[NR_CPUS]; 1.1396 s_time_t sumt[NR_CPUS]; 1.1397 int cpu; 1.1398 @@ -1108,25 +1327,31 @@ static inline int sedf_adjust_weights(st 1.1399 sumw[cpu] = 0; 1.1400 sumt[cpu] = 0; 1.1401 } 1.1402 - //sum up all weights 1.1403 + /*sum up all weights*/ 1.1404 for_each_domain(p) { 1.1405 if (DOM_INFO(p)->weight) 1.1406 sumw[p->processor] += DOM_INFO(p)->weight; 1.1407 else { 1.1408 - //don't modify domains who don't have a weight, but sum up 1.1409 - //the time they need, projected to a WEIGHT_PERIOD, so that 1.1410 - //this time is not given to the weight-driven domains 1.1411 - ASSERT((WEIGHT_PERIOD < ULONG_MAX) && (DOM_INFO(p)->slice_orig < ULONG_MAX)); //this results in max. 4s slice/period length 1.1412 - sumt[p->processor] += (WEIGHT_PERIOD * DOM_INFO(p)->slice_orig) / DOM_INFO(p)->period_orig; 1.1413 + /*don't modify domains who don't have a weight, but sum 1.1414 + up the time they need, projected to a WEIGHT_PERIOD, 1.1415 + so that this time is not given to the weight-driven 1.1416 + domains*/ 1.1417 + /*check for overflows*/ 1.1418 + ASSERT((WEIGHT_PERIOD < ULONG_MAX) 1.1419 + && (DOM_INFO(p)->slice_orig < ULONG_MAX)); 1.1420 + sumt[p->processor] += (WEIGHT_PERIOD * 1.1421 + DOM_INFO(p)->slice_orig) / DOM_INFO(p)->period_orig; 1.1422 } 1.1423 } 1.1424 - //adjust all slices (and periods) to the new weight 1.1425 + /*adjust all slices (and periods) to the new weight*/ 1.1426 for_each_domain(p) { 1.1427 if (DOM_INFO(p)->weight) { 1.1428 DOM_INFO(p)->period_orig = 1.1429 DOM_INFO(p)->period = WEIGHT_PERIOD; 1.1430 DOM_INFO(p)->slice_orig = 1.1431 - DOM_INFO(p)->slice = (DOM_INFO(p)->weight * (WEIGHT_PERIOD - WEIGHT_SAFETY - sumt[p->processor])) / sumw[p->processor]; 1.1432 + DOM_INFO(p)->slice = (DOM_INFO(p)->weight * 1.1433 + (WEIGHT_PERIOD -WEIGHT_SAFETY - 1.1434 + sumt[p->processor])) / sumw[p->processor]; 1.1435 } 1.1436 } 1.1437 return 0; 1.1438 @@ -1134,19 +1359,24 @@ static inline int sedf_adjust_weights(st 1.1439 1.1440 /* set or fetch domain scheduling parameters */ 1.1441 static int sedf_adjdom(struct domain *p, struct sched_adjdom_cmd *cmd) { 1.1442 - PRINT(2,"sedf_adjdom was called, domain-id %i new period %llu new slice %llu\n" 1.1443 - "latency %llu extra: %s\n",p->id,cmd->u.sedf.period,cmd->u.sedf.slice,cmd->u.sedf.latency,(cmd->u.sedf.extratime)?"yes":"no"); 1.1444 + PRINT(2,"sedf_adjdom was called, domain-id %i new period %llu "\ 1.1445 + "new slice %llu\nlatency %llu extra:%s\n", 1.1446 + p->id, cmd->u.sedf.period, cmd->u.sedf.slice, 1.1447 + cmd->u.sedf.latency, (cmd->u.sedf.extratime)?"yes":"no"); 1.1448 if ( cmd->direction == SCHED_INFO_PUT ) 1.1449 { 1.1450 - if (!cmd->u.sedf.period && !cmd->u.sedf.weight) //check for sane parameters 1.1451 + /*check for sane parameters*/ 1.1452 + if (!cmd->u.sedf.period && !cmd->u.sedf.weight) 1.1453 return -EINVAL; 1.1454 + /*weight driven domains*/ 1.1455 if (cmd->u.sedf.weight) { 1.1456 - DOM_INFO(p)->weight = cmd->u.sedf.weight; //weight driven domains 1.1457 + DOM_INFO(p)->weight = cmd->u.sedf.weight; 1.1458 } 1.1459 else { 1.1460 - //time driven domains 1.1461 + /*time driven domains*/ 1.1462 DOM_INFO(p)->weight = 0; 1.1463 - if(cmd->u.sedf.slice > cmd->u.sedf.period ) /* sanity checking! */ 1.1464 + /* sanity checking! */ 1.1465 + if(cmd->u.sedf.slice > cmd->u.sedf.period ) 1.1466 return -EINVAL; 1.1467 DOM_INFO(p)->period_orig = 1.1468 DOM_INFO(p)->period = cmd->u.sedf.period; 1.1469 @@ -1155,7 +1385,8 @@ static int sedf_adjdom(struct domain *p, 1.1470 } 1.1471 if (sedf_adjust_weights(p,cmd)) 1.1472 return -EINVAL; 1.1473 - DOM_INFO(p)->extra = (DOM_INFO(p)-> extra & ~EXTRA_AWARE) | (cmd->u.sedf.extratime & EXTRA_AWARE); 1.1474 + DOM_INFO(p)->extra = (DOM_INFO(p)-> extra & ~EXTRA_AWARE) 1.1475 + | (cmd->u.sedf.extratime & EXTRA_AWARE); 1.1476 DOM_INFO(p)->latency = cmd->u.sedf.latency; 1.1477 extraq_check(p); 1.1478 }