Multiprocessor Scheduling (Advanced)

New Scheduling Duties in the Multicore Era

Chip designers can no longer raise single-core clock speeds without exploding power consumption, so they place several slower cores on one die. A sequential program occupies only one of those cores, forcing programmers to split work into threads. The OS now decides not only which thread runs next but also on which core it should run, creating a fresh tension between load balance and data locality.

How Per-Core Caches Break a Simple Memory View

Each core owns a small fast cache that holds recently touched data and instructions. After one core writes an address it may update only its own cache and delay the write-back to main memory; another core that immediately reads the same address can therefore obtain a stale value from DRAM. Hardware protocols such as bus snooping let caches notify one another of invalidations or updates so that a coherent shared-memory illusion is preserved. Software still cannot treat an ordinary load or store as atomic.

Locks and Affinity: Two Concerns a Scheduler Must Juggle

Even when hardware eventually restores coherence, concurrent modifications to the same list or queue still produce lost updates or double-frees. Shared structures therefore need mutexes. Those locks themselves become scalability bottlenecks. Meanwhile, once a thread has executed on a core that core’s cache is warm with its data; moving the thread elsewhere causes a flood of misses. A good multiprocessor scheduler therefore keeps a thread on its previous core (cache affinity) and migrates only when load imbalance becomes severe.

Pitfalls

• Believing extra cores automatically accelerate every sequential program
• Assuming hardware coherence makes locks unnecessary for shared queues
• Migrating threads constantly for perfect fairness and thereby flushing caches

Minimum C11 · complete program · Download .c

#include <stdio.h>

int main(void) {
    printf("Multiprocessor Scheduling Simulation\n");
    printf("====================================\n");
    printf("Assigning jobs considering cache affinity:\n");
    printf("CPU 0: JobA (initial placement)\n");
    printf("CPU 1: JobB (initial placement)\n");
    printf("CPU 0: JobC (affinity to previous cache)\n");
    printf("CPU 1: JobD (load balance)\n");
    printf("Note: Keeping jobs on same CPU preserves cache contents.\n");
    return 0;
}

Compile locally

gcc -std=c11 -Wall -Wextra -Wpedantic -Werror ostep-10-multiprocessor.c -o example && ./example

Expected result

Multiprocessor Scheduling Simulation
====================================
Assigning jobs considering cache affinity:
CPU 0: JobA (initial placement)
CPU 1: JobB (initial placement)
CPU 0: JobC (affinity to previous cache)
CPU 1: JobD (load balance)
Note: Keeping jobs on same CPU preserves cache contents.

CHECK YOUR UNDERSTANDING

Close the answer. Explain it.

A thread updates variable x on CPU 0 and is immediately migrated to CPU 1. What value might the first read on CPU 1 observe and why?

Check the sources

• OSTEP chapter PDF

Drafts and official chapters change. The version mark is only the example’s minimum.