Process Queues: Managing System Resources

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

/* Simplified process admission after fork() */
int admit_new_process(struct task_struct *p) {
    /* Check system-wide process limits */
    if (nr_threads >= max_threads) {
        /* Too many processes - reject */
        return -EAGAIN;
    }
    
    /* Check per-user process limits */
    if (p->cred->user->processes >= rlimit(RLIMIT_NPROC)) {
        return -EAGAIN;
    }
    
    /* Check cgroup limits */
    if (cgroup_over_limit(p)) {
        return -EAGAIN;
    }
    
    /* Check memory availability */
    if (!can_allocate_memory_for_process(p)) {
        /* Overcommit check - may still allow */
        if (!vm_overcommit_allowed()) {
            return -ENOMEM;
        }
    }
    
    /* All checks passed - admit to ready queue */
    p->state = TASK_RUNNING;  /* READY state */
    activate_task(task_rq(p), p, ENQUEUE_WAKEUP);
    
    return 0;
}
 
/* Cgroup-based admission control */
bool cgroup_over_limit(struct task_struct *p) {
    struct cgroup *cg = p->cgroups->dfl_cgrp;
    
    /* Check pids controller */
    struct pids_cgroup *pids = cg->pids;
    if (pids->nr_pids >= pids->limit) {
        return true;  /* Cgroup at PID limit */
    }
    
    /* Check CPU controller for CPU shares */
    struct cpu_cgroup *cpu = cg->cpu;
    if (cpu->nr_running >= cpu->max_nr_tasks) {
        return true;  /* Too many running tasks in cgroup */
    }
    
    return false;
}
 
/* Linux sysctl limits */
// /proc/sys/kernel/threads-max         - Max threads system-wide
// /proc/sys/kernel/pid_max             - Max PID value (limits processes)
// /proc/sys/vm/max_map_count           - Max memory mappings per process

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

/* Scheduling domain structure */
struct sched_domain {
    struct sched_domain *parent;      /* Parent domain */
    struct sched_domain *child;       /* Child domain */
    struct sched_group *groups;       /* Groups of CPUs in this domain */
    
    /* Balancing parameters */
    int balance_interval;             /* How often to balance (in jiffies) */
    int busy_factor;                  /* Multiply interval when busy */
    int imbalance_pct;                /* Threshold for imbalance */
    int cache_nice_tries;             /* Attempts before breaking affinity */
    
    /* Flags */
    unsigned int flags;               /* SD_SHARE_CPUPOWER, SD_NUMA, etc. */
    
    /* Statistics */
    unsigned long last_balance;       /* When last balanced */
    unsigned int balance_cnt;         /* Number of balance attempts */
};
 
/* Main load balancing function */
static int load_balance(int this_cpu, struct rq *this_rq,
                        struct sched_domain *sd,
                        enum cpu_idle_type idle) {
    struct sched_group *busiest_group;
    struct rq *busiest;
    unsigned long imbalance;
    int moved = 0;
    
    /* Find the busiest group in this domain */
    busiest_group = find_busiest_group(sd, this_cpu, &imbalance, idle);
    if (!busiest_group)
        goto out_balanced;  /* Already balanced */
    
    /* Find the busiest CPU in that group */
    busiest = find_busiest_queue(busiest_group, this_cpu);
    if (!busiest)
        goto out_balanced;
    
    /* Can't balance from ourselves */
    if (busiest == this_rq)
        goto out_balanced;
    
    /* Calculate how many tasks to move */
    if (imbalance < busiest->nr_running)
        imbalance = 1;  /* Move at least one task */
    
    /* Pull tasks from busiest to this_rq */
    moved = move_tasks(this_rq, this_cpu, busiest, imbalance, sd, idle);
    
    if (moved) {
        /* Successful balance */
        sd->balance_cnt++;
    }
    
    sd->last_balance = jiffies;
    return moved;
 
out_balanced:
    return 0;
}
 
/* Calculate group load for comparison */
static inline unsigned long group_load(struct sched_group *group) {
    unsigned long load = 0;
    int i;
    
    for_each_cpu(i, sched_group_span(group)) {
        load += cpu_rq(i)->cfs.runnable_load_avg;
    }
    
    return load;
}
 
