《Linux内核源码分析》(3)调度器及CFS调度器

《Linux内核源码分析》(3)调度器及CFS调度器

一、调度器

1、调度器

• Linux内核中用来安排调度进程（一段程序的执行过程）执行的模块称为调度器(Scheduler),它可以切换进程状态(Process status)。比如：执行、可中断睡眠、不可中断睡眠、退出、暂停等。

• 调度器相当于CPU中央处理器的管理员，主要负责完成做两件事情:
  • 选择某些就绪进程来执行
  • 打断某些执行的进程让它们变为就绪状态

2、调度类sched_class结构体

• 调度器类提供了通用调度器和各个调度方法之间的关联，Linux内核抽象一个调度类struct sched_class结构体表示调度类，具体内核源码如下：
  kernel/sched/<sched.h>

  struct sched_class {/*系统当中有多个调度类，按照调度优先级排成一个链表,下一优先级的高类*/const struct sched_class *next;#ifdef CONFIG_UCLAMP_TASKint uclamp_enabled;
  #endif/*将进程加入到执行队列当中,即将调度实体(进程)存放到红黑树中,并对nr_running变量自动会加1。（nr_running指定了队列上可运行进程的数目，不考虑其优先级或调度类）*/void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);/*从执行队列当中删除进程，并对nr_running变量自动减1 */void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);/*放弃CPU执行权，实际上该函数执行先出队后入队，在这种情况下，它直接将调度实体放在红黑树的最右端*/void (*yield_task)   (struct rq *rq);bool (*yield_to_task)(struct rq *rq, struct task_struct *p, bool preempt);/*用于检杳当前进程是否可被新进程抢占*/void (*check_preempt_curr)(struct rq *rq, struct task_struct *p, int flags);/*选择下一个应用要运行的进程*/struct task_struct *(*pick_next_task)(struct rq *rq);/*将进程放回到运行队列当中*/void (*put_prev_task)(struct rq *rq, struct task_struct *p);void (*set_next_task)(struct rq *rq, struct task_struct *p, bool first);#ifdef CONFIG_SMPint (*balance)(struct rq *rq, struct task_struct *prev, struct rq_flags *rf);/*为进程选择一个合适的CPU */int  (*select_task_rq)(struct task_struct *p, int task_cpu, int sd_flag, int flags);/*迁移任务到处一个CPU */void (*migrate_task_rq)(struct task_struct *p, int new_cpu);/*专门用于唤醍进程*/void (*task_woken)(struct rq *this_rq, struct task_struct *task);/*修改进程在CPU的亲和力*/void (*set_cpus_allowed)(struct task_struct *p,const struct cpumask *newmask);/*启动运行队列*/void (*rq_online)(struct rq *rq);/*禁止运行队列*/void (*rq_offline)(struct rq *rq);
  #endif/*调用自time tick函数，它可能引起进程切换，将驱动运行时(running)抢占*/void (*task_tick)(struct rq *rq, struct task_struct *p, int queued);/* 进程创建时调用，不同调度策略的进程初始化也是不一样的 */void (*task_fork)(struct task_struct *p);/*进程退出时会使用*/void (*task_dead)(struct task_struct *p);/** The switched_from() call is allowed to drop rq->lock, therefore we* cannot assume the switched_from/switched_to pair is serliazed by* rq->lock. They are however serialized by p->pi_lock.*//*专门用于进程切换操作*/void (*switched_from)(struct rq *this_rq, struct task_struct *task);void (*switched_to)  (struct rq *this_rq, struct task_struct *task);/*更改进程的优先级*/void (*prio_changed) (struct rq *this_rq, struct task_struct *task,int oldprio);unsigned int (*get_rr_interval)(struct rq *rq,struct task_struct *task);void (*update_curr)(struct rq *rq);#define TASK_SET_GROUP		0
  #define TASK_MOVE_GROUP		1#ifdef CONFIG_FAIR_GROUP_SCHEDvoid (*task_change_group)(struct task_struct *p, int type);
  #endif
  };
  

