Abstract | ||
---|---|---|
Continuous display is an important issue in the domain of multimedia applications. Especially, to ensure this continuity in the presence of multiusers, a feasible scheduling algorithm is prerequisite for real time data retrieval from the I/O subsystem. I/O scheduling techniques can be classified into two types: meta-I/O scheduling which arranges the sequence of data retrieval before issuing physical I/O requests, and disk scheduling which determines the order of processing I/O requests that have been issued. In disk scheduling, there are several elegant algorithms that had been discussed such as Scan, C-Scan, shortest seek time first and Scan-EDF. All of them focused on improving I/O throughput by serving requests closer to disk head first [7][8]. We focus this paper, however, on solving the real time meta-I/O scheduling.For real-time scheduling, several algorithms had been addressed such as earliest-deadline-first (EDF) [4], least-laxity-first (LLF) [9], earliest-ready-time first (LRF) [6], and so on, which had shown to be elegant for task scheduling to promote system throughput. When applying to meta-I/O scheduling, however, these algorithms would result in large amount of buffer requirement for accommodating the retrieved data. In this paper, we proposed two real-time algorithms and a technique, called object migration, to minimize buffer requirement for meta-I/O scheduling. A buffer measurement approach was also proposed in this paper to estimate the performance of a real-time scheduling algorithm, which is based upon the well-known graph coloring technique. Simulation experiments were conducted to analyze the performance of algorithms. The results indicate that our approaches perform much better than existing real-time algorithms in terms of reducing buffer requirement. |
Year | DOI | Venue |
---|---|---|
1996 | 10.1145/230908.230921 | Operating Systems Review |
Keywords | Field | DocType |
o scheduling,real-time algorithm,buffer requirement,o scheduling technique,disk scheduling,real time,scheduling,real-time scheduling,task scheduling,buffer management,feasible scheduling algorithm,data retrieval,multimedia data retrieval,real-time scheduling algorithm,o request,simulation experiment,real time data,scheduling algorithm,earliest deadline first,graph coloring,least laxity first | Fixed-priority pre-emptive scheduling,I/O scheduling,Fair-share scheduling,Computer science,Two-level scheduling,Real-time computing,Rate-monotonic scheduling,Earliest deadline first scheduling,Dynamic priority scheduling,Round-robin scheduling,Distributed computing | Journal |
Volume | Issue | Citations |
30 | 3 | 1 |
PageRank | References | Authors |
0.38 | 5 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Wen-Jiin Tsai | 1 | 174 | 19.57 |
Suh-Yin Lee | 2 | 1596 | 319.67 |