DISTANCE-CONSTRAINED SCHEDULING AND ITS APPLICATIONS TO REAL-TIME SYSTEMS

In hard real-time systems, each task must not only be functionally cor rect but also meet its timing constraints. A common approach to charac terizing hard real-time tasks with repetitive requests is the periodic task model [1]. In the periodic task model, every task needs to be ex ecuted once during each of its periods. The execution of a task in one period is independent of the execution of the same task in another pe riod. Hence, the executions of the same task in two consecutive period s may be right next to each other, or at the far ends of the two perio ds. While the periodic task model can serve as a simple paradigm for s cheduling tasks with repetitive requests, it may not be suitable for a ll real-time applications. For example, in some real-time systems, the temporal distance between the finishing times of any two consecutive executions of the same task must be less than or equal to a given valu e. In other words, each execution of a task has a deadline relative to the finishing time of the previous execution of the same task. Schedu ling algorithms designed for the periodic task model may not provide e fficient solutions for tasks with temporal distance constraints. In th is paper, we propose the (preemptive) distance-constrained task system model which can serve as a more intuitive and adequate scheduling mod el for ''repetitive'' task executions. We design an efficient scheduli ng scheme for the model, and derive a schedulability condition for the scheduling scheme. The schedulability condition is a measure for prov iding the fundamental predictability requirement in hard real-time app lications. To show the usefulness of the distance-constrained task mod el and its scheduling scheme, we also discuss how to apply the schedul ing scheme to real-time sporadic task scheduling and to real-time comm unications.