PROCESSOR SCHEDULING IN MULTIPROCESSOR SYSTEMS

Processor scheduling in multiprocessor systems can be divided into two steps. The first step, referred to as the processor allocation problem, is to determine the number of processors to be allocated to a job so as to maximize the system throughput and processor utilization. This depends both on the load on the system and on certain inherent characteristics of the job - most importantly bow efficiently the job can utilize a given number of processors. The second step, referred to as the processor assignment problem, assigns processors to the parallel tasks in a job so as to minimize the execution time on the allocated processors. The processor assignment depends on the number of processor allocated, the processor interconnection structure, and the precedence relationship among the tasks in the job. This paper reviews the various issues in the above two steps of the processor scheduling.