logo
搜索
我的图书馆

发文章

发文工具

其他工具

留言交流
搜索
分享

【原】Linux内核CFS调度器：实现高效多任务处理

 深度Linux 2023-11-16 发布于湖南

FS调度器（Completely Fair Scheduler）是Linux操作系统中的一种进程调度器，用于管理和分配CPU时间给各个运行的进程。它采用红黑树数据结构来维护进程的就绪队列，并使用虚拟时钟来进行公平的时间片分配。CFS调度器通过动态地计算每个进程的虚拟运行时间，以及维护一个近似最小优先级队列，从而保证了公平性和高效性。

CFS调度器在多核处理器环境下有效地利用了CPU资源，根据每个进程所需的权重来分配时间片，并提供良好的响应性能。它还支持实时任务，并可以自动调节调度策略以适应系统负载变化。

CFS简介

CFS，即Completely Fair Scheduler，由资深内核开发者IngoMolnar开发，在2.6.23版本的内核中并入主线，并沿用至今。按照内核文档介绍（参考linux-4.18 Documentation/scheduler/sched-design-CFS.txt），CFS的设计理念用一句话概括：在真实的硬件上实现理想的、精准、完全公平的多任务调度。

CFS调度器的目标是保证每一个进程的完全公平调度。 CFS调度器和以往的调度器不同之处在于没有时间片的概念，而是分配cpu使用时间的比例。理想状态下每个进程都能获得相同的时间片，并且同时运行在CPU上，但实际上一个CPU同一时刻运行的进程只能有一个。 也就是说，当一个进程占用CPU时，其他进程就必须等待。CFS为了实现公平，必须惩罚当前正在运行的进程，以使那些正在等待的进程下次被调度。CFS调度引入虚拟时间代替实际时间，每次在就绪队列中选择虚拟时间最小的task，实现公平。

任务调度器发展

什么是调度器（scheduler）？调度器的作用是什么？调度器是一个操作系统的核心部分，可以比作是CPU时间的管理员。调度器主要负责选择某些就绪的任务来执行。不同的调度器根据不同的方法挑选出最适合运行的任务。那么依据什么挑选最适合运行的任务呢？这就是每一个调度器需要关注的问题。

不同的任务有不同的需求，因此我们需要对任务进行分类：一种是普通进程，另外一种是实时进程，对于实时进程，Linux内核的主要考虑因素是优先级，调度器总是选择优先级最高的那个进程执行。普通进程又分为交互式进程（IO密集型的，等待IO）和批处理进程（CPU密集型的，守护进程等），交互式进程需要和用户进行交互，因此对调度延迟比较敏感，而批处理进程属于那种在后台默默干活的，因此它更注重吞吐，对调度延迟要求不高。普通进程如何细分时间片则是调度器的核心思考点。过大的时间片会严重损伤系统的响应延迟，让用户明显能够感知到延迟，卡顿，从而影响用户体验。较小的时间片虽然有助于减少调度延迟，但是频繁的切换对系统的吞吐会造成严重的影响。

任务？进程？进程是资源管理的单位，线程才是调度的单位，但线程调度器这个说法很少见，所以我们可以说任务调度器。

Linux内核中使用一个非常大的结构体来同时表达进程和线程，即task_struct。但是调度类管理和调度的单位是调度实体，即sched_entity，并不是task_struct。我们这里只看下task_struct中与调度相关的字段：

struct task_struct {
      /*
      进程执行时，它会根据具体情况改变状态,Linux 中的进程主要有如下状态
      TASK_RUNNING  可运行
      TASK_INTERRUPTIBLE  可中断的等待状态
      TASK_UNINTERRUPTIBLE 不可中断的等待状态
      TASK_ZOMBIE 僵死
      TASK_STOPPED  暂停
    */ 
    volatile long state;    /* -1 unrunnable, 0 runnable, >0 stopped */
  	int                             prio;							/*动态优先级，根据静态优先级及其他条件计算而来*/
    int                             static_prio;			/*普通进程静态优先级，取值范围是100（优先级最高）～139（优先级最低），分别对应nice value的-20 ～ 19。*/
    int                             normal_prio;			/*调度器综合考虑各种因素，例如调度策略，nice value、scheduling priority等，把这些factor全部考虑进来，归一化成一个数轴上的number，以此来表示其优先级，这就是normalized priority。对于一个线程，其normalized priority的number越小，其优先级越大。*/
    unsigned int                    rt_priority;       /*实时进程优先级*/
    
