Removing Priority Inversion from an Operating System

Steven Sommer
Distributed Computing Group,
Microsoft Research Institute,
Macquarie University
NSW 2109, Australia.
steve@mpce.mq.edu.au

Abstract

In a conventional operating system, priority inversion is a problem for time sensitive applications, for example, video and animation. Priority inversion can also make priority scheduling schemes entirely ineffective. The problem of priority inversion has not been properly addressed outside of the context of real-time systems.

This paper makes two contributions: first it highlights the need to remove priority inversion from most conventional multitasking operating systems; and second it explains and documents the set of changes needed to solve this problem. This paper proposes that specific synchronisation primitives and the system call mechanism support priority inheritance, and presents a general algorithm for doing so. It outlines a partial implementation in the Windows NT operating system.

Conference Home Page