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: Windows password security audit tool. GUI, reports in PDF.

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

Message-ID: <alpine.LRH.2.00.0907141259100.16818@anderson.cs.unc.edu>
Date:	Tue, 14 Jul 2009 13:16:52 -0400 (EDT)
From:	"James H. Anderson" <anderson@...unc.edu>
To:	Peter Zijlstra <a.p.zijlstra@...llo.nl>
cc:	Chris Friesen <cfriesen@...tel.com>, Raistlin <raistlin@...ux.it>,
	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>,
	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>,
	Bjoern Brandenburg <bbb@...unc.edu>,
	"James H. Anderson" <anderson@...unc.edu>
Subject: Re: RFC for a new Scheduling policy/class in the Linux-kernel

On Tue, 14 Jul 2009, Peter Zijlstra wrote:

> On that, how does the priority ceiling/protection protocol extend to
> deadline schedulers?

Sorry -- I should have responded to this.

These things are pretty easy to extend to deadline scheduling if
partitioning is assumed, and this has been done.  However, it is not
easy to do under global scheduling.  Having tasks pinned to processors
(partitioning) makes it much easier to compute blocking terms (it's much
easier to predict what is happening on each processor at any time).
Without this, it is *really* hard to compute reasonable blocking
terms.  Even doing something as mundane as avoiding deadlocks without a lot
of overhead may not be trivial.  At the time we developed the FMLP
(a couple of years ago), there was *no* published locking protocol (to my
knowledge) that worked under GEDF.  To my knowledge, the FMLP is still the
only one that works under GEDF.  (BTW, I should say that I am not
familiar with the PEP protocol that has been discussed in this thread.
I assume it doesn't work under GEDF, or you wouldn't have asked the
question.)

BTW, FIFO waiting makes blocking terms in the global case much easier
to compute: once a lock request is initiated, the set of blocking lock
requests (onces initiated earlier) is fixed.  (This is actually a bit
of an over-simplification if waiting is by suspending.)  With priority-based
waiting, higher-priority requests can come later.  Determining a
reasonable bound on the number of such requests is hard.

You can find references to papers by others in our FMLP papers.

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