With multiple CPUs, scheduling involves another decision: not only which thread runs next, but also where it should run.

Suppose a server has eight logical CPUs and twelve runnable threads. Poor placement might leave one CPU idle while another has several threads waiting. Moving a thread to the idle CPU can improve throughput, but it may also discard useful cache data or place the thread farther from the memory it uses.

Multiprocessor scheduling coordinates runnable work across several CPUs while balancing three goals:

The challenge is that load balancing and locality often pull in opposite directions.

Scheduling discussions use CPU to mean a logical execution context on which the operating system can dispatch one thread.

A machine can contain:

The operating system may enumerate each hardware thread as a logical CPU:

Two logical CPUs on one core do not have the throughput of two separate cores. They share the core's execution resources, which is why the scheduler treats this tree as more than a flat list of four CPUs.

CPU 0 and CPU 1 can execute separate software threads at the same time, but if they are hardware threads of one core, they share some physical execution resources. Two logical CPUs are therefore not always equivalent to two independent physical cores.

The scheduler needs the machine's topology, not merely a flat CPU count.

Multiprocessor scheduling does not change the basic execution rule:

One logical CPU executes at most one software thread at an instant.

With four logical CPUs, at most four threads can execute simultaneously:

A thread may run on CPU 0 during one interval and CPU 2 later. That change is a CPU migration.

The scheduler operates on threads, not entire processes. A single-threaded process can use only one logical CPU at a time. A multithreaded process can execute several of its threads in parallel if they are runnable and the scheduler places them on different CPUs.

Adding CPUs cannot make one sequential thread execute several instructions at once. The workload must expose runnable parallelism.

Imagine two CPUs with separate ready queues:

If the CPUs never coordinate, CPU 1 remains idle while B, C, and D wait for CPU 0.

CPU 0 works through A, B, C, and D in turn while CPU 1 sits idle.

Each local scheduler can be correct according to its own queue while the machine as a whole wastes half its execution capacity.

Multiprocessor scheduling therefore needs a placement or balancing mechanism that considers more than one CPU.

Processes A and B each need six CPU units and are both allowed on either of two CPUs.

If both remain assigned to CPU 0:

The makespan is 12 units. Across the 12-unit interval, the machine provides:

Only 12 units perform work:

If B moves to CPU 1:

Both processes now finish at time 6 instead of one waiting for the other.

Both finish at time 6, and simplified machine-wide utilization is 100%.

This example assumes zero migration and coordination cost. Real placement decisions also consider whether B has warm state on CPU 0 and whether moving it is worth the locality loss.

Two broad organizational models explain who makes scheduling decisions.

Asymmetric multiprocessing

In asymmetric multiprocessing, one designated processor controls scheduling and often performs other operating-system work on behalf of the remaining processors:

The master CPU owns scheduling decisions, manages shared kernel state, and assigns work. The worker CPUs only execute the work they are assigned.

Central control simplifies synchronization because fewer CPUs modify scheduling structures. It can also create a bottleneck and a single point of dependence as CPU count grows.

Symmetric multiprocessing

In symmetric multiprocessing (SMP), CPUs participate as peers. Each CPU can enter the kernel, schedule work, and manage runnable tasks under shared coordination rules.

SMP scales better, but concurrent scheduling decisions require careful synchronization. Modern general-purpose multiprocessor systems primarily use symmetric designs.

SMP does not require every CPU to use one shared ready queue. Queue organization is a separate design decision.

The simplest shared design places all runnable tasks in one global queue:

Every CPU reaching into the same structure is what makes this design simple to reason about and expensive to run, because that one queue has to be protected against four simultaneous users.

When a CPU needs work, it selects from the shared runnable population.

Advantages

A global queue provides a natural machine-wide view:

Costs

The global data structure is shared by every CPU. Enqueueing, dequeueing, priority changes, and task wakeups require coordination.

As CPU count and scheduling frequency grow, the queue can suffer:

A global queue can also weaken affinity. Any available CPU may select a task, even if another CPU holds warmer cache state for it.

A scalable alternative gives each CPU its own run queue:

Each CPU usually selects from local state.

Advantages

Local queues reduce shared contention. Different CPUs can make scheduling decisions in parallel without constantly modifying one central structure.

They also support locality. A task can remain near the CPU where its instructions, data, and address translations may still be warm.

Costs

Local queues can become imbalanced:

The scheduler now needs load balancing to move eligible work between CPUs.

Per-CPU queues transform the problem:

Instead of contending on every scheduling decision, CPUs coordinate periodically or when imbalance becomes important.

