ia64/xen-unstable

changeset 4042:2d335430f7fc

bitkeeper revision 1.1159.170.105 (422f0996UBOVE7bb-GrY-kHTfrNOMQ)

Implemented twol level extra-time scheduling and added an advanced scheduling history
author sd386@font.cl.cam.ac.uk
date Wed Mar 09 14:35:02 2005 +0000 (2005-03-09)
parents c712c4935a13
children 6bb21b5051a9
files .rootkeys xen/common/sched_sedf.c xen/include/xen/adv_sched_hist.h
line diff
     1.1 --- a/.rootkeys	Thu Feb 17 18:50:24 2005 +0000
     1.2 +++ b/.rootkeys	Wed Mar 09 14:35:02 2005 +0000
     1.3 @@ -854,6 +854,7 @@ 404f3d2eR2Owk-ZcGOx9ULGHg3nrww xen/inclu
     1.4  3ddb79c25UE59iu4JJcbRalx95mvcg xen/include/public/xen.h
     1.5  3e397e66m2tO3s-J8Jnr7Ws_tGoPTg xen/include/xen/ac_timer.h
     1.6  40715b2epYl2jBbxzz9CI2rgIca7Zg xen/include/xen/acpi.h
     1.7 +422f0995xCgnbsVhTjSncnqIABs64g xen/include/xen/adv_sched_hist.h
     1.8  3ddb79c0c0cX_DZE209-Bb-Rx1v-Aw xen/include/xen/cache.h
     1.9  3f840f12CkbYSlwMrY2S11Mpyxg7Nw xen/include/xen/compiler.h
    1.10  3ddb79c259jh8hE7vre_8NuE7nwNSA xen/include/xen/config.h
     2.1 --- a/xen/common/sched_sedf.c	Thu Feb 17 18:50:24 2005 +0000
     2.2 +++ b/xen/common/sched_sedf.c	Wed Mar 09 14:35:02 2005 +0000
     2.3 @@ -5,6 +5,14 @@
     2.4   * based on code by Mark Williamson (C) 2004 Intel Research Cambridge
     2.5   */
     2.6  
     2.7 +/*
     2.8 +	TODO:
     2.9 +	TESTING!
    2.10 +	tracing instead of PRINTs
    2.11 +*/
    2.12 +
    2.13 +
    2.14 +
    2.15  #include <xen/sched.h>
    2.16  #include <xen/sched-if.h>
    2.17  #include <public/sched_ctl.h>
    2.18 @@ -25,8 +33,8 @@ if ((_f)<=SEDFLEVEL) printk(_a );
    2.19  #define UNBLOCK_ATROPOS 3
    2.20  #define UNBLOCK_SHORT_RESUME 4
    2.21  #define UNBLOCK_BURST 5
    2.22 -
    2.23 -#define UNBLOCK UNBLOCK_BURST
    2.24 +#define UNBLOCK_EXTRA_SUPPORT 6
    2.25 +#define UNBLOCK UNBLOCK_EXTRA_SUPPORT
    2.26  
    2.27  //various ways of treating extra-time
    2.28  #define EXTRA_OFF 1
    2.29 @@ -34,20 +42,19 @@ if ((_f)<=SEDFLEVEL) printk(_a );
    2.30  #define EXTRA_SLICE_WEIGHT 3
    2.31  #define EXTRA_BLOCK_WEIGHT 4
    2.32  
    2.33 -#define EXTRA EXTRA_OFF
    2.34 -
    2.35 +#define EXTRA EXTRA_BLOCK_WEIGHT
    2.36  
    2.37 -/*
    2.38 -	TODO:
    2.39 -	TESTING!
    2.40 -	tracing instead of PRINTs
    2.41 -*/
    2.42 -
    2.43 -
    2.44 -#define TRC_SEDF 0xBEEF0000
    2.45  #define EXTRA_NONE (0)
    2.46  #define EXTRA_AWARE (1)
    2.47 -#define EXTRA_RUNNING (2)
    2.48 +#define EXTRA_RUN_PEN (2)
    2.49 +#define EXTRA_RUN_UTIL (4)
    2.50 +#define EXTRA_WANT_PEN_Q (8)
    2.51 +#define EXTRA_PEN_Q (0)
    2.52 +#define EXTRA_UTIL_Q (1)
    2.53 +
    2.54 +#define extra_runs(inf) ((inf->extra) & 6)
    2.55 +#define extra_get_cur_q(inf) (((inf->extra & 6) >> 1)-1)
    2.56 +
    2.57  #define EXTRA_QUANTUM (MICROSECS(500)) 
    2.58  #define WEIGHT_PERIOD (MILLISECS(100))
    2.59  #define WEIGHT_SAFETY (MILLISECS(5))
    2.60 @@ -70,7 +77,7 @@ struct sedf_dom_info
    2.61  	s_time_t		latency;
    2.62  	//extra-time status of domain
    2.63  	short			extra;
    2.64 -	//weights for "Scheduling for beginners/ lazy/ etc."
    2.65 +	//weights for "Scheduling for beginners/ lazy/ etc." ;)
    2.66  	short			weight;
    2.67  	
    2.68  	//Bookkeeping
    2.69 @@ -90,46 +97,58 @@ struct sedf_dom_info
    2.70  	int			short_block_tot;
    2.71  	int			long_block_tot;
    2.72  	int			short_cont;
    2.73 +	int			pen_extra_blocks;
    2.74 +	int			pen_extra_slices;
    2.75  };
    2.76  
    2.77  struct sedf_cpu_info {
    2.78  	struct list_head runnableq;
    2.79  	struct list_head waitq;
    2.80 -	struct list_head extraq;
    2.81 +	struct list_head extraq[2];
    2.82  };
    2.83  
    2.84  #define DOM_INFO(d)		((struct sedf_dom_info *)((d)->sched_priv))
    2.85  #define CPU_INFO(cpu)		((struct sedf_cpu_info *)schedule_data[cpu].sched_priv)
    2.86  #define LIST(d)			(&DOM_INFO(d)->list)
    2.87 -#define EXTRALIST(d)		(&DOM_INFO(d)->extralist)
    2.88 +#define EXTRALIST(d,i)		(&(DOM_INFO(d)->extralist[i]))
    2.89  #define RUNQ(cpu)   		(&CPU_INFO(cpu)->runnableq)
    2.90  #define WAITQ(cpu)   		(&CPU_INFO(cpu)->waitq)
    2.91 -#define EXTRAQ(cpu)   		(&CPU_INFO(cpu)->extraq)
    2.92 +#define EXTRAQ(cpu,i)  		(&(CPU_INFO(cpu)->extraq[i]))
    2.93  #define IDLETASK(cpu)		((struct domain *)schedule_data[cpu].idle)
    2.94  
    2.95  #define PERIOD_BEGIN(inf)	((inf)->absdead - (inf)->period)
    2.96  
    2.97 +#define MIN(x,y) (((x)<(y))?(x):(y))
    2.98 +#define DIV_UP(x,y) (((x) + (y) - 1) / y)
    2.99 +
   2.100  static xmem_cache_t *dom_info_cache;
   2.101  
   2.102 -static inline void extraq_add_head(struct domain *d)
   2.103 -{
   2.104 -    list_add(EXTRALIST(d), EXTRAQ(d->processor));
   2.105 +static void sedf_dump_cpu_state(int i);
   2.106 +
   2.107 +static inline int extraq_on(struct domain *d, int i) {
   2.108 +	return ((EXTRALIST(d,i)->next != NULL) && (EXTRALIST(d,i)->next != EXTRALIST(d,i)));
   2.109  }
   2.110  
   2.111 -static inline void extraq_add_tail(struct domain *d)
   2.112 +static inline void extraq_add_head(struct domain *d, int i)
   2.113  {
   2.114 -    list_add_tail(EXTRALIST(d), EXTRAQ(d->processor));
   2.115 +    list_add(EXTRALIST(d,i), EXTRAQ(d->processor,i));
   2.116  }
   2.117  
   2.118 -static inline void extraq_del(struct domain *d)
   2.119 +static inline void extraq_add_tail(struct domain *d, int i)
   2.120  {
   2.121 -    struct list_head *list = EXTRALIST(d);
   2.122 -    list_del(list);
   2.123 -    list->next = NULL;
   2.124 +    list_add_tail(EXTRALIST(d,i), EXTRAQ(d->processor,i));
   2.125  }
   2.126  
   2.127 -static inline int extraq_on(struct domain *d) {
   2.128 -	return (((EXTRALIST(d))->next != NULL) && (EXTRALIST(d)->next != EXTRALIST(d)));
   2.129 +static inline void extraq_del(struct domain *d, int i)
   2.130 +{
   2.131 +	struct list_head *list = EXTRALIST(d,i);
   2.132 +	/*if (!extraq_on(d,i)) {
   2.133 +		PRINT(0,"extraq_del: domain %i is NOT on L%i extraq! HALTING\n",d->id,i);
   2.134 +		sedf_dump_cpu_state(0);(*((int*)0))++;
   2.135 +	}*/
   2.136 +	PRINT(3, "Removing domain %i from L%i extraq\n", d->id,i);	
   2.137 +	list_del(list);
   2.138 +	list->next = NULL;
   2.139  }
   2.140  
   2.141  /* adds a domain to the queue of processes which are aware of extra time. List is sorted by score,
   2.142 @@ -137,50 +156,57 @@ static inline int extraq_on(struct domai
   2.143     a fixed value from each entry, in order to avoid overflow. The algorithm works by simply charging each domain
   2.144     that recieved extratime with an inverse of its weight.
   2.145   */ 
   2.146 -static inline void extraq_add_sort_update(struct domain *d, unsigned long sub) {
   2.147 +static inline void extraq_add_sort_update(struct domain *d, int i, int sub) {
   2.148  	struct list_head     *cur;
   2.149  	struct sedf_dom_info *curinf;
   2.150  	
   2.151 -	PRINT(3,"Adding domain %i (score= %llu) to extraq\n",d->id,DOM_INFO(d)->score);	
   2.152 +	/*if (extraq_on(d,i)) {
   2.153 +		PRINT(0,"extraq_add_sort_update: domain %i is already on L%i extraq! HALTING\n",d->id,i);
   2.154 +		sedf_dump_cpu_state(0);(*((int*)0))++;
   2.155 +	}*/
   2.156 +	PRINT(3, "Adding domain %i (score= %i, short_pen= %lli) to L%i extraq\n", d->id,
   2.157 +		DOM_INFO(d)->score[i], DOM_INFO(d)->short_block_lost_tot, i);	
   2.158  	//iterate through all elements to find our "hole" and on our way update all the other scores
   2.159 -	list_for_each(cur,EXTRAQ(d->processor)){
   2.160 -		curinf         = list_entry(cur,struct sedf_dom_info,extralist);
   2.161 -		curinf->score -= sub;
   2.162 -		if (DOM_INFO(d)->score < curinf->score)
   2.163 +	list_for_each(cur,EXTRAQ(d->processor,i)){
   2.164 +		curinf            = list_entry(cur,struct sedf_dom_info,extralist[i]);
   2.165 +		curinf->score[i] -= sub;
   2.166 +		if (DOM_INFO(d)->score[i] < curinf->score[i])
   2.167  	 		break;
   2.168  		else
   2.169 -			PRINT(4,"\tbehind domain %i (score= %llu)\n",curinf->owner->id,curinf->score);
   2.170 +			PRINT(4,"\tbehind domain %i (score= %i)\n", curinf->owner->id, curinf->score[i]);
   2.171  	}
   2.172 -	//cur now contains the element, before which we'll enqueue
   2.173 -	PRINT(3,"\tlist_add to %x\n",cur->prev);
   2.174 -	list_add(EXTRALIST(d),cur->prev);
   2.175 +	//cur now contains the element, before which we'll enq	ueue
   2.176 +	PRINT(3, "\tlist_add to %x\n", cur->prev);
   2.177 +	list_add(EXTRALIST(d,i),cur->prev);
   2.178  	
   2.179  	//continue updating the extraq
   2.180 -	if ((cur != EXTRAQ(d->processor)) && sub) 
   2.181 -		for (cur = cur->next; cur != EXTRAQ(d->processor); cur = cur-> next) {
   2.182 -			curinf         = list_entry(cur,struct sedf_dom_info,extralist);
   2.183 -			curinf->score -= sub;
   2.184 -			PRINT(4,"\tupdating domain %i (score= %llu)\n",curinf->owner->id,curinf->score);
   2.185 +	if ((cur != EXTRAQ(d->processor,i)) && sub) 
   2.186 +		for (cur = cur->next; cur != EXTRAQ(d->processor,i); cur = cur-> next) {
   2.187 +			curinf         = list_entry(cur,struct sedf_dom_info,extralist[i]);
   2.188 +			curinf->score[i] -= sub;
   2.189 +			PRINT(4, "\tupdating domain %i (score= %llu)\n", curinf->owner->id, curinf->score[i]);
   2.190  		}
   2.191  }
   2.192  static inline void extraq_check(struct domain *d) {
   2.193 -	if (extraq_on(d)) {
   2.194 +	if (extraq_on(d, EXTRA_UTIL_Q)) {
   2.195  		PRINT(2,"Dom %i is on extraQ\n",d->id);
   2.196 -		if (DOM_INFO(d)->extra == EXTRA_NONE) {
   2.197 -			extraq_del(d);
   2.198 -			PRINT(2,"Removed dom %i from extraQ\n",d->id);
   2.199 +		if (!(DOM_INFO(d)->extra & EXTRA_AWARE)) {
   2.200 +			extraq_del(d, EXTRA_UTIL_Q);
   2.201 +			PRINT(2,"Removed dom %i from L1 extraQ\n",d->id);
   2.202  		}
   2.203  	} else {
   2.204 -		PRINT(2,"Dom %i is NOT on extraQ\n",d->id);
   2.205 -		if (DOM_INFO(d)->extra != EXTRA_NONE) {
   2.206 -			PRINT(2,"Added dom %i to extraQ\n",d->id);
   2.207 -			extraq_add_sort_update(d, 0);
   2.208 +		PRINT(2,"Dom %i is NOT on L1 extraQ\n",d->id);
   2.209 +		if ((DOM_INFO(d)->extra & EXTRA_AWARE) && domain_runnable(d))  {
   2.210 +			extraq_add_sort_update(d, EXTRA_UTIL_Q, 0);
   2.211 +			PRINT(2,"Added dom %i to L1 extraQ\n",d->id);
   2.212 +			//TODO: add extraq_add_tail
   2.213  		}
   2.214  	}
   2.215  }
   2.216  static inline void __del_from_queue(struct domain *d)
   2.217  {
   2.218      struct list_head *list = LIST(d);
   2.219 +    PRINT(3,"Removing domain %i (bop= %llu) from runq/waitq\n",d->id,PERIOD_BEGIN(DOM_INFO(d)));
   2.220      list_del(list);
   2.221      list->next = NULL;
   2.222  }
   2.223 @@ -192,7 +218,7 @@ static inline void __add_to_waitqueue_so
   2.224  	struct list_head     *cur;
   2.225  	struct sedf_dom_info *curinf;
   2.226  	
   2.227 -	PRINT(3,"Adding domain %i (bop= %llu) to waitq\n",d->id,PERIOD_BEGIN(DOM_INFO(d)));	
   2.228 +	PRINT(3,"Adding domain %i (bop= %llu) to waitq\n",d->id,PERIOD_BEGIN(DOM_INFO(d)));
   2.229  	//iterate through all elements to find our "hole"
   2.230  	list_for_each(cur,WAITQ(d->processor)){
   2.231  		curinf = list_entry(cur,struct sedf_dom_info,list);
   2.232 @@ -243,13 +269,12 @@ static int sedf_init_scheduler() {
   2.233  		schedule_data[i].sched_priv = xmalloc(sizeof(struct sedf_cpu_info));
   2.234  		if ( schedule_data[i].sched_priv == NULL )
   2.235  			return -1;
   2.236 -		INIT_LIST_HEAD(WAITQ(i));//used for Latency Scaling
   2.237 +		INIT_LIST_HEAD(WAITQ(i));
   2.238  		INIT_LIST_HEAD(RUNQ(i));
   2.239 -		INIT_LIST_HEAD(EXTRAQ(i));
   2.240 +		INIT_LIST_HEAD(EXTRAQ(i,EXTRA_PEN_Q));
   2.241 +		INIT_LIST_HEAD(EXTRAQ(i,EXTRA_UTIL_Q));
   2.242  	}
   2.243 -				//we could not find any suitable domain => look for domains that are aware of extratime
   2.244 -	dom_info_cache = xmem_cache_create(
   2.245 -		"SEDF dom info", sizeof(struct sedf_dom_info), 0, 0, 0, NULL);
   2.246 +	dom_info_cache = xmem_cache_create("SEDF dom info", sizeof(struct sedf_dom_info), 0, 0, 0, NULL);
   2.247  	if ( dom_info_cache == NULL )
   2.248  	{
   2.249  		printk("Could not allocate SLAB cache.\n");
   2.250 @@ -294,7 +319,8 @@ static void sedf_add_task(struct domain 
   2.251  	}
   2.252  	inf->period_orig = inf->period; inf->slice_orig = inf->slice;
   2.253  	INIT_LIST_HEAD(&(inf->list));
   2.254 -	INIT_LIST_HEAD(&(inf->extralist));
   2.255 +	INIT_LIST_HEAD(&(inf->extralist[EXTRA_PEN_Q]));
   2.256 +	INIT_LIST_HEAD(&(inf->extralist[EXTRA_UTIL_Q]));
   2.257  }
   2.258  
   2.259  /* Frees memory used by domain info */
   2.260 @@ -312,112 +338,72 @@ static int sedf_init_idle_task(struct do
   2.261  		return -1;
   2.262  	
   2.263  	sedf_add_task(d);
   2.264 -	DOM_INFO(d)->absdead=0;
   2.265 +	DOM_INFO(d)->absdead = 0;
   2.266  	set_bit(DF_RUNNING, &d->flags);
   2.267  	//the idle task doesn't have to turn up on any list...
   2.268  	return 0;
   2.269  }
   2.270  
   2.271 -#define MIN(x,y) (((x)<(y))?(x):(y))
   2.272 -/* Main scheduling function
   2.273 - * Reasons for calling this function are:
   2.274 - * -timeslice for the current period used up
   2.275 - * -domain on waitqueue has started it's period
   2.276 - * -and various others ;) in general: determin which domain to run next*/
   2.277 -static task_slice_t sedf_do_schedule(s_time_t now)
   2.278 -{
   2.279 -	struct sedf_dom_info *inf   = DOM_INFO(current);
   2.280 -	int                   cpu   = current->processor;
   2.281 -	struct list_head     *runq  = RUNQ(cpu);
   2.282 -	struct list_head     *waitq = WAITQ(cpu);
   2.283 -	#if (EXTRA > EXTRA_OFF)
   2.284 -	struct list_head     *extraq = EXTRAQ(cpu);
   2.285 -	#endif
   2.286 +/* handles the rescheduling, bookkeeping of domains running in their realtime-time :)*/
   2.287 +static inline void desched_edf_dom (s_time_t now, struct domain* d) {
   2.288 +	struct sedf_dom_info* inf = DOM_INFO(d);
   2.289 +	
   2.290 +	//current domain is running in real time mode
   2.291 +	inf->cputime += now - inf->sched_start;				//update the domains cputime
   2.292 +	//scheduling decisions, which don't remove the running domain from the runq
   2.293 +	if ((inf->cputime < inf->slice) && domain_runnable(d))
   2.294 +		return;						//there is nothing to do with the running task
   2.295 +		
   2.296 +	__del_from_queue(d);
   2.297 +	/*if (__task_on_queue(current)) {
   2.298 +		PRINT(0,"domain %i was removed but still on run/waitq => HALT\n",current->id);
   2.299 +		sedf_dump_cpu_state(0);(*((int*)0))++;
   2.300 +	}*/
   2.301 +	
   2.302 +	//manage bookkeeping (i.e. calculate next deadline, memorize overun time of slice) of finished domains
   2.303 +	if (inf->cputime >= inf->slice) {
   2.304 +		inf->cputime -= inf->slice;
   2.305 +		
   2.306 +		if (inf->period < inf->period_orig) {
   2.307 +			//this domain runs in latency scaling or burst mode
   2.308 +			#if (UNBLOCK == UNBLOCK_BURST)
   2.309 +			if (now - inf->absunblock >= 2 * inf->period)
   2.310 +			#endif
   2.311 +			{
   2.312 +				inf->period *= 2; inf->slice *= 2;
   2.313 +				if ((inf->period > inf->period_orig) || (inf->slice > inf->slice_orig)) {
   2.314 +					inf->period = inf->period_orig;	//update the domains cputime
   2.315 +					inf->slice = inf->slice_orig;
   2.316 +				}
   2.317 +			}
   2.318 +		}
   2.319 +		inf->absdead += inf->period;				//set next deadline
   2.320 +	}
   2.321 +	//if (inf->absdead<now);
   2.322 +		//printk("Domain %i exceeded it't deadline!!!! (now: %llu ddl: %llu)\n",current->id,now,inf->absdead);
   2.323 +	if (domain_runnable(d))						//add a runnable domain to the waitqueue		
   2.324 +		__add_to_waitqueue_sort(d);
   2.325 +	else {
   2.326 +		inf->absblock = now;					//we have a blocked realtime task
   2.327 +		#if (EXTRA > EXTRA_OFF)
   2.328 +		#if (EXTRA == EXTRA_BLOCK_WEIGHT)
   2.329 +		if (extraq_on(d,EXTRA_PEN_Q)) extraq_del(d,EXTRA_PEN_Q);
   2.330 +		if (extraq_on(d,EXTRA_UTIL_Q)) extraq_del(d,EXTRA_UTIL_Q);
   2.331 +		#endif
   2.332 +		#endif
   2.333 +	}
   2.334 +}
   2.335 +
   2.336 +/* Update all elements on the queues */
   2.337 +static inline void update_queues(s_time_t now, struct list_head* runq, struct list_head* waitq) {
   2.338  	struct list_head     *cur,*tmp;
   2.339  	struct sedf_dom_info *curinf;
   2.340 -	task_slice_t          ret;
   2.341 -	#if (EXTRA == EXTRA_SLICE_WEIGHT)
   2.342 -	unsigned long         oldscore;
   2.343 -	#endif
   2.344  	
   2.345 -	//idle tasks don't need any of the following stuf
   2.346 -	if (is_idle_task(inf->owner))
   2.347 -		goto check_waitq;				//idle task doesn't get scheduled on the runq
   2.348 -
   2.349 -	#if (EXTRA > EXTRA_OFF)
   2.350 -	if (unlikely(inf->extra == EXTRA_RUNNING)) {
   2.351 -		//special treatment of domains running in extra time
   2.352 -		inf->extra = EXTRA_AWARE;
   2.353 -		inf->cputime=0;
   2.354 -		inf->extra_time_tot += now - inf->sched_start;
   2.355 -		
   2.356 -		extraq_del(current);					//remove extradomain from head of the queue
   2.357 -		
   2.358 -		#if (EXTRA == EXTRA_ROUNDR)
   2.359 -		if (domain_runnable(current))
   2.360 -			extraq_add_tail(current);			//and add to the tail if it is runnable => round-robin
   2.361 -		#elif (EXTRA == EXTRA_SLICE_WEIGHT)
   2.362 -		oldscore   = inf->score;				//update the score
   2.363 -		inf->score = (inf->period << 10) / inf->slice;		//use fixed point arithmetic with 10 bits
   2.364 -		
   2.365 -		if (domain_runnable(current))
   2.366 -			extraq_add_sort_update(current, oldscore);	//add according to score: weighted round robin
   2.367 -		#endif
   2.368 -		else
   2.369 -			__del_from_queue(inf->owner);			//if domain blocked in extratime remove it from waitq(/runq) as well
   2.370 -	}
   2.371 -	else
   2.372 -	#endif
   2.373 -	{
   2.374 -		//current domain is running in real time mode
   2.375 -		//update the domains cputime
   2.376 -		inf->cputime += now - inf->sched_start;
   2.377 -		//scheduling decisions, which don't move the running domain to any queues
   2.378 -		if ((inf->cputime < inf->slice) && domain_runnable(inf->owner))
   2.379 -			goto check_waitq;			//there is nothing to do with the running task
   2.380 -		
   2.381 -		//remove tasks that can't run
   2.382 -		__del_from_queue(inf->owner);
   2.383 -		
   2.384 -		//manage bookkeeping (i.e. calculate next deadline, memorize overun time of slice) of finished domains
   2.385 -		if (inf->cputime >= inf->slice) {
   2.386 -			inf->cputime -= inf->slice;
   2.387 -			
   2.388 -			if (inf->period < inf->period_orig) {
   2.389 -				//this domain runs in latency scaling or burst mode
   2.390 -				#if (UNBLOCK == UNBLOCK_BURST)
   2.391 -				if (now - inf->absunblock >= 2 * inf->period)
   2.392 -				#endif
   2.393 -				{
   2.394 -					inf->period *= 2;
   2.395 -					inf->slice *= 2;
   2.396 -					if ((inf->period > inf->period_orig) || (inf->slice > inf->slice_orig)) {
   2.397 -						//now switch back to standard timing
   2.398 -						inf->period = inf->period_orig;
   2.399 -						inf->slice = inf->slice_orig;
   2.400 -					}
   2.401 -				}
   2.402 -			}
   2.403 -			inf->absdead += inf->period;		//set next deadline
   2.404 -		}
   2.405 -		//if (inf->absdead<now);
   2.406 -			//printk("Domain %i exceeded it't deadline!!!! (now: %llu ddl: %llu)\n",current->id,now,inf->absdead);
   2.407 -		//add a runnable domain to the waitqueue		
   2.408 -		if (domain_runnable(inf->owner))
   2.409 -			__add_to_waitqueue_sort(inf->owner);
   2.410 -		else {
   2.411 -			//we have a blocked realtime task
   2.412 -			inf->absblock = now;
   2.413 -			#if (EXTRA > EXTRA_OFF)
   2.414 -			if (inf->extra == EXTRA_AWARE)
   2.415 -				extraq_del(inf->owner);		//remove a blocked domain from the extraq aswell
   2.416 -			#endif
   2.417 -		}
   2.418 -	}
   2.419 -check_waitq:
   2.420 +	PRINT(3,"Updating waitq..\n");
   2.421  	//check for the first elements of the waitqueue, whether their next period has already started
   2.422  	list_for_each_safe(cur,tmp,waitq) {
   2.423  		curinf = list_entry(cur,struct sedf_dom_info,list);
   2.424 +		PRINT(4,"\tLooking @ dom %i\n",curinf->owner->id);
   2.425  		if (PERIOD_BEGIN(curinf) <= now) {
   2.426  			__del_from_queue(curinf->owner);
   2.427  			__add_to_runqueue_sort(curinf->owner);
   2.428 @@ -426,29 +412,188 @@ check_waitq:
   2.429  			break;
   2.430  	}
   2.431  	
   2.432 -	//process the runq
   2.433 +	PRINT(3,"Updating runq..\n");
   2.434 +	//process the runq, find domains that are on the runqueue which shouldn't be there
   2.435  	list_for_each_safe(cur,tmp,runq) {
   2.436  		curinf = list_entry(cur,struct sedf_dom_info,list);
   2.437 -		if (unlikely(curinf->slice == 0)) {
   2.438 -			//special treatment of elements with empty slice
   2.439 +		PRINT(4,"\tLooking @ dom %i\n",curinf->owner->id);
   2.440 +		if (unlikely(curinf->slice == 0)) {			//ignore domains with empty slice
   2.441 +			PRINT(4,"\tUpdating zero-slice domain %i\n",curinf->owner->id);
   2.442  			__del_from_queue(curinf->owner);
   2.443 -			curinf->absdead += curinf->period;
   2.444 -			__add_to_waitqueue_sort(curinf->owner);
   2.445 +			curinf->absdead += curinf->period;		//move to their next period
   2.446 +			__add_to_waitqueue_sort(curinf->owner);		//and put them back into the queue
   2.447  		}
   2.448  		else {
   2.449  			if (unlikely((curinf->absdead < now) || (curinf->cputime > curinf->slice))) {
   2.450  				//we missed the deadline or the slice was already finished... might hapen because of dom_adj.
   2.451  				//printk("Ouch! Domain %i missed deadline %llu\n",curinf->owner->id,curinf->absdead);
   2.452 +				PRINT(4,"\tDomain %i exceeded it's deadline/slice (%llu / %llu) now: %llu cputime: %llu\n",
   2.453 +					curinf->owner->id, curinf->absdead, curinf->slice, now, curinf->cputime);
   2.454  				__del_from_queue(curinf->owner);
   2.455 -				curinf->absdead += ((now - curinf->absdead + (curinf->period-1)) / curinf->period) * curinf->period;		
   2.456 +				curinf->absdead += curinf->period;	//common case: we miss one period!
   2.457 +				if (unlikely(curinf->absdead < now))
   2.458 +					curinf->absdead += DIV_UP(now - curinf->absdead, curinf->period) * curinf->period;		
   2.459  					//force start of period to be in future and aligned to period borders!
   2.460 -				curinf->cputime = 0;
   2.461 +				curinf->cputime = 0;			//give a fresh slice
   2.462  				__add_to_runqueue_sort(curinf->owner);
   2.463  			}
   2.464  			else
   2.465  				break;
   2.466  		}
   2.467  	}
   2.468 +	PRINT(3,"done updating the queues\n");
   2.469 +}
   2.470 +
   2.471 +#if (EXTRA > EXTRA_OFF)
   2.472 +/*removes a domain from the head of the according extraQ and requeues it at a specified position:
   2.473 +  round-robin extratime: end of extraQ
   2.474 +  weighted ext.: insert in sorted list by score
   2.475 +  if the domain is blocked / has regained its short-block-loss time it is not put on any queue*/
   2.476 +static inline void desched_extra_dom(s_time_t now, struct domain* d) {
   2.477 +	struct sedf_dom_info	*inf = DOM_INFO(d);
   2.478 +	int 			i    = extra_get_cur_q(inf);
   2.479 +	
   2.480 +	#if (EXTRA == EXTRA_SLICE_WEIGHT || EXTRA == EXTRA_BLOCK_WEIGHT)
   2.481 +	unsigned long         oldscore;
   2.482 +	#endif
   2.483 +
   2.484 +	inf->extra  &= ~(EXTRA_RUN_PEN | EXTRA_RUN_UTIL);	//unset all running flags
   2.485 +	inf->cputime = 0;					//fresh slice for the next run
   2.486 +	inf->extra_time_tot += now - inf->sched_start;		//accumulate total extratime
   2.487 +	extraq_del(d, i);					//remove extradomain from head of the queue
   2.488 +
   2.489 +	#if (EXTRA == EXTRA_ROUNDR)
   2.490 +	if (domain_runnable(d))
   2.491 +		extraq_add_tail(d, EXTRA_UTIL_Q);		//and add to the tail if it is runnable => round-robin
   2.492 +	#elif (EXTRA == EXTRA_SLICE_WEIGHT || EXTRA == EXTRA_BLOCK_WEIGHT)
   2.493 +	oldscore      = inf->score[i];				//update the score
   2.494 +	#if (EXTRA == EXTRA_BLOCK_WEIGHT)
   2.495 +	if (i == EXTRA_PEN_Q) {
   2.496 +		//domain was running in L0 extraq
   2.497 +		//inf->short_block_lost_tot -= EXTRA_QUANTUM;	//reduce block lost, probably more sophistication here!
   2.498 +		inf->short_block_lost_tot -= now - inf->sched_start;
   2.499 +		PRINT(3,"Domain %i: Short_block_lost: %lli\n",inf->owner->id,inf->short_block_lost_tot);
   2.500 +		if (inf->short_block_lost_tot <= 0) {
   2.501 +			PRINT(4,"Domain %i compensated short block loss!\n");
   2.502 +			inf->short_block_lost_tot = 0;		//we have (over-)compensated our block penalty
   2.503 +			inf->extra &= ~EXTRA_WANT_PEN_Q;	//we don't want a place on the penalty queue anymore!
   2.504 +			return;					//do not add us on this block extraq again!
   2.505 +		}
   2.506 +		//we have to go again for another try in the block-extraq
   2.507 +		inf->score[EXTRA_PEN_Q] = (inf->period << 10) / inf->short_block_lost_tot;
   2.508 +		oldscore = 0;
   2.509 +	} else
   2.510 +	#endif
   2.511 +	{
   2.512 +		//domain was running in L1 extraq => score is inverse of utilization and is used somewhat incremental!
   2.513 +		inf->score[EXTRA_UTIL_Q] = (inf->period << 10) / inf->slice;//use fixed point arithmetic with 10 bits
   2.514 +	}
   2.515 +	if (domain_runnable(d))
   2.516 +		extraq_add_sort_update(d, i, oldscore);		//add according to score: weighted round robin
   2.517 +	else {
   2.518 +		inf->absblock = now;
   2.519 +		/*if (!__task_on_queue(d)) 
   2.520 +			printf("Oops... We attempt to remove d %i from the waitq, but it is not on :(\n",d->id);*/
   2.521 +		__del_from_queue(d);				//also remove this blocked domain from the waitq!
   2.522 +		//make sure that we remove a blocked domain from the other extraq aswell (this caused hours of debugging!)
   2.523 +		if (i == EXTRA_PEN_Q) {
   2.524 +			if (extraq_on(d,EXTRA_UTIL_Q)) extraq_del(d,EXTRA_UTIL_Q);
   2.525 +		}
   2.526 +		else {
   2.527 +			if (extraq_on(d,EXTRA_PEN_Q)) extraq_del(d,EXTRA_PEN_Q);
   2.528 +		}
   2.529 +	}
   2.530 +	#endif
   2.531 +	/*if (!domain_runnable(d)) {
   2.532 +		if (extraq_on(d,EXTRA_UTIL_Q)) {
   2.533 +			PRINT(0,"domain %i is blocked but still on L1 xq=> HALT\n",d->id);
   2.534 +			sedf_dump_cpu_state(0);(*((int*)0))++;
   2.535 +		}
   2.536 +		if (__task_on_queue(d)) {
   2.537 +			PRINT(0,"domain %i is blocked but still on run/waitq=> HALT\n",d->id);
   2.538 +			sedf_dump_cpu_state(0);(*((int*)0))++;
   2.539 +		}
   2.540 +	}*/
   2.541 +}
   2.542 +#endif
   2.543 +
   2.544 +
   2.545 +static inline task_slice_t sedf_do_extra_schedule(s_time_t now, s_time_t end_xt, struct list_head *extraq[], int cpu) {
   2.546 +	task_slice_t 		ret;
   2.547 +	struct sedf_dom_info	*runinf;
   2.548 +	//TODO write this stuff as a loop and pay attention to normal stuff!
   2.549 +	
   2.550 +	if (end_xt - now < EXTRA_QUANTUM)
   2.551 +		goto return_idle;
   2.552 +		
   2.553 +	if (!list_empty(extraq[EXTRA_PEN_Q])) {
   2.554 +		//we still have elements on the level 0 extraq => let those run first!
   2.555 +		runinf   = list_entry(extraq[EXTRA_PEN_Q]->next, struct sedf_dom_info, extralist[EXTRA_PEN_Q]);
   2.556 +		runinf->extra |= EXTRA_RUN_PEN;
   2.557 +		ret.task = runinf->owner;
   2.558 +		ret.time = EXTRA_QUANTUM;
   2.559 +		runinf->pen_extra_slices++;
   2.560 +	}
   2.561 +	else if (!list_empty(extraq[EXTRA_UTIL_Q])) {
   2.562 +		//use elements from the normal extraqueue
   2.563 +		runinf   = list_entry(extraq[EXTRA_UTIL_Q]->next,struct sedf_dom_info,extralist[EXTRA_UTIL_Q]);
   2.564 +		runinf->extra |= EXTRA_RUN_UTIL;
   2.565 +		ret.task = runinf->owner;
   2.566 +		ret.time = EXTRA_QUANTUM;
   2.567 +	}
   2.568 +	else
   2.569 +		goto return_idle;
   2.570 +
   2.571 +	return ret;
   2.572 +	
   2.573 +return_idle:
   2.574 +	ret.task = IDLETASK(cpu);
   2.575 +	ret.time = end_xt - now;
   2.576 +	return ret;
   2.577 +}
   2.578 +/* Main scheduling function
   2.579 + * Reasons for calling this function are:
   2.580 + * -timeslice for the current period used up
   2.581 + * -domain on waitqueue has started it's period
   2.582 + * -and various others ;) in general: determin which domain to run next*/
   2.583 +static task_slice_t sedf_do_schedule(s_time_t now)
   2.584 +{
   2.585 +	int                   cpu      = current->processor;
   2.586 +	struct list_head     *runq     = RUNQ(cpu);
   2.587 +	struct list_head     *waitq    = WAITQ(cpu);
   2.588 +	#if (EXTRA > EXTRA_OFF)
   2.589 +	struct sedf_dom_info *inf      = DOM_INFO(current);
   2.590 +	struct list_head     *extraq[] = {EXTRAQ(cpu,EXTRA_PEN_Q),EXTRAQ(cpu, EXTRA_UTIL_Q)};
   2.591 +	#endif
   2.592 +	task_slice_t          ret;
   2.593 +	//int i = 0;
   2.594 +	//idle tasks don't need any of the following stuf
   2.595 +	if (is_idle_task(current))
   2.596 +		goto check_waitq;				//idle task doesn't get moved around on any queues
   2.597 +	
   2.598 +	#if (EXTRA > EXTRA_OFF)
   2.599 +	if (unlikely(extra_runs(inf))) {
   2.600 +		//i=1;
   2.601 +		desched_extra_dom(now, current);		//special treatment of domains running in extra time
   2.602 +	}
   2.603 +	else 
   2.604 +	#endif
   2.605 +	{
   2.606 +		//i=2;
   2.607 +		desched_edf_dom(now, current);
   2.608 +	}
   2.609 +	/*if (!domain_runnable(current)) {
   2.610 +		if (extraq_on(current,EXTRA_UTIL_Q)) {
   2.611 +			PRINT(0,"domain %i is blocked but still on L1 xq branch %i=> HALT\n",current->id,i);
   2.612 +			sedf_dump_cpu_state(0);(*((int*)0))++;
   2.613 +		}
   2.614 +		if (__task_on_queue(current)) {
   2.615 +			PRINT(0,"domain %i is blocked but still on run/waitq branch %i=> HALT\n",current->id,i);
   2.616 +			sedf_dump_cpu_state(0);(*((int*)0))++;
   2.617 +		}
   2.618 +	}*/
   2.619 +check_waitq:
   2.620 +	update_queues(now, runq, waitq);
   2.621  	
   2.622  	//now simply pick the first domain from the runqueue
   2.623  	struct sedf_dom_info *runinf, *waitinf;
   2.624 @@ -464,33 +609,28 @@ check_waitq:
   2.625  		else {
   2.626  			ret.time = runinf->slice - runinf->cputime;
   2.627  		}
   2.628 +		goto sched_done;
   2.629 +	}
   2.630 +	
   2.631 +	if (!list_empty(waitq)) {
   2.632 +		waitinf  = list_entry(waitq->next,struct sedf_dom_info,list);
   2.633 +		//we could not find any suitable domain => look for domains that are aware of extratime
   2.634 +		#if (EXTRA > EXTRA_OFF)
   2.635 +		ret = sedf_do_extra_schedule(now, PERIOD_BEGIN(waitinf), extraq, cpu);
   2.636 +		#else
   2.637 +		ret.task = IDLETASK(cpu);
   2.638 +		ret.time = PERIOD_BEGIN(waitinf) - now;
   2.639 +		#endif
   2.640  	}
   2.641  	else {
   2.642 -		if (!list_empty(waitq)) {
   2.643 -			waitinf  = list_entry(waitq->next,struct sedf_dom_info,list);
   2.644 -			//we could not find any suitable domain => look for domains that are aware of extratime
   2.645 -			#if (EXTRA > EXTRA_OFF)
   2.646 -			if (!list_empty(extraq) && (PERIOD_BEGIN(waitinf) - now >= EXTRA_QUANTUM)) {
   2.647 -				runinf   = list_entry(extraq->next,struct sedf_dom_info,extralist);
   2.648 -				runinf->extra = EXTRA_RUNNING;
   2.649 -				ret.task = runinf->owner;
   2.650 -				ret.time = EXTRA_QUANTUM;
   2.651 -			}
   2.652 -			else
   2.653 -			#endif
   2.654 -			{
   2.655 -				//we have an empty run- and extraqueue or too less time => idle task!
   2.656 -				ret.task = IDLETASK(cpu);
   2.657 -				ret.time = PERIOD_BEGIN(waitinf) - now;
   2.658 -			}
   2.659 -		}
   2.660 -		else {
   2.661 -			//this could probably never happen, but one never knows...
   2.662 -			//it can... imagine a second CPU, which is pure scifi ATM, but one never knows ;)
   2.663 -			ret.task = IDLETASK(cpu);
   2.664 -			ret.time = SECONDS(1);
   2.665 -		}
   2.666 +		//this could probably never happen, but one never knows...
   2.667 +		//it can... imagine a second CPU, which is pure scifi ATM, but one never knows ;)
   2.668 +		ret.task = IDLETASK(cpu);
   2.669 +		ret.time = SECONDS(1);
   2.670  	}
   2.671 +
   2.672 +sched_done:	
   2.673 +	//TODO: Do something USEFUL when this happens and find out, why it still can happen!!!
   2.674  	if (ret.time<0)
   2.675  		printk("Ouch! We are seriously BEHIND schedule! %lli\n",ret.time);
   2.676  	DOM_INFO(ret.task)->sched_start=now;
   2.677 @@ -509,8 +649,12 @@ static void sedf_sleep(struct domain *d)
   2.678  		if ( __task_on_queue(d) )
   2.679  			__del_from_queue(d);
   2.680  		#if (EXTRA > EXTRA_OFF)
   2.681 -		if (extraq_on(d))
   2.682 -			extraq_del(d);
   2.683 +		if (extraq_on(d, EXTRA_UTIL_Q)) 
   2.684 +			extraq_del(d, EXTRA_UTIL_Q);
   2.685 +		#endif
   2.686 +		#if (EXTRA == EXTRA_BLOCK_WEIGHT)
   2.687 +		if (extraq_on(d, EXTRA_PEN_Q))
   2.688 +			extraq_del(d, EXTRA_PEN_Q);
   2.689  		#endif
   2.690  	}
   2.691  }
   2.692 @@ -589,7 +733,31 @@ static inline void unblock_short_cons(st
   2.693  	else
   2.694  		inf->short_cont++;							//we let the domain run in the current period
   2.695  }
   2.696 -
   2.697 +static inline void unblock_short_extra_support(struct sedf_dom_info* inf, s_time_t now) {
   2.698 +	/*this unblocking scheme tries to support the domain, by assigning it a priority in extratime distribution
   2.699 +	  according to the loss of time in this slice due to blocking*/
   2.700 +	s_time_t pen;
   2.701 +	inf->absdead += inf->period;							//no more realtime execution in this period!
   2.702 +	if (likely(inf->absblock)) {
   2.703 +		//inf->cputime += now - inf->absblock;					//treat blocked time as consumed by the domain
   2.704 +		pen = (inf->slice - inf->cputime);
   2.705 +		if (pen < 0) pen = 0;
   2.706 +		//inf->short_block_lost_tot += pen;					//calc. penalty because of that
   2.707 +		inf->short_block_lost_tot = pen;  					//set penalty to the current value 
   2.708 +		//not sure which one is better.. but seems to work well...
   2.709 +		
   2.710 +		if (inf->short_block_lost_tot) {
   2.711 +			inf->score[0] = (inf->period << 10) / inf->short_block_lost_tot;
   2.712 +			inf->pen_extra_blocks++;
   2.713 +			if (extraq_on(inf->owner, EXTRA_PEN_Q))
   2.714 +				extraq_del(inf->owner, EXTRA_PEN_Q);			//remove domain for possible resorting!
   2.715 +			else								//remember that we want to be on the penalty queue,
   2.716 +				inf->extra |= EXTRA_WANT_PEN_Q;				//so that we can continue when we (un-)blocked in pen-ext.
   2.717 +			extraq_add_sort_update(inf->owner, EXTRA_PEN_Q, 0);		//(re-)add domain to the penalty extraq
   2.718 +		}
   2.719 +	}
   2.720 +	inf->cputime = 0;								//give it a fresh slice in the next period!
   2.721 +}
   2.722  static inline void unblock_long_vcons(struct sedf_dom_info* inf, s_time_t now) {
   2.723  	inf->absdead += ((now - inf->absdead) / inf->period + 1) * inf->period;		//very conservative
   2.724  	inf->cputime = 0;
   2.725 @@ -655,6 +823,55 @@ static inline void unblock_long_burst(st
   2.726  	inf->absunblock = now;
   2.727  }
   2.728  
   2.729 +#define DOMAIN_EDF 		1
   2.730 +#define DOMAIN_EXTRA_PEN 	2
   2.731 +#define DOMAIN_EXTRA_UTIL 	3
   2.732 +#define DOMAIN_IDLE 		4
   2.733 +static inline int get_run_type(struct domain* d) {
   2.734 +	struct sedf_dom_info* inf = DOM_INFO(d);
   2.735 +	if (is_idle_task(d))
   2.736 +		return DOMAIN_IDLE;
   2.737 +	if (inf->extra & EXTRA_RUN_PEN)
   2.738 +		return DOMAIN_EXTRA_PEN;
   2.739 +	if (inf->extra & EXTRA_RUN_UTIL)
   2.740 +		return DOMAIN_EXTRA_UTIL;
   2.741 +	return DOMAIN_EDF;
   2.742 +}
   2.743 +/*Compares two domains in the relation of whether the one is allowed to interrupt the others execution.
   2.744 +  It returns true (!=0) if a switch to the other domain is good.
   2.745 +  Current Priority scheme is as follows:
   2.746 +  	EDF > L0 (penalty based) extra-time > L1 (utilization) extra-time > blocked domain > idle-domain
   2.747 +  In the same class priorities are assigned as following:
   2.748 +  	EDF: early deadline > late deadline
   2.749 +  	L0 extra-time: lower score > higher score*/
   2.750 +static inline int should_switch(struct domain* cur, struct domain* other, s_time_t now) {
   2.751 +	struct sedf_dom_info *cur_inf, *other_inf;
   2.752 +	cur_inf   = DOM_INFO(cur);
   2.753 +	other_inf = DOM_INFO(other);
   2.754 +	
   2.755 +	switch (get_run_type(cur)) {
   2.756 +		case DOMAIN_EDF:
   2.757 +			//check whether we need to make an earlier sched-decision
   2.758 +			if ((PERIOD_BEGIN(other_inf) < schedule_data[other->processor].s_timer.expires)
   2.759 +			&& (other_inf->absdead < cur_inf->absdead))
   2.760 +				return 1;
   2.761 +			else	return 0;
   2.762 +		case DOMAIN_EXTRA_PEN:
   2.763 +			//check whether we need an earlier decision or we also want the L0 ex-q with lower score
   2.764 +			if ((PERIOD_BEGIN(other_inf) < schedule_data[other->processor].s_timer.expires)
   2.765 +			|| ((other_inf->extra & EXTRA_WANT_PEN_Q) && (other_inf->score[EXTRA_PEN_Q] < cur_inf->score[EXTRA_PEN_Q])))
   2.766 +				return 1;
   2.767 +			else	return 0;
   2.768 +		case DOMAIN_EXTRA_UTIL:
   2.769 +			//check whether we need an earlier decision or we want the L0 extraq, don't switch if both domains want L1 extraq 
   2.770 +			if ((PERIOD_BEGIN(other_inf) < schedule_data[other->processor].s_timer.expires)
   2.771 +			|| (other_inf->extra & EXTRA_WANT_PEN_Q))
   2.772 +				return 1;
   2.773 +			else	return 0;
   2.774 +		case DOMAIN_IDLE:
   2.775 +			return 1;
   2.776 +	}
   2.777 +}
   2.778  void sedf_wake(struct domain *d) {
   2.779  	//for the first try just implement the "very conservative" way of waking domains up
   2.780  	s_time_t              now = NOW();
   2.781 @@ -669,7 +886,7 @@ void sedf_wake(struct domain *d) {
   2.782  		PRINT(3,"\tdomain %i is already in some queue\n",d->id);
   2.783  		return;
   2.784  	}
   2.785 -	if ( unlikely(extraq_on(d)) ) {
   2.786 +	if ( unlikely(extraq_on(d,EXTRA_UTIL_Q) || extraq_on(d,EXTRA_PEN_Q)) ) {
   2.787  		PRINT(3,"\tdomain %i is already in the extraQ\n",d->id);
   2.788  	}
   2.789  	if (unlikely(inf->absdead == 0))
   2.790 @@ -679,12 +896,18 @@ void sedf_wake(struct domain *d) {
   2.791  	
   2.792  	inf->block_tot++;
   2.793  	if (unlikely(now< PERIOD_BEGIN(inf))) {
   2.794 +		PRINT(4,"extratime unblock\n");
   2.795  		//this might happen, imagine unblocking in extra-time!
   2.796 -		if (likely(inf->extra == EXTRA_AWARE)) 
   2.797 +		#if (EXTRA == EXTRA_BLOCK_WEIGHT)
   2.798 +		if (inf->extra & EXTRA_WANT_PEN_Q) {			//we have a domain that wants compensation
   2.799 +			extraq_add_sort_update(d, EXTRA_PEN_Q, 0);
   2.800 +		} /*else*/
   2.801 +		#endif
   2.802 +		if (inf->extra & EXTRA_AWARE) 
   2.803  		#if (EXTRA == EXTRA_ROUNDR)
   2.804 -			extraq_add_tail(d);				//SD: Could extraq_add_head be better?
   2.805 -		#elif (EXTRA == EXTRA_SLICE_WEIGHT)
   2.806 -			extraq_add_sort_update(d, 0);
   2.807 +			extraq_add_tail(d,EXTRA_UTIL_Q);		//SD: Could extraq_add_head be better?
   2.808 +		#elif (EXTRA == EXTRA_SLICE_WEIGHT || EXTRA == EXTRA_BLOCK_WEIGHT)
   2.809 +			extraq_add_sort_update(d, EXTRA_UTIL_Q, 0);	//put in on the weighted extraq
   2.810  		#else
   2.811  			;
   2.812  		#endif
   2.813 @@ -693,6 +916,7 @@ void sedf_wake(struct domain *d) {
   2.814  	}		
   2.815  	else {		
   2.816  		if (now < inf->absdead) {
   2.817 +			PRINT(4,"short unblocking\n");
   2.818  			//short blocking
   2.819  			inf->short_block_tot++;
   2.820  			#if (UNBLOCK <= UNBLOCK_ATROPOS)
   2.821 @@ -701,24 +925,27 @@ void sedf_wake(struct domain *d) {
   2.822  			unblock_short_cons(inf, now);
   2.823  			#elif (UNBLOCK == UNBLOCK_BURST)
   2.824  			unblock_short_burst(inf, now);
   2.825 +			#elif (UNBLOCK == UNBLOCK_EXTRA_SUPPORT)
   2.826 +			unblock_short_extra_support(inf, now);
   2.827  			#endif
   2.828 -			
   2.829 -			if (inf->extra == EXTRA_AWARE)
   2.830 +
   2.831 +			if (inf->extra & EXTRA_AWARE)
   2.832  				#if (EXTRA == EXTRA_OFF)
   2.833  				;
   2.834  				#elif (EXTRA == EXTRA_ROUNDR)
   2.835 -				extraq_add_head(d);
   2.836 -				#elif (EXTRA == EXTRA_SLICE_WEIGHT)
   2.837 -				extraq_add_sort_update(d, 0);
   2.838 +				extraq_add_head(d);			//Favour domains which got short unblocked
   2.839 +				#elif (EXTRA == EXTRA_SLICE_WEIGHT || EXTRA == EXTRA_BLOCK_WEIGHT)
   2.840 +				extraq_add_sort_update(d, EXTRA_UTIL_Q, 0);
   2.841  				#endif
   2.842  		}
   2.843  		else {
   2.844 +			PRINT(4,"long unblocking\n");
   2.845  			//long blocking
   2.846  			inf->long_block_tot++;
   2.847  			//PRINT(3,"old=%llu ",inf->absdead);
   2.848  			#if (UNBLOCK == UNBLOCK_ISOCHRONOUS_EDF)
   2.849  			unblock_long_vcons(inf, now);
   2.850 -			#elif (UNBLOCK == UNBLOCK_EDF)
   2.851 +			#elif (UNBLOCK == UNBLOCK_EDF || UNBLOCK == UNBLOCK_EXTRA_SUPPORT)
   2.852  			unblock_long_cons_b(inf, now);
   2.853  			#elif (UNBLOCK == UNBLOCK_ATROPOS)
   2.854  			unblock_long_cons_c(inf, now);
   2.855 @@ -729,17 +956,21 @@ void sedf_wake(struct domain *d) {
   2.856  			unblock_long_burst(inf, now);
   2.857  			#endif
   2.858  			
   2.859 -			if (inf->extra == EXTRA_AWARE) 
   2.860 +			if (inf->extra & EXTRA_AWARE) {
   2.861  				#if (EXTRA == EXTRA_OFF)
   2.862  				;
   2.863  				#elif (EXTRA == EXTRA_ROUNDR)
   2.864  				extraq_add_head(d);
   2.865 -				#elif (EXTRA == EXTRA_SLICE_WEIGHT)
   2.866 -				extraq_add_sort_update(d,0);
   2.867 +				#elif (EXTRA == EXTRA_SLICE_WEIGHT || EXTRA == EXTRA_BLOCK_WEIGHT)
   2.868 +				//PRINT(2,"now try to add domain %i to the extra_util_q\n",d->id);
   2.869 +				extraq_add_sort_update(d, EXTRA_UTIL_Q, 0);
   2.870 +				//PRINT(2,"added domain\n");
   2.871  				#endif
   2.872 +			}
   2.873 +			
   2.874  		}
   2.875  	}
   2.876 -	PRINT(3,"waking up domain %i (deadl= %llu period= %llu now= %llu)\n",d->id,inf->absdead,inf->period,now);
   2.877 +	PRINT(3,"woke up domain %i (deadl= %llu period= %llu now= %llu)\n",d->id,inf->absdead,inf->period,now);
   2.878  	__add_to_waitqueue_sort(d);
   2.879  	PRINT(3,"added to waitq\n");	
   2.880  	
   2.881 @@ -747,19 +978,15 @@ void sedf_wake(struct domain *d) {
   2.882  	if (inf->absblock != 0) {
   2.883  		inf->block_time_tot += now - inf->absblock;
   2.884  		inf->penalty_time_tot += PERIOD_BEGIN(inf) + inf->cputime - inf->absblock;
   2.885 -		/*if (DOM_INFO(d)->block_time_tot)
   2.886 -			PRINT(3,"penalty: %lu\n",(DOM_INFO(d)->penalty_time_tot*100)/DOM_INFO(d)->block_time_tot);*/
   2.887  	}
   2.888 -	/*if ( is_idle_task(schedule_data[d->processor].curr)) {
   2.889 -		cpu_raise_softirq(d->processor, SCHEDULE_SOFTIRQ);
   2.890 -		return;
   2.891 -	}*/
   2.892 -	
   2.893 +	//sanity check: make sure each extra-aware domain IS on the util-q!
   2.894 +	if (inf->extra & EXTRA_AWARE) {
   2.895 +		if (!extraq_on(d, EXTRA_UTIL_Q))
   2.896 +			printf("sedf_wake: domain %i is extra-aware, but NOT on L1 extraq!\n",d->id);
   2.897 +	}
   2.898  	//check whether the awakened task needs to get scheduled before the next sched. decision
   2.899  	//and check, whether we are idling and this domain is extratime aware
   2.900 -	if ((PERIOD_BEGIN(inf) < schedule_data[d->processor].s_timer.expires) ||
   2.901 -	    (is_idle_task(schedule_data[d->processor].curr) && (now + EXTRA_QUANTUM < schedule_data[d->processor].s_timer.expires) &&
   2.902 -	     (inf->extra == EXTRA_AWARE))) {
   2.903 +	if (should_switch(schedule_data[d->processor].curr, d, now)){
   2.904  #ifdef ADV_SCHED_HISTO
   2.905  		adv_sched_hist_start(d->processor);
   2.906  #endif
   2.907 @@ -772,17 +999,18 @@ void sedf_wake(struct domain *d) {
   2.908  static void sedf_dump_domain(struct domain *d) {
   2.909  	printk("%u has=%c ", d->id,
   2.910  		test_bit(DF_RUNNING, &d->flags) ? 'T':'F');
   2.911 -	printk("p=%llu sl=%llu ddl=%llu w=%u c=%llu sc=%i xtr(%s)=%llu",
   2.912 +	printk("p=%llu sl=%llu ddl=%llu w=%hu c=%llu sc=%i xtr(%s)=%llu",
   2.913  	 	DOM_INFO(d)->period, DOM_INFO(d)->slice, DOM_INFO(d)->absdead, DOM_INFO(d)->weight, d->cpu_time,
   2.914 -		DOM_INFO(d)->score, DOM_INFO(d)->extra ? "yes" : "no", DOM_INFO(d)->extra_time_tot);
   2.915 +		DOM_INFO(d)->score[EXTRA_UTIL_Q], (DOM_INFO(d)->extra & EXTRA_AWARE) ? "yes" : "no", DOM_INFO(d)->extra_time_tot);
   2.916  	if (d->cpu_time !=0)
   2.917  		printf(" (%lu%)", (DOM_INFO(d)->extra_time_tot * 100) / d->cpu_time);
   2.918  	if (DOM_INFO(d)->block_time_tot!=0)
   2.919  		printf(" pen=%lu%", (DOM_INFO(d)->penalty_time_tot * 100) / DOM_INFO(d)->block_time_tot);
   2.920  	if (DOM_INFO(d)->block_tot!=0)
   2.921 -		printf("\n   blks=%lu sh=%lu (%lu%) (shc=%lu (%lu%)) l=%lu (%lu%) avg: b=%llu p=%llu", DOM_INFO(d)->block_tot,
   2.922 +		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,
   2.923  		       DOM_INFO(d)->short_block_tot, (DOM_INFO(d)->short_block_tot * 100) / DOM_INFO(d)->block_tot,
   2.924  		       DOM_INFO(d)->short_cont, (DOM_INFO(d)->short_cont * 100) / DOM_INFO(d)->block_tot,
   2.925 +		       DOM_INFO(d)->pen_extra_blocks, DOM_INFO(d)->pen_extra_slices,
   2.926  		       DOM_INFO(d)->long_block_tot, (DOM_INFO(d)->long_block_tot * 100) / DOM_INFO(d)->block_tot,
   2.927  		       (DOM_INFO(d)->block_time_tot) / DOM_INFO(d)->block_tot,
   2.928  		       (DOM_INFO(d)->penalty_time_tot) / DOM_INFO(d)->block_tot);
   2.929 @@ -793,8 +1021,6 @@ static void sedf_dump_cpu_state(int i)
   2.930  {
   2.931  	struct list_head *list, *queue, *tmp;
   2.932  	int loop = 0;
   2.933 -/*	int found = 0;
   2.934 -	int id1st = 0;*/
   2.935  	struct sedf_dom_info *d_inf;
   2.936  	struct domain* d;
   2.937  	
   2.938 @@ -802,8 +1028,7 @@ static void sedf_dump_cpu_state(int i)
   2.939  	queue = RUNQ(i);
   2.940  	printk("RUNQ rq %lx   n: %lx, p: %lx\n",  (unsigned long)queue,
   2.941  		(unsigned long) queue->next, (unsigned long) queue->prev);
   2.942 -	list_for_each_safe ( list, tmp, queue )
   2.943 -	{
   2.944 +	list_for_each_safe ( list, tmp, queue ) {
   2.945  		printk("%3d: ",loop++);
   2.946  		d_inf = list_entry(list, struct sedf_dom_info, list);
   2.947  		sedf_dump_domain(d_inf->owner);
   2.948 @@ -812,25 +1037,26 @@ static void sedf_dump_cpu_state(int i)
   2.949  	queue = WAITQ(i); loop = 0;
   2.950  	printk("\nWAITQ rq %lx   n: %lx, p: %lx\n",  (unsigned long)queue,
   2.951  		(unsigned long) queue->next, (unsigned long) queue->prev);
   2.952 -	list_for_each_safe ( list, tmp, queue )
   2.953 -	{
   2.954 +	list_for_each_safe ( list, tmp, queue ) {
   2.955  		printk("%3d: ",loop++);
   2.956  		d_inf = list_entry(list, struct sedf_dom_info, list);
   2.957  		sedf_dump_domain(d_inf->owner);
   2.958  	}
   2.959  	
   2.960 -	queue = EXTRAQ(i); loop = 0;
   2.961 -	printk("\nEXTRAQ rq %lx   n: %lx, p: %lx\n",  (unsigned long)queue,
   2.962 +	queue = EXTRAQ(i,EXTRA_PEN_Q); loop = 0;
   2.963 +	printk("\nEXTRAQ (penalty) rq %lx   n: %lx, p: %lx\n",  (unsigned long)queue,
   2.964  		(unsigned long) queue->next, (unsigned long) queue->prev);
   2.965 -	list_for_each_safe ( list, tmp, queue )
   2.966 -	{
   2.967 -		d_inf = list_entry(list, struct sedf_dom_info, extralist);
   2.968 -		
   2.969 -/*		if (found) {
   2.970 -			if (id1st == d_inf->owner->id)
   2.971 -				break; 
   2.972 -		} 
   2.973 -		else { id1st=d_inf->owner->id; found=1;}*/
   2.974 +	list_for_each_safe ( list, tmp, queue ) {
   2.975 +		d_inf = list_entry(list, struct sedf_dom_info, extralist[EXTRA_PEN_Q]);
   2.976 +		printk("%3d: ",loop++);
   2.977 +		sedf_dump_domain(d_inf->owner);
   2.978 +	}
   2.979 +	
   2.980 +	queue = EXTRAQ(i,EXTRA_UTIL_Q); loop = 0;
   2.981 +	printk("\nEXTRAQ (utilization) rq %lx   n: %lx, p: %lx\n",  (unsigned long)queue,
   2.982 +		(unsigned long) queue->next, (unsigned long) queue->prev);
   2.983 +	list_for_each_safe ( list, tmp, queue )	{
   2.984 +		d_inf = list_entry(list, struct sedf_dom_info, extralist[EXTRA_UTIL_Q]);
   2.985  		printk("%3d: ",loop++);
   2.986  		sedf_dump_domain(d_inf->owner);
   2.987  	}
   2.988 @@ -838,7 +1064,7 @@ static void sedf_dump_cpu_state(int i)
   2.989  	loop = 0;
   2.990  	printk("\nnot on Q\n");
   2.991  	for_each_domain(d) {
   2.992 -		if (!extraq_on(d) && !__task_on_queue(d)) {
   2.993 +		if (!extraq_on(d,1) && !__task_on_queue(d)) {
   2.994  			printk("%3d: ",loop++);
   2.995  			sedf_dump_domain(d);
   2.996  		}
   2.997 @@ -896,7 +1122,7 @@ static int sedf_adjdom(struct domain *p,
   2.998  		}
   2.999  		if (sedf_adjust_weights(p,cmd))
  2.1000  			return -EINVAL;
  2.1001 -		DOM_INFO(p)->extra       = cmd->u.sedf.extratime;
  2.1002 +		DOM_INFO(p)->extra       = (DOM_INFO(p)-> extra & ~EXTRA_AWARE) | (cmd->u.sedf.extratime & EXTRA_AWARE);
  2.1003  		DOM_INFO(p)->latency     = cmd->u.sedf.latency;
  2.1004  		extraq_check(p);
  2.1005  	}
  2.1006 @@ -904,7 +1130,7 @@ static int sedf_adjdom(struct domain *p,
  2.1007  	{
  2.1008  		cmd->u.sedf.period    = DOM_INFO(p)->period;
  2.1009  		cmd->u.sedf.slice     = DOM_INFO(p)->slice;
  2.1010 -		cmd->u.sedf.extratime = DOM_INFO(p)->extra;
  2.1011 +		cmd->u.sedf.extratime = DOM_INFO(p)->extra & EXTRA_AWARE;
  2.1012  		cmd->u.sedf.latency   = DOM_INFO(p)->latency;
  2.1013  		cmd->u.sedf.weight    = DOM_INFO(p)->weight;
  2.1014  	}
     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/xen/include/xen/adv_sched_hist.h	Wed Mar 09 14:35:02 2005 +0000
     3.3 @@ -0,0 +1,40 @@
     3.4 +/* Some functions to suport advanced scheduler histograms
     3.5 +   Author: Stephan.Diestelhorst@cl.cam.ac.uk */
     3.6 +//#include <xen/sched.h>
     3.7 +//#include <xen/sched-if.h>
     3.8 +#include <asm/msr.h>
     3.9 +#define ADV_SCHED_HISTO
    3.10 +static inline void adv_sched_hist_start(int cpu) {
    3.11 +	u64 now;
    3.12 +	rdtscll(now);
    3.13 +	if (!schedule_data[cpu].save_tsc)
    3.14 +		schedule_data[cpu].save_tsc = now;
    3.15 +}
    3.16 +static inline void adv_sched_hist_from_stop(int cpu) {
    3.17 +	u64 now;
    3.18 +	rdtscll(now);
    3.19 +	if (schedule_data[cpu].save_tsc) {
    3.20 +		now -= schedule_data[cpu].save_tsc;
    3.21 +		now /= 7;
    3.22 +		if (now < BUCKETS-1)
    3.23 +			schedule_data[cpu].from_hist[now]++;
    3.24 +		else
    3.25 +			schedule_data[cpu].from_hist[BUCKETS-1]++;
    3.26 +
    3.27 +		schedule_data[cpu].save_tsc = 0;
    3.28 +	}
    3.29 +}
    3.30 +static inline void adv_sched_hist_to_stop(int cpu) {
    3.31 +	u64 now;
    3.32 +	rdtscll(now);
    3.33 +	if (schedule_data[cpu].save_tsc) {
    3.34 +		now -= schedule_data[cpu].save_tsc;
    3.35 +		now /= 24;
    3.36 +		if (now < BUCKETS-1)
    3.37 +			schedule_data[cpu].to_hist[now]++;
    3.38 +		else
    3.39 +			schedule_data[cpu].to_hist[BUCKETS-1]++;
    3.40 +
    3.41 +		schedule_data[cpu].save_tsc = 0;
    3.42 +	}
    3.43 +}