Scheduling distance-constrained real-time tasks

In the traditional periodic real-time task model, every task needs to be executed once during each of its periods. The execution of a task in one period is independent of the execution of the same task in any other period. As a result, two executions of the same task in consecutive periods may be right next to each other, or at the two far ends of the two periods. In this paper, we present a new model of real-time task systems with temporal distance constraints. In such systems, the distance between any two consecutive finishing times of the same task must be less than or equal to a given value. Using the periodic task model for such tasks may not provide an efficient solution. We discuss the scheduling approaches for this distance-constrained task model and propose several scheduling algorithms. We also study the schedulability conditions for these algorithms.