BERT: A Scheduler for Best Effort and Realtime Tasks - revised
Abstract:
We describe a new scheduler, called BERT, that runs both best effort
and realtime tasks on a multimedia workstation. BERT exploits two
innovations. First, it extends the proportional share scheduling
algorithm to allow one task to dynamically steal cycles from
another. This mechanism allows BERT to address a main drawback of
scheduling MPEG video decoding using proportional share: the
difficulty of making the right reservation. Second, BERT combines the
stealing mechanism with task importance to maintain QoS guarantees in
overload. In BERT, important realtime tasks can steal to make
deadlines and important best effort tasks can be made immune from
stealing. The result is a graceful degradation of performance under
heavy load. We have implemented BERT in the Scout operating system
and we present our experiences using it to schedule multimedia
workloads.