linux-kernel - Re: RFC for a new Scheduling policy/class in the Linux-kernel

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 for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Tue, 14 Jul 2009 18:48:32 +0200
From:	Raistlin <raistlin@...ux.it>
To:	Chris Friesen <cfriesen@...tel.com>
Cc:	Peter Zijlstra <a.p.zijlstra@...llo.nl>,
	Douglas Niehaus <niehaus@...c.ku.edu>,
	Henrik Austad <henrik@...tad.us>,
	LKML <linux-kernel@...r.kernel.org>, Ingo Molnar <mingo@...e.hu>,
	Bill Huey <billh@...ppy.monkey.org>,
	Linux RT <linux-rt-users@...r.kernel.org>,
	Fabio Checconi <fabio@...dalf.sssup.it>,
	"James H. Anderson" <anderson@...unc.edu>,
	Thomas Gleixner <tglx@...utronix.de>,
	Ted Baker <baker@...fsu.edu>,
	Dhaval Giani <dhaval.giani@...il.com>,
	Noah Watkins <jayhawk@....ucsc.edu>,
	KUSP Google Group <kusp@...glegroups.com>,
	Tommaso Cucinotta <cucinotta@...up.it>,
	Giuseppe Lipari <lipari@...is.sssup.it>
Subject: Re: RFC for a new Scheduling policy/class in the Linux-kernel

On Tue, 2009-07-14 at 08:48 -0600, Chris Friesen wrote:
> Let's call the highest priority task A, while the task holding the lock
> (that A wants) is called B.  Suppose we're on an dual-cpu system.
> 
Ok.

> According to your proposal above we would have A busy-waiting while B
> runs with A's priority.  When B gives up the lock it gets downgraded and
> A acquires it and continues to run.
> 
Yes. The first part of my proposal --the "theoretically safe" one.

> Alternately, we could have A blocked waiting for the lock, a separate
> task C running, and B runs with A's priority on the other cpu.  When B
> gives up the lock it gets downgraded and A acquires it and continues to run.
> 
Right. And this is in my proposal as well.

I'm just saying that the analysis gets more complicated, that some of
the nice properties may be lost, and suggested a first draft of idea to
turn it back to be easy again... With, unfortunately, a lot of flaws in
there yet. :-(

In fact, I'm suggesting that, in the scenario you described, C should be
able to run, but B's budget have to be affected somehow.

> From an overall system perspective we allowed C to make additional
> forward progress, increasing the throughput.
As said, I agre with this from the very beginning of the whole
thing! :-)

>  On the other hand, there
> is a small window where A isn't running and it theoretically should be.
>   If we can bound it, would this window really cause so much difficulty
> to the schedulability analysis?
> 
Well, I'm not sure right now... I would need to do some math to be!

Remember that all my points are concerned with budgets, i.e., a scenario
where you have some mean to limit the capability of a task to ask for
CPU time over some kind of period.
And here it is where the problem comes since running C instead of having
A busy waiting means:
- that A is actually blocked, as said before;
- that A's budget is not diminished.
And this certainly improves system throughput but may affect its
predictability and, in this particular case, task's isolation among each
other...

Anyway, if you are saying that this could be a possible theory-practice
compromise, well, could be... And I'm open and ready to (try to)
contribute even in a discussion of such kind. :-)

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" (198 bytes)