How do Linux handle process priority inversion? - Linux

This is a discussion on How do Linux handle process priority inversion? - Linux ; Hi, If serveral processes in the Linux are using RT SCHED_RR scheduling mechanism, does the Linux scheduler has the ability to handle the priority inversion? Thanks, Cyril...

+ Reply to Thread
Results 1 to 20 of 20

Thread: How do Linux handle process priority inversion?

  1. How do Linux handle process priority inversion?

    Hi,

    If serveral processes in the Linux are using RT SCHED_RR scheduling
    mechanism, does the Linux scheduler has the ability to handle the
    priority inversion?


    Thanks,
    Cyril


  2. Re: How do Linux handle process priority inversion?

    cyril.li@gmail.com wrote:

    > If serveral processes in the Linux are using RT SCHED_RR scheduling
    > mechanism, does the Linux scheduler has the ability to handle the
    > priority inversion?


    Not sure what you're asking. By definition, the RT (SCHED_FIFO and
    SCHED_RR) schedulers explicitly don't handle priority inversion; that's
    the point of them. A process in SCHED_RR (or SCHED_FIFO) with a higher
    priority will always preempt one of a lower priority (including any
    SCHED_OTHER process). Forever unless the RT priority process blocks on
    I/O.

    GH


  3. Re: How do Linux handle process priority inversion?

    gil_hamilton@hotmail.com wrote:
    > cyril.li@gmail.com wrote:


    >>If serveral processes in the Linux are using RT SCHED_RR scheduling
    >>mechanism, does the Linux scheduler has the ability to handle the
    >>priority inversion?


    > Not sure what you're asking.


    I assume he's asking about things like priority inheritance, priority
    protection, etc.

    To the original poster--mainline vanilla linux does not protect against
    priority inversion, but there are several patch sets out there that add
    this ability.

    Chris

  4. Re: How do Linux handle process priority inversion?

    Chris Friesen wrote:
    > gil_hamilton@hotmail.com wrote:
    >> cyril.li@gmail.com wrote:

    >
    >>> If serveral processes in the Linux are using RT SCHED_RR scheduling
    >>> mechanism, does the Linux scheduler has the ability to handle the
    >>> priority inversion?

    >
    >> Not sure what you're asking.

    >
    > I assume he's asking about things like priority inheritance, priority
    > protection, etc.
    >
    > To the original poster--mainline vanilla linux does not protect against
    > priority inversion, but there are several patch sets out there that add
    > this ability.
    >
    > Chris


    ISTR "priority inversion" means a situation where process A, supposedly
    with strong priority, cant proceed because resource B is locked by
    process C which has weak priority. Some OSes have a way by which C will
    be temporarily boosted to the priority of A, so that A has a chance of
    continuing ASAP. But I could be completely off the mark...

    --
    Michel Bardiaux
    R&D Director
    T +32 [0] 2 790 29 41
    F +32 [0] 2 790 29 02
    E mailto:mbardiaux@mediaxim.be

    Mediaxim NV/SA
    Vorstlaan 191 Boulevard du Souverain
    Brussel 1160 Bruxelles
    http://www.mediaxim.com/

  5. Re: How do Linux handle process priority inversion?

    Michel Bardiaux wrote in part:
    > ISTR "priority inversion" means a situation where process A,
    > supposedly with strong priority, cant proceed because resource B
    > is locked by process C which has weak priority. Some OSes have
    > a way by which C will be temporarily boosted to the priority
    > of A, so that A has a chance of continuing ASAP. But I could be
    > completely off the mark...


    I don't see this as a scheduling problem. It looks far more like a
    locking problem. If it's a kernelspace resource (devices), the OS
    should arbitrate, and in particular not permit any processes to lock.

    If it's a userspace resource (like a semaphore), then the programmer
    should fix her poxy code! Fix the multithreading by adding sleep()
    rather than dropping priority (which cannot be restored my non-root).

    -- Robert





  6. Re: How do Linux handle process priority inversion?

    Robert Redelmeier wrote:

    > If it's a userspace resource (like a semaphore), then the programmer
    > should fix her poxy code! Fix the multithreading by adding sleep()
    > rather than dropping priority (which cannot be restored my non-root).


    That's not really a fix...how long do you sleep for?

    The typical case is something like this:

    1) low-priority task C aquires a resource "Z"
    2) mid-priority task B hogs the cpu but needs no resources
    3) high-priority task A wakes up and tries to aquire resource "Z", but
    is unable to aquire it because C still owns it

    If the OS supports priority inheritance, it will automatically bump up
    the priority of C to the same as A, so that C can do what it needs to
    and give up the resource. At this point C's priority is dropped back
    down to what it was before, and A proceeds to aquire the resource and
    continue.

    As it stands, there is only priority protection, which requires that the
    tasks be run as root, and that any task aquiring resource "Z" first
    boost their priority (to a value equal or greater to the priority of the
    highest-priority task aquiring Z), then aquire the resource, then free
    the resource, then drop their priority back down.

    Alternately, if you can guarantee that all tasks contending on a
    resource share a priority and use the SCHED_RR policy, then you can't
    get priority inversion.


    Chris

  7. Re: How do Linux handle process priority inversion?

    > As it stands, there is only priority protection, which requires that the
    > tasks be run as root, and that any task aquiring resource "Z" first
    > boost their priority (to a value equal or greater to the priority of the
    > highest-priority task aquiring Z), then aquire the resource, then free
    > the resource, then drop their priority back down.


    Seems that Linux kernel doesn't boost RT process's priority, so the
    priority inversion in the Linux is unavoidable, right?

    >
    > Alternately, if you can guarantee that all tasks contending on a
    > resource share a priority and use the SCHED_RR policy, then you can't
    > get priority inversion.
    >
    >
    > Chris



  8. Re: How do Linux handle process priority inversion?

    cyril.li@gmail.com wrote:
    >>As it stands, there is only priority protection, which requires that the
    >>tasks be run as root, and that any task aquiring resource "Z" first
    >>boost their priority (to a value equal or greater to the priority of the
    >>highest-priority task aquiring Z), then aquire the resource, then free
    >>the resource, then drop their priority back down.

    >
    > Seems that Linux kernel doesn't boost RT process's priority, so the
    > priority inversion in the Linux is unavoidable, right?


    The scheduler certainly does run soft-realtime tasks before regular
    tasks, and it runs higher-priority soft-realtime tasks before
    lower-priority ones.

    One problem area is that if you have multiple waiters on a lock, when
    the lock is free it may not be the highest-priority task that aquires
    the lock.

    Chris

  9. Re: How do Linux handle process priority inversion?

    Chris Friesen wrote in part:
    > Robert Redelmeier wrote:
    >> If it's a userspace resource (like a semaphore), then the programmer
    >> should fix her poxy code! Fix the multithreading by adding sleep()
    >> rather than dropping priority (which cannot be restored my non-root).

    >
    > That's not really a fix...how long do you sleep for?


    sleep(0) (or yield()) sould be inserted in a lot of
    multi-threaded code.

    > The typical case is something like this:
    >
    > 1) low-priority task C aquires a resource "Z"
    > 2) mid-priority task B hogs the cpu but needs no resources
    > 3) high-priority task A wakes up and tries to aquire resource "Z", but
    > is unable to aquire it because C still owns it


    What you're talking about here is starvation. Solved long ago.

    Short of moving from one queue to the other, the only thing
    low priority does is shorten the timeslice before pre-emption.
    The process still runs round-robin.

    Ideally, C should be sleeping and woken by a signal from A.
    Sleeping processes get moved toward the head of the queue.

    > As it stands, there is only priority protection, which
    > requires that the tasks be run as root, and that any task
    > aquiring resource "Z" first boost their priority (to a value
    > equal or greater to the priority of the highest-priority
    > task aquiring Z), then aquire the resource, then free the
    > resource, then drop their priority back down.


    Yes, the one-way ratchet down (inability to restore priority)
    is a shortcoming.

    -- Robert


  10. Re: How do Linux handle process priority inversion?

    On 2006-06-29, Robert Redelmeier wrote:

    >> The typical case is something like this:
    >>
    >> 1) low-priority task C aquires a resource "Z"
    >> 2) mid-priority task B hogs the cpu but needs no resources
    >> 3) high-priority task A wakes up and tries to aquire resource "Z", but
    >> is unable to aquire it because C still owns it

    >
    > What you're talking about here is starvation. Solved long ago.


    In the real-time world, that's always referred to as priority
    inversion. It's generally "solved" by something like priority
    inheritence: a task that owns resource X runs at the same
    priority as the highest priority task that's blocked on X (if
    that priority is higher than that of the task that owns X).

    Linux isn't an RTOS, so expecting Linux to handle priority
    inversion in the same manner as an RTOS is a bit delusional.

    --
    Grant Edwards grante Yow! I once decorated my
    at apartment entirely in ten
    visi.com foot salad forks!!

  11. Re: How do Linux handle process priority inversion?

    Robert Redelmeier wrote:
    > Chris Friesen wrote in part:


    > sleep(0) (or yield()) sould be inserted in a lot of
    > multi-threaded code.


    I guess we'll have to disagree on that.

    >>The typical case is something like this:
    >>
    >>1) low-priority task C aquires a resource "Z"
    >>2) mid-priority task B hogs the cpu but needs no resources
    >>3) high-priority task A wakes up and tries to aquire resource "Z", but
    >>is unable to aquire it because C still owns it

    >
    >
    > What you're talking about here is starvation. Solved long ago.


    In this context, it's priority inversion.

    http://www.embedded.com/story/OEG20020321S0023
    http://en.wikipedia.org/wiki/Priority_inversion

    > Short of moving from one queue to the other, the only thing
    > low priority does is shorten the timeslice before pre-emption.
    > The process still runs round-robin.


    You're thinking of tasks using SCHED_OTHER. Consider the case where all
    three are using either of SCHED_FIFO or SCHED_RR. In that case, B will
    run forever.

    Chris

  12. Re: How do Linux handle process priority inversion?

    Chris Friesen wrote in part:
    > You're thinking of tasks using SCHED_OTHER. Consider the
    > case where all three are using either of SCHED_FIFO or
    > SCHED_RR. In that case, B will run forever.


    Sure. But if you put a CPU hog in one of these queues,
    then you presumably want that result. Unix and other
    Linux-like systems won't save you from yourself.

    -- Robert


  13. Re: How do Linux handle process priority inversion?

    Robert Redelmeier wrote:
    > Chris Friesen wrote in part:
    >
    >>You're thinking of tasks using SCHED_OTHER. Consider the
    >>case where all three are using either of SCHED_FIFO or
    >>SCHED_RR. In that case, B will run forever.

    >
    > Sure. But if you put a CPU hog in one of these queues,
    > then you presumably want that result. Unix and other
    > Linux-like systems won't save you from yourself.


    No, what I want is for the system to obey the priorities that I set. In
    this case, A has a higher priority than B, but B is able to keep A from
    running. This is arguably a deficiency.

    As has been mentioned before, there are a number of standard ways of
    dealing with the issue. Mainline linux doesn't support any of them, but
    there are patches around to add them.

    Chris

  14. Re: How do Linux handle process priority inversion?

    Chris Friesen wrote in part:
    > Robert Redelmeier wrote:
    >> Chris Friesen wrote in part:
    >>>You're thinking of tasks using SCHED_OTHER. Consider the
    >>>case where all three are using either of SCHED_FIFO or
    >>>SCHED_RR. In that case, B will run forever.

    >>
    >> Sure. But if you put a CPU hog in one of these queues,
    >> then you presumably want that result. Unix and other
    >> Linux-like systems won't save you from yourself.

    >
    > No, what I want is for the system to obey the priorities that
    > I set. In this case, A has a higher priority than B, but B is
    > able to keep A from running. This is arguably a deficiency.


    No, it is a _feature_ of RR & FIFO defined by POSIX, AFAIK.
    Priority only matters when the scheduler runs and is empowered
    to switch tasks. RR & FIFO are limited.

    > As has been mentioned before, there are a number of
    > standard ways of dealing with the issue. Mainline linux
    > doesn't support any of them, but there are patches around
    > to add them.


    Certainly. But they arguably break RR & FIFO which are designed
    for maximum compute thruput by minimizing task switching.
    Certainly at a cost in latency for some processes. That's why
    SCHED_OTHER is so highly recommended. RR & FIFO are meant for
    independant tasks.

    -- Robert


  15. Re: How do Linux handle process priority inversion?

    Robert Redelmeier wrote:
    > Chris Friesen wrote in part:


    >>No, what I want is for the system to obey the priorities that
    >>I set. In this case, A has a higher priority than B, but B is
    >>able to keep A from running. This is arguably a deficiency.


    > No, it is a _feature_ of RR & FIFO defined by POSIX, AFAIK.
    > Priority only matters when the scheduler runs and is empowered
    > to switch tasks. RR & FIFO are limited.


    Both RR and FIFO still use the scheduler and thus priorities still apply.

    Consider the following, where all tasks are either RR or FIFO.

    If I have task B that is a cpu hog, and something happens to wake up
    task A (which is higher priority than B), then task A should run. Do we
    agree so far?

    Now, we introduce the inversion. Suppose there is a task C at lower
    priority than B, but which holds a resource desired by A.

    The standard behaviour is that B will continue to run and A will be
    blocked. Arguably this is the standard POSIX behaviour because it's the
    simplest to code and likely the fastest at runtime.

    The behaviour with priority inheritance is that C's priority gets
    temporarily boosted to that of A, C does its thing then gives up the
    lock, A takes the lock, and A runs.

    POSIX allows for this (on mutexes, anyway) by setting
    PTHREAD_PRIO_INHERIT. It's optional though, because its a lot more
    complex to implement and is going to be slower at runtime when used.

    That said, I'd argue that the prio inheritance case is closer to the
    "spirit" of what I requested when setting the priorities. Putting aside
    POSIX for a second, if I indicate that "A" has the highest priority in
    the system, it would be logical for the system to do whatever is
    necessary to ensure that A runs whenever it wants.

    On the other hand, if you can design the system such that priority
    inversion is impossible, you're going to reap performance benefits.

    Chris

  16. Re: How do Linux handle process priority inversion?

    Chris Friesen wrote in part:
    > Both RR and FIFO still use the scheduler and thus priorities
    > still apply.


    Certainly. But _when_ they apply is the question.
    The scheduling _policies_ are very different, including
    run-to-completion[or block] (FIFO).


    > Consider the following, where all tasks are either RR
    > or FIFO.


    > If I have task B that is a cpu hog, and something happens
    > to wake up task A (which is higher priority than B), then
    > task A should run. Do we agree so far?


    No, we do not agree. Task A doesn't "wake up" under RR or FIFO.
    If it unblocks, then it waits for RR or FIFO to time-out/complete
    (respectively) Task B and the scheduler to run again. These are
    not pre-emptive scheduling policies and certainly can block
    the system. That's why they require root to set.

    You may find more at:
    http://www.opengroup.org/onlinepubs/...ag_03_02_08_16

    Of course some people don't like these primative policies,
    however POSIX they may be. So various patches have been
    written (SCHED_SOFTRR).

    These scheduling policies have been designed for stochastic system
    throughput under relatively fixed conditions, like on a realtime
    system. Co-operative multitasking techniques are mandatory.

    -- Robert


  17. Re: How do Linux handle process priority inversion?

    Robert Redelmeier wrote:
    > Chris Friesen wrote in part:


    >>If I have task B that is a cpu hog, and something happens
    >>to wake up task A (which is higher priority than B), then
    >>task A should run. Do we agree so far?

    >
    >
    > No, we do not agree. Task A doesn't "wake up" under RR or FIFO.
    > If it unblocks, then it waits for RR or FIFO to time-out/complete
    > (respectively) Task B and the scheduler to run again. These are
    > not pre-emptive scheduling policies and certainly can block
    > the system. That's why they require root to set.
    >
    > You may find more at:
    > http://www.opengroup.org/onlinepubs/...ag_03_02_08_16


    I think you just proved my point. From that document:

    "Typically, the scheduling code is executed whenever an event occurs
    that might alter the process to be executed next."

    "Thus, when a process becomes unblocked, it will preempt a running
    process of lower priority without otherwise altering the ready list."

    "The system scheduler always dispatches a process that has the highest
    (generally the most time-critical) priority among all runnable processes
    in the system."

    Taken together, it's pretty clear that when A unblocks, it is perfectly
    valid to run the scheduler, preempt B, and start running A.


    Chris

  18. Re: How do Linux handle process priority inversion?

    Chris Friesen wrote:

    > Robert Redelmeier wrote:
    >> Chris Friesen wrote in part:

    >
    >>>If I have task B that is a cpu hog, and something happens
    >>>to wake up task A (which is higher priority than B), then
    >>>task A should run. Do we agree so far?

    >>
    >>
    >> No, we do not agree. Task A doesn't "wake up" under RR or FIFO.
    >> If it unblocks, then it waits for RR or FIFO to time-out/complete
    >> (respectively) Task B and the scheduler to run again. These are
    >> not pre-emptive scheduling policies and certainly can block
    >> the system. That's why they require root to set.
    >>
    >> You may find more at:
    >>

    http://www.opengroup.org/onlinepubs/...ag_03_02_08_16
    >
    > I think you just proved my point. From that document:
    >
    > "Typically, the scheduling code is executed whenever an event occurs
    > that might alter the process to be executed next."
    >
    > "Thus, when a process becomes unblocked, it will preempt a running
    > process of lower priority without otherwise altering the ready list."
    >
    > "The system scheduler always dispatches a process that has the highest
    > (generally the most time-critical) priority among all runnable processes
    > in the system."
    >
    > Taken together, it's pretty clear that when A unblocks, it is perfectly
    > valid to run the scheduler, preempt B, and start running A.
    >
    >
    > Chris

    Something for all of us to keep in mind, just because an event happens that
    unblocks a process does not mean that either the scheduler, or more
    importantly the switcher, will run. In general these only get run when a
    timeslice runs out or a process blocks.
    --
    JosephKK
    Gegen dummheit kampfen die Gotter Selbst, vergebens.**
    --Schiller

  19. Re: How do Linux handle process priority inversion?

    joseph2k wrote:

    > Something for all of us to keep in mind, just because an event happens that
    > unblocks a process does not mean that either the scheduler, or more
    > importantly the switcher, will run. In general these only get run when a
    > timeslice runs out or a process blocks.


    That is implementation-specific, and Linux behaves differently than you
    explain above.

    Pretty much any event in the kernel that could unblock a process or
    trigger priorities to change will set a flag that indicates that the
    scheduler should run. That flag is checked after every syscall and on
    every interrupt.

    When the scheduler runs, it picks the highest-priority task on that
    cpu's runqueue. If the task is already running, then it doesn't need to
    switch to another task, which simplifies things somewhat.

    Search the kernel code for TIF_NEED_RESCHED if you're interested in more
    detail.

    Chris

  20. Re: How do Linux handle process priority inversion?

    Chris Friesen wrote in part:
    > Taken together, it's pretty clear that when A unblocks,
    > it is perfectly valid to run the scheduler, preempt B,
    > and start running A.


    Is this what you're arguing? Current Linux already does this:

    http://josh.trancesoftware.com/linux..._scheduler.pdf

    under 5.8.2 and 5.8.3 for FIFO and RR tasks.

    -- Robert



+ Reply to Thread