Algorithms and complexity concerning the preemptive scheduling of periodic, real-time tasks on one processor

Abstract

We investigate the preemptive scheduling of periodic, real-time task systems on one processor. First, we show that when all parameters to the system are integers, we may assume without loss of generality that all preemptions occur at integer time values. We then assume, for the remainder of the paper, that all parameters are indeed integers. We then give, as our main lemma, both necessary and sufficient conditions for a task system to be feasible on one processor. Although these conditions cannot, in general, be tested efficiently (unless P=NP), they do allow us to give efficient algorithms for deciding feasibility on one processor for certain types of periodic task systems. For example, we give a pseudo-polynomial-time algorithm for synchronous systems whose densities are bounded by a fixed constant less than 1. This algorithm represents an exponential improvement over the previous best algorithm. We also give a polynomial-time algorithm for systems having a fixed number of distinct types of tasks. Furthermore, we are able to use our main lemma to show that the feasibility problem for task systems on one processor is co-NP-complete in the strong sence. In order to show this last result, we first show the Simultaneous Congruences Problem to be NP-complete in the strong sense. Both of these last two results answer questions that have been open for ten years. We conclude by showing that for incomplete task systems, that is, task systems in which the start times are not specified, the feasibility problem is ∑ ^p₂ -complete.