linux-kernel - Re: periods and deadlines in 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]

Message-ID: <1278745706.4390.2.camel@Palantir>
Date:	Sat, 10 Jul 2010 09:08:26 +0200
From:	Raistlin <raistlin@...ux.it>
To:	Bjoern Brandenburg <bbb@...il.unc.edu>
Cc:	Peter Zijlstra <peterz@...radead.org>,
	linux-kernel <linux-kernel@...r.kernel.org>,
	Song Yuan <song.yuan@...csson.com>,
	Dmitry Adamushko <dmitry.adamushko@...il.com>,
	Thomas Gleixner <tglx@...utronix.de>,
	Nicola Manica <nicola.manica@...i.unitn.it>,
	Luca Abeni <lucabe72@...il.it>,
	Claudio Scordino <claudio@...dence.eu.com>,
	Harald Gustafsson <harald.gustafsson@...csson.com>,
	bastoni@...unc.edu, Giuseppe Lipari <lipari@...is.sssup.it>
Subject: Re: periods and deadlines in SCHED_DEADLINE

On Fri, 2010-07-09 at 16:51 +0200, Bjoern Brandenburg wrote:
> > Happen to have a paper handy that explains all this in a concise way? 
> > 
> 
> Sounds confusing, but this is actually not that complicated.
> 
> - If the period exceeds the deadline of a task, then it is said to have a constrained deadline, and is said to be a constrained task.
> 
> - The density of a task is the ratio budget/min(period, relative deadline). The density of a task is at most its utilization (budget/period).
> 
> - There exists a simple *sufficient* (but not necessary) test for uniprocessor EDF for constrained tasks: if the sum of all task densities is at most one (on each processor), then all jobs will meet their deadlines. (Of course, this assumes that the budget is only replenished at the beginning at each period and does not take self-suspensions due to I/O etc. into account.)
> 
Right, I think Bjoern made it much more clear than how you can find it
in many of the existing papers! :-)

Just to make a simple UP example, if you have two tasks with the
following parameters (where T_i=(C_i, P_i, D_i)):

 T_1 = (4, 10, 5)
 T_2 = (4, 10, 5)

Then the test Sum_i(C_i/P_i)<1 will say "go!" (4/10+4/10<1), but
one of the tasks can miss its deadline by 3 time units in the worst case
(if, and if yes which one, depends on the order with witch they arrive).

Using D_i instead of P_i in the test will make things better in this
case (4/5+4/5>1 ==> "no go!"), but its overly pessimistic (i.e., only
sufficient). In fact for this task set:

T_1 = (1, 10, 2)
T_2 = (2, 20, 4)
T_3 = (3, 50, 6)

which has small utilization (Sum_i(C_i/P_i)=.26) and *is schedulable*,
even if 1/2+2/4+3/6=1.5>1.

Hope this helped in clarifying things even more! :-D
Btw, another nice survey about schedulability tests for global EDF I
know (and you'll forgive me if I point you to something from my
institution :-)) is this http://retis.sssup.it/~marko/papers/ICPP09.pdf.

> As a side note, almost all global EDF hard real-time admission tests can handle tasks with constrained deadlines transparently. However, as far as I can tell, they do not apply to SCHED_DEADLINE.
> 
This is the only part I am not sure I got... Can you explain me what do
you mena by "they do not apply" ?

> PS: My responses will be delayed, I'm off to the airport...
> 
Yep, so will be mine one, including this one! :-P

Thanks and regards,
Dario

-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
----------------------------------------------------------------------
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa  (Italy)

http://blog.linux.it/raistlin / raistlin@...ga.net /
dario.faggioli@...ber.org


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