Multicore CPU Scheduling

Introduction

Earlier CPU scheduling discussions usually assume a single CPU core. In that model, the scheduler mainly answers one question: which ready task should run next?

Modern systems usually have multiple CPU cores. That changes scheduling because several tasks can truly run at the same time, so the scheduler must choose both the task and the core.

Why Multicore Scheduling Exists

On a single-core CPU, only one task executes at one exact instant. The system may feel like many tasks are active because the OS switches quickly, but the hardware is still running one task at a time.

On a multicore machine, different cores can run different tasks in parallel. This improves throughput and responsiveness, but it also creates new scheduling questions:

• Task choice: Which runnable task should execute?

• Core choice: Which CPU core should run it?

• Load balance: Is one core overloaded while another is idle?

• Migration: Should a task move to another core?

• Locality: Will moving the task hurt cache performance?

Single-Core vs Multicore Scheduling

Per-Core Run Queues

A per-core run queue stores runnable tasks for one CPU core. Instead of every core competing for one shared global queue, each core can make local scheduling decisions from its own queue.

This improves scalability because the scheduler avoids constant contention on one shared structure. It also makes local task selection faster on systems with many cores.

Per-core run queues have clear benefits:

• Less contention: Cores do not always fight over one global queue.

• Faster local decisions: Each core can pick from its own runnable tasks.

• Better scalability: The design works better as core count grows.

The weakness is imbalance. One core may have many runnable tasks while another core becomes idle, so per-core queues need load balancing.

Load Balancing and Task Migration

Load balancing tries to spread work across CPU cores. If one core is busy and another core is idle, the scheduler may migrate a runnable task to the idle core.

Task migration helps because it can use idle cores, reduce waiting time and improve throughput.

Migration is useful, but it is not free. Moving a task can add overhead and may reduce cache locality, so a good scheduler does not move tasks unnecessarily.

Cache Locality and Processor Affinity

CPU caches store recently used data. If a task runs again on the same core, some of its useful data may still be in that core’s cache.

This is called good cache locality. It can reduce cache misses and help the task run faster.

This creates the main multicore scheduling tradeoff. Load balancing wants to move tasks toward idle cores, while cache locality prefers keeping tasks where their useful data is already warm.

Multicore Scheduling and Concurrency

Multicore systems also make concurrency problems more visible. Multiple threads can run at the same time on different cores and access shared data at the same time.

For example, suppose only one movie seat is left. Thread A and Thread B both check the seat at the same time, and both see it as available. If both continue without synchronization, both may reserve the same seat.

This is a race condition because the result depends on timing. More true parallelism creates more possible execution interleavings, so shared data must be handled carefully using synchronization techniques.

Summary

Multicore scheduling exists because modern systems have multiple CPU cores. The scheduler must decide not only which task should run, but also which core should run it.

Per-core run queues improve scalability, task migration improves load balancing, and cache locality improves performance when tasks stay near useful cached data. The central challenge is balancing load distribution with locality while also handling the concurrency risks created by true parallel execution.