Abstract | |
|
Back to Advance Program
On the complexity of scheduling real-time tasks with self-suspensions on one processorP. RichardTo appear at Euromicro Conference on Real-Time Systems (ECRTS03), Porto, Portugal, 2-4 July 2003
AbstractIntegrating practical factors in scheduling theory is a major issue. Efficient schedulability tests (polynomial time or pseudo-polynomial time algorithms) are known for preemptive, independent tasks. In this paper, tasks are allowed to self-suspend. In practice,self-suspensions are performed by the real-time kernel when a task requests an external operation (such as INPUT/OUTPUT or remote operations on a specialized processor). We study feasibility analysis problems from the computational complexity point of view. The problem is proved NP-hard in the strong sense for periodic, preemptive or non-preemptive task sets. If we allow tasks to have several flows of control (multi-threaded tasks), then the corresponding feasibility problem is shown to be NP-hard in the strong sense in the case of unit execution time threads.
10 Mar 2003 at 21:02:26 |