		unsigned int                    policy;       /*调度策略*/
    const struct sched_class        *sched_class;  /*调度类*/
    struct sched_entity             se;						/*普通进程调度实体*/
    struct sched_rt_entity          rt;						/*实时进程调度实体*/
    struct sched_dl_entity          dl;						
};

不同的任务有不同的需求，因此一个系统中会共存多个调度器，目前Linux支持的调度器有RT scheduler、Deadline scheduler、CFS scheduler及Idle scheduler等。

针对以上调度类，系统中有明确的优先级概念。每一个调度类利用next成员构建单项链表。优先级从高到低示意图如下：

sched_class_highest----->stop_sched_class
.next---------->dl_sched_class
.next---------->rt_sched_class
.next--------->fair_sched_class
.next----------->idle_sched_class
.next = NULL

Linux的任务调度器是不断演进的，先后出现过三种里程碑式的调度器：

  • O(n)调度器 内核版本 2.4-2.6

  • O(1) 调度器 内核版本 2.6.0-2.6.22

  • CFS调度器 内核版本 2.6.23-至今

O(n) 调度器

O(n)调度器采用一个全局队列runqueue作为核心数据结构，存在的问题非常多：

  • 对runqueue队列的遍历的复杂度是O(n)；

  • 多个cpu共享全局队列，随着CPU数目增多，加锁开销成为性能瓶颈；

  • 实时进程和普通进程混合且无序存放

  • CPU空转问题：当runqueue链表中的所有进程耗尽时间片，才会启动新一轮对系统中所有进程时间片重新计算的过程，只要有一个CPU上还在运行着进程，其他CPU都是idle，造成CPU资源的浪费

  • task bouncing issue：一般而言，一个进程最好是一直保持在同一个CPU上运行。随着runqueue中的进程一个个的耗尽其时间片，cpu可选择的余地在不断的压缩，从而导致进程可能在一个和它亲和性不大的处理器上执行。

O(1)调度器

O（n）调度器中只有一个全局的runqueue，严重影响了扩展性，因此O（1）调度器中引入了per-CPU runqueue的概念。系统中所有的可运行状态的进程首先经过负载均衡模块挂入各个CPU的runqueue，然后由各自的调度器驱动CPU上的调度行为。

由于引入了per-CPU runqueue，O（1）调度器删除了全局runqueue的spin lock，同时把spin lock放入到per-CPU runqueue数据结构中，通过把一个大锁细分成小锁，可以大大降低调度延迟，提升系统响应时间。这种方法在内核中经常使用，是一个比较通用的性能优化方法。

在Linux 2.5版本的开发过程中，Ingo Molnar设计的O（1）调度器替换掉了原始的、简陋的O（n）调度器，从而解决了扩展性很差，性能不佳的问题。然而O（1）并非完美，在实际的使用过程中，还是有不少的桌面用户在抱怨交互性比较差。

在O（n）和O（1）调度器中，时间片是固定分配的，静态优先级高的进程获取更大的time slice。例如nice value等于20的进程获取的default timeslice是5ms，而nice value等于0的进程获取的是100ms。直观上，这样的策略没有毛病（高优先级的获取更多的执行时间），但是，这样的设定潜台词就是：高优先级的进程会获得更多的连续执行的机会，这是CPU-bound进程期望的，但是实际上，CPU-bound进程往往在后台执行，其优先级都是比较低的。

因此，假设我们调度策略就是根据进程静态优先级确定一个固定大小的时间片，这时候我们在如何分配时间片上会遇到两难的状况：想要给用户交互型进程设定高优先级，以便它能有更好的用户体验，但是分配一个大的时间片是毫无意义的，因为这种进程多半是处于阻塞态，等待用户的输入。而后台进程的优先级一般不高，但是根据其优先级分配一个较小的时间片往往会影响其性能，这种类型的进程最好是趁着cache hot的时候狂奔。

怎么办？或者传统调度器固定分配时间片这个设计概念就是错误的。

在反反复复修复用户卡顿issue的过程中，很多天才工程师试图通过修改用户交互指数算法来解决问题，试图去猜测进程对交互性的需求，这其实非常困难，就像收集了一个人性格特点，业余爱好，做事风格，逻辑思维水平，星座猜。。。也很难猜测一个人的心中所想。

在进程调度这件事情上为何不能根据实实在在确定的东西来调度呢？一个进程的静态优先级已经完说明了其调度需求了，这就足够了，不需要猜测进程对交互性的需求，只要维持公平就OK了，而所谓的公平就是进程获取和其静态优先级匹配的CPU执行时间。在这样的思想指导下，Con Kolivas提出了RSDL（Rotating Staircase Deadline）调度器。