/* Decide if a task should migrate */
static int can_migrate_task(struct task_struct *p, 
                             struct rq *busiest,
                             struct rq *target,
                             struct sched_domain *sd) {
    /* Don't migrate currently running tasks */
    if (task_running(busiest, p))
        return 0;
    
    /* Respect CPU affinity */
    if (!cpumask_test_cpu(target->cpu, p->cpus_ptr))
        return 0;
    
    /* Check cache hotness - recently run tasks have hot caches */
    if (task_hot(p, sd))
        return 0;
    
    /* NUMA: Prefer tasks whose memory is local to target */
    if (sd->flags & SD_NUMA) {
        int src_nid = cpu_to_node(task_cpu(p));
        int dst_nid = cpu_to_node(target->cpu);
        if (src_nid == p->numa_preferred_nid &&
            dst_nid != p->numa_preferred_nid)
            return 0;  /* Would move away from preferred node */
    }
    
    return 1;  /* OK to migrate */
}

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

/* Windows priority boost situations (conceptual) */
 
/* 1. Foreground Window Boost */
void boost_foreground_thread(PETHTHREAD Thread) {
    /* The thread that owns the foreground window gets a boost */
    if (thread_owns_foreground_window(Thread)) {
        Thread->PriorityBoost += 2;
        /* Decay: boost decreases by 1 each quantum until base */
    }
}
 
/* 2. I/O Completion Boost */
void complete_io_operation(PETHTHREAD Thread, int DeviceType) {
    /* Boost varies by device type */
    int boost;
    
    switch (DeviceType) {
        case IO_KEYBOARD_INCREMENT:
        case IO_MOUSE_INCREMENT:
            boost = 6;  /* High boost for input devices */
            break;
        case IO_NETWORK_INCREMENT:
            boost = 2;  /* Network I/O */
            break;
        case IO_DISK_INCREMENT:
            boost = 1;  /* Disk I/O - lowest */
            break;
        case IO_SOUND_INCREMENT:
            boost = 8;  /* Audio - needs low latency */
            break;
        default:
            boost = 1;
    }
    
    Thread->Priority = min(Thread->BasePriority + boost, 15);
    /* Note: Boost never pushes normal thread into RT range (16-31) */
}
 
/* 3. Wait Completion Boost */
void complete_wait_event(PETHTHREAD Thread, int WaitType) {
    /* Threads waiting for events/semaphores get boosted */
    if (WaitType == EVENT_WAIT) {
        Thread->PriorityBoost += 1;
    } else if (WaitType == SEMAPHORE_WAIT) {
        Thread->PriorityBoost += 2;
    }
}
 
/* 4. CPU Starvation Prevention (Balance Set Manager) */
void prevent_starvation(void) {
    /* Periodic scan for starving threads */
    for_each_ready_thread(Thread) {
        LARGE_INTEGER CurrentTime;
        KeQuerySystemTime(&CurrentTime);
        
        /* If thread hasn't run in 4 seconds */
        LONGLONG wait_time = CurrentTime - Thread->LastRunTime;
        if (wait_time > 4 * SECONDS_TO_100NS) {
            /* Boost to priority 15 for one quantum */
            Thread->Priority = 15;
            Thread->Quantum = 2;  /* Very short quantum */
            /* After running, returns to base priority */
        }
    }
}
 
/* 5. GUI Thread Boost */
void handle_window_message(PETHTHREAD Thread) {
    /* Thread receiving window message gets boosted */
    Thread->Priority = min(Thread->BasePriority + 2, 15);
}

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

/* Virtual runtime calculation in CFS */
static u64 calc_delta_fair(u64 delta, struct sched_entity *se) {
    /* delta = actual time elapsed
     * se->load.weight = task's weight (from nice value)
     * Returns: virtual time elapsed
     */
    
    if (se->load.weight == NICE_0_LOAD) {
        /* Nice 0 task: vruntime == actual runtime */
        return delta;
    }
    
    /* Higher weight = slower vruntime increase = more CPU time
     * vruntime_delta = actual_delta * (NICE_0_LOAD / weight)
     */
    return cal_delta(delta, NICE_0_LOAD, &se->load);
}
 
/* Nice value to weight table (partial) */
const int sched_prio_to_weight[40] = {
    /* -20 */ 88761,  /* 88x more weight than nice 0 */
    /* -10 */  9548,  /* 9x more weight */
    /*   0 */  1024,  /* Base weight */
    /*  10 */   110,  /* ~1/9 weight */
    /*  19 */    15,  /* ~1/68 weight */
};
 
/* Effect: nice -20 process gets ~88x more CPU than nice 19
 * All processes' vruntimes still advance, preventing starvation
 */
 
/* Sleep/Wake fairness: sleeping tasks get vruntime credit */
static void place_entity(struct cfs_rq *cfs_rq, 
                         struct sched_entity *se) {
    u64 vruntime = cfs_rq->min_vruntime;
    
    /* New/waking tasks start at min_vruntime minus a "sleeper bonus"
     * This prevents them from immediately preempting long-running tasks
     * but still gives them a small advantage for sleeping
     */
    if (sched_feat(GENTLE_FAIR_SLEEPERS)) {
        /* Subtract half the scheduling latency */
        vruntime -= sysctl_sched_latency >> 1;
    }
    
    /* Clamp to min_vruntime (can't go into the past too far) */
    se->vruntime = max_vruntime(se->vruntime, vruntime);
}

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

