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
|
Home