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