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 ... 0 ... 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 = 0; } if ((*p)->signal && (*p)->state == TASK_INTERRUPTIBLE) (*p)->state = TASK_RUNNING; } while (1) { c = -1; next = 0; 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 0;}

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