The performance of local and global scheduling strategies in multiprogrammed parallel systems

Processor scheduling on multiprogrammed parallel systems is currently not well-understood. Based on analytical models this paper presents an investigation of local as well as global scheduling in the context of fork and join applications running on shared-memory multiprocessor systems. Local scheduling is concerned with the allocation of a given number of processors to the component processes of a single job while global scheduling deals with the system at large and is concerned with the partitioning of the available processing resources among competing jobs that are currently active on the system. The global scheduling approach analysed in the paper is static in the sense that a fixed set of processor is allocated to a job and dynamic processor switching from one application to another is not allowed. Important insights into system behaviour that are useful in the context of operating systems for parallel systems are obtained as a result of this analysis. For example, parallelism characteristics of jobs do not seem to have any significant effect on the relative performance of different local scheduling strategies while job characteristics are observed to have a strong impact on the performance of global scheduling. A number of basic issues that concern the relationship between job characteristics, system performance and effective scheduling are discussed