[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Fwd: [rtl] What kind of sharing is intended/supported for rtfifos?]]
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@xxxxxxxxxxx wrote:
> >
> > On Tue, Jan 25, 2000 at 06:14:03PM +0000, Paolo Mantegazza wrote:
> > > yodaiken@xxxxxxxxxxx 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@xxxxxxxxxxxxxxxxxx OR
> > echo "unsubscribe rtl <Your_email>" | mail majordomo@xxxxxxxxxxxxxxxxxx
> > ----
> > For more information on Real-Time Linux see:
> > http://www.rtlinux.org/~rtlinux/
> --- [rtl] ---
> To unsubscribe:
> echo "unsubscribe rtl" | mail majordomo@xxxxxxxxxxxxxxxxxx OR
> echo "unsubscribe rtl <Your_email>" | mail majordomo@xxxxxxxxxxxxxxxxxx
> ----
> For more information on Real-Time Linux see:
> http://www.rtlinux.org/~rtlinux/
--
Dr A E Lawrence (from home)