Load Balancing in Multiprocessor Systems

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

/* 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 */
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

/* 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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

/* 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);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

/* 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 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

/* 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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121

/* 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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

/* 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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

/* 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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

/* 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;
}