linux-kernel - Re: [PATCH] sched/deadline: Add sched

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date:	Mon, 27 Jan 2014 13:40:11 +0100
From:	Henrik Austad <henrik@...tad.us>
To:	Luca Abeni <luca.abeni@...tn.it>
Cc:	Juri Lelli <juri.lelli@...il.com>, peterz@...radead.org,
	tglx@...utronix.de, mingo@...hat.com, rostedt@...dmis.org,
	oleg@...hat.com, fweisbec@...il.com, darren@...art.com,
	johan.eker@...csson.com, p.faure@...tech.ch,
	linux-kernel@...r.kernel.org, claudio@...dence.eu.com,
	michael@...rulasolutions.com, fchecconi@...il.com,
	tommaso.cucinotta@...up.it, nicola.manica@...i.unitn.it,
	dhaval.giani@...il.com, hgu1972@...il.com,
	paulmck@...ux.vnet.ibm.com, raistlin@...ux.it,
	insop.song@...il.com, liming.wang@...driver.com, jkacur@...hat.com,
	harald.gustafsson@...csson.com, vincent.guittot@...aro.org,
	bruce.ashfield@...driver.com, linux-doc@...r.kernel.org,
	rob@...dley.net
Subject: Re: [PATCH] sched/deadline: Add sched_dl documentation

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

Download attachment "signature.asc" of type "application/pgp-signature" (199 bytes)