[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Xen-changelog] Extended sedf scheduler (weighted extraqueues), added enhanced scheduling histogramm



ChangeSet 1.1159.170.104, 2005/02/17 18:50:24+00:00, sd386@xxxxxxxxxxxxxxxxx

        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@xxxxxxxxxxxxxxxxxxx
http://lists.xensource.com/xen-changelog


 


Rackspace

Lists.xenproject.org is hosted with RackSpace, monitoring our
servers 24x7x365 and backed by RackSpace's Fanatical Support®.