| Abstract |
|
Integrating 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, the real-time kernel suspends a task when it requests an external blocking operation. 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 .ows 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.
|
 Additional Information
|
Citation:
Pascal Richard,
"On the Complexity of Scheduling Real-Time Tasks with Self-Suspensions on One Processor,"
ecrts,
p. 187,
15th Euromicro Conference on Real-Time Systems (ECRTS'03),
2003
|
