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: <4CE18EC0.8070802@cs.unc.edu>
Date:	Mon, 15 Nov 2010 14:49:20 -0500
From:	"James H. Anderson" <anderson@...unc.edu>
To:	Luca Abeni <luca.abeni@...tn.it>
CC:	Raistlin <raistlin@...ux.it>,
	Peter Zijlstra <peterz@...radead.org>,
	Ingo Molnar <mingo@...e.hu>,
	Thomas Gleixner <tglx@...utronix.de>,
	Steven Rostedt <rostedt@...dmis.org>,
	Chris Friesen <cfriesen@...tel.com>, oleg@...hat.com,
	Frederic Weisbecker <fweisbec@...il.com>,
	Darren Hart <darren@...art.com>,
	Johan Eker <johan.eker@...csson.com>,
	"p.faure" <p.faure@...tech.ch>,
	linux-kernel <linux-kernel@...r.kernel.org>,
	Claudio Scordino <claudio@...dence.eu.com>,
	michael trimarchi <trimarchi@...is.sssup.it>,
	Fabio Checconi <fabio@...dalf.sssup.it>,
	Tommaso Cucinotta <cucinotta@...up.it>,
	Juri Lelli <juri.lelli@...il.com>,
	Nicola Manica <nicola.manica@...i.unitn.it>,
	Dhaval Giani <dhaval@...is.sssup.it>,
	Harald Gustafsson <hgu1972@...il.com>,
	paulmck <paulmck@...ux.vnet.ibm.com>,
	Bjoern Brandenburg <bbb@...il.unc.edu>
Subject: Re: [RFC][PATCH 18/22] sched: add reclaiming logic to -deadline tasks



On 11/15/2010 2:23 PM, Luca Abeni wrote:
> Hi James,
>
> On 15/11/10 19:37, James H. Anderson wrote:
> [...]
>>>> The problem the stochastic execution time model tries to address is 
>>>> the
>>>> WCET computation mess, WCET computation is hard and often overly
>>>> pessimistic, resulting in under-utilized systems.
>>>>
>>> I know, and it's very reasonable. The point I'm trying to make is that
>>> resource reservation tries to address the very same issue.
>>> I am all but against this model, just want to be sure it's not too much
>>> in conflict to the other features we have, especially with resource
>>> reservation. Especially considering that --if I got the whole thing
>>> about this scheduler right-- resource reservation is something we 
>>> really
>>> want, and I think UNC people would agree here, since I heard Bjorn
>>> stating this very clear both in Dresden and in Dublin. :-)
>>>
>>> BTW, I'm adding them to the Cc, seems fair, and more useful than all
>>> this speculation! :-P
>>>
>>> Bjorn, Jim, sorry for bothering. If you're interested, this is the very
>>> beginning of the whole thread:
>>> http://lkml.org/lkml/2010/10/29/67
> [...]
>> If you're talking about our most recent "stochastic" paper, it is about
>> supporting
>> soft real-time task systems on a multiprocessor where resource
>> reservations are
>> used. The main result of the paper is that if you provision the
>> reservation for a
>> task slightly higher than it's average-case execution time, and if you
>> use a
>> scheduling algorithm (like global EDF) that ensures bounded tardiness
>> (w.r.t.
>> these reservations), then the task's expected tardiness will be bounded
>> and the
>> expected bound does not depend on worst-case execution times. I'm not
>> sure if
>> slack-reallocation methods have come up in this discussion (sorry, I'm
>> really
>> pressed for time and didn't look), but we didn't get into that in our
>> paper.
> So, if I understand well (sorry, I am just trying to make a short 
> summary to check if we are aligned) your analysis is similar to the 
> one presented in the papers I mentioned earlier in this thread 
> (different stochastic modelling, but similar approach): you analyse a 
> reservation in isolation and you provide some stochastic tardiness 
> guarantees based on an (e_i, p_i) service model.... Right?
Sorry, I don't have time right now to check these papers, but what you 
are saying sounds correct.

>
> If my understanding is correct (please, correct me if I am wrong), 
> your analysis can be applied even with the current version of Dario's 
> patch (I mean: no modifications to the patch are needed for removing 
> assumptions about WCET knowledge... Your paper uses a sporadic server 
> for the reservation mechanism, but I think a CBS can work too...).

This sounds correct a well.  We assume that if a job of a task overruns 
its current budget allocation (which will likely happen, provisioning 
reservations on the average case), then the remainder of that job will 
be executed using future allocations for the same task.  The analysis 
doesn't (I think) depend too much on the exact way reservations are 
supported.

-Jim


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

Powered by blists - more mailing lists

Powered by Openwall GNU/*/Linux Powered by OpenVZ