Paper #9

The Power of Virtual Time
for Multimedia Scheduling

Andy Bavier & Larry Peterson
Princeton University


Many multimedia scheduling algorithms implement fair sharing of the CPU among processes. However, often a share of the CPU does not adequately satisfy the timing constraints of applications such as MPEG video. Several schedulers have been proposed to address this problem; each provides CPU shares but also features innovative uses of virtual time to better support multimedia applications. To give the reader a flavor of the work in this area, we first compare the mechanisms by which the SMART, BERT, and BVT algorithms provide better multimedia performance. Second, and more significantly, we propose a design methodology for producing multimedia schedulers with provable realtime behaviors using virtual time. Virtual time abstracts critical information from a complex mathematical description of the ideal system. This information is then used to schedule tasks so that the system conforms to its ideal description in real time. Virtual time is a bridge between theory and code, and this is its power.
Download a copy of this paper in either: Compressed PostScript (46K) - or - PDF (86K) format.

Back to the NOSSDAV 2000 On-Line Proceedings.


- Last revised: Weds Jun 27 20:56:29 EDT 2000