linux调度器源码分析

本文为原创，转载请注明：http://www.CUOXin.com/tolimit/

• 公平：保证每个进程得到合理的CPU时间。
• 高效：使CPU保持忙碌状态，即总是有进程在CPU上运行。
• 响应时间：使交互用户的响应时间尽可能短。
• 周转时间：使批处理用户等待输出的时间尽可能短。
• 吞吐量：使单位时间内处理的进程数量尽可能多。
• 负载均衡：在多核多处理器系统中提供更高的性能

• 实时进程：对系统的响应时间要求很高，它们需要短的响应时间，并且这个时间的变化非常小，典型的实时进程有音乐播放器，视频播放器等。
• 普通进程：包括交互进程和非交互进程，交互进程如文本编辑器，它会不断的休眠，又不断地通过鼠标键盘进行唤醒，而非交互进程就如后台维护进程，他们对IO，响应时间没有很高的要求，比如编译器。

• SCHED_NORMAL：普通进程使用的调度策略，现在此调度策略使用的是CFS调度器。
• SCHED_FIFO：实时进程使用的调度策略，此调度策略的进程一旦使用CPU则一直运行，直到有比其更高优先级的实时进程进入队列，或者其自动放弃CPU，适用于时间性要求比较高，但每次运行时间比较短的进程。
• SCHED_RR：实时进程使用的时间片轮转法策略，实时进程的时间片用完后，调度器将其放到队列末尾，这样每个实时进程都可以执行一段时间。适用于每次运行时间比较长的实时进程。

• 调用cond_resched()时
• 显式调用schedule()时
• 从系统调用或者异常中断返回用户空间时
• 从中断上下文返回用户空间时

• 在系统调用或者异常中断上下文中调用PReempt_enable()时(多次调用preempt_enable()时，系统只会在最后一次调用时会调度)
• 在中断上下文中，从中断处理函数返回到可抢占的上下文时(这里是中断下半部，中断上半部实际上会关中断，而新的中断只会被登记，由于上半部处理很快，上半部处理完成后才会执行新的中断信号，这样就形成了中断可重入)

　　图1

