Most conventional CPU scheduling algorithms have been designed for specific application classes (e.g., earliest deadline first and rate monotonic algorithms for hard real-time applications, time-sharing for best-effort applications). To support applications with diverse service requirements, we have developed a {\em hierarchical CPU scheduling framework} that enables different schedulers to be employed for different application classes, while protecting application classes from one another. In this framework, the hierarchical partitioning is specified by a tree. Each thread in the system belongs to exactly one leaf node, and each node in the tree represents either an application class or an aggregation of application classes. Whereas the requirements of application classes determine the leaf node schedulers, intermediate nodes are scheduled using SFQ. This approach provides throughput guarantees to each application class, and does not impose higher overhead than conventional time-sharing schedulers.

Representative Publication:

1. P. Goyal, X. Guo, and H.M. Vin, A Hierarchical CPU Scheduler for Multimedia Operating Systems, In Proceedings of the Second Symposium on Operating Systems Design and Implementations (OSDI'96), Seattle, Washington, Pages 107-122, October 1996 [ Abstract | Paper ]