Scheduling Design with Unknown Execution Time Distributions or Modes

Abstract: Open soft real-time systems, such as mobile robots, experience unpredictable interactions with their environments and yet must respond both adaptively and with reasonable temporal predictability. Because of the uncertainty inherent in such interactions, many of the assumptions of the real-time scheduling techniques traditionally used to ensure predictable timing of system actions do not hold in those environments. In previous work we have developed novel techniques for scheduling policy design where up-front knowledge of execution time distributions can be used to produce both compact representations of resource utilization state spaces and efficient optimal scheduling policies over those state spaces. This paper makes two main contributions beyond our previous work, to the state of the art in scheduling open soft real-time systems: (1) it shows how to relax the assumption that the entire distribution of execution times is known up front, to allow online learning of an execution time distribution during system run-time; and (2) it shows how to relax the assumption that the execution time of a system action can be characterized by a single distribution, to accommodate different execution time distributions for an action being taken in one of multiple modes. Each of these contributions allows a wider range of system actions to be scheduled adaptively and with Notes: On-line version of paper submitted to RTSS 2009, with full proof in Appendix A