Scheduling periodic-time-critical tasks on multiprocessor computing systems /

Abstract

The problem of allocating a set of periodic-time-critical tasks to processors in a multiprocessor system is considered. A periodic-time-critical task consists of a certain number of requests, arising periodically, each of which has a prescribed deadline. The allocation problem is to use a minimum number of processors subject to the condition that the tasks allocated to any processor must be feasibly schedulable according to some specified algorithm, i.e. the schedule provided by the algorithm must guarantee that the deadline of each request is honored. We first prove that this problem is NP-hard, and then present three heuristic algorithms and analyze their complexity and worst-case performance. One of the algorithms presented is an off-line algorithm and the other two are on-line. Two heuristic off-line algorithms for this problem are available in literature. The worst-case performance of our off-line algorithm is shown to be better than that of the two existing off-line algorithms. The on-line algorithms presented here are the only on-line algorithms presented for this problem to date. The time and space complexity of the presented on-line algorithms are shown to be better than those of the available off-line algorithms, and their worst-case performance are shown to be comparable to that of the available off-line algorithms. Finally, it is shown that if the set of tasks to be scheduled does not contain any task with utilization factor in the range (2(' 1/2)-1, 1/2 then the worst-case performance of one of the on-line algorithms will improve considerably.