linux-kernel - Re: 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: <1243710957.6645.157.camel@laptop>
Date:	Sat, 30 May 2009 21:15:57 +0200
From:	Peter Zijlstra <peterz@...radead.org>
To:	Henrik Austad <henrik@...tad.us>
Cc:	GeunSik Lim <leemgs1@...il.com>, finarfin@...amos.org,
	linux-kernel@...r.kernel.org
Subject: Re: SCHED_EDF infos

On Fri, 2009-05-08 at 11:10 +0200, Henrik Austad wrote:
> > In fact, I also  don't have perfect know how to solve PI in Multicore.
> > [...]
> > > deadline inversion will be a problem, in fact, whatever you chooose to 
> > > be the 'key' for picking tasks (priority, niceness, deadlines, wind 
> > > direction, <whatever>), you can pretty much take that and add a 
> > > -inversion after it. :)
> 
> No, PI is going to be deadly no matter what you do.

Right, we would need to extend the Priority Inheritance Protocol to
include everything the regular scheduling functions operate on.

That is, we can reduce scheduling to a single order operator that orders
all the available tasks, such that t_n < t_n+1.

For pure EDF that would be a comparison on deadlines (and available
bandwidth), for FIFO on static priority and for CFS something based on
the virtual runtimes of the involved tasks. For the combined set of
these scheduling classes the comparator uses the class hierarchy to
order between them.

Lets call the full set of data that is used to determine this order a
task's key.

If we then substitute this key for the static priority of the classic
PIP and use this generic comparison operator, it can be extended to
cover arbitrary complex scheduling functions.

This is a bit like the Proxy Execution Protocol, where we leave the
blocked task in the runqueue, but run another task in its stead. The key
point is that it donates the full task state as relevant to the
scheduling function, or even more directly, it uses the scheduler
itself, to solve the Priority Inversion.

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