Real-time scheduling of multimedia data retrieval to minimize buffer requirement

W. J. Tsai*, Suh Yin Lee

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


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.

Original languageEnglish
Pages (from-to)67-80
Number of pages14
JournalOperating Systems Review (ACM)
Issue number3
StatePublished - Jul 1996


  • Buffer management
  • Data retrieval
  • Real time
  • Scheduling


Dive into the research topics of 'Real-time scheduling of multimedia data retrieval to minimize buffer requirement'. Together they form a unique fingerprint.

Cite this