Fair Share Modeling for Large Systems: Aggregation, Hierarchical Decomposition and Randomization

摘要

HP, IBM and Sun each offer fair share scheduling packages on their UNIX platforms, so that customers can manage the performance of multiple workloads by allocating shares of system resources among the workloads. A good model can help you use such a package 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.