Seminars & Meetings | Abstracts

November 23, 2009

Chris Gill
Computer Science and Engineering
Washington University in St. Louis
Non-Preemptive Scheduling Policy Design for Tasks with Stochastic Execution Times


Scheduling to partition the utilization of processors and other resources that allow efficient preemption and resumption, precisely among tasks with well bounded execution times, has received significant attention in the real-time systems research community. However, for an important class of cyber-physical tasks such as positioning a robotic arm or camera on a shared pan-tilt unit (1) preemption and resumption may be prohibitively expensive, and (2) even mutually independent tasks may exhibit highly variable execution times, e.g., due to differences in the physical state of the system when a task starts.

This talk describes the development of new techniques to find non-preemptive scheduling policies that can share resource utilization among tasks with stochastic execution times, with reasonable precision. Contributions of this research, which integrates methods from real-time systems and machine learning, include: (1) applying Markov Decision Process (MDP) based policy iteration to resource utilization state spaces; (2) bounding and wrapping the utilization state spaces to obtain decidable exact techniques for scheduling policy design with small numbers of tasks; and (3) parametric approximation of scheduling policies to obtain tractable and effective search-based techniques for scheduling policy design with larger numbers of tasks.


Christopher D. Gill is an Associate Professor of Computer Science and Engineering at Washington University in St. Louis. His research focuses on the modeling, enforcement, verification, and validation of properties of distributed real-time and embedded systems in which the complexities of interacting hardware, software, and physical environments demand novel solutions that are grounded in sound theory. A major goal of his work is to assure that constraints on timing, memory footprint, fault-tolerance, and other system properties can be met when system components are re-used across heterogeneous applications, operating environments, and deployment platforms.