ChangeSet 1.1159.170.104, 2005/02/17 18:50:24+00:00, sd386@xxxxxxxxxxxxxxxxx
Extended sedf scheduler (weighted extraqueues), added enhanced
scheduling histogramm
common/sched_sedf.c | 258 +++++++++++++++++++++++++++++++++++++++----------
common/schedule.c | 92 ++++++++++++++++-
include/xen/sched-if.h | 11 +-
3 files changed, 302 insertions(+), 59 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:09 -04:00
+++ b/xen/common/sched_sedf.c 2005-05-09 14:04:09 -04:00
@@ -13,14 +13,33 @@
#include <xen/time.h>
#include <xen/slab.h>
+//#include <xen/adv_sched_hist.h>
+
#define SEDFLEVEL 2
#define PRINT(_f, _a...) \
if ((_f)<=SEDFLEVEL) printk(_a );
+//various ways of unblocking domains
+#define UNBLOCK_ISOCHRONOUS_EDF 1
+#define UNBLOCK_EDF 2
+#define UNBLOCK_ATROPOS 3
+#define UNBLOCK_SHORT_RESUME 4
+#define UNBLOCK_BURST 5
+
+#define UNBLOCK UNBLOCK_BURST
+
+//various ways of treating extra-time
+#define EXTRA_OFF 1
+#define EXTRA_ROUNDR 2
+#define EXTRA_SLICE_WEIGHT 3
+#define EXTRA_BLOCK_WEIGHT 4
+
+#define EXTRA EXTRA_OFF
+
+
/*
TODO:
TESTING!
- implement stylish features!
tracing instead of PRINTs
*/
@@ -29,15 +48,16 @@
#define EXTRA_NONE (0)
#define EXTRA_AWARE (1)
#define EXTRA_RUNNING (2)
-#define EXTRA_QUANTUM (MICROSECS(1000))
+#define EXTRA_QUANTUM (MICROSECS(500))
#define WEIGHT_PERIOD (MILLISECS(100))
#define WEIGHT_SAFETY (MILLISECS(5))
+
struct sedf_dom_info
{
struct domain *owner;
struct list_head list;
- struct list_head extralist;
+ struct list_head extralist[2];
//Parameters for EDF
s_time_t period; //=(relative deadline)
@@ -50,14 +70,17 @@
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
s_time_t absdead;
s_time_t sched_start;
s_time_t cputime;
- s_time_t absblock;
+ s_time_t absblock;
+ s_time_t absunblock; //time the domain unblocked,
used by burst mode to determine unblocking intervals
+ int score[2]; //scores for {util, block
penalty}-weighted extratime distribution
+ s_time_t short_block_lost_tot;
//Statistics
s_time_t block_time_tot;
@@ -109,6 +132,37 @@
return (((EXTRALIST(d))->next != NULL) && (EXTRALIST(d)->next !=
EXTRALIST(d)));
}
+/* adds a domain to the queue of processes which are aware of extra time. List
is sorted by score,
+ where a lower score means higher priority for an extra slice. It also
updates the score, by simply subtracting
+ 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)
{
+ 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);
+ //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)
+ break;
+ else
+ PRINT(4,"\tbehind domain %i (score=
%llu)\n",curinf->owner->id,curinf->score);
+ }
+ //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);
+
+ //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);
+ }
+}
static inline void extraq_check(struct domain *d) {
if (extraq_on(d)) {
PRINT(2,"Dom %i is on extraQ\n",d->id);
@@ -120,11 +174,10 @@
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_tail(d);
+ extraq_add_sort_update(d, 0);
}
}
}
-
static inline void __del_from_queue(struct domain *d)
{
struct list_head *list = LIST(d);
@@ -277,29 +330,45 @@
int cpu = current->processor;
struct list_head *runq = RUNQ(cpu);
struct list_head *waitq = WAITQ(cpu);
+ #if (EXTRA > EXTRA_OFF)
struct list_head *extraq = EXTRAQ(cpu);
+ #endif
struct list_head *cur,*tmp;
struct sedf_dom_info *curinf;
task_slice_t ret;
-
+ #if (EXTRA == EXTRA_SLICE_WEIGHT)
+ unsigned long oldscore;
+ #endif
//idle tasks don't need any of the following stuf
if (is_idle_task(inf->owner))
goto check_waitq; //idle task
doesn't get scheduled on the runq
-
+
+ #if (EXTRA > EXTRA_OFF)
if (unlikely(inf->extra == EXTRA_RUNNING)) {
//special treatment of domains running in extra time
inf->extra = EXTRA_AWARE;
inf->cputime=0;
inf->extra_time_tot += now - inf->sched_start;
- extraq_del(current); //remove
extradomain from head of the queue
- if (domain_runnable(inf->owner))
- extraq_add_tail(current); //and add to
the tail if it is runnable => round-robin
+ extraq_del(current);
//remove extradomain from head of the queue
+
+ #if (EXTRA == EXTRA_ROUNDR)
+ if (domain_runnable(current))
+ extraq_add_tail(current); //and
add to the tail if it is runnable => round-robin
+ #elif (EXTRA == EXTRA_SLICE_WEIGHT)
+ oldscore = inf->score;
//update the score
+ inf->score = (inf->period << 10) / inf->slice; //use
fixed point arithmetic with 10 bits
+
+ if (domain_runnable(current))
+ extraq_add_sort_update(current, oldscore); //add
according to score: weighted round robin
+ #endif
else
- __del_from_queue(inf->owner); //if domain
blocked in extratime remove it from waitq(/runq) as well
+ __del_from_queue(inf->owner); //if
domain blocked in extratime remove it from waitq(/runq) as well
}
- else {
+ else
+ #endif
+ {
//current domain is running in real time mode
//update the domains cputime
inf->cputime += now - inf->sched_start;
@@ -315,13 +384,18 @@
inf->cputime -= inf->slice;
if (inf->period < inf->period_orig) {
- //this domain runs in latency scaling mode
- inf->period *= 2;
- inf->slice *= 2;
- if ((inf->period > inf->period_orig) ||
(inf->slice > inf->slice_orig)) {
- //now switch back to standard timing
- inf->period = inf->period_orig;
- inf->slice = inf->slice_orig;
+ //this domain runs in latency scaling or burst
mode
+ #if (UNBLOCK == UNBLOCK_BURST)
+ if (now - inf->absunblock >= 2 * inf->period)
+ #endif
+ {
+ inf->period *= 2;
+ inf->slice *= 2;
+ if ((inf->period > inf->period_orig) ||
(inf->slice > inf->slice_orig)) {
+ //now switch back to standard
timing
+ inf->period = inf->period_orig;
+ inf->slice = inf->slice_orig;
+ }
}
}
inf->absdead += inf->period; //set next
deadline
@@ -333,9 +407,11 @@
__add_to_waitqueue_sort(inf->owner);
else {
//we have a blocked realtime task
- inf->absblock=now;
+ inf->absblock = now;
+ #if (EXTRA > EXTRA_OFF)
if (inf->extra == EXTRA_AWARE)
extraq_del(inf->owner); //remove a
blocked domain from the extraq aswell
+ #endif
}
}
check_waitq:
@@ -393,13 +469,16 @@
if (!list_empty(waitq)) {
waitinf = list_entry(waitq->next,struct
sedf_dom_info,list);
//we could not find any suitable domain => look for
domains that are aware of extratime
+ #if (EXTRA > EXTRA_OFF)
if (!list_empty(extraq) && (PERIOD_BEGIN(waitinf) - now
>= EXTRA_QUANTUM)) {
runinf = list_entry(extraq->next,struct
sedf_dom_info,extralist);
runinf->extra = EXTRA_RUNNING;
ret.task = runinf->owner;
ret.time = EXTRA_QUANTUM;
}
- else {
+ else
+ #endif
+ {
//we have an empty run- and extraqueue or too
less time => idle task!
ret.task = IDLETASK(cpu);
ret.time = PERIOD_BEGIN(waitinf) - now;
@@ -420,13 +499,19 @@
static void sedf_sleep(struct domain *d) {
PRINT(2,"sedf_sleep was called, domain-id %i\n",d->id);
- if ( test_bit(DF_RUNNING, &d->flags) )
+ if ( test_bit(DF_RUNNING, &d->flags) ) {
+#ifdef ADV_SCHED_HISTO
+ adv_sched_hist_start(d->processor);
+#endif
cpu_raise_softirq(d->processor, SCHEDULE_SOFTIRQ);
+ }
else {
_______________________________________________
Xen-changelog mailing list
Xen-changelog@xxxxxxxxxxxxxxxxxxx
http://lists.xensource.com/xen-changelog
|
Home