Issues in multiprogrammed multiprocessor scheduling
Scott T. Leutenegger, Mary K. Vernon · Minds at UW (University of Wisconsin) · 1990
Scheduling policies for general purpose multiprogrammed multiprocessors are not well understood. This thesis examines various policies to determine which characteristics of a scheduling policy are the most significant determinants of performance. In particular we consider three scheduling policy characteristics: allocation of processing power among competing jobs, support for inter-process synchronization, and preemption frequency. We find that allocation of processing power among competing jobs is at least as important as the other two scheduling policy characteristics. We compare a more comprehensive set of policies than previous work, including four scheduling policies that have not previously been examined. We also compare the policies under workloads that may be more realistic than previous studies have used. Using these new workloads, we arrive at different conclusions than reported in earlier work. In particular, we find that the smallest number of processes first (SNPF) scheduling discipline performs poorly, even when the number of processes in a job is positively correlated with the total service demand of the job. We also find that policies that allocate an equal fraction of the processing power to each job in the system perform better than practical policies that allocate processing power unequally. We find that allocation of processing power among competing jobs is at least as important as explicit support for spin-lock and barrier synchronization. (Minimizing spin-waiting is achieved by coscheduling processes within a job, or by using a thread management package that avoids preemption of processes that hold spinlocks.) We also find that allocation of processing power among competing jobs is a more important characteristic of a scheduling policy than preemption frequency for a wide range of preemption overhead values. Our studies are done by simulating abstract models of the system and the workloads.