Linux内核进程调度器CFS与完全公平调度算法深度实战：从红黑树时间切片到SCHED_FIFO实时抢占

这意味着NICE值为-20（最高优先级）的进程，其vruntime增速仅为NICE值为19（最低优先级）进程的约1/300，从而获得远更多的CPU时间。

红黑树：O(log n)的高效任务选择

CFS使用红黑树(rb-tree)组织所有可运行进程，关键键值为vruntime。红黑树的性质保证了：(1) 最左侧节点始终是vruntime最小的进程——调度器只需O(1)时间获取它；(2) 插入和删除操作均为O(log n)。每个CPU运行队列(cfs_rb)维护自己的红黑树，避免全局锁争用。

// CFS运行队列核心结构（简化）
struct cfs_rq {  
    struct rb_root_cached runiments;  // 红黑树根节点缓存（最左节点）
    struct rb_node *rb_leftmost;     // 直接指向最左（最小vruntime）
    unsigned long h_nr_running;      // 可运行任务数
    u64 min_vruntime;                // 队列最小vruntime（单调递增）
    struct load_weight load;         // 队列总权重
    // ... 额外统计与cgroup关联
};

// 选择下一个进程（O(1)获取最左节点）
static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)  
{  
    struct sched_entity *se = __pick_first_entity(cfs_rq);
    // ... 处理组调度、next_idx等优化
    return se;
}  

// 内核sched/fair.c - 计算时间片
static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    // slice = (se->load.weight / cfs_rq->load.weight) * sched_period
    // sched_period 在nr_running>8时为 nr_running * min_granularity
    // 否则为 sched_latency (6ms)
    u64 slice = __sched_period(cfs_rq->h_nr_running);
    slice = div64_u64(slice * se->load.weight, cfs_rq->load.weight);
    return slice;
}

// 实时优先级映射（内核/psched.h）
#define MAX_RT_PRIO 100
// 实时优先级: 0 ~ 99 (对应prio 0-99)
// 普通进程优先级: 100 ~ 139 (对应nice -20 ~ 19)

// 实时抢占检查（简化）
static void check_preempt_curr(struct rq *rq, struct task_struct *p, int flags)
{
    // 如果新进程的调度类高于当前调度类，触发抢占
    // 且如果实时队列中有高优先级进程，立即resched_curr
    if (p->sched_class == &stop_sched_class || p->prio < curr->prio)
        resched_curr(rq);
}