Title :
Real-time scheduling of non-preemptive periodic tasks for continuous media retrieval
Author :
Baek, Yun-Cheol ; Koh, Kern
Author_Institution :
Dept. of Comput. Sci., Seoul Nat. Univ., South Korea
Abstract :
A real-time system should guarantee that each hard real-time task completes execution before its deadline. When non-preemptive earliest deadline first (EDF) scheduling is used for a set of periodic tasks, one can achieve full processor utilization, but its schedulability test is known to be an NP-hard problem. Continuous media (CM) retrieval is becoming an important application of real-time systems. In such an application, the CM server should provide CM data requested by clients within the specified deadline. We examine the O(1) time online schedulability tests for a set of equal computation time tasks and for a set of equal period tasks using non-preemptive EDF algorithm. We also demonstrate that these results can be used for scheduling a set of client requests in CM retrieval system
Keywords :
computational complexity; processor scheduling; real-time systems; CM retrieval system; NP-hard problem; client requests; continuous media retrieval; earliest deadline first scheduling; equal computation time tasks; equal period tasks; full processor utilization; hard real-time task; non-preemptive periodic tasks; online schedulability tests; real-time scheduling; schedulability test; Computer science; Dynamic scheduling; NP-hard problem; Network servers; Processor scheduling; Real time systems; Runtime; Scheduling algorithm; Testing; Timing;
Conference_Titel :
TENCON '94. IEEE Region 10's Ninth Annual International Conference. Theme: Frontiers of Computer Technology. Proceedings of 1994
Print_ISBN :
0-7803-1862-5
DOI :
10.1109/TENCON.1994.369254
