Fair Share Scheduling for Big Systems 大系统的公平共享调度.doc

effectively. Since the target systems are potentially large, a model is useful only if we

have a scalable algorithm to analyze it. In this paper we discuss three approaches to

solving the scalability problem, based on aggregation, hierarchical decomposition and

randomization. We then compare our scalable algorithms to each other and to the existing

expensive exact solution that runs in time proportional to n! for an n workload model.

1. Introduction

Fair Share scheduling is now a

mainstream technology for managing

application performance on Unix

systems. Hewlett Packard offers Process

allow planners to understand how to use

that technology effectively [BD00],

[BB99]. Unfortunately, the evaluation

algorithm takes time proportional to n!

for an n workload model. On today's

processors that becomes unbearably slow

when n is about 10.