Paper Info
Title
The NP-Hardness and the Algorithm for Real-Time Disk-Scheduling in a Multimedia System
Abstract
Real-time disk scheduling is an important research topic for time-critical multimedia applications. Some well-known research results, such as SCAN-earliest deadline first (EDF) and DM-SCAN, applied the SCAN scheme to reschedule service sequence of input tasks and reduce their service time. In this paper, we prove that the general disk-scheduling problem with linear cost-function is NP-Hard. We also propose the shortest-task-first-DM, a new real-time disk-scheduling algorithm using the concept of the shortest-task-firstand the deadline modification. As shown in the experimental results, our approach can schedule more tasks to meet their deadlines.
Year
DOI
Venue
2005
10.1109/RTCSA.2005.98
RTCSA
Keywords
Field
DocType
real-time disk-scheduling,well-known research result,important research topic,multimedia system,scan scheme,new real-time disk-scheduling algorithm,general disk-scheduling problem,service sequence,real-time disk scheduling,deadline modification,scan-earliest deadline,service time,real time,cost function,algorithms,computational complexity,scheduling,earliest deadline first,disk scheduling,real time systems
I/O scheduling,Fair-share scheduling,Computer science,Algorithm,Real-time computing,Two-level scheduling,Least slack time scheduling,Rate-monotonic scheduling,Dynamic priority scheduling,Earliest deadline first scheduling,Round-robin scheduling,Distributed computing
Conference
ISBN
Citations 
PageRank 
0-7695-2346-3
4
0.39
References 
Authors
9
4
Name
Order
Citations
PageRank
Pei-Chi Huang1649.92
Wan-Chen Lu2415.63
Chun-Nan Chou3402.82
Wei-Kuan Shih493898.21