A distributed interactive application spawns resilient real-time tasks with known resource requirements in response to aperiodic user actions. When running in a shared computing environment that supports neither reservations nor globally-respected priorities, such an application must carefully choose which host runs a task in order to increase the chances that the task's deadline will be met.
A real-time scheduling advisor is a middleware service that the application can use to find the most appropriate host for the task. In addition to recommending a host, the advisor also predicts the running time of the task on that host. The application uses this feedback to modify the task's resource requirements or deadline until a host is found where the task will meet its deadline with sufficiently high probability.
This dissertation recommends basing real-time scheduling advisors on the explicit prediction of resource signals, which are easily measured, time-varying, scalar quantities that are strongly correlated with resource availability. This resource-oriented approach has numerous advantages over the competing application-oriented approach, which I also studied. It scales well, makes decisions based on up-to-date information, can support other forms of adaptation advisors, and can easily leverage advances in statistical signal prediction techniques. However, resource signal predictions exist at considerable remove from predictions of application performance.
To show that this gap can be spanned, this dissertation describes the design, implementation, and performance evaluation of a prototype real-time scheduling advisor that is based on the prediction of host load signals. I have found that, despite its complex properties, which include self-similarity and epochal behavior, host load can be usefully predicted using linear time series models. These models have sufficiently low overhead to be used in practice, and I have developed a toolkit to make it easy to do so. Furthermore, I have devised an algorithm that uses host load predictions to compute a confidence interval for the running time of a task on a particular host. My real-time scheduling advisor uses these confidence intervals to provide useful recommendations to applications. Each layer of this online system has been evaluated using real host load signals and workloads.
Being able to predict the running time of a task is vital to controlling many different adaptation mechanisms in pursuit of goals other than simply those of the real-time scheduling advisor. For this reason, I also expose the running time advisor, the part of my system that computes a confidence interval for the running time of a task.
Cited By
- Hammer H, Yazidi A, Bratterud A, Haugerud H and Feng B (2018). A Queue Model for Reliable Forecasting of Future CPU Consumption, Mobile Networks and Applications, 23:4, (840-853), Online publication date: 1-Aug-2018.
- Amiri M and Mohammad-Khanli L (2017). Survey on prediction models of applications for resources provisioning in cloud, Journal of Network and Computer Applications, 82:C, (93-113), Online publication date: 15-Mar-2017.
- Chrisochoides N, Lee C and Lowekamp B Mesh generation and optimistic computation on the grid Performance analysis and grid computing, (231-250)
- Garlan D, Siewiorek D, Smailagic A and Steenkiste P (2002). Project Aura, IEEE Pervasive Computing, 1:2, (22-31), Online publication date: 1-Apr-2002.
- Dinda P Online prediction of the running time of tasks Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, (336-337)
- Dinda P (2001). Online prediction of the running time of tasks, ACM SIGMETRICS Performance Evaluation Review, 29:1, (336-337), Online publication date: 1-Jun-2001.
Recommendations
Real-time multi-core virtual machine scheduling in xen
EMSOFT '14: Proceedings of the 14th International Conference on Embedded SoftwareRecent years have witnessed two major trends in the development of complex real-time embedded systems. First, to reduce cost and enhance flexibility, multiple systems are sharing common computing platforms via virtualization technology, instead of being ...
Real-time scheduling in cloud-based virtualized software systems
NordiCloud '13: Proceedings of the Second Nordic Symposium on Cloud Computing & Internet TechnologiesThe number of applications that use virtualized cloud-based systems is growing, and one would like to use this kind of systems also for real-time applications with hard deadlines. There is scheduling on two levels in real-time applications executing in ...
A Prediction-Based Real-Time Scheduling Advisor
IPDPS '02: Proceedings of the 16th International Symposium on Parallel and Distributed ProcessingThe Real-time Scheduling Advisor (RTSA) is an entirely user-level system that an application running on a typical shared, unreserved distributed computing environment can turn to for advice on how to schedule its compute-bound soft real-time tasks. ...