Imagine 4 checkout lines (CPUs) at a shop. Each shopper (task) has their stuff already placed near one specific lane (that's the cache — their data is "warm" there). If one lane has a huge crowd and another is empty, you could send people to the empty lane — but they'd have to carry all their stuff over, which takes time. So the rule is simple: only move someone to a new lane if their wait in the old lane is longer than the hassle of carrying their stuff. That's load balancing (move to empty lanes) fighting affinity (stuff is warm where you are).
CPU Scheduling Basics — single-CPU algorithms this generalizes (RR, priority).
Cache Memory and Locality — why affinity matters (hot vs cold cache, working set).
NUMA Architectures — affinity extends to memory-node locality, not just cache.
Linux CFS Scheduler — real MQMS + periodic balancing (sched_domains, imbalance_pct).
Spinlocks and Lock Contention — why SQMS's single queue lock doesn't scale.
Context Switching Cost — migration cost M builds on switch + cache reload.
What are the two competing goals in multiprocessor scheduling?
Load balancing (keep all CPUs equally busy) vs. cache/processor affinity (keep a task on the same CPU so its data stays hot in cache).
Define processor affinity, soft vs hard.
Affinity = preference to keep a task on the CPU it last ran on for cache warmth. Soft: scheduler tries but may migrate. Hard: program forces a CPU set (e.g. sched_setaffinity); scheduler must obey.
What is the migrate-or-stay rule derived from costs?
Migrate iff W > M, where W = wait time saved on the busy CPU and M = migration cost including cold-cache reload penalty.
Push vs pull migration?
Push: a periodic task checks loads and pushes tasks off overloaded CPUs. Pull: an idle CPU pulls a waiting task from a busy CPU's queue.
SQMS — what is it and its drawbacks?
Single-Queue Multiprocessor Scheduling: one global ready queue. Drawbacks: lock contention (poor scaling) and no affinity.
MQMS — what is it and its drawback?
Multi-Queue: one ready queue per CPU; scalable + affinity-friendly but queues drift out of balance, needing explicit load balancing.
Why not balance until imbalance Δ = 0?
It causes migration thrashing — tasks ping-pong between CPUs, caches stay cold; balance only past a threshold (e.g. imbalance_pct ≈ 125%).
Why steal only waiting (not currently-running) tasks during pull migration?
The running task is cache-hot on its CPU; pulling a waiting task minimizes lost cache warmth.
When balancing, why migrate toward the mean rather than fully emptying the busy CPU?
Overshooting just creates reverse imbalance and extra migrations; moving toward mean load minimizes total migration cost.
Why does a single global queue (SQMS) fail to scale on many CPUs?
All CPUs contend for one queue lock, serializing the scheduler — the opposite of parallel speedup.
Dekho, jab ek hi CPU thi to scheduling simple thi — bas next task pick karo. Lekin multiprocessor (4, 8, 64 CPUs) mein do problem aati hain jo aapas mein ladti hain. Pehli cheez hai affinity: jab koi task CPU0 par chala, uska data CPU0 ke cache mein "garam" (hot) ho jaata hai. Agar use CPU3 par bhej do, to wahan cache "thanda" hai, RAM se dobara data laana padega — slow. Doosri cheez hai load balancing: agar saara kaam CPU0 par hai aur CPU3 khaali baitha hai, to throughput waste ho raha hai, isliye kaam ko spread karna padta hai.
Ab dono ek doosre ke khilaaf hain. Balance ke liye task ko move karoge to affinity (hot cache) marr jaata hai. Isliye rule yeh hai: migrate tabhi karo jab fayda nuksaan se zyada ho — yaani W>M, jahan W hai jitna wait time bachega busy CPU par, aur M hai migration ka cost (cache reload included). Agar CPU0 par sirf 2ms wait hai par migration 5ms ka padega, to mat hilao — bhale hi CPU3 khaali ho. Yeh sabse important insight hai.
Queue design do tarah ke hote hain. SQMS = ek hi global queue, sabki — automatically balanced par ek lock pe sab CPUs fight karti hain (scaling kharaab) aur affinity zero. MQMS = har CPU ki apni queue — fast, scalable, affinity-friendly, par queues imbalance ho jaati hain, isliye periodic load balancing chahiye (push migration = busy CPU se kaam hatao; pull migration = idle CPU khud kaam utha le). Real Linux (CFS) yahi MQMS + balancing use karta hai.
Exam aur real life dono ke liye 80/20 yaad rakho: per-CPU queues + occasional migration, sirf jab imbalance ek threshold cross kare (taaki migration thrashing na ho). Aur idle CPU ko sirf waiting task chura na chahiye, running hot task ko nahi. Bas itna samajh lo to topic clear hai.
