An Optimal, On-Line Window-Constrained Scheduler for Real-Time, Heterogeneous Activities

Abstract

This paper describes how Dynamic Window-Constrained Scheduling (DWCS) can guarantee hard real-time service to activities, such as network-bound packets, and CPU-bound threads. We show that: (1) DWCS can guarantee there are no more than x missed deadlines for every y requests for service, (2) DWCS bounds the delay of service to real-time activities even when the scheduler is overloaded, (3) the least upper bound on resource utilization using DWCS is 100%, and (4) a fast response time for best-effortactivities, in the presence of hard real-time activities, is possible. As long as the minimum resource utilization of a set of real-time activities does not exceed 100%, DWCS guarantees that each such activity does not miss more than x deadlines for every y requests. In this sense, DWCS is an optimal on-line scheduling algorithm.