# View current CFS settings
$ cat /proc/sys/kernel/sched_latency_ns
24000000  # 24 milliseconds
 
$ cat /proc/sys/kernel/sched_min_granularity_ns
3000000   # 3 milliseconds
 
# Tuning for throughput-oriented server workload
# Increase granularity to reduce context switches
echo 6000000 > /proc/sys/kernel/sched_min_granularity_ns
echo 48000000 > /proc/sys/kernel/sched_latency_ns
echo 0 > /proc/sys/kernel/sched_autogroup_enabled
 
# Tuning for interactive desktop workload
# Decrease granularity for better responsiveness
echo 1000000 > /proc/sys/kernel/sched_min_granularity_ns
echo 12000000 > /proc/sys/kernel/sched_latency_ns
echo 1 > /proc/sys/kernel/sched_autogroup_enabled
 
# Tuning for real-time / low-latency workload
# Also consider PREEMPT_RT kernel
 
# Set process scheduling policy
$ chrt -f 50 ./my_realtime_app  # SCHED_FIFO at priority 50
$ chrt -r 50 ./my_realtime_app  # SCHED_RR at priority 50
 
# CPU affinity - bind to specific CPUs
$ taskset -c 0-3 ./my_app       # Use CPUs 0-3
$ taskset -c 4-7 ./other_app    # Use CPUs 4-7
 
# Nice value adjustment
$ nice -n -5 ./important_app    # Higher priority
$ renice -n 10 -p 1234          # Lower priority for PID 1234
 
# cgroups for resource isolation
# Create cgroup for batch jobs
$ mkdir /sys/fs/cgroup/cpu/batch
$ echo 100000 > /sys/fs/cgroup/cpu/batch/cpu.cfs_quota_us  # 10% of one CPU
$ echo 100000 > /sys/fs/cgroup/cpu/batch/cpu.cfs_period_us
$ echo $PID > /sys/fs/cgroup/cpu/batch/cgroup.procs

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

/* Anti-Starvation Technique 1: Aging
 * Increase priority over time for waiting tasks
 */
struct task_with_aging {
    int base_priority;
    int current_priority;
    unsigned long wait_start;
};
 
void age_waiting_tasks(struct queue *q) {
    struct task_with_aging *t;
    unsigned long now = jiffies;
    
    list_for_each_entry(t, &q->wait_list, link) {
        unsigned long wait_time = now - t->wait_start;
        
        /* Increase priority by 1 for every 100ms waiting */
        int age_boost = wait_time / msecs_to_jiffies(100);
        
        t->current_priority = max(0, t->base_priority - age_boost);
    }
}
 
/* Anti-Starvation Technique 2: Deadline Guarantee
 * I/O scheduler (deadline) enforces maximum wait time
 */
struct deadline_request {
    struct list_head sort_list;   /* Sorted by sector */
    struct list_head fifo_list;   /* Sorted by deadline */
    unsigned long deadline;
};
 
struct request *deadline_dispatch(struct deadline_queue *dq) {
    struct request *rq;
    
    /* First check for expired deadlines */
    rq = check_expired_deadline(&dq->read_fifo, dq->read_expire);
    if (rq) return rq;  /* Must service this immediately */
    
    rq = check_expired_deadline(&dq->write_fifo, dq->write_expire);
    if (rq) return rq;
    
    /* No deadline pressure - optimize for throughput */
    return pick_from_sorted_queue(dq);
}
 
/* Anti-Starvation Technique 3: Round-Robin at Same Priority
 * MLFQ: Process runs for quantum, then moves to next queue
 */
void mlfq_quantum_expired(struct task_struct *task) {
    /* Move to lower priority queue */
    if (task->queue_level < MAX_QUEUE_LEVEL) {
        task->queue_level++;
    }
    
    /* But periodically boost everyone back up */
    if (time_to_boost()) {
        boost_all_tasks_to_top_queue();
    }
}
 
/* Anti-Starvation Technique 4: Fair Sharing (CFS approach)
 * Virtual runtime ensures eventual execution for all
 */
void cfs_fair_share(void) {
    /* Task with lowest vruntime runs
     * Even lowest priority eventually has lowest vruntime
     * Because they get less CPU time, vruntime grows slower
     * But it still grows, and eventually they become lowest
     */
    
    /* Mathematical guarantee: In steady state
     * CPU share of task i = weight_i / sum(all weights)
     * Every task makes progress proportional to its weight
     */
}