|
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] [Xen-devel] [RFC PATCH v2 3/7] Added constant bandwidth server functionality to sedf scheduler
This patch adds the pieces needed for the CBS functionality. This includes a
"soft" flag to indicate whether a domain should be handled in a pure EDF manner
or handled by the CBS algorithm, the CBS algorithm itself to the wake function,
and few other bits and comments to track scheduler statistics, set parameters,
and document the functionality of the code itself.
Signed-off-by: Nathan Studer <nate.studer@xxxxxxxxx>
Signed-off-by: Joshua Whitehead <Josh.Whitehead@xxxxxxxxxxxxxxx>
---
xen/common/sched_sedf.c | 197 ++++++++++++++++++++++++++++++++++++-----------
1 file changed, 153 insertions(+), 44 deletions(-)
diff --git a/xen/common/sched_sedf.c b/xen/common/sched_sedf.c
index a8dd3e0..7333095 100644
--- a/xen/common/sched_sedf.c
+++ b/xen/common/sched_sedf.c
@@ -1,5 +1,5 @@
/******************************************************************************
- * Simple EDF Scheduler for xen
+ * Simple EDF Scheduler for Xen
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to
@@ -46,6 +46,7 @@
#define CHECK(_p) ((void)0)
#endif
+#define SEDF_SOFT_TASK (1)
#define SEDF_ASLEEP (16)
#define DEFAULT_PERIOD (MILLISECS(20))
@@ -73,7 +74,8 @@ struct sedf_vcpu_info {
/* Parameters for EDF */
s_time_t period; /* = Server scheduling period */
- s_time_t budget; /* = Guarenteed minimum CPU time per period */
+ s_time_t budget; /* = Guarenteed minimum CPU time per period */
+ /* Note: Server bandwidth = (budget / period) */
/* Status of vcpu */
int status;
@@ -90,6 +92,10 @@ struct sedf_vcpu_info {
int block_tot;
int short_block_tot;
int long_block_tot;
+ s_time_t miss_time;
+ s_time_t over_time;
+ int miss_tot;
+ int over_tot;
#endif
};
@@ -115,6 +121,7 @@ struct sedf_cpu_info {
#define sedf_runnable(edom) (!(SEDF_VCPU(edom)->status & SEDF_ASLEEP))
+#define sedf_soft(edom) (SEDF_VCPU(edom)->status & SEDF_SOFT_TASK)
static void sedf_dump_cpu_state(const struct scheduler *ops, int cpu);
@@ -208,6 +215,7 @@ static void *sedf_alloc_vdata(const struct scheduler *ops,
struct vcpu *v, void
inf->vcpu = v;
inf->deadl_abs = 0;
+ inf->cputime = 0;
inf->status = SEDF_ASLEEP;
if (v->domain->domain_id == 0)
@@ -306,29 +314,64 @@ static void desched_edf_vcpu(s_time_t now, struct vcpu *v)
/* Update the vcpu's cputime */
inf->cputime += now - inf->sched_start_abs;
- /* Scheduling decisions which don't remove the running vcpu from
- * the runq */
+ /* If running vcpu has budget remaining, return */
if ( (inf->cputime < inf->budget) && sedf_runnable(v) )
return;
+ /* Current vcpu has consumed its budget for this period */
__del_from_queue(v);
- /*
- * Manage bookkeeping (i.e. calculate next deadline, memorise
- * overrun-time of budget) of finished vcpus.
- */
+#ifdef SEDF_STATS
+ /* Manage deadline misses */
+ if ( unlikely(inf->deadl_abs < now) )
+ {
+ inf->miss_tot++;
+ inf->miss_time += inf->cputime;
+ }
+#endif
+
+ /* Manage overruns */
if ( inf->cputime >= inf->budget )
{
inf->cputime -= inf->budget;
/* Set next deadline */
inf->deadl_abs += inf->period;
+
+ /* Ensure that the cputime is always less than budget */
+ if ( unlikely(inf->cputime > inf->budget) )
+ {
+#ifdef SEDF_STATS
+ inf->over_tot++;
+ inf->over_time += inf->cputime;
+#endif
+
+ /* Make up for the overage by pushing the deadline
+ into the future; ensure one domain doesn't consistently
+ consume extra time by overrunning its budget */
+ inf->deadl_abs += ((inf->cputime / inf->budget)
+ * inf->period);
+ inf->cputime -= (inf->cputime / inf->budget) * inf->budget;
+ }
+
+ /* Ensure that the start of the next period is in the future */
+ if ( unlikely(PERIOD_BEGIN(inf) < now) )
+ inf->deadl_abs +=
+ (DIV_UP(now - PERIOD_BEGIN(inf),
+ inf->period)) * inf->period;
}
/* Add a runnable vcpu to the appropriate queue */
if ( sedf_runnable(v) )
{
- __add_to_waitqueue_sort(v);
+ if( sedf_soft(v) )
+ {
+ __add_to_runqueue_sort(v);
+ }
+ else
+ {
+ __add_to_waitqueue_sort(v);
+ }
}
ASSERT(EQ(sedf_runnable(v), __task_on_queue(v)));
@@ -418,9 +461,9 @@ static void sedf_deinit(const struct scheduler *ops)
static struct task_slice sedf_do_schedule(
const struct scheduler *ops, s_time_t now, bool_t tasklet_work_scheduled)
{
- int cpu = smp_processor_id();
- struct list_head *runq = RUNQ(cpu);
- struct list_head *waitq = WAITQ(cpu);
+ int cpu = smp_processor_id();
+ struct list_head *runq = RUNQ(cpu);
+ struct list_head *waitq = WAITQ(cpu);
struct sedf_vcpu_info *inf = SEDF_VCPU(current);
struct sedf_vcpu_info *runinf, *waitinf;
struct task_slice ret;
@@ -469,7 +512,7 @@ static struct task_slice sedf_do_schedule(
waitinf = list_entry(waitq->next,
struct sedf_vcpu_info, list);
/*
- * Rerun scheduler, when scheduled vcpu consumes
+ * Rerun scheduler when scheduled vcpu consumes
* its budget or the first vcpu from the waitqueue
* gets ready.
*/
@@ -490,7 +533,7 @@ static struct task_slice sedf_do_schedule(
}
/*
- * TODO: Do something USEFUL when this happens and find out, why it
+ * TODO: Do something USEFUL when this happens and find out why it
* still can happen!!!
*/
if ( ret.time < 0)
@@ -554,15 +597,21 @@ static inline int should_switch(struct vcpu *cur,
/*
* This function wakes up a vcpu, i.e. moves them into the appropriate queue
*
- * When a blocked vcpu unblocks, it is allowed to start execution at
- * the beginning of the next complete period
- * (D..deadline, R..running, B..blocking/sleeping, U..unblocking/waking up
+ * For Hard Real-Time vcpus (soft = 0):
+ * -When a blocked vcpu unblocks, it is allowed to start execution at
+ * the beginning of the next complete period
+ * (D..deadline, R..running, B..blocking/sleeping, U..unblocking/waking up
+ *
+ * DRRB_____D__U_____DRRRRR___D________ ...
+ *
+ * -This causes the vcpu to miss a period (and a deadlline)
+ * -Doesn't disturb the schedule at all
+ * -Deadlines keep occuring isochronous
*
- * DRRB_____D__U_____DRRRRR___D________ ...
+ * For Soft Real-Time vcpus (soft = 1):
+ * -Deadlines are set and updated according to the Constant Bandwidth
Server
+ * rule and vcpus are moved immediately to the run queue.
*
- * - This causes the vcpu to miss a period (and a deadlline)
- * - Doesn't disturb the schedule at all
- * - Deadlines keep occuring isochronous
*/
static void sedf_wake(const struct scheduler *ops, struct vcpu *v)
{
@@ -588,21 +637,62 @@ static void sedf_wake(const struct scheduler *ops, struct
vcpu *v)
inf->block_tot++;
#endif
- if ( now < inf->deadl_abs )
- {
- /* Short blocking */
- inf->short_block_tot++;
- }
- else
+ if ( sedf_soft(v) )
{
- /* Long unblocking, someone is going to miss their deadline. */
- inf->long_block_tot++;
+ /*
+ * Apply CBS rule
+ * Where:
+ * c == Remaining server budget == (inf->budget - cpu_time)
+ * d == Server (vcpu) deadline == inf->deadl_abs
+ * r == Wake-up time of vcpu == now
+ * U == Server (vcpu) bandwidth == (inf->budget / inf->period)
+ *
+ * if c>=(d-r)*U --->
+ * (inf->budget - cputime) >=
+ * (inf->deadl_abs - now) * (inf->period / inf->period)
+ *
+ * If true, push deadline back by one period and refresh budget, else
+ * use current budget and deadline.
+ *
+ * Note: The 'if' statement below is equivalent to the above comments;
+ * it has been simplified to avoid the division operator
+ */
+ if ((inf->budget - inf->cputime) * inf->period >=
+ (inf->deadl_abs - now) * inf->budget)
+ {
+ /* Push back deadline by one period */
+ inf->deadl_abs += inf->period;
+ inf->cputime = 0;
+ }
+
+ /*
+ * In CBS we don't care if the period has begun,
+ * the task doesn't have to wait for its period
+ * because it'll never request more than its budget
+ * for any given period.
+ */
+ __add_to_runqueue_sort(v);
}
+ else {
+ /* Task is a hard task, treat accordingly */
+#ifdef SEDF_STATS
+ if ( now < inf->deadl_abs )
+ {
+ /* Short blocking */
+ inf->short_block_tot++;
+ }
+ else
+ {
+ /* Long unblocking, someone is going to miss their deadline. */
+ inf->long_block_tot++;
+ }
+#endif
- if ( PERIOD_BEGIN(inf) > now )
- __add_to_waitqueue_sort(v);
- else
- __add_to_runqueue_sort(v);
+ if ( PERIOD_BEGIN(inf) > now )
+ __add_to_waitqueue_sort(v);
+ else
+ __add_to_runqueue_sort(v);
+ }
#ifdef SEDF_STATS
/* Do some statistics here... */
@@ -626,7 +716,7 @@ static void sedf_wake(const struct scheduler *ops, struct
vcpu *v)
cpu_raise_softirq(v->processor, SCHEDULE_SOFTIRQ);
}
-/* Print a lot of useful information about a vcpus in the system */
+/* Print a lot of useful information about a vcpu in the system */
static void sedf_dump_vcpu(struct vcpu *v)
{
printk("%i.%i has=%c ", v->domain->domain_id, v->vcpu_id,
@@ -635,17 +725,18 @@ static void sedf_dump_vcpu(struct vcpu *v)
SEDF_VCPU(v)->period, SEDF_VCPU(v)->budget,
SEDF_VCPU(v)->deadl_abs);
#ifdef SEDF_STATS
- if ( SEDF_VCPU(v)->block_time_tot != 0 )
- printk(" pen=%"PRIu64"%%", SEDF_VCPU(v)->block_time_tot);
+ printk(" m=%u mt=%"PRIu64"o=%u ot=%"PRIu64,
+ SEDF_VCPU(v)->miss_tot, SEDF_VCPU(v)->miss_time,
+ SEDF_VCPU(v)->over_tot, SEDF_VCPU(v)->over_time);
+
if ( SEDF_VCPU(v)->block_tot != 0 )
printk("\n blks=%u sh=%u (%u%%) "\
- "l=%u (%u%%) avg: b=%"PRIu64" p=%d",
+ "l=%u (%u%%) avg: b=%"PRIu64,
SEDF_VCPU(v)->block_tot, SEDF_VCPU(v)->short_block_tot,
(SEDF_VCPU(v)->short_block_tot * 100) / SEDF_VCPU(v)->block_tot,
SEDF_VCPU(v)->long_block_tot,
(SEDF_VCPU(v)->long_block_tot * 100) / SEDF_VCPU(v)->block_tot,
- (SEDF_VCPU(v)->block_time_tot) / SEDF_VCPU(v)->block_tot,
- SEDF_VCPU(v)->block_tot);
+ (SEDF_VCPU(v)->block_time_tot) / SEDF_VCPU(v)->block_tot);
#endif
printk("\n");
}
@@ -708,6 +799,7 @@ static int sedf_adjust(const struct scheduler *ops, struct
domain *d, struct xen
{
struct sedf_priv_info *prv = SEDF_PRIV(ops);
unsigned long flags;
+ s_time_t now = NOW();
struct vcpu *v;
int rc = 0;
@@ -726,6 +818,7 @@ static int sedf_adjust(const struct scheduler *ops, struct
domain *d, struct xen
/* Check for sane parameters */
if ( !op->u.sedf.period )
{
+ printk("Period Not set");
rc = -EINVAL;
goto out;
}
@@ -735,9 +828,10 @@ static int sedf_adjust(const struct scheduler *ops, struct
domain *d, struct xen
*/
if ( (op->u.sedf.period > PERIOD_MAX) ||
(op->u.sedf.period < PERIOD_MIN) ||
- (op->u.sedf.slice > op->u.sedf.slice) ||
- (op->u.sedf.slice < BUDGET_MIN) )
+ (op->u.sedf.budget > op->u.sedf.budget) ||
+ (op->u.sedf.budget < BUDGET_MIN) )
{
+ printk("Insane Parameters: period: %lu\tbudget: %lu\n",
op->u.sedf.period, op->u.sedf.budget);
rc = -EINVAL;
goto out;
}
@@ -748,7 +842,21 @@ static int sedf_adjust(const struct scheduler *ops, struct
domain *d, struct xen
spinlock_t *lock = vcpu_schedule_lock(v);
SEDF_VCPU(v)->period = op->u.sedf.period;
- SEDF_VCPU(v)->budget = op->u.sedf.slice;
+ SEDF_VCPU(v)->budget = op->u.sedf.budget;
+ if(op->u.sedf.soft)
+ {
+ SEDF_VCPU(v)->status |= SEDF_SOFT_TASK;
+ }
+ else
+ {
+ /* Correct deadline when switching from a soft to hard vcpu */
+ if( unlikely((SEDF_VCPU(v)->deadl_abs - now) >=
(SEDF_VCPU(v)->period * 3)) )
+ {
+ SEDF_VCPU(v)->deadl_abs = (now - SEDF_VCPU(v)->cputime) +
(2 * SEDF_VCPU(v)->period);
+ }
+
+ SEDF_VCPU(v)->status &= (~SEDF_SOFT_TASK);
+ }
vcpu_schedule_unlock(lock, v);
}
}
@@ -760,8 +868,9 @@ static int sedf_adjust(const struct scheduler *ops, struct
domain *d, struct xen
goto out;
}
- op->u.sedf.period = SEDF_VCPU(d->vcpu[0])->period;
- op->u.sedf.slice = SEDF_VCPU(d->vcpu[0])->budget;
+ op->u.sedf.period = SEDF_VCPU(d->vcpu[0])->period;
+ op->u.sedf.budget = SEDF_VCPU(d->vcpu[0])->budget;
+ op->u.sedf.soft = sedf_soft(d->vcpu[0]);
}
out:
--
1.7.9.5
_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxx
http://lists.xen.org/xen-devel
|
 |
Lists.xenproject.org is hosted with RackSpace, monitoring our |