The Power of Virtual Time
for Multimedia Scheduling
Andy Bavier & Larry Peterson
Princeton University
Abstract:
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.