【文章福利】小编推荐自己的Linux内核技术交流群:【865977150】整理了一些个人觉得比较好的学习书籍、视频资料共享在群文件里面，有需要的可以自行添加哦！！！

RSDL调度器

RSDL（Rotating Staircase Deadline)）调度器仍然沿用了O（1）调度的数据结构和软件结构，当然删除了那些令人毛骨悚然的评估进程交互指数的代码。限于篇幅，这一小节只简单了解下RSDL算法，了解Rotating、Staircase和Deadline这三个基本概念。

首先看Staircase概念，它更详细表述应该是priority staircase，即在进程调度过程中，其优先级会象下楼梯那样一点点的降低。在传统的调度概念中，一个进程有一个和其静态优先级相匹配的时间片，在RSDL中，同样也存在这样的时间片，但是时间片是散布在很多优先级中。例如如果一个进程的优先级是120，那么整个时间片散布在120～139的优先级中，在一个调度周期，进程开始是挂入120的优先级队列，并在其上运行6ms（这是一个可调参数，我们假设每个优先级的时间配额是6ms），一旦在120级别的时间配额使用完毕之后，该进程会转入121的队列中（优先级降低一个level），发生一次Rotating，更准确的说是Priority minor rotating。之后，该进程沿阶而下，直到139的优先级，在这个优先级上如果耗尽了6ms的时间片，这时候，该进程所有的时间片就都耗尽了，就会被挂入到expired队列中去等待下一个调度周期。这次rotating被称为major rotating。当然，这时候该进程会挂入其静态优先级对应的expired队列，即一切又回到了调度的起点。

Deadline是指在RSDL算法中，任何一个进程可以准确的预估其调度延迟。一个简单的例子，假设runqueue中有两个task，静态优先级分别是130的A进程和139的B进程。对于A进程，只有在进程沿着优先级楼梯从130走到139的时候，B进程才有机会执行，其调度延迟是9 x 6ms ＝ 54ms。

多么简洁的算法，只需要维持公平，没有对进程睡眠/运行时间的统计，没有对用户交互指数的计算，没有那些奇奇怪怪的常数……调度，就是这么简单。

调度类

从Linux 2.6.23开始，Linux引入scheduling class的概念，目的是将调度器模块化。这样提高了扩展性，添加一个新的调度器也变得简单起来。一个系统中还可以共存多个调度器。在Linux中，将调度器公共的部分抽象，使用struct sched_class结构体描述一个具体的调度类。系统核心调度代码会通过struct sched_class结构体的成员调用具体调度类的核心算法。先简单的介绍下struct sched_class部分成员作用。

调度类 描述 调度策略
dl_sched_class deadline调度器 SCHED_DEADLINE
rt_sched_class 实时调度器 SCHED_FIFO、SCHED_RR
fair_sched_class 完全公平调度器 SCHED_NORMAL、SCHED_BATCH
idle_sched_class idle task SCHED_IDLE
struct sched_class {
 const struct sched_class *next;//指向下一个调度类，按照优先级
 void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);//向该调度类的runqueue(就绪队列)中添加进程
 void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);//向该调度类的runqueue(就绪队列)中删除进程
  void (*check_preempt_curr)(struct rq *rq, struct task_struct *p, int flags);//当一个进程被唤醒或者创建的时候，需要检查当前进程是否可以抢占当前cpu上正在运行的进程，如果可以抢占需要标记TIF_NEED_RESCHED flag。

      //从runqueue中选择一个最适合运行的task
 struct task_struct * (*pick_next_task)(struct rq *rq,
                                       struct task_struct *prev,
                                        struct rq_flags *rf);

普通进程的优先级及虚拟时间

CFS调度器针对优先级又提出了nice值的概念，其实和权重是一一对应的关系。nice值就是一个具体的数字，取值范围是[-20, 19]。数值越小代表优先级越大，同时也意味着权重值越大，nice值和权重之间可以互相转换。内核提供了一个表格转换nice值和权重。

const int sched_prio_to_weight[40] = {
7527 /* -20 */     88761,     71755,     56483,     46273,     36291,
7528 /* -15 */     29154,     23254,     18705,     14949,     11916,
7529 /* -10 */      9548,      7620,      6100,      4904,      3906,
7530 /*  -5 */      3121,      2501,      1991,      1586,      1277,
7531 /*   0 */      1024,       820,       655,       526,       423,
7532 /*   5 */       335,       272,       215,       172,       137,
7533 /*  10 */       110,        87,        70,        56,        45,
7534 /*  15 */        36,        29,        23,        18,        15,
7535};

