6a:T42a,In multiprocessor systems, the fundamental promise of parallelism—multiple CPUs working simultaneously to achieve greater throughput—can be undermined by a deceptively simple problem: **load imbalance**. When some processors are overwhelmed with work while others sit idle, the system fails to realize its full potential, wasting both computational resources and power. **Push migration** represents one of the most intuitive and widely-deployed solutions to this problem. It embodies a proactive philosophy: when a processor detects that it is overloaded relative to its peers, it actively 'pushes' excess tasks to less-loaded processors, redistributing work before the imbalance becomes severe. This page provides a comprehensive exploration of push migration—its mechanisms, implementation strategies, performance characteristics, and role in modern operating system schedulers. By the end, you will understand not just *how* push migration works, but *when* it is the optimal choice and *why* it behaves the way it does under various workload conditions.6b:T40a,To understand push migration deeply, we must first appreciate the operating environment it addresses and the specific problem it solves. **The Multiprocessor Scheduling Context** In symmetric multiprocessing (SMP) systems, each CPU maintains its own run queue—a data structure containing processes ready to execute. The scheduler on each CPU independently selects the next process to run from its local queue. This per-CPU queue architecture is essential for: - **Scalability** — Avoiding a single global lock that would become a bottleneck as processor count increases - **Cache affinity** — Keeping processes on the same CPU to benefit from warm caches - **Reduced latency** — Enabling scheduling decisions without cross-CPU communication However, this distributed design introduces a fundamental challenge: run queues can become unbalanced. One CPU might have 20 runnable processes while another has none. Without intervention, the overloaded CPU cannot make progress on all its tasks, while the idle CPU wastes cycles.6c:T59d,**The Push Migration Philosophy** Push migration addresses imbalance through a **proactive, sender-initiated** approach. The core concept is elegantly simple: 1. **Detection** — Each CPU periodically monitors its own load relative to the system average or specific thresholds 2. **Decision** — When a CPU determines it is significantly overloaded, it identifies tasks suitable for migration 3. **Transfer** — The overloaded CPU actively moves selected tasks to less-loaded processors 4. **Continuation** — The migrated tasks resume execution on their new CPUs This 'push' terminology reflects the direction of agency: the **overloaded processor initiates** the migration, pushing work away from itself. This contrasts with 'pull' migration where idle processors request work from busy ones. **Formal Definition** We can define push migration formally as follows: *Push migration is a load balancing mechanism in which a processor P, upon detecting that its local load L(P) exceeds a threshold T, selects one or more tasks from its run queue and transfers them to processors whose load is below T, thereby reducing L(P) and increasing utilization of underloaded processors.* The elegance of this definition belies the complexity of implementation: What constitutes 'load'? How is the threshold determined? Which tasks should be migrated? How do we avoid thrashing? These questions drive the detailed design we explore next.6d:T4e5,/* Simplified representation of per-CPU run queue components */ struct run_queue { /* Core scheduling structures */ struct list_head tasks; /* List of runnable tasks */ unsigned int nr_running; /* Number of runnable tasks */ unsigned int nr_waiting; /* Tasks waiting for I/O */ /* Load tracking for balancing decisions */ unsigned long load_weight; /* Weighted load (priority-adjusted) */ unsigned long avg_load; /* Running average over time */ unsigned long cpu_capacity; /* This CPU's processing capacity */ /* Push migration specific fields */ int overloaded; /* Flag: is this CPU overloaded? */ int push_count; /* Tasks pushed in current interval */ unsigned long last_push_time; /* Timestamp of last push attempt */ /* Locking and synchronization */ spinlock_t lock; /* Protects queue modifications */ int migration_disabled; /* Temporarily prevent migrations */ /* Migration target tracking */ cpumask_t idle_siblings; /* Known idle CPUs in local domain */ int busy_idx; /* Index for scanning busy CPUs */ };6e:T541,/* Priority-to-weight mapping (simplified from Linux CFS) */ static const int priority_to_weight[40] = { /* -20 */ 88761, 71755, 56483, 46273, 36291, /* -15 */ 29154, 23254, 18705, 14949, 11916, /* -10 */ 9548, 7620, 6100, 4904, 3906, /* -5 */ 3121, 2501, 1991, 1586, 1277, /* 0 */ 1024, 820, 655, 526, 423, /* 5 */ 335, 272, 215, 172, 137, /* 10 */ 110, 87, 70, 56, 45, /* 15 */ 36, 29, 23, 18, 15, }; /* Calculate weighted load for a run queue */ unsigned long calculate_weighted_load(struct run_queue *rq) { unsigned long total_weight = 0; struct task_struct *task; list_for_each_entry(task, &rq->tasks, run_list) { int priority = task->static_prio - 100; /* Normalize to 0-39 */ if (priority < 0) priority = 0; if (priority > 39) priority = 39; total_weight += priority_to_weight[priority]; } return total_weight; } /* Calculate exponential moving average for stability */ unsigned long update_load_average(struct run_queue *rq, unsigned long new_load) { /* Classic EMA: new_avg = alpha * new + (1-alpha) * old */ /* Using fixed-point: (new * 4 + old * 12) / 16 */ rq->avg_load = (new_load * 4 + rq->avg_load * 12) >> 4; return rq->avg_load; }6f:T633,/* Main push migration entry point - called from timer interrupt */ void try_to_push_tasks(struct run_queue *this_rq) { int this_cpu = smp_processor_id(); struct migration_context ctx; int nr_pushed = 0; /* Phase 1: Quick check - any point in pushing? */ if (!should_attempt_push(this_rq)) { return; /* Not overloaded or no migration needed */ } /* Acquire local runqueue lock */ spin_lock(&this_rq->lock); /* Phase 2: Detailed analysis */ if (!calculate_push_imbalance(this_rq, &ctx)) { spin_unlock(&this_rq->lock); return; /* No actionable imbalance */ } /* Phase 3: Find destination CPUs and candidate tasks */ while (ctx.imbalance > 0 && nr_pushed < MAX_PUSH_PER_CYCLE) { struct task_struct *task; int dst_cpu; /* Find a suitable destination CPU */ dst_cpu = find_push_destination(this_rq, &ctx); if (dst_cpu < 0) { break; /* No suitable destinations available */ } /* Select a task to migrate */ task = select_task_for_push(this_rq, dst_cpu, &ctx); if (!task) { break; /* No suitable tasks to migrate */ } /* Phase 4: Execute the migration */ if (migrate_task_to_cpu(task, dst_cpu)) { ctx.imbalance -= task_load_weight(task); nr_pushed++; this_rq->push_count++; } } spin_unlock(&this_rq->lock); /* Update statistics */ update_push_statistics(this_cpu, nr_pushed); }70:T498,/* Quick pre-check to avoid unnecessary work */ static bool should_attempt_push(struct run_queue *rq) { /* Need at least 2 runnable tasks to push one away */ if (rq->nr_running < 2) { return false; } /* Check if we've pushed recently (prevent thrashing) */ if (time_before(jiffies, rq->last_push_time + PUSH_MIN_INTERVAL)) { return false; } /* Check if system has any idle CPUs worth pushing to */ if (cpumask_empty(&rq->idle_siblings)) { /* No known idle CPUs - do detailed scan only periodically */ if (!time_to_rescan_idle_cpus(rq)) { return false; } } /* Basic weighted load check */ if (rq->load_weight <= avg_load_per_cpu() * PUSH_THRESHOLD_PCT / 100) { return false; /* Not overloaded relative to average */ } return true; /* Worth doing detailed analysis */ } /* Constants governing push behavior */ #define PUSH_MIN_INTERVAL (HZ / 10) /* Max 10 push attempts/second */ #define PUSH_THRESHOLD_PCT 125 /* 25% above average triggers push */ #define MAX_PUSH_PER_CYCLE 2 /* Limit work per cycle */71:T4d9,/* Detailed imbalance calculation */ static bool calculate_push_imbalance(struct run_queue *rq, struct migration_context *ctx) { unsigned long this_load = rq->avg_load; unsigned long target_load; unsigned long system_load = 0; int nr_online_cpus = 0; int cpu; /* Calculate system-wide load */ for_each_online_cpu(cpu) { system_load += per_cpu(runqueues, cpu).avg_load; nr_online_cpus++; } /* Target: each CPU should have average load */ target_load = system_load / nr_online_cpus; /* Imbalance is how much we exceed target */ if (this_load <= target_load) { return false; /* We're at or below average - no push needed */ } ctx->imbalance = this_load - target_load; /* Apply minimum threshold to prevent trivial migrations */ if (ctx->imbalance < MIN_PUSH_IMBALANCE) { return false; } /* Adjust for migration cost - don't push if benefit is marginal */ if (ctx->imbalance < estimated_migration_cost()) { return false; } ctx->this_load = this_load; ctx->target_load = target_load; ctx->system_load = system_load; return true; }72:Te55,/* Find the best destination CPU for pushing a task */ static int find_push_destination(struct run_queue *src_rq, struct migration_context *ctx) { int best_cpu = -1; unsigned long best_capacity = 0; int cpu; /* Priority 1: Check for any idle CPUs in same NUMA node */ for_each_cpu(cpu, &src_rq->idle_siblings) { if (cpu_is_same_numa_node(src_rq, cpu)) { struct run_queue *dst_rq = &per_cpu(runqueues, cpu); if (dst_rq->nr_running == 0) { /* Perfect match: idle CPU on same NUMA node */ return cpu; } } } /* Priority 2: Any idle CPU (cross-NUMA if necessary) */ for_each_cpu(cpu, &src_rq->idle_siblings) { struct run_queue *dst_rq = &per_cpu(runqueues, cpu); if (dst_rq->nr_running == 0) { return cpu; } } /* Priority 3: Find least-loaded CPU that's below average */ for_each_online_cpu(cpu) { struct run_queue *dst_rq = &per_cpu(runqueues, cpu); unsigned long available_capacity; if (cpu == smp_processor_id()) { continue; /* Don't push to self */ } /* Skip CPUs at or above average load */ if (dst_rq->avg_load >= ctx->target_load) { continue; } /* Calculate how much load this CPU can accept */ available_capacity = ctx->target_load - dst_rq->avg_load; if (available_capacity > best_capacity) { best_capacity = available_capacity; best_cpu = cpu; } } return best_cpu; } /* Select a task suitable for migration to given destination */ static struct task_struct *select_task_for_push(struct run_queue *rq, int dst_cpu, struct migration_context *ctx) { struct task_struct *best_task = NULL; struct task_struct *task; int best_score = INT_MIN; list_for_each_entry(task, &rq->tasks, run_list) { int score = 0; /* Skip tasks that cannot migrate */ if (!task_can_migrate(task, dst_cpu)) { continue; } /* Prefer cache-cold tasks (haven't run recently) */ if (task_cache_cold(task)) { score += 100; } /* Prefer tasks with weak CPU affinity */ if (task_has_weak_affinity(task)) { score += 50; } /* Prefer lower priority tasks (less latency-sensitive) */ score += (MAX_PRIO - task->prio); /* Prefer tasks whose load contribution matches our needs */ if (task_load_weight(task) <= ctx->imbalance * 2) { score += 25; /* Right size for our imbalance */ } if (score > best_score) { best_score = score; best_task = task; } } return best_task; } /* Check if a task can legally migrate to a given CPU */ static bool task_can_migrate(struct task_struct *task, int dst_cpu) { /* Check CPU affinity mask */ if (!cpumask_test_cpu(dst_cpu, &task->cpus_allowed)) { return false; } /* Check if task requested migration disabled */ if (task->migration_disabled) { return false; } /* Currently running tasks cannot migrate */ if (task_running(task)) { return false; } /* Kernel threads with CPU bindings */ if (task_is_bound_kthread(task)) { return false; } return true; }73:T4c1,/* Execute the migration of a task to a new CPU */ static bool migrate_task_to_cpu(struct task_struct *task, int dst_cpu) { struct run_queue *src_rq = task_rq(task); struct run_queue *dst_rq = &per_cpu(runqueues, dst_cpu); /* Double-lock ordering to prevent deadlock */ /* Always lock lower-numbered CPU first */ if (dst_cpu < smp_processor_id()) { spin_lock(&dst_rq->lock); } /* Dequeue from source */ dequeue_task(src_rq, task); /* Update task's CPU assignment */ task->cpu = dst_cpu; /* Enqueue on destination */ enqueue_task(dst_rq, task); /* Update load tracking */ src_rq->load_weight -= task_load_weight(task); dst_rq->load_weight += task_load_weight(task); src_rq->nr_running--; dst_rq->nr_running++; /* Release destination lock if we took it */ if (dst_cpu < smp_processor_id()) { spin_unlock(&dst_rq->lock); } /* Record migration for statistics */ record_migration(smp_processor_id(), dst_cpu, task); /* Send IPI to wake destination CPU if it was idle */ if (need_resched_cpu(dst_cpu)) { send_reschedule_ipi(dst_cpu); } return true; }74:T9eb,/* NUMA-aware destination selection for push migration */ static int find_numa_aware_destination(struct run_queue *src_rq, struct migration_context *ctx) { int src_cpu = rq_cpu(src_rq); struct sched_domain *sd; int best_cpu = -1; /* Walk up the domain hierarchy, starting local */ for_each_domain(src_cpu, sd) { struct sched_group *sg = sd->groups; int found_in_domain = false; /* Scan scheduling groups within this domain */ do { int cpu; for_each_cpu(cpu, sched_group_cpus(sg)) { struct run_queue *dst_rq = &per_cpu(runqueues, cpu); if (cpu == src_cpu) continue; /* Check if this CPU can accept work */ if (dst_rq->avg_load < ctx->target_load) { /* At lower domains (closer), prefer any available */ /* At higher domains (NUMA), require significant benefit */ unsigned long domain_cost = domain_migration_cost(sd); unsigned long benefit = ctx->imbalance; if (benefit > domain_cost) { best_cpu = cpu; found_in_domain = true; /* Prefer idle CPUs */ if (dst_rq->nr_running == 0) { return cpu; /* Perfect match at this level */ } } } } sg = sg->next; } while (sg != sd->groups); /* If we found a candidate at this level, use it */ /* Prevents unnecessary promotion to higher (costlier) domains */ if (found_in_domain && best_cpu >= 0) { return best_cpu; } } return best_cpu; /* May be -1 if no suitable destination */ } /* Estimate cost of migrating across a scheduling domain */ static unsigned long domain_migration_cost(struct sched_domain *sd) { /* Base cost increases with domain level */ unsigned long base_cost = sd->level * 1000; /* NUMA domains have additional memory latency cost */ if (sd->flags & SD_NUMA) { base_cost += numa_remote_access_penalty(); } /* Factor in domain's historical migration success rate */ base_cost = base_cost * sd->migration_success_rate / 100; return base_cost; }75:T484,Linux's Completely Fair Scheduler (CFS) provides a production-grade implementation of push migration that has been refined over two decades of deployment on systems ranging from smartphones to supercomputers. Examining its design reveals practical solutions to the theoretical challenges we've discussed. **CFS Load Balancing Overview** CFS integrates push migration into a broader load balancing framework triggered by timer interrupts. The `run_rebalance_domains()` function, invoked periodically, walks the scheduling domain hierarchy and calls `load_balance()` for domains requiring intervention. **Key CFS Concepts for Push** 1. **Load Weight** — CFS uses PELT (Per-Entity Load Tracking) to compute temporally-decayed load for each task, accounting for both recent CPU usage and historical patterns. 2. **Scheduling Domains** — Hierarchical CPU groupings (SMT → Core → Socket → NUMA) with per-domain balance intervals. 3. **Busiest Queue Detection** — Before pushing, CFS identifies the busiest CPU/group, ensuring push actions actually improve balance. 4. **Migration Throttling** — Rate limits on migrations prevent oscillation.76:T6e0,/* Simplified representation of CFS load balancing logic */ /* See kernel/sched/fair.c for full implementation */ /* Main load balance function called for each scheduling domain */ static int load_balance(struct lb_env *env) { struct run_queue *busiest; unsigned long imbalance; int ld_moved = 0; /* Find the busiest group in this scheduling domain */ struct sched_group *busiest_group = find_busiest_group(env); if (!busiest_group) { return 0; /* No imbalance at group level */ } /* Find the busiest run queue within that group */ busiest = find_busiest_queue(env, busiest_group); if (!busiest) { return 0; /* No specific CPU to balance from */ } /* Calculate how much load to move */ imbalance = calculate_imbalance(env, busiest_group); if (imbalance == 0) { return 0; /* Imbalance below threshold */ } /* Attempt to migrate tasks from busiest to local CPU */ env->src_rq = busiest; env->dst_rq = this_rq(); env->imbalance = imbalance; /* The actual migration loop */ while (env->imbalance > 0) { struct task_struct *p; /* Select a task that can migrate */ p = detach_one_task(env); if (!p) { break; /* No more migratable tasks */ } /* Attach the task to local run queue */ attach_one_task(env->dst_rq, p); ld_moved++; env->imbalance -= task_load(p); } return ld_moved; } /* PELT-based load calculation (simplified) */ static unsigned long task_load(struct task_struct *p) { /* Load is decayed average of CPU demand */ return p->se.load.weight * p->se.avg.load_avg / LOAD_AVG_MAX; }63:{"json":{"id":"seed_41dddc45b432539003b3b063ac912949","slug":"os-load-balancing","category":"Operating Systems","topic":"Load Balancing","title":"Load Balancing in Multiprocessor Systems","description":"Master the art and science of load balancing in modern multiprocessor operating systems. Explore push migration, pull migration, work stealing algorithms, balancing frequency considerations, and quantitative metrics for evaluating load distribution effectiveness.","difficulty":"ADVANCED","estimatedMinutes":75,"pages":[{"id":"seed_5f81d9b47621626e9229e63f36d3f3ac","title":"Push Migration: Proactive Load Distribution","order":0,"content":[{"id":"opening-context","title":"The Challenge of Load Imbalance","content":[{"data":{"content":"$6a"},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"By completing this page, you will understand: (1) The fundamental concept and motivation behind push migration, (2) The architectural components required for implementation, (3) Algorithms for detecting overload and selecting migration candidates, (4) Integration with SMP schedulers in production operating systems, and (5) The performance tradeoffs inherent in proactive load redistribution.","variant":"info"},"type":"callout"}]},{"id":"conceptual-foundations","title":"Conceptual Foundations of Push Migration","content":[{"data":{"content":"$6b"},"type":"text"},{"data":{"icon":"Info","title":"Why Imbalance Occurs","content":"Load imbalance arises naturally from multiple sources: processes are often created on specific CPUs (e.g., where the parent runs), processes exit unpredictably, I/O completions wake processes on arbitrary CPUs, and user-space thread pools may distribute work unevenly. Even with perfect initial placement, the system drifts toward imbalance over time.","variant":"note"},"type":"callout"},{"data":{"content":"$6c"},"type":"text"},{"data":{"rows":[["Load Metric","How do we quantify CPU load?","Run queue length, weighted by priority/niceness"],["Threshold","When is a CPU 'overloaded'?","Absolute count, relative to average, percentage above mean"],["Target Selection","Which CPU receives migrated tasks?","Least loaded, round-robin among idle, NUMA-aware selection"],["Task Selection","Which tasks should migrate?","Lowest priority, most recently queued, cache-cold processes"],["Timing","When do we check for imbalance?","Periodic timer interrupt, after scheduling events"]],"caption":"Push Migration: Key Design Decisions","headers":["Design Aspect","Question","Typical Approaches"]},"type":"table"}],"titleType":"number","titleNumber":1},{"id":"architectural-components","title":"Architectural Components for Push Migration","content":[{"data":{"content":"Implementing push migration requires several coordinated components within the operating system's scheduler. Understanding these components is essential for grasping how the abstract concept becomes working code.\n\n**Per-CPU Run Queue Infrastructure**\n\nThe foundation of push migration is the per-CPU run queue. Each processor maintains its own queue of runnable tasks, typically organized as a multi-level structure with different priority levels or scheduling classes.\n\nIn Linux, for example, the `struct rq` (run queue) structure exists for each CPU and contains:\n- **Active tasks** — Processes currently ready to run\n- **Load tracking** — Statistics about recent CPU utilization\n- **Locking** — Per-queue locks for thread-safe access\n- **Migration state** — Flags and counters for load balancing"},"type":"text"},{"data":{"code":"$6d","variant":"default","fileName":"run_queue_structure.c","showLineNumbers":true},"type":"code"},{"data":{"content":"**Load Calculation Subsystem**\n\nAccurate load calculation is the cornerstone of effective push migration. The system must answer a deceptively complex question: *How busy is this CPU compared to others?*\n\nSimple metrics like 'number of runnable tasks' are inadequate because:\n- A CPU with 5 low-priority background tasks is less 'loaded' than one with 2 high-priority interactive tasks\n- Tasks with different CPU affinities contribute differently to effective load\n- Historical load (running average) matters more than instantaneous snapshots for stability\n\n**Weighted Load Calculation**\n\nModern schedulers use weighted load calculations that account for task priority. Each task contributes a 'load weight' proportional to its scheduling priority:"},"type":"text"},{"data":{"code":"$6e","variant":"default","fileName":"load_calculation.c","showLineNumbers":true},"type":"code"},{"data":{"icon":"Lightbulb","title":"Exponential Smoothing Matters","content":"Using a running average rather than instantaneous load prevents 'migration thrashing'—where tasks bounce between CPUs responding to momentary fluctuations. The smoothing factor (alpha) balances responsiveness against stability. Too responsive: thrashing. Too stable: slow to correct imbalances.","variant":"tip"},"type":"callout"},{"data":{"content":"**Overload Detection Mechanism**\n\nWith load calculated, the next component determines when a CPU is sufficiently overloaded to trigger migration. Several strategies exist:\n\n**Absolute Threshold**\n```\nif (rq->nr_running > PUSH_THRESHOLD) trigger_push();\n```\nSimple but inflexible—ignores system-wide load context.\n\n**Relative Threshold (Average-Based)**\n```\nif (rq->avg_load > system_avg_load * 1.25) trigger_push();\n```\nAdapts to overall system load but requires cross-CPU coordination.\n\n**Imbalance-Based**\n```\nimbalance = rq->avg_load - busiest_group_avg_load / nr_cpus;\nif (imbalance > min_migration_threshold) migrate(imbalance);\n```\nMost sophisticated—considers where work would go, not just local overload.\n\nLinux's CFS scheduler uses a hybrid approach, computing 'imbalance' as the weighted difference between scheduling domains and triggering migration when this exceeds a configurable threshold."},"type":"text"}],"titleType":"number","titleNumber":2},{"id":"push-migration-algorithm","title":"The Push Migration Algorithm in Detail","content":[{"data":{"content":"With the foundational components in place, we can now examine the push migration algorithm itself. This section presents a production-quality algorithm with all the nuances required for robust operation.\n\n**High-Level Algorithm Flow**\n\nThe push migration process follows a four-phase structure:\n\n1. **Trigger Phase** — Timer interrupt or scheduling event initiates load check\n2. **Analysis Phase** — Compute local load, compare against thresholds\n3. **Selection Phase** — Choose tasks and destination CPUs for migration\n4. **Execution Phase** — Transfer selected tasks, update accounting\n\nLet's examine each phase in detail."},"type":"text"},{"data":{"code":"$6f","variant":"default","fileName":"push_migration_algorithm.c","showLineNumbers":true},"type":"code"},{"data":{"content":"**Phase 1: Trigger and Quick Check**\n\nPush migration is typically triggered by a periodic timer interrupt (every few milliseconds) or after significant scheduling events. Before proceeding with expensive calculations, a quick check determines if migration is even plausible:"},"type":"text"},{"data":{"code":"$70","variant":"default","fileName":"push_trigger_check.c","showLineNumbers":true},"type":"code"},{"data":{"content":"**Phase 2: Imbalance Calculation**\n\nIf the quick check passes, we compute the precise imbalance—the amount of load that should be migrated to achieve balance:"},"type":"text"},{"data":{"code":"$71","variant":"default","fileName":"imbalance_calculation.c","showLineNumbers":true},"type":"code"},{"data":{"icon":"AlertCircle","title":"Migration Cost Consideration","content":"Every migration has a cost: cache invalidation, TLB flushes, memory bandwidth for moving task state. Push migration must only occur when the expected benefit (reduced imbalance) exceeds this cost. Without this check, aggressive pushing can decrease overall throughput despite achieving better balance on paper.","variant":"warning"},"type":"callout"},{"data":{"content":"**Phase 3: Destination and Task Selection**\n\nWith imbalance quantified, we must select *which* task to push and *where* to push it. These decisions profoundly affect migration effectiveness:"},"type":"text"},{"data":{"code":"$72","variant":"default","fileName":"selection_algorithm.c","showLineNumbers":true},"type":"code"},{"data":{"content":"**Phase 4: Migration Execution**\n\nOnce destination and task are selected, the actual migration transfers the task's scheduling state:"},"type":"text"},{"data":{"code":"$73","variant":"default","fileName":"migration_execution.c","showLineNumbers":true},"type":"code"}],"titleType":"number","titleNumber":3},{"id":"numa-aware-push","title":"NUMA-Aware Push Migration","content":[{"data":{"content":"Modern multiprocessor systems are typically organized as Non-Uniform Memory Access (NUMA) architectures, where memory access latency varies based on the physical relationship between CPUs and memory controllers. This architectural reality profoundly impacts push migration strategies.\n\n**The NUMA Challenge**\n\nIn NUMA systems, migrating a task to a distant CPU can significantly degrade that task's performance:\n\n- **Remote memory access latency** — Tasks accessing memory allocated on their original node face 2-3x slower access from a remote node\n- **Interconnect bandwidth** — Cross-node traffic consumes limited inter-node bandwidth\n- **Cache coherency overhead** — Maintaining cache coherency across NUMA boundaries is more expensive\n\nNaive push migration that ignores NUMA topology can actually *decrease* system throughput despite achieving better load balance."},"type":"text"},{"data":{"rows":[["NUMA-Blind","Optimal","Severely degraded","May decrease 20-40%"],["Local-Only","Suboptimal","Preserved","Limited improvement"],["NUMA-Aware Hybrid","Near-optimal","Mostly preserved","Best overall results"]],"caption":"NUMA-Aware vs. NUMA-Blind Migration","headers":["Approach","Load Balance","Memory Locality","Overall Throughput"]},"type":"table"},{"data":{"content":"**Hierarchical Domain Organization**\n\nTo handle NUMA effectively, schedulers organize CPUs into hierarchical scheduling domains. Each domain represents a set of CPUs that share some architectural characteristic:\n\n```\nNUMA Node 0 NUMA Node 1\n+-----------+ +-----------+\n| Core 0-3 |<------>| Core 4-7 |\n| L3 Cache | QPI | L3 Cache |\n| DDR4 Bank | | DDR4 Bank |\n+-----------+ +-----------+\n | |\n v v\nSMT Domain SMT Domain\n(Core siblings) (Core siblings)\n```\n\n**NUMA-Aware Push Strategy**\n\nWith domain hierarchy in place, push migration follows a domain-aware strategy:"},"type":"text"},{"data":{"code":"$74","variant":"default","fileName":"numa_aware_push.c","showLineNumbers":true},"type":"code"},{"data":{"icon":"Lightbulb","title":"Domain Hierarchy as Cost Function","content":"The scheduling domain hierarchy encodes migration costs implicitly. SMT siblings share L1 cache—nearly free migration. Same-socket cores share L3—cheap migration. Same-node CPUs share memory—moderate cost. Cross-node requires interconnect—expensive. Push migration uses this hierarchy to make cost-aware decisions.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":4},{"id":"linux-cfs-implementation","title":"Push Migration in Linux CFS","content":[{"data":{"content":"$75"},"type":"text"},{"data":{"code":"$76","variant":"default","fileName":"cfs_load_balance.c","showLineNumbers":true},"type":"code"},{"data":{"content":"**Balance Intervals by Domain Level**\n\nCFS adjusts push migration frequency based on domain level, balancing responsiveness against overhead:"},"type":"text"},{"data":{"rows":[["SMT (Hyperthreads)","4ms","Same core—nearly free migration"],["MC (Multi-core)","8ms","Same socket—low cost"],["DIE (Same die)","16ms","Shared L3—moderate cost"],["NUMA (Cross-node)","64ms","High latency—cautious balancing"]],"caption":"CFS Balance Intervals (Typical Values)","headers":["Domain Level","Balance Interval","Rationale"]},"type":"table"},{"data":{"icon":"Info","title":"Push vs. Pull in CFS","content":"CFS actually implements both push and pull, but in a unified framework. The 'push' perspective occurs when code running on CPU A considers sending tasks away. The 'pull' perspective occurs when idle CPU B looks for work to take. CFS's load_balance() can be viewed as 'push from busiest to local' or 'pull from busiest to local' depending on which CPU initiates.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":5},{"id":"performance-analysis","title":"Performance Analysis of Push Migration","content":[{"data":{"content":"Understanding when push migration helps—and when it hurts—requires analyzing its performance characteristics under different workload patterns.\n\n**Beneficial Scenarios**\n\nPush migration provides significant benefits in scenarios with:\n\n1. **Bursty Task Creation** — When processes spawn many children on a single CPU\n2. **Uneven Wakeups** — When I/O completions wake tasks concentrated on few CPUs\n3. **Long-Running Compute Tasks** — Tasks that exceed their time slice multiple times\n4. **Mixed Workloads** — Combinations of batch and interactive tasks\n\n**Detrimental Scenarios**\n\nPush migration can hurt performance when:\n\n1. **High-Locality Workloads** — Tasks with strong cache affinity that shouldn't move\n2. **Short-Lived Tasks** — Tasks that complete before migration overhead pays off\n3. **Memory-Intensive NUMA Workloads** — Cross-node migration destroys locality\n4. **Real-Time Workloads** — Migration latency may miss deadlines"},"type":"text"},{"data":{"rows":[["Run queue lock contention","1-10 μs","Per-CPU queues, lock-free checking"],["Task state copying","0.5-2 μs","Minimal state transfer"],["Cache invalidation (L1/L2)","100-500 cycles","Prefer cache-cold tasks"],["TLB flush on new CPU","50-200 cycles","Batch migrations"],["Memory controller switch (NUMA)","100-300 ns additional latency","NUMA-aware selection"],["IPI for destination wakeup","1-5 μs","Coalesce with other IPIs"]],"caption":"Push Migration Overhead Components","headers":["Overhead Source","Typical Cost","Mitigation Strategy"]},"type":"table"},{"data":{"content":"**Quantifying the Benefit**\n\nThe net benefit of push migration can be modeled as:\n\n```\nBenefit = (Imbalance_Reduction × Task_Throughput_Gain) - Migration_Cost\n```\n\nWhere:\n- **Imbalance_Reduction** = Time saved by distributing work more evenly\n- **Task_Throughput_Gain** = Performance improvement from utilizing idle CPUs\n- **Migration_Cost** = Direct overhead + locality loss + cache rebuild time\n\nFor a task that would wait 50ms in queue on an overloaded CPU:\n- If migration takes 10μs total overhead\n- And cache rebuild adds 100μs slowdown\n- Net benefit = 50ms - 0.11ms ≈ 50ms saved (clear win)\n\nFor a task that would wait 200μs:\n- Same 110μs migration cost\n- Net benefit = 200μs - 110μs = 90μs saved (marginal)\n\nFor a task with 1ms remaining lifetime:\n- Migration cost = 110μs overhead + locality loss\n- Task may complete before benefiting (potential loss)"},"type":"text"},{"data":{"icon":"Lightbulb","title":"The 'Don't Migrate Short Tasks' Heuristic","content":"Production schedulers often track task 'cache footprint' or 'run time since last migration'. Tasks with warm caches or short expected remaining runtime are skipped for migration. This simple heuristic prevents the most common anti-pattern: migrating a task that was about to complete anyway.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":6},{"id":"summary","title":"Summary: Push Migration Mastery","content":[{"data":{"content":"Push migration represents a fundamental technique in the operating system's arsenal for extracting maximum performance from multiprocessor hardware. Let's consolidate the key insights from this comprehensive exploration:"},"type":"text"},{"data":{"type":"ordered","items":["**Push migration is proactive load balancing** — Overloaded CPUs actively redistribute their excess work to less-loaded processors, preventing severe imbalance.","**Weighted load metrics enable fair comparison** — Simple task counts are insufficient; priority-weighted calculations account for the true computational demand of each task.","**NUMA topology must guide destination selection** — Cross-node migrations can negate load balancing benefits by destroying memory locality.","**Task selection is as important as destination selection** — Cache-cold, low-priority tasks with weak affinity are ideal migration candidates.","**Migration cost must be weighed against benefit** — Not every imbalance warrants migration; threshold tuning prevents thrashing.","**Production schedulers use hierarchical domains** — CFS and similar schedulers balance more aggressively within low-cost domains and cautiously across NUMA boundaries."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**Connecting to the Broader Picture**\n\nPush migration is one half of the load balancing equation. In the next page, we'll explore **pull migration**—the complementary approach where idle processors actively seek work from busy ones. Together, push and pull form a complete solution for maintaining balance across diverse workload patterns."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now possess deep understanding of push migration—from conceptual foundations through production implementation. You can reason about when push migration helps, when it hurts, and how operating systems tune its behavior across different hardware topologies. Next, we examine the complementary pull migration mechanism.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":7}],"isLocked":false},{"id":"seed_4511c9fc0afb0eb3a9a91ef4f9bbb46b","title":"Pull Migration: Demand-Driven Load Distribution","order":1,"content":null,"isLocked":true},{"id":"seed_c56ec33efb315f1af16cfb001df73c99","title":"Work Stealing: Algorithmic Load Balancing","order":2,"content":null,"isLocked":true},{"id":"seed_18bc9121a8a8bf51fc3c5574cccac339","title":"Balancing Frequency: The When of Load Distribution","order":3,"content":null,"isLocked":true},{"id":"seed_2fd8efaeb25d379193ad95d215d4df82","title":"Metrics: Measuring Load and Balance Quality","order":4,"content":null,"isLocked":true}]}}