深入理解Linux Kernel调度器的身世之谜

struct task_struct {    int prio, static_prio, normal_prio;    unsigned int rt_priority;    const struct sched_class *sched_class;    struct sched_entity se;    struct sched_rt_entity rt;    …    unsigned int policy;    cpumask_t cpus_allowed;    …};

$ ps -eo pid, rtprio, cmd

#define MAX_NICE 19#define MIN_NICE -20#define NICE_WIDTH (MAX_NICE - MIN_NICE + 1)…#define MAX_USER_RT_PRIO 100#define MAX_RT_PRIO MAX_USER_RT_PRIO#define MAX_PRIO (MAX_RT_PRIO + NICE_WIDTH)#define DEFAULT_PRIO (MAX_RT_PRIO + NICE_WIDTH / 2)/** Convert user-nice values [ -20 ...  ... 19 ]* to static priority [ MAX_RT_PRIO..MAX_PRIO-1 ],* and back.*/#define NICE_TO_PRIO(nice) ((nice) + DEFAULT_PRIO)#define PRIO_TO_NICE(prio) ((prio) - DEFAULT_PRIO)/** 'User priority' is the nice value converted to something we* can work with better when scaling various scheduler parameters,* it's a [ 0 ... 39 ] range.*/#define USER_PRIO(p) ((p)-MAX_RT_PRIO)#define TASK_USER_PRIO(p) USER_PRIO((p)->static_prio)#define MAX_USER_PRIO (USER_PRIO(MAX_PRIO))

int prio, static_prio, normal_prio;unsigned int rt_priority;

p->static_prio = NICE_TO_PRIO(nice_value);

p->prio = effective_prio(p);// kernel/sched/core.c 中定义了计算方法static int effective_prio(struct task_struct *p){    p->normal_prio = normal_prio(p);    /*    * If we are RT tasks or we were boosted to RT priority,    * keep the priority unchanged. Otherwise, update priority    * to the normal priority:    */    if (!rt_prio(p->prio))        return p->normal_prio;    return p->prio;}
static inline int normal_prio(struct task_struct *p){    int prio;    if (task_has_dl_policy(p))        prio = MAX_DL_PRIO-1;    else if (task_has_rt_policy(p))        prio = MAX_RT_PRIO-1 - p->rt_priority;    else         prio = __normal_prio(p);    return prio;}
static inline int __normal_prio(struct task_struct *p){    return p->static_prio;}

struct sched_entity {    struct load_weight load; /* for load-balancing */    …}struct load_weight {    unsigned long weight;    u32 inv_weight;};

static const int prio_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,};

static void set_load_weight(struct task_struct *p){    int prio = p->static_prio - MAX_RT_PRIO;    struct load_weight *load = &p->se.load;    /*    * SCHED_IDLE tasks get minimal weight:    */    if (p->policy == SCHED_IDLE) {        load->weight = scale_load(WEIGHT_IDLEPRIO);        load->inv_weight = WMULT_IDLEPRIO;        return;    }    load->weight = scale_load(prio_to_weight[prio]);    load->inv_weight = prio_to_wmult[prio];}

// 为了简单起见，隐藏了部分代码（如 SMP 相关的）struct sched_class {    // 多个 sched_class 是链接在一起的    const struct sched_class *next;    // 该 hook 会在任务进入可运行状态时调用。它会将调度单元（如一个任务）放到    // 队列中，同时递增 `nr_running` 变量（该变量表示运行队列中可运行的任务数）    void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);    // 该 hook 会在任务不可运行时调用。它会将任务移出队列，同时递减 `nr_running`    void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);    // 该 hook 可以在任务需要主动放弃 CPU 时调用，但是需要注意的是，它不会改变    // 任务的可运行状态，也就是说依然会在队列中等待下次调度。类似于先 dequeue_task，    // 再 enqueue_task    void (*yield_task) (struct rq *rq);    // 该 hook 会在任务进入可运行状态时调用并检查是否需要抢占当前任务    void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);    // 该 hook 用来选择适合运行的下一个任务    struct task_struct * (*pick_next_task) (struct rq *rq, struct task_struct *prev);    // 该 hook 会在任务修改自身的调度类或者任务组时调用    void (*set_curr_task) (struct rq *rq);    // 通常是在时钟中断时调用，可能会导致任务切换    void (*task_tick) (struct rq *rq, struct task_struct *p, int queued);    // 当任务被 fork 时通知调度器    void (*task_fork) (struct task_struct *p);    // 当任务挂掉时通知调度器    void (*task_dead) (struct task_struct *p);};

