ChangeSet 1.1346.1.3, 2005/05/02 16:49:43+01:00, sd386@xxxxxxxxxxxxxxxxx
Port of the sedf scheduler to unstable tree.
Signed-off: Stephan.Diestelhorst@{cl.cam.ac.uk , inf.tu-dresden.de}
sched_sedf.c | 499 +++++++++++++++++++++++++++++------------------------------
schedule.c | 45 +++++
2 files changed, 292 insertions(+), 252 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:34 -04:00
+++ b/xen/common/sched_sedf.c 2005-05-09 14:07:34 -04:00
@@ -1,4 +1,4 @@
-/****************************************************************************
+/*******************************************************************************
* Simple EDF scheduler for xen
*
* by Stephan Diestelhorst (C) 2004 Cambridge University
@@ -20,8 +20,13 @@
#define PRINT(_f, _a...) \
if ((_f)<=SEDFLEVEL) printk(_a );
-#ifdef DEBUG
+#ifndef NDEBUG
#define SEDF_STATS
+ #define CHECK(_p) if ( !(_p) ) \
+ { printk("Check '%s' failed, line %d, file %s\n", #_p , __LINE__,\
+ __FILE__);}
+#else
+ #define CHECK(_p) ((void)0)
#endif
/*various ways of unblocking domains*/
@@ -48,14 +53,16 @@
#define EXTRA_WANT_PEN_Q (8)
#define EXTRA_PEN_Q (0)
#define EXTRA_UTIL_Q (1)
-
-#define extra_runs(inf) ((inf->extra) & 6)
-#define extra_get_cur_q(inf) (((inf->extra & 6) >> 1)-1)
+#define SEDF_ASLEEP (16)
#define EXTRA_QUANTUM (MICROSECS(500))
#define WEIGHT_PERIOD (MILLISECS(100))
#define WEIGHT_SAFETY (MILLISECS(5))
+#define IMPLY(a, b) (!(a) || (b))
+#define EQ(a, b) ((!!(a)) == (!!(b)))
+
+
struct sedf_dom_info {
struct domain *domain;
};
@@ -75,12 +82,12 @@
s_time_t slice_orig;
s_time_t latency;
- /*extra-time status of domain*/
- short extra;
+ /*status of domain*/
+ int status;
/*weights for "Scheduling for beginners/ lazy/ etc." ;)*/
short weight;
-
- /*Bookkeeping*/
+ short extraweight;
+ /*Bookkeeping*/
s_time_t deadl_abs;
s_time_t sched_start_abs;
s_time_t cputime;
@@ -127,6 +134,11 @@
#define MIN(x,y) (((x)<(y))?(x):(y))
#define DIV_UP(x,y) (((x) + (y) - 1) / y)
+#define extra_runs(inf) ((inf->status) & 6)
+#define extra_get_cur_q(inf) (((inf->status & 6) >> 1)-1)
+#define sedf_runnable(edom) (!(EDOM_INFO(edom)->status & SEDF_ASLEEP))
+
+
static void sedf_dump_cpu_state(int i);
static inline int extraq_on(struct exec_domain *d, int i) {
@@ -137,25 +149,24 @@
static inline void extraq_add_head(struct exec_domain *d, int i)
{
list_add(EXTRALIST(d,i), EXTRAQ(d->processor,i));
+ ASSERT(extraq_on(d, i));
}
static inline void extraq_add_tail(struct exec_domain *d, int i)
{
list_add_tail(EXTRALIST(d,i), EXTRAQ(d->processor,i));
+ ASSERT(extraq_on(d, 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.%i is NOT on L%i extraq "\
- "HALTING\n",d->domain->id, d->eid,i);
- sedf_dump_cpu_state(0);(*((int*)0))++;
- }*/
+ ASSERT(extraq_on(d,i));
PRINT(3, "Removing domain %i.%i from L%i extraq\n", d->domain->id,
d->eid, i);
list_del(list);
list->next = NULL;
+ ASSERT(!extraq_on(d, i));
}
/* adds a domain to the queue of processes which are aware of extra time. List
@@ -168,11 +179,7 @@
struct list_head *cur;
struct sedf_edom_info *curinf;
- /*if (extraq_on(d,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))++;
- }*/
+ ASSERT(!extraq_on(d,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);
@@ -203,11 +210,12 @@
curinf->exec_domain->domain->id,
curinf->exec_domain->eid, curinf->score[i]);
}
+ ASSERT(extraq_on(d,i));
}
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->domain->id, d->eid);
- if (!(EDOM_INFO(d)->extra & EXTRA_AWARE) &&
+ PRINT(2,"Dom %i.%i is on L1 extraQ\n",d->domain->id, d->eid);
+ if (!(EDOM_INFO(d)->status & EXTRA_AWARE) &&
!extra_runs(EDOM_INFO(d))) {
extraq_del(d, EXTRA_UTIL_Q);
PRINT(2,"Removed dom %i.%i from L1 extraQ\n",
@@ -216,10 +224,9 @@
} else {
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 ((EDOM_INFO(d)->status & EXTRA_AWARE) && sedf_runnable(d))
{
#if (EXTRA == EXTRA_ROUNDR)
- /*Favour domains which got short unblocked*/
extraq_add_tail(d, EXTRA_UTIL_Q);
#elif (EXTRA == EXTRA_SLICE_WEIGHT || \
EXTRA == EXTRA_BLOCK_WEIGHT)
@@ -232,39 +239,78 @@
}
}
}
+
+static inline void extraq_check_add_unblocked(struct exec_domain *d,
+ int priority) {
+ struct sedf_edom_info *inf = EDOM_INFO(d);
+ if (inf->status & EXTRA_AWARE)
+ #if (EXTRA == EXTRA_ROUNDR)
+ if (priority)
+ extraq_add_head(d,EXTRA_UTIL_Q);
+ else
+ extraq_add_tail(d,EXTRA_UTIL_Q);
+ #elif (EXTRA == EXTRA_SLICE_WEIGHT \
+ || EXTRA == EXTRA_BLOCK_WEIGHT)
+ /*put in on the weighted extraq,
+ without updating any scores*/
+ extraq_add_sort_update(d, EXTRA_UTIL_Q, 0);
+ #else
+ ;
+ #endif
+}
+
+static inline int __task_on_queue(struct exec_domain *d) {
+ return (((LIST(d))->next != NULL) && (LIST(d)->next != LIST(d)));
+}
static inline void __del_from_queue(struct exec_domain *d)
{
struct list_head *list = LIST(d);
+ ASSERT(__task_on_queue(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;
+ ASSERT(!__task_on_queue(d));
}
-/* adds a domain to the queue of processes which wait for the beginning of the
- next period; this list is therefore sortet by this time, which is simply
- absol. deadline - period
- */
-static inline void __add_to_waitqueue_sort(struct exec_domain *d) {
+typedef int(*list_comparer)(struct list_head* el1, struct list_head* el2);
+
+static inline void list_insert_sort(struct list_head *list,
+ struct list_head *element, list_comparer comp) {
struct list_head *cur;
- struct sedf_edom_info *curinf;
-
- 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_edom_info,list);
- if (PERIOD_BEGIN(EDOM_INFO(d)) < PERIOD_BEGIN(curinf))
+ list_for_each(cur,list){
+ if (comp(element, cur) < 0)
break;
- else
- 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);
+ list_add(element, cur->prev);
+}
+#define DOMAIN_COMPARER(name, field, comp1, comp2) \
+int name##_comp(struct list_head* el1, struct list_head* el2) \
+{ \
+ struct sedf_edom_info *d1, *d2; \
+ d1 = list_entry(el1,struct sedf_edom_info, field); \
+ d2 = list_entry(el2,struct sedf_edom_info, field); \
+ if ((comp1) == (comp2)) \
+ return 0; \
+ if ((comp1) < (comp2)) \
+ return -1; \
+ else \
+ return 1; \
+}
+/* adds a domain to the queue of processes which wait for the beginning of the
+ next period; this list is therefore sortet by this time, which is simply
+ absol. deadline - period
+ */
+DOMAIN_COMPARER(waitq, list, PERIOD_BEGIN(d1), PERIOD_BEGIN(d2))
+static inline void __add_to_waitqueue_sort(struct exec_domain *d) {
+ ASSERT(!__task_on_queue(d));
+ PRINT(3,"Adding domain %i.%i (bop= %llu) to waitq\n", d->domain->id,
+ d->eid, PERIOD_BEGIN(EDOM_INFO(d)));
+ list_insert_sort(WAITQ(d->processor), LIST(d), waitq_comp);
+ ASSERT(__task_on_queue(d));
}
/* adds a domain to the queue of processes which have started their current
@@ -272,30 +318,11 @@
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.
*/
+DOMAIN_COMPARER(runq, list, d1->deadl_abs, d2->deadl_abs)
static inline void __add_to_runqueue_sort(struct exec_domain *d) {
- struct list_head *cur;
- struct sedf_edom_info *curinf;
-
PRINT(3,"Adding domain %i.%i (deadl= %llu) to runq\n", d->domain->id,
_______________________________________________
Xen-changelog mailing list
Xen-changelog@xxxxxxxxxxxxxxxxxxx
http://lists.xensource.com/xen-changelog
|
Home