虚拟运行时间是通过进程的实际运行时间和进程的权重（weight）计算出来的。在CFS调度器中，将进程优先级这个概念弱化，而是强调进程的权重。一个进程的权重越大，则说明这个进程更需要运行，因此它的虚拟运行时间就越小，这样被调度的机会就越大

虚拟运行时间的计算公式：

vriture_runtime = wall_time * 1024/weight
virtue_runtime — 虚拟运行时间
wall_time - 实际运行时间

由公式可以看出nice为0的virtue_time与time一致，且weight越大，相同的实际运行时间下，虚拟时间越小，越会被调度。下图给实际运行时间，虚拟运行时间，nice值之间的关系：

系统中使用struct load_weight结构体描述进程的权重信息。weight代表进程的权重，inv_weight等于2^ 32/weight。

struct load_weight {
    unsigned long       weight;
    u32         inv_weight;
};

Linux中有哪些调度类

Linux中主要包含dl_sched_class、rt_sched_class、fair_sched_class及idle_sched_class等调度类。每一个进程都对应一种调度策略，每一种调度策略又对应一种调度类（每一个调度类可以对应多种调度策略）。例如实时调度器以优先级为导向选择优先级最高的进程运行。每一个进程在创建之后，总是要选择一种调度策略。针对不同的调度策略，选择的调度器也是不一样的。不同的调度策略对应的调度类如下表：

针对以上调度类，系统中有明确的优先级概念。每一个调度类利用next成员构建单项链表。优先级从高到低示意图如下：

sched_class_highest----->stop_sched_class
                         .next---------->dl_sched_class
                                         .next---------->rt_sched_class
                                                         .next--------->fair_sched_class
                                                                        .next----------->idle_sched_class
                                                                                         .next = NULL

Linux调度核心在选择下一个合适的task运行的时候，会按照优先级的顺序便利调度类的pick_next_task函数。因此，SCHED_FIFO调度策略的实时进程永远比SCHED_NORMAL调度策略的普通进程优先运行。代码中pick_next_task函数也有体现。pick_next_task函数就是负责选择一个即将运行的进程，以下贴出省略版代码。

static inline struct task_struct *pick_next_task(struct rq *rq,
                                                 struct task_struct *prev, struct rq_flags *rf)
{
	const struct sched_class *class;
	struct task_struct *p;
 
	for_each_class(class) {          /* 按照优先级顺序便利所有的调度类，通过next指针便利单链表 */
		p = class->pick_next_task(rq, prev, rf);
		if (p)
			return p;
	}
}

针对CFS调度器，管理的进程都属于SCHED_NORMAL或者SCHED_BATCH策略。

普通进程的优先级

CFS是Completely Fair Scheduler简称，即完全公平调度器。CFS的设计理念是在真实硬件上实现理想的、精确的多任务CPU。CFS调度器和以往的调度器不同之处在于没有时间片的概念，而是分配cpu使用时间的比例。例如：2个相同优先级的进程在一个cpu上运行，那么每个进程都将会分配50%的cpu运行时间。这就是要实现的公平。

以上举例是基于同等优先级的情况下。但是现实却并非如此，有些任务优先级就是比较高。那么CFS调度器的优先级是如何实现的呢？首先，我们引入权重的概念，权重代表着进程的优先级。各个进程之间按照权重的比例分配cpu时间。例如：2个进程A和B。A的权重是1024，B的权重是2048。那么A获得cpu的时间比例是1024/(1024+2048) = 33.3%。B进程获得的cpu时间比例是2048/(1024+2048)=66.7%。我们可以看出，权重越大分配的时间比例越大，相当于优先级越高。在引入权重之后，分配给进程的时间计算公式如下：

分配给进程的时间 = 总的cpu时间 * 进程的权重/就绪队列（runqueue）所有进程权重之和

CFS调度器针对优先级又提出了nice值的概念，其实和权重是一一对应的关系。nice值就是一个具体的数字，取值范围是[-20, 19]。数值越小代表优先级越大，同时也意味着权重值越大，nice值和权重之间可以互相转换。内核提供了一个表格转换nice值和权重。

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

数组的值可以看作是公式：weight = 1024 / 1.25^nice计算得到。公式中的1.25取值依据是：进程每降低一个nice值，将多获得10% cpu的时间。公式中以1024权重为基准值计算得来，1024权重对应nice值为0，其权重被称为NICE_0_LOAD。默认情况下，大部分进程的权重基本都是NICE_0_LOAD。

