In the paper:
Leslie Lamport: What It Means for a Concurrent Program to Satisfy a Specification: Why No One Has Specified Priority; ACM Symp Principles of Programming Languages, (POPL-12):78-83, 1985.
Lamport shows that "...existing specifications that claim to describe prioirty are either vacuous or else too restrictive to be implemented...", and in the conclusion says
Waiting is an implementation-level concept that I feel cannot be expressed in a general way.
Yet, we have vigorous conversations about priority inversion in real operating systems. Take, for example, this argument I found between Victor Yodaiken and Doug Locke about whether it is a good or bad idea to implement priority inheritance in a real-time Linux scheduler. Yodaiken cites the classic Lampson and Redell paper about monitors (CACM, 23(2):105-117, 1980) to describe what priority inversion is.
I thought I had a concrete but informal notion of priority inversion and priority inheritance, and have been teaching these concepts to unwitting undergraduates for over a decade. Should I stop trying to teach about priority since the concept is apparently vacuous?