// 为了简单起见，隐藏了部分代码（SMP 相关）// 这个是每个 CPU 都会有的一个任务运行队列struct rq{    // 表示当前队列中总共有多少个可运行的任务（包含所有的 sched class）    unsigned int nr_running;#define CPU_LOAD_IDX_MAX 5    unsigned long cpu_load[CPU_LOAD_IDX_MAX];    // 运行队列负载记录    struct load_weight load;    // 嵌套的 CFS 调度器运行队列    struct cfs_rq cfs;    // 嵌套的实时任务调度器运行队列    struct rt_rq rt;    // curr 指向当前正在运行的进程描述符    // idle 则指向空闲进程描述符（当没有其它可运行任务时，该任务才会启动）    struct task_struct *curr, *idle;    u64 clock;    int cpu;}

scheduler_tick└── task_tick    └── entity_tick        └── check_preempt_tick            └── resched_task                └── set_tsk_need_resched

// 'schedule()' is the scheduler function. // This is GOOD CODE! There probably won't be any reason to change // this, as it should work well in all circumstances (ie gives // IO-bound processes good response etc)...void schedule(void){    int i, next, c;    struct task_struct **p;    // 遍历所有任务，如果有信号，则需要唤醒 `TASK_INTERRUPTABLE` 的任务    for (p = &LAST_TASK; p > &FIRST_TASK; --p)        if (*p) {            if ((*p)->alarm && (*p)->alarm < jiffies) {                (*p)->signal |= (1 << (SIGALRM - 1));                (*p)->alarm = ;            }            if ((*p)->signal && (*p)->state == TASK_INTERRUPTIBLE)                (*p)->state = TASK_RUNNING;        }    while (1)    {        c = -1;        next = ;        i = NR_TASKS;        p = &task[NR_TASKS];        // 遍历所有任务，找到时间片长的那个        while (--i) {            if (!*--p)                continue;            if ((*p)->state == TASK_RUNNING && (*p)->counter > c)                c = (*p)->counter, next = i;        }        if (c)            break;        // 遍历任务，重新设值时间片        for (p = &LAST_TASK; p > &FIRST_TASK; --p)            if (*p)                (*p)->counter = ((*p)->counter >> 1) + (*p)->priority;    }    // 切换到下一个需要执行的任务    switch_to(next);}

// schedule() 算法会遍历所有的任务（O(N)），并且计算出每个任务的// goodness 值，且挑选出「好」的任务来运行。// 以下是部分核心源码，主要是了解下它的思路。asmlinkage void schedule(void){    // 任务（进程）描述符：    // 1. prev: 当前正在运行的任务    // 2. next: 下一个将运行的任务    // 3. p: 当前正在遍历的任务    struct task_struct *prev, *next, *p;    int this_cpu, c; // c 表示权重值repeat_schedule:    // 默认选中的任务    next = idle_task(this_cpu);    c = -1000;    list_for_each(tmp, &runqueue_head) {        p = list_entry(tmp, struct task_struct, run_list);        if (can_schedule(p, this_cpu)) {            int weight = goodness(p, this_cpu, prev->active_mm);            if (weight > c)                c = weight, next = p;        }    }}

struct runqueue {    unsigned long nr_running; /* 可运行的任务总数（某个 CPU） */    struct prio_array *active; /* 指向 active 的队列的指针 */    struct prio_array *expired; /* 指向 expired 的队列的指针 */    struct prio_array arrays[2]; /* 实际存放不同优先级对应的任务链表 */}

struct prio_array {    int nr_active; /* 列表中的任务总数 */    unsigned long bitmap[BITMAP_SIZE]; /* 位图表示对应优先级链表是否有任务存在 */    struct list_head queue[MAX_PRIO]; /* 任务队列（每种优先级对应一个双向链表） */};

