Multiprocessor Scheduling in Operating System Explained With Examples
In a single-processor system, the operating system mainly decides which ready process should use the CPU next. But modern computers may have several processor cores or logical CPUs available at the same time. Now the operating system has an extra problem: it must decide not only which task should run, but also which processor should run that task.
This is called Multiprocessor Scheduling in Operating System. Important topics include Asymmetric Multiprocessing, Symmetric Multiprocessing, global and per-CPU run queues, processor affinity, load balancing, push migration, pull migration, multicore scheduling, NUMA and processor migration. We will connect all of them step by step in very simple language.
SCHEDULER
What Is Multiprocessor Scheduling in Operating System?
Multiprocessor Scheduling in Operating System means scheduling processes or threads when more than one processor or processing unit is available.
The system must decide which runnable task should execute and on which processor that task should run.
Multiprocessor scheduling is the process of assigning and scheduling runnable tasks across multiple CPUs or cores so that processor resources are used efficiently.
Why Is Multiprocessor Scheduling More Difficult?
Single-Processor vs Multiprocessor Scheduling
Single Processor
Only one CPU execution resource is considered in the basic model.
The scheduler mainly decides: Which ready task should run next?
Multiprocessor System
Several processors, cores or logical CPUs may execute tasks.
The scheduler must decide: Which task should run and where should it run?
The Main Multiprocessor Scheduling Problem
Suppose a system has four processors.
If CPU 0 and CPU 1 are extremely busy while CPU 3 has almost no work, the hardware is not being used efficiently.
A multiprocessor scheduler may try to redistribute runnable tasks so that the processors are used more effectively.
Asymmetric and Symmetric Multiprocessing Scheduling
Two important approaches traditionally used to explain multiprocessor scheduling in OS are Asymmetric Multiprocessing (AMP) and Symmetric Multiprocessing (SMP).
Asymmetric Multiprocessing
In asymmetric multiprocessing, processors do not necessarily perform the same operating-system responsibilities.
One processor may act as a master and handle scheduling or other system tasks, while other processors execute work assigned to them.
Symmetric Multiprocessing
In symmetric multiprocessing, processors participate more equally.
Each processor may execute operating-system code and participate in scheduling, subject to the operating system's implementation.
Asymmetric Multiprocessing Example
Scheduler + Control
Symmetric Multiprocessing Example
Asymmetric vs Symmetric Multiprocessing
| Point | Asymmetric Multiprocessing | Symmetric Multiprocessing |
|---|---|---|
| Control | One processor may have a special master/control role | Processors can participate more equally |
| Scheduling | Master processor may control task assignment | Scheduling work can be distributed |
| Complexity | Conceptually simpler central control | Requires coordination among CPUs and shared kernel data |
| Scalability | Master can become a bottleneck | Better suited to general multiprocessor scaling |
Global Run Queue vs Per-CPU Run Queue
A major design question in multiprocessor scheduling is: Where should runnable tasks wait?
Global Run Queue
All runnable tasks can conceptually wait in one shared queue or shared scheduling structure.
This can make work distribution conceptually easy, but a heavily shared scheduling structure may create contention as the processor count grows.
Per-CPU Run Queues
Each CPU keeps its own runnable-task queue.
This can reduce contention and improve locality, but now the operating system must make sure the queues do not become badly unbalanced.
Processor Affinity in Multiprocessor Scheduling
Suppose a process runs on CPU 2. While it runs, useful instructions and data may enter CPU 2's caches.
If the scheduler immediately moves that process to CPU 0, CPU 0 may not have the same useful cached data.
For this reason, operating systems often try to keep a task on the same CPU when practical. This idea is called processor affinity or CPU affinity.
Processor affinity is the tendency or restriction that keeps a process or thread running on a particular CPU or set of CPUs.
✓ preferred
Its useful code and data may already be present in CPU 1's cache.
CPU 1 may become overloaded while another allowed processor is idle.
cache locality vs load balancing.
Soft Affinity vs Hard Affinity
Soft Processor Affinity
The scheduler tries to keep a task on the same processor when practical, but the task may still migrate if scheduling conditions require it.
Hard Processor Affinity
A task is explicitly restricted to a selected CPU or set of CPUs through an affinity mask or similar mechanism.
Why Can Processor Migration Be Expensive?
Stay on CPU 1
The process may reuse useful data already stored in CPU 1's cache.
Warm CacheMove to CPU 3
CPU 3 may need to fetch the process's working data again.
Possible Locality CostTherefore, moving a process simply because another CPU is slightly less busy is not always free.
Multiprocessor scheduling is a trade-off between load distribution and locality.
Load Balancing in Multiprocessor Scheduling
Load balancing in Operating System means distributing runnable work across processors so that some CPUs do not remain heavily overloaded while others remain unnecessarily idle.
Push Migration and Pull Migration
Textbooks commonly explain multiprocessor load balancing using two ideas: push migration and pull migration.
Push Migration
A scheduler or balancing mechanism notices that one processor is overloaded and moves some runnable work away from it.
The work is effectively pushed away from the busy processor.
Pull Migration
An idle or lightly loaded processor looks for runnable work available on another processor.
The idle processor effectively pulls work toward itself.
Push Migration vs Pull Migration
| Point | Push Migration | Pull Migration |
|---|---|---|
| Triggered By | Overloaded side / balancing mechanism | Idle or underloaded processor |
| Main Idea | Move tasks away from busy CPU | Bring runnable tasks to idle CPU |
| Goal | Improve distribution of runnable work | |
Multiprocessor Scheduling Example With Two CPUs
Let us understand the basic idea with a simple example.
Assume all four processes arrive at time 0 and we have two identical CPUs.
Step 1
At time 0, both CPUs are free. CPU 0 can start P1 while CPU 1 starts P2.
Step 2
P2 finishes at time 4, so CPU 1 can immediately start P3.
Step 3
P1 finishes at time 6. P4 can then run on CPU 0.
This simple example is not meant to represent every real multiprocessor scheduler. It only shows the important idea: different tasks can execute simultaneously on different processors.
Multiprocessor Scheduling and Multicore Processors
Modern systems often contain several CPU cores inside one physical processor package.
From a scheduling point of view, these cores provide multiple execution resources, although their caches and hardware topology may differ.
Multicore Processor
One physical processor package may contain several execution cores.
Logical CPUs / SMT
Some physical cores can expose more than one hardware execution context. This is commonly called Simultaneous Multithreading (SMT).
How SMT Affects Scheduling
Two logical CPUs that belong to the same physical core may share some underlying core resources.
Therefore, two logical CPUs are not always equivalent to two completely independent physical cores in performance.
A topology-aware scheduler can consider relationships between:
- logical hardware threads,
- physical cores,
- shared caches,
- processor packages,
- and NUMA nodes.
NUMA and Multiprocessor Scheduling
On larger systems, memory access time may depend on which processor accesses which memory.
This architecture is called Non-Uniform Memory Access (NUMA).
CPU 0 may access memory in Node 0 more efficiently than memory attached to another NUMA node.
Therefore, a scheduler may try to keep a task near the memory it frequently uses. This is called maintaining NUMA locality.
Processor Affinity and NUMA Locality
Processor affinity becomes even more important on NUMA systems.
Moving a process from one NUMA node to another may place the process far from the memory pages it frequently accesses.
A scheduler therefore has to consider:
Linux documentation notes that its scheduler understands NUMA topology and tries to reduce unnecessary movement across distant scheduling domains, while administrators can also use affinity and NUMA policies to influence placement. :contentReference[oaicite:1]{index=1}
What Is Gang Scheduling?
Some parallel applications contain a group of related threads that frequently communicate or synchronize with each other.
Gang scheduling is the idea of scheduling related threads to execute at the same time on different processors when possible.
→ CPU 0
→ CPU 1
→ CPU 2
→ CPU 3
The purpose is to reduce situations where one related thread is running while another thread it depends on is waiting for CPU time.
Homogeneous vs Heterogeneous Multiprocessor Scheduling
Homogeneous Processors
Processing units have similar capabilities. A task can usually run on any suitable processor.
Heterogeneous Processors
Processing units may have different performance, power or instruction capabilities. The scheduler may need to choose a processor that matches the task.
This becomes important in modern systems containing combinations of performance-oriented and efficiency-oriented cores.
Goals of Multiprocessor Scheduling
Load Balancing vs Processor Affinity
These two goals can sometimes conflict.
Load Balancing Says
Move a task from an overloaded CPU to an idle CPU.
Affinity Says
Keep the task on its current CPU because its cache and memory locality may be useful.
Task Migration in Multiprocessor Scheduling
When a task moves from one processor's scheduling context to another processor, this is called task migration or processor migration.
Migration may happen because:
- the current CPU is overloaded,
- another CPU becomes idle,
- affinity rules change,
- system topology or power policy changes,
- or a scheduler decides another placement is better.
How Real Operating Systems Handle CPU Placement
Real schedulers are much more advanced than simple classroom diagrams.
For example, Linux organizes CPUs into scheduling domains that represent groups across which load balancing can occur. The scheduler can redistribute tasks when processors become unevenly loaded, while affinity and cpuset rules restrict where a task is allowed to run. :contentReference[oaicite:2]{index=2}
Linux also exposes CPU affinity controls. An affinity mask specifies the CPUs on which a thread is eligible to execute, and changing the mask can cause a thread to migrate if it is currently running on a disallowed CPU. :contentReference[oaicite:3]{index=3}
Why Doesn't the OS Keep Every CPU Exactly Equally Loaded?
Perfect equality can actually cost more than it saves.
Imagine CPU 0 has slightly more work than CPU 1. Moving a process just to make the load numbers identical may:
So the goal is normally useful balance, not mathematical perfection.
Performance Factors in Multiprocessor Scheduling
Common Mistakes Students Make
The scheduler also has to decide processor placement.
That description belongs more closely to asymmetric multiprocessing.
Different processes can create very different CPU loads.
Migration can reduce cache and memory locality.
Soft affinity is a preference; hard affinity explicitly restricts eligible CPUs.
Multiple physical cores and multiple hardware threads on one core are different concepts.
On larger systems, memory location can affect the quality of CPU placement.
Complete Multiprocessor Scheduling Flow
Multiprocessor Scheduling Exam Preparation
For a 2-Mark Question
Answer: Multiprocessor scheduling is the process of scheduling runnable tasks across two or more processors or CPU cores. The operating system decides which task should execute and on which processor.
For a 5-Mark Question
Explain:
- definition of multiprocessor scheduling
- Asymmetric Multiprocessing
- Symmetric Multiprocessing
- processor affinity
- load balancing
For a 10-Mark Question
Write in this order:
- meaning of Multiprocessor Scheduling in Operating System
- single-processor vs multiprocessor scheduling
- AMP and SMP
- global vs per-CPU run queues
- processor affinity
- soft and hard affinity
- load balancing
- push migration
- pull migration
- multicore and SMT scheduling
- NUMA locality
- migration cost
- simple multiprocessor example
Important Diagram
In a long-answer question, draw either:
- AMP master-worker diagram,
- SMP CPU scheduling diagram,
- processor affinity diagram,
- or push/pull load balancing diagram.
Multiprocessor Scheduling Practice Questions
Multiprocessor Scheduling Quick Revision
Frequently Asked Questions About Multiprocessor Scheduling
What is Multiprocessor Scheduling in Operating System?
Multiprocessor scheduling is the operating-system process of assigning and scheduling runnable tasks across multiple processors, cores or logical CPUs.
Why is multiprocessor scheduling needed?
It is needed because when several processors are available, the operating system must decide not only which task should run but also where that task should run.
What is Asymmetric Multiprocessing?
In asymmetric multiprocessing, one processor may have a special master or control role, while other processors perform work assigned to them.
What is Symmetric Multiprocessing?
Symmetric multiprocessing is a design in which processors participate more equally in running tasks and operating-system work.
What is processor affinity?
Processor affinity is the preference or restriction that keeps a process or thread on a particular processor or set of processors.
What is soft processor affinity?
Soft affinity means the scheduler tries to keep a task on the same processor for locality, but the task may still move when required.
What is hard processor affinity?
Hard affinity explicitly restricts a task to a defined CPU or set of CPUs.
What is load balancing in multiprocessor scheduling?
Load balancing is the process of distributing runnable work across CPUs so that some processors do not remain heavily overloaded while other eligible processors remain unnecessarily idle.
What is push migration?
Push migration happens when work is moved away from an overloaded processor toward another processor.
What is pull migration?
Pull migration happens when an idle or underloaded processor takes runnable work from another processor.
What is the difference between processor affinity and load balancing?
Processor affinity tries to preserve useful task placement, while load balancing may move a task to improve distribution of processor load.
What is task migration in Operating System?
Task migration means moving a runnable process or thread from one processor's scheduling context to another processor.
What is a global run queue?
A global run queue is a shared scheduling structure from which multiple processors can obtain runnable work.
What are per-CPU run queues?
Per-CPU run queues mean each CPU maintains its own runnable-task queue, with load balancing used when work becomes unevenly distributed.
Why is CPU affinity useful?
CPU affinity can preserve cache and memory locality by reducing unnecessary migration between processors.
What is NUMA in multiprocessor scheduling?
NUMA stands for Non-Uniform Memory Access. In NUMA systems, memory access cost can depend on which CPU accesses which memory node, so the scheduler may consider memory locality when placing tasks.
What is gang scheduling?
Gang scheduling is a technique in which related threads of a parallel application are scheduled to run together on different processors when possible.
Why is task migration not always good?
Migration can improve load balance, but it may also reduce cache locality, worsen NUMA locality and create additional scheduler overhead.
What is SMT in multiprocessor scheduling?
SMT stands for Simultaneous Multithreading. It allows one physical processor core to expose multiple hardware execution contexts that the operating system can see as logical CPUs.
Conclusion
Multiprocessor Scheduling in Operating System is more than simply giving work to several CPUs. The operating system must decide which task should run, which processor should run it, and whether moving the task will actually improve performance.
In Asymmetric Multiprocessing, one processor may perform a special control role. In Symmetric Multiprocessing, processors participate more equally. Modern systems commonly need additional ideas such as global or per-CPU run queues, processor affinity, load balancing, push migration and pull migration.
Processor affinity helps preserve cache locality, while load balancing tries to avoid overloaded and idle processors. These goals can conflict, which is why task migration must be used carefully.
On modern multicore and NUMA systems, the scheduler may also consider physical cores, logical CPUs, shared caches and memory locality. So the easiest way to remember the complete chapter is: multiprocessor scheduling = task selection + CPU placement + balance + locality.
