Processor scheduling in multiprogrammed parallel systems
Shikharesh Majumdar · 1988
The advantages of converting a problem into a parallel program and running it on a multiprocessor system are well-known. Appropriate processor management strategies are required, however, to harness the power of the multiprocessor system and exploit the concurrency of the program. Most of the existing work in the area is concerned with local scheduling or the allocation of the available processors in the system to the component processes of a single given program. Comparatively little work has been done in the area of global scheduling: the scheduling of processors to competing parallel programs running on a multiprogrammed multiprocessor environment. This research focuses on the global scheduling problem, primarily in the context of shared memory systems. Three different classes of scheduling approaches, dynamic, static, and semi-static are considered. These correspond to three different ranges of cost associated with taking a processor away from an executing program and allocating it to a different program. Based on analytic and simulation techniques the research concentrates on the basic principles underlying global scheduling. The performance of a number of scheduling policies and their inter-relationship with the characteristics of parallel programs are analysed. A number of basic questions that are important in the context of scheduling in multiprogrammed parallel systems have been identified and answered.