Thank you Rene. On Fri, Jul 4, 2008 at 2:12 AM, Rene Herman <rene.herman@xxxxxxxxxxxx> wrote: > 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: > The case of medium prio forever hijacking the high prio process happened is also because (i guessed) that there is no sorting of priority before selecting the task to be executed. But then sorting operation is never O(1), and so to achieve O(1) scheduling, u just need to have some simpler heuristics. >> 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. > I see....eh...or I don't see......the original problem was that the highest prio cannot acquire the lock, even though it has the highest prio. So your statement is that any NEW task will always acquire the same prio as the current highest prio....but does that necessarily guarantee acquisition of locks? (ie, ANY CURRENT OR NEW TASK not holding to the lock will have EQUAL chances of acuiring the locks right? - so long as it is higher prio than the previous owner holding the lock the scheduler will just schedule it).....are my statement so far correct? another question arising is if all process always acquire a higher or equal prio, then in no time it will reach infinity right? Very confused :-). BTW.....inherent in the current design is that any tasks holding to a lock WILL NOT HAVE ITS priority change dynamically right? (once prio assigned at task creation it will not change?) thanks. > HTH, > Rene > -- Regards, Peter Teoh -- To unsubscribe from this list: send an email with "unsubscribe kernelnewbies" to ecartis@xxxxxxxxxxxx Please read the FAQ at http://kernelnewbies.org/FAQ
