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

[Xen-changelog] Finished port of the sEDF scheduler to 3.0.



ChangeSet 1.1346.1.2, 2005/04/22 18:05:34+01:00, sd386@xxxxxxxxxxxxxxxxx

        Finished port of the sEDF scheduler to 3.0.
        sEDF is a new scheduler for Xen, that provides time guarantees using 
        an EDF like algorithm, and also distributes idle cpu time on a weighted
        fair share policy.
        
        Signed off by: Stephan.Diestelhorst@{cl.cam.ac.uk , inf.tu-dresden.de}



 sched_sedf.c |  673 +++++++++++++++++++++++++++++++----------------------------
 1 files changed, 365 insertions(+), 308 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:07:06 -04:00
+++ b/xen/common/sched_sedf.c   2005-05-09 14:07:06 -04:00
@@ -56,10 +56,12 @@
 #define WEIGHT_PERIOD (MILLISECS(100))
 #define WEIGHT_SAFETY (MILLISECS(5))
 
-
-struct sedf_dom_info
+struct sedf_dom_info {
+       struct domain           *domain;
+};
+struct sedf_edom_info
 {
-       struct domain           *owner;
+       struct exec_domain      *exec_domain;
        struct list_head        list;
        struct list_head        extralist[2];
        
@@ -79,13 +81,12 @@
        short                   weight;
        
        /*Bookkeeping*/
-       s_time_t                absdead;
-       s_time_t                sched_start;
+       s_time_t                deadl_abs;
+       s_time_t                sched_start_abs;
        s_time_t                cputime;
-       s_time_t                absblock;
-       
-       /*time the domain unblocked, used to determine unblocking intervals*/
-       s_time_t                absunblock;
+       /* times the domain un-/blocked */
+       s_time_t                block_abs;
+       s_time_t                unblock_abs;
        
        /*scores for {util, block penalty}-weighted extratime distribution*/
        int                     score[2];       
@@ -112,48 +113,47 @@
        struct list_head extraq[2];
 };
 
-#define DOM_INFO(d)            ((struct sedf_dom_info *)((d)->sched_priv))
+#define EDOM_INFO(d)           ((struct sedf_edom_info *)((d)->ed_sched_priv))
 #define CPU_INFO(cpu)  ((struct sedf_cpu_info *)schedule_data[cpu].sched_priv)
-#define LIST(d)                        (&DOM_INFO(d)->list)
-#define EXTRALIST(d,i)         (&(DOM_INFO(d)->extralist[i]))
+#define LIST(d)                        (&EDOM_INFO(d)->list)
+#define EXTRALIST(d,i)         (&(EDOM_INFO(d)->extralist[i]))
 #define RUNQ(cpu)              (&CPU_INFO(cpu)->runnableq)
 #define WAITQ(cpu)             (&CPU_INFO(cpu)->waitq)
 #define EXTRAQ(cpu,i)                  (&(CPU_INFO(cpu)->extraq[i]))
-#define IDLETASK(cpu)          ((struct domain *)schedule_data[cpu].idle)
+#define IDLETASK(cpu)          ((struct exec_domain *)schedule_data[cpu].idle)
 
-#define PERIOD_BEGIN(inf)      ((inf)->absdead - (inf)->period)
+#define PERIOD_BEGIN(inf)      ((inf)->deadl_abs - (inf)->period)
 
 #define MIN(x,y) (((x)<(y))?(x):(y))
 #define DIV_UP(x,y) (((x) + (y) - 1) / y)
 
-static xmem_cache_t *dom_info_cache;
-
 static void sedf_dump_cpu_state(int i);
 