• 用户ID：按照进程的USER ID进行分组，在对应的/sys/kernel/uid/目录下会生成一个cpu.share的文件，可以通过配置该文件来配置用户所占CPU时间比例。
• cgourp(control group)：生成组用于限制其所有进程，比如我生成一个组(生成后此组为空，里面没有进程)，设置其CPU使用率为10%，并把一个进程丢进这个组中，那么这个进程最多只能使用CPU的10%，如果我们将多个进程丢进这个组，这个组的所有进程平分这个10%。

 1 /* 进程组，用于实现组调度 */ 2 struct task_group { 3     /* 用于进程找到其所属进程组结构 */ 4     struct cgroup_subsys_state CSS; 5  6 #ifdef CONFIG_FAIR_GROUP_SCHED 7     /* CFS调度器的进程组变量，在 alloc_fair_sched_group() 中进程初始化及分配内存 */ 8     /* 该进程组在每个CPU上都有对应的一个调度实体，因为有可能此进程组同时在两个CPU上运行(它的A进程在CPU0上运行，B进程在CPU1上运行) */ 9     struct sched_entity **se;10     /* 进程组在每个CPU上都有一个CFS运行队列(为什么需要，稍后解释) */11     struct cfs_rq **cfs_rq;12     /* 用于保存优先级默认为NICE 0的优先级 */13     unsigned long shares;14 15 #ifdef    CONFIG_SMP16     atomic_long_t load_avg;17     atomic_t runnable_avg;18 #endif19 #endif20 21 #ifdef CONFIG_RT_GROUP_SCHED22     /* 实时进程调度器的进程组变量，同 CFS */23     struct sched_rt_entity **rt_se;24     struct rt_rq **rt_rq;25 26     struct rt_bandwidth rt_bandwidth;27 #endif28 29     struct rcu_head rcu;30     /* 用于建立进程链表(属于此调度组的进程链表) */31     struct list_head list;32 33     /* 指向其上层的进程组，每一层的进程组都是它上一层进程组的运行队列的一个调度实体，在同一层中，进程组和进程被同等对待 */34     struct task_group *parent;35     /* 进程组的兄弟结点链表 */36     struct list_head siblings;37     /* 进程组的儿子结点链表 */38     struct list_head children;39 40 #ifdef CONFIG_SCHED_AUTOGROUP41     struct autogroup *autogroup;42 #endif43 44     struct cfs_bandwidth cfs_bandwidth;45 };

 1 /* 一个调度实体(红黑树的一个结点)，其包含一组或一个指定的进程，包含一个自己的运行队列，一个父亲指针，一个指向需要调度的运行队列指针 */ 2 struct sched_entity { 3     /* 权重，在数组prio_to_weight[]包含优先级转权重的数值 */ 4     struct load_weight    load;        /* for load-balancing */ 5     /* 实体在红黑树对应的结点信息 */ 6     struct rb_node        run_node;     7     /* 实体所在的进程组 */ 8     struct list_head    group_node; 9     /* 实体是否处于红黑树运行队列中 */10     unsigned int        on_rq;11 12     /* 开始运行时间 */13     u64            exec_start;14     /* 总运行时间 */15     u64            sum_exec_runtime;16     /* 虚拟运行时间，在时间中断或者任务状态发生改变时会更新17      * 其会不停增长，增长速度与load权重成反比，load越高，增长速度越慢，就越可能处于红黑树最左边被调度18      * 每次时钟中断都会修改其值19      * 具体见calc_delta_fair()函数20      */21     u64            vruntime;22     /* 进程在切换进CPU时的sum_exec_runtime值 */23     u64            prev_sum_exec_runtime;24 25     /* 此调度实体中进程移到其他CPU组的数量 */26     u64            nr_migrations;27 28 #ifdef CONFIG_SCHEDSTATS29     /* 用于统计一些数据 */30     struct sched_statistics statistics;31 #endif32 33 #ifdef CONFIG_FAIR_GROUP_SCHED34     /* 代表此进程组的深度，每个进程组都比其parent调度组深度大1 */35     int            depth;36     /* 父亲调度实体指针，如果是进程则指向其运行队列的调度实体，如果是进程组则指向其上一个进程组的调度实体37      * 在 set_task_rq 函数中设置38      */39     struct sched_entity    *parent;40     /* 实体所处红黑树运行队列 */41     struct cfs_rq        *cfs_rq;        42     /* 实体的红黑树运行队列，如果为NULL表明其是一个进程，若非NULL表明其是调度组 */43     struct cfs_rq        *my_q;44 #endif45 46 #ifdef CONFIG_SMP47     /* Per-entity load-tracking */48     struct sched_avg    avg;49 #endif50 };

　　实际上，红黑树是根据 structrb_node 建立起关系的，不过 struct rb_node 与 struct sched_entity 是一一对应关系，也可以简单看为一个红黑树结点就是一个调度实体。可以看出，在 struct sched_entity 结构中，包含了一个进程(或进程组)调度的全部数据，其被包含在 struct task_struct 结构中的se中，如下：

 1 struct task_struct { 2     ........ 3     /* 表示是否在运行队列 */ 4     int on_rq; 5  6     /* 进程优先级  7      * prio: 动态优先级，范围为100~139，与静态优先级和补偿(bonus)有关 8      * static_prio: 静态优先级，static_prio = 100 + nice + 20 (nice值为-20~19,所以static_prio值为100~139) 9      * normal_prio: 没有受优先级继承影响的常规优先级，具体见normal_prio函数，跟属于什么类型的进程有关10      */11     int prio, static_prio, normal_prio;12     /* 实时进程优先级 */13     unsigned int rt_priority;14     /* 调度类，调度处理函数类 */15     const struct sched_class *sched_class;16     /* 调度实体(红黑树的一个结点) */17     struct sched_entity se;18     /* 调度实体(实时调度使用) */19     struct sched_rt_entity rt;20 #ifdef CONFIG_CGROUP_SCHED21     /* 指向其所在进程组 */22     struct task_group *sched_task_group;23 #endif24     ........25 }

　　在 struct sched_entity 结构中，值得我们注意的成员是：

• load：权重，通过优先级转换而成，是vruntime计算的关键。
• on_rq：表明是否处于CFS红黑树运行队列中，需要明确一个观点就是，CFS运行队列里面包含有一个红黑树，但这个红黑树并不是CFS运行队列的全部，因为红黑树仅仅是用于选择出下一个调度程序的算法。很简单的一个例子，普通程序运行时，其并不在红黑树中，但是还是处于CFS运行队列中，其on_rq为真。只有准备退出、即将睡眠等待和转为实时进程的进程其CFS运行队列的on_rq为假。
• vruntime：虚拟运行时间，调度的关键，其计算公式：一次调度间隔的虚拟运行时间 = 实际运行时间 * (NICE_0_LOAD / 权重)。可以看出跟实际运行时间和权重有关，红黑树就是以此作为排序的标准，优先级越高的进程在运行时其vruntime增长的越慢，其可运行时间相对就长，而且也越有可能处于红黑树的最左结点，调度器每次都选择最左边的结点为下一个调度进程。注意其值为单调递增，在每个调度器的时钟中断时当前进程的虚拟运行时间都会累加。单纯的说就是进程们都在比谁的vruntime最小，最小的将被调度。
• cfs_rq：此调度实体所处于的CFS运行队列。
• my_q：如果此调度实体代表的是一个进程组，那么此调度实体就包含有一个自己的CFS运行队列，其CFS运行队列中存放的是此进程组中的进程，这些进程就不会在其他CFS运行队列的红黑树中被包含(包括顶层红黑树也不会包含他们，他们只属于这个进程组的红黑树)。

　　而在 struct task_struct 结构中，我们注意到有个调度类，里面包含的是调度处理函数，它具体如下：

 1 struct sched_class { 2     /* 下一优先级的调度类 3      * 调度类优先级顺序: stop_sched_class -> dl_sched_class -> rt_sched_class -> fair_sched_class -> idle_sched_class 4      */ 5     const struct sched_class *next; 6  7     /* 将进程加入到运行队列中，即将调度实体（进程）放入红黑树中，并对 nr_running 变量加1 */ 8     void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags); 9     /* 从运行队列中删除进程，并对 nr_running 变量中减1 */10     void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);11     /* 放弃CPU，在 compat_yield sysctl 关闭的情况下，该函数实际上执行先出队后入队；在这种情况下，它将调度实体放在红黑树的最右端 */12     void (*yield_task) (struct rq *rq);13     bool (*yield_to_task) (struct rq *rq, struct task_struct *p, bool preempt);14 15     /* 检查当前进程是否可被新进程抢占 */16     void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);17 18     /*19      * It is the responsibility of the pick_next_task() method that will20      * return the next task to call put_prev_task() on the @prev task or21      * something equivalent.22      *23      * May return RETRY_TASK when it finds a higher prio class has runnable24      * tasks.25      */26     /* 选择下一个应该要运行的进程运行 */27     struct task_struct * (*pick_next_task) (struct rq *rq,28                         struct task_struct *prev);29     /* 将进程放回运行队列 */30     void (*put_prev_task) (struct rq *rq, struct task_struct *p);31 32 #ifdef CONFIG_SMP33     /* 为进程选择一个合适的CPU */34     int (*select_task_rq)(struct task_struct *p, int task_cpu, int sd_flag, int flags);35     /* 迁移任务到另一个CPU */36     void (*migrate_task_rq)(struct task_struct *p, int next_cpu);37     /* 用于上下文切换后 */38     void (*post_schedule) (struct rq *this_rq);39     /* 用于进程唤醒 */40     void (*task_waking) (struct task_struct *task);41     void (*task_woken) (struct rq *this_rq, struct task_struct *task);42     /* 修改进程的CPU亲和力(affinity) */43     void (*set_cpus_allowed)(struct task_struct *p,44                  const struct cpumask *newmask);45     /* 启动运行队列 */46     void (*rq_online)(struct rq *rq);47     /* 禁止运行队列 */48     void (*rq_offline)(struct rq *rq);49 #endif50     /* 当进程改变它的调度类或进程组时被调用 */51     void (*set_curr_task) (struct rq *rq);52     /* 该函数通常调用自 time tick 函数；它可能引起进程切换。这将驱动运行时（running）抢占 */53     void (*task_tick) (struct rq *rq, struct task_struct *p, int queued);54     /* 在进程创建时调用，不同调度策略的进程初始化不一样 */55     void (*task_fork) (struct task_struct *p);56     /* 在进程退出时会使用 */57     void (*task_dead) (struct task_struct *p);58 59     /* 用于进程切换 */60     void (*switched_from) (struct rq *this_rq, struct task_struct *task);61     void (*switched_to) (struct rq *this_rq, struct task_struct *task);62     /* 改变优先级 */63     void (*prio_changed) (struct rq *this_rq, struct task_struct *task,64              int oldprio);65 66     unsigned int (*get_rr_interval) (struct rq *rq,67                      struct task_struct *task);68 69     void (*update_curr) (struct rq *rq);70 71 #ifdef CONFIG_FAIR_GROUP_SCHED72     void (*task_move_group) (struct task_struct *p, int on_rq);73 #endif74 };

　　这个调度类具体有什么用呢，实际上在内核中不同的调度算法它们的操作都不相同，为了方便修改、替换调度算法，使用了调度类，每个调度算法只需要实现自己的调度类就可以了，CFS算法有它的调度类，SCHED_FIFO也有它自己的调度类，当一个进程创建时，用什么调度算法就将其 task_struct->sched_class 指向其相应的调度类，调度器每次调度处理时，就通过当前进程的调度类函数进程操作，大大提高了可移植性和易修改性。

 1 /* CFS调度的运行队列，每个CPU的rq会包含一个cfs_rq，而每个组调度的sched_entity也会有自己的一个cfs_rq队列 */ 2 struct cfs_rq { 3     /* CFS运行队列中所有进程的总负载 */ 4     struct load_weight load; 5     /* 6      * nr_running: cfs_rq中调度实体数量 7      * h_nr_running: 只对进程组有效，其下所有进程组中cfs_rq的nr_running之和 8      */ 9     unsigned int nr_running, h_nr_running;10 11     u64 exec_clock;12     /* 当前CFS队列上最小运行时间，单调递增13      * 两种情况下更新该值: 14      * 1、更新当前运行任务的累计运行时间时15      * 2、当任务从队列删除去，如任务睡眠或退出，这时候会查看剩下的任务的vruntime是否大于min_vruntime，如果是则更新该值。16      */17     u64 min_vruntime;18 #ifndef CONFIG_64BIT19     u64 min_vruntime_copy;20 #endif21     /* 该红黑树的root */22     struct rb_root tasks_timeline;23     /* 下一个调度结点(红黑树最左边结点，最左边结点就是下个调度实体) */24     struct rb_node *rb_leftmost;25 26     /*27      * 'curr' points to currently running entity on this cfs_rq.28      * It is set to NULL otherwise (i.e when none are currently running).29      */30     /*31      * curr: 当前正在运行的sched_entity（对于组虽然它不会在cpu上运行，但是当它的下层有一个task在cpu上运行，那么它所在的cfs_rq就把它当做是该cfs_rq上当前正在运行的sched_entity）32      * next: 表示有些进程急需运行，即使不遵从CFS调度也必须运行它，调度时会检查是否next需要调度，有就调度next33      *34      * skip: 略过进程(不会选择skip指定的进程调度)35      */36     struct sched_entity *curr, *next, *last, *skip;37 38 #ifdef    CONFIG_SCHED_DEBUG39     unsigned int nr_spread_over;40 #endif41 42 #ifdef CONFIG_SMP43     /*44      * CFS Load tracking45      * Under CFS, load is tracked on a per-entity basis and aggregated up.46      * This allows for the description of both thread and group usage (in47      * the FAIR_GROUP_SCHED case).48      */49     unsigned long runnable_load_avg, blocked_load_avg;50     atomic64_t decay_counter;51     u64 last_decay;52     atomic_long_t removed_load;53 54 #ifdef CONFIG_FAIR_GROUP_SCHED55     /* Required to track per-cpu representation of a task_group */56     u32 tg_runnable_contrib;57     unsigned long tg_load_contrib;58 59     /*60      * h_load = weight * f(tg)61      *62      * Where f(tg) is the recursive weight fraction assigned to63      * this group.64      */65     unsigned long h_load;66     u64 last_h_load_update;67     struct sched_entity *h_load_next;68 #endif /* CONFIG_FAIR_GROUP_SCHED */69 #endif /* CONFIG_SMP */70 71 #ifdef CONFIG_FAIR_GROUP_SCHED72     /* 所属于的CPU rq */73     struct rq *rq;    /* cpu runqueue to which this cfs_rq is attached */74 75     /*76      * leaf cfs_rqs are those that hold tasks (lowest schedulable entity in77      * a hierarchy). Non-leaf lrqs hold other higher schedulable entities78      * (like users, containers etc.)79      *80      * leaf_cfs_rq_list ties together list of leaf cfs_rq's in a cpu. This81      * list is used during load balance.82      */83     int on_list;84     struct list_head leaf_cfs_rq_list;85     /* 拥有该CFS运行队列的进程组 */86     struct task_group *tg;    /* group that "owns" this runqueue */87 88 #ifdef CONFIG_CFS_BANDWIDTH89     int runtime_enabled;90     u64 runtime_expires;91     s64 runtime_remaining;92 93     u64 throttled_clock, throttled_clock_task;94     u64 throttled_clock_task_time;95     int throttled, throttle_count;96     struct list_head throttled_list;97 #endif /* CONFIG_CFS_BANDWIDTH */98 #endif /* CONFIG_FAIR_GROUP_SCHED */99 };

• load：其保存的是进程组中所有进程的权值总和，需要注意子进程计算vruntime时需要用到进程组的load。

　　每个CPU都有自己的 struct rq 结构，其用于描述在此CPU上所运行的所有进程，其包括一个实时进程队列和一个根CFS运行队列，在调度时，调度器首先会先去实时进程队列找是否有实时进程需要运行，如果没有才会去CFS运行队列找是否有进行需要运行，这就是为什么常说的实时进程优先级比普通进程高，不仅仅体现在prio优先级上，还体现在调度器的设计上，至于dl运行队列，我暂时还不知道有什么用处，其优先级比实时进程还高，但是创建进程时如果创建的是dl进程创建会错误(具体见sys_fork)。

  1 /* CPU运行队列，每个CPU包含一个struct rq */  2 struct rq {  3     /* 处于运行队列中所有就绪进程的load之和 */  4     raw_spinlock_t lock;  5   6     /*  7      * nr_running and cpu_load should be in the same cacheline because  8      * remote CPUs use both these fields when doing load calculation.  9      */ 10     /* 此CPU上总共就绪的进程数，包括cfs，rt和正在运行的 */ 11     unsigned int nr_running; 12 #ifdef CONFIG_NUMA_BALANCING 13     unsigned int nr_numa_running; 14     unsigned int nr_preferred_running; 15 #endif 16     #define CPU_LOAD_IDX_MAX 5 17     /* 根据CPU历史情况计算的负载，cpu_load[0]一直等于load.weight，当达到负载平衡时，cpu_load[1]和cpu_load[2]都应该等于load.weight */ 18     unsigned long cpu_load[CPU_LOAD_IDX_MAX]; 19     /* 最后一次更新 cpu_load 的时间 */ 20     unsigned long last_load_update_tick; 21 #ifdef CONFIG_NO_HZ_COMMON 22     u64 nohz_stamp; 23     unsigned long nohz_flags; 24 #endif 25 #ifdef CONFIG_NO_HZ_FULL 26     unsigned long last_sched_tick; 27 #endif 28     /* 是否需要更新rq的运行时间 */ 29     int skip_clock_update; 30  31     /* capture load from *all* tasks on this cpu: */ 32     /* CPU负载，该CPU上所有可运行进程的load之和，nr_running更新时这个值也必须更新 */ 33     struct load_weight load; 34     unsigned long nr_load_updates; 35     /* 进行上下文切换次数，只有proc会使用这个 */ 36     u64 nr_switches; 37  38     /* cfs调度运行队列，包含红黑树的根 */ 39     struct cfs_rq cfs; 40     /* 实时调度运行队列 */ 41     struct rt_rq rt; 42     struct dl_rq dl; 43  44 #ifdef CONFIG_FAIR_GROUP_SCHED 45     /* list of leaf cfs_rq on this cpu: */ 46     struct list_head leaf_cfs_rq_list; 47  48     struct sched_avg avg; 49 #endif /* CONFIG_FAIR_GROUP_SCHED */ 50  51     /* 52      * This is part of a global counter where only the total sum 53      * over all CPUs matters. A task can increase this counter on 54      * one CPU and if it got migrated afterwards it may decrease 55      * it on another CPU. Always updated under the runqueue lock: 56      */ 57      /* 曾经处于队列但现在处于TASK_UNINTERRUPTIBLE状态的进程数量 */ 58     unsigned long nr_uninterruptible; 59  60     /* 61      * curr: 当前正在此CPU上运行的进程 62      * idle: 当前CPU上idle进程的指针，idle进程用于当CPU没事做的时候调用，它什么都不执行 63      */ 64     struct task_struct *curr, *idle, *stop; 65     /* 下次进行负载平衡执行时间 */ 66     unsigned long next_balance; 67     /* 在进程切换时用来存放换出进程的内存描述符地址 */ 68     struct mm_struct *prev_mm; 69  70     /* rq运行时间 */ 71     u64 clock; 72     u64 clock_task; 73  74     atomic_t nr_iowait; 75  76 #ifdef CONFIG_SMP 77     struct root_domain *rd; 78     /* 当前CPU所在基本调度域，每个调度域包含一个或多个CPU组，每个CPU组包含该调度域中一个或多个CPU子集，负载均衡都是在调度域中的组之间完成的，不能跨域进行负载均衡 */ 79     struct sched_domain *sd; 80  81     unsigned long cpu_capacity; 82  83     unsigned char idle_balance; 84     /* For active balancing */ 85     int post_schedule; 86     /* 如果需要把进程迁移到其他运行队列，就需要设置这个位 */ 87     int active_balance; 88     int push_cpu; 89     struct cpu_stop_work active_balance_work; 90  91     /* 该运行队列所属CPU */ 92     int cpu; 93     int online; 94  95     struct list_head cfs_tasks; 96  97     u64 rt_avg; 98     /* 该运行队列存活时间 */ 99     u64 age_stamp;100     u64 idle_stamp;101     u64 avg_idle;102 103     /* This is used to determine avg_idle's max value */104     u64 max_idle_balance_cost;105 #endif106 107 #ifdef CONFIG_IRQ_TIME_ACCOUNTING108     u64 prev_irq_time;109 #endif110 #ifdef CONFIG_PARAVIRT111     u64 prev_steal_time;112 #endif113 #ifdef CONFIG_PARAVIRT_TIME_ACCOUNTING114     u64 prev_steal_time_rq;115 #endif116 117     /* calc_load related fields */118     /* 用于负载均衡 */119     unsigned long calc_load_update;120     long calc_load_active;121 122 #ifdef CONFIG_SCHED_HRTICK123 #ifdef CONFIG_SMP124     int hrtick_csd_pending;125     struct call_single_data hrtick_csd;126 #endif127     /* 调度使用的高精度定时器 */128     struct hrtimer hrtick_timer;129 #endif130 131 #ifdef CONFIG_SCHEDSTATS132     /* latency stats */133     struct sched_info rq_sched_info;134     unsigned long long rq_cpu_time;135     /* could above be rq->cfs_rq.exec_clock + rq->rt_rq.rt_runtime ? */136 137     /* sys_sched_yield() stats */138     unsigned int yld_count;139 140     /* schedule() stats */141     unsigned int sched_count;142     unsigned int sched_goidle;143 144     /* try_to_wake_up() stats */145     unsigned int ttwu_count;146     unsigned int ttwu_local;147 #endif148 149 #ifdef CONFIG_SMP150     struct llist_head wake_list;151 #endif152 153 #ifdef CONFIG_CPU_IDLE154     /* Must be inspected within a rcu lock section */155     struct cpuidle_state *idle_state;156 #endif157 };