Multiprocessor Scheduling – CPU Scheduling

Multiprocessor Scheduling – CPU Scheduling

• Symmetric Multiprocessing system is a system in which CPUS share system resources, including the bus to common memory space. CPUS communicate one another by sharing information in this memory space. This type of setup is also known as tightly coupled architecture.
• On the other hand, Parallel Processing (PP) system is a system in which each CPU has its own memory and often a unique set of system resources. The CPUS communicate externally using some type of network. This type of system is known as loosely coupled architecture.
• In some type of multiprocessor system, classification is done on the basis of type of CPUS used. When multiprocessor system uses different types of CPUS, it is called heterogeneous system whereas homogeneous system uses identical CPUs.
• CPU scheduling in symmetric multiprocessor systems is almost similar to that of uniprocessor system (that uses single processor). In such a system, a single global ready queue is used by all the CPUS. In addition to this, each CPU may have its own local ready queue in order to avoid high contention.
• The processes from the global ready queue are distributed to local queue. This is done by balancing the workload on CPUs.

There are various way in which the multiprocessors system can be connected and operate. These techniques differ in degree of scheduling sophistication. These are :

1. Separate systems
2. Coordinated job scheduling
3. Master/slave scheduling
4. Homogeneous scheduling

1. Separate Systems

• In this type multiprocessor system, there are two or more separate systems, each with one processor, some main memory and peripheral devices. This is just like having two or more separate computing systems.
• In this kind of system, there is no job or process scheduling between the processor except that which is accomplished manually.
• The various processes are scheduled on each of the individual processor in the same way as is done in uniprocessor scheduling.
• This type of scheduling is used in IBM system/360 Model 67.

The separate system scheduling offers several advantages:

1. The various processors, memories and I/O devices can be easily switched. This switching is usually done manually.
2. This configuration flexibility is useful if there are some jobs that require the full complement of memory and/or I/O device resources.
3. If one processor is being repaired, all other resource can be pooled into one large system rather than be allowed to sit idle.

2. Coordinated Job Scheduling

• Coordinated job scheduling approach is also known as loosely coupled multiprocessing.
• In this method, each processor is associated with a separate system.
• When a job arrives, it may be assigned to any processor.

• This assignment of a job to a system may be based on a variety of requirements and policies, such as assigning the job to the system with the lightest load.
• To accomplish this balancing, all job scheduling must be coordinated. This may be done manually, by a special purpose computer or by one of the actual processing systems.
• The permanent assignment of a job to a system, cannot handle the short term balancing of resource demand.

3. Master/Slave Scheduling

• In this technique, there is one main processor called master and rest of all processors are slaves.
• In master/slave scheduling technique, master processor maintains the status of all processes in the system.
• All other processor called slave are managed by master processor i.e. master schedules the work of all the slave processors.
• The master processor selects a process to be run, finds an available processor, and issues a start processor instruction.
• The slave processor starts execution at the indicated memory location. When the slave encounters an exceptional event such as an I/O request, it generates an interrupt to the master processor and stops to await further orders.

There are certain disadvantages of master/slave scheduling :

1. It is not fair as it does not give equal importance to all processes.
2. Under heavy scheduling loads, the master processor may become overloaded and cause a major bottleneck.

4. Homogeneous processor scheduling

• In homogeneous processor scheduling, all processors and treated equally i.e. there is no master or slave. Under such conditions, processor scheduling is logically decentralized.
• A list of processes and their status is maintained in this system.
• Any processor can have access to this list.
• Whenever a process is stopped due to I/O wait or timer limit etc., its processor goes the process state list, updates the process status, and finds another process to run.
• Each processor uses the same scheduling algorithm to select the next process to run.
• If all processors are handled identically, no policy differences need exist with regard to a single processor or multiple processor operating system.