Global and per-CPU queues are endpoints, not the only possibilities.

A scheduler can combine:

The purpose of a hybrid is to obtain local scalability without losing the ability to distribute work across the machine.

The core trade-off remains the same: frequent global coordination improves immediate balance but costs synchronization and locality.

Load balancing redistributes runnable work so that allowed CPUs receive appropriate amounts of work.

Starting from:

the balancer might migrate C:

Load balancing can happen at several moments:

The scheduler should not wait for extreme imbalance if an idle CPU can perform useful work, but checking every CPU on every event would itself be expensive.

Two useful mental models describe movement.

Push

A busy CPU or balancing mechanism detects excess local work and pushes a runnable task toward a less-loaded CPU:

CPU 0 holds A, B, and C, and pushes C to CPU 1.

Pull

An idle or lightly loaded CPU searches another queue and pulls eligible work:

CPU 1 has an empty queue, so it pulls B from CPU 0.

Pulling when a CPU becomes idle is sometimes called work stealing.

Real schedulers can use both ideas. Wakeup placement is another opportunity: rather than enqueueing a newly runnable task on an overloaded CPU and migrating it later, the scheduler can choose a suitable CPU immediately.

Consider:

CPU 1 has more tasks, but CPU 0 may have more sustained demand.

Task count alone ignores:

A scheduler therefore needs a load estimate, not merely a queue-length comparison.

Load estimates are imperfect because future behavior is unknown. Moving work based on a momentary spike can cause unnecessary migration if the imbalance disappears immediately afterward.

CPU affinity describes the CPUs on which a thread is allowed or preferred to run.

There are two related ideas.

Hard affinity

A thread has an allowed CPU mask:

The scheduler may choose CPU 0 or CPU 2, but not CPU 1 or CPU 3.

If the mask contains only CPU 0, the thread is commonly described as pinned to CPU 0.

Soft or natural affinity

Even when a thread is allowed everywhere, the scheduler may prefer its previous CPU because useful hardware state may remain there.

The preference can be overridden when another CPU offers a sufficiently better opportunity to run.

Hard affinity is a constraint. Soft affinity is a locality preference.

Suppose both A and B are restricted to CPU 0:

Even while B waits, the scheduler cannot move it to CPU 1:

CPU 0 alternates between A and B while CPU 1 stays idle.

The machine has spare capacity but no eligible work for CPU 1.

This is not a load-balancer bug. The affinity rule removes CPU 1 from the scheduler's legal choices.

Affinity is useful for measured locality or isolation needs, but overly narrow masks can create hotspots, reduce throughput, and worsen tail latency.

A CPU migration changes where a thread resumes. The kernel does not copy the thread's entire virtual address space to the new CPU.

The cost comes from several sources.

Direct scheduling work

The scheduler must safely remove the task from one CPU's runnable state and place it on another. Cross-CPU coordination may be required.

Cache locality

The old CPU may hold the task's recently used instructions and data in private caches. The destination CPU may need to fetch those lines again.

Some cache levels are shared between nearby CPUs, so moving within one core or socket may cost less than moving farther away.

Translation locality

The destination CPU may not have useful address-translation entries for the task, increasing translation misses while state warms.

Memory locality

On machines with multiple memory nodes, memory can be physically closer to one group of CPUs than another. Moving execution without moving data can increase memory-access latency.

Migration cost depends on topology and workload. It is not one constant value that applies to every task movement.

Consider a runnable task waiting behind another task on CPU 0 while CPU 1 is idle.

Keeping it on CPU 0 preserves affinity:

Migrating it to CPU 1 improves balance:

For a long CPU burst, immediate parallel execution usually has time to repay the migration cost. For a task that needs only a few microseconds, it may finish sooner by waiting briefly on its warm CPU.

Schedulers use heuristics because they do not know the task's exact future execution length or cache footprint.

The goal is not perfect balance at every instant:

Move work when the expected reduction in queueing delay justifies the coordination and locality cost.

An overly aggressive balancer can move a task repeatedly:

By the time each decision takes effect, the load may have changed again. The task pays repeated locality costs without obtaining a stable execution opportunity.

This behavior is sometimes described as task bouncing.

A scheduler can reduce it by:

These safeguards accept short-lived imbalance to improve overall stability.

Not all destination CPUs have the same migration cost or execution capacity.

Consider a system with two physical cores, each exposing two logical CPUs:

If one CPU-bound task already runs on CPU 0, placing another on CPU 2 may provide more independent core resources than placing it on sibling CPU 1.

On a multi-socket system, moving within the same socket may preserve more shared cache and memory locality than moving across sockets.

