Window-Constrained real-time periodic task scheduling

Window-Constrained Scheduling is one of the task models proposed in recent years for scheduling periodic real-time tasks where service must be guaranteed in only a fraction of the periods. In RTSS'2000, a Dynamic Window-Constrained Scheduling (DWCS) algorithm was proposed by West and Poellabauer (17) for multiplexing multiple packet streams where the number of consecutive packet lost must be bounded. In this paper, we show that the DWCS algorithm can fail for arbitrarily low aggregate utilization rates of the packet streams. We shall show that Window-Constrained Scheduling is NP-hard in the strong sense. However if the execution time of all jobs is of unit size, as might be modelled in some packet stream applications, then a schedule must exist as long as the aggregate utilization rate is no more than the number of processors (packet switching resources). Some subclasses of the Window-Constrained Scheduling for unit-size jobs can be transformed to the well known Liu and Layland model or the more recent Pfair model and can therefore be scheduled optimally and at low scheduling cost. In considering the general unit-size-job case, we note that non-proportionate progress in scheduling Window-Constrained tasks is often the cause of unschedulability, no matter how low the aggregate utilization rate is. We shall define the notion of Pfairness in relation to the Window-Constrained Scheduling model so as to quantitatively describe the concept of strictly proportionate progress. An EDF (Earliest-Deadline-First) based algorithm will be defined for the Window-Constrained Scheduler problem. This algorithm is computationally efficient, on-line, and Pfair A sufficient schedulability test for this EDF-based algorithm is proved.