hide
Free keywords:
-
Abstract:
We investigate the preemptive scheduling of periodic tasks with hard deadlines.
We show that, even in the uniprocessor case, no polynomial time algorithm can
test the feasibility of a task system within a constant speedup bound, unless
$\ccp=\ccnp$. This result contrasts with recent results for sporadic task
systems. For two special cases, synchronous task systems and systems with a
constant number of different task types, we provide the first polynomial time
constant-speedup feasibility tests for multiprocessor platforms. Furthermore,
we show that the problem of testing feasibility is coNP-hard for synchronous
multiprocessor tasks systems. The complexity of some of these problems has been
open for a long time.
We also propose a profit maximization variant of the feasibility
problem, where every task has a non-negative profit, and the goal is to find a
subset of tasks that can be scheduled feasibly with maximum profit. We give the
first constant-speed, constant-approximation algorithm for the case of
synchronous task systems, together with related hardness results.
