Real-Time Scheduling

Real-time scheduling algorithms have traditionally relied on deterministic techniques, which are based on worst-case execution times of tasks. This approach, while sufficient for some types of timing constraints, is inadequate when relative constraints exist between several tasks, and when execution times can range between lower and upper bounds. In collaboration with Professor William Pugh, we developed the novel technique of parametric dispatching to solve this problem [IEEE-TC94]. The approach is to separate the problem into an offline component (during which the schedule is partially produced), and an online component (during which actual task dispatch times are generated). This technique efficiently schedules real-time tasks with complex timing constraints. Since then we have pushed the technique further, to dynamically change schedules on the fly [Manas-Thesis94]. In the future we plan use parametric dispatching to help dispatch object-oriented, real-time programs. The main problem we can address is that of dynamic binding, in which method invocations are not known until runtime.