Publications

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

Scalable Utility Aware Scheduling Heuristics for Real-time Tasks with Stochastic Non-preemptive Execution Intervals

Terry Tidwell, Carter Bass, Eli Lasker, Micah Wylde, Christopher D. Gill, and William D. Smart.
In "Proceedings of the 23rd Euromicro Conference on Real-Time Systems (ECRTS 2011)", pages 238-247, Porto, Portugal, 2011.

Time utility functions can describe the complex timing constraints of real-time and cyber-physical systems. However, utility aware scheduling policy design is an open research problem. Previously we solved a Markov Decision Process formulation of the scheduling problem to derive value-optimal scheduling policies for systems with periodic real-time task sets and stochastic non-preemptive execution intervals. However, the complexity of computing solutions and their policy storage requirements necessitate the exploration of scalable solutions. In this paper we generalize the Utility Accrual Packet Scheduling Algorithm. We compare several heuristics to Markov Decision Process policy evaluation under soft and hard real-time conditions, different load conditions, and different classes of time utility functions. Based on these evaluations we present guidelines for which heuristics are best suited to particular scheduling criteria.

@inproceedings{ecrts11,
  author = {Tidwell, Terry and Bass, Carter and Lasker, Eli and Wylde, Micah and Gill, Christopher D. and Smart, William D.},
  title = {Scalable Utility Aware Scheduling Heuristics for Real-time Tasks with Stochastic Non-preemptive Execution Intervals},
  booktitle = {Proceedings of the 23rd Euromicro Conference on Real-Time Systems ({ECRTS 2011})},
  pages = {238-247},
  address = {Porto, Portugal},
  year = {2011}
}