From adrian.lawrence@computing-services.oxford.ac.uk Sun Oct 31 15:49:04 2004 From: A E Lawrence To: occam-com@ukc.ac.uk Date: Wed, 26 Jan 2000 22:20:10 +0000 Subject: [Fwd: [rtl] What kind of sharing is intended/supported for rtfifos?]] Sender: owner-occam-com@ukc.ac.uk Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset=us-ascii MIME-Version: 1.0 X-Mailer: Mozilla 4.7 [en] (X11; U; Linux 2.2.14 i586) Message-ID: <388F731A.23DA4420@oucs.ox.ac.uk> This appeared on the real time linux list. Sorry if you have all seen this stuff. Adrian ---------------------------------------------------------------------------- Kulwinder Atwal wrote: > > I see we all read the Dr. Dobbs article on the Mars Pathfinder. I think > that using semaphores to control resource usage is an incorrect > application of semaphores. I think the proper use of semaphores is for > the synchronization of tasks. > > Maybe a possible solution to resource Priority Inversion is to have a > linked list containing task ids that are requesting the resource. The > list is ordered with the highest priority tasks first, and same priority > tasks on a first come first serve basis. The list is maintained by the > resource driver. > > To me, calling tasks that have critical sections to control resources > suggest an incorrect division of labour between the calling task and the > resource driver. Maybe even the undo absence of a resource driver. By > making the resource driver code re-entrant (multi-threaded) the over > reliance on critical sections can be reduced. For those who might > suggest that writing a multi-threaded resource driver adds too much > overhead I would disagree. As someone who has written hard real time > assembler code for Motorola 68K MCUs, I think that by moving the > critical section codes into a resource driver reduces the overall code > base and promotes code re-use. By making the resource driver fully > re-entrant such that the code does not require a specific sequence of > events to occur (other than for synchronization), because it maintains > instances, reduces the need for critical sections. This may require > more RAM, but the preformance increase and reduction in more expensive > non-volatile program memory (EPROMs) may be worth it. > > This would make resource use independent, priority based, low latency, > and the worst case easier to compute. > > - Cheers, Kal. > > yodaiken@fsmlabs.com wrote: > > > > On Tue, Jan 25, 2000 at 06:14:03PM +0000, Paolo Mantegazza wrote: > > > yodaiken@fsmlabs.com wrote: > > > > > > > I think there are two different, and useful, paths here. The one we > > > > are looking at is to craft the bare essentials of a POSIX 1003.13 > > > > Minimal Realtime Environment + minimal assist > > > > that will facilitate the most efficient realtime programming. The second > > > > path is to facilitate porting of software from operating systems that offer > > > > full POSIX.4. The modular structure of RTLinux makes is possible to do > > > > both at once, but it's important to understand the distinctions. > > > > > > Who proved that smaller is necessarely more efficient? For me the main > > > difference is between real and "toy" applications. > > > > I'm suitably impressed. > > > > > > > > > As an example, I think that the priority inheritance stuff in POSIX.4 is > > > > technical garbage and should be banned from any clean RT system. However, > > > > if I had to port 300K lines of code from Chorus, I would be happy to > > > > have PI mutexes available -- well, I don't know if one could be happy > > > > under such a condition, but ... > > > > > > Priority inheratance is far from garbage. In my experience is one of the > > > simplest way to avoid priority inversion, ask about Mars Pathfinder. I > > > agree it is not needed for "toy" applications. > > > > The Mars Pathfinder example is a excellent illustration of why priority > > inheritance is a terrible idea and why hidden semaphores in black boxes > > are so dangerous. Many people have been mislead by the initial discussion > > of the problem on RISKS, but later discussion cleared things up. > > > > Despite your experience, priority inheritance is a hack to compensate for > > poor design. It has almost impossible to compute but terrible > > worst case behavior, is prone to complex error modes, and encourages sloppy > > design. > > > > 1. Worst case behavior. For priority inheritance to be logically correct > > it must be ``transitive". That is, if T1 blocks on S1 it must pass > > its priority to T2 that holds S1, but if T2 is blocked waiting for S2, then > > T1 must also pass priority to T3 holding S2 and so on. That is, the > > worst case delay for acquiring a semaphore for the highest priority > > task is the cost of descending the longest interleaved chain of semaphores > > and then waiting for each task in this chain to complete its critical > > region. To me, this is unaceptable in real time applications. To > > you, unknown delays may be acceptable for non "toy" > > applications. I hope I don't have to fly in such a non-toy. > > > > 2. Sloppy design. The axiom of a priority driven realtime system is > > A. The highest priority runnable task should run within a small > > fixed time bound. > > The axiom of semaphores is: > > B. All tasks that request a semaphore must wait until the owning > > task releases the semaphore. > > > > Obviously, A and B cannot be true at the same time if any two > > tasks with distinct priorities share a semaphore. > > > > Priority inheritance seeks to take a flawed design and disguise > > the error well enough to limp through most cases. > > I very much dislike this type of dangerous programming. > > > > For these reasons, serious real time programmers have for many > > years used techniques like flip-buffers, lock-free algorithms, > > atomic-update and optimistic atomic update instead of using > > semaphore guarded critical regions. Where they have used semaphore > > guarded critical regions, they have done careful analysis and > > implemented, by hand, a variation of what has recently been called > > priority ceiling. The Mars Pathfinder programmers, being highly > > qualified, made extensive use of such techniques in their code. > > Unfortunately, they had a very low priority task that seemed to be > > so unimportant that its data structures could be allowed to block. > > So they let this task use VxWorks IPC. What they didn't know > > was that VxWorks internally used a semaphore to guard access to > > file structures. So the low priority task started IO, VxWorks > > helpfully took a semaphore on the file structures, the highest > > priority task preempted and then sent some data via IPC to the > > lowest priority and blocked inside VxWorks! This is pathetic. > > By turning on PI, the JPL engineers got VxWorks to survive its own > > ugly design flaw. But this is hardly a validation of such a technique. > > > > Note, semaphores and mutexes can be used safely in realtime systems. > > In particular they are excellent for producer/consumer situation. > > However, semaphore guarded critical regions are exceptionally dangerous > > in realtime programming and by encouraging sloppy use of this > > technique PI has created a serious software reliabilty problem. > > > > Ciao > > Victor > > > > -- > > --------------------------------------------------------- > > Victor Yodaiken > > FSMLabs: www.fsmlabs.com www.rtlinux.com > > FSMLabs is a servicemark and a service of > > VJY Associates L.L.C, New Mexico. > > > > ----- End forwarded message ----- > > > > -- > > --------------------------------------------------------- > > Victor Yodaiken > > FSMLabs: www.fsmlabs.com www.rtlinux.com > > FSMLabs is a servicemark and a service of > > VJY Associates L.L.C, New Mexico. > > > > --- [rtl] --- > > To unsubscribe: > > echo "unsubscribe rtl" | mail majordomo@rtlinux.cs.nmt.edu OR > > echo "unsubscribe rtl " | mail majordomo@rtlinux.cs.nmt.edu > > ---- > > For more information on Real-Time Linux see: > > http://www.rtlinux.org/~rtlinux/ > --- [rtl] --- > To unsubscribe: > echo "unsubscribe rtl" | mail majordomo@rtlinux.cs.nmt.edu OR > echo "unsubscribe rtl " | mail majordomo@rtlinux.cs.nmt.edu > ---- > For more information on Real-Time Linux see: > http://www.rtlinux.org/~rtlinux/ -- Dr A E Lawrence (from home)