-static inline int extraq_on(struct domain *d, int i) {
+static inline int extraq_on(struct exec_domain *d, int i) {
        return ((EXTRALIST(d,i)->next != NULL) &&
                (EXTRALIST(d,i)->next != EXTRALIST(d,i)));
 }
 
-static inline void extraq_add_head(struct domain *d, int i)
+static inline void extraq_add_head(struct exec_domain *d, int i)
 {
     list_add(EXTRALIST(d,i), EXTRAQ(d->processor,i));
 }
 
-static inline void extraq_add_tail(struct domain *d, int i)
+static inline void extraq_add_tail(struct exec_domain *d, int i)
 {
     list_add_tail(EXTRALIST(d,i), EXTRAQ(d->processor,i));
 }
 
-static inline void extraq_del(struct domain *d, int i)
+static inline void extraq_del(struct exec_domain *d, int i)
 {
        struct list_head *list = EXTRALIST(d,i);
        /*if (!extraq_on(d,i)) {
-               PRINT(0,"extraq_del: domain %i is NOT on L%i extraq "\
-                       "HALTING\n",d->id,i);
+               PRINT(0,"extraq_del: domain %i.%i is NOT on L%i extraq "\
+                       "HALTING\n",d->domain->id, d->eid,i);
                sedf_dump_cpu_state(0);(*((int*)0))++;
        }*/
-       PRINT(3, "Removing domain %i from L%i extraq\n", d->id,i);      
+       PRINT(3, "Removing domain %i.%i from L%i extraq\n", d->domain->id,
+          d->eid, i);  
        list_del(list);
        list->next = NULL;
 }
@@ -164,28 +164,29 @@
    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, int i, int sub) {
-       struct list_head     *cur;
-       struct sedf_dom_info *curinf;
+static inline void extraq_add_sort_update(struct exec_domain *d, int i, int 
sub) {
+       struct list_head      *cur;
+       struct sedf_edom_info *curinf;
        
        /*if (extraq_on(d,i)) {
-               PRINT(0,"extraq_add_sort_update: domain %i is already on "\
-                       "L%i extraq! HALTING\n",d->id,i);
+               PRINT(0,"extraq_add_sort_update: domain %i.%i is already on "\
+                       "L%i extraq! HALTING\n",d->domain->id, d->eid, i);
                sedf_dump_cpu_state(0);(*((int*)0))++;
        }*/
-       PRINT(3, "Adding domain %i (score= %i, short_pen= %lli) to L%i "\
-                "extraq\n", d->id, DOM_INFO(d)->score[i],
-                DOM_INFO(d)->short_block_lost_tot, i); 
+       PRINT(3, "Adding domain %i.%i (score= %i, short_pen= %lli) to L%i "\
+                "extraq\n", d->domain->id, d->eid, EDOM_INFO(d)->score[i],
+                EDOM_INFO(d)->short_block_lost_tot, i);        
        /*iterate through all elements to find our "hole" and on our way
          update all the other scores*/
        list_for_each(cur,EXTRAQ(d->processor,i)){
-               curinf = list_entry(cur,struct sedf_dom_info,extralist[i]);
+               curinf = list_entry(cur,struct sedf_edom_info,extralist[i]);
                curinf->score[i] -= sub;
-               if (DOM_INFO(d)->score[i] < curinf->score[i])
+               if (EDOM_INFO(d)->score[i] < curinf->score[i])
                        break;
                else
-                       PRINT(4,"\tbehind domain %i (score= %i)\n",
-                             curinf->owner->id, curinf->score[i]);
+                       PRINT(4,"\tbehind domain %i.%i (score= %i)\n",
+                             curinf->exec_domain->domain->id,
+                             curinf->exec_domain->eid, curinf->score[i]);
        }
        /*cur now contains the element, before which we'll enqueue*/
        PRINT(3, "\tlist_add to %x\n", cur->prev);
@@ -195,24 +196,27 @@
        if ((cur != EXTRAQ(d->processor,i)) && sub)
                for (cur = cur->next; cur != EXTRAQ(d->processor,i);
                     cur = cur-> next) {
-                       curinf = list_entry(cur,struct sedf_dom_info,
+                       curinf = list_entry(cur,struct sedf_edom_info,
                                extralist[i]);
                        curinf->score[i] -= sub;
-                       PRINT(4, "\tupdating domain %i (score= %llu)\n",
-                             curinf->owner->id, curinf->score[i]);
+                       PRINT(4, "\tupdating domain %i.%i (score= %llu)\n",
+                             curinf->exec_domain->domain->id, 
+                             curinf->exec_domain->eid, curinf->score[i]);
                }
 }
-static inline void extraq_check(struct domain *d) {
+static inline void extraq_check(struct exec_domain *d) {
        if (extraq_on(d, EXTRA_UTIL_Q)) {
-               PRINT(2,"Dom %i is on extraQ\n",d->id);
-               if (!(DOM_INFO(d)->extra & EXTRA_AWARE) &&
-                   !extra_runs(DOM_INFO(d))) {
+               PRINT(2,"Dom %i is on extraQ\n",d->domain->id, d->eid);
+               if (!(EDOM_INFO(d)->extra & EXTRA_AWARE) &&
+                   !extra_runs(EDOM_INFO(d))) {
                        extraq_del(d, EXTRA_UTIL_Q);
-                       PRINT(2,"Removed dom %i from L1 extraQ\n",d->id);
+                       PRINT(2,"Removed dom %i.%i from L1 extraQ\n",
+                             d->domain->id, d->eid);
                }
        } else {
-               PRINT(2,"Dom %i is NOT on L1 extraQ\n",d->id);
-               if ((DOM_INFO(d)->extra & EXTRA_AWARE) && domain_runnable(d))
+               PRINT(2,"Dom %i.%i is NOT on L1 extraQ\n",d->domain->id,
+                     d->eid);
+               if ((EDOM_INFO(d)->extra & EXTRA_AWARE) && domain_runnable(d))
                {
                        #if (EXTRA == EXTRA_ROUNDR)
                        /*Favour domains which got short unblocked*/
@@ -223,15 +227,16 @@
                        #elif
                        ;
                        #endif
-                       PRINT(2,"Added dom %i to L1 extraQ\n",d->id);
+                       PRINT(2,"Added dom %i.%i to L1 extraQ\n",d->domain->id,
+                             d->eid);
                }
        }
 }
-static inline void __del_from_queue(struct domain *d)
+static inline void __del_from_queue(struct exec_domain *d)
 {
     struct list_head *list = LIST(d);
-    PRINT(3,"Removing domain %i (bop= %llu) from runq/waitq\n", d->id,
-          PERIOD_BEGIN(DOM_INFO(d)));
+    PRINT(3,"Removing domain %i.%i (bop= %llu) from runq/waitq\n", 
d->domain->id,
+          d->eid, PERIOD_BEGIN(EDOM_INFO(d)));
     list_del(list);
     list->next = NULL;
 }
@@ -240,26 +245,26 @@
    next period; this list is therefore sortet by this time, which is simply
    absol. deadline - period
  */ 
-static inline void __add_to_waitqueue_sort(struct domain *d) {
+static inline void __add_to_waitqueue_sort(struct exec_domain *d) {
        struct list_head     *cur;
-       struct sedf_dom_info *curinf;
+       struct sedf_edom_info *curinf;
        
-       PRINT(3,"Adding domain %i (bop= %llu) to waitq\n", d->id,
-             PERIOD_BEGIN(DOM_INFO(d)));
+       PRINT(3,"Adding domain %i.%i (bop= %llu) to waitq\n", d->domain->id,
+       d->eid, PERIOD_BEGIN(EDOM_INFO(d)));
              
        /*iterate through all elements to find our "hole"*/
-       list_for_each(cur,WAITQ(d->processor)){
-               curinf = list_entry(cur,struct sedf_dom_info,list);
-               if (PERIOD_BEGIN(DOM_INFO(d)) < PERIOD_BEGIN(curinf))
+       list_for_each(cur, WAITQ(d->processor)){
+               curinf = list_entry(cur,struct sedf_edom_info,list);
+               if (PERIOD_BEGIN(EDOM_INFO(d)) < PERIOD_BEGIN(curinf))
                        break;
                else
-                       PRINT(4,"\tbehind domain %i (bop= %llu)\n",
-                             curinf->owner->id, PERIOD_BEGIN(curinf));
+                       PRINT(4,"\tbehind domain %i.%i (bop= %llu)\n",
+                             curinf->exec_domain->domain->id,
+                             curinf->exec_domain->eid, PERIOD_BEGIN(curinf));
        }
        /*cur now contains the element, before which we'll enqueue*/
        PRINT(3,"\tlist_add to %x\n",cur->prev);
        list_add(LIST(d),cur->prev);
-
 }
 
 /* adds a domain to the queue of processes which have started their current
@@ -267,40 +272,40 @@
    on this list is running on the processor, if the list is empty the idle
    task will run. As we are implementing EDF, this list is sorted by deadlines.
  */ 
-static inline void __add_to_runqueue_sort(struct domain *d) {
+static inline void __add_to_runqueue_sort(struct exec_domain *d) {
        struct list_head     *cur;
-       struct sedf_dom_info *curinf;
+       struct sedf_edom_info *curinf;
 
-       PRINT(3,"Adding domain %i (deadl= %llu) to runq\n", d->id,
-             DOM_INFO(d)->absdead);    

_______________________________________________
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®.