Linux内核必懂知识—调度器和完全公平调度器CFS

调度器分析

调度器

• 内核中安排进程执行的模块，用以切换进程状态。

• 做两件事：选择某些就绪进程来执行；打断某些执行的进程让其变为就绪状态。

• 分配CPU时间的基本依据：进程优先级。 上下文切换（context switch）：将进程在CPU中切换执行的过程，内核承担 此任务，负责重建和存储被切换掉之前的CPU状态。

调度类sched_class结构体与调度类

sched_class结构体表示调度类，定义在kernel/sched/sched.h。

• 成员解析 ecqueue_task:向就绪队列添加一个进程，某个任务进入可运行状态时，该函数将会被调用，它将调度实体放入到红黑树中。 dequeue_task:将一个进程从就绪队列中进行删除，当某个任务退出可运行状态时调用该函数，它将从红黑树中去掉对应调度实体。 yield_task:在进程想要资源放弃对处理器的控制权时，可食用在sched_yield系统调用，会调用内核API去处理操作。 check_preempt_curr:检查当前运行任务是否被抢占。 pick_next_task:选在接下来要运行的最合适的实体（进程）。 put_prev_task:用于另一个进程代替当前运行的进程。 set_curr_task:当任务修改它的调用类或修改它的任务组时，将调用这个函数。 task_tick:在每次激活周期调度器时，由周期性调度器调用。

• 源码注释

1.  
   // 系统当中有多个调度类，按照调度优先级排成一个链表，下一个优先级调度类
2.  
   const struct sched_class *next;
3.  
   // 将进程加入到执行队列当中，即将调度实体（进程）存放到红黑树中，并对nr_running变量自动加1
4.  
   void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
5.  
   // 从执行队列当中删除进程，并对nr_running变量自动减1
6.  
   void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
7.  
   // 放弃CPU执行权,实际上该函数执行先出队后入队,在这种情况下,它直接将调度实体放在红黑树的最右端
8.  
   void (*yield_task) (struct rq *rq);
9.  
   bool (*yield_to_task) (struct rq *rq, struct task_struct *p, bool preempt);
10.  
    // 用于检查当前进程是否可以被新的进程抢占
11.  
    void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);
12.  
     
13.  
    /*
14.  
    * It is the responsibility of the pick_next_task() method that will
15.  
    * return the next task to call put_prev_task() on the @prev task or
16.  
    * something equivalent.
17.  
    *
18.  
    * May return RETRY_TASK when it finds a higher prio class has runnable
19.  
    * tasks.
20.  
    */
21.  
    // 选择下一个应该要运行的进程
22.  
    struct task_struct * (*pick_next_task) (struct rq *rq,
23.  
    struct task_struct *prev);
24.  
    // 将进程放回到运行队列当中
25.  
    void (*put_prev_task) (struct rq *rq, struct task_struct *p);
26.  
     
27.  
    #ifdef CONFIG_SMP
28.  
    // 为进程选择一个合适的CPU
29.  
    int (*select_task_rq)(struct task_struct *p, int task_cpu, int sd_flag, int flags);
30.  
    // 迁移任务到另一个CPU
31.  
    void (*migrate_task_rq)(struct task_struct *p);
32.  
    // 专门用户唤醒进程
33.  
    void (*task_waking) (struct task_struct *task);
34.  
    void (*task_woken) (struct rq *this_rq, struct task_struct *task);
35.  
    // 修改进程在CPU的亲和力
36.  
    void (*set_cpus_allowed)(struct task_struct *p,
37.  
    const struct cpumask *newmask);
38.  
    // 启动运行队列
39.  
    void (*rq_online)(struct rq *rq);
40.  
    // 禁止运行队列
41.  
    void (*rq_offline)(struct rq *rq);
42.  
    #endif
43.  
    // 当进程改变它的调度类或进程组时被调用
44.  
    void (*set_curr_task) (struct rq *rq);
45.  
    // 调用自己time_tick函数，可能引起进程切换，将驱动运行时抢占
46.  
    void (*task_tick) (struct rq *rq, struct task_struct *p, int queued);
47.  
    // 当进程创建时候调用，不同调度策略的进程初始化不一样
48.  
    void (*task_fork) (struct task_struct *p);
49.  
    // 进程退出时会使用
