Re: Priority Inversion/Inheritance in Linux Kernel

[Rene Herman <rene.herman@xxxxxxxxxxxx>]

On 03-07-08 18:36, Peter Teoh wrote:

> Thank you Roberto for the link:
>
> http://free-electrons.com/doc/embedded_linux_realtime/img25.html
>
> (the full link is here:
> http://free-electrons.com/doc/embedded_linux_realtime.pdf)
>
> Yes, but the link does not explain anything at all.   Or perhaps my
> mind is not able to see the answer.

It's a very nicely concise graphic explanation...

We have 3 processes. One with low, one with high and one with medium 
priority.

The low-prio process runs and acquires a lock. The high-prio process 
preempts it and tries to acquire the same lock. By the nature of lock, 
it goes to sleep waiting for the lock to be released. All fine and well 
upto this point.

But then comes along the medium priority process which again preempts 
the low priority one and keeps it from running to the point where it 
releases the lock. We now have a situation where the medium priority 
process (through its "accomplice", the low-priority process, but that's 
not important) is keeping the high priority process from running: an 
effective inversion of priority between the medium and the high prio 
process has taken place.

This is the problem of priority inversion. It need not always be a huge 
problem. Eventually, assuming the medium-priority process doesn't 
indefinitely starve the low-priority process, the latter should release 
the lock and things will be on their way again. As in the case of the 
classic example you linked to:

> Classic origin of story:
>
> http://lkml.org/lkml/1997/12/24/18

the more direct problem was the watchdog deciding that the high-priority 
process hadn't run for so long that something appeared really wrong and 
resetting the system was in order. They didn't set the priorities or the 
watchdog for nothing though and it's obvious that you don't want this 
scenario to happen.

Priority inheritance (next slide) is a way to deal with the problem. A 
task holding a lock inherits the highest priority of tasks waiting for 
the same lock, so that not any lower priority process (as our medium 
prio process) is going to keep it from releasing it.

HTH,
Rene

--
To unsubscribe from this list: send an email with
"unsubscribe kernelnewbies" to ecartis@xxxxxxxxxxxx
Please read the FAQ at http://kernelnewbies.org/FAQ