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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.