Sort by: [year] [type] [author]

Scalable Scheduling Policy Design for Open Soft Real-Time Systems

Robert Glaubius, Terry Tidwell, Brandon Sidoti, David Pilla, Justin Meden, Christopher D. Gill, and William D. Smart.
In "Proceedings of the 16th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2010)", pages 237-246, Stockholm, Sweden, 2010.

This paper won the Best Student Paper award at RTAS 2010.

Open soft real-time systems, such as mobile robots, must respond adaptively to varying operating conditions, while balancing the need to perform multiple mission speci?c tasks against the requirement that those tasks complete in a timely manner. Setting and enforcing a utilization target for shared resources is a key mechanism for achieving this behavior. However, because of the uncertainty and non-preemptability of some tasks, key assumptions of classical scheduling approaches do not hold. In previous work we presented foundational methods for generating task scheduling policies to enforce proportional resource utilization for open soft real-time systems with these properties. However, these methods scale exponentially in the number of tasks, limiting their practical applicability.

In this paper, we present a novel parameterized scheduling policy that scales our technique to a much wider range of systems. These policies can represent geometric features of the scheduling policies produced by our earlier methods, but only require a number of parameters that is quadratic in the number of tasks. We provide empirical evidence that the best of these policies are competitive with exact solution methods in small problems, and signi?cantly outperform heuristic methods in larger ones.

  author = {Glaubius, Robert and Tidwell, Terry and Sidoti, Brandon and Pilla, David and Meden, Justin and Gill, Christopher D. and Smart, William D.},
  title = {Scalable Scheduling Policy Design for Open Soft Real-Time Systems},
  booktitle = {Proceedings of the 16th IEEE Real-Time and Embedded Technology and Applications Symposium ({RTAS} 2010)},
  pages = {237--246},
  address = {Stockholm, Sweden},
  year = {2010}