Pfair-Scheduled Real-Time Systems: Extending Theory to Practice

Principal Investigator: James Anderson
Funding Agency: National Science Foundation
Agency Number: CCR-9972211

Abstract
Real-time systems are defined as those systems for which correctness depends not only on the logical properties of the produced results, but also on the temporal properties of those results. The scope of real-time computing is increasing to include "next generation" applications implemented across multiple processors, with complex data-sharing, synchronization, and fault-tolerance requirements. Examples of such applications include automated manufacturing systems, defense systems, avionics and spacecraft control systems, and telepresence systems.

Developing complex systems such as these requires effective techniques for realizing timing constraints in systems of multiple processors. A major step forward in the evolution of such techniques was recently achieved in the work of Baruah and colleagues on Pfair scheduling. Pfair scheduling differs from more conventional real-time scheduling paradigms in that tasks are explicitly required to make progress at steady rates. Executing tasks at steady rates has important consequences. For instance, the Pfair scheduling algorithms proposed by Baruah et al., optimally solve the problem of scheduling periodic tasks on a multiprocessor in polynomial time. This is a problem that was previously viewed by most researchers as being almost undoubtedly NP-hard.

Unfortunately, prior research on Pfair scheduling has left many critical practical problems largely unsolved. For example, mechanisms for supporting tasks with synchronization and data-sharing requirements are completely lacking. Moreover, while theoretical research has shown that Pfair scheduling might be of tremendous practical value, no Pfair-scheduled system has actually ever been implemented, so the true utility of Pfair scheduling is still unproven.

In this project, these shortcomings will be addressed through the development of a Pfair scheduling framework that can be practically applied. There are two major research goals in this project. The first of these goals is to extend the current theory of Pfair scheduling to support functionality needed in actual systems. A variety of extensions will be considered, including support for interprocess communication and synchronization, I/O, and fault tolerance. The second major goal of this project is to develop an implementation of a Pfair-scheduled real-time operating system and to evaluate this system in the context of both synthetic and real-world applications. The applications to be considered include real-time interactive graphics applications taken from ongoing projects at UNC and a real-time system for managing military track data. Target platforms for this work will include stand-alone uniprocessors, workstation-class multiprocessors, and distributed systems.