Check out the new USENIX Web site.

Home About USENIX Events Membership Publications Students
OSDI 2000 Abstract

Surplus Fair Scheduling: A Proportional-Share CPU Scheduling Algorithm for Symmetric Multiprocessors

Abhishek Chandra, Micah Adler,University of Massachusetts Amherst, Pawan Goyal, Ensim Corporation and Prashant Shenoy, University of Massachusetts Amherst

Abstract

In this paper, we present surplus fair scheduling (SFS), a proportional-share CPU scheduler designed for symmetric multiprocessors. We first show that the infeasibility of certain weight assignments in multiprocessor environments results in unfairness or starvation in many existing proportional-share schedulers. We present a novel weight readjustment algorithm to translate infeasible weight assignments to a set of feasible weights. We show that weight readjustment enables existing proportional-share schedulers to significantly reduce, but not eliminate, the unfairness in their allocations. We then present surplus fair scheduling, a proportional-share scheduler that is designed explicitly for multiprocessor environments. We implement our scheduler in the Linux kernel and demonstrate its efficacy through an experimental evaluation. Our results show that SFS can achieve proportionate allocation, application isolation and good interactive performance, albeit at a slight increase in scheduling overhead. We conclude from our results that a proportional-share scheduler such as SFS is not only practical but also desirable for server operating systems.
?Need help? Use our Contacts page.

Last changed: 16 Jan. 2002 ml
Technical Program
OSDI 2000 Home
USENIX home