Operating System (CS2701)

Multi-Processor Scheduling

​

​

Dr. Rourab Paul

Computer Science Department, SNU University, Chennai

​

​

Operating System

CPU Scheduling in Multiprocessor Systems

Operating System

2

1. Asymmetric Multiprocessing (AMP)

• Approach:
• One processor = Master server
• Handles all scheduling, I/O processing, system activities
• Other processors = execute only user code
• Advantages:
• Simple design
• Only one processor accesses system data structures
• Less need for data sharing
• Disadvantage:
• Master server bottleneck
• Can reduce overall system performance

CPU Scheduling in Multiprocessor Systems

Operating System

3

2. Symmetric Multiprocessing (SMP)

• Approach:
• Each processor is self-scheduling
• Every processor runs its own scheduler
• Scheduler picks threads from the ready queue
• Advantages:
• Better load balancing
• No single bottleneck
• Improves performance & scalability

Scheduling Strategies

Operating System

4

1. All threads may be in a common ready queue.
2. Each processor may have its own private queue of threads.

Scheduling Strategies

Operating System

5

• All threads may be in a common ready queue.

If we select the first option, we have a possible race condition on the shared ready queue and therefore must ensure that two separate processors do not choose to schedule the same thread and that threads are not lost from the queue.

we could use some form of locking to protect the common ready queue from this race condition. Locking would be highly contended, however, as all accesses to the queue would require lock ownership, and accessing the shared queue would likely be a performance bottleneck.

SMP and Multicore Processors

Operating System

6

Traditional SMP:

• Multiple physical processors for parallel execution

Modern hardware:

• Multicore processors (multiple cores on one chip)
• Each core = separate logical CPU to the OS

Advantages:

• Faster execution
• Lower power consumption than multiple physical CPUs

​

Scheduling Challenges

Operating System

7

Problem:

• Processor often waits for data (memory stalls)
• Causes:
• Processor is faster than memory
• Cache misses

Impact:�Processor may spend up to 50% of time waiting

​

Multithreaded Cores

Operating System

8

• Solution:
• Assign multiple hardware threads per core
• If one thread stalls → core switches to another
• Each hardware thread:
• Has its own instruction pointer & registers
• Appears as a logical CPU to the OS
• Benefit:
• Keeps core busy, reduces idle waiting

Example:

• 4 cores, each with 2 hardware threads. Intel Hyper Threading
• OS sees 8 logical CPUs

Improves CPU utilization and throughput

Chip threading

Operating System

9

Load Balancing in SMP

Operating System

10

• Ensures even distribution of workload across processors.
• Prevents idle processors while others are overloaded.�Needed mostly when processors have private ready queues.
• Not required if using a common run queue (idle CPU directly picks a task).

​

Approaches to Load Balancing

1. Push Migration
• A dedicated task monitors load.
• If imbalance is found → push threads from busy → idle processors.
2. Pull Migration
• An idle processor pulls a waiting task from an overloaded processor.

Processor Affinity

Operating System

11

Concept

• When a thread runs on a processor, its cache stores recent data → warm cache.
• If the thread moves to another processor:
• Old cache is invalidated.
• New cache must be repopulated → performance cost.
• To avoid this, OS tries to keep a thread on the same processor.

Types of Processor Affinity

1. Soft Affinity
• OS tries to keep a process on the same CPU.
• Migration may still occur during load balancing.
2. Hard Affinity
• Process can specify a subset of CPUs it is allowed to run on.
• Example: Linux sched_setaffinity() system call.

Thank You

Operating System

12