Report Number: CSL-TR-94-601
Institution: Stanford University, Computer Systems Laboratory.
Title: Efficient Scheduling on Multiprogrammed Shared-Memory Multiprocessors
Author: Tucker, Andrew
Date: March 1994
Abstract: 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. Most parallel applications are written with the model of a stable computing environment, where applications are running uninterrupted on a fixed number of processors. On a time-sharing system, processes are interrupted periodically and the number of processors running an application continually varies. The result is an decrease in performance for a number of reasons, including processes being obliviously preempted inside critical sections and cached data being replaced by intervening processes. This thesis explores using more sophisticated scheduling systems to avoid these problems. Robust implementations of previously proposed approaches involving cache affinity scheduling and gang scheduling are developed and evaluated. It then presents the design, implementation, and performance of process control, a novel scheduling approach using explicit cooperation between the application and kernel to minimize context switching. Performance results from a suite of workloads containing both serial and parallel applications, run on a 4-processor Silicon Graphics workstation, confirm the effectiveness of the process control approach.