Subject: Re: Deadline scheduling (was: Re: Rearranging layout of code in
 the scheduler)
From: Peter Zijlstra <peterz@infradead.org>
To: faggioli@gandalf.sssup.it
Cc: henrik@austad.us, Ingo Molnar <mingo@elte.hu>,
       linux-kernel <linux-kernel@vger.kernel.org>, fabio@gandalf.sssup.it,
       Michael Trimarchi <trimarchimichael@yahoo.it>,
       Thomas Gleixner <tglx@linutronix.de>,
       Steven Rostedt <rostedt@goodmis.org>,
       "gregory.haskins" <gregory.haskins@gmail.com>
In-Reply-To: <1225387034.7803.182.camel@twins>
References: <200810281634.11285.henrik@austad.us>
	 <1225212627.15763.16.camel@lappy.programming.kicks-ass.net>
	 <20081030174925.36023f19jy3o832t@feanor.sssup.it>
	 <1225387034.7803.182.camel@twins>
Content-Type: text/plain
Content-Transfer-Encoding: 7bit
Date: Thu, 30 Oct 2008 18:48:03 +0100
Message-Id: <1225388883.7803.217.camel@twins>
Mime-Version: 1.0
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 1060
Lines: 24

On Thu, 2008-10-30 at 18:17 +0100, Peter Zijlstra wrote:

> Personally I'd like to see the full priority inversion issue solved by
> something like the proxy execution protocol, however the SMP extension
> thereof seems to be a tad expensive - found a book on graph theory, all
> that remains is finding time to read it :-)
> 
> The advantage of proxy execution is that its fully invariant to the
> schedule function and thus even works for proportional fair schedulers
> and any kind of scheduler hierarchy.

Basically the problem that I'm looking at is:

Given a directed acyclic graph G, with entry nodes E (those who don't
have an inbound edge) and exit nodes X (those without an outbound edge)
then given an exit node x of X, split the graph into G1 and G2 so that
G1 contains x and all paths leading to it.


--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/