Re: [PATCH] sched/deadline: Add sched_dl documentation

From: Henrik Austad
Date: Mon Jan 27 2014 - 07:42:36 EST


On Mon, Jan 27, 2014 at 01:30:42PM +0100, Luca Abeni wrote:
> Hi Henrik,
>
> On 01/27/2014 12:53 PM, Henrik Austad wrote:
> [...]
> >>+ In more details, the CBS algorithm assigns scheduling deadlines to
> >>+ tasks in the following way:
> >>+
> >>+ - Each SCHED_DEADLINE task is characterised by the "runtime",
> >>+ "deadline", and "period" parameters;

> >>+
> >>+ - The state of the task is described by a "scheduling deadline", and
> >>+ a "current runtime". These two parameters are initially set to 0;
> >>+
> >>+ - When a SCHED_DEADLINE task wakes up (becomes ready for execution),
> >>+ the scheduler checks if
> >>+
> >>+ current runtime runtime
> >>+ ---------------------------------- > ----------------
> >>+ scheduling deadline - current time period
> >>+
> >>+ then, if the scheduling deadline is smaller than the current time, or
> >>+ this condition is verified, the scheduling deadline and the
> >>+ current budget are re-initialised as
> >
> >Current runtime: time spent running _this_ period? or is _remaining_
> >runtime this period? I get the feeling it's the latter.
> >
> >So, roughly, it is the ration
> >
> > remaining_runtime / relative_time_to_deadline
> >
> >which needs to be greater than the assigned CPU bandwidth, and if so, the
> >budget should be replensihed?
> >
> >Shouldn't there be something about not refilling the budget before a new
> >period has started?
> Uh... Maybe the description above can be improved :)
> Do you think that using "remaining runtime" instead of "current runtime"
> would help? If yes, I'll make this change.

Yes, in my vocabularly, "remaining" != "current" :), so changing to
'remaining runtime' would be nice.

> Also, I see that some of your questions are answered by some items below...

Yes, but I left the comments to indicate that the order was a bit
confusing.

> Do you think that changing the order of the items in the presentation would
> improve the readability? If you suggest a better ordering, I'll try to
> rewrite the algorithm's description according to it.

Could be, at least the ratio-caclulation was a bit confusing until I'd read
the entire section.

My preferred order (I've just cut'n'pased from the original email here)

+ - The state of the task is described by a "scheduling deadline", and
+ a "current runtime". These two parameters are initially set to 0;
+
+ - Each SCHED_DEADLINE task is characterised by the "runtime",
+ "deadline", and "period" parameters;
+



+ - When a SCHED_DEADLINE task executes for an amount of time t, its
+ current runtime is decreased as
+
+ current runtime = current runtime - t
+
+ (technically, the runtime is decreased at every tick, or when the
+ task is descheduled / preempted);
+
+ - When the current runtime becomes less or equal than 0, the task is
+ said to be "throttled" (also known as "depleted" in real-time literature)
+ and cannot be scheduled until its scheduling deadline. The "replenishment
+ time" for this task (see next item) is set to be equal to the current
+ value of the scheduling deadline;
+
+ - When the current time is equal to the replenishment time of a
+ throttled task, the scheduling deadline and the current runtime are
+ updated as
+
+ scheduling deadline = scheduling deadline + period
+ current runtime = current runtime + runtime




+ - When a SCHED_DEADLINE task wakes up (becomes ready for execution),
+ the scheduler checks if
+
+ current runtime runtime
+ ---------------------------------- > ----------------
+ scheduling deadline - current time period
+
+ then, if the scheduling deadline is smaller than the current time, or
+ this condition is verified, the scheduling deadline and the
+ current budget are re-initialised as
+
+ scheduling deadline = current time + deadline
+ current runtime = runtime
+
+ otherwise, the scheduling deadline and the current runtime are
+ left unchanged;
+

Emphasis on -my- preferred order. :)

Either way, I'm quite happy with this documentation-update, this is just
nitpick :)

--
Henrik Austad

Attachment: signature.asc
Description: Digital signature