Some systems also contain cores with different performance or energy characteristics. A numerically equal queue length can still represent unequal available capacity.

Topology-aware scheduling therefore considers:

The details are hardware-specific, but the principle is general: CPU identifiers are not a map of interchangeable boxes.

On one CPU, a high-priority runnable task displaces a lower-priority task under preemptive priority scheduling.

On four CPUs, one high-priority task can run alongside three lower-priority tasks:

The lower-priority work does not need to stop while spare CPUs exist.

If five high-priority tasks become runnable, only four can run simultaneously. The scheduler must then decide which high-priority task waits, and lower-priority tasks may lose all CPUs.

Multiprocessor priority policy must answer both:

This is another reason a single-CPU timeline cannot simply be copied onto every CPU independently.

Suppose a server has eight logical CPUs.

If it has four runnable threads, all four may run simultaneously and four CPUs may remain idle. There is no CPU queueing merely because many other blocked threads exist.

If it has twenty CPU-bound runnable threads, the system is oversubscribed:

At least twelve are not executing at any given instant.

Oversubscription is not automatically a problem. Time-sharing is expected. It becomes costly when queueing delay, switching, cache interference, or throughput no longer meets the workload's goals.

Adding application threads beyond CPU count helps only when enough of them block or when additional concurrency serves another measured purpose. CPU-bound threads cannot create more execution capacity.

Multiprocessor measurements need an explicit scope.

For one CPU:

For m CPUs:

This conventional calculation treats each logical CPU as one unit of schedulable capacity. Hardware-thread sharing and unequal core performance mean that equal percentages do not always represent equal amounts of physical work.

An average of 50% on a two-CPU machine can mean:

or:

The average is identical, but the first pattern may indicate constrained or imbalanced work.

Useful observations include:

A machine-wide average can hide a severe hotspot.

Display the logical CPUs available to the current environment:

Inspect their topology:

A typical fragment might look like:

Here, CPU 0 and CPU 1 are logical CPUs associated with the same core. Exact columns depend on the architecture and virtual-machine configuration.

Show the CPU on which each thread was last observed:

PSR identifies a logical CPU. It is a snapshot, not permanent placement; an unrestricted thread can migrate immediately after the command reads its state.

Show the current shell's allowed CPU list:

Typical output:

Linux also exposes the mask through /proc:

Example:

The hexadecimal mask and list represent the same allowed CPUs.

CPU affinity applies to threads. For a multithreaded process, inspect individual thread IDs under:

The taskset -a option operates on all threads associated with a PID. Without it, changing one thread's affinity should not be assumed to update every thread in the process.

Use a Linux test machine with at least two allowed CPUs. Do not run this on a shared production host.

First find two CPU identifiers allowed to the shell:

For the clearest result, use lscpu to choose CPUs belonging to different physical cores when the environment permits. The following commands use CPU 0 and CPU 1; replace them if those CPUs are not allowed or are not the pair you selected.

Start two CPU-bound, single-threaded processes pinned to CPU 0:

Install cleanup immediately:

Observe placement and CPU use:

Both PSR values should show CPU 0. The processes time-share that CPU even if CPU 1 is otherwise idle.

Now restrict the second process to CPU 1:

Observe again:

The two processes can now execute in parallel on different CPUs. PSR should reflect the legal placement after each task runs. The %CPU column is averaged over process lifetime, so it may take time to reflect the new phase.

Clean up:

The experiment demonstrates two facts:

Affinity changes eligibility. They do not add CPU time or make a single thread execute on two CPUs simultaneously.

Carefully chosen affinity can be useful when measurements show that placement matters.

Examples include:

Affinity is not a universal optimization. Pinning every worker can prevent useful balancing when traffic changes or one worker blocks.

A fixed mapping that performs well at steady load may behave poorly during failures, uneven request distribution, or changes in CPU availability.

Use affinity to enforce an understood placement requirement, not merely because migration appears in a metric.

Multiprocessor scheduling decides both which runnable thread executes and which eligible CPU should execute it. A global queue offers a simple machine-wide view but can become a shared contention point; per-CPU queues improve scalability and locality but require load balancing.

Migration can reduce queueing and use idle capacity, while also imposing coordination, cache, translation, and memory-locality costs. Effective schedulers balance only when the expected benefit justifies those costs and respect each thread's CPU-affinity mask.

CPU topology, per-CPU utilization, runnable placement, and thread-level affinity all matter. Machine-wide averages can hide a busy-CPU hotspot, and adding CPUs helps only when the workload exposes enough runnable parallelism.