• 调度器类可分为：stop_sched_class、dl_sched_class、rt_sched_class、fair_sched_class和idle_sched_class
  kernel/sched/<sched.h>

  extern const struct sched_class stop_sched_class;//停机调度类
  extern const struct sched_class dl_sched_class;//限期调度类
  extern const struct sched_class rt_sched_class;//实时调度类
  extern const struct sched_class fair_sched_class;//公平调度类
  extern const struct sched_class idle_sched_class;//空闲调度类
  

  这5种调度类的优先级从高到低依次为：停机调度类、限期调度类、实时调度类、公平调度类、空闲调度类。其中，SCHED_NORMAL、SCHED_BATCH和SCHED_IDLE直接被映射到fair_sched_class；SCHED_FIFO和SCHED_RR与rt_sched_class向关联。Linux调度核心选择下一个合适的task运行时，会按照优先级顺序遍历调度类的pick_next_task函数

  • 停机调度类：优先级是最高的调度类，停机进程是优先级最高的进程，可以抢占所有其它进程，其他进程不可能抢占停机进程.

    const struct sched_class stop_sched_class = {.next			= &dl_sched_class,.enqueue_task		= enqueue_task_stop,.dequeue_task		= dequeue_task_stop,.yield_task		= yield_task_stop,.check_preempt_curr	= check_preempt_curr_stop,.pick_next_task		= pick_next_task_stop,.put_prev_task		= put_prev_task_stop,.set_next_task          = set_next_task_stop,...
    };
    

  • 限期调度类：最早使用优先算法，使用红黑树把进程按照绝对截止期限从小到大排序，每次调度时选择绝对截止期限最小的进程。

    const struct sched_class dl_sched_class = {.next			= &rt_sched_class,.enqueue_task		= enqueue_task_dl,.dequeue_task		= dequeue_task_dl,.yield_task		= yield_task_dl,.check_preempt_curr	= check_preempt_curr_dl,.pick_next_task		= pick_next_task_dl,.put_prev_task		= put_prev_task_dl,.set_next_task		= set_next_task_dl,...
    };
    

  • 实时调度类：为每个调度优先级维护一个队列。

    const struct sched_class rt_sched_class = {.next			= &fair_sched_class,.enqueue_task		= enqueue_task_rt,.dequeue_task		= dequeue_task_rt,.yield_task		= yield_task_rt,.check_preempt_curr	= check_preempt_curr_rt,.pick_next_task		= pick_next_task_rt,.put_prev_task		= put_prev_task_rt,.set_next_task          = set_next_task_rt,...
    };
    

  • 公平调度类：使用完全公平调度算法。完全公平调度算法引入虚拟运行时间的相关概念：虚拟运行时间 = 实际运行时间 * nice为0对应的权重 / 进程的权重。

    const struct sched_class fair_sched_class = {.next			= &idle_sched_class,.enqueue_task		= enqueue_task_fair,.dequeue_task		= dequeue_task_fair,.yield_task		= yield_task_fair,.yield_to_task		= yield_to_task_fair,.check_preempt_curr	= check_preempt_wakeup,.pick_next_task		= __pick_next_task_fair,.put_prev_task		= put_prev_task_fair,.set_next_task          = set_next_task_fair,...
    };
    

  • 空闲调度类：每个CPU上有一个空闲线程，即0号线程。空闲调度类优先级最低，仅当没有其他进程可以调度的时候，才会调度空闲线程。

    const struct sched_class idle_sched_class = {/* .next is NULL *//* no enqueue/yield_task for idle tasks *//* dequeue is not valid, we print a debug message there: */.dequeue_task		= dequeue_task_idle,.check_preempt_curr	= check_preempt_curr_idle,.pick_next_task		= pick_next_task_idle,.put_prev_task		= put_prev_task_idle,.set_next_task          = set_next_task_idle,...
    };
    

• 观察上述5个调度类的next成员变量，可以发现他们是串联在一起的。Linux调度核心选择下一个合适的task运行时，会按照优先级顺序遍历调度类的pick_next_task函数。

3、优先级

• 在用户空间可以通过nice命令设置进程的静态优先级，这在内部会调用nice系统调用。进程的nice值为[-20,+19]。值越低，表明优先级越高。内核使用范围[0,139]来表示内部优先级。同样是值越低，优先级越高。实时进程范围为[0,99]。nice值[-20, +19]映射到范围100到139。如下图所示，实时进程的优先级总是比普通进程更高。
  
