[prev in list] [next in list] [prev in thread] [next in thread] 

List:       xen-cvs
Subject:    [Xen-changelog] Extended sedf scheduler (weighted extraqueues),
From:       BitKeeper Bot <riel () surriel ! com>
Date:       2005-02-17 18:50:24
Message-ID: E1DVCbt-0005Cp-0V () moria ! surriel ! com
[Download RAW message or body]

ChangeSet 1.1159.170.104, 2005/02/17 18:50:24+00:00, sd386@font.cl.cam.ac.uk

	Extended sedf scheduler (weighted extraqueues), added enhanced scheduling histogramm



 common/sched_sedf.c    |  258 +++++++++++++++++++++++++++++++++++++++----------
 common/schedule.c      |   92 ++++++++++++++++-
 include/xen/sched-if.h |   11 +-
 3 files changed, 302 insertions(+), 59 deletions(-)


diff -Nru a/xen/common/sched_sedf.c b/xen/common/sched_sedf.c
--- a/xen/common/sched_sedf.c	2005-05-09 14:04:09 -04:00
+++ b/xen/common/sched_sedf.c	2005-05-09 14:04:09 -04:00
@@ -13,14 +13,33 @@
 #include <xen/time.h>
 #include <xen/slab.h>
 
+//#include <xen/adv_sched_hist.h>
+
 #define SEDFLEVEL 2
 #define PRINT(_f, _a...)  \
 if ((_f)<=SEDFLEVEL) printk(_a );
 
+//various ways of unblocking domains
+#define UNBLOCK_ISOCHRONOUS_EDF 1
+#define UNBLOCK_EDF 2
+#define UNBLOCK_ATROPOS 3
+#define UNBLOCK_SHORT_RESUME 4
+#define UNBLOCK_BURST 5
+
+#define UNBLOCK UNBLOCK_BURST
+
+//various ways of treating extra-time
+#define EXTRA_OFF 1
+#define EXTRA_ROUNDR 2
+#define EXTRA_SLICE_WEIGHT 3
+#define EXTRA_BLOCK_WEIGHT 4
+
+#define EXTRA EXTRA_OFF
+
+
 /*
 	TODO:
 	TESTING!
-	implement stylish features!
 	tracing instead of PRINTs
 */
 
@@ -29,15 +48,16 @@
 #define EXTRA_NONE (0)
 #define EXTRA_AWARE (1)
 #define EXTRA_RUNNING (2)
-#define EXTRA_QUANTUM (MICROSECS(1000)) 
+#define EXTRA_QUANTUM (MICROSECS(500)) 
 #define WEIGHT_PERIOD (MILLISECS(100))
 #define WEIGHT_SAFETY (MILLISECS(5))
 
+
 struct sedf_dom_info
 {
 	struct domain		*owner;
 	struct list_head	list;
-	struct list_head	extralist;
+	struct list_head	extralist[2];
 	
 	//Parameters for EDF
 	s_time_t		period;		//=(relative deadline)
@@ -50,14 +70,17 @@
 	s_time_t		latency;
 	//extra-time status of domain
 	short			extra;
-	//weights for "Scheduling for Beginners/ Lazy/ etc."
+	//weights for "Scheduling for beginners/ lazy/ etc."
 	short			weight;
 	
 	//Bookkeeping
 	s_time_t		absdead;
 	s_time_t		sched_start;
 	s_time_t		cputime;
-	s_time_t		absblock;
+	s_time_t		absblock;	
+	s_time_t		absunblock;	//time the domain unblocked, used by burst mode to determine \
unblocking intervals +	int			score[2];	//scores for {util, block penalty}-weighted \
extratime distribution +	s_time_t		short_block_lost_tot;
 	
 	//Statistics
 	s_time_t		block_time_tot;
@@ -109,6 +132,37 @@
 	return (((EXTRALIST(d))->next != NULL) && (EXTRALIST(d)->next != EXTRALIST(d)));
 }
 
