Risks-19.54-7.1

Re: Priority Inversion and early Unix

From: Greg Rose < ggr@qualcomm.com>
Date: Fri, 09 Jan 1998 08:11:19 +1100

"Fred B. Schneider" <fbs@CS.Cornell.EDU>, in "What really happened on Mars Rover Pathfinder (Mike Jones, R-19.49)" R-19.53, mentions Lampson and Redell's 1980 paper.

John Lions' 1977 book "Commentary on UNIX 6th Edition", which contains the source code for this early version of Unix, and an extremely lucid examination of that code, has recently been republished (Peer-to-Peer Communications, ISBN 1-57398-013-7).

Lions (p8-4) comments:

The code to which this refers was of the form:

    oldpri = spl7();
    /* critical region here */
    spl(oldpri);

The processor priorities of the PDP-11 were allowed to dictate this structure to some extent; priority 7 was the highest, and disabled all interrupts. There was no attempt to set the priority to the lowest necessary, as the lack of different levels (0, 4, 5, 6, 7 for device interrupts) meant that 7 was almost always the lowest such level, although in some cases spl6() was used analogously, that being the clock interrupt priority. Most local critical regions, such as device drivers, used the simpler:

    spl5();
    ...
    spl0();

(Here I have used 5 as an example of a known interrupt priority for this device. All "normal" code ran at a processor priority level of 0, with a separate software priority and context switching mechanism.) Clearly Thompson and Ritchie had thought about and found a way to solve the priority inversion problem for the limited case of Unix on a single CPU. Their code predates Lions' commentary by a couple of years at least (1975 or earlier); I don't know exactly which version of Unix introduced that construction.

Greg Rose, QUALCOMM Australia, 6 Kingston Avenue, Mortlake NSW 2137 Australia
http://people.qualcomm.com/ggr/     ggr@qualcomm.com     +61-2-9743 4646