PROCESS SCHEDULING: Parallel Languages Versus Operating Systems

This paper deals with multiple processes performing a parallel program, how they are scheduled on physical processors, and their effectiveness in completing the total work to which the individual processes contribute. The current ideas in process scheduling have, to a large extent, grown out of operating systems research on scheduling relatively independent processes on one or a few processors, with the goal being maximal utilization of available resources, especially the processors. Multiprocessor parallel programs may trade processor utilization efficiency for decreased completion time and may employ very fine grained interaction among processes. This yields a different set of requirements on process scheduling than those arising from optimal use of shared resources among weakly dependent or independent tasks. It is argued that coscheduling specifications are a good way to coordinate the possibly conflicting requirements of parallel program completion and multiple job resource utilization. Coscheduling requirements specify the simultaneous availability of a set of resources, processors being the foremost example. Coscheduling requirements may be met by simultaneous assignment of the required number of units or by fine grained time multiplexing of fewer units.