+/* adds a domain to the queue of processes which are aware of extra time. List is \
sorted by score, +   where a lower score means higher priority for an extra slice. It \
also updates the score, by simply subtracting +   a fixed value from each entry, in \
order to avoid overflow. The algorithm works by simply charging each domain +   that \
recieved extratime with an inverse of its weight. + */ 
+static inline void extraq_add_sort_update(struct domain *d, unsigned long sub) {
+	struct list_head     *cur;
+	struct sedf_dom_info *curinf;
+	
+	PRINT(3,"Adding domain %i (score= %llu) to extraq\n",d->id,DOM_INFO(d)->score);	
+	//iterate through all elements to find our "hole" and on our way update all the \
other scores +	list_for_each(cur,EXTRAQ(d->processor)){
+		curinf         = list_entry(cur,struct sedf_dom_info,extralist);
+		curinf->score -= sub;
+		if (DOM_INFO(d)->score < curinf->score)
+	 		break;
+		else
+			PRINT(4,"\tbehind domain %i (score= %llu)\n",curinf->owner->id,curinf->score);
+	}
+	//cur now contains the element, before which we'll enqueue
+	PRINT(3,"\tlist_add to %x\n",cur->prev);
+	list_add(EXTRALIST(d),cur->prev);
+	
+	//continue updating the extraq
+	if ((cur != EXTRAQ(d->processor)) && sub) 
+		for (cur = cur->next; cur != EXTRAQ(d->processor); cur = cur-> next) {
+			curinf         = list_entry(cur,struct sedf_dom_info,extralist);
+			curinf->score -= sub;
+			PRINT(4,"\tupdating domain %i (score= %llu)\n",curinf->owner->id,curinf->score);
+		}
+}
 static inline void extraq_check(struct domain *d) {
 	if (extraq_on(d)) {
 		PRINT(2,"Dom %i is on extraQ\n",d->id);
@@ -120,11 +174,10 @@
 		PRINT(2,"Dom %i is NOT on extraQ\n",d->id);
 		if (DOM_INFO(d)->extra != EXTRA_NONE) {
 			PRINT(2,"Added dom %i to extraQ\n",d->id);
-			extraq_add_tail(d);
+			extraq_add_sort_update(d, 0);
 		}
 	}
 }