• Linux内核优先级源码如下：
  include/linux/sched/<prio.h>

  #define MAX_NICE	19
  #define MIN_NICE	-20/*nice值的范围*/
  #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) // 140#define DEFAULT_PRIO		(MAX_RT_PRIO + NICE_WIDTH / 2)
  

4、内核调度策略

• struct task_struct中有成员变量unsigned int policy，指代保存进程的调度策略。
• Linux内核提供一些调度策略供用户应用程序来选择调度器。Linux内核调度策略源码分析如下：
  include/uapi/linux/<sched.h>

  /** Scheduling policies*//*用于普通进程，通过CFS调度器实现。*/
  #define SCHED_NORMAL		0/* 先进先出调度算法（实时调度策略），相同优先级任务先到先服务，高优先级的任务可以抢占低优先级的任务 */
  #define SCHED_FIFO		1/*轮流调度算法（实时调度策略）*/
  #define SCHED_RR		2/*用于非交互处理器消耗型进程，相当于SCHED_NORMAL分化版本，采用分时策略，根据动态优先级，分配CPU运行需要资源*/
  #define SCHED_BATCH		3/* SCHED_ISO: reserved but not implemented yet *//*普通迸程调度策略，使task以最低优先级选择CFS调度器来调度运行*/
  #define SCHED_IDLE		5/*限期进程调度策略，使task选择Deadline调度器来调度运行*/
  #define SCHED_DEADLINE		6
  

  • 备注：其中stop调度器和DLE-task调度器，仅使用于内核，用户没有办法进行选择。

二、CFS调度器

1、CFS调度器基本原理

• 完全公平调度算法体现在对待每个进程都是公平的，让每个进程都运行—段相同的时间片，这就是基于时间片轮询调度算法。CFS定义一种新调度模型，它给cfs_rq (cfs的run queue)中的每一个进程都设置一个虚拟时钟:vruntime(virtual runtime)。如果一个进程得以执行，随着执行时间的不断增长，其vruntime也将不断增大，没有得到执行的进程vruntime 将保持不变。
• 下图说明了调度器如何记录哪个进程已经等待了多长时间。由于可运行进程是排队的，该结构称之为就绪队列
  
  所有的可运行进程都按时间在一个红黑树中排序，所谓时间即其等待时间。等待CPU时间最长的进程是最左侧的项，调度器下一次会考虑该进程。等待时间稍短的进程在该树上从左至右排序。在一个调度周期里面，所有进程的虚拟运行时间是相同的，所以在进程调度时，只需要找到虚拟运行时间最小的进程调度运行即可。
• 实现完全公平调度算法，要为进程定义两个时间

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

    eg：调度周期为60ms，进程A的权重为1，而且进程B的权重为2,那么：
    进程A实际运行时间为：60ms * 1/（1 +2）=20ms
    进程B实际运行时间为：60ms * 2/（1 +2）=40ms

  • 虚拟运行时间
    虚拟运行时间 = 实际运行时间 * nice为0对应的权重（1024） / 进程的权重 =（调度周期 * 进程权重 / 所有进程权重之和 * 1024 / 进程权重 = 调度周期 * 1024 / 所有进程总权重。

2、调度子系统各个组件模块

• 调度器通过各个组件模块及一系列数据结构，来排序和管理系统中的进程。它们之间关系如下：
  
  • 主调度器：通过调用schedule()函数来完成进程的选择和切换。
  • 周期性调度器：根据固定频率自动调用scheduler_tick函数，不时检测是否有必要进行进程切换。
  • 上下文切换：主要做两个事情（切换地址空间、切换寄存器和栈空间）

3、CFS调度器就绪队列内核源码

struct cfs_rq {/*CFS运行队列中所有进程总负我*/struct load_weight	load;unsigned long		runnable_weight;/*cfs_rq中调度实体数量*/unsigned int		nr_running;unsigned int		h_nr_running;      /* SCHED_{NORMAL,BATCH,IDLE} */unsigned int		idle_h_nr_running; /* SCHED_IDLE */u64			exec_clock;u64			min_vruntime;
#ifndef CONFIG_64BITu64			min_vruntime_copy;
#endif/*红黑树的root*/struct rb_root_cached	tasks_timeline;/*下一个调度结点(红黑树最左边结点就是下个调度实体）*/struct rb node *rb leftmost;...