|  | |||||||||
Removing Priority Inversion from an Operating System
Steven Sommer
Distributed Computing Group,
Microsoft Institute Research,
P.O. Box 91, North Ryde,
N.S.W. 2113
Australia
Department of Computing,
Macquarie University,
N.S.W. 2109
Australia
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.
Keywords Priority inversion, priority inheritance, operating systems, scheduling, synchronisation, real-time.
1 Introduction
The problem of priority inversion has been identified and addressed in the area of real-time system scheduling and specific solutions have been found [1, 2, 7, 9, 11, 12]. However priority inversion is also frequently experienced in conventional operating systems. When these specific solutions were applied to conventional operating systems, problems arose that necessitated a more complex solution. This paper motivates the removal of priority inversion in such systems and describes how this can be achieved.
This research forms part of the DREAMS (Distributed and Real-Time Extensions with Ap-
Proceedings of the 19
th
Australasian Computer
Science Conference, Melbourne, Australia, January
31?February 2 1996.
plication to Multimedia Systems) project. The aim of this project is to determine a set of extensions to a conventional network operating system to allow it to support local and distributed real-time applications. The extensions should have a minimal impact on the conventional functioning of the operating system and on the programming paradigm used. These extensions are being implemented within Windows NT? [4] in order to demonstrate their viability. It has been found that a number of the enhancements required to allow an operating system to reliably schedule real-time tasks also improve the operating system?s handling of conventional tasks. This paper describes one such enhancement: the removal of priority inversion.
The second section of this paper explains a number of relevant terms and describes the general problem of priority inversion and the general solution of priority inheritance used in realtime systems. Section three describes the types of problems that priority inversion can cause in an operating system and that warrant correction. The fourth section describes the areas of a conventional operating system that need to be modified to support priority inheritance, and extends the priority inheritance protocol to align with these systems. Section five summarises the results of our partial implementation of priority inheritance within Windows NT.
The reader is assumed to have a general understanding of operating system concepts such as threads and scheduling, and synchronisation constructs such as critical sections, semaphores, and mutexes (an ?owned? binary semaphore). A good explanation of these concepts can be found in [10].
2 Background
A real-time task is a task for which the correctness is based not only on the task?s result but also on the time at which that result occurs. A