Universität Bielefeld - Technische Fakultät
 AG Rechnernetze und Verteilte Systeme 
 Arbeitsgruppe von Prof. Peter B. Ladkin, Ph.D. 
Zurück   Weiter
  From the Risk Forum 19.53  

Risks-19.53-9.2

Re: What really happened on Mars Rover Pathfinder (Mike Jones, R-19.49)

From: Fred B. Schneider < fbs@CS.Cornell.EDU>
Date: Mon, 5 Jan 1998 18:29:27 -0500 (EST)

Readers of RISKS could get the wrong impression about who did what and when from what David Wilner is reported to have said in Mike Jones' item on the Mars Pathfinder mission in RISKS-19.49. This note attempts to provide some missing information.

Jones' Mars Pathfinder article ends with:

THE IMPORTANCE OF GOOD THEORY/ALGORITHMS

David [Wilner] also said that some of the real heroes of the situation were some people from CMU who had published a paper he'd heard presented many years ago who first identified the priority inversion problem and proposed the solution. ...

For the record, the paper was:

L. Sha, R. Rajkumar, and J. P. Lehoczky. Priority Inheritance Protocols: An Approach to Real-Time Synchronization. In IEEE Transactions on Computers, vol. 39, pp. 1175-1185, Sep. 1990.

Actually, a "priority inheritance" protocol can be found in

B. W. Lampson and D. D. Redell.
Experience with processes and monitors in Mesa.
Communications of the ACM,
vol. 23, no. 2, pp. 105--117, February 1980.

which is a reprint of a paper that appeared in Dec 1979 (7th ACM Symposium on Operating System Principles). Below is the relevant excerpt; it is almost - but not exactly - what Sha et al. investigate.

4.3 Priorities

In some applications it is desirable to use a priority scheduling discipline for allocating the processor(s) to processes which are not waiting. Unless care is taken, the ordering implied by the assignment of priorities can be subverted by monitors. Suppose there are three priority levels (3 highest, 1 lowest), and three processes P_1, P_2, and P_3, one running at each level. Let P_1 and P_3 communicate using a monitor M. Now consider the following sequence of events:

P_1 enters M
P_1 is preempted by P_2
P_2 is preempted by P_3
P_3 tries to enter the monitor, and waits for the lock
P_2 runs again, and can effectively prevent P_3 from
running, contrary to the purpose of the priorities

A simple way to avoid this situation is to associate with each monitor the priority of the highest-priority process which ever enters that monitor. Then whenever a process enters a monitor, its priority is temporarily increased to the monitor's priority...

So, it would be incorrect to credit Sha et al. for first *identifying* the problem or for first *proposing a protocol* to solve it. Lampson & Redell do not give any quantitative analysis of their prio scheme, though.

The development of this thread of research in real-time scheduling is accurately described in section 5 of Audsley et al., as noted by Ken Tindell.

A parable comes to mind. School children in the U.S. are taught that "Columbus discovered America". Ultimately they learn that Columbus was preceded by, among others, the Vikings. So why aren't they taught that "The vikings discovered America"? Perhaps it is because when Columbus discovered America, it stayed discovered.

 Copyright © 1998 Peter B. Ladkin, 05. September 1998 
Letzte Änderung am 11.12.2001
von Mirco Hilbert