Theory
and Practice of
Feedback Control Real-Time Scheduling
|
Ronghua Zhang |
|
Supported
in part by NSF grants CCR-9901706,
CCR-0098269, and EIA-9900895.
Project Description
The Feedback
Control Real-Time Scheduling project is motivated by the observation that many
existing software adaptation techniques are based on ad hoc approaches
and rely on laborious
design/tuning/testing iterations. While the design methodology for
automatic adaptive systems has been developed in feedback control theory, the
modeling, analysis and implementation of adaptive real-time systems lead to
significant research challenges to both software and control theory research.
Our research aims to establish FCS, a novel and unified framework for
designing adaptive resource management architectures and algorithms to satisfy
the performance specifications based on feedback control theory. Our FCS framework includes
adaptive resource management architectures composed of continuous performance
feedback control loops, performance specifications to characterize the
efficiency and accuracy of system adaptation in enforcing the desired QoS,
practical and novel modeling techniques tailored for computer systems, and a
feedback control theory based design methodology for resource management
algorithms to satisfy system performance specifications. Our framework enables
system designers to systematically design adaptive real-time systems with
established analytical methods to achieve specified QoS guarantees in
unpredictable environments. Furthermore, our framework
also include provable robustness of QoS guarantees in face of workload and
system variations and practical parameter tuning methods for algorithm
parameters.
In the area of real-time CPU
scheduling, we developed a set of real-time CPU scheduling algorithms that
guarantees low deadline miss ratio and high CPU utilization by adaptively
adjusting task QoS levels and CPU requirements.
Simulation experiments demonstrate that our FCS algorithms provide robust
steady and transient state desired performance guarantees even when the task
execution time varied considerably from the estimation.
We
developed an adaptive web server architecture to provide relative, absolute and
hybrid service delay guarantees for different service classes on web servers.
Our architecture features feedback control loops that enforce service delay
guarantees via dynamic TCP connection scheduling and server process allocation.
Our new server is implemented by modifying the Apache
server code with a new control library on a Linux platform. A system
identification software tool was developed to estimate the parameters of the
dynamic model of a Web server based on system profiling data.
Publications
·
Lu, J.
A. Stankovic, G. Tao, and S. H. Son. “Feedback Control Real-Time
Scheduling: Framework, Modeling, and Algorithms,” Journal of Real-Time
Systems, Special Issue on Control-Theoretical Approaches to Real-Time
Computing, to appear.
·
C.
Lu, T. F. Abdelzaher, J. A. Stankovic, and S. H. Son. “A Feedback Control
Architecture and Design Methodology for Service Delay Guarantees in Web Servers,”
University of Virginia Tech Report CS-2001-06. (Submitted for journal publication)
·
J. A. Stankovic, T. He, T. F. Abdelzaher, M. Marley, G.
Tao, S. H. Son, and C. Lu, ``Feedback Control
Scheduling in Distributed Systems,'' IEEE Real-Time Systems Symposium,
London, UK, December 2001.
· C. Lu, T. F. Abdelzaher, J. A. Stankovic, and S. H. Son, “A Feedback Control Approach for Guaranteeing Relative Delays in Web Servers,” IEEE Real-Time Technology and Applications Symposium, Taipei, Taiwan, June 2001.
· T. F. Abdelzaher and C. Lu, “Schedulability Analysis and Utilization Bounds for Highly Scalable Real-Time Services,” IEEE Real-Time Technology and Applications Symposium, Taipei, Taiwan, June 2001.
· C. Lu, J. A. Stankovic, T.
F. Abdelzaher, G. Tao, S. H. Son, and M. Marley, "Performance
Specifications and Metrics for Adaptive Real-Time Systems," 21th
IEEE Real-Time Systems Symposium, Orlando, FL, December 2000.
· T. F. Abdelzaher and C. Lu, "Modeling and Performance
Control of Internet Servers," Invited Paper, 39th IEEE Conference
on Decision and Control, Sydney, Australia, December 2000.
· C. Lu, J. A. Stankovic, G.
Tao, and S. H. Son, "Design
and Evaluation of a Feedback Control EDF Scheduling Algorithm," 20th
IEEE Real-Time Systems Symposium, Phoenix, AZ, December 1999.
· J. A. Stankovic, C. Lu, S.
H. Son, and G. Tao, "The
Case for Feedback Control Real-Time Scheduling," 11th EuroMicro
Conference on Real-Time Systems, York, UK, June 1999.
PhD Thesis
·
C.
Lu, “Feedback
Control Real-Time Scheduling,” PhD Thesis, University of Virginia,
May 2001.
Last modified: 8/20/01
11:43 PM by Chenyang Lu