Two trends are evident in recent work on real-time systems. First, multiprocessor designs are becoming quite common. This is due both to the advent of reasonably-priced multiprocessor platforms and also to the prevalence of computationally-intensive applications with real-time and quality-of-service (QoS) requirements that have pushed beyond the capabilities of single-processor systems. Second, many applications now exist that require fine-grained adaptivity, i.e., the ability to react to events within short time scales by adjusting task parameters. Examples of such applications include systems that track people and machines, many computer-vision systems, and signal-processing applications such as synthetic aperture imaging.
This proposal is directed at the development of techniques for implementing such systems on tightly-coupled multiprocessors. In practice, the most common approach by far for doing this is by overprovisioning hardware resources, and by validating timing requirements through ad hoc testing. A more formal approach would clearly be desirable. The goal of this project is to fill this need by developing and experimentally evaluating multiprocessor scheduling algorithms that are very flexible in their ability to react to task-set changes, faults, and overload conditions.
The proposed research will build upon recent research conducted at UNC on multiprocessor fair scheduling algorithms for systems with real-time and QoS constraints. Such algorithms are designed to mimic the allocations of an ideal fluid scheduler, which can react instantaneously to task-set changes. In prior work, we have developed fair scheduling algorithms for hard real-time tasks that are provably optimal in their ability to meet task deadlines, and related algorithms that are optimized for scheduling soft real-time tasks that require only bounded deadline tardiness. In addition, we have developed extensions to these algorithms that permit separately-developed applications to be multiplexed on the same system, and that incorporate mechanisms for efficiently supporting intertask communication and synchronization.
In this project, we propose to extend this prior work by developing (i) multiprocessor scheduling algorithms that facilitate adaptation, (ii) kernel services for synchronization and I/O to be used in conjunction with these algorithms, and (iii) mechanisms for determining how and when to adapt. Proposed research on (iii) will extend prior work on using feedback-control mechanisms to induce adaptations in uniprocessor real-time scheduling algorithms.
The algorithms and mechanisms we develop will be implemented within the QNX Neutrino real-time operating system (www.qnx.com). This platform will be evaluated by implementing a spread-spectrum acoustic full-body tracking system for virtual environments (VEs). The resulting system will be able to track a VE user's hands, elbows, feet, and knees to allow interaction with the VE and to enable proper animation of each user's avatar (virtual representation). We expect this experimental effort to be of independent interest, as it will provide researchers interested in tracking applications with new techniques that can be applied to deploy and analyze their systems. More generally, tracking is a good surrogate for the wide range of highly-adaptive computationally-intensive real-time applications that exist.