调度延迟

什么是调度延迟？调度延迟就是保证每一个可运行进程都至少运行一次的时间间隔。例如，每个进程都运行10ms，系统中总共有2个进程，那么调度延迟就是20ms。如果有5个进程，那么调度延迟就是50ms。如果现在保证调度延迟不变，固定是6ms，那么系统中如果有2个进程，那么每个进程运行3ms。如果有6个进程，那么每个进程运行1ms。如果有100个进程，那么每个进程分配到的时间就是0.06ms。随着进程的增加，每个进程分配的时间在减少，进程调度过于频繁，上下文切换时间开销就会变大。因此，CFS调度器的调度延迟时间的设定并不是固定的。当系统处于就绪态的进程少于一个定值（默认值8）的时候，调度延迟也是固定一个值不变（默认值6ms）。当系统就绪态进程个数超过这个值时，我们保证每个进程至少运行一定的时间才让出cpu。这个“至少一定的时间”被称为最小粒度时间。在CFS默认设置中，最小粒度时间是0.75ms。用变量sysctl_sched_min_granularity记录。因此，调度周期是一个动态变化的值。调度周期计算函数是__sched_period()。

static u64 __sched_period(unsigned long nr_running)
{
	if (unlikely(nr_running > sched_nr_latency))
		return nr_running * sysctl_sched_min_granularity;
	else
		return sysctl_sched_latency;
}
nr_running是系统中就绪进程数量，当超过sched_nr_latency时，我们无法保证调度延迟，因此转为保证调度最小粒度。如果nr_running并没有超过sched_nr_latency，那么调度周期就等于调度延迟sysctl_sched_latency（6ms）。

虚拟时间（virtual time）

CFS调度器的目标是保证每一个进程的完全公平调度。CFS调度器就像是一个母亲，她有很多个孩子（进程）。但是，手上只有一个玩具（cpu）需要公平的分配给孩子玩。假设有2个孩子，那么一个玩具怎么才可以公平让2个孩子玩呢？简单点的思路就是第一个孩子玩10分钟，然后第二个孩子玩10分钟，以此循环下去。CFS调度器也是这样记录每一个进程的执行时间，保证每个进程获取CPU执行时间的公平。因此，哪个进程运行的时间最少，应该让哪个进程运行。

                                 NICE_0_LOAD
vriture_runtime = wall_time * ----------------
                                    weight

进程A的虚拟时间3.3 * 1024 / 1024 = 3.3ms，我们可以看出nice值为0的进程的虚拟时间和实际时间是相等的。进程B的虚拟时间是2.7 * 1024 / 820 = 3.3ms。我们可以看出尽管A和B进程的权重值不一样，但是计算得到的虚拟时间是一样的。因此CFS主要保证每一个进程获得执行的虚拟时间一致即可。在选择下一个即将运行的进程的时候，只需要找到虚拟时间最小的进程即可。为了避免浮点数运算，因此我们采用先放大再缩小的方法以保证计算精度。

内核又对公式做了如下转换：

                                 NICE_0_LOAD
vriture_runtime = wall_time * ----------------
                                    weight
  
                                   NICE_0_LOAD * 2^32
                = (wall_time * -------------------------) >> 32
                                        weight
                                                                                        2^32
                = (wall_time * NICE_0_LOAD * inv_weight) >> 32        (inv_weight = ------------ )
                                                                                        weight

权重的值已经计算保存到sched_prio_to_weight数组中，根据这个数组我们可以很容易计算inv_weight的值。内核中使用sched_prio_to_wmult数组保存inv_weight的值。计算公式是：sched_prio_to_wmult[i] = 232/sched_prio_to_weight[i]。

const u32 sched_prio_to_wmult[40] = {
 /* -20 */     48388,     59856,     76040,     92818,    118348,
 /* -15 */    147320,    184698,    229616,    287308,    360437,
 /* -10 */    449829,    563644,    704093,    875809,   1099582,
 /*  -5 */   1376151,   1717300,   2157191,   2708050,   3363326,
 /*   0 */   4194304,   5237765,   6557202,   8165337,  10153587,
 /*   5 */  12820798,  15790321,  19976592,  24970740,  31350126,
 /*  10 */  39045157,  49367440,  61356676,  76695844,  95443717,
 /*  15 */ 119304647, 148102320, 186737708, 238609294, 286331153,
};

系统中使用struct load_weight结构体描述进程的权重信息。weight代表进程的权重，inv_weight等于232/weight。

