direct-io.hg

changeset 3573:3dc193a9786a

bitkeeper revision 1.1159.170.102 (41fa2751heRkQ76AYa9Oe-6cOyJuLw)

Enhanced SEDF scheduler
author sd386@font.cl.cam.ac.uk
date Fri Jan 28 11:51:45 2005 +0000 (2005-01-28)
parents f8e1f285e41f
children 3c2ccb0cf6c0
files tools/libxc/xc.h tools/libxc/xc_sedf.c tools/python/xen/lowlevel/xc/xc.c tools/python/xen/xend/XendClient.py tools/python/xen/xend/XendDomain.py tools/python/xen/xend/server/SrvDomain.py tools/python/xen/xm/main.py xen/common/sched_sedf.c xen/include/public/sched_ctl.h
line diff
     1.1 --- a/tools/libxc/xc.h	Mon Jan 17 13:39:09 2005 +0000
     1.2 +++ b/tools/libxc/xc.h	Fri Jan 28 11:51:45 2005 +0000
     1.3 @@ -243,11 +243,11 @@ int xc_rrobin_global_get(int xc_handle, 
     1.4  
     1.5  int xc_sedf_domain_set(int xc_handle,
     1.6                            u32 domid,
     1.7 -                          u64 period, u64 slice);
     1.8 +                          u64 period, u64 slice, u64 latency, u16 extratime, u16 weight);
     1.9  
    1.10  int xc_sedf_domain_get(int xc_handle,
    1.11                            u32 domid,
    1.12 -                          u64* period, u64 *slice);
    1.13 +                          u64* period, u64 *slice, u64 *latency, u16 *extratime, u16* weight);
    1.14  
    1.15  typedef evtchn_status_t xc_evtchn_status_t;
    1.16  
     2.1 --- a/tools/libxc/xc_sedf.c	Mon Jan 17 13:39:09 2005 +0000
     2.2 +++ b/tools/libxc/xc_sedf.c	Fri Jan 28 11:51:45 2005 +0000
     2.3 @@ -11,7 +11,7 @@
     2.4  #include "xc_private.h"
     2.5  
     2.6  int xc_sedf_domain_set(int xc_handle,
     2.7 -                          u32 domid, u64 period, u64 slice)
     2.8 +                          u32 domid, u64 period, u64 slice,u64 latency, u16 extratime,u16 weight)
     2.9  {
    2.10      dom0_op_t op;
    2.11      struct sedf_adjdom *p = &op.u.adjustdom.u.sedf;
    2.12 @@ -21,12 +21,15 @@ int xc_sedf_domain_set(int xc_handle,
    2.13      op.u.adjustdom.sched_id = SCHED_SEDF;
    2.14      op.u.adjustdom.direction = SCHED_INFO_PUT;
    2.15  
    2.16 -    p->period   = period;
    2.17 -    p->slice    = slice;
    2.18 +    p->period    = period;
    2.19 +    p->slice     = slice;
    2.20 +    p->latency   = latency;
    2.21 +    p->extratime = extratime;
    2.22 +    p->weight    = weight;
    2.23      return do_dom0_op(xc_handle, &op);
    2.24  }
    2.25  
    2.26 -int xc_sedf_domain_get(int xc_handle, u32 domid, u64 *period, u64 *slice)
    2.27 +int xc_sedf_domain_get(int xc_handle, u32 domid, u64 *period, u64 *slice, u64* latency, u16* extratime, u16* weight)
    2.28  {
    2.29      dom0_op_t op;
    2.30      int ret;
    2.31 @@ -39,7 +42,10 @@ int xc_sedf_domain_get(int xc_handle, u3
    2.32  
    2.33      ret = do_dom0_op(xc_handle, &op);
    2.34  
    2.35 -    *period   = p->period;
    2.36 -    *slice    = p->slice;
    2.37 +    *period    = p->period;
    2.38 +    *slice     = p->slice;
    2.39 +    *latency   = p->latency;
    2.40 +    *extratime = p->extratime;
    2.41 +    *weight    = p->weight;
    2.42      return ret;
    2.43  }
     3.1 --- a/tools/python/xen/lowlevel/xc/xc.c	Mon Jan 17 13:39:09 2005 +0000
     3.2 +++ b/tools/python/xen/lowlevel/xc/xc.c	Fri Jan 28 11:51:45 2005 +0000
     3.3 @@ -791,15 +791,14 @@ static PyObject *pyxc_sedf_domain_set(Py
     3.4  {
     3.5      XcObject *xc = (XcObject *)self;
     3.6      u32 domid;
     3.7 -    u64 period, slice;
     3.8 -    
     3.9 -    static char *kwd_list[] = { "dom", "period", "slice", NULL };
    3.10 +    u64 period, slice, latency;
    3.11 +    u16 extratime, weight;
    3.12 +    static char *kwd_list[] = { "dom", "period", "slice", "latency", "extratime", "weight",NULL };
    3.13      
    3.14 -    if( !PyArg_ParseTupleAndKeywords(args, kwds, "iLL", kwd_list, &domid,
    3.15 -                                     &period, &slice) )
    3.16 +    if( !PyArg_ParseTupleAndKeywords(args, kwds, "iLLLhh", kwd_list, &domid,
    3.17 +                                     &period, &slice, &latency, &extratime, &weight) )
    3.18          return NULL;
    3.19 -   
    3.20 -    if ( xc_sedf_domain_set(xc->xc_handle, domid, period, slice) != 0 )
    3.21 +   if ( xc_sedf_domain_set(xc->xc_handle, domid, period, slice, latency, extratime,weight) != 0 )
    3.22          return PyErr_SetFromErrno(xc_error);
    3.23  
    3.24      Py_INCREF(zero);
    3.25 @@ -812,21 +811,24 @@ static PyObject *pyxc_sedf_domain_get(Py
    3.26  {
    3.27      XcObject *xc = (XcObject *)self;
    3.28      u32 domid;
    3.29 -    u64 period, slice;
    3.30 -        
    3.31 +    u64 period, slice,latency;
    3.32 +    u16 weight, extratime;
    3.33 +    
    3.34      static char *kwd_list[] = { "dom", NULL };
    3.35  
    3.36      if( !PyArg_ParseTupleAndKeywords(args, kwds, "i", kwd_list, &domid) )
    3.37          return NULL;
    3.38      
    3.39      if ( xc_sedf_domain_get( xc->xc_handle, domid, &period,
    3.40 -                                &slice) )
    3.41 +                                &slice,&latency,&extratime,&weight) )
    3.42          return PyErr_SetFromErrno(xc_error);
    3.43  
    3.44 -    return Py_BuildValue("{s:i,s:L,s:L}",
    3.45 -                         "domain",  domid,
    3.46 -                         "period",  period,
    3.47 -                         "slice",   slice);
    3.48 +    return Py_BuildValue("{s:i,s:L,s:L,s:L,s:i}",
    3.49 +                         "domain",    domid,
    3.50 +                         "period",    period,
    3.51 +                         "slice",     slice,
    3.52 +			 "latency",   latency,
    3.53 +			 "extratime", extratime);
    3.54  }
    3.55  
    3.56  static PyObject *pyxc_shadow_control(PyObject *self,
    3.57 @@ -1068,9 +1070,11 @@ static PyMethodDef pyxc_methods[] = {
    3.58        (PyCFunction)pyxc_sedf_domain_set,
    3.59        METH_KEYWORDS, "\n"
    3.60        "Set the scheduling parameters for a domain when running with Atropos.\n"
    3.61 -      " dom      [int]:  domain to set\n"
    3.62 -      " period   [long]: domain's scheduling period\n"
    3.63 -      " slice    [long]: domain's slice per period\n"
    3.64 +      " dom       [int]:  domain to set\n"
    3.65 +      " period    [long]: domain's scheduling period\n"
    3.66 +      " slice     [long]: domain's slice per period\n"
    3.67 +      " latency   [long]: domain's wakeup latency hint\n"
    3.68 +      " extratime [int]:  domain aware of extratime?\n"
    3.69        "Returns: [int] 0 on success; -1 on error.\n" },
    3.70  
    3.71      { "sedf_domain_get",
    3.72 @@ -1078,11 +1082,13 @@ static PyMethodDef pyxc_methods[] = {
    3.73        METH_KEYWORDS, "\n"
    3.74        "Get the current scheduling parameters for a domain when running with\n"
    3.75        "the Atropos scheduler."
    3.76 -      " dom      [int]: domain to query\n"
    3.77 -      "Returns:  [dict]\n"
    3.78 -      " domain   [int]: domain ID\n"
    3.79 -      " period   [long]: scheduler period\n"
    3.80 -      " slice    [long]: CPU reservation per period\n"},
    3.81 +      " dom       [int]: domain to query\n"
    3.82 +      "Returns:   [dict]\n"
    3.83 +      " domain    [int]: domain ID\n"
    3.84 +      " period    [long]: scheduler period\n"
    3.85 +      " slice     [long]: CPU reservation per period\n"
    3.86 +      " latency   [long]: domain's wakeup latency hint\n"
    3.87 +      " extratime [int]:  domain aware of extratime?\n"},
    3.88  
    3.89      { "evtchn_alloc_unbound", 
    3.90        (PyCFunction)pyxc_evtchn_alloc_unbound,
     4.1 --- a/tools/python/xen/xend/XendClient.py	Mon Jan 17 13:39:09 2005 +0000
     4.2 +++ b/tools/python/xen/xend/XendClient.py	Fri Jan 28 11:51:45 2005 +0000
     4.3 @@ -273,11 +273,14 @@ class Xend:
     4.4                                'latency' : latency,
     4.5                                'xtratime': xtratime })
     4.6  
     4.7 -    def xend_domain_cpu_sedf_set(self, id, period, slice):
     4.8 +    def xend_domain_cpu_sedf_set(self, id, period, slice, latency, extratime, weight):
     4.9          return self.xendPost(self.domainurl(id),
    4.10 -                             {'op'      : 'cpu_sedf_set',
    4.11 -                              'period'  : period,
    4.12 -                              'slice'   : slice })
    4.13 +                             {'op'        : 'cpu_sedf_set',
    4.14 +                              'period'    : period,
    4.15 +                              'slice'     : slice,
    4.16 +			      'latency'   : latency,
    4.17 +			      'extratime' : extratime,
    4.18 +			      'weight'    : weight })
    4.19  
    4.20      def xend_domain_maxmem_set(self, id, memory):
    4.21          return self.xendPost(self.domainurl(id),
     5.1 --- a/tools/python/xen/xend/XendDomain.py	Mon Jan 17 13:39:09 2005 +0000
     5.2 +++ b/tools/python/xen/xend/XendDomain.py	Fri Jan 28 11:51:45 2005 +0000
     5.3 @@ -660,12 +660,12 @@ class XendDomain:
     5.4          except Exception, ex:
     5.5              raise XendError(str(ex))
     5.6      
     5.7 -    def domain_cpu_sedf_set(self, id, period, slice):
     5.8 -        """Set Atropos scheduler parameters for a domain.
     5.9 +    def domain_cpu_sedf_set(self, id, period, slice, latency, extratime, weight):
    5.10 +        """Set Simple EDF scheduler parameters for a domain.
    5.11          """
    5.12 -        dominfo = self.domain_lookup(id)
    5.13 +	dominfo = self.domain_lookup(id)
    5.14          try:
    5.15 -            return xc.sedf_domain_set(dominfo.dom, period, slice)
    5.16 +            return xc.sedf_domain_set(dominfo.dom, period, slice, latency, extratime, weight)
    5.17          except Exception, ex:
    5.18              raise XendError(str(ex))
    5.19  
     6.1 --- a/tools/python/xen/xend/server/SrvDomain.py	Mon Jan 17 13:39:09 2005 +0000
     6.2 +++ b/tools/python/xen/xend/server/SrvDomain.py	Fri Jan 28 11:51:45 2005 +0000
     6.3 @@ -138,7 +138,10 @@ class SrvDomain(SrvDir):
     6.4          fn = FormFn(self.xd.domain_cpu_sedf_set,
     6.5                      [['dom', 'str'],
     6.6                       ['period', 'int'],
     6.7 -                     ['slice', 'int']])
     6.8 +                     ['slice', 'int'],
     6.9 +		     ['latency', 'int'],
    6.10 +		     ['extratime', 'int'],
    6.11 +		     ['weight', 'int']])
    6.12          val = fn(req.args, {'dom': self.dom.id})
    6.13          return val
    6.14  
     7.1 --- a/tools/python/xen/xm/main.py	Mon Jan 17 13:39:09 2005 +0000
     7.2 +++ b/tools/python/xen/xm/main.py	Fri Jan 28 11:51:45 2005 +0000
     7.3 @@ -606,14 +606,14 @@ class ProgSedf(Prog):
     7.4      info = """Set simple EDF parameters."""
     7.5  
     7.6      def help(self, args):
     7.7 -        print args[0], "DOM PERIOD SLICE"
     7.8 +        print args[0], "DOM PERIOD SLICE LATENCY EXTRATIME WEIGHT"
     7.9          print "\nSet simple EDF parameters."
    7.10  
    7.11      def main(self, args):
    7.12 -        if len(args) != 4: self.err("%s: Invalid argument(s)" % args[0])
    7.13 -        dom = args[1]
    7.14 -        v = map(int, args[2:4])
    7.15 -        server.xend_domain_cpu_sedf_set(dom, *v)
    7.16 +	if len(args) != 7: self.err("%s: Invalid argument(s)" % args[0])
    7.17 +	dom = args[1]
    7.18 +	v = map(int, args[2:7])
    7.19 +	server.xend_domain_cpu_sedf_set(dom, *v)
    7.20  
    7.21  xm.prog(ProgSedf)
    7.22  
     8.1 --- a/xen/common/sched_sedf.c	Mon Jan 17 13:39:09 2005 +0000
     8.2 +++ b/xen/common/sched_sedf.c	Fri Jan 28 11:51:45 2005 +0000
     8.3 @@ -13,7 +13,7 @@
     8.4  #include <xen/time.h>
     8.5  #include <xen/slab.h>
     8.6  
     8.7 -#define SEDFLEVEL 0
     8.8 +#define SEDFLEVEL 2
     8.9  #define PRINT(_f, _a...)  \
    8.10  if ((_f)<=SEDFLEVEL) printk(_a );
    8.11  
    8.12 @@ -26,50 +26,104 @@ if ((_f)<=SEDFLEVEL) printk(_a );
    8.13  
    8.14  
    8.15  #define TRC_SEDF 0xBEEF0000
    8.16 +#define EXTRA_NONE (0)
    8.17 +#define EXTRA_AWARE (1)
    8.18 +#define EXTRA_RUNNING (2)
    8.19 +#define EXTRA_QUANTUM (MICROSECS(1000)) 
    8.20 +#define WEIGHT_PERIOD (MILLISECS(100))
    8.21 +#define WEIGHT_SAFETY (MILLISECS(5))
    8.22  
    8.23  struct sedf_dom_info
    8.24  {
    8.25  	struct domain		*owner;
    8.26  	struct list_head	list;
    8.27 +	struct list_head	extralist;
    8.28  	
    8.29  	//Parameters for EDF
    8.30  	s_time_t		period;		//=(relative deadline)
    8.31  	s_time_t		slice;		//=worst case execution time
    8.32 -	int			extratime;
    8.33 +	
    8.34 +	//Advaced Parameters
    8.35 +	//Latency Scaling
    8.36 +	s_time_t		period_orig;	
    8.37 +	s_time_t		slice_orig;
    8.38 +	s_time_t		latency;
    8.39 +	//extra-time status of domain
    8.40 +	short			extra;
    8.41 +	//weights for "Scheduling for Beginners/ Lazy/ etc."
    8.42 +	short			weight;
    8.43 +	
    8.44  	//Bookkeeping
    8.45  	s_time_t		absdead;
    8.46  	s_time_t		sched_start;
    8.47  	s_time_t		cputime;
    8.48  	s_time_t		absblock;
    8.49 +	
    8.50  	//Statistics
    8.51  	s_time_t		block_time_tot;
    8.52  	s_time_t		penalty_time_tot;
    8.53 -	
    8.54 +	s_time_t		extra_time_tot;
    8.55 +	int			block_tot;
    8.56 +	int			short_block_tot;
    8.57 +	int			long_block_tot;
    8.58 +	int			short_cont;
    8.59  };
    8.60  
    8.61  struct sedf_cpu_info {
    8.62  	struct list_head runnableq;
    8.63  	struct list_head waitq;
    8.64 +	struct list_head extraq;
    8.65  };
    8.66  
    8.67 -#define DOM_INFO(d)	((struct sedf_dom_info *)((d)->sched_priv))
    8.68 -#define CPU_INFO(cpu)	((struct sedf_cpu_info *)schedule_data[cpu].sched_priv)
    8.69 -#define LIST(d)		(&DOM_INFO(d)->list)
    8.70 -#define RUNQ(cpu)   	(&CPU_INFO(cpu)->runnableq)
    8.71 -#define WAITQ(cpu)   	(&CPU_INFO(cpu)->waitq)
    8.72 -#define IDLETASK(cpu)	((struct domain *)schedule_data[cpu].idle)
    8.73 +#define DOM_INFO(d)		((struct sedf_dom_info *)((d)->sched_priv))
    8.74 +#define CPU_INFO(cpu)		((struct sedf_cpu_info *)schedule_data[cpu].sched_priv)
    8.75 +#define LIST(d)			(&DOM_INFO(d)->list)
    8.76 +#define EXTRALIST(d)		(&DOM_INFO(d)->extralist)
    8.77 +#define RUNQ(cpu)   		(&CPU_INFO(cpu)->runnableq)
    8.78 +#define WAITQ(cpu)   		(&CPU_INFO(cpu)->waitq)
    8.79 +#define EXTRAQ(cpu)   		(&CPU_INFO(cpu)->extraq)
    8.80 +#define IDLETASK(cpu)		((struct domain *)schedule_data[cpu].idle)
    8.81 +
    8.82 +#define PERIOD_BEGIN(inf)	((inf)->absdead - (inf)->period)
    8.83  
    8.84  static xmem_cache_t *dom_info_cache;
    8.85  
    8.86 -/*static inline void __add_to_runqueue_head(struct domain *d)
    8.87 +static inline void extraq_add_head(struct domain *d)
    8.88  {
    8.89 -    list_add(RUNLIST(d), RUNQUEUE(d->processor));
    8.90 +    list_add(EXTRALIST(d), EXTRAQ(d->processor));
    8.91  }
    8.92  
    8.93 -static inline void __add_to_runqueue_tail(struct domain *d)
    8.94 +static inline void extraq_add_tail(struct domain *d)
    8.95  {
    8.96 -    list_add_tail(RUNLIST(d), RUNQUEUE(d->processor));
    8.97 -}*/
    8.98 +    list_add_tail(EXTRALIST(d), EXTRAQ(d->processor));
    8.99 +}
   8.100 +
   8.101 +static inline void extraq_del(struct domain *d)
   8.102 +{
   8.103 +    struct list_head *list = EXTRALIST(d);
   8.104 +    list_del(list);
   8.105 +    list->next = NULL;
   8.106 +}
   8.107 +
   8.108 +static inline int extraq_on(struct domain *d) {
   8.109 +	return (((EXTRALIST(d))->next != NULL) && (EXTRALIST(d)->next != EXTRALIST(d)));
   8.110 +}
   8.111 +
   8.112 +static inline void extraq_check(struct domain *d) {
   8.113 +	if (extraq_on(d)) {
   8.114 +		PRINT(2,"Dom %i is on extraQ\n",d->id);
   8.115 +		if (DOM_INFO(d)->extra == EXTRA_NONE) {
   8.116 +			extraq_del(d);
   8.117 +			PRINT(2,"Removed dom %i from extraQ\n",d->id);
   8.118 +		}
   8.119 +	} else {
   8.120 +		PRINT(2,"Dom %i is NOT on extraQ\n",d->id);
   8.121 +		if (DOM_INFO(d)->extra != EXTRA_NONE) {
   8.122 +			PRINT(2,"Added dom %i to extraQ\n",d->id);
   8.123 +			extraq_add_tail(d);
   8.124 +		}
   8.125 +	}
   8.126 +}
   8.127  
   8.128  static inline void __del_from_queue(struct domain *d)
   8.129  {
   8.130 @@ -85,14 +139,14 @@ static inline void __add_to_waitqueue_so
   8.131  	struct list_head     *cur;
   8.132  	struct sedf_dom_info *curinf;
   8.133  	
   8.134 -	PRINT(3,"Adding domain %i (bop= %llu) to waitq\n",d->id,DOM_INFO(d)->absdead - DOM_INFO(d)->period);	
   8.135 +	PRINT(3,"Adding domain %i (bop= %llu) to waitq\n",d->id,PERIOD_BEGIN(DOM_INFO(d)));	
   8.136  	//iterate through all elements to find our "hole"
   8.137  	list_for_each(cur,WAITQ(d->processor)){
   8.138  		curinf = list_entry(cur,struct sedf_dom_info,list);
   8.139 -		if ( DOM_INFO(d)->absdead - DOM_INFO(d)->period < curinf->absdead - curinf->period)
   8.140 +		if (PERIOD_BEGIN(DOM_INFO(d)) < PERIOD_BEGIN(curinf))
   8.141  	 		break;
   8.142  		else
   8.143 -			PRINT(4,"\tbehind domain %i (bop= %llu)\n",curinf->owner->id,curinf->absdead - curinf->period);
   8.144 +			PRINT(4,"\tbehind domain %i (bop= %llu)\n",curinf->owner->id,PERIOD_BEGIN(curinf));
   8.145  	}
   8.146  	//cur now contains the element, before which we'll enqueue
   8.147  	PRINT(3,"\tlist_add to %x\n",cur->prev);
   8.148 @@ -136,10 +190,11 @@ static int sedf_init_scheduler() {
   8.149  		schedule_data[i].sched_priv = xmalloc(sizeof(struct sedf_cpu_info));
   8.150  		if ( schedule_data[i].sched_priv == NULL )
   8.151  			return -1;
   8.152 -		INIT_LIST_HEAD(WAITQ(i));
   8.153 +		INIT_LIST_HEAD(WAITQ(i));//used for Latency Scaling
   8.154  		INIT_LIST_HEAD(RUNQ(i));
   8.155 +		INIT_LIST_HEAD(EXTRAQ(i));
   8.156  	}
   8.157 -	
   8.158 +				//we could not find any suitable domain => look for domains that are aware of extratime
   8.159  	dom_info_cache = xmem_cache_create(
   8.160  		"SEDF dom info", sizeof(struct sedf_dom_info), 0, 0, 0, NULL);
   8.161  	if ( dom_info_cache == NULL )
   8.162 @@ -170,17 +225,23 @@ static void sedf_add_task(struct domain 
   8.163  	PRINT(2,"sedf_add_task was called, domain-id %i\n",d->id);
   8.164  	if (d->id==0) {
   8.165  		//set dom0 to something useful to boot the machine
   8.166 -		inf->period = MILLISECS(20);
   8.167 -		inf->slice  = MILLISECS(15);
   8.168 -		inf->absdead= 0;
   8.169 +		inf->period    = MILLISECS(20);
   8.170 +		inf->slice     = MILLISECS(15);
   8.171 +		inf->latency   = 0;
   8.172 +		inf->absdead   = 0;
   8.173 +		inf->extra     = EXTRA_NONE;//EXTRA_AWARE; 
   8.174  	}
   8.175  	else {
   8.176  		//other domains don't get any execution time at all in the beginning!
   8.177 -		inf->period = MILLISECS(20);
   8.178 -		inf->slice  = 0;
   8.179 -		inf->absdead= 0;
   8.180 +		inf->period    = MILLISECS(20);
   8.181 +		inf->slice     = 0;
   8.182 +		inf->absdead   = 0;
   8.183 +		inf->latency   = 0;
   8.184 +		inf->extra     = EXTRA_NONE;//EXTRA_AWARE
   8.185  	}
   8.186 +	inf->period_orig = inf->period; inf->slice_orig = inf->slice;
   8.187  	INIT_LIST_HEAD(&(inf->list));
   8.188 +	INIT_LIST_HEAD(&(inf->extralist));
   8.189  }
   8.190  
   8.191  /* Frees memory used by domain info */
   8.192 @@ -208,48 +269,80 @@ static int sedf_init_idle_task(struct do
   8.193  /* Main scheduling function
   8.194   * Reasons for calling this function are:
   8.195   * -timeslice for the current period used up
   8.196 - * -domain on waitqueue has started it's period*/
   8.197 + * -domain on waitqueue has started it's period
   8.198 + * -and various others ;) in general: determin which domain to run next*/
   8.199  static task_slice_t sedf_do_schedule(s_time_t now)
   8.200  {
   8.201  	struct sedf_dom_info *inf   = DOM_INFO(current);
   8.202  	int                   cpu   = current->processor;
   8.203  	struct list_head     *runq  = RUNQ(cpu);
   8.204  	struct list_head     *waitq = WAITQ(cpu);
   8.205 +	struct list_head     *extraq = EXTRAQ(cpu);
   8.206  	struct list_head     *cur,*tmp;
   8.207  	struct sedf_dom_info *curinf;
   8.208  	task_slice_t          ret;
   8.209 +
   8.210  	
   8.211 -	//first of all update the domains cputime
   8.212 -	inf->cputime += now - inf->sched_start;
   8.213 -	
   8.214 -	//scheduling decisions, which don't involve the running domain
   8.215 +	//idle tasks don't need any of the following stuf
   8.216  	if (is_idle_task(inf->owner))
   8.217  		goto check_waitq;				//idle task doesn't get scheduled on the runq
   8.218 -	if (!((inf->cputime >= inf->slice) || !domain_runnable(inf->owner)))
   8.219 -		goto check_waitq;				//nothing to do with the running task
   8.220  	
   8.221 -	//remove tasks that can't run
   8.222 -	__del_from_queue(inf->owner);
   8.223 +	if (unlikely(inf->extra == EXTRA_RUNNING)) {
   8.224 +		//special treatment of domains running in extra time
   8.225 +		inf->extra = EXTRA_AWARE;
   8.226 +		inf->cputime=0;
   8.227 +		inf->extra_time_tot += now - inf->sched_start;
   8.228  		
   8.229 -	//manage bookkeeping
   8.230 -	if (inf->cputime >= inf->slice) {
   8.231 -		inf->absdead += inf->period;
   8.232 -		inf->cputime -= inf->slice;
   8.233 -		if (inf->cputime<0) inf->cputime = 0;
   8.234 +		extraq_del(current);				//remove extradomain from head of the queue
   8.235 +		if (domain_runnable(inf->owner))
   8.236 +			extraq_add_tail(current);		//and add to the tail if it is runnable => round-robin
   8.237 +		else
   8.238 +			__del_from_queue(inf->owner);		//if domain blocked in extratime remove it from waitq(/runq) as well
   8.239  	}
   8.240 -	if (inf->absdead<now);
   8.241 -		//printk("Domain %i exceeded it't deadline!!!! (now: %llu ddl: %llu)\n",current->id,now,inf->absdead);
   8.242 -	//add a runnable domain to the waitqueue		
   8.243 -	if (domain_runnable(inf->owner))
   8.244 -		__add_to_waitqueue_sort(inf->owner);
   8.245 -	else
   8.246 -		inf->absblock=now;
   8.247 +	else {
   8.248 +		//current domain is running in real time mode
   8.249 +		//update the domains cputime
   8.250 +		inf->cputime += now - inf->sched_start;
   8.251 +		//scheduling decisions, which don't move the running domain to any queues
   8.252 +		if ((inf->cputime < inf->slice) && domain_runnable(inf->owner))
   8.253 +			goto check_waitq;			//there is nothing to do with the running task
   8.254  		
   8.255 +		//remove tasks that can't run
   8.256 +		__del_from_queue(inf->owner);
   8.257 +		
   8.258 +		//manage bookkeeping (i.e. calculate next deadline, memorize overun time of slice) of finished domains
   8.259 +		if (inf->cputime >= inf->slice) {
   8.260 +			inf->cputime -= inf->slice;
   8.261 +			
   8.262 +			if (inf->period < inf->period_orig) {
   8.263 +				//this domain runs in latency scaling mode
   8.264 +				inf->period *= 2;
   8.265 +				inf->slice *= 2;
   8.266 +				if ((inf->period > inf->period_orig) || (inf->slice > inf->slice_orig)) {
   8.267 +					//now switch back to standard timing
   8.268 +					inf->period = inf->period_orig;
   8.269 +					inf->slice = inf->slice_orig;
   8.270 +				}
   8.271 +			}
   8.272 +			inf->absdead += inf->period;		//set next deadline
   8.273 +		}
   8.274 +		//if (inf->absdead<now);
   8.275 +			//printk("Domain %i exceeded it't deadline!!!! (now: %llu ddl: %llu)\n",current->id,now,inf->absdead);
   8.276 +		//add a runnable domain to the waitqueue		
   8.277 +		if (domain_runnable(inf->owner))
   8.278 +			__add_to_waitqueue_sort(inf->owner);
   8.279 +		else {
   8.280 +			//we have a blocked realtime task
   8.281 +			inf->absblock=now;
   8.282 +			if (inf->extra == EXTRA_AWARE)
   8.283 +				extraq_del(inf->owner);		//remove a blocked domain from the extraq aswell
   8.284 +		}
   8.285 +	}
   8.286  check_waitq:
   8.287  	//check for the first elements of the waitqueue, whether their next period has already started
   8.288  	list_for_each_safe(cur,tmp,waitq) {
   8.289  		curinf = list_entry(cur,struct sedf_dom_info,list);
   8.290 -		if (curinf->absdead - curinf->period<=now) {
   8.291 +		if (PERIOD_BEGIN(curinf) <= now) {
   8.292  			__del_from_queue(curinf->owner);
   8.293  			__add_to_runqueue_sort(curinf->owner);
   8.294  		}
   8.295 @@ -266,19 +359,19 @@ check_waitq:
   8.296  			curinf->absdead += curinf->period;
   8.297  			__add_to_waitqueue_sort(curinf->owner);
   8.298  		}
   8.299 -		else
   8.300 +		else {
   8.301  			if (unlikely((curinf->absdead < now) || (curinf->cputime > curinf->slice))) {
   8.302  				//we missed the deadline or the slice was already finished... might hapen because of dom_adj.
   8.303  				//printk("Ouch! Domain %i missed deadline %llu\n",curinf->owner->id,curinf->absdead);
   8.304  				__del_from_queue(curinf->owner);
   8.305 -				curinf->absdead += ((now - curinf->absdead) / curinf->period + 1) * curinf->period;		
   8.306 -					//force start of period to be in future!
   8.307 -				//curinf->absdead += curinf->period;
   8.308 +				curinf->absdead += ((now - curinf->absdead + (curinf->period-1)) / curinf->period) * curinf->period;		
   8.309 +					//force start of period to be in future and aligned to period borders!
   8.310  				curinf->cputime = 0;
   8.311  				__add_to_runqueue_sort(curinf->owner);
   8.312  			}
   8.313  			else
   8.314  				break;
   8.315 +		}
   8.316  	}
   8.317  	
   8.318  	//now simply pick the first domain from the runqueue
   8.319 @@ -290,23 +383,33 @@ check_waitq:
   8.320  		if (!list_empty(waitq)) {
   8.321  			//rerun scheduler, when scheduled domain reaches it's end of slice or the first domain from the waitqueue gets ready
   8.322  			waitinf  = list_entry(waitq->next,struct sedf_dom_info,list);
   8.323 -			ret.time = MIN(now + runinf->slice - runinf->cputime,waitinf->absdead - waitinf->period) - now;
   8.324 +			ret.time = MIN(now + runinf->slice - runinf->cputime,PERIOD_BEGIN(waitinf)) - now;
   8.325  		}
   8.326  		else {
   8.327  			ret.time = runinf->slice - runinf->cputime;
   8.328  		}
   8.329  	}
   8.330  	else {
   8.331 -		//we have an empty runqueue => let the idle domain run and start the scheduler, when the next task becomes available
   8.332 -		ret.task = IDLETASK(cpu);
   8.333  		if (!list_empty(waitq)) {
   8.334 -			waitinf = list_entry(waitq->next,struct sedf_dom_info,list);
   8.335 -			ret.time = (waitinf->absdead - waitinf->period) - now;
   8.336 +			waitinf  = list_entry(waitq->next,struct sedf_dom_info,list);
   8.337 +			//we could not find any suitable domain => look for domains that are aware of extratime
   8.338 +			if (!list_empty(extraq) && (PERIOD_BEGIN(waitinf) - now >= EXTRA_QUANTUM)) {
   8.339 +				runinf   = list_entry(extraq->next,struct sedf_dom_info,extralist);
   8.340 +				runinf->extra = EXTRA_RUNNING;
   8.341 +				ret.task = runinf->owner;
   8.342 +				ret.time = EXTRA_QUANTUM;
   8.343 +			}
   8.344 +			else {
   8.345 +				//we have an empty run- and extraqueue or too less time => idle task!
   8.346 +				ret.task = IDLETASK(cpu);
   8.347 +				ret.time = PERIOD_BEGIN(waitinf) - now;
   8.348 +			}
   8.349  		}
   8.350  		else {
   8.351 -			//this could porbably never happen, but one never knows...
   8.352 +			//this could probably never happen, but one never knows...
   8.353  			//it can... imagine a second CPU, which is pure scifi ATM, but one never knows ;)
   8.354 -			ret.time=SECONDS(1);
   8.355 +			ret.task = IDLETASK(cpu);
   8.356 +			ret.time = SECONDS(1);
   8.357  		}
   8.358  	}
   8.359  	if (ret.time<0)
   8.360 @@ -319,8 +422,12 @@ static void sedf_sleep(struct domain *d)
   8.361  	PRINT(2,"sedf_sleep was called, domain-id %i\n",d->id);
   8.362  	if ( test_bit(DF_RUNNING, &d->flags) )
   8.363  		cpu_raise_softirq(d->processor, SCHEDULE_SOFTIRQ);
   8.364 -	else if ( __task_on_queue(d) )
   8.365 -		__del_from_queue(d);
   8.366 +	else  {
   8.367 +		if ( __task_on_queue(d) )
   8.368 +			__del_from_queue(d);
   8.369 +		if (extraq_on(d))
   8.370 +			extraq_del(d);
   8.371 +	}
   8.372  }
   8.373  
   8.374  /* This function wakes ifup a domain, i.e. moves them into the waitqueue
   8.375 @@ -343,7 +450,7 @@ static void sedf_sleep(struct domain *d)
   8.376   *     -doesn't disturb the schedule at all
   8.377   *     -deadlines keep occuring isochronous
   8.378   *
   8.379 - * 2. Conservative Part 1
   8.380 + * 2. Conservative Part 1: Short Unblocking
   8.381   *     -when a domain unblocks in the same period as it was blocked it unblocks and
   8.382   *      may consume the rest of it's original time-slice minus the time it was blocked
   8.383   *      (assume period=9, slice=5)
   8.384 @@ -352,10 +459,13 @@ static void sedf_sleep(struct domain *d)
   8.385   *
   8.386   *     -this also doesn't disturb scheduling, but might lead to the fact, that the domain
   8.387   *      can't finish it's workload in the period
   8.388 + *     -in addition to that the domain can be treated prioritised when extratime is available
   8.389   *
   8.390 + *    Part2: Long Unblocking
   8.391   *    Part 2a
   8.392   *     -it is obvious that such behaviour, applied when then unblocking is happening in
   8.393 - *      later domains,tinyvnc works fine aswell
   8.394 + *      later periods, works fine aswell
   8.395 + *     -the domain is treated as if it would have been running since the start of its new period
   8.396   *
   8.397   *      DRB______D___UR___D... 
   8.398   *
   8.399 @@ -369,13 +479,62 @@ static void sedf_sleep(struct domain *d)
   8.400   *      DRB______D___URRRR___D...
   8.401   *                       (D) 
   8.402   *     -problem: deadlines don't occur isochronous anymore
   8.403 + *    Part 2c (Improved Atropos design)
   8.404 + *     -when a domain unblocks it is given a very short period (=latency hint) and slice length scaled
   8.405 + *      accordingly
   8.406 + *     -both rise again to the original value (e.g. get doubled every period)
   8.407   *
   8.408   * 3. Unconservative (i.e. incorrect)
   8.409   *     -to boost the performance of I/O dependent domains it would be possible to put the domain into
   8.410   *      the runnable queue immediately, and let it run for the remainder of the slice of the current period
   8.411 - *      (or even worse: allocate a new full slice for the domain) (and probably tweaking the deadline/slice even more)
   8.412 + *      (or even worse: allocate a new full slice for the domain) 
   8.413   *     -either behaviour can lead to missed deadlines in other domains as opposed to approaches 1,2a,2b
   8.414   */
   8.415 +static inline void unblock_short_vcons(struct sedf_dom_info* inf, s_time_t now) { inf->absdead += inf->period;}
   8.416 +static inline void unblock_long_vcons(struct sedf_dom_info* inf, s_time_t now) {
   8.417 +	inf->absdead += ((now - inf->absdead) / inf->period + 1) * inf->period;		//very conservative
   8.418 +	inf->cputime = 0;
   8.419 +}
   8.420 +
   8.421 +static inline void unblock_short_cons(struct sedf_dom_info* inf, s_time_t now) {
   8.422 +	inf->cputime += now - inf->absblock;						//treat blocked time as consumed by the domain
   8.423 +	if (inf->cputime + EXTRA_QUANTUM > inf->slice) {
   8.424 +		//we don't have a reasonable amount of time in our slice left :(
   8.425 +		inf->cputime=0;
   8.426 +		inf->absdead += inf->period;						//start in next period!
   8.427 +	}
   8.428 +	else
   8.429 +		inf->short_cont++;
   8.430 +}
   8.431 +static inline void unblock_long_cons_a(struct sedf_dom_info* inf, s_time_t now) {
   8.432 +	inf->cputime = (now - inf->absdead) % inf->period;				//treat the time the domain was blocked in the CURRENT
   8.433 +											//period as consumed by the domain
   8.434 +	if (inf->cputime + EXTRA_QUANTUM > inf->slice) {
   8.435 +		//we don't have a reasonable amount of time in our slice left :(
   8.436 +		inf->cputime=0;
   8.437 +		inf->absdead += inf->period;						//start in next period!
   8.438 +	}
   8.439 +}
   8.440 +static inline void unblock_long_cons_b(struct sedf_dom_info* inf,s_time_t now) {
   8.441 +	inf->absdead = now + inf->period;						//Conservative 2b
   8.442 +	inf->cputime = 0;
   8.443 +}
   8.444 +static inline void unblock_long_cons_c(struct sedf_dom_info* inf,s_time_t now) {
   8.445 +	if (likely(inf->latency)) {
   8.446 +		//sclae the slice and period accordingly to the latency hint
   8.447 +		inf->period = inf->latency;						//reduce period temporarily to the latency hint
   8.448 +		ASSERT((inf->latency < ULONG_MAX) && (inf->slice_orig < ULONG_MAX));	//this results in max. 4s slice/period length
   8.449 +		inf->slice = (inf->latency * inf->slice_orig) / inf->period_orig;	//scale slice accordingly, so that utilisation stays the same
   8.450 +	}	
   8.451 +	else {
   8.452 +		//we don't have a latency hint.. use some other technique
   8.453 +		inf->absdead = now + inf->period;					//Conservative 2b...
   8.454 +		inf->cputime = 0;
   8.455 +	}
   8.456 +}
   8.457 +
   8.458 +/*static inline void unblock_short_vcons
   8.459 +static inline void unblock_short_vcons*/
   8.460  void sedf_wake(struct domain *d) {
   8.461  	//for the first try just implement the "very conservative" way of waking domains up
   8.462  	s_time_t              now = NOW();
   8.463 @@ -390,29 +549,52 @@ void sedf_wake(struct domain *d) {
   8.464  		PRINT(3,"\tdomain %i is already in some queue\n",d->id);
   8.465  		return;
   8.466  	}
   8.467 -	
   8.468 +	if ( unlikely(extraq_on(d)) ) {
   8.469 +		PRINT(3,"\tdomain %i is already in the extraQ\n",d->id);
   8.470 +	}
   8.471 +	if (unlikely(inf->absdead == 0))
   8.472 +		inf->absdead = now + inf->slice;			//initial setup of the deadline
   8.473 +		
   8.474  	//very conservative way of unblocking
   8.475  	//make sure that the start of the period for this
   8.476  	//domain is happening in the future
   8.477  	PRINT(3,"waking up domain %i (deadl= %llu period= %llu now= %llu)\n",d->id,inf->absdead,inf->period,now);
   8.478 -	inf->absdead += ((now - inf->absdead) / inf->period+1)*inf->period;
   8.479 +	
   8.480 +	inf->block_tot++;
   8.481 +	if (unlikely(now< PERIOD_BEGIN(inf))) {
   8.482 +		//this might happen, imagine unblocking in extra-time!
   8.483 +		if (likely(inf->extra == EXTRA_AWARE)) 
   8.484 +			extraq_add_tail(d);				//SD: Could extraq_add_head be better?
   8.485 +		//else
   8.486 +		//This is very very unlikely, ie. might even be an error?!
   8.487 +	}		
   8.488 +	else {		
   8.489 +		if (now < inf->absdead) {
   8.490 +			//short blocking
   8.491 +			inf->short_block_tot++;
   8.492 +			//unblock_short_vcons(inf, now);
   8.493 +			unblock_short_cons(inf, now);
   8.494 +			if (inf->extra == EXTRA_AWARE) 
   8.495 +				extraq_add_head(d);
   8.496 +		}
   8.497 +		else {
   8.498 +			//long blocking
   8.499 +			inf->long_block_tot++;
   8.500 +			//PRINT(3,"old=%llu ",inf->absdead);
   8.501 +			//unblock_long_vcons(inf, now);
   8.502 +			unblock_long_cons_c(inf,now);
   8.503 +			if (inf->extra == EXTRA_AWARE) 
   8.504 +				extraq_add_tail(d);
   8.505 +		}
   8.506 +	}
   8.507  	PRINT(3,"waking up domain %i (deadl= %llu period= %llu now= %llu)\n",d->id,inf->absdead,inf->period,now);
   8.508 -	
   8.509  	__add_to_waitqueue_sort(d);
   8.510  	PRINT(3,"added to waitq\n");	
   8.511  	
   8.512 -	//TODO: Implement more fancy unblocking schemes!
   8.513 -	/*if (now < inf->absdead) {
   8.514 -		//short blocking
   8.515 -	}
   8.516 -	else {
   8.517 -		//long blocking 
   8.518 -	}*/
   8.519 -	
   8.520  	//do some statistics here...
   8.521  	if (inf->absblock!=0) {
   8.522  		inf->block_time_tot += now - inf->absblock;
   8.523 -		inf->penalty_time_tot += (inf->absdead - inf-> period) - inf->absblock;
   8.524 +		inf->penalty_time_tot += PERIOD_BEGIN(inf) + inf->cputime - inf->absblock;
   8.525  		/*if (DOM_INFO(d)->block_time_tot)
   8.526  			PRINT(3,"penalty: %lu\n",(DOM_INFO(d)->penalty_time_tot*100)/DOM_INFO(d)->block_time_tot);*/
   8.527  	}
   8.528 @@ -422,7 +604,10 @@ void sedf_wake(struct domain *d) {
   8.529  	}*/
   8.530  	
   8.531  	//check whether the awakened task needs to get scheduled before the next sched. decision
   8.532 -	if  (inf->absdead - inf->period < schedule_data[d->processor].s_timer.expires)
   8.533 +	//and check, whether we are idling and this domain is extratime aware
   8.534 +	if ((PERIOD_BEGIN(inf) < schedule_data[d->processor].s_timer.expires) ||
   8.535 +	    (is_idle_task(schedule_data[d->processor].curr) && (now + EXTRA_QUANTUM < schedule_data[d->processor].s_timer.expires) &&
   8.536 +	     (inf->extra == EXTRA_AWARE)))
   8.537  		cpu_raise_softirq(d->processor, SCHEDULE_SOFTIRQ);
   8.538  }
   8.539  
   8.540 @@ -431,57 +616,140 @@ void sedf_wake(struct domain *d) {
   8.541  static void sedf_dump_domain(struct domain *d) {
   8.542  	printk("%u has=%c ", d->id,
   8.543  		test_bit(DF_RUNNING, &d->flags) ? 'T':'F');
   8.544 -	printk("c=%llu p=%llu sl=%llu ddl=%llu", d->cpu_time,DOM_INFO(d)->period,DOM_INFO(d)->slice,DOM_INFO(d)->absdead);
   8.545 +	printk("p=%llu sl=%llu ddl=%llu w=%u c=%llu xtr(%s)=%llu",
   8.546 +	 	DOM_INFO(d)->period, DOM_INFO(d)->slice, DOM_INFO(d)->absdead, DOM_INFO(d)->weight, d->cpu_time,
   8.547 +		DOM_INFO(d)->extra ? "yes" : "no", DOM_INFO(d)->extra_time_tot);
   8.548 +	if (d->cpu_time !=0)
   8.549 +		printf(" (%lu%)", (DOM_INFO(d)->extra_time_tot * 100) / d->cpu_time);
   8.550  	if (DOM_INFO(d)->block_time_tot!=0)
   8.551 -		printf(" penalty: %lu",(DOM_INFO(d)->penalty_time_tot*100)/DOM_INFO(d)->block_time_tot);
   8.552 +		printf(" pen=%lu%", (DOM_INFO(d)->penalty_time_tot * 100) / DOM_INFO(d)->block_time_tot);
   8.553 +	if (DOM_INFO(d)->block_tot!=0)
   8.554 +		printf("\n   blks=%lu sh=%lu (%lu%) (shc=%lu (%lu%)) l=%lu (%lu%) avg: b=%llu p=%llu", DOM_INFO(d)->block_tot,
   8.555 +		       DOM_INFO(d)->short_block_tot, (DOM_INFO(d)->short_block_tot * 100) / DOM_INFO(d)->block_tot,
   8.556 +		       DOM_INFO(d)->short_cont, (DOM_INFO(d)->short_cont * 100) / DOM_INFO(d)->block_tot,
   8.557 +		       DOM_INFO(d)->long_block_tot, (DOM_INFO(d)->long_block_tot * 100) / DOM_INFO(d)->block_tot,
   8.558 +		       (DOM_INFO(d)->block_time_tot) / DOM_INFO(d)->block_tot,
   8.559 +		       (DOM_INFO(d)->penalty_time_tot) / DOM_INFO(d)->block_tot);
   8.560  	printf("\n");
   8.561  }
   8.562  
   8.563  static void sedf_dump_cpu_state(int i)
   8.564  {
   8.565 -    struct list_head *list, *queue;
   8.566 -    int loop = 0;
   8.567 -    struct sedf_dom_info *d_inf;
   8.568 -
   8.569 -    printk("now=%llu\n",NOW());
   8.570 -    queue = RUNQ(i);
   8.571 -    printk("RUNQ rq %lx   n: %lx, p: %lx\n",  (unsigned long)queue,
   8.572 -        (unsigned long) queue->next, (unsigned long) queue->prev);
   8.573 -    list_for_each ( list, queue )
   8.574 -    {
   8.575 -        printk("%3d: ",loop++);
   8.576 -        d_inf = list_entry(list, struct sedf_dom_info, list);
   8.577 -        sedf_dump_domain(d_inf->owner);
   8.578 -    }
   8.579 -    
   8.580 -    queue = WAITQ(i);
   8.581 -    printk("\nWAITQ rq %lx   n: %lx, p: %lx\n",  (unsigned long)queue,
   8.582 -        (unsigned long) queue->next, (unsigned long) queue->prev);
   8.583 -    list_for_each ( list, queue )
   8.584 -    {
   8.585 -        printk("%3d: ",loop++);
   8.586 -        d_inf = list_entry(list, struct sedf_dom_info, list);
   8.587 -        sedf_dump_domain(d_inf->owner);
   8.588 -    }
   8.589 -
   8.590 +	struct list_head *list, *queue, *tmp;
   8.591 +	int loop = 0;
   8.592 +/*	int found = 0;
   8.593 +	int id1st = 0;*/
   8.594 +	struct sedf_dom_info *d_inf;
   8.595 +	struct domain* d;
   8.596 +	
   8.597 +	printk("now=%llu\n",NOW());
   8.598 +	queue = RUNQ(i);
   8.599 +	printk("RUNQ rq %lx   n: %lx, p: %lx\n",  (unsigned long)queue,
   8.600 +		(unsigned long) queue->next, (unsigned long) queue->prev);
   8.601 +	list_for_each_safe ( list, tmp, queue )
   8.602 +	{
   8.603 +		printk("%3d: ",loop++);
   8.604 +		d_inf = list_entry(list, struct sedf_dom_info, list);
   8.605 +		sedf_dump_domain(d_inf->owner);
   8.606 +	}
   8.607 +	
   8.608 +	queue = WAITQ(i); loop = 0;
   8.609 +	printk("\nWAITQ rq %lx   n: %lx, p: %lx\n",  (unsigned long)queue,
   8.610 +		(unsigned long) queue->next, (unsigned long) queue->prev);
   8.611 +	list_for_each_safe ( list, tmp, queue )
   8.612 +	{
   8.613 +		printk("%3d: ",loop++);
   8.614 +		d_inf = list_entry(list, struct sedf_dom_info, list);
   8.615 +		sedf_dump_domain(d_inf->owner);
   8.616 +	}
   8.617 +	
   8.618 +	queue = EXTRAQ(i); loop = 0;
   8.619 +	printk("\nEXTRAQ rq %lx   n: %lx, p: %lx\n",  (unsigned long)queue,
   8.620 +		(unsigned long) queue->next, (unsigned long) queue->prev);
   8.621 +	list_for_each_safe ( list, tmp, queue )
   8.622 +	{
   8.623 +		d_inf = list_entry(list, struct sedf_dom_info, extralist);
   8.624 +		
   8.625 +/*		if (found) {
   8.626 +			if (id1st == d_inf->owner->id)
   8.627 +				break; 
   8.628 +		} 
   8.629 +		else { id1st=d_inf->owner->id; found=1;}*/
   8.630 +		printk("%3d: ",loop++);
   8.631 +		sedf_dump_domain(d_inf->owner);
   8.632 +	}
   8.633 +	
   8.634 +	loop = 0;
   8.635 +	printk("\nnot on Q\n");
   8.636 +	for_each_domain(d) {
   8.637 +		if (!extraq_on(d) && !__task_on_queue(d)) {
   8.638 +			printk("%3d: ",loop++);
   8.639 +			sedf_dump_domain(d);
   8.640 +		}
   8.641 +	}
   8.642 +}
   8.643 +//Adjusts periods and slices of the domains accordingly to their weights
   8.644 +static inline int sedf_adjust_weights(struct domain *p, struct sched_adjdom_cmd *cmd) {
   8.645 +	int sumw      = 0;
   8.646 +	s_time_t sumt = 0;
   8.647 +	
   8.648 +	//sum up all weights
   8.649 +	for_each_domain(p) {
   8.650 +		if (DOM_INFO(p)->weight)
   8.651 +			sumw += DOM_INFO(p)->weight;
   8.652 +		else {
   8.653 +			//don't modify domains who don't have a weight, but sum up
   8.654 +			//the time they need, projected to a WEIGHT_PERIOD, so that
   8.655 +			//this time is not given to the weight-driven domains
   8.656 +			ASSERT((WEIGHT_PERIOD < ULONG_MAX) && (DOM_INFO(p)->slice_orig < ULONG_MAX));	//this results in max. 4s slice/period length
   8.657 +			sumt += (WEIGHT_PERIOD * DOM_INFO(p)->slice_orig) / DOM_INFO(p)->period_orig;
   8.658 +		}
   8.659 +	}
   8.660 +	//adjust all slices (and periods) to the new weight
   8.661 +	for_each_domain(p) {
   8.662 +		if (DOM_INFO(p)->weight) {
   8.663 +			DOM_INFO(p)->period_orig = 
   8.664 +			     DOM_INFO(p)->period = WEIGHT_PERIOD;
   8.665 +			DOM_INFO(p)->slice_orig  =
   8.666 +			      DOM_INFO(p)->slice = (DOM_INFO(p)->weight * (WEIGHT_PERIOD - WEIGHT_SAFETY - sumt)) / sumw;
   8.667 +		}
   8.668 +	}
   8.669 +	return 0;
   8.670  }
   8.671  
   8.672  /* set or fetch domain scheduling parameters */
   8.673  static int sedf_adjdom(struct domain *p, struct sched_adjdom_cmd *cmd) {
   8.674 -	PRINT(2,"sedf_adjdom was called, domain-id %i new period %llu new slice %llu\n",p->id,cmd->u.sedf.period,cmd->u.sedf.slice);
   8.675 +	PRINT(2,"sedf_adjdom was called, domain-id %i new period %llu new slice %llu\n"
   8.676 +	        "latency %llu extra: %s\n",p->id,cmd->u.sedf.period,cmd->u.sedf.slice,cmd->u.sedf.latency,(cmd->u.sedf.extratime)?"yes":"no");
   8.677  	if ( cmd->direction == SCHED_INFO_PUT )
   8.678  	{
   8.679 -		/* sanity checking! */
   8.680 -		if(cmd->u.sedf.slice > cmd->u.sedf.period )
   8.681 -		return -EINVAL;
   8.682 -		
   8.683 -		DOM_INFO(p)->period   = cmd->u.sedf.period;
   8.684 -		DOM_INFO(p)->slice    = cmd->u.sedf.slice;
   8.685 +		if (!cmd->u.sedf.period && !cmd->u.sedf.weight)			//check for sane parameters
   8.686 +			return -EINVAL;
   8.687 +		if (cmd->u.sedf.weight) {
   8.688 +			DOM_INFO(p)->weight = cmd->u.sedf.weight;		//weight driven domains
   8.689 +		}
   8.690 +		else {
   8.691 +			//time driven domains
   8.692 +			if(cmd->u.sedf.slice > cmd->u.sedf.period )		/* sanity checking! */
   8.693 +				return -EINVAL;
   8.694 +			DOM_INFO(p)->period_orig = 
   8.695 +			   DOM_INFO(p)->period   = cmd->u.sedf.period;
   8.696 +			DOM_INFO(p)->slice_orig  = 
   8.697 +			   DOM_INFO(p)->slice    = cmd->u.sedf.slice;
   8.698 +		}
   8.699 +		if (sedf_adjust_weights(p,cmd))
   8.700 +			return -EINVAL;
   8.701 +		DOM_INFO(p)->extra       = cmd->u.sedf.extratime;
   8.702 +		DOM_INFO(p)->latency     = cmd->u.sedf.latency;
   8.703 +		extraq_check(p);
   8.704  	}
   8.705  	else if ( cmd->direction == SCHED_INFO_GET )
   8.706  	{
   8.707 -		cmd->u.sedf.period   = DOM_INFO(p)->period;
   8.708 -		cmd->u.sedf.slice    = DOM_INFO(p)->slice;
   8.709 +		cmd->u.sedf.period    = DOM_INFO(p)->period;
   8.710 +		cmd->u.sedf.slice     = DOM_INFO(p)->slice;
   8.711 +		cmd->u.sedf.extratime = DOM_INFO(p)->extra;
   8.712 +		cmd->u.sedf.latency   = DOM_INFO(p)->latency;
   8.713 +		cmd->u.sedf.weight    = DOM_INFO(p)->weight;
   8.714  	}
   8.715  	PRINT(2,"sedf_adjdom_finished\n");
   8.716  	return 0;
     9.1 --- a/xen/include/public/sched_ctl.h	Mon Jan 17 13:39:09 2005 +0000
     9.2 +++ b/xen/include/public/sched_ctl.h	Fri Jan 28 11:51:45 2005 +0000
     9.3 @@ -70,8 +70,9 @@ struct sched_adjdom_cmd
     9.4          {
     9.5              u64 period;     /* 16 */
     9.6              u64 slice;      /* 24 */
     9.7 -            u64 dummy1;     /* 32 */
     9.8 -            u32 dummy2;     /* 36 */
     9.9 +            u64 latency;    /* 32 */
    9.10 +            u16 extratime;  /* 36 */
    9.11 +	    u16 weight;     /* 38 */
    9.12          } PACKED sedf;
    9.13  
    9.14      } PACKED u;