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: <CFACD068-2139-4FAE-8A2D-B138DD6B80D6@cs.unc.edu>
Date:	Wed, 4 Aug 2010 01:18:20 -0400
From:	Bjoern Brandenburg <bbb@...unc.edu>
To:	Peter Zijlstra <peterz@...radead.org>
Cc:	Bjoern Brandenburg <bbb@...il.unc.edu>,
	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>,
	Luca Abeni <lucabe72@...il.it>,
	Claudio Scordino <claudio@...dence.eu.com>,
	Harald Gustafsson <harald.gustafsson@...csson.com>,
	"bastoni@...unc.edu" <bastoni@...unc.edu>,
	Giuseppe Lipari <lipari@...is.sssup.it>
Subject: Re: periods and deadlines in SCHED_DEADLINE

On Aug 3, 2010, at 5:41 AM, Peter Zijlstra <peterz@...radead.org> wrote:

> On Sun, 2010-07-11 at 08:42 +0200, Bjoern Brandenburg wrote:
>> 
>> If you want to do G-EDF with limited and different budgets on each CPU
>> (e.g., G-EDF tasks may only run for 100 out of 1000 ms on CPU 0, but
>> for 400 out of 1000 ms on CPU 1), then you are entering the domain of
>> restricted-supply scheduling, which is significantly more complicated
>> to analyze (see [1,2]). 
> 
> Without having looked at the refs, won't the soft case still have
> bounded tardiness? Since the boundedness property mostly depends on
> u<=1, that is, as long as we can always run everything within the
> available time we won't start drifting.

No, not in all cases. Suppose you have a soft task with a  utilization of 0.2 and two G-EDF reservations of utilization 0.15 each (the rest of the CPU time is allocated to partitioned hard tasks), reservation periods and task period are equal, and no CPU is overutilized. If the reservations become available at different times during each period, then the soft task has bounded tardiness, but if they become available in parallel, then tardiness can grow unboundedly because it can only execute on one CPU at a time.

Hennadiy Leontvey has analyzed this in the bounded-tardiness context extensively and provides some counter examples in his dissertation. For hard real-time, the MPR papers that Andrea pointed out are the state of the art afaik. (I stand by my opinion that global hard real-time is less pressing for the Linux kernel.)

> 
>> As far as I know there is no exiting analysis for "almost G-EDF",
>> i.e.,  the case where each task may only migrate among a subset of the
>> processors (= affinity masks), except for the special case of
>> clustered EDF (C-EDF), wherein the subsets of processors are
>> non-overlapping. 
> 
> Right, affinity masks are a pain, hence I proposed to limit that to
> either 1 cpu (yielding fully paritioned) or the full cluster.

Yes, I agree.

> That will leave us with only having to stack a partitioned and global
> scheduler on top of each other, and per the previous point, I think that
> ought to work out trivially for soft, hard otoh will get 'interesting'.

As I mentioned in my other reply, this is exactly what EDF-HSB (http://www.cs.unc.edu/~anderson/papers/ecrts07b.pdf) does.

- Björn

--
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/