On Friday 09 November 2007, Bernhard Kuhn wrote: [...] > Can you please give me hint where to find papers on that topic? > A Google research didn't helped very much - i guess i didn't used > the right keywords ... Actually, I do not have any links on my bookmarks on this topic, but, after a very quick search, I guess I found something that you might take a look at: http://www-md.e-technik.uni-rostock.de/ma/gol/rtsys/articulos/YCS159.pdf And talking about articles, there is one on this topic that you probably already know: "Against priority inheritance". It is a very light article... well... against priority inheritance :) > > the main goal of PI and PC protocols is not dead-locks > > avoidance but to prevent priority inversion. > > In respect to prevent priority inversion, i think PI is > superior to PC, but i have recently learned that a dead-lock > avoidance mechanism can be very helpful if it comes to SIL > certification: stating "we follow good programming practices" > is certainly a weaker justification for a high safety integrity > level rather then telling "our OS avoids dead-locks by design". Yes, fully agree with you this. I would like, however, to add that telling "our OS avoids dead-locks by design" is also not enough for SIL certification -- you need to prove this, which might be as difficult as implementing your system without these mechanisms (they tend to add high complexity to the kernel). BTW and just for curiosity: anyone's aware of any application running on top of a Linux kernel that has been SIL (or similar) certified? I guess that you need a fully qualified kernel for SIL, right? > > When you have a some kind of locking mechanism (a mutex, for example) > > that implements the PC protocol, you need to define a ceiling value for > > it. This ceiling value is defined according to an analysis of your > > system and correspond to the highest priority task that can access this > > locking mechanism. My question was: sometimes it may not be easy to > > define this value and, in runtime, the ceiling may be violated by a task > > that accesses this mutex. > > Now i see the problem: i.e.. if the *topmost* priority task *rarely* > accesses a *highly* contended lock, you may decide to lower the > ceiling because otherwise the lock pretty much acts like a giant lock. > (causing in-determinism). However, when lowering the ceiling, then > dead-locks may happen, again, and the only potential advantage of PC > over PI is gone ... > > > Well, but if you dynamically change the ceiling value, then we are > > talking about PI, right? :) > > Not necessarily: lets assume that we stick to the rule that the ceiling > value for a lock should always be equal to the highest priority amongst > all tasks using the lock. Now the situation is that the ceiling value > may change when new high priority tasks are created or old high priority > tasks get killed. If each task provides a list of locks it uses to the > OS, then the OS could easily decide the new ceiling value for each lock > when a tasks is created or killed (from what i understand, this might > be tricky to implement for -rt). Change the ceiling value during runtime > is IMHO no problem: either no task is currently accessing a lock, so the > new task can simple run at it's priority, or the the lock is in use by > another task so it's priority will be temporarily raised to the new > ceiling value. Did i missed anything? You're right, I heard about this variation on the PC protocol. If I remember correctly, it is called "dynamic priority ceiling protocol". To sum up: most of the priority-inversion/dead-lock avoidance mechanisms (we've been discussing PI and PC but probably there are much more...) have advantages and disadventages which are widely known and documented. The conclusion, I guess, is that no "magic" solution exists and the applications system architects will need to choose one or more (or none!) of the available mechanisms. My personal opinion is that, no matter what mechanism you select, if your developing critical software you will _always_ need to perform static schedulability analysis of your system and never rely on PI or PC. Been there... ;) -- Luís Henriques - To unsubscribe from this list: send the line "unsubscribe linux-rt-users" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
