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: <F3AA2541-6CF9-48A4-B0A6-E5CFA7BF53BB@email.unc.edu>
Date:	Sun, 11 Jul 2010 08:12:14 +0200
From:	Bjoern Brandenburg <bbb@...il.unc.edu>
To:	Peter Zijlstra <peterz@...radead.org>
Cc:	Luca Abeni <lucabe72@...il.it>, Raistlin <raistlin@...ux.it>,
	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>,
	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 Jul 10, 2010, at 12:36 PM, Peter Zijlstra wrote:
> On Sat, 2010-07-10 at 09:11 +0200, Luca Abeni wrote:
>> On Fri, 2010-07-09 at 16:24 +0200, Peter Zijlstra wrote:
>>> On Fri, 2010-07-09 at 15:38 +0200, Raistlin wrote:
>>>> Basically, from the scheduling point of view, what it could happen is
>>>> that I'm still _NOT_ going to allow a task with runtime Q_i, deadline
>>>> D_i and period P_i to use more bandwidth than Q_i/P_i, I'm still using D
>>>> for scheduling but the passing of the simple in-kernel admission test
>>>> Sum_i(Q_i/P_i)<1 won't guarantee that the task will always finish its
>>>> jobs before D. 
>>> 
>>> But the tardiness would still be bounded, right? So its a valid Soft-RT
>>> model?
> 
>> I think that if Sum_i(Q_i/P_i)<1 but Sum_i(Q_i/min{P_i,D_i})>=1 then you
>> can have sporadic deadline misses, but it should still be possible to
>> compute an upper bound for the tardiness.
>> But this is just a feeling, I have no proof... :)
> 
> The paper referenced by Bjoern yesterday mentioned that Baruah et al.
> did that proof.
> 
>        "For the considered case di < pi , Baruah et al. [7] showed
>        that the complexity increases considerably. However, as-
>        suming the processor utilization to be strictly less than 1,
>        Baruah et al. [6, 7] proved that if a deadline is missed,
>        this happens within a maximum time upper bound which
>        can be computed."
> 
> 
> [6] S. Baruah, A. Mok, and L. Rosier. Preemptively scheduling
> hard-real-time sporadic tasks on one processor. Proceedings
> of the 11th IEEE Real-Time Systems Symposium, December 1990.
> 
> [7] S. Baruah, L. Rosier, and R. Howell. Algorithms and
> complexity concerning the preemptive scheduling of peri-
> odic real-time tasks on one processor. Real-Time Systems,
> 2(4):301–324, November 1990.

These are two different things.

"Bounded tardiness" means "is there a constant x such that _every deadline_ is missed by at most x" and is commonly used in the context of global multiprocessor schedulers.

Baruah et al. showed that _on a uniprocessor_ the first deadline miss occurs within a bounded-length interval if the system is not fully utilized, which yields a slow but accurate admissions test. This result doesn't say by how much the first deadline is missed (if it is missed), nor whether or not there will be later deadline misses with ever-growing tardiness. (I don't think that's the case, but Baruah et al.'s work was not concerned with this question.)

> 
> 
> It also jives well with that I remember from reading through Jim's
> papers on Soft-RT G-EDF.
> 

Guaranteed bounded tardiness as long as the system is not over-utilized for the case P_i!=D_i follows from Leontyev & Anderson's work on window-constrained scheduling policies [1]: each priority priority point (i.e., deadline) lies within the window [release, release + max(D_i)] and is thus window-constrained.

- Björn

[1] H. Leontyev and J. Anderson, " Generalized Tardiness Bounds for Global Multiprocessor Scheduling ", Proceedings of the 28th IEEE Real-Time Systems Symposium, pp. 413-422, December 2007.  http://www.cs.unc.edu/~anderson/papers/rtss07b.pdf

---
Björn B. Brandenburg
Ph.D. Student 
Dept. of Computer Science
University of North Carolina at Chapel Hill
http://www.cs.unc.edu/~bbb




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