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

Scheduling as a Learned Art

Christopher D. Gill, William D. Smart, Terry Tidwell, and Robert Glaubius.
In "Proceedings of the 4th International Workshop on Operating Systems Platforms for Embedded Real-Time Applications (OSPERT 2008)", pages 53-62, July 2008.

Scheduling the execution of multiple concurrent tasks on shared resources such as CPUs and network links is essential to ensuring the reliable and correct operation of real-time systems. For closed hard real-time systems in which task sets and the dependencies among them are know a priori, existing real-time scheduling techniques can offer rigorous timing and preemption guarantees. However, for open soft-real-time systems in which task sets and dependencies may vary or may not be know a priori and for which we would still like assurance of real-time behavior, new scheduling techniques are needed.

Our recent work has shown that modeling non-preemptive resource sharing between threads as a Markov Decision Process (MDP) produces (1) an analyzable utilization state space, and (2) a representation of a scheduling decision policy based on the MDP, even when task execution times are loosened from exact values to known distributions within which execution times may vary. However, if dependencies among tasks, or the distributions of their execution times are not known, then how to obtain the appropriate MDP remains an open problem.

In this paper, we posit that this problem can be addressed by applying focused reinforcement learning techniques. In doing so, our goal is to overcome a lack of knowledge about system tasks by observing their states (e.g., task resource utilizations) and their actions(e.g., which tasks are scheduled), and comparing the transitions among states under different actions to obtain models of system behavior through which to analyze and enforce desired system properties.

Paper: [PDF]

  author = {Gill, Christopher D. and Smart, William D. and Tidwell, Terry and Glaubius, Robert},
  title = {Scheduling as a Learned Art},
  booktitle = {Proceedings of the 4th International Workshop on Operating Systems Platforms for Embedded Real-Time Applications ({OSPERT 2008})},
  pages = {53--62},
  howpublished = {{UNC} Technical Report TR08-010},
  month = {July},
  year = {2008}