BERT: A Scheduler for Best Effort and Realtime Tasks
Abstract:
We describe a new algorithm, called BERT, that can be used to schedule
both best effort and realtime tasks on a multimedia workstation. BERT
exploits two innovations. First, it is based on the virtual clock
algorithm originally developed to schedule bandwidth on packet
switches. Because this algorithm maintains a relationship between
virtual time and real time, our algorithm allows us to simultaneously
factor realtime deadlines into the scheduling decision, and to
allocate some fraction of the processor to best effort tasks. Second,
BERT includes a mechanism that allows one task to steal cycles
from another. This mechanism is valuable for two reasons: it allows us
to distinguish among tasks based on their importance, and it results
in a robust algorithm that is not overly sensitive to the task having
made a perfect reservation.