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

[Ted Baker <baker@cs.fsu.edu>]

On Mon, Jul 13, 2009 at 03:45:11PM -0600, Chris Friesen wrote:

> Given that the semantics of POSIX PI locking assumes certain scheduler
> behaviours, is it actually abstraction inversion to have that same
> dependency expressed in the kernel code that implements it?
...> 
> The whole point of mutexes (and semaphores) within the linux kernel is
> that it is possible to block while holding them.  I suspect you're going
> to find it fairly difficult to convince people to spinlocks just to make
> it possible to provide latency guarantees.

The abstraction inversion is when the kernel uses (internally)
something as complex as a POSIX PI mutex.  So, I'm not arguing
that the kernel does not need internal mutexes/semaphores that
can be held while a task is suspended/blocked.  I'm just arguing
that those internal mutexes/semaphores should not be PI ones.

> ...  the selling point for PI vs PP is that under PIP the
> priority of the lock holder is automatically boosted only if
> necessary, and only as high as necessary.

The putative benefit of this is disputed, as shown by Jim and
Bjorn's work with LITMUS-RT and others.  For difference to be
noted, there must be a lot of contention, and long critical
sections.  The benefit of less frequent priority boosting and
lower priorities can be balanced by more increased worst-case
number of context switches.

> On the other hand, PP requires code analysis to properly set the
> ceilings for each individual mutex.

Indeed, this is difficult, but no more difficult than estimating
worst-case blocking times, which requires more extensive code
analysis and requires consideration of more cases with PI than PP.

If determining the exact ceiling is too difficult.  one can simply
set the ceiling to the maximum priority used by the application.

Again, I don't think that either PP or PI is appropriate for use
in a (SMP) kernel. For non-blocking locks, the current
no-preeemption spinlock mechanism works.  For higher-level
(blocking) locks, I'm attracted to Jim Anderson's model of
non-preemptable critical sections, combined with FIFO queue
service.

> Certainly if you block waiting for I/O while holding a lock then it
> impacts the ability to provide latency guarantees for others waiting for
> that lock.  But this has nothing to do with PI vs PP or spinlocks, and
> everything to do with how the lock is actually used.

My only point there was with respect to application-level use of
POSIX mutexes, that if an application needs to suspend while
holding a mutex (e.g., for I/O) then the application will have
potentially unbounded priority inversion, and so is losing the
benefit from priority inheritance.  So, if the only benefit of
PRIO_INHERIT over PRIO_PROTECT is being able to suspend while
holding a lock, there is no real benefit.  

Ted