Efficient Scheduling on Multiprogrammed Shared-Memory Multiprocessors
Andrew Tucker · 1994
Shared-memory multiprocessors are often used as compute servers, with multiple users running applications in a multiprogrammed style. On such systems, naive time-sharing scheduling policies can result in poor performance for parallel applications. The reason is that many parallel applications are written assuming a model where applications are running uninterrupted on a fixed number of processors. In compute server environments, where new applications are continuously moving in and out of the system, the computing environment is much more unstable; processes are frequently preempted to allow other applications' processes to run, and both the number of processors and the set of processors running an application varies over time. The result is a decrease in performance due to a variety of factors, including processes being obliviously preempted inside critical sections and cached data being replaced by intervening processes. This thesis explores the problem of developing more sophisticated scheduling systems to avoid the performance problems raised by running parallel applications in a multiprogrammed environment. It begins with a study of two previously proposed solutions, cache affinity scheduling and gang scheduling. Effective new implementations of each have been developed that maintain good response time and fair processor allocation. Performance results from a suite of multiprogrammed workloads containing parallel and serial applications, run on a 4-processor Silicon Graphics workstation, show improvements of up to 16% and 15% (over a standard UNIX scheduler) for cache affinity and gang scheduling, respectively. The thesis then presents the design, implementation, and performance of a novel approach that offers high performance by combining the techniques of process control and processor partitioning. The process control approach is based on the principle that to maximize performance, a parallel application must dynamically match the number of runnable processes associated with it to the effective number of processors available. This avoids problems arising from frequent process preemption and allows applications to work at better operating points on their speedup curves. Performance results show speedups of up to 22% over the performance of a standard UNIX scheduler.