Scheduling in Multiprogrammed Parallel Systems

by Fang Wang

In the context of parallel systems, scheduling is often thought of as assigning tasks in a program to processors. This assumes that the processors are dedicated to the program. However, in multiprogrammed parallel and distributed systems, scheduling involves the execution of tasks from competing programs on the same processors. In this case, scheduling becomes a resource allocation issue.

Scheduling schemes for these systems can be classified as one or two leveled. Single-level scheduling combines the allocation of processors with the decision of which task will use it. Two-level scheduling decouples the two issues: first, processors are allocated to the job, and second, the job's tasks are scheduled using this pool of processors. The processors of a parallel and distributed system can be used by multiple programs in three ways, which are relevant for both one-level and two-level scheduling. Some systems use time slicing, where all the processors in the system serve a global queue of ready tasks. Other systems use space slicing and partition the processors statically or dynamically among the different jobs. The third mode is to use both time slicing and space slicing, as in gang scheduling.

I will give a brief survey of systems using each of these approaches, and describe the implications of the various mechanisms. Gang scheduling and related issues will be presented in more detail.