Notes on the history of the Priority Inversion problem

Since I sent my original "What really happened on Mars?" message, a number of people replied saying that the priority inversion problem and solutions to it were known much earlier than Sha et al.'s 1990 article. Excerpts from representative responses include:

Joe Gwinn, a friend from Raytheon wrote:

You know, I must rain on this parade a bit -- priority inversion was well known in the embedded realtime community when I arrived in the mid 1970s, but it had neither a name nor a literature back then. It was part of the unwritten lore; some knew it, some didn't, so people tended to rediscover it the hard way.

Don Gillies and others have pointed out that the problem and a solution were described in the paper:

Butler W. Lampson and David D. Redell. Experience with processes and monitors in Mesa. Communications of the ACM, 23(2):105-117, February 1980.

Doug Jensen said that the problem and solution were mentioned in the Intel iRMX (an OS for the 8086) manuals.

Jim Gray wrote that:

The idea of a process inheriting the max priority of members of the wait list was implemented in the Tandem system in 1983 as a solution to the problem (and we even documented it in the literature). See Andrea Borr's papers on the Tandem Disk Process in VLDB proceedings and later papers by me and others. By that time we had learned the term priority inversion and used it to describe the problem and the solution.

My summary...

It's not surprising that a number of people would have discovered priority inversion and invented priority independence independently. In fact, Sha, et al. seem to be the last people to have claimed to have independently invented it. For whatever reason though, theirs seems to have been the publication that people think of as having made the concept widely known. Which may not be "fair". But it seems to be true. I'm sure that David Wilner, for one, appreciates their efforts!

As reporting (which it was), I believe that my message was accurate. I reported that David Wilner first heard about priority inversion from Sha et al. and that he thanked them during the talk. Which is true. Nonetheless, since people might infer that they were the original inventors of the concept from my message, I felt that this historical note was in order.

-- Mike Jones


Related Links:

Last modified December 16, 1997.