50.  
    void (*task_dead) (struct task_struct *p);
51.  
     
52.  
    /*
53.  
    * The switched_from() call is allowed to drop rq->lock, therefore we
54.  
    * cannot assume the switched_from/switched_to pair is serliazed by
55.  
    * rq->lock. They are however serialized by p->pi_lock.
56.  
    */
57.  
    // 专门用于进程切换操作
58.  
    void (*switched_from) (struct rq *this_rq, struct task_struct *task);
59.  
    void (*switched_to) (struct rq *this_rq, struct task_struct *task);
60.  
    // 更改进程优先级
61.  
    void (*prio_changed) (struct rq *this_rq, struct task_struct *task,
62.  
    int oldprio);
63.  
     
64.  
    unsigned int (*get_rr_interval) (struct rq *rq,
65.  
    struct task_struct *task);
66.  
     
67.  
    void (*update_curr) (struct rq *rq);
68.  
     
69.  
    #ifdef CONFIG_FAIR_GROUP_SCHED
70.  
    void (*task_move_group) (struct task_struct *p);
71.  
    #endif
72.  
    };
73.  
    ```struct sched_class {
74.  
    // 系统当中有多个调度类，按照调度优先级排成一个链表，下一个优先级调度类
75.  
    const struct sched_class *next;
76.  
    // 江金城加入到执行队列当中，即将调度实体（进程）存放到红黑树中，并对nr_running变量自动加1
77.  
    void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
78.  
    // 从执行队列当中删除进程，并对nr_running变量自动减1
79.  
    void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
80.  
    // 放弃CPU执行权,实际上该函数执行先出队后入队,在这种情况下,它直接将调度实体放在红黑树的最右端
81.  
    void (*yield_task) (struct rq *rq);
82.  
    bool (*yield_to_task) (struct rq *rq, struct task_struct *p, bool preempt);
83.  
    // 用于检查当前进程是否可以被新的进程抢占
84.  
    void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);
85.  
     
86.  
    /*
87.  
    * It is the responsibility of the pick_next_task() method that will
88.  
    * return the next task to call put_prev_task() on the @prev task or
89.  
    * something equivalent.
90.  
    *
91.  
    * May return RETRY_TASK when it finds a higher prio class has runnable
92.  
    * tasks.
93.  
    */
94.  
    // 选择下一个应该要运行的进程
95.  
    struct task_struct * (*pick_next_task) (struct rq *rq,
96.  
    struct task_struct *prev);
97.  
    // 将进程放回到运行队列当中
98.  
    void (*put_prev_task) (struct rq *rq, struct task_struct *p);
99.  
     
100.  
     #ifdef CONFIG_SMP
101.  
     // 为进程选择一个合适的CPU
102.  
     int (*select_task_rq)(struct task_struct *p, int task_cpu, int sd_flag, int flags);
103.  
     // 迁移任务到另一个CPU
104.  
     void (*migrate_task_rq)(struct task_struct *p);
105.  
     // 专门用户唤醒进程
106.  
     void (*task_waking) (struct task_struct *task);
107.  
     void (*task_woken) (struct rq *this_rq, struct task_struct *task);
108.  
     // 修改进程在CPU的亲和力
109.  
     void (*set_cpus_allowed)(struct task_struct *p,
110.  
     const struct cpumask *newmask);
111.  
     // 启动运行队列
112.  
     void (*rq_online)(struct rq *rq);
113.  
     // 禁止运行队列
114.  
     void (*rq_offline)(struct rq *rq);
115.  
     #endif
116.  
     // 当进程改变它的调度类或进程组时被调用
117.  
     void (*set_curr_task) (struct rq *rq);
118.  
     // 调用自己time_tick函数，可能引起进程切换，将驱动运行时抢占
119.  
     void (*task_tick) (struct rq *rq, struct task_struct *p, int queued);
120.  
     // 当进程创建时候调用，不同调度策略的进程初始化不一样
121.  
     void (*task_fork) (struct task_struct *p);
122.  
     // 进程退出时会使用
123.  
     void (*task_dead) (struct task_struct *p);
124.  
      
125.  
     /*
126.  
     * The switched_from() call is allowed to drop rq->lock, therefore we
127.  
     * cannot assume the switched_from/switched_to pair is serliazed by
128.  
     * rq->lock. They are however serialized by p->pi_lock.
129.  
     */
130.  
     // 专门用于进程切换操作
131.  
     void (*switched_from) (struct rq *this_rq, struct task_struct *task);
132.  
     void (*switched_to) (struct rq *this_rq, struct task_struct *task);
133.  
     // 更改进程优先级
134.  
     void (*prio_changed) (struct rq *this_rq, struct task_struct *task,
135.  
     int oldprio);
136.  
      
137.  
     unsigned int (*get_rr_interval) (struct rq *rq,
138.  
     struct task_struct *task);
139.  
      
140.  
     void (*update_curr) (struct rq *rq);
141.  
      
142.  
     #ifdef CONFIG_FAIR_GROUP_SCHED
143.  
     void (*task_move_group) (struct task_struct *p);
144.  
     #endif
145.  
     };

Linux调度类

dl_sched_class、rt_sched_class、fair_sched_class及idle_sched_class等。每个进程都有对应一种调度策略，每一种调度策略又对应一种调度类（每一个调度类可以对应多种调度策略）。

1.  
   extern const struct sched_class stop_sched_class;
2.  
   extern const struct sched_class dl_sched_class;
3.  
   extern const struct sched_class rt_sched_class;
4.  
   extern const struct sched_class fair_sched_class;
5.  
   extern const struct sched_class idle_sched_class;

rt_sched_class类 实时调度器（调度策略:SCHED_FIFO SCHED_RR）
fair_sched_class类 完全公平调度器（调度策略：SCHED_NORMAL、SCHED_BATCH） 
SCHED_FIFO调度策略的实时进程永远比SCHED_NORMAL调度策略的普通进程优先运行。eg:pick_next_task函数。 
调度类优先级顺序：stop_sched_class > dl_sched_class > rt_sched_class > fair_sched_class > idle_sched_class. 
stop_sched_class：优先级最高的线程，会中断所有其他线程，并且不会被其他任务打断。 
dl_sched_class 
rt_sched_class：作用于实时线程。 
fair_sched_class： 公平调度器CFS，作用： 一般常用线程。 
idle_sched_class： 每个CPU的第一个PID=0线程，swapper，是一个静态线程。每个调度类属于
idle_sched_class。一般运行在开机过程和CPU异常时会做dump。 SCHED_NORMAL,SCHED_BATCH,SCHED_IDLE直接被映射到fair_sched_class； 
SCHED_RR,SCHED_FIFO与rt_sched_class相关联。

1.  
   * Simple, special scheduling class for the per-CPU stop tasks:
2.  
   */
3.  
   const struct sched_class stop_sched_class = {
4.  
   .next = &dl_sched_class,
5.  
    
6.  
   .enqueue_task = enqueue_task_stop,
7.  
   .dequeue_task = dequeue_task_stop,
8.  
   .yield_task = yield_task_stop,
9.  
    
10.  
    .check_preempt_curr = check_preempt_curr_stop,
11.  
     
12.  
    .pick_next_task = pick_next_task_stop,
13.  
    .put_prev_task = put_prev_task_stop,
14.  
     
15.  
    #ifdef CONFIG_SMP
16.  
    .select_task_rq = select_task_rq_stop,
17.  
    .set_cpus_allowed = set_cpus_allowed_common,
18.  
    #endif
19.  
     
20.  
    .set_curr_task = set_curr_task_stop,
21.  
    .task_tick = task_tick_stop,
22.  
     
23.  
    .get_rr_interval = get_rr_interval_stop,
24.  
     
25.  
    .prio_changed = prio_changed_stop,
26.  
    .switched_to = switched_to_stop,
27.  
    .update_curr = update_curr_stop,
28.  
    };

Linux调度核心选择下一个合适的task运行时，会按照优先级顺序遍历调度类的pick_next_task函数。

学习思维导图以及Linux内核相关学习视频，清晰版导图可以点击：linux内核学习资料 获取

Linux内核开发系统学习视频链接：Linux内核源码/内存调优/文件系统/进程管理/设备驱动/网络协议栈学习视频

优先级

• task_struct结构体中采用三个成员表示进程的优先级：prio和normal_prio表示动态优先级, static_prio表示进程的静态优先级。

• 内核将任务优先级划分，实时优先级范围是0到MAX_RT_PRIO-1（即99），而普通进 程的静态优先级范围是从MAX_RT_PRIO到MAX_PRIO-1（即100到139）。数字越小优先级越高。

1.  
   /*
2.  
   * Priority of a process goes from 0..MAX_PRIO-1, valid RT
3.  
   * priority is 0..MAX_RT_PRIO-1, and SCHED_NORMAL/SCHED_BATCH
4.  
   * tasks are in the range MAX_RT_PRIO..MAX_PRIO-1. Priority
5.  
   * values are inverted: lower p->prio value means higher priority.
6.  
   *
7.  
   * The MAX_USER_RT_PRIO value allows the actual maximum
8.  
   * RT priority to be separate from the value exported to
9.  
   * user-space. This allows kernel threads to set their
10.  
    * priority to a value higher than any user task. Note:
11.  
    * MAX_RT_PRIO must not be smaller than MAX_USER_RT_PRIO.
12.  
    */
13.  
     
14.  
    #define MAX_USER_RT_PRIO 100
15.  
    #define MAX_RT_PRIO MAX_USER_RT_PRIO
16.  
     
17.  
    #define MAX_PRIO (MAX_RT_PRIO NICE_WIDTH)
18.  
    #define DEFAULT_PRIO (MAX_RT_PRIO NICE_WIDTH / 2)

• 进程分类

• 实时进程（Real-Time Process）：优先级高、需要立即被执行的进程。

• 普通进程（Normal Process）:优先级低、更长执行时间的进程。

调度策略

unsigned int policy:保存进程的调度策略（5种）

• SCHED_NORMAL：用于普通进程，通过CFS调度器实现。

• SCHED_BATCH: 相当于SCHED_NORMAL分化版本，采用分时策略，根据动态优先级，分配CPU运行需要资源。用于非交互处理器消耗型进程。

• SCHED_IDLE:优先级最低，在系统空闲时才执行这类进程。系统负载很低时使用CFS。

• SCHED_FIFO:先进先出调度算法（实时调度策略），相同优先级任务先到先服务，高优先级任务可以抢占低优先级任务。

• SCHED_RR：轮流调度算法（实时调度策略）。

• SCHED_DEADLINE:新支持实时进程调度策略，针对突发性计算。

1.  
   /*
2.  
   * Scheduling policies
3.  
   */
4.  
   #define SCHED_NORMAL 0
5.  
   #define SCHED_FIFO 1
6.  
   #define SCHED_RR 2
7.  
   #define SCHED_BATCH 3
8.  
   /* SCHED_ISO: reserved but not implemented yet */
9.  
   #define SCHED_IDLE 5
10.  
    #define SCHED_DEADLINE 6

完全公平调度算法（时间片轮询调度算法）

实现完全公平调度算法，要为进程定义两个时间：

1. 实际运行时间  实际运行时间=调度周期进程权重/所有进程权重之和。 调度周期：指所有进程运行一遍所需要的时间。 进程权重：根据进程的重要性，分配给每个进程不同的权重。

2. 2.虚拟运行时间 虚拟运行时间=实际运行时间1024/进程权重=（调度周期进程权重/所有进程权重之和） 1024/进程权重=调度周期*1024/所有进程总权重。 一个调度周期里，所有进程的虚拟运行时间相同。

• 基本原理 CFS定义一种新调度模型，它给cfs_rq（cfs的run queue）中的每一个进程都设置一个虚 拟时钟-virtual runtime(vruntime)。如果一个进程得以执行，随着执行时间的不断增长，其 vruntime也将不断增大，没有得到执行的进程vruntime将保持不变。

调度器结构分析

任务：合理分配CPU时间给运行进程。

目标：有效分配CPU是时间片。

主调度器：通过schedule()函数来完成进程的选择和切换。 周期调度器：根据频率自动调用scheduler_tick函数，作用：根据进程运行时间触发调度。 上下文切换：主要做两件事：切换地址空间；切换寄存器和栈空间。

CFS就绪队列

调度管理是各个调度器的职责。CFS的顶级调度就队列struct cfs_rq。

1.  
   /* CFS-related fields in a runqueue */
2.  
   // CFS调度运行队列，每个CPU的rq都会包含一个cfs_rq,每个组调度的sched_entity也会有一个cfs_rq队列
3.  
   struct cfs_rq {
4.  
   // CFS运行队列中所有进程总负载
5.  
   struct load_weight load;
6.  
   // nr_running::cfs_rq中调度实体数量
7.  
   // h_nr_running 只对进程有效
8.  
   unsigned int nr_running, h_nr_running;
9.  
    
10.  
    u64 exec_clock;
11.  
    //跟踪记录队列所有进程最小虚拟运行时间
12.  
    u64 min_vruntime;
13.  
    #ifndef CONFIG_64BIT
14.  
    u64 min_vruntime_copy;
15.  
    #endif
16.  
    // 红黑树的root 用于在按时间排序的红黑树中管理所有进程
17.  
    struct rb_root tasks_timeline;
18.  
    // 下一个调度结点（红黑树最左边结点就是下个调度实体）
19.  
    struct rb_node *rb_leftmost;
20.  
     
21.  
    /*
22.  
    * 'curr' points to currently running entity on this cfs_rq.
23.  
    * It is set to NULL otherwise (i.e when none are currently running).
24.  
    */
25.  
    struct sched_entity *curr, *next, *last, *skip;
26.  
     
27.  
    #ifdef CONFIG_SCHED_DEBUG
28.  
    unsigned int nr_spread_over;
29.  
    #endif
30.  
     
31.  
    #ifdef CONFIG_SMP
32.  
    /*
33.  
    * CFS load tracking
34.  
    */
35.  
    struct sched_avg avg;
36.  
    u64 runnable_load_sum;
37.  
    unsigned long runnable_load_avg;
38.  
    #ifdef CONFIG_FAIR_GROUP_SCHED
39.  
    unsigned long tg_load_avg_contrib;
40.  
    #endif
41.  
    atomic_long_t removed_load_avg, removed_util_avg;
42.  
    #ifndef CONFIG_64BIT
43.  
    u64 load_last_update_time_copy;
44.  
    #endif
45.  
     
46.  
    #ifdef CONFIG_FAIR_GROUP_SCHED
47.  
    /*
48.  
    * h_load = weight * f(tg)
49.  
    *
50.  
    * Where f(tg) is the recursive weight fraction assigned to
51.  
    * this group.
52.  
    */
53.  
    unsigned long h_load;
54.  
    u64 last_h_load_update;
55.  
    struct sched_entity *h_load_next;
56.  
    #endif /* CONFIG_FAIR_GROUP_SCHED */
57.  
    #endif /* CONFIG_SMP */
58.  
     
59.  
    #ifdef CONFIG_FAIR_GROUP_SCHED
60.  
    struct rq *rq; /* cpu runqueue to which this cfs_rq is attached */
61.  
     
62.  
    /*
63.  
    * leaf cfs_rqs are those that hold tasks (lowest schedulable entity in
64.  
    * a hierarchy). Non-leaf lrqs hold other higher schedulable entities
65.  
    * (like users, containers etc.)
66.  
    *
67.  
    * leaf_cfs_rq_list ties together list of leaf cfs_rq's in a cpu. This
68.  
    * list is used during load balance.
69.  
    */
70.  
    int on_list;
71.  
    struct list_head leaf_cfs_rq_list;
72.  
    struct task_group *tg; /* group that "owns" this runqueue */
73.  
     
74.  
    #ifdef CONFIG_CFS_BANDWIDTH
75.  
    int runtime_enabled;
76.  
    u64 runtime_expires;
77.  
    s64 runtime_remaining;
78.  
     
79.  
    u64 throttled_clock, throttled_clock_task;
80.  
    u64 throttled_clock_task_time;
81.  
    int throttled, throttle_count;
82.  
    struct list_head throttled_list;
83.  
    #endif /* CONFIG_CFS_BANDWIDTH */
84.  
    #endif /* CONFIG_FAIR_GROUP_SCHED */
85.  
    };

总结

本文主要介绍了调度器分析：功能，调度类sched_class结构体与调度类；Linux调度类（5种）及其优先级，调度策略（5种）；完全公平调度算法，包括实际运行时间、虚拟运行时间，调度器结构分析，CFS就绪队列等内容。

Linux内核学习大纲：Linux内核学习思维导图

视频学习链接：Linux内核源码/内存调优/文件系统/进程管理/设备驱动/网络协议栈

这篇好文章是转载于：学新通技术网