Feedback Control Real-Time Scheduling

Lu, Chenyang, Department of Computer Science, University of Virginia
Knight, John, Department of Computer Science, University of Virginia

We develop Feedback Control real-time Scheduling (FCS) as a unified framework to provide Quality of Service (QoS) guarantees in unpredictable environments (such as ebusiness servers on the Internet). FCS includes four major components. First, novel scheduling architectures provide performance control to a new category of QoS critical systems that cannot be addressed by traditional open loop scheduling paradigms. Second, we derive dynamic models for computing systems for the purpose of performance control. These models provide a theoretical foundation for adaptive performance control. Third, we apply established control methodology to design scheduling algorithms with proven performance guarantees, which is in contrast with existing heuristics-based solutions relying on laborious design/tuning/testing iterations. Fourth, a set of controlbased performance specifications characterizes the efficiency, accuracy, and robustness of QoS guarantees.
The generality and strength of FCS are demonstrated by its instantiations in three important applications with significantly different characteristics. First, we develop realtime CPU scheduling algorithms that guarantees low deadline miss ratios in systems where task execution times may deviate from estimations at run-time. We solve the saturation problems of real-time CPU scheduling systems with a novel integrated control structure. Second, we develop an adaptive web server architecture to provide relative and absolute delay guarantees to different service classes with unpredictable workloads. The adaptive architecture has been implemented by modifying an Apache web server. Evaluation experiments on a testbed of networked Linux PC's demonstrate that our server provides robust relative/absolute delay guarantees despite of instantaneous changes in the user population. Third, we develop a data migration executor for networked storage systems that migrate data on-line while guaranteeing specified I/O throughput of concurrent applications.

PHD (Doctor of Philosophy)
All rights reserved (no additional license for public reuse)
Issued Date: