What is Load Balancing in a Multiprocessor OS?
Learn how multiprocessor OS load balancing works — push vs pull migration and cache-affinity cost — with an interview-ready explanation.
Expected Interview Answer
Load balancing in a multiprocessor OS is the scheduler policy of spreading runnable tasks evenly across all available CPU cores so no core sits idle while another core has a backlog of ready processes waiting.
Each core typically keeps its own local ready queue for cache-friendliness, so imbalance can appear when some cores finish their work early while others stay overloaded. Push migration has a periodic task check core loads and move threads from busy queues to idle ones, while pull migration lets an idle core actively steal work from a busy core the moment it goes idle. Real schedulers such as the Linux Completely Fair Scheduler combine both: periodic rebalancing catches slow drift, and idle-core work stealing catches sudden imbalance immediately. The tradeoff is always migration cost versus imbalance cost — moving a thread to another core can invalidate its cache lines and force a costlier memory fetch, so schedulers only migrate when the imbalance is large enough to be worth that cost.
- Keeps all CPU cores utilized instead of some idling while others queue up
- Improves overall system throughput and reduces average wait time
- Distinguishes push migration (periodic rebalance) from pull migration (work stealing)
- Forces engineers to reason about cache-affinity cost versus imbalance cost
AI Mentor Explanation
Load balancing is like a franchise splitting net-practice sessions across four bowling lanes: if three lanes are backed up with players waiting while one lane sits empty, the coach reassigns some waiting players to the empty lane rather than letting them queue needlessly. A coach who reassigns too eagerly wastes time re-briefing players on a new lane’s rhythm, so reassignment only happens once the queue imbalance is clearly worth the disruption. This mirrors how an OS scheduler weighs migration cost against the benefit of an idle core picking up work.
Step-by-Step Explanation
Step 1
Monitor per-core load
The kernel tracks each core’s ready-queue length or run-queue weight to detect imbalance.
Step 2
Detect imbalance
A periodic rebalance timer or an idle core going empty triggers a load-balancing check against other cores.
Step 3
Choose migration strategy
Push migration moves threads from an overloaded core; pull migration lets an idle core steal work from a busy one.
Step 4
Weigh migration cost
The scheduler only migrates a thread if the imbalance outweighs the cache-affinity cost of moving it to a cold core.
What Interviewer Expects
- A clear definition centered on distributing runnable tasks across cores
- Distinction between push migration and pull/work-stealing migration
- Awareness of cache-affinity cost as the reason migration is not always immediate
- A real-world example such as the Linux CFS load balancer
Common Mistakes
- Describing load balancing only as a network/distributed-systems concept and missing the OS-scheduler meaning
- Assuming the OS migrates threads constantly with no cost consideration
- Confusing load balancing with simple round-robin scheduling on one core
- Not knowing that per-core ready queues are the reason imbalance can occur at all
Best Answer (HR Friendly)
“Load balancing in an operating system means spreading the work across all the CPU cores so none of them sit idle while others are overloaded. The scheduler periodically checks how busy each core is and moves tasks around when needed, but it is careful not to move things too often because shifting a task to a new core loses the performance benefit of that core’s warm cache.”
Code Example
#define IMBALANCE_THRESHOLD 2
struct core {
int id;
int ready_queue_len;
};
/* Find the busiest and least busy core, migrate one task if imbalance is large */
void balance_load(struct core cores[], int n_cores) {
int busiest = 0, idlest = 0;
for (int i = 1; i < n_cores; i++) {
if (cores[i].ready_queue_len > cores[busiest].ready_queue_len) busiest = i;
if (cores[i].ready_queue_len < cores[idlest].ready_queue_len) idlest = i;
}
int imbalance = cores[busiest].ready_queue_len - cores[idlest].ready_queue_len;
if (imbalance >= IMBALANCE_THRESHOLD) {
migrate_one_task(busiest, idlest); /* pay cache-affinity cost only if worth it */
cores[busiest].ready_queue_len--;
cores[idlest].ready_queue_len++;
}
}Follow-up Questions
- What is the difference between push migration and pull (work-stealing) migration?
- Why is cache affinity a cost when migrating a thread between cores?
- How does the Linux Completely Fair Scheduler perform load balancing across cores?
- How does load balancing interact with NUMA architectures?
MCQ Practice
1. What does load balancing in a multiprocessor OS primarily aim to do?
Load balancing spreads ready tasks across cores so no core is idle while another has a backlog.
2. What is “pull migration” in load balancing?
Pull migration (work stealing) happens when an idle core reaches out and takes work from a busier core rather than waiting for a periodic push.
3. Why does a scheduler avoid migrating threads too frequently?
Moving a thread to a different core loses its cache locality, so migration is only done when the imbalance outweighs that cost.
Flash Cards
What is load balancing in a multiprocessor OS? — Distributing runnable tasks evenly across all CPU cores to avoid idle cores while others queue up.
Push vs pull migration? — Push: periodic rebalance moves tasks from busy cores. Pull: an idle core actively steals work from a busy one.
Why is migration not free? — Moving a thread to a new core invalidates its warm cache lines, costing performance.
Name a real scheduler that does load balancing. — The Linux Completely Fair Scheduler (CFS) load balancer.