struct load_weight {
	unsigned long		weight;
	u32			inv_weight;
};

将实际时间转换成虚拟时间的实现函数是calc_delta_fair()。calc_delta_fair()调用__calc_delta()函数，__calc_delta()主要功能是实现如下公式的计算。

__calc_delta() = (delta_exec * weight * lw->inv_weight) >> 32
 
                                  weight                                 2^32
               = delta_exec * ----------------    (lw->inv_weight = --------------- )
                                lw->weight                             lw->weight

和上面计算虚拟时间计算公式对比发现。如果需要计算进程的虚拟时间，这里的weight只需要传递参数NICE_0_LOAD，lw参数是进程对应的struct load_weight结构体。

static u64 __calc_delta(u64 delta_exec, unsigned long weight, struct load_weight *lw)
{
	u64 fact = scale_load_down(weight);
	int shift = 32;
 
	__update_inv_weight(lw);
 
	if (unlikely(fact >> 32)) {
		while (fact >> 32) {
			fact >>= 1;
			shift--;
		}
	}
 
	fact = (u64)(u32)fact * lw->inv_weight;
 
	while (fact >> 32) {
		fact >>= 1;
		shift--;
	}
 
	return mul_u64_u32_shr(delta_exec, fact, shift);
}

按照上面说的理论，calc_delta_fair()函数调用__calc_delta()的时候传递的weight参数是NICE_0_LOAD，lw参数是进程对应的struct load_weight结构体。

static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
{
	if (unlikely(se->load.weight != NICE_0_LOAD))             /* 1 */
		delta = __calc_delta(delta, NICE_0_LOAD, &se->load);  /* 2 */
 
	return delta;
}

  1. 就不用计算。

  2. 调用__calc_delta()函数。

Linux通过struct task_struct结构体描述每一个进程。但是调度类管理和调度的单位是调度实体，并不是task_struct。在支持组调度的时候，一个组也会抽象成一个调度实体，它并不是一个task。所以，我们在struct task_struct结构体中可以找到以下不同调度类的调度实体。

struct task_struct {
         struct sched_entity		se;
	struct sched_rt_entity		rt;
	struct sched_dl_entity		dl;
    /* ... */
}
se、rt、dl分别对应CFS调度器、RT调度器、Deadline调度器的调度实体。

struct sched_entity结构体描述调度实体，包括struct load_weight用来记录权重信息。除此以外我们一直关心的时间信息，肯定也要一起记录。struct sched_entity结构体简化后如下：

struct sched_entity {
	struct load_weight		load;
	struct rb_node		run_node;
	unsigned int		on_rq;
	u64			sum_exec_runtime;
	u64			vruntime;
};

  1. load：权重信息，在计算虚拟时间的时候会用到inv_weight成员。

  2. run_node：CFS调度器的每个就绪队列维护了一颗红黑树，上面挂满了就绪等待执行的task，run_node就是挂载点。

  3. on_rq：调度实体se加入就绪队列后，on_rq置1。从就绪队列删除后，on_rq置0。

  4. sum_exec_runtime：调度实体已经运行实际时间总合。

  5. vruntime：调度实体已经运行的虚拟时间总合。

调度实体

Linux通过struct task_struct结构体描述每一个进程。但是调度类管理和调度的单位是调度实体，并不是task_struct。在支持组调度的时候，一个组也会抽象成一个调度实体，它并不是一个task。所以，我们在struct task_struct结构体中可以找到以下不同调度类的调度实体。

struct task_struct {
    struct sched_entity     se;
    struct sched_rt_entity      rt;
    struct sched_dl_entity      dl;
    /* ... */
} 
struct sched_entity {
    struct load_weight      load;//权重信息
    struct rb_node      run_node;//就绪队列红黑树上的挂载点
    unsigned int        on_rq;//调度实体se加入就绪队列后，on_rq标志置为1，从就绪队列删除,on_rq置为0
    u64         sum_exec_runtime;//调度实体已经运行的实际时间总和
    u64         vruntime;//调度实体已经运行的虚拟时间总和
};

就绪队列

系统中每个CPU都会有一个全局的就绪队列（cpu runqueue），使用struct rq结构体描述，它是per-cpu类型，即每个cpu上都会有一个struct rq结构体。每一个调度类也有属于自己管理的就绪队列。例如，struct cfs_rq是CFS调度类的就绪队列，管理就绪态的struct sched_entity调度实体，后续通过pick_next_task接口从就绪队列中选择最适合运行的调度实体（虚拟时间最小的调度实体）。struct rt_rq是实时调度器就绪队列。struct dl_rq是Deadline调度器就绪队列。

