BERT: A Scheduler for Best Effort and Realtime Tasks
Report ID: TR-587-98Author: Peterson, Larry / Bavier, Andy / Mosberger, David
Date: 1998-08-00
Pages: 22
Download Formats: |Postscript|
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.