ia64/xen-unstable

changeset 3850:c712c4935a13

bitkeeper revision 1.1159.170.104 (4214e770zuNBDS-jq2cWXHSs1B4UOw)

Extended sedf scheduler (weighted extraqueues), added enhanced scheduling histogramm
author sd386@font.cl.cam.ac.uk
date Thu Feb 17 18:50:24 2005 +0000 (2005-02-17)
parents 3c2ccb0cf6c0
children 2d335430f7fc
files xen/common/sched_sedf.c xen/common/schedule.c xen/include/xen/sched-if.h
line diff
     1.1 --- a/xen/common/sched_sedf.c	Fri Jan 28 17:31:35 2005 +0000
     1.2 +++ b/xen/common/sched_sedf.c	Thu Feb 17 18:50:24 2005 +0000
     1.3 @@ -13,14 +13,33 @@
     1.4  #include <xen/time.h>
     1.5  #include <xen/slab.h>
     1.6  
     1.7 +//#include <xen/adv_sched_hist.h>
     1.8 +
     1.9  #define SEDFLEVEL 2
    1.10  #define PRINT(_f, _a...)  \
    1.11  if ((_f)<=SEDFLEVEL) printk(_a );
    1.12  
    1.13 +//various ways of unblocking domains
    1.14 +#define UNBLOCK_ISOCHRONOUS_EDF 1
    1.15 +#define UNBLOCK_EDF 2
    1.16 +#define UNBLOCK_ATROPOS 3
    1.17 +#define UNBLOCK_SHORT_RESUME 4
    1.18 +#define UNBLOCK_BURST 5
    1.19 +
    1.20 +#define UNBLOCK UNBLOCK_BURST
    1.21 +
    1.22 +//various ways of treating extra-time
    1.23 +#define EXTRA_OFF 1
    1.24 +#define EXTRA_ROUNDR 2
    1.25 +#define EXTRA_SLICE_WEIGHT 3
    1.26 +#define EXTRA_BLOCK_WEIGHT 4
    1.27 +
    1.28 +#define EXTRA EXTRA_OFF
    1.29 +
    1.30 +
    1.31  /*
    1.32  	TODO:
    1.33  	TESTING!
    1.34 -	implement stylish features!
    1.35  	tracing instead of PRINTs
    1.36  */
    1.37  
    1.38 @@ -29,15 +48,16 @@ if ((_f)<=SEDFLEVEL) printk(_a );
    1.39  #define EXTRA_NONE (0)
    1.40  #define EXTRA_AWARE (1)
    1.41  #define EXTRA_RUNNING (2)
    1.42 -#define EXTRA_QUANTUM (MICROSECS(1000)) 
    1.43 +#define EXTRA_QUANTUM (MICROSECS(500)) 
    1.44  #define WEIGHT_PERIOD (MILLISECS(100))
    1.45  #define WEIGHT_SAFETY (MILLISECS(5))
    1.46  
    1.47 +
    1.48  struct sedf_dom_info
    1.49  {
    1.50  	struct domain		*owner;
    1.51  	struct list_head	list;
    1.52 -	struct list_head	extralist;
    1.53 +	struct list_head	extralist[2];
    1.54  	
    1.55  	//Parameters for EDF
    1.56  	s_time_t		period;		//=(relative deadline)
    1.57 @@ -50,14 +70,17 @@ struct sedf_dom_info
    1.58  	s_time_t		latency;
    1.59  	//extra-time status of domain
    1.60  	short			extra;
    1.61 -	//weights for "Scheduling for Beginners/ Lazy/ etc."
    1.62 +	//weights for "Scheduling for beginners/ lazy/ etc."
    1.63  	short			weight;
    1.64  	
    1.65  	//Bookkeeping
    1.66  	s_time_t		absdead;
    1.67  	s_time_t		sched_start;
    1.68  	s_time_t		cputime;
    1.69 -	s_time_t		absblock;
    1.70 +	s_time_t		absblock;	
    1.71 +	s_time_t		absunblock;	//time the domain unblocked, used by burst mode to determine unblocking intervals
    1.72 +	int			score[2];	//scores for {util, block penalty}-weighted extratime distribution
    1.73 +	s_time_t		short_block_lost_tot;
    1.74  	
    1.75  	//Statistics
    1.76  	s_time_t		block_time_tot;
    1.77 @@ -109,6 +132,37 @@ static inline int extraq_on(struct domai
    1.78  	return (((EXTRALIST(d))->next != NULL) && (EXTRALIST(d)->next != EXTRALIST(d)));
    1.79  }
    1.80  
    1.81 +/* adds a domain to the queue of processes which are aware of extra time. List is sorted by score,
    1.82 +   where a lower score means higher priority for an extra slice. It also updates the score, by simply subtracting
    1.83 +   a fixed value from each entry, in order to avoid overflow. The algorithm works by simply charging each domain
    1.84 +   that recieved extratime with an inverse of its weight.
    1.85 + */ 
    1.86 +static inline void extraq_add_sort_update(struct domain *d, unsigned long sub) {
    1.87 +	struct list_head     *cur;
    1.88 +	struct sedf_dom_info *curinf;
    1.89 +	
    1.90 +	PRINT(3,"Adding domain %i (score= %llu) to extraq\n",d->id,DOM_INFO(d)->score);	
    1.91 +	//iterate through all elements to find our "hole" and on our way update all the other scores
    1.92 +	list_for_each(cur,EXTRAQ(d->processor)){
    1.93 +		curinf         = list_entry(cur,struct sedf_dom_info,extralist);
    1.94 +		curinf->score -= sub;
    1.95 +		if (DOM_INFO(d)->score < curinf->score)
    1.96 +	 		break;
    1.97 +		else
    1.98 +			PRINT(4,"\tbehind domain %i (score= %llu)\n",curinf->owner->id,curinf->score);
    1.99 +	}
   1.100 +	//cur now contains the element, before which we'll enqueue
   1.101 +	PRINT(3,"\tlist_add to %x\n",cur->prev);
   1.102 +	list_add(EXTRALIST(d),cur->prev);
   1.103 +	
   1.104 +	//continue updating the extraq
   1.105 +	if ((cur != EXTRAQ(d->processor)) && sub) 
   1.106 +		for (cur = cur->next; cur != EXTRAQ(d->processor); cur = cur-> next) {
   1.107 +			curinf         = list_entry(cur,struct sedf_dom_info,extralist);
   1.108 +			curinf->score -= sub;
   1.109 +			PRINT(4,"\tupdating domain %i (score= %llu)\n",curinf->owner->id,curinf->score);
   1.110 +		}
   1.111 +}
   1.112  static inline void extraq_check(struct domain *d) {
   1.113  	if (extraq_on(d)) {
   1.114  		PRINT(2,"Dom %i is on extraQ\n",d->id);
   1.115 @@ -120,11 +174,10 @@ static inline void extraq_check(struct d
   1.116  		PRINT(2,"Dom %i is NOT on extraQ\n",d->id);
   1.117  		if (DOM_INFO(d)->extra != EXTRA_NONE) {
   1.118  			PRINT(2,"Added dom %i to extraQ\n",d->id);
   1.119 -			extraq_add_tail(d);
   1.120 +			extraq_add_sort_update(d, 0);
   1.121  		}
   1.122  	}
   1.123  }
   1.124 -
   1.125  static inline void __del_from_queue(struct domain *d)
   1.126  {
   1.127      struct list_head *list = LIST(d);
   1.128 @@ -277,29 +330,45 @@ static task_slice_t sedf_do_schedule(s_t
   1.129  	int                   cpu   = current->processor;
   1.130  	struct list_head     *runq  = RUNQ(cpu);
   1.131  	struct list_head     *waitq = WAITQ(cpu);
   1.132 +	#if (EXTRA > EXTRA_OFF)
   1.133  	struct list_head     *extraq = EXTRAQ(cpu);
   1.134 +	#endif
   1.135  	struct list_head     *cur,*tmp;
   1.136  	struct sedf_dom_info *curinf;
   1.137  	task_slice_t          ret;
   1.138 -
   1.139 +	#if (EXTRA == EXTRA_SLICE_WEIGHT)
   1.140 +	unsigned long         oldscore;
   1.141 +	#endif
   1.142  	
   1.143  	//idle tasks don't need any of the following stuf
   1.144  	if (is_idle_task(inf->owner))
   1.145  		goto check_waitq;				//idle task doesn't get scheduled on the runq
   1.146 -	
   1.147 +
   1.148 +	#if (EXTRA > EXTRA_OFF)
   1.149  	if (unlikely(inf->extra == EXTRA_RUNNING)) {
   1.150  		//special treatment of domains running in extra time
   1.151  		inf->extra = EXTRA_AWARE;
   1.152  		inf->cputime=0;
   1.153  		inf->extra_time_tot += now - inf->sched_start;
   1.154  		
   1.155 -		extraq_del(current);				//remove extradomain from head of the queue
   1.156 -		if (domain_runnable(inf->owner))
   1.157 -			extraq_add_tail(current);		//and add to the tail if it is runnable => round-robin
   1.158 +		extraq_del(current);					//remove extradomain from head of the queue
   1.159 +		
   1.160 +		#if (EXTRA == EXTRA_ROUNDR)
   1.161 +		if (domain_runnable(current))
   1.162 +			extraq_add_tail(current);			//and add to the tail if it is runnable => round-robin
   1.163 +		#elif (EXTRA == EXTRA_SLICE_WEIGHT)
   1.164 +		oldscore   = inf->score;				//update the score
   1.165 +		inf->score = (inf->period << 10) / inf->slice;		//use fixed point arithmetic with 10 bits
   1.166 +		
   1.167 +		if (domain_runnable(current))
   1.168 +			extraq_add_sort_update(current, oldscore);	//add according to score: weighted round robin
   1.169 +		#endif
   1.170  		else
   1.171 -			__del_from_queue(inf->owner);		//if domain blocked in extratime remove it from waitq(/runq) as well
   1.172 +			__del_from_queue(inf->owner);			//if domain blocked in extratime remove it from waitq(/runq) as well
   1.173  	}
   1.174 -	else {
   1.175 +	else
   1.176 +	#endif
   1.177 +	{
   1.178  		//current domain is running in real time mode
   1.179  		//update the domains cputime
   1.180  		inf->cputime += now - inf->sched_start;
   1.181 @@ -315,13 +384,18 @@ static task_slice_t sedf_do_schedule(s_t
   1.182  			inf->cputime -= inf->slice;
   1.183  			
   1.184  			if (inf->period < inf->period_orig) {
   1.185 -				//this domain runs in latency scaling mode
   1.186 -				inf->period *= 2;
   1.187 -				inf->slice *= 2;
   1.188 -				if ((inf->period > inf->period_orig) || (inf->slice > inf->slice_orig)) {
   1.189 -					//now switch back to standard timing
   1.190 -					inf->period = inf->period_orig;
   1.191 -					inf->slice = inf->slice_orig;
   1.192 +				//this domain runs in latency scaling or burst mode
   1.193 +				#if (UNBLOCK == UNBLOCK_BURST)
   1.194 +				if (now - inf->absunblock >= 2 * inf->period)
   1.195 +				#endif
   1.196 +				{
   1.197 +					inf->period *= 2;
   1.198 +					inf->slice *= 2;
   1.199 +					if ((inf->period > inf->period_orig) || (inf->slice > inf->slice_orig)) {
   1.200 +						//now switch back to standard timing
   1.201 +						inf->period = inf->period_orig;
   1.202 +						inf->slice = inf->slice_orig;
   1.203 +					}
   1.204  				}
   1.205  			}
   1.206  			inf->absdead += inf->period;		//set next deadline
   1.207 @@ -333,9 +407,11 @@ static task_slice_t sedf_do_schedule(s_t
   1.208  			__add_to_waitqueue_sort(inf->owner);
   1.209  		else {
   1.210  			//we have a blocked realtime task
   1.211 -			inf->absblock=now;
   1.212 +			inf->absblock = now;
   1.213 +			#if (EXTRA > EXTRA_OFF)
   1.214  			if (inf->extra == EXTRA_AWARE)
   1.215  				extraq_del(inf->owner);		//remove a blocked domain from the extraq aswell
   1.216 +			#endif
   1.217  		}
   1.218  	}
   1.219  check_waitq:
   1.220 @@ -393,13 +469,16 @@ check_waitq:
   1.221  		if (!list_empty(waitq)) {
   1.222  			waitinf  = list_entry(waitq->next,struct sedf_dom_info,list);
   1.223  			//we could not find any suitable domain => look for domains that are aware of extratime
   1.224 +			#if (EXTRA > EXTRA_OFF)
   1.225  			if (!list_empty(extraq) && (PERIOD_BEGIN(waitinf) - now >= EXTRA_QUANTUM)) {
   1.226  				runinf   = list_entry(extraq->next,struct sedf_dom_info,extralist);
   1.227  				runinf->extra = EXTRA_RUNNING;
   1.228  				ret.task = runinf->owner;
   1.229  				ret.time = EXTRA_QUANTUM;
   1.230  			}
   1.231 -			else {
   1.232 +			else
   1.233 +			#endif
   1.234 +			{
   1.235  				//we have an empty run- and extraqueue or too less time => idle task!
   1.236  				ret.task = IDLETASK(cpu);
   1.237  				ret.time = PERIOD_BEGIN(waitinf) - now;
   1.238 @@ -420,13 +499,19 @@ check_waitq:
   1.239  
   1.240  static void sedf_sleep(struct domain *d) {
   1.241  	PRINT(2,"sedf_sleep was called, domain-id %i\n",d->id);
   1.242 -	if ( test_bit(DF_RUNNING, &d->flags) )
   1.243 +	if ( test_bit(DF_RUNNING, &d->flags) ) {
   1.244 +#ifdef ADV_SCHED_HISTO
   1.245 +		adv_sched_hist_start(d->processor);
   1.246 +#endif
   1.247  		cpu_raise_softirq(d->processor, SCHEDULE_SOFTIRQ);
   1.248 +	}
   1.249  	else  {
   1.250  		if ( __task_on_queue(d) )
   1.251  			__del_from_queue(d);
   1.252 +		#if (EXTRA > EXTRA_OFF)
   1.253  		if (extraq_on(d))
   1.254  			extraq_del(d);
   1.255 +		#endif
   1.256  	}
   1.257  }
   1.258  
   1.259 @@ -490,9 +575,8 @@ static void sedf_sleep(struct domain *d)
   1.260   *      (or even worse: allocate a new full slice for the domain) 
   1.261   *     -either behaviour can lead to missed deadlines in other domains as opposed to approaches 1,2a,2b
   1.262   */
   1.263 -static inline void unblock_short_vcons(struct sedf_dom_info* inf, s_time_t now) { inf->absdead += inf->period;}
   1.264 -static inline void unblock_long_vcons(struct sedf_dom_info* inf, s_time_t now) {
   1.265 -	inf->absdead += ((now - inf->absdead) / inf->period + 1) * inf->period;		//very conservative
   1.266 +static inline void unblock_short_vcons(struct sedf_dom_info* inf, s_time_t now) { 
   1.267 +	inf->absdead += inf->period;
   1.268  	inf->cputime = 0;
   1.269  }
   1.270  
   1.271 @@ -500,19 +584,23 @@ static inline void unblock_short_cons(st
   1.272  	inf->cputime += now - inf->absblock;						//treat blocked time as consumed by the domain
   1.273  	if (inf->cputime + EXTRA_QUANTUM > inf->slice) {
   1.274  		//we don't have a reasonable amount of time in our slice left :(
   1.275 -		inf->cputime=0;
   1.276 -		inf->absdead += inf->period;						//start in next period!
   1.277 +		unblock_short_vcons(inf, now);						//start in next period!
   1.278  	}
   1.279  	else
   1.280 -		inf->short_cont++;
   1.281 +		inf->short_cont++;							//we let the domain run in the current period
   1.282  }
   1.283 +
   1.284 +static inline void unblock_long_vcons(struct sedf_dom_info* inf, s_time_t now) {
   1.285 +	inf->absdead += ((now - inf->absdead) / inf->period + 1) * inf->period;		//very conservative
   1.286 +	inf->cputime = 0;
   1.287 +}
   1.288 +
   1.289  static inline void unblock_long_cons_a(struct sedf_dom_info* inf, s_time_t now) {
   1.290  	inf->cputime = (now - inf->absdead) % inf->period;				//treat the time the domain was blocked in the CURRENT
   1.291  											//period as consumed by the domain
   1.292  	if (inf->cputime + EXTRA_QUANTUM > inf->slice) {
   1.293  		//we don't have a reasonable amount of time in our slice left :(
   1.294 -		inf->cputime=0;
   1.295 -		inf->absdead += inf->period;						//start in next period!
   1.296 +		unblock_long_vcons(inf, now);						//start in next period!
   1.297  	}
   1.298  }
   1.299  static inline void unblock_long_cons_b(struct sedf_dom_info* inf,s_time_t now) {
   1.300 @@ -521,20 +609,52 @@ static inline void unblock_long_cons_b(s
   1.301  }
   1.302  static inline void unblock_long_cons_c(struct sedf_dom_info* inf,s_time_t now) {
   1.303  	if (likely(inf->latency)) {
   1.304 -		//sclae the slice and period accordingly to the latency hint
   1.305 +		//scale the slice and period accordingly to the latency hint
   1.306  		inf->period = inf->latency;						//reduce period temporarily to the latency hint
   1.307 -		ASSERT((inf->latency < ULONG_MAX) && (inf->slice_orig < ULONG_MAX));	//this results in max. 4s slice/period length
   1.308 -		inf->slice = (inf->latency * inf->slice_orig) / inf->period_orig;	//scale slice accordingly, so that utilisation stays the same
   1.309 +		ASSERT((inf->period < ULONG_MAX) && (inf->slice_orig < ULONG_MAX));	//this results in max. 4s slice/period length
   1.310 +		inf->slice = (inf->period * inf->slice_orig) / inf->period_orig;	//scale slice accordingly, so that utilisation stays the same
   1.311  	}	
   1.312  	else {
   1.313  		//we don't have a latency hint.. use some other technique
   1.314 -		inf->absdead = now + inf->period;					//Conservative 2b...
   1.315 -		inf->cputime = 0;
   1.316 +		unblock_long_cons_b(inf, now);
   1.317  	}
   1.318  }
   1.319 +//a new idea of dealing with short blocks: burst period scaling
   1.320 +static inline void unblock_short_burst(struct sedf_dom_info* inf, s_time_t now) {
   1.321 +	inf->cputime += now - inf->absblock;						//treat blocked time as consumed by the domain
   1.322 +	
   1.323 +	if (inf->cputime + EXTRA_QUANTUM <= inf->slice) {
   1.324 +		inf->short_cont++;							//we let the domain run in the current period
   1.325 +	}
   1.326 +	else {
   1.327 +		//we don't have a reasonable amount of time in our slice left => switch to burst mode
   1.328 +		if (likely(inf->absunblock)) {
   1.329 +			inf->period = now - inf->absunblock;				//set the period-length to the current blocking interval
   1.330 +			ASSERT((inf->period < ULONG_MAX) && (inf->slice_orig < ULONG_MAX));//this results in max. 4s slice/period length
   1.331 +			inf->slice = (inf->period * inf->slice_orig) / inf->period_orig;//scale slice accordingly, so that utilisation stays the same
   1.332 +		}
   1.333 +		else {
   1.334 +			inf->cputime=0;							//in Case we haven't unblocked before
   1.335 +			inf->absdead += inf->period;					//start in next period!
   1.336 +		}
   1.337 +	}
   1.338 +	inf->absunblock = now;
   1.339 +}
   1.340 +static inline void unblock_long_burst(struct sedf_dom_info* inf,s_time_t now) {
   1.341 +	if (unlikely(inf->latency && (inf->period > inf->latency))) {
   1.342 +		//sclae the slice and period accordingly to the latency hint
   1.343 +		inf->period = inf->latency;						//reduce period temporarily to the latency hint
   1.344 +		ASSERT((inf->period < ULONG_MAX) && (inf->slice_orig < ULONG_MAX));	//this results in max. 4s slice/period length
   1.345 +		inf->slice = (inf->period * inf->slice_orig) / inf->period_orig;	//scale slice accordingly, so that utilisation stays the same
   1.346 +	}
   1.347 +	else {
   1.348 +		//we don't have a latency hint.. or we are currently in "burst mode": use some other technique
   1.349 +		//this should be in fact the normal way of operation, when we are in sync with the device!
   1.350 +		unblock_long_cons_b(inf, now);
   1.351 +	}
   1.352 +	inf->absunblock = now;
   1.353 +}
   1.354  
   1.355 -/*static inline void unblock_short_vcons
   1.356 -static inline void unblock_short_vcons*/
   1.357  void sedf_wake(struct domain *d) {
   1.358  	//for the first try just implement the "very conservative" way of waking domains up
   1.359  	s_time_t              now = NOW();
   1.360 @@ -555,16 +675,19 @@ void sedf_wake(struct domain *d) {
   1.361  	if (unlikely(inf->absdead == 0))
   1.362  		inf->absdead = now + inf->slice;			//initial setup of the deadline
   1.363  		
   1.364 -	//very conservative way of unblocking
   1.365 -	//make sure that the start of the period for this
   1.366 -	//domain is happening in the future
   1.367  	PRINT(3,"waking up domain %i (deadl= %llu period= %llu now= %llu)\n",d->id,inf->absdead,inf->period,now);
   1.368  	
   1.369  	inf->block_tot++;
   1.370  	if (unlikely(now< PERIOD_BEGIN(inf))) {
   1.371  		//this might happen, imagine unblocking in extra-time!
   1.372  		if (likely(inf->extra == EXTRA_AWARE)) 
   1.373 +		#if (EXTRA == EXTRA_ROUNDR)
   1.374  			extraq_add_tail(d);				//SD: Could extraq_add_head be better?
   1.375 +		#elif (EXTRA == EXTRA_SLICE_WEIGHT)
   1.376 +			extraq_add_sort_update(d, 0);
   1.377 +		#else
   1.378 +			;
   1.379 +		#endif
   1.380  		//else
   1.381  		//This is very very unlikely, ie. might even be an error?!
   1.382  	}		
   1.383 @@ -572,19 +695,48 @@ void sedf_wake(struct domain *d) {
   1.384  		if (now < inf->absdead) {
   1.385  			//short blocking
   1.386  			inf->short_block_tot++;
   1.387 -			//unblock_short_vcons(inf, now);
   1.388 +			#if (UNBLOCK <= UNBLOCK_ATROPOS)
   1.389 +			unblock_short_vcons(inf, now);
   1.390 +			#elif (UNBLOCK == UNBLOCK_SHORT_RESUME)
   1.391  			unblock_short_cons(inf, now);
   1.392 -			if (inf->extra == EXTRA_AWARE) 
   1.393 +			#elif (UNBLOCK == UNBLOCK_BURST)
   1.394 +			unblock_short_burst(inf, now);
   1.395 +			#endif
   1.396 +			
   1.397 +			if (inf->extra == EXTRA_AWARE)
   1.398 +				#if (EXTRA == EXTRA_OFF)
   1.399 +				;
   1.400 +				#elif (EXTRA == EXTRA_ROUNDR)
   1.401  				extraq_add_head(d);
   1.402 +				#elif (EXTRA == EXTRA_SLICE_WEIGHT)
   1.403 +				extraq_add_sort_update(d, 0);
   1.404 +				#endif
   1.405  		}
   1.406  		else {
   1.407  			//long blocking
   1.408  			inf->long_block_tot++;
   1.409  			//PRINT(3,"old=%llu ",inf->absdead);
   1.410 -			//unblock_long_vcons(inf, now);
   1.411 -			unblock_long_cons_c(inf,now);
   1.412 +			#if (UNBLOCK == UNBLOCK_ISOCHRONOUS_EDF)
   1.413 +			unblock_long_vcons(inf, now);
   1.414 +			#elif (UNBLOCK == UNBLOCK_EDF)
   1.415 +			unblock_long_cons_b(inf, now);
   1.416 +			#elif (UNBLOCK == UNBLOCK_ATROPOS)
   1.417 +			unblock_long_cons_c(inf, now);
   1.418 +			#elif (UNBLOCK == UNBLOCK_SHORT_RESUME)
   1.419 +			unblock_long_cons_b(inf, now);
   1.420 +			//unblock_short_cons_c(inf, now);
   1.421 +			#elif (UNBLOCK == UNBLOCK_BURST)
   1.422 +			unblock_long_burst(inf, now);
   1.423 +			#endif
   1.424 +			
   1.425  			if (inf->extra == EXTRA_AWARE) 
   1.426 -				extraq_add_tail(d);
   1.427 +				#if (EXTRA == EXTRA_OFF)
   1.428 +				;
   1.429 +				#elif (EXTRA == EXTRA_ROUNDR)
   1.430 +				extraq_add_head(d);
   1.431 +				#elif (EXTRA == EXTRA_SLICE_WEIGHT)
   1.432 +				extraq_add_sort_update(d,0);
   1.433 +				#endif
   1.434  		}
   1.435  	}
   1.436  	PRINT(3,"waking up domain %i (deadl= %llu period= %llu now= %llu)\n",d->id,inf->absdead,inf->period,now);
   1.437 @@ -592,7 +744,7 @@ void sedf_wake(struct domain *d) {
   1.438  	PRINT(3,"added to waitq\n");	
   1.439  	
   1.440  	//do some statistics here...
   1.441 -	if (inf->absblock!=0) {
   1.442 +	if (inf->absblock != 0) {
   1.443  		inf->block_time_tot += now - inf->absblock;
   1.444  		inf->penalty_time_tot += PERIOD_BEGIN(inf) + inf->cputime - inf->absblock;
   1.445  		/*if (DOM_INFO(d)->block_time_tot)
   1.446 @@ -607,8 +759,12 @@ void sedf_wake(struct domain *d) {
   1.447  	//and check, whether we are idling and this domain is extratime aware
   1.448  	if ((PERIOD_BEGIN(inf) < schedule_data[d->processor].s_timer.expires) ||
   1.449  	    (is_idle_task(schedule_data[d->processor].curr) && (now + EXTRA_QUANTUM < schedule_data[d->processor].s_timer.expires) &&
   1.450 -	     (inf->extra == EXTRA_AWARE)))
   1.451 +	     (inf->extra == EXTRA_AWARE))) {
   1.452 +#ifdef ADV_SCHED_HISTO
   1.453 +		adv_sched_hist_start(d->processor);
   1.454 +#endif
   1.455  		cpu_raise_softirq(d->processor, SCHEDULE_SOFTIRQ);
   1.456 +	}
   1.457  }
   1.458  
   1.459  
   1.460 @@ -616,9 +772,9 @@ void sedf_wake(struct domain *d) {
   1.461  static void sedf_dump_domain(struct domain *d) {
   1.462  	printk("%u has=%c ", d->id,
   1.463  		test_bit(DF_RUNNING, &d->flags) ? 'T':'F');
   1.464 -	printk("p=%llu sl=%llu ddl=%llu w=%u c=%llu xtr(%s)=%llu",
   1.465 +	printk("p=%llu sl=%llu ddl=%llu w=%u c=%llu sc=%i xtr(%s)=%llu",
   1.466  	 	DOM_INFO(d)->period, DOM_INFO(d)->slice, DOM_INFO(d)->absdead, DOM_INFO(d)->weight, d->cpu_time,
   1.467 -		DOM_INFO(d)->extra ? "yes" : "no", DOM_INFO(d)->extra_time_tot);
   1.468 +		DOM_INFO(d)->score, DOM_INFO(d)->extra ? "yes" : "no", DOM_INFO(d)->extra_time_tot);
   1.469  	if (d->cpu_time !=0)
   1.470  		printf(" (%lu%)", (DOM_INFO(d)->extra_time_tot * 100) / d->cpu_time);
   1.471  	if (DOM_INFO(d)->block_time_tot!=0)
     2.1 --- a/xen/common/schedule.c	Fri Jan 28 17:31:35 2005 +0000
     2.2 +++ b/xen/common/schedule.c	Thu Feb 17 18:50:24 2005 +0000
     2.3 @@ -34,6 +34,8 @@ string_param("sched", opt_sched);
     2.4  
     2.5  /*#define WAKE_HISTO*/
     2.6  /*#define BLOCKTIME_HISTO*/
     2.7 +/*#define ADV_SCHED_HISTO*/
     2.8 +//#include <xen/adv_sched_hist.h>
     2.9  
    2.10  #if defined(WAKE_HISTO)
    2.11  #define BUCKETS 31
    2.12 @@ -198,6 +200,10 @@ void domain_wake(struct domain *d)
    2.13  /* Block the currently-executing domain until a pertinent event occurs. */
    2.14  long do_block(void)
    2.15  {
    2.16 +#ifdef ADV_SCHED_HISTO
    2.17 +    adv_sched_hist_start(current->processor);
    2.18 +#endif
    2.19 +
    2.20      ASSERT(current->id != IDLE_DOMAIN_ID);
    2.21      current->shared_info->vcpu_data[0].evtchn_upcall_mask = 0;
    2.22      set_bit(DF_BLOCKED, &current->flags);
    2.23 @@ -209,6 +215,10 @@ long do_block(void)
    2.24  /* Voluntarily yield the processor for this allocation. */
    2.25  static long do_yield(void)
    2.26  {
    2.27 +#ifdef ADV_SCHED_HISTO
    2.28 +    adv_sched_hist_start(current->processor);
    2.29 +#endif
    2.30 +    
    2.31      TRACE_2D(TRC_SCHED_YIELD, current->id, current);
    2.32      __enter_scheduler();
    2.33      return 0;
    2.34 @@ -328,8 +338,14 @@ void __enter_scheduler(void)
    2.35      perfc_incrc(sched_run);
    2.36      
    2.37      spin_lock_irq(&schedule_data[cpu].schedule_lock);
    2.38 - 
    2.39 +
    2.40 +#ifdef ADV_SCHED_HISTO
    2.41 +    adv_sched_hist_from_stop(cpu);
    2.42 +#endif
    2.43      now = NOW();
    2.44 +#ifdef ADV_SCHED_HISTO
    2.45 +    adv_sched_hist_start(cpu);
    2.46 +#endif
    2.47  
    2.48      rem_ac_timer(&schedule_data[cpu].s_timer);
    2.49      
    2.50 @@ -369,9 +385,12 @@ void __enter_scheduler(void)
    2.51      if ( !is_idle_task(next) )
    2.52          update_dom_time(next->shared_info);
    2.53  
    2.54 -    if ( unlikely(prev == next) )
    2.55 +    if ( unlikely(prev == next) ) {
    2.56 +#ifdef ADV_SCHED_HISTO
    2.57 +        adv_sched_hist_to_stop(cpu);
    2.58 +#endif
    2.59          return;
    2.60 -    
    2.61 +    }
    2.62      perfc_incrc(sched_ctx);
    2.63  
    2.64  #if defined(WAKE_HISTO)
    2.65 @@ -393,7 +412,6 @@ void __enter_scheduler(void)
    2.66  #endif
    2.67  
    2.68      TRACE_2D(TRC_SCHED_SWITCH, next->id, next);
    2.69 -
    2.70      switch_to(prev, next);
    2.71  
    2.72      /*
    2.73 @@ -407,7 +425,10 @@ void __enter_scheduler(void)
    2.74      /* Mark a timer event for the newly-scheduled domain. */
    2.75      if ( !is_idle_task(next) )
    2.76          send_guest_virq(next, VIRQ_TIMER);
    2.77 -    
    2.78 +
    2.79 +#ifdef ADV_SCHED_HISTO
    2.80 +    adv_sched_hist_to_stop(cpu);
    2.81 +#endif
    2.82      schedule_tail(next);
    2.83  
    2.84      BUG();
    2.85 @@ -431,6 +452,10 @@ int idle_cpu(int cpu)
    2.86  /* The scheduler timer: force a run through the scheduler*/
    2.87  static void s_timer_fn(unsigned long unused)
    2.88  {
    2.89 +#ifdef ADV_SCHED_HISTO
    2.90 +    adv_sched_hist_start(current->processor);
    2.91 +#endif
    2.92 +
    2.93      TRACE_0D(TRC_SCHED_S_TIMER_FN);
    2.94      raise_softirq(SCHEDULE_SOFTIRQ);
    2.95      perfc_incrc(sched_irq);
    2.96 @@ -572,6 +597,63 @@ void reset_sched_histo(unsigned char key
    2.97              schedule_data[j].hist[i] = 0;
    2.98  }
    2.99  #else
   2.100 +#if defined(ADV_SCHED_HISTO)
   2.101 +void print_sched_histo(unsigned char key)
   2.102 +{
   2.103 +    int i, j, k,t;
   2.104 +    printf("Hello!\n");
   2.105 +    for ( k = 0; k < smp_num_cpus; k++ )
   2.106 +    {
   2.107 +        j = 0;
   2.108 +	t = 0;
   2.109 +        printf ("CPU[%02d]: scheduler latency histogram FROM (ms:[count])\n", k);
   2.110 +        for ( i = 0; i < BUCKETS; i++ )
   2.111 +        {
   2.112 +            //if ( schedule_data[k].hist[i] != 0 )
   2.113 +            {
   2.114 +	        t += schedule_data[k].from_hist[i];
   2.115 +                if ( i < BUCKETS-1 )
   2.116 +                    printk("%3d:[%7u]    ", i, schedule_data[k].from_hist[i]);
   2.117 +                else
   2.118 +                    printk(" >:[%7u]    ", schedule_data[k].from_hist[i]);
   2.119 +                //if ( !(++j % 5) )
   2.120 +                    printk("\n");
   2.121 +            }
   2.122 +        }
   2.123 +        printk("\nTotal: %i\n",t);
   2.124 +    }
   2.125 +    for ( k = 0; k < smp_num_cpus; k++ )
   2.126 +    {
   2.127 +        j = 0; t = 0;
   2.128 +        printf ("CPU[%02d]: scheduler latency histogram TO (ms:[count])\n", k);
   2.129 +        for ( i = 0; i < BUCKETS; i++ )
   2.130 +        {
   2.131 +            //if ( schedule_data[k].hist[i] != 0 )
   2.132 +            {
   2.133 +	    	t += schedule_data[k].from_hist[i];
   2.134 +                if ( i < BUCKETS-1 )
   2.135 +                    printk("%3d:[%7u]    ", i, schedule_data[k].to_hist[i]);
   2.136 +                else
   2.137 +                    printk(" >:[%7u]    ", schedule_data[k].to_hist[i]);
   2.138 +                //if ( !(++j % 5) )
   2.139 +                    printk("\n");
   2.140 +            }
   2.141 +        }
   2.142 +	printk("\nTotal: %i\n",t);
   2.143 +    }
   2.144 +      
   2.145 +}
   2.146 +void reset_sched_histo(unsigned char key)
   2.147 +{
   2.148 +    int i, j;
   2.149 +    for ( j = 0; j < smp_num_cpus; j++ ) {
   2.150 +        for ( i=0; i < BUCKETS; i++ ) 
   2.151 +            schedule_data[j].to_hist[i] = schedule_data[j].from_hist[i] = 0;
   2.152 +        schedule_data[j].save_tsc = 0;
   2.153 +    }
   2.154 +}
   2.155 +#else
   2.156  void print_sched_histo(unsigned char key) { }
   2.157  void reset_sched_histo(unsigned char key) { }
   2.158  #endif
   2.159 +#endif
     3.1 --- a/xen/include/xen/sched-if.h	Fri Jan 28 17:31:35 2005 +0000
     3.2 +++ b/xen/include/xen/sched-if.h	Thu Feb 17 18:50:24 2005 +0000
     3.3 @@ -7,7 +7,9 @@
     3.4   * Portions by Mark Williamson are (C) 2004 Intel Research Cambridge
     3.5   */
     3.6  
     3.7 -#define BUCKETS 10
     3.8 +//#define ADV_SCHED_HISTO
     3.9 +#define BUCKETS  10
    3.10 +/*300*/
    3.11  
    3.12  typedef struct schedule_data_st
    3.13  {
    3.14 @@ -17,6 +19,11 @@ typedef struct schedule_data_st
    3.15      struct domain       *idle;          /* idle task for this cpu */
    3.16      void *              sched_priv;
    3.17      struct ac_timer     s_timer;        /* scheduling timer  */
    3.18 +#ifdef ADV_SCHED_HISTO
    3.19 +    u32			to_hist[BUCKETS];
    3.20 +    u32			from_hist[BUCKETS];
    3.21 +    u64			save_tsc;
    3.22 +#endif
    3.23  #ifdef BUCKETS
    3.24      u32                 hist[BUCKETS];  /* for scheduler latency histogram */
    3.25  #endif
    3.26 @@ -55,5 +62,3 @@ struct scheduler
    3.27  
    3.28  /* per CPU scheduler information */
    3.29  extern schedule_data_t schedule_data[];
    3.30 -
    3.31 -