ChangeSet 1.1159.170.105, 2005/03/09 14:35:02+00:00, sd386@xxxxxxxxxxxxxxxxx
Implemented twol level extra-time scheduling and added an advanced
scheduling history
common/sched_sedf.c | 688 ++++++++++++++++++++++++++++---------------
include/xen/adv_sched_hist.h | 40 ++
2 files changed, 497 insertions(+), 231 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:21 -04:00
+++ b/xen/common/sched_sedf.c 2005-05-09 14:04:21 -04:00
@@ -5,6 +5,14 @@
* based on code by Mark Williamson (C) 2004 Intel Research Cambridge
*/
+/*
+ TODO:
+ TESTING!
+ tracing instead of PRINTs
+*/
+
+
+
#include <xen/sched.h>
#include <xen/sched-if.h>
#include <public/sched_ctl.h>
@@ -25,8 +33,8 @@
#define UNBLOCK_ATROPOS 3
#define UNBLOCK_SHORT_RESUME 4
#define UNBLOCK_BURST 5
-
-#define UNBLOCK UNBLOCK_BURST
+#define UNBLOCK_EXTRA_SUPPORT 6
+#define UNBLOCK UNBLOCK_EXTRA_SUPPORT
//various ways of treating extra-time
#define EXTRA_OFF 1
@@ -34,20 +42,19 @@
#define EXTRA_SLICE_WEIGHT 3
#define EXTRA_BLOCK_WEIGHT 4
-#define EXTRA EXTRA_OFF
+#define EXTRA EXTRA_BLOCK_WEIGHT
-
-/*
- TODO:
- TESTING!
- tracing instead of PRINTs
-*/
-
-
-#define TRC_SEDF 0xBEEF0000
#define EXTRA_NONE (0)
#define EXTRA_AWARE (1)
-#define EXTRA_RUNNING (2)
+#define EXTRA_RUN_PEN (2)
+#define EXTRA_RUN_UTIL (4)
+#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 EXTRA_QUANTUM (MICROSECS(500))
#define WEIGHT_PERIOD (MILLISECS(100))
#define WEIGHT_SAFETY (MILLISECS(5))
@@ -70,7 +77,7 @@
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
@@ -90,46 +97,58 @@
int short_block_tot;
int long_block_tot;
int short_cont;
+ int pen_extra_blocks;
+ int pen_extra_slices;
};
struct sedf_cpu_info {
struct list_head runnableq;
struct list_head waitq;
- struct list_head extraq;
+ struct list_head extraq[2];
};
#define DOM_INFO(d) ((struct sedf_dom_info *)((d)->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) (&DOM_INFO(d)->extralist)
+#define EXTRALIST(d,i) (&(DOM_INFO(d)->extralist[i]))
#define RUNQ(cpu) (&CPU_INFO(cpu)->runnableq)
#define WAITQ(cpu) (&CPU_INFO(cpu)->waitq)
-#define EXTRAQ(cpu) (&CPU_INFO(cpu)->extraq)
+#define EXTRAQ(cpu,i) (&(CPU_INFO(cpu)->extraq[i]))
#define IDLETASK(cpu) ((struct domain *)schedule_data[cpu].idle)
#define PERIOD_BEGIN(inf) ((inf)->absdead - (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 inline void extraq_add_head(struct domain *d)
-{
- list_add(EXTRALIST(d), EXTRAQ(d->processor));
+static void sedf_dump_cpu_state(int i);
+
+static inline int extraq_on(struct domain *d, int i) {
+ return ((EXTRALIST(d,i)->next != NULL) && (EXTRALIST(d,i)->next !=
EXTRALIST(d,i)));
}
-static inline void extraq_add_tail(struct domain *d)
+static inline void extraq_add_head(struct domain *d, int i)
{
- list_add_tail(EXTRALIST(d), EXTRAQ(d->processor));
+ list_add(EXTRALIST(d,i), EXTRAQ(d->processor,i));
}
-static inline void extraq_del(struct domain *d)
+static inline void extraq_add_tail(struct domain *d, int i)
{
- struct list_head *list = EXTRALIST(d);
- list_del(list);
- list->next = NULL;
+ list_add_tail(EXTRALIST(d,i), EXTRAQ(d->processor,i));
}
-static inline int extraq_on(struct domain *d) {
- return (((EXTRALIST(d))->next != NULL) && (EXTRALIST(d)->next !=
EXTRALIST(d)));
+static inline void extraq_del(struct 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);
+ sedf_dump_cpu_state(0);(*((int*)0))++;
+ }*/
+ PRINT(3, "Removing domain %i from L%i extraq\n", d->id,i);
+ list_del(list);
+ list->next = NULL;
}
/* adds a domain to the queue of processes which are aware of extra time. List
is sorted by score,
@@ -137,50 +156,57 @@
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)
{
+static inline void extraq_add_sort_update(struct domain *d, int i, int 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);
+ /*if (extraq_on(d,i)) {
+ PRINT(0,"extraq_add_sort_update: domain %i is already on L%i
extraq! HALTING\n",d->id,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);
//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)
+ list_for_each(cur,EXTRAQ(d->processor,i)){
+ curinf = list_entry(cur,struct
sedf_dom_info,extralist[i]);
+ curinf->score[i] -= sub;
+ if (DOM_INFO(d)->score[i] < curinf->score[i])
break;
else
- PRINT(4,"\tbehind domain %i (score=
%llu)\n",curinf->owner->id,curinf->score);
+ PRINT(4,"\tbehind domain %i (score= %i)\n",
curinf->owner->id, curinf->score[i]);
}
- //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);
+ //cur now contains the element, before which we'll enq ueue
+ PRINT(3, "\tlist_add to %x\n", cur->prev);
+ list_add(EXTRALIST(d,i),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);
+ 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,extralist[i]);
+ curinf->score[i] -= sub;
+ PRINT(4, "\tupdating domain %i (score= %llu)\n",
curinf->owner->id, curinf->score[i]);
}
}
static inline void extraq_check(struct domain *d) {
- if (extraq_on(d)) {
+ if (extraq_on(d, EXTRA_UTIL_Q)) {
PRINT(2,"Dom %i is on extraQ\n",d->id);
- if (DOM_INFO(d)->extra == EXTRA_NONE) {
- extraq_del(d);
- PRINT(2,"Removed dom %i from extraQ\n",d->id);
+ if (!(DOM_INFO(d)->extra & EXTRA_AWARE)) {
+ extraq_del(d, EXTRA_UTIL_Q);
+ PRINT(2,"Removed dom %i from L1 extraQ\n",d->id);
}
} else {
- 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_sort_update(d, 0);
+ PRINT(2,"Dom %i is NOT on L1 extraQ\n",d->id);
+ if ((DOM_INFO(d)->extra & EXTRA_AWARE) && domain_runnable(d)) {
+ extraq_add_sort_update(d, EXTRA_UTIL_Q, 0);
+ PRINT(2,"Added dom %i to L1 extraQ\n",d->id);
+ //TODO: add extraq_add_tail
}
}
}
static inline void __del_from_queue(struct 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)));
list_del(list);
list->next = NULL;
}
@@ -192,7 +218,7 @@
struct list_head *cur;
struct sedf_dom_info *curinf;
- PRINT(3,"Adding domain %i (bop= %llu) to
waitq\n",d->id,PERIOD_BEGIN(DOM_INFO(d)));
+ PRINT(3,"Adding domain %i (bop= %llu) to
waitq\n",d->id,PERIOD_BEGIN(DOM_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);
@@ -243,13 +269,12 @@
schedule_data[i].sched_priv = xmalloc(sizeof(struct
sedf_cpu_info));
if ( schedule_data[i].sched_priv == NULL )
return -1;
- INIT_LIST_HEAD(WAITQ(i));//used for Latency Scaling
+ INIT_LIST_HEAD(WAITQ(i));
INIT_LIST_HEAD(RUNQ(i));
- INIT_LIST_HEAD(EXTRAQ(i));
+ INIT_LIST_HEAD(EXTRAQ(i,EXTRA_PEN_Q));
+ INIT_LIST_HEAD(EXTRAQ(i,EXTRA_UTIL_Q));
}
- //we could not find any suitable domain => look
for domains that are aware of extratime
- dom_info_cache = xmem_cache_create(
- "SEDF dom info", sizeof(struct sedf_dom_info), 0, 0, 0, NULL);
+ dom_info_cache = xmem_cache_create("SEDF dom info", sizeof(struct
sedf_dom_info), 0, 0, 0, NULL);
if ( dom_info_cache == NULL )
{
printk("Could not allocate SLAB cache.\n");
_______________________________________________
Xen-changelog mailing list
Xen-changelog@xxxxxxxxxxxxxxxxxxx
http://lists.xensource.com/xen-changelog
|
Home