A DYNAMIC PROCESSOR ALLOCATION POLICY FOR MULTIPROGRAMMED SHARED-MEMORY MULTIPROCESSORS

作     者：MCCANN, C VASWANI, R ZAHORJAN, J 

作者机构：Univ. of Washington St. Louis MO Univ. of Washington St. Louis MO Univ. of Washington St. Louis MO 

出 版 物：《ACM TRANSACTIONS ON COMPUTER SYSTEMS》 (美国计算机学会计算机系统汇刊)

年 卷 期：1993年第11卷第2期

页      面：146-178页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：SHARED MEMORY PARALLEL PROCESSORS THREADS 2-LEVEL SCHEDULING 

摘      要：We propose and evaluate empirically the performance of a dynamic processor-scheduling policy for multiprogrammed shared-memory multiprocessors. The policy is dynamic in that it reallocates processors from one parallel job to another based on the currently realized parallelism of those jobs. The policy is suitable for implementation in production systems in that: It interacts well with very efficient user-level thread packages, leaving to them many low-level thread operations that do not require kernel intervention. It deals with thread blocking due to user I/O and page faults. It ensures fairness in delivering resources to jobs. Its performance, measured in terms of average job response time, is superior to that of previously proposed schedulers, including those implemented in existing systems. It provides good performance to very short, sequential (e.g., interactive) requests. We have evaluated our scheduler and compared it to alternatives using a set of prototype implementations running on a Sequent Symmetry multiprocessor. Using a number of parallel applications with distinct qualitative behaviors, we have both evaluated the policies according to the major criterion of overall performance and examined a number of more general policy issues, including the advantage of space sharing over time sharing the processors of a multiprocessor, and the importance of cooperation between the kernel and the application in reallocating processors between jobs. We have also compared the policies according to other criteria important in real implementations, in particular, fairness and response time to short, sequential requests. We conclude that a combination of performance and implementation considerations makes a compelling case for our dynamic scheduling policy.