FOR FREE YEAR SOLVED

Multi-Processor Scheduling

Some important key terms of multi-processor scheduling:

a) Asymmetric Multiprocessing:

In this concept, CPU scheduling in a multiprocessing system has all scheduling decisions, I/O processing, and other system activities handled by a single processor. The other processors execute only user code. This asymmetric multiprocessing is simple because only one processor accesses the system data-structure, reducing the need for data-sharing.

b) Symmetric Multiprocessing (SMP): 

In the case of Symmetric multiprocessing system, each processor is self-scheduling. All processes may be in a common ready queue, or each processor may have its own private queue of ready processes. Scheduling proceeds by having the scheduler for each processor examine the ready queue and select a process to execute. 

c) Processor Affinity:

Consider what happens to cache memory when a process has been running on a specific processor. The data most recently accessed by the process populate the cache for the processor. As a result, successive memory accesses by the process are often satisfied in cache memory. 

Now consider what happens if the process migrates to another processor. The contents of 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 SMP systems try to avoid the migration of processes from one processor to another and instead attempt to keep a process running on the same processor. This is known as processor affinity—that is, a process has an affinity for the processor on which it is currently running.

d) Load balancing: 

It attempts to keep the workload evenly distributed across all processors in a Symmetric Multiprocessing (SMP) system.

There are two general approaches to load balancing: push migration and pull migration.

i) Push Migration: With push migration, a specific task periodically checks the load on each processor and—if it finds an imbalance—evenly distributes the load by moving (or pushing) processes from overloaded to idle or less-busy processors.

ii) Pull Migration: Pull migration occurs when an idle processor pulls a waiting task from a busy processor.

Note: Push and pull migration need not be mutually exclusive and are in fact often implemented in parallel on load-balancing systems. For example, the Linux scheduler and the ULE scheduler available for FreeBSD systems implement both techniques.

e) Multicore Processors:

Traditionally, Symmetric Multiprocessing (SMP) system has allowed several threads to run on currently by providing multiple physical processors. However, a recent practice in computer hardware has been to place multiple processor cores on the same physical chip, resulting in a multicore processor. Each core maintains its architectural state and thus appears to the operating system to be a separate physical processor.

Note: Multi-Processor and Multi-Core processor is a different concept.

f) Memory Stall:

When a processor accesses the main memory, it spends a significant amount of time waiting for the data to become available. This situation, known as a memory stall, may occur for various reasons, such as a cache miss (accessing data that are not in the cache memory).

Fig: 20 

In the above example (Fig:20),  the processor can spend up to 50 percent of its time waiting for data to become available from memory.

Solution:

To remedy this situation, many recent hardware designs have implemented multithreaded processor cores in which two (or more) hardware threads are assigned to each core. That way, if one thread stalls while waiting for memory, the core can switch to another thread.