struct cfs_rq{    // 所有任务的累计权重值    struct load_weight load;    // 表示该队列中有多少个可运行的任务    unsigned int nr_running;    // 运行队列中小的 vruntime    u64 min_vruntime;    // 红黑树的根节点，指向运行任务队列    struct rb_root tasks_timeline;    // 下一个即将被调度的任务    struct rb_node *rb_leftmost;    // 指向当前正在运行的调度单元    struct sched_entity *curr;}

struct sched_entity{    // 表示调度单元的负载权重（比如该调度单元是一个组，则该值就是该组下所有线程的负载权重的组合）    struct load_weight load; /* for load-balancing */    // 表示红黑树的节点    struct rb_node run_node;    // 表示当前调度单元是否位于运行队列    unsigned int on_rq;    // 开始执行时间    u64 exec_start;    // 总共运行的时间，该值是通过 `update_curr()` 更新的。    u64 sum_exec_runtime;    // 基于虚拟时钟计算出该调度单元已运行的时间    u64 vruntime;
    // 用于记录之前运行的时间之和    u64 prev_sum_exec_runtime;};

static void update_curr(struct cfs_rq *cfs_rq){    struct sched_entity *curr = cfs_rq->curr;    u64 now = rq_clock_task(rq_of(cfs_rq));    u64 delta_exec;    if (unlikely(!curr))        return;    // 计算出调度单元开始执行时间和当前之间的差值，即真实运行时间    delta_exec = now - curr->exec_start;    curr->vruntime += calc_delta_fair(delta_exec, curr);    update_min_vruntime(cfs_rq);}
static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se){    // 如果任务的优先级是默认的优先级（内部 nice 值是 120），那么虚拟运行时间    // 就是真实运行时间。否则，会基于 `__calc_delta` 计算出虚拟运行时间。    if (unlikely(se->load.weight != NICE_0_LOAD))        // 该计算过程基本等同于：        // delta = delta_exec * NICE_0_LOAD / cur->load.weight;        delta = __calc_delta(delta, NICE_0_LOAD, &se->load);    return delta;}
static void update_min_vruntime(struct cfs_rq *cfs_rq){    u64 vruntime = cfs_rq->min_vruntime;    if (cfs_rq->curr)        // 如果此时有任务在运行，就更新小运行时间为当前任务的 vruntime        vruntime = cfs_rq->curr->vruntime;    if (cfs_rq->rb_leftmost)    {        // 获得下一个要运行的调度单元        struct sched_entity *se = rb_entry(cfs_rq->rb_leftmost,                                           struct sched_entity,                                           run_node);        if (!cfs_rq->curr)            vruntime = se->vruntime;        else            // 保证 min_vruntime 是二者之间较小的那个值            vruntime = min_vruntime(vruntime, se->vruntime);    }
    // 这里之所以去二者之间的大值，是为了保证 min_vruntime 能够单调增长    // 可以想想为什么需要这样做？    cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime);}

struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq){    // 其实这里取的是缓存的 leftmost 节点    // 所以执行就会更快了    struct rb_node *left = cfs_rq->rb_leftmost;    if (!left)        return NULL;    return rb_entry(left, struct sched_entity, run_node);}

struct sched_rt_entity{    struct list_head run_list;    unsigned long timeout;    unsigned long watchdog_stamp;    unsigned int time_slice;    struct sched_rt_entity *back;    struct sched_rt_entity *parent;    /* rq on which this entity is (to be) queued: */    struct rt_rq *rt_rq;};

int sched_rr_timeslice = RR_TIMESLICE;static unsigned int get_rr_interval_rt(struct rq *rq,                                       struct task_struct *task){    if (task->policy == SCHED_RR)        return sched_rr_timeslice;    else        return ;}

/* Real-Time classes' related field in a runqueue: */struct rt_rq{    // 所有相同优先级的实时任务都保存在 `active.queue[prio]` 链表中    struct rt_prio_array active;    unsigned int rt_nr_running;    struct rq *rq; /* main runqueue */};
/** This is the priority-queue data structure of the RT scheduling class:*/struct rt_prio_array{    /* include 1 bit for delimiter */    // 类似 O(1) 调度器，使用位图来标记对应优先级的链表是否为空    DECLARE_BITMAP(bitmap, MAX_RT_PRIO + 1);    struct list_head queue[MAX_RT_PRIO];};