-
 static inline void __del_from_queue(struct domain *d)
 {
     struct list_head *list = LIST(d);
@@ -277,29 +330,45 @@
 	int                   cpu   = current->processor;
 	struct list_head     *runq  = RUNQ(cpu);
 	struct list_head     *waitq = WAITQ(cpu);
+	#if (EXTRA > EXTRA_OFF)
 	struct list_head     *extraq = EXTRAQ(cpu);
+	#endif
 	struct list_head     *cur,*tmp;
 	struct sedf_dom_info *curinf;
 	task_slice_t          ret;
-
+	#if (EXTRA == EXTRA_SLICE_WEIGHT)
+	unsigned long         oldscore;
+	#endif
 	
 	//idle tasks don't need any of the following stuf
 	if (is_idle_task(inf->owner))
 		goto check_waitq;				//idle task doesn't get scheduled on the runq
-	
+
+	#if (EXTRA > EXTRA_OFF)
 	if (unlikely(inf->extra == EXTRA_RUNNING)) {
 		//special treatment of domains running in extra time
 		inf->extra = EXTRA_AWARE;
 		inf->cputime=0;
 		inf->extra_time_tot += now - inf->sched_start;
 		
-		extraq_del(current);				//remove extradomain from head of the queue
-		if (domain_runnable(inf->owner))
-			extraq_add_tail(current);		//and add to the tail if it is runnable => round-robin
+		extraq_del(current);					//remove extradomain from head of the queue
+		
+		#if (EXTRA == EXTRA_ROUNDR)
+		if (domain_runnable(current))
+			extraq_add_tail(current);			//and add to the tail if it is runnable => \
round-robin +		#elif (EXTRA == EXTRA_SLICE_WEIGHT)
+		oldscore   = inf->score;				//update the score
+		inf->score = (inf->period << 10) / inf->slice;		//use fixed point arithmetic with \
10 bits +		
+		if (domain_runnable(current))
+			extraq_add_sort_update(current, oldscore);	//add according to score: weighted \
round robin +		#endif
 		else
-			__del_from_queue(inf->owner);		//if domain blocked in extratime remove it from \
waitq(/runq) as well +			__del_from_queue(inf->owner);			//if domain blocked in \
extratime remove it from waitq(/runq) as well  }
-	else {
+	else
+	#endif
+	{
 		//current domain is running in real time mode
 		//update the domains cputime
 		inf->cputime += now - inf->sched_start;
@@ -315,13 +384,18 @@
 			inf->cputime -= inf->slice;
 			
 			if (inf->period < inf->period_orig) {
-				//this domain runs in latency scaling mode
-				inf->period *= 2;
-				inf->slice *= 2;
-				if ((inf->period > inf->period_orig) || (inf->slice > inf->slice_orig)) {
-					//now switch back to standard timing
-					inf->period = inf->period_orig;
-					inf->slice = inf->slice_orig;
+				//this domain runs in latency scaling or burst mode
+				#if (UNBLOCK == UNBLOCK_BURST)
+				if (now - inf->absunblock >= 2 * inf->period)
+				#endif
+				{
+					inf->period *= 2;
+					inf->slice *= 2;
+					if ((inf->period > inf->period_orig) || (inf->slice > inf->slice_orig)) {
+						//now switch back to standard timing
+						inf->period = inf->period_orig;
+						inf->slice = inf->slice_orig;
+					}
 				}
 			}
 			inf->absdead += inf->period;		//set next deadline
@@ -333,9 +407,11 @@
 			__add_to_waitqueue_sort(inf->owner);
 		else {
 			//we have a blocked realtime task
-			inf->absblock=now;
+			inf->absblock = now;
+			#if (EXTRA > EXTRA_OFF)
 			if (inf->extra == EXTRA_AWARE)
 				extraq_del(inf->owner);		//remove a blocked domain from the extraq aswell
+			#endif
 		}
 	}
 check_waitq:
@@ -393,13 +469,16 @@
 		if (!list_empty(waitq)) {
 			waitinf  = list_entry(waitq->next,struct sedf_dom_info,list);
 			//we could not find any suitable domain => look for domains that are aware of \
extratime +			#if (EXTRA > EXTRA_OFF)
 			if (!list_empty(extraq) && (PERIOD_BEGIN(waitinf) - now >= EXTRA_QUANTUM)) {
 				runinf   = list_entry(extraq->next,struct sedf_dom_info,extralist);
 				runinf->extra = EXTRA_RUNNING;
 				ret.task = runinf->owner;
 				ret.time = EXTRA_QUANTUM;
 			}
-			else {
+			else
+			#endif
+			{
 				//we have an empty run- and extraqueue or too less time => idle task!
 				ret.task = IDLETASK(cpu);
 				ret.time = PERIOD_BEGIN(waitinf) - now;
@@ -420,13 +499,19 @@
 
 static void sedf_sleep(struct domain *d) {
 	PRINT(2,"sedf_sleep was called, domain-id %i\n",d->id);
-	if ( test_bit(DF_RUNNING, &d->flags) )
+	if ( test_bit(DF_RUNNING, &d->flags) ) {
+#ifdef ADV_SCHED_HISTO
+		adv_sched_hist_start(d->processor);
+#endif
 		cpu_raise_softirq(d->processor, SCHEDULE_SOFTIRQ);
+	}
 	else  {

_______________________________________________
Xen-changelog mailing list
Xen-changelog@lists.xensource.com
http://lists.xensource.com/xen-changelog


[prev in list] [next in list] [prev in thread] [next in thread]