struct rq {
    struct cfs_rq cfs;
    struct rt_rq rt;
    struct dl_rq dl;
};
 
struct rb_root_cached {
    struct rb_root rb_root;//红黑树的根节点
    struct rb_node *rb_leftmost;//红黑树的最左边节点
};
 
struct cfs_rq {
    struct load_weight load;//就绪队列管理的所有调度实体权重之和
    unsigned int nr_running;//调度实体的个数
    u64 min_vruntime;//就绪队列上的最小虚拟时间
    struct rb_root_cached tasks_timeline;//就绪队列红黑树的信息
};

CFS调度器实现

Linux中所有的进程使用task_struct描述。task_struct包含很多进程相关的信息（例如，优先级、进程状态以及调度实体等）。但是，每一个调度类并不是直接管理task_struct，而是引入调度实体的概念。CFS调度器使用sched_entity跟踪调度信息。

CFS调度器使用cfs_rq跟踪就绪队列信息以及管理就绪态调度实体，并维护一棵按照虚拟时间排序的红黑树。tasks_timeline->rb_root是红黑树的根，tasks_timeline->rb_leftmost指向红黑树中最左边的调度实体，即虚拟时间最小的调度实体（为了更快的选择最适合运行的调度实体，因此rb_leftmost相当于一个缓存）。

每个就绪态的调度实体sched_entity包含插入红黑树中使用的节点rb_node，同时vruntime成员记录已经运行的虚拟时间。我们将这几个数据结构简单梳理，如下图所示：

源码分析

流程分析

整个流程分析，围绕着 CFS 调度类实体：fair_sched_class 中的关键函数来展开。

先来看看 fair_sched_class 都包含了哪些函数：

/* All the scheduling class methods: */
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,

    #ifdef CONFIG_SMP
    .select_task_rq  = select_task_rq_fair,
    .migrate_task_rq = migrate_task_rq_fair,

    .rq_online  = rq_online_fair,
    .rq_offline = rq_offline_fair,

    .task_dead  = task_dead_fair,
    .set_cpus_allowed = set_cpus_allowed_common,
    #endif

    .set_curr_task  = set_curr_task_fair,
    .task_tick      = task_tick_fair,
    .task_fork      = task_fork_fair,

    .prio_changed   = prio_changed_fair,
    .switched_from  = switched_from_fair,
    .switched_to    = switched_to_fair,

    .get_rr_interval = get_rr_interval_fair,

    .update_curr     = update_curr_fair,

    #ifdef CONFIG_FAIR_GROUP_SCHED
    .task_change_group = task_change_group_fair,
    #endif
};

(1)runtime 与 vruntime

CFS 调度器没有时间片的概念了，而是根据实际的运行时间和虚拟运行时间来对任务进行排序，从而选择调度。那么，运行时间和虚拟运行时间是怎么计算的呢？看一下流程调用：

Linux 内核默认的 sysctl_sched_latency 是 6ms，这个值用户态可设。sched_period 用于保证可运行任务都能至少运行一次的时间间隔；(2) 当可运行任务大于 8 个的时候，sched_period 的计算则需要根据任务个数乘以最小调度颗粒值，这个值系统默认为 0.75ms；(3) 每个任务的运行时间计算，是用 sched_period 值，去乘以该任务在整个 CFS 运行队列中的权重占比；(4) 虚拟运行的时间 = 实际运行时间 * NICE_0_LOAD / 该任务的权重；

从上面计算公式可以看出，权重高的进程运行时间 runtime 更大，但是 vruntime 由于分子分母互相消除，权重高的进程的虚拟运行时间的增速却是一样的。

还是来看一个实例吧，以 5 个 Task 为例，其中每个 Task 的 nice 值不一样（优先级不同），对应到的权重值在内核中提供了一个转换数组：

/*权重只和进程的nice值有关*/
const int sched_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,
};

从 sched_prio_to_weight[]可知，nice 值每减小 1，权重增加约 25%，一个调度周期中大约可以多获得 25%的 CPU 时间。

图来了：

(2)CFS 调度 tick

CFS 调度器中的 tick 函数为 task_tick_fair，系统中每个调度 tick 都会调用到，此外如果使用了 hrtimer，也会调用到这个函数。流程如下：

主要的工作包括：

  • (1) 更新运行时的各类统计信息，比如 vruntime， 运行时间、负载值、权重值等；

  • (2) 检查是否需要抢占，主要是比较运行时间是否耗尽，以及 vruntime 的差值是否大于运行时间等；

