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: <20090716212603.GB27757@cs.fsu.edu>
Date:	Thu, 16 Jul 2009 17:26:03 -0400
From:	Ted Baker <baker@...fsu.edu>
To:	Chris Friesen <cfriesen@...tel.com>
Cc:	Noah Watkins <jayhawk@....ucsc.edu>,
	Peter Zijlstra <a.p.zijlstra@...llo.nl>,
	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>,
	"James H. Anderson" <anderson@...unc.edu>,
	Thomas Gleixner <tglx@...utronix.de>,
	Dhaval Giani <dhaval.giani@...il.com>,
	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 Thu, Jul 16, 2009 at 09:17:32AM -0600, Chris Friesen wrote:

> If a high-priority task A makes a syscall that requires a lock currently
> held by a sleeping low-priority task C, and there is a medium priority B
> task that wants to run, the classic scenario for priority inversion has
> been achieved.

I think you don't really mean "sleeping" low-priority task C,
since then the priority inheritance would do no good.  I guess you
mean that C has been/is preempted by B (and for global SMP, there
is some other medicum priority task B' that is eligible to run on
A's processor).  That could be a priority inversion scenario.

BTW, if migration is allowed the probability of this kind of thing
(and hence the payoff for PIP) goes down rapidly with the number
of processors.

> I know of at least one example with millions of lines of code being
> ported to linux from another OS.  The scheduling requirements are fairly
> lax but deadlock due to priority inversion is a highly likely.  They
> compare PI and PP, see that PP requires up-front analysis, so they
> enable PI.
> 
> I suspect there are other similar cases where deadlock is the real
> issue, and hard realtime isn't a concern (but low latency may be
> desirable).  PI is simple to enable and doesn't require any thought on
> the part of the app writer.

I'm confused by your reference to deadlock.  Priority inheritance
does not prevent deadlock, even on a single processor.

> At least for POSIX, both PI and PP mutexes can suspend while the lock is
> held.  From the user's point of view, the only difference between the
> two is that PP bumps the lock holder's priority always, while PI bumps
> the priority only if/when necessary.

You are right that POSIX missed the point of priority ceilings,
by allowing suspension.

However, there is still a difference in context-switching
overhead.  Worst-case, you have twice as many context switches
per critical section with PIP as with PP.

In any case, for a multiprocessor, PP is not enough.  





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