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: <51F8E441-58D7-45E1-B7A0-7A717EDF08B5@email.unc.edu>
Date:	Fri, 9 Jul 2010 16:51:45 +0200
From:	Bjoern Brandenburg <bbb@...il.unc.edu>
To:	Peter Zijlstra <peterz@...radead.org>
Cc:	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, Giuseppe Lipari <lipari@...is.sssup.it>
Subject: Re: periods and deadlines in SCHED_DEADLINE


On Jul 9, 2010, at 4:18 PM, Peter Zijlstra wrote:

> On Fri, 2010-07-09 at 15:38 +0200, Raistlin wrote:
> 
>> - using periods for calculating the tasks' bandwidth and then using   
>>   deadlines for scheduling the tasks is going to work, but the
>>   admission control test that you would need for ensuring anybody
>>   will make its deadline is waaay more complex than Sum_i(BW_i)<1, even
>>   for uniprocessors/partitionig. That one instead would gives you just
>>   a very basic guarantee that the design in not completely broken
>>   (formally, I think I should say it is only a necessary
>>   condition :-)).
> 
> 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.)

- More accurate tests exist. A very recent paper (presented this Wednesday at ECRTS) by Masrur et al. provides a summary of the state of the art and a new constant-time admissions test.

	Constant-Time Admission Control for Partitioned EDF
	Alejandro Masrur, Samarjit Chakraborty, and Georg Färber
	Proc. ECRTS 2010, pp 34-43
	ftp://ftp.rcs.ei.tum.de/pub/papers/rtsg/edffast.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.

- Björn

PS: My responses will be delayed, I'm off to the airport...


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