Multi processor scheduling

Operating System: Multi-Processor scheduling, Multi-Core issues, Processor affinity and Load balancing

1. Multi- Processor Scheduling: Multi-core issues, Processor affinity, load balancing Presented By Shashank Kapoor Chandradeep Gautam

2. Scheduling The process scheduling is the activity of the process manager that handles the removal of the running process from the CPU and the selection of another process on the basis of a particular strategy.

3. Multi- Processor Scheduling Multi-Processor scheduling is an NP-hard optimization problem . The problem statement is: " Given a set  J  of jobs where job  j i  has length  l i  and a number of processors  m , what is the minimum possible time required to schedule all jobs in  J  on  m  processors such that none overlap ? “

4. What is Multi- Processor Scheduling ? In multiple-processor scheduling multiple CPU’s are available Load Sharing becomes possible, as distributed among these available processor. Multiple processor scheduling is more complex as compared to single processor scheduling. Multi-Processor scheduling is of two types: # Asymmetric Scheduling # Symmetric Scheduling

5. Multi- Processor Scheduling: Asymmetric Approach In this scheduling approach, all scheduling decisions, I/O processing and resource allocation are handled by a single processor which is called the Master Processor  and the other processors executes only the user code. This is simple and reduces the need of data sharing. This entire scenario is called Asymmetric Multiprocessing.

6. Multi- Processor Scheduling: Symmetric Approach A second approach uses Symmetric Multiprocessing where each processor is self scheduling. All processes may be in a common ready queue or each processor may have its own private queue for ready processes. The scheduling proceeds further by having the scheduler for each processor examine the ready queue and select a process to execute.

7. Multi-Core Issues Locking system As we know that the resources are shared in the multiprocessor system so there is a need to protect these resources for safe access among the multiple processors. The main purpose of locking scheme is to serialize access of the resources by the multiple processors. Shared data When the multiple processor access the same data at the same time then there may be a chance of inconsistency of data so to protect this we have to use some protocols or locking scheme. Cache coherence It is the shared resource data which is stored in the multiple local caches. Suppose there are two clients have a cached copy of memory and one client change the memory block and the other client could be left with invalid cache without notification of the change so this kind of conflict can be resolved by maintaining a coherence view of the data.

8. Processor Affinity When a process runs on a specific processor there are certain effects on the cache memory. The data most recently accessed by the process populate the cache for the processor and as a result successive memory access by the process are often satisfied in the cache memory. Now if the process migrates to another processor, the contents of the cache memory must be invalidated for the first processor and the cache for the second processor must be repopulated. Because of the high cost of invalidating and repopulating caches, most of the SMP(symmetric multiprocessing) systems try to avoid migration of processes from one processor to another and try to keep a process running on the same processor. This is known as  PROCESSOR AFFINITY . There are two types of processor affinity: # Soft Affinity # Hard Affinity

9. Processor Affinity: Soft Affinity When an operating system has a policy of attempting to keep a process running on the same processor but not guaranteeing it will do so, this situation is called soft affinity.

10. Processor Affinity: Hard Affinity Some systems such as Linux also provide some system calls that support Hard Affinity which allows a process to migrate between processors.

11. Load Balancing Load Balancing is the  phenomena  which keeps the  workload  evenly  distributed  across all processors in an SMP system. Load balancing is necessary only on systems where each processor has its own private queue of process which are eligible to execute. Load balancing is unnecessary because once a processor becomes idle it immediately extracts a runnable process from the common run queue. On SMP(symmetric multiprocessing), it is important to keep the workload balanced among all processors to fully utilize the benefits of having more than one processor else one or more processor will sit idle while other processors have high workloads along with lists of processors awaiting the CPU . There are two general approaches to load balancing : # Push Migration # Pull Migration

12. In push migration a task routinely checks the load on each processor and if it finds an imbalance then it evenly distributes load on each processors by moving the processes from overloaded to idle or less busy processors. Load Balancing : Push Migration

13. Pull Migration occurs when an idle processor pulls a waiting task from a busy processor for its execution. Load Balancing : Pull Migration