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

[Henrik Austad <henrik@austad.us>]

[-- Attachment #1: Type: text/plain, Size: 4369 bytes --]

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 #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 198 bytes --]