From: Peter Zijlstra on
On Sun, 2010-02-28 at 20:17 +0100, Raistlin wrote:
> +/*
> + * When a -deadline task is queued back on the runqueue, its runtime and
> + * deadline might need updating.
> + *
> + * The policy here is that we update the deadline of the task only if:
> + * - the current deadline is in the past,
> + * - using the remaining remaining with the current deadline would make

"remaining runtime", I presume?

> + * the task exceed its bandwidth.
> + */
> +static void update_dl_entity(struct sched_dl_entity *dl_se)
> +{
> + struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
> + struct rq *rq = rq_of_dl_rq(dl_rq);
> +
> + /*
> + * The arrival of a new task (or of a new task instance) needs
> + * special treatment. The actual scheduling parameters have to be
> + * "renewed" instead of recalculatetd accordingly to the bandwidth
> + * enforcement rule.
> + */
> + if (dl_se->flags & DL_NEW) {
> + setup_new_dl_entity(dl_se);
> + return;
> + }
> +
> + if (dl_time_before(dl_se->deadline, rq->clock))
> + goto update;
> +
> + if (!dl_check_bandwidth(dl_se, rq->clock)) {
> +update:
> + dl_se->deadline = rq->clock + dl_se->dl_deadline;
> + dl_se->runtime = dl_se->dl_runtime;
> + }
> +}

We could write that as:

if (dl_time_before(dl_se, rq->clock) ||
!dl_check_bandwidth(dl_se, rq->clock)) {
/* reset parameters */
}

Also, I was wondering about a more descriptive name for
dl_check_bandwidth(), check _what_ about the bandwidth!?

dl_bandwidth_overflow() perhaps, that would also remove that negation.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo(a)vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
From: Peter Zijlstra on
On Sun, 2010-02-28 at 20:17 +0100, Raistlin wrote:
> +/*
> + * Pure Earliest Deadline First (EDF) scheduling does not deal with the
> + * possibility of a task lasting more than what it declared, and thus
> + * exhausting its runtime.
> + *
> + * Here we are interested in making runtime overrun possible, but we do
> + * not want a task which is misbehaving to affect the scheduling of all
> + * other tasks.
> + * Therefore, a budgeting strategy called Constant Bandwidth Server (CBS)
> + * is used, in order to confine each task within its own bandwidth.
> + *
> + * This function deals exactly with that, and ensures that when the runtime
> + * of a task is replenished, its deadline is also postponed. That results
> + * in "priority unboosting" for the overrunning task, and makes it impossible
> + * for it to cause unexpected interfere to other tasks in the system.
> + */

This is not about lock/inheritance related overrun, right? But simply a
task that got its WCET wrong.


--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo(a)vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
From: Steven Rostedt on
On Tue, 2010-04-13 at 20:22 +0200, Peter Zijlstra wrote:
> On Sun, 2010-02-28 at 20:17 +0100, Raistlin wrote:
> > +/*
> > + * Here we check if --at time t-- a task (which is probably being
> > + * [re]activated or, in general, enqueued) can use its remaining runtime
> > + * and its current deadline _without_ exceeding the bandwidth it is
> > + * assigned (function returns true if it can).
> > + *
> > + * For this to hold, we must check if:
> > + * runtime / (deadline - t) < dl_runtime / dl_deadline .
> > + */
> > +static bool dl_check_bandwidth(struct sched_dl_entity *dl_se, u64 t)
> > +{
> > + u64 left, right;
> > +
> > + /*
> > + * left and right are the two sides of the equation above,
> > + * after a bit of shuffling to use multiplications instead
> > + * of divisions.
> > + */
> > + left = dl_se->dl_deadline * dl_se->runtime;
> > + right = (dl_se->deadline - t) * dl_se->dl_runtime;
> > +
> > + return dl_time_before(left, right);
> > +}
>
> So what happens when we overflow u64?

Is the resolution in nanosecs starting from zero? If so, then we don't
need to worry about overflow for 583 years? And that is only if the
difference in time is greater than 292 years since dl_time_before() does
a:

(s64)(a - b) < 0

The (s64)(a - b) returns the difference even on overflow as long as the
difference is not greater than 2^63


-- Steve


--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo(a)vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
From: Peter Zijlstra on
On Tue, 2010-04-13 at 14:55 -0400, Steven Rostedt wrote:
> On Tue, 2010-04-13 at 20:22 +0200, Peter Zijlstra wrote:
> > On Sun, 2010-02-28 at 20:17 +0100, Raistlin wrote:
> > > +/*
> > > + * Here we check if --at time t-- a task (which is probably being
> > > + * [re]activated or, in general, enqueued) can use its remaining runtime
> > > + * and its current deadline _without_ exceeding the bandwidth it is
> > > + * assigned (function returns true if it can).
> > > + *
> > > + * For this to hold, we must check if:
> > > + * runtime / (deadline - t) < dl_runtime / dl_deadline .
> > > + */
> > > +static bool dl_check_bandwidth(struct sched_dl_entity *dl_se, u64 t)
> > > +{
> > > + u64 left, right;
> > > +
> > > + /*
> > > + * left and right are the two sides of the equation above,
> > > + * after a bit of shuffling to use multiplications instead
> > > + * of divisions.
> > > + */
> > > + left = dl_se->dl_deadline * dl_se->runtime;
> > > + right = (dl_se->deadline - t) * dl_se->dl_runtime;
> > > +
> > > + return dl_time_before(left, right);
> > > +}
> >
> > So what happens when we overflow u64?
>
> Is the resolution in nanosecs starting from zero? If so, then we don't
> need to worry about overflow for 583 years? And that is only if the
> difference in time is greater than 292 years since dl_time_before() does
> a:
>
> (s64)(a - b) < 0
>
> The (s64)(a - b) returns the difference even on overflow as long as the
> difference is not greater than 2^63

Its a multiplication of two u64, that's a lot easier to overflow.

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo(a)vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/