Introduction
Load balancing in an operating system means distributing runnable work across CPU cores. In a multicore system, the scheduler must decide not only which task should run, but also where it should run.
The main problem is imbalance. One core may have too much runnable work while another core is idle, causing wasted hardware, lower throughput, and higher waiting time.
What Load Balancing Means
Load balancing tries to keep CPU cores usefully busy. If all runnable work stays on one core, only that core makes progress while other cores contribute little or nothing.
This improves two important outcomes:
Throughput: More tasks can complete per unit time when more cores do useful work.
Latency: Runnable tasks wait less when they are not stuck behind a long queue on one overloaded core.
Moving Work Has a Cost
Load balancing often uses task migration. Migration means moving a runnable task from one CPU core to another.
Migration helps when it lets an idle or underused core do useful work. But it is not free because a task may have useful data in the cache of its previous core.
Benefit of Migration | Cost of Migration |
|---|---|
Uses idle CPU cores | Adds scheduler overhead |
Reduces waiting on overloaded cores | May lose useful cached data |
Improves parallel progress | Can increase cache misses |
Helps throughput | May hurt locality and latency |
A good scheduler does not move tasks just for the sake of movement. It moves work only when the benefit is likely to be greater than the cost.
Moving Work Has a Cost
What Load Actually Means
Load does not mean only the number of tasks. Two cores may have the same task count but very different real pressure.
Important signals include:
CPU usage: How busy a CPU has been.
Run queue length: How many runnable tasks are waiting for CPU time.
Sleeping or I/O-waiting tasks: Tasks waiting for disk, network, input, or another event.
Task behavior: Whether tasks are CPU-bound, interactive, or often blocked.
A task waiting for I/O is not currently competing for CPU, but it may become runnable again when the event completes. This is why load balancing needs more than one simple number.
Equal Task Count Is Not Enough
Equal distribution can still be a bad distribution. Suppose Core 0 gets three CPU-bound tasks, while Core 1 gets three tasks that sleep often.
The task count is equal, but the load is not balanced. Core 0 may stay busy for a long time, while Core 1 may become idle quickly.
A better scheduler considers workload behavior:
CPU-bound tasks: Need sustained CPU time.
Sleeping tasks: Frequently wait for I/O or events.
Latency-sensitive tasks: Need quick response.
Background tasks: Can often tolerate more delay.
The goal is useful balance, not perfect-looking task count.
Equal Task Count Is Not Enough
Push and Pull Migration
Push and pull migration are two simple ways to understand how imbalance can be corrected.
Migration Type | Meaning |
|---|---|
Push migration | An overloaded CPU sends runnable work to another CPU |
Pull migration | An idle CPU takes runnable work from a busy CPU |
In push migration, the busy CPU is active. It notices that it has too much work and tries to move some of it away.
In pull migration, the idle CPU is active. It looks for work from another CPU so it can stop sitting unused. Real schedulers may use both ideas along with more detailed checks.
Topology-Aware Load Balancing
Modern hardware is not a flat group of identical cores. CPU placement matters because cores, hardware threads, sockets, caches, and memory nodes can have different distances and costs.
A system may include:
Hardware threads: Multiple logical CPUs inside a core.
CPU cores: Physical execution units.
Sockets or packages: Physical CPU packages containing cores.
NUMA nodes: Groups where some memory is closer to some CPUs.
NUMA means Non-Uniform Memory Access. In a NUMA system, local memory access is cheaper than remote memory access. Moving a task across NUMA nodes may hurt performance if its memory remains closer to the old node.
Topology-Aware Load Balancing
Practical Load Balancing Signals
Load balancing issues often appear through system behavior rather than one perfect metric.
Common signals include:
Per-core CPU imbalance: Some cores are busy while others are idle.
High run queue length: Too many runnable tasks are waiting.
High context-switch rate: The CPU spends too much time switching.
High task migration count: Work may be moving too frequently.
Latency spikes under load: Response time becomes unstable when the system is busy.
These signals suggest that the scheduler may be dealing with uneven work distribution, excessive movement, or poor locality.
Summary
Load balancing in OS distributes runnable work across CPU cores so multicore systems can use hardware effectively. It improves throughput and latency when it prevents one core from being overloaded while others remain idle.
The important point is that load balancing is not just equal task count. A good scheduler considers CPU usage, run queue pressure, task behavior, cache locality, NUMA topology, and migration cost together.
Be the first to add a comment.