来一张图，感受一下 update_curr 函数的相关信息更新吧：

/*注册这些定时器中断*/
arch_timer_register(void) //drivers\clocksource\arm_arch_timer.c
    irqreturn_t timer_handler(const int access, struct clock_event_device *evt) //drivers\clocksource\arm_arch_timer.c
    evt->event_handler(evt);
        tick_device_uses_broadcast(struct clock_event_device *dev, int cpu) //kernel\time\tick-broadcast.c
            tick_handle_periodic(struct clock_event_device *dev) //kernel\time\tick-common.c
                tick_periodic(int cpu) //kernel\time\tick-common.c
                        /*在定时器中断处理函数中调用，user_tick若是用户时间为1，若是系统时间为0*/
                        update_process_times(int user_tick) //kernel\time\timer.c
                            /*这个函数是在定时器的代码中被调用，调用周期为HZ，关着中断调用的*/
                            scheduler_tick(void) //kernel\sched\core.c

/*切换到高分辨率模式*/
hrtimer_switch_to_hres(void)
    tick_setup_sched_timer(void) //kernel\time\tick-sched.c
        tick_sched_timer(struct hrtimer *timer) //kernel\time\tick-sched.c
            tick_sched_handle(struct tick_sched *ts, struct pt_regs *regs) //kernel\time\tick-sched.c
                update_process_times(user_mode(regs));


tick_nohz_switch_to_nohz(void)
    /*nohz低分辨率中断处理函数*/
    tick_nohz_handler(struct clock_event_device *dev)
        tick_sched_handle(struct tick_sched *ts, struct pt_regs *regs) //kernel\time\tick-sched.c
            update_process_times(user_mode(regs));

(3)任务出队入队

  • 当任务进入可运行状态时，需要将调度实体放入到红黑树中，完成入队操作；

  • 当任务退出可运行状态时，需要将调度实体从红黑树中移除，完成出队操作（移除后放在哪？）；

  • CFS 调度器，使用 enqueue_task_fair 函数将任务入队到 CFS 队列，使用 dequeue_task_fair 函数将任务从 CFS 队列中出队操作。

出队与入队的操作中，核心的逻辑可以分成两部分：

  • 1）更新运行时的数据，比如负载、权重、组调度的占比等等；

  • 2）将 sched_entity 插入红黑树，或者从红黑树移除；

(2) 由于 dequeue_task_fair 大体的逻辑类似，不再深入分析；

(3) 这个过程中，涉及到了 CPU 负载计算、task_group 组调度、CFS Bandwidth 带宽控制等，这些都在前边的文章中分析过，可以结合进行理解；

(4)任务创建

在父进程通过 fork 创建子进程的时候，task_fork_fair 函数会被调用，这个函数的传入参数是子进程的 task_struct。该函数的主要作用，就是确定子任务的 vruntime，因此也能确定子任务的调度实体在红黑树 RB 中的位置。

task_fork_fair 本身比较简单，流程如下图：

(5)任务选择

每当进程任务切换的时候，也就是 schedule 函数执行时，调度器都需要选择下一个将要执行的任务。在 CFS 调度器中，是通过 pick_next_task_fair 函数完成的，流程如下：

  • (1) 当需要进程任务切换的时候，pick_next_task_fair 函数的传入参数中包含了需要被切换出去的任务，也就是 pre_task；

  • (2) 当 pre_task 不是普通进程时，也就是调度类不是 CFS，那么它就不使用 sched_entity 的调度实体来参与调度，因此会执行 simple 分支，通过 put_pre_task 函数来通知系统当前的任务需要被切换，而不是通过 put_prev_entity 函数来完成；

  • (3) 当 pre_task 是普通进程时，调用 pick_next_entity 来选择下一个执行的任务，这个选择过程实际是有两种情况：当调度实体对应 task 时，do while()遍历一次，当调度实体对应 task_group 时，则需要遍历任务组来选择下一个执行的任务了。

  • (4) put_prev_entity，用于切换任务前的准备工作，更新运行时的统计数据，并不进行 dequeue 的操作，其中需要将 CFS 队列的 curr 指针置位成 NULL；

  • (5) set_next_entity，用于设置下一个要运行的调度实体，设置 CFS 队列的 curr 指针；

  • (6) 如果使能了 hrtimer，则将 hrtimer 的到期时间设置为调度实体的剩余运行时间；

  • (7) 调度类的优先级体现在 pick_next_task 函数中。

    转藏 分享 献花（0）

    来自： 深度Linux > 《待分类》

    举报/认领

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多