(no subject)

[John Yau]

>Your mechanism is basically "backboost". Its how you get X to keep a
>high piroirity, but quite unpredictable. Giving a boost to a process
>holding a semaphore is an interesting idea, but it doesn't address the
>X problem.

Hmm...I'm actually curious why you called it "backboosting".  In academia
this approach first described in the paper here:

L. Sha, R. Rajkumar, and J. P. Lehoczky. Priority Inheritance Protocols: An
Approach to Real-Time Synchronization. In IEEE Transactions on Computers,
vol. 39, pp. 1175-1185, Sep. 1990.

is referred to as priority inheritance.  Is there significant difference
between your implementation and priority inheritance schemes implemented in
other OSes?  If so, why backboosting?

I was under the impression that pipes and IPC in general are synchronized
using some sort of semaphores/mutex...or does Linux use a different
mechanism for IPC and does away with user space synchronization all together
(e.g. flip-flop buffers with the kernel arbitrating all contention)?  IIRC
processes don't write to X directly and has to send data to X via IPC.  If
some futex derivative is used to synchronize the producers with X, then
making priority inheritable futexes would solve the problem.

>The scheduler in Linus' tree is basically obsolete now, so there isn't
>any point testing it really. Test Con's or my patches, and let us know
>if you're still having problems with sir dumps-a-lot.

Okay enough said, you and Con should get your patches merged into that tree
ASAP if they're ready.


John Yau

Re:

[Nick Piggin]

John Yau wrote:

>>Your mechanism is basically "backboost". Its how you get X to keep a
>>high piroirity, but quite unpredictable. Giving a boost to a process
>>holding a semaphore is an interesting idea, but it doesn't address the
>>X problem.
>>
>
>Hmm...I'm actually curious why you called it "backboosting".  In academia
>this approach first described in the paper here:
>
>L. Sha, R. Rajkumar, and J. P. Lehoczky. Priority Inheritance Protocols: An
>Approach to Real-Time Synchronization. In IEEE Transactions on Computers,
>vol. 39, pp. 1175-1185, Sep. 1990.
>
>is referred to as priority inheritance.  Is there significant difference
>between your implementation and priority inheritance schemes implemented in
>other OSes?  If so, why backboosting?
>

Well I haven't read the paper, but I'm guessing this is semaphore
priority inheritance.

>
>I was under the impression that pipes and IPC in general are synchronized
>using some sort of semaphores/mutex...or does Linux use a different
>mechanism for IPC and does away with user space synchronization all together
>(e.g. flip-flop buffers with the kernel arbitrating all contention)?  IIRC
>processes don't write to X directly and has to send data to X via IPC.  If
>some futex derivative is used to synchronize the producers with X, then
>making priority inheritable futexes would solve the problem.
>

I _think_ communication with X will mostly be done with waitqueues.
Someone has a priority inheritance futex patch around. I'm not sure
that it is such an open and shut case as you think though. Even if you
could use futexes in communication with X.

>
>>The scheduler in Linus' tree is basically obsolete now, so there isn't
>>any point testing it really. Test Con's or my patches, and let us know
>>if you're still having problems with sir dumps-a-lot.
>>
>
>Okay enough said, you and Con should get your patches merged into that tree
>ASAP if they're ready.
>
>

I think Con's is ready (I think mine is as well, but nobody else does!)

Re: Priority Inversion in Scheduling

[John Yau]

>
> Well I haven't read the paper, but I'm guessing this is semaphore
> priority inheritance.
>

Yip...it outlines the basic idea of the priority inheritance where semphores
are the locking mechanism.  However, though it buys you better prioritized
scheduling in certain situation, things can get rather hairy when you have
lots of semaphores nested inside each other.  If you have a cyclic
dependency somewhere in those nested semaphores, you're headed for deadlock
or worse livelock.  The Mars Rover had a classic case of priority inversion
in it's software that was later solved through this approach via an update
after it landed on Mars a while back.

>
> I _think_ communication with X will mostly be done with waitqueues.
> Someone has a priority inheritance futex patch around. I'm not sure
> that it is such an open and shut case as you think though. Even if you
> could use futexes in communication with X.
>

It's not an open and shut case...actually it'd be quite an undertaking I
suspect.  Because a poorly designed and/or poorly implemented scheme can
easily lead to deadlocks and what not, any implementation would need massive
peer review.