精华内容
下载资源
问答
  • 如何做好调度工作
    千次阅读
    2020-09-13 09:53:55

    一、什么是调度系统

    调度系统,更确切地说,作业调度系统(Job Scheduler)或者说工作流调度系统(workflow Scheduler)是任何一个稍微有点规模,不是简单玩玩的大数据开发平台都必不可少的重要组成部分。除了Crontab,Quartz这类偏单机的定时调度程序/库。开源的分布式作业调度系统也有很多,比较知名的比如:oozie,azkaban,chronos,zeus等等,此外,还有包括阿里的TBSchedule,SchedulerX和腾讯的Lhotse。

    二、为什么需要调度系统

    我们都知道大数据的计算、分析和处理,一般由多个任务单元组成(Hive、Sparksql、Spark、Shell等),每个任务单元完成特定的数据处理逻辑。

    多个任务单元之间往往有着强依赖关系,上游任务执行并成功,下游任务才可以执行。比如上游任务结束后拿到 A 结果,下游任务需结合 A 结果才能产出 B 结果,因此下游任务的开始一定是在上游任务成功运行拿到结果之后才可以开始。

    而为了保证数据处理结果的准确性,就必须要求这些任务按照上下游依赖关系有序、高效的执行。一个较为基础的处理方式是:预估出每个任务处理所需时间,根据先后顺序,计算出每个任务的执行的起止时间,通过定时跑任务的方式,让整个系统保持稳定的运行。

    一个完整的数据分析任务最少执行一次,在数据量较少,依赖关系较为简单的低频数据处理过程中,这种调度方式完全可以满足需求。然而在企业级场景中,更多的是需要每天执行,如果任务数量较多,在任务启动的时间计算上就将耗费大量时间,另外如果出现上游任务执行时长超出原定预计时间或者运行异常的问题,上述的处理方式将完全无法应对,也会对人力物力造成重复损耗。因此,对于企业数据开发过程来说,一个完整且高效的工作流调度系统将起到至关重要的作用。

    三、调度系统的两大种类

    调度系统分为作业调度系统资源调度系统两大类,但很多时候大家往往把这两类的概念混为一谈。

    1、资源调度系统

    资源调度系统的关注的重点底层物理资源的分配管理,目标是最大化地利用集群机器的CPU、磁盘、网络等硬件资源,所调配和处理的往往是与业务逻辑没有直接关联的诸如通用程序进程这类的对象。

    2、作业调度系统

    作业调度系统关注的重点在正确的时间点启动正确的作业,确保作业按照正常的依赖关系及时准确地执行。资源的利用率通常不是第一关注要点,业务流程的正确性才是最重要的。作业调度系统有时也会考虑负载均衡问题,但保证负载均衡更多的是为了系统自身的健壮性,而资源的合理利用作为一个可以优化的点,往往依托底层的资源调度系统来实现。

    那么,为什么市面上会存在这么多的作业调度系统项目,作业调度系统为什么没有像HDFS、Hive、 HBase 之类的组件那样形成一个相对 标准化的解决方案呢?归根结底,还是由作业调度系统的业务复杂性决定的。

    一个成熟易用、便于管理和维护的作业调度系统,需要和大量的周边组件对接,不仅包括各种存储计算框架,还可能要处理或使用到血缘管理、权限控制、负载流控、监控报警、质量分析等各种服务或事务。这些事务环节,每家公司都有自己的解决方案,所以作业调度系统所处的整体外部环境千差万别,而且,各公司各种业务流程的定制化需求又进一步加大了环境的差异性,所以,调度系统很难做到既能灵活通用地适配广大用户的各种需求,又不太晦涩难用。

    市面上现有的各种开源作业调度系统,不是在某些环节、功能上是缺失的,使用和运维的代价很高,需要大量二次开发;就是只针对特定的业务场景,形态简单,缺乏灵活性;要不就是在一些功能环节上是封闭自成体系的,很难和外部系统进行对接。

    那么,理想中的完备作业调度系统,到底都要处理哪些事务呢?要做好这些事务都有哪些困难要克服,有哪些方案可以选择,市面上的开源调度系统项目又是如何应对这些问题的,下面就让我和大家一起来探讨一 下。

    四、作业调度系统的两大种类

    根据实际的功能定位,市面上的作业调度系统主要分为以下两大类:定时分片类作业调度系统DAG工作流类作业调度系统。这两类系统的架构和功能实现通常存在很大的差异。

    1、定时分片类作业调度系统

    定时分片类系统的方向,重点定位于任务的分片执行场景,这类系统的代表包括TBSchedule、SchedulerX、 Elastic-job、 Saturn。

    这种功能定位的作业调度系统,其最早的需求来源和出发点往往是做一个分布式Crontab和Quartz。

    一开始各个业务方自成一体,自己搞自己的单机定时任务,随着越来越多,分散管理的代价越来越高。再加上有些业务随着数据量的增加,各种定时任务为了提高运行效率,也需要以分布式的方式在多台机器上并发执行。这时候,分布式分片调度系统也就应运而生了。

    这类系统的实际应用场景,往往和日常维护工作或需要定时执行的业务逻辑有一定的关联。比如需要定时批量清理一批机器的磁盘空间, 需要定时生成一批商品清单,需要定时批量对一批数据建索引, 需要定时对一批用户发送推评通知等。

    这类系统的核心目标基本是以下两点:

    (1)对作业分片逻辑的支持:将一个大的任务拆成多个小任务,分配到不同的服务器上执行,难点在于要做到不漏、不重,保证负载均衡,节点崩溃时自动进行任务迁移等。

    (2)高可用的精确定时触发要求:因为往往涉及实际业务流程的及时性和准确性,所以通常需要保证任务触发的强实时和可靠性。

    所以,负载均衡、弹性扩容、状态同步和失效转移通常是这类调度系统在架构设计时重点考虑的特性。

    从接入方案和流程上来说,因为要支持分片逻辑和失效转移等,这类调度系统对所调度的任务通常都是有侵入性要求的。

    常见的做法是用户作业需要依赖相关分片调度系统的客户端库函数,扩展一个作业调度类作为作业触发的入口类。一般还需要接收和处理分片信息用于对数据进行正确的分片处理。通常还需要实现一些接口用于满足服务端的管理需求,比如注册节点、注册作业、启动任务、停止任务、汇报状态等。有些系统还要求作业执行节点常驻守护进程,用于协调本地作业的管理和通信。

    2、DAG工作流类调度系统

    DAG工作流类调度系统的关注重点定位于任务的调度依赖关系的正确处理,分片执行的逻辑通常不是系统关注的核心,或者不是系统核心流程的关键组成部分,如果某些任务真的关注分片逻辑,往往交给后端集群(比如MR任务自带分片能力)或具体类型的任务执行后端去实现。

    这类系统的代表包括oozie、azkaban、chronos、zeus、 Lhotse, 还有各种大大小小的公有云服务提供的可视化工作流定义系统。

    DAG工作流类调度系统所服务的往往是作业繁多、作业之间的流程依赖比较复杂的场景。比如大数据开发平台的离线数仓报表业务,从数据采集、清洗,到各个层级的报表的汇总运算,再到最后教据导出到外部业务系统,一个完整的业务流程可能涉及成百上千个相互交叉,依赖关联的作业。

    所以DAG工作流类调度系统关注的重点通常包括以下几点:

    (1)足够丰富和灵活的依赖触发机制:比如时间触发任务、依赖触发任文混合触发任务

    而依赖触发任务自身可能还要考虑多亲依赖、长短周期依赖(如小时村任务依赖天任务,或者反过来)、依赖范围判定(比如所依赖任务最后一次成功就可以触发下游,还是过去一个星期的所有任务都成功才可以触发下游)、自身历史任务依赖、串并行触发机制等。

    (2)作业的计划、变更和执行流水的管理和同步

    定时分片类调度系统中固然也要考虑这个需求,但通常相对简单。而在DAG工作流类调度系统中,因为任务触发机制的灵活性和作业依赖关系的复杂性,这个需求就尤为重要,需要提供的功能更加复杂,具体的问题解决起来也困难很多。

    (3)任务的优先级管理、业务隔离、权限管理

    在定时分片类调度系统中,具体执行端的业务在很多情况下本来就是隔离的,注册了特定业务的节点才会去执行特定的任务。而且业务链路一般都比较短,再加上强实时性要求,所以对优先级的管理通常要求也不高,基本靠资源隔离来实现资源的可用,一般不存在竞争资源的问题,权限管理也是一样的。

    而在DAG工作流类调度系统中,往往一大批作业共享资源执行,所以优先级、负载隔离和权限管控的问题也就突显出来了。

    (4)各种特殊流程的处理,比如暂停任务、重刷历史数据、人工标注失败或成功、临时任务和周期任务的协同

    这类需求本质上也是业务流程的复杂性带来的,比如业务逻辑变更、脚本写错、上游数据有问题、下游系统挂掉等,而业务之间的网状关联性,导致处理问题时需要考虑的因素很多,也就要求处理的手段应足够灵活强大。

    (5)完备的监控报警通知机制

    最简单的有任务失败报警、超时报警,复杂一点的有流量负载监控、业务进度监控和预测, 如果做得再完善一点,还可以包括业务健康度监控分析、性能优化建议和问题诊断专家系统等。

    需要注意的是,这两类系统的定位目标并不是绝对冲突矛盾的。只不过要同时圆满地支持这两类系统的需求,从实现的角度来说是很困难的,因为侧重点不同,在架构上多少会对某些方面做些取舍,当前的系统都没有做到完美的两者兼顾。但并不代表这两类系统的实现就一定是不可调和的,好比离线批处理计算框架和流式实时计算框架,长期以来它们各行其道,但是随着理论和实践的深入,也开始有依托一种框架统一处理两类计算业务的可能性出现。

    参考自:刘旭晖《大数据平台架构基础指南》

    更多相关内容
  • Apache DolphinScheduler是一个新一代分布式大数据工作流任务... DolphinScheduler 发展很快 很多公司调度都切换到了DolphinScheduler,掌握DolphinScheduler调度使用势在必行,抓住新技术机遇,为跳巢涨薪做好准备。
  • Apache DolphinScheduler是一个新一代分布式大数据工作流任务调度系统,致力于“解决大数据任务之间错综复杂的依赖关系,整个数据处理开箱即用”。它以 DAG(有向无环图) 的方式将任务连接起来,可实时监控任务的运行...
  • 不羡鸳鸯不羡仙,一行代码调半天。SpringBoot集成任务调度,实现每天定时发送天气预报,随时做好了“速冻”的心理准备
  • 1、课程名字:新一代分布式大数据工作流任务调度系统DolphinScheduler源码分析,2021年8月新课,提供代码课件下载! 2、课程概述: 本课程会带大家深入DolphinScheduler框架源码,包括设计的思想和技术都会讲解,...
  • 进程调度基本原理

    2022-04-16 12:44:18
    1. 为什么需要调度 进程调度的概念比较简单,我们假设在一个单核处理器的系统中,同一时刻只有一个进程可以拥有处理器资源,那么其他的进程只能在就绪队列中等待,等到处理器空闲之后才有计划获得处理器资源来运行。...

    进程调度的概念比较简单,我们假设在一个单核处理器的系统中,同一时刻只有一个进程可以拥有处理器资源,那么其他的进程只能在就绪队列中等待,等到处理器空闲之后才有计划获得处理器资源来运行。在这种场景下,操作系统就需要从众多的就绪进程中选择一个最合适的进程来运行,这个就是调度器需要做的事情。linux内核管理过程中是按照线程完成调度工作,与线程所属进程基本上没有什么关系。

    1. 调度简介

    在计算机开始的初期调度算法非常简单,多道程序按照顺序方式进行执行,管理过程只需要做好基本的输入和输出管理即可。但是,现代社会计算机CPU速度非常快,输入输出已经限制了程序的运行。当前运行的进程基本上划分为I/O请求信和CPU密集型,随着时代的发展,实际计算机越来越偏向于I/O请求型计算机发展,CPU密集型逐渐用外部基本的IC替代其复杂的计算工作。

    1.1. 调度情况

    通常来说,操作系统是应用程序和可用资源直接的媒体,CPU是一个重要的资源,调度器可以临时分配一个任务在CPU上执行。为了使各个进程间可以公平共享CPU时间,而同时又要考虑不同的任务优先级,所以就需要一个调度器,来保证以下功能有效的分配CPU时间片,根据用户的目标来提供一个很好的用户体验。当面对一些互相冲突的目标的时候,提供一个最优化的调度算法,例如既要为关键实时任务最小响应时间,又要最大限度的提高CPU的总体利用率。知道了进程的分类,那就可以知道哪些场景需要调度来协调,如IO消耗性的,例如磁盘,打印机,网络等场景。调度在不同场景下的目标有。

    我们以生活中为例,来看看调度器对我们实际生活的影响,以我们手机上的一个场景为例。如我们手机上运行一个机器学习的程序,大约CPU需要运行30分钟,我们也需要播放音乐。如果没有调度器:

    在这里插入图片描述

    对于手机上运行的学习进程和播放进程,学习进程属于批处理进程,而播放音乐属于实时进程,如果整体播放延时比较大就会出现卡顿的情况,用户体验就会很差。如果没有调度器,对于用户就需要30分钟才能播放音乐,那么它可能等不到30分就会抛弃这个手机。

    如果有调度器:调度器让生活更美好

    在这里插入图片描述

    调度器“任性化”将程序切片执行,对于用户就可以边听音乐边等待他的程序运行完,能够完美的实现二者的兼容。

    1.2. 调度行为与何时调度

    如果站在CPU的角度来看进程,有些进程一直占用处理器,有些进程只需要一部分处理器资源即可。所以进程按照这个特性可以分为两类

    1. CPU消耗型:CPU消耗型的进程会把大部分的时间用在运行代码上,并且会一直占用CPU。一个常见的例子就是while循环的运行,如运行大量计算的程序等。
    2. IO消耗性:IO消耗性的进程会把大部分的时间用在提交I/O请求或等待I/O请求,所以这类的进程通常只需要很少的处理器计算资源即可,如需要键盘的输入进程或等待网路I/O的进程。

    存在调度的基本情况类型如下:

    1. 在创建子进程以后,父进程与子进程执行顺序需要调度
    2. 一个进程退出时需要确定调度
    3. 当一个进程阻塞在I/O和信号量上时,需要调度其他进程进入执行
    4. 当I/O中断发生时,必须做出调度决策

    1.3. 调度算法分类

    不同环境或者领域需要实现目标不同,需要不同的调度算法方向也是不一样的。具体可以划分成三种类型,分别是交互式、批处理、实时。其特征如下:

    1. 交互式进程: 与人机交互的进程,例如鼠标、键盘、触摸屏等相关的应用,这类进程的特点是系统响应时间越短越好,否则用户就会抱怨系统卡顿。一般个人PC和掌上设备属于这种类型。
    2. 批处理进程: 此类进程默默运行,可能会占用比较多的系统资源,对响应时间没有确定的要求。网络处理器和数据流水处理都属于这种类型。
    3. 实时进程: 有些应用对整体时延有严格的要求,如VR设备,从头部转动到画面显示的间隔时间有明确的要求,否则人的体验不是太好;同时例如工业控制系统,不符合时延可能会导致严重的事故。工厂中RTOS系统属于这种类型。

    1.4. 调度器目标

    针对不同的目标环境,设计调度算法的侧重点也是不一样的。当然,多有系统都会有如下几项的公共特点:

    • 公平 - 给每个进程公平的CPU份额
    • 策略强制执行 - 保证规定的策略被执行
    • 平衡 - 保存系统的所有部分都忙碌
    • 低功耗 - 对于目前的移动设备,如何设计一个更优的调度算法,来保证系统的低功耗也需要重点

    对于批量处理系统

    • 吞吐量 - 每小时最大的作业数。最大系统利用率(高吞吐量),对于一些批处理系统中需要考虑
    • 周转时间 - 从提交到中止的最小时间

    对于交互式系统

    • 响应时间 - 快速响应请求。此类进程经常与用户进行交互, 因此需要花费很多时间等待键盘和鼠标操作. 当接受了用户的输入后, 进程必须很快被唤醒, 否则用户会感觉系统反应迟钝,主要用于一些交互式系统需要重点考虑
    • 均衡性 - 满足用户的期望

    实时系统

    • 满足截至时间 - 避免丢失数据。这些进程由很强的调度需要, 这样的进程绝不会被低优先级的进程阻塞. 并且他们的响应时间要尽可能的短
    • 可预测性 - 在多媒体系统中避免品质降低

    确定如何从就绪队列中选择下一个执行的进程进入调度,需要解决以下问题。如何挑选就绪队列中的哪一个进程,通过什么样的调度准则来选择。调度算法的要求,希望得到**“更快”**服务,那么如何定义什么是更快呢?根据调度器的目标,其可以重点关注:

    高吞吐量:传输文件时的高带宽
    低响应延时:玩游戏时的低延迟
    调度器的响应目标考虑:

    减小响应时间:及时处理用户的输入请求,尽快将输出反馈给用户
    减小平均响应的时间波动:在交互系统中,可预测性比高差异低平均更重要
    低延迟调度改善了用户的交互体验:如果移动鼠标时,屏幕中的光标没动,那么客户会如何做呢?会不会重启
    处理器调度吞吐 量目标考虑

    增加吞吐量:减小开销,主要是上下文切换的开销,系统资源的高利用(CPU /IO设备)
    减小等待时间:减小每个进程的等待时间
    处理器公平的定义:

    2. 交互式系统中的调度

    3.1 先来先服务算法(First Come First Served, FCFS)

    每次从就绪队列选择最先进入队列的进程,然后一直运行,直到进程退出或被阻塞,才会继续从队列中选择第一个进程接着运行。

    依据进程进入就绪队列的先后顺序排列,进程进入等待或者结束状态时,就绪队列中的下一个进程占用CPU,3个进程,计算时间分别为12,3,3,FCFS算法的周转时间,根据任务到达的顺序不同,周转时间不同

    在这里插入图片描述

    结合大家学习中,遇到的实际例子,我们来学习下整个过程,例如该过程中,调度器是我们生活中遇到的学霸,而此时有3个同学想学霸请教问题,其思路如下

    在这里插入图片描述

    该问题对于C同学来说,有一个很大的问题是,我的问题很简单,却需要等那么长的时间,所以对于该算法的特征如下:

    优点缺点
    简单 1. 平均等待时间波动较大,短进程可能排到长进程后面
    2. IO资源和CPU资源的利用率较低,对于上面的例子,如果该同学需要查阅相关文档,那么学霸就需要一直等待,浪费学霸的资源


    3.2 短进程优先算法(SPN)

    它会优先选择运行时间最短的进程来运行,这有助于提高系统的吞吐量。

    选择就绪队列中执行时间最短进程占用CPU进入运行状态,就绪队列按预期的执行时间来排序

    在这里插入图片描述

    进程的平均周转时间为:

    在这里插入图片描述

    还是基于刚才学霸解决问题的实例来看看这个算法的执行顺序,首先A同学先执行,当执行到2后,同学B和C都来寻求学霸解决问题,但是此时A占用了学霸,所以当A解决完问题后,发现同学C问题简单,所以就优先解决C的问题

    在这里插入图片描述

    优点缺点
    平均周转时间较短1. 不公平,可能出现导致饥饿,连续的短进程流会使得长进程长时间无法获得CPU资源
    2. 平均响应时间过长
    3. 需要预知未来,需要解决预估下一个CPU计算的持续时间

    2.3 时间片轮转算法(RR, Round-Robin)

    定义:每个进程被分配一个时间段,称为时间片(*Quantum*),即允许该进程在该时间段中运行。如果时间片用完,进程还在运行,那么将会把此进程从 CPU 释放出来,并把 CPU 分配另外一个进程;如果该进程在时间片结束前阻塞或结束,则 CPU 立即进行切换;
    通过时间片,分配处理器资源的基本单元,当时间片结束后,按FCFS算法切换到下一个就绪进程,我们还是以刚才例子为例,此时为

    在这里插入图片描述

    但是这种算法也需要重点考虑时间片长度,因为切换进程,需要有额外的上下文切换

    时间片太长

    • 等待时间过长
    • 极限情况下退化成FCFS

    时间片太短

    • 反应迅速,但产生大量的上下文切换
    • 大量上下文切换开销会影响系统的吞吐量

    时间片长度选择目标

    • 选择一个合适的时间片长度
    • 经验规律:维持上下文切换开销处于1%以内

    3. 调度优先级

    对于操作系统中的任务是不同的,例如,系统进程和用户进程、前台进程和后台进程,如果不加以区分,那么系统中关键的任务无法及时处理,后台运算导致视频播放卡顿,所以基于此,重要的任务需要被优先调度,就产生了优先级的概念。

    3.4.1 多队列调度算法(MQ)

    对于该调度算法,就绪队列被划分成多个独立的子队列,如前台(交互)、后台(批处理),每个队列拥有自己的调度策略,如前台-RR,后台-FCFS,队列间的调度

    **固定优先级:**先处理前台,后处理后台,可能导致饥饿
    **时间片轮转:**每个队列读的到一个确定的能够调度器进程的总时间,如80%CPU时间用于前台,20%CPU时间用于后台

    在这里插入图片描述
    还是以学霸解决问题为例,基于此的算法为:

    在这里插入图片描述

    所以该算法特征为:

    维护多个优先级队列
    高优先级的任务优先执行
    同优先级内使用Round Robin调度

    3.4.2 公平共享调度(FSS, Fair Share Scheduling)

    公平共享调度控制用户对系统资源的访问

    一些用户组比其他用户组更重要
    保证不重要的组无法垄断资源
    未使用的资源按比例分配
    没有达到资源使用率目标的组获得更高的优先级

    4 调度算法总结

    算法 优点缺点
    先来先服务算法简单不公平,平均等待时间较差
    短进程优先算法平均周转时间最小

    1. 不公平,可能导致饥饿

    2. 需要精确预测计算时间

    时间片轮转算法公平平均等待时间较差
    公平共享调度公平是第一要素
    多队列调度算法多种算法的集成 
    展开全文
  • 什么是调度调度是CPU资源管理器。操作系统的作用之一就是系统资源管理器。CPU是计算机系统中最重要的资源,当然也要管理。所有进程的运行都需要CPU,对CPU该如何管理呢?对于直接共享型的事物,我们有两种管理方法...

    知识体系树
    总体写作原则



    推荐阅读: 操作系统导论


    一、进程调度概览

    进程调度是操作系统最重要的内容之一,也是学习操作系统的重点和难点。关于进程本身的实现和管理请参看《深入理解Linux进程管理》。关于进程调度,我们首先就会问出一些问题,什么是进程调度,为什么要进程调度,如何进行调度。下面我们用一幅图把这些问题关联起来:

    在这里插入图片描述
    这张图把进程调度的所有问题和知识点都关联了起来,本文后面所有的内容都是对这张图的解释和扩展延伸,下面让我们来一一讲解。

    1.1 什么是调度

    什么是调度?调度是CPU资源管理器。操作系统的作用之一就是系统资源管理器。CPU是计算机系统中最重要的资源,当然也要管理。所有进程的运行都需要CPU,对CPU该如何管理呢?对于直接共享型的事物,我们有两种管理方法:一种是时间分割管理,另一种是空间分割管理。由于CPU自身的特性,没有空间分割相似性,只有时间分割相似性,所以我们只能对CPU进行时间分割管理。对CPU进行时间分割管理的具体做法就叫做进程调度。

    那么调度的是什么呢?进程调度,调度的当然是进程啦,也对也不对。我们知道进程是资源分配的单位,线程是执行的单位。早期的时候没有多线程,进程就是线程,线程就是进程,所以此时进程调度调度的是进程。但是当有了多线程之后,线程变成了执行的单位,进程不再是执行的单位,进程调度调度的就是线程了。不过由于历史原因,大家都习惯叫进程调度,所以现在这个领域的名称还是叫进程调度。后文中说到调度进程的地方都是调度的线程,由于习惯问题,我们还说调度进程不说调度线程,请大家要注意。

    对线程的调度可以有两种方式:一种是直接调度线程,不考虑它们所属的进程,这种方式叫做直接调度或者一级调度;另一种是先调度进程,再在进程内部调度线程,这种方式叫做间接调度或者二级调度。POSIX规定,操作系统可以选择这两种方式中的任何一种都行。Linux选择的是一级调度,为什么会这么选择呢?主要是为了提高进程的并发性,充分利用多CPU多核的优势。如果使用二级调度的话,看似每个进程之间都公平了,但是有些进程的计算量比较大,就无法通过多开线程提高自己的性能,这样对系统整体的性能是有害的,也不利用发挥计算机多CPU的优势。一级调度看似对有些进程不公平,但是计算量小的进程少开线程,计算量大的进程多开线程,相对还是很公平的。

    就像国家希望每个企业都做大做强,但是同时也会反垄断一样。Linux也推出了cgroup组调度机制,来限制某个或者某一类进程对CPU资源的过度占用。本文中不讲cgroup组调度机制,后文的讲解都是假设没有cgroup组调度。

    1.2 为什么要调度

    我们知道了什么是调度,那么为什么要调度呢,没有调度会怎么样呢?最早的计算机是没有调度的,程序只能一个一个地运行,一个进程死亡之后才能去运行下一个进程。这里面首先存在的问题就是我们没法同时运行多个进程。其次就算我们不需要同时运行多个进程,程序在运行的过程中如果要等IO,CPU就只能空转,这也十分浪费CPU资源。于是最早的多任务——协作式多任务诞生了,当程序由于要等IO而阻塞时就会去调度执行其它的进程。但是协作式多任务存在着很大的问题,就是每个进程运行的时间片长短是不确定的,而且是很偶然很随机的。如果一个进程它一直在做运算就是不进行IO操作,那么它就会一直霸占CPU。针对这个问题,当时想出的方法是道德解决方案。内核向进程提供系统调用sched_yield,它会使进程主动放弃CPU让其它进程来执行。然后要求所有的程序员在程序中合适的地方尽量多地加入sched_yield调用。这个方法在当时是管用的,因为当时计算机的使用者(同时也是程序员)仅限于少数科研机构和政府机关的部分人员,一台电脑的共同使用者都认识,面子上还得过得去。

    后来随着计算机的普及,以及计算机的使用者和程序员这两个角色的分离,主要靠道德约束的协作式多任务已经行不通了,我们需要强制性多任务,也就是抢占式多任务。抢占式多任务使得每个进程都可以相对公平地平分CPU时间,如果一个进程运行了过长的时间就会被强制性地调度出去,不管这个进程是否愿意。有了抢占式多任务,我们在宏观上不仅可以同时运行多个进程,而且它们会一起齐头并进地往前运行,不会出现某个进程被饿死的情况,这样我们使用电脑的体验就非常完美了。抢占式多任务和协作式多任务不是对立的,它们是相互独立的,可以同时存在于系统中。

    抢占又分为用户抢占和内核抢占。由于抢占对进程来说是异步的,进程被抢占时不一定运行在什么地方,有可能运行在用户空间,也有可能运行在内核空间(进程通过系统调用进入内核空间)。如果抢占点是在用户空间,那么抢占就是安全的,如果在内核空间就不一定安全,这是为什么呢?因为对于用户空间来说,如果抢占会导致线程同步问题,那么用户空间有责任使用线程同步机制来保护临界区,只要用户空间做好同步就不会出问题。如果内核也做好了同步措施,内核抢占也不会出问题,但是内核最初的设计就没有考虑内核抢占问题,所以刚开始的时候内核是不能抢占的。后来内核开发者对内核进行了完善,把内核所有的临界区都加上了同步措施,然后内核就是可抢占的了。内核能抢占了不代表内核一定会抢占,内核会不会抢占由config选项控制,可以开启也可以关闭,因为内核抢占还会影响系统的响应性和性能。开启内核抢占会提高系统的响应性但是会降低一点性能,关闭内核抢占会降低系统的响应性但是会提高一点性能。因此把内核抢占做成配置项,可以让大家灵活配置。服务器系统一般不需要与用户交互,所以会关闭内核抢占来提高性能,桌面系统会开启内核抢占来提高系统的响应性,来增加用户体验。

    现在我们再来看一下为什么要调度。因为如果没有调度的话,就不能实现多任务,一次就只能运行一个程序,我们使用电脑的体验就会大大降低。有了调度就有了多任务,我们就能同时在电脑上做很多事情,使用体验就会非常好。

    1.3 为什么能调度

    我们再来看看为什么能调度呢。我们把协作式多任务叫做主动调度,抢占式多任务叫做被动调度。为什么能调度分为两部分:为什么能触发调度和为什么能执行调度。对于主动调度,调度是进程主动触发的,这个是肯定能的。对于被动调度,在图灵机模型中是做不到的,因为图灵机是一条线性一直往前走的,进程在执行时,进程要是不主动,是不可能跳到其它进程来执行的。被动调度能做到的原因关键就在于中断机制,因为中断是强行在正常的执行流中插入了一段代码,它能改变后续代码的走向。有了中断机制,我们就可以创建一个定时器中断,以固定的时间间隔比如每10ms来触发中断,检测进程是否运行时间过长,如果过长就触发调度。这样任何进程都不可能霸占CPU,所以进程都能公平地共享CPU时间。关于中断的原理,请参看《深入理解Linux中断机制》。这里引用其中的一幅图来看一下:
    在这里插入图片描述
    可以看到在纯图灵机模型中,进程如果不主动进行调度,是没有外力强迫进程进行调度的,进程就能一直霸占CPU。有了中断机制之后,在中断的处理中可以触发调度,在中断返回的点可以执行调度,这样就可以避免进程霸占CPU了。

    前面说的是为何能触发进程调度,主动调度是进程自己触发的,被动调度是在中断中触发的。现在来看看为何能执行调度,执行调度包括两部分:选择进程和切换进程。选择进程是纯软件的,肯定能实现。切换进程是怎么切换呢?一个进程执行的好好的,怎么就切换了呢,需不需要硬件的支持呢?进程切换主要是切换执行栈和用户空间,这两个都需要用到CPU特定的指令。进程切换的具体原理和细节我们在2.7节中讲。

    1.4 何时调度

    我们前面已经讲了主动调度(协作式多任务)和被动调度(抢占式多任务)。

    对于主动调度,触发调度和执行调度是同步的、一体的,触发即执行。主动调度发生的时机有IO等待、加锁失败等各种阻塞操作以及用户空间主动调用sched_yield。

    对于被动调度,触发调度和执行调度是异步的、分离的,触发调度并不会立马执行调度,而是做个需要调度的标记,然后在之后的某个合适的地方会检测这个标记,如果被设置就进行调度。触发调度的点有:在定时器中断中发现当前进程超时了,在唤醒进程时发现新进程需要抢占当前进程,在迁移进程时发现新进程需要抢占当前进程,在改变进程优先级时发现新进程需要抢占当前进程。其中第一个触发点是当前进程需要被抢占,它是用来保证公平调度,防止进程霸占CPU的,后三个触发点是新进程需要抢占当前进程,它是用来提高系统响应性的。执行调度的点有:系统调用完成之后即将返回用户空间,中断完成之后即将返回用户空间,如果开启了内核抢占的话则还有,中断完成之后即将返回内核,如果中断发生在禁止抢占临界区中,那么中断完成之后返回内核是不会执行调度的,而是会在临界区结束的时候执行调度。下面我们借用《深入理解Linux中断机制》中的几个图来看一下这几个执行调度检测点:
    在这里插入图片描述
    系统调用完成之后即将返回用户空间和中断完成之后即将返回用户空间,是非常好的执行进行调度的点,也就是此图中的三个箭头的地方。CPU异常在意义上不是系统调用,但是在形式上和逻辑上相当于是系统调用。
    在这里插入图片描述
    在这里插入图片描述
    中断发生在内核空间的场景,如果开启了内核抢占,如果被抢占的内核代码不是在禁用抢占临界区,中断返回时是执行调度的点。如果被抢占的内核代码在禁用抢占临界区中,在执行调度的点被推迟到了临界区的出口处。

    1.5 如何调度

    现在到了执行调度的时刻了。执行调度分为两步:一是选择下一个要执行的进程,二是切换进程。选择下一个要执行的进程,这就是调度算法了。首先调度算法只能从Runnable的进程中进行选择,不能选择Blocked进程,因为选择了也没有意义。其次算法还要区分进程类型,比如普通进程与实时进程,肯定要优先选择实时进程,在同一类型的进程中还要有具体的算法来决定到底选择哪个进程。在Linux中一共把进程分为了5类,每一类都有一个具体的算法。类之间的关系是优先选择高类的进程,只有当高类没有Runnable进程时才会去选择低类进程。

    进程选择好了之后就要切换进程了。切换进程分两步:第一步是切换用户空间,第二步是切换执行栈(线程栈)。如果要切换的两个线程属于同一个进程就不需要切换用户空间了。切换用户空间是一个CPU架构相关的事情,在x86 CPU上是给CR3寄存器赋值新进程的页表树的根指针。此时切换的执行栈是线程的内核栈,执行栈代表的是当前线程的执行情况,切换执行栈就是切换线程。线程的用户栈信息都在内核栈里保存着。切换完内核栈之后,线程继续执行就会返回用户空间,由于此时用户空间已经切换完成,内核栈上也保存着用户栈的信息,所以线程能返回到正确的用户空间线程上去。

    下面我们画个图来看一下:
    在这里插入图片描述
    对于一个CPU来说,永远只有一个当前进程在运行,当执行进程调度时,需要从其它进程中选择一个进程,把它旋转到最下方作为当前进程,它就开始运行了。

    1.6 调度均衡

    前面所说的都是针对一个CPU的情况,对于多个CPU来说,每个CPU也是这样的逻辑。但是有一点不同的是,如果一个系统上的多个CPU忙的忙死闲的闲死,显然不太好,因此多个CPU之间会进行调度均衡。调度均衡可以分为个体均衡和总体均衡。个体均衡是从进程的角度出发选择到一个相对清闲的CPU上去运行。总体均衡是从CPU的角度出发如何从别的CPU上拉取一些进程到自己这来执行,使得所有CPU的工作量尽量平均。个体均衡的触发点有三个:一是新进程刚创建时,二是进程要执行新程序时,三是进程被唤醒时,在这三个点进程都可以选择去哪个CPU的运行队列上去等待执行。在个体均衡下,每个进程都尽量选择相对清闲的CPU,所以所有CPU的负载应该还是会比较均衡的。但是时间长了可能还是会出现负载不均衡的情况,此时就要进行总体均衡了。总体均衡的触发点有三个:一是CPU即将idle前会去找到最忙的CPU然后拉取一些任务过来;二是定时器中断的周期性检测,会检查是否所有的CPU都一样忙,如果忙闲差别太大就会进行进程迁移,使得所有CPU忙闲程度接近;三是在idle进程中如果CPU发现自己太忙而有的CPU在idle就会唤醒那个CPU进行负载均衡。

    1.7 调度器评价

    狭义的调度器指的是具体的调度算法,广义的调度器指的是整个调度体系。不过两者的评价指标是相同的,所以我们这里不具体区分调度器是指调度算法还是调度体系。调度器的评价指标有以下几个:

    1.响应性,当一个进程发生事件需要去处理的时候能否及时被调度。这一点和使用体验是密切相关的,当我们用鼠标点击一个程序的时候,肯定希望程序立即能做出响应,如果程序过了好几秒才有反应,那我们肯定会很烦的。

    2.吞吐量,系统在相同的时间内能够运行更多的程序、执行更多的指令。这个首先要求调度器本身的代码要尽量的高效。如果调度器写得非常复杂,运行一次就需要好几毫秒的话,那留给进程运行的时间就不多了。其次进程调度的频率要低,如果进程调度的频率比较高的话,那调度器执行的次数就比较多,从而占用了较多的CPU时间,而且频繁切换进程也会影响缓存的性能。从这一点来看响应性和吞吐量是有矛盾的,提高响应性会增加进程切换的频率,而这会降低系统的吞吐量。

    3.公平性,指的是相对公平性,每个进程实际获得的时间份额与应当获得的时间份额都相差不大。不会出现有些进程饥饿的情况,也不会出现有些进程获得过多时间份额的情况。

    4.适应性,指的是系统无论是调度几个进程还是调度几万个进程,都能撑得住,都能收放自如,各项指标都不能受到太大的影响。

    5.节能性,自从智能手机越来越普及,而手机的电池技术一直没有较大的突破,所以省电对手机来说就是一项非常重要的任务,调度器也不可避免地要考虑省电问题了。

    1.8 调度器历史

    Linux的调度器经历了长久的发展,是内核中被优化最多目前最完善的模块之一。下面我们来看一下Linux调度器发展的历史。

    Traditional Scheduler: v1.0 – v2.4
    这一阶段的调度器和传统的UNIX上的调度器逻辑是一样的。全局只有一个运行队列,所有进程都放在一个队列上。进程区分IO密集型和CPU密集型,根据进程的睡眠时间计算动态优先级,按照动态优先级决定进程的调度顺序,按照优先级分配进程的时间片大小,时间片大小是等差数列。进程在运行队列上并没有特定的排序,每次选择下一个进程的时候都要遍历整个队列,所以算法的时间复杂度是O(n)。在SMP上也只有一个运行队列,当CPU比较多进程也比较多的时候,锁冲突比较严重。

    O(1) Scheduler: v2.5 – v2.6.22
    此调度器主要是针对传统调度器进行了改进。首先把运行队列从单一变量变成了per-CPU变量,每个CPU一个运行队列,这样就不会有锁冲突了,不过这样就需要调度均衡了。其次把运行队列的一个链表分成了两个链表数组:活动数组和过期数组。时间片没用耗尽的进程放在活动数组中,时间片耗尽的进程放在过期数组中,当所有进程的时间片都耗尽的时候交换两个数组,重新分配时间片。两个数组都使用动态优先级排序,并用bitmap来表示哪个优先级队列中有可运行的进程,把选择进程的算法复杂度降低到了O(1)。对进程区分IO密集型和CPU密集型并计算动态优先级这一点和传统调度器一样没有变。

    SD Scheduler:(未合入)
    楼梯调度器,它是对O(1)调度器的改进,算法复杂还是O(1)。之前的调度器都区分IO密集型和CPU密集型,算法要对进程的类型进行探测,根据探测结果调整动态优先级。这就有很大的问题,探测不一定准确,而且进程还可以欺骗调度器,最终会导致调度有很大的不公平性。楼梯调度器是第一次尝试使用公平调度算法,它废除了动态优先级,不再区分IO密集型进程和CPU密集型进程,但是仍然让IO密集型进程保持较高的响应性。在实现上,楼梯调度算法废弃了过期数组,只使用一个数组。当进程使用完自己的时间片之后,其时间片就会被减半并下降到下一个优先级,其本身的优先级还是不变的。当进程下降到最后一个优先级之后就再回到它本来的优先级队列并重新分配时间片。整个过程就像下楼梯一样,所以这个算法就叫做楼梯调度器。此算法虽然没有合入到标准内核,但是它第一次证明了可以采取完全公平的思想进行调度,也就是不区分IO密集型和CPU密集型进程。

    RSDL Scheduler:(未合入)
    旋转楼梯调度器,是对楼梯调度器的改进。又重新引入了过期数组,为每个优先级都分配一个组时间配额记为Tg,进程本身的时间片记为Tp。当进程用完自己的时间片时会下降一个优先级,当一个优先级的Tg被用完时,组内所有的进程都会下降一个优先级。进程下降到最低优先级之后会被放入过期数组,当活动数组为空时就会交换活动数组和过期数组。由于加了Tg,使得低优先级进程的调度延迟可控,进一步增加了公平性。

    CFS: Completely Fair Scheduler: v2.6.23 – now
    完全公平调度器,从SD/RSDL中吸取了完全公平的思想,不再区分IO密集型进程与CPU密集型进程,不再根据睡眠时间调整动态优先级,所有普通进程都按优先级相对平分CPU时间,算法复杂度是O(logn)。此时对调度器框架也进行了重构,和之前的有很大的不同。之前的调度器是一个算法调度所有进程,在算法内部区别对待实时进程和普通进程。现在的调度器框架是先区分不同类型的进程,普通进程一个调度类,实时进程一个调度类,调度类里面再去实现具体的调度算法。CFS是普通调度类的算法。

    二、进程调度框架

    前面我们对进程调度的概念和逻辑进行了讲解,现在我们来看一下Linux上进程调度的框架结构。本章只讲总体框架,不讲具体算法,具体算法在后面的章节中讲。

    2.1 调度队列

    我们先来看一下进程的状态转换图。
    在这里插入图片描述
    处于就绪(Runnable)状态的进程可以被调度到CPU上去执行。但是处于就绪状态的进程可能不止一个,所以我们需要一个运行队列来安放所有就绪的进程,由于CPU也不止一个,所以我们需要NR_CPU个运行队列。

    我们看一下调度队列的定义(代码经过了高度删减):
    linux-src/kernel/sched/sched.h

    struct rq {
    	raw_spinlock_t		__lock;
    	unsigned int		nr_running;
    
    	struct cfs_rq		cfs;
    	struct rt_rq		rt;
    	struct dl_rq		dl;
    
    	struct task_struct __rcu	*curr;
    	struct task_struct	*idle;
    	struct task_struct	*stop;
    
    	int			cpu;
    	int			online;
    };
    

    linux-src/kernel/sched/core.c

    DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);
    

    内核定义了一个per-CPU变量runqueues,其类型是struct rq。所有的就绪进程都会被放入某个CPU的rq上去,具体放到哪个rq上,这个在调度均衡里面讲。内核一共定义了五个调度类(这个在2.5中细讲),属于不同调度类的进程会被放入不同的子队列,所以rq中包含三个子运行队列cfs_rq、rt_rq、dl_rq。为啥只有3个子运行队列呢?因为有两个调度类idle、stop,每个CPU只能有一个进程,所以没必要弄个队列,直接关联它们的进程就可以了,就是上面代码中的两个struct task_struct * 类型的指针变量idle、stop。

    2.2 进程唤醒

    进程是怎么被放入运行队列的呢?都是通过进程唤醒来放入的,包括新创建的进程也是。新建唤醒和阻塞唤醒的代码不太一样,下面我们分别来看一下。

    我们先来看一下新建唤醒的代码:
    linux-src/kernel/sched/core.c

    void wake_up_new_task(struct task_struct *p)
    {
    	struct rq_flags rf;
    	struct rq *rq;
    
    	raw_spin_lock_irqsave(&p->pi_lock, rf.flags);
    	WRITE_ONCE(p->__state, TASK_RUNNING);
    
    	p->recent_used_cpu = task_cpu(p);
    	rseq_migrate(p);
    	__set_task_cpu(p, select_task_rq(p, task_cpu(p), WF_FORK));
    
    	rq = __task_rq_lock(p, &rf);
    	update_rq_clock(rq);
    
    	activate_task(rq, p, ENQUEUE_NOCLOCK);
    
    	check_preempt_curr(rq, p, WF_FORK);
    	task_rq_unlock(rq, p, &rf);
    }
    

    在fork中会调用此函数唤醒新创建的进程,把它放入到运行队列中等待被调度。此函数会先调用select_task_rq来选择自己要去哪个CPU的rq上去,然后调用activate_task把进程加入到相应的运行队列上,最后调用check_preempt_curr看一下是否需要抢占,如果需要就触发抢占。select_task_rq的逻辑我们在调度均衡中讲,check_preempt_curr的逻辑我们在下一节的被动调度中讲。

    我们再来看一下阻塞唤醒的代码:
    linux-src/kernel/sched/core.c

    static int
    try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)
    {
    	unsigned long flags;
    	int cpu, success = 0;
    
    	preempt_disable();
    	if (p == current) {
    		goto out;
    	}
    
    	raw_spin_lock_irqsave(&p->pi_lock, flags);
    	if (!ttwu_state_match(p, state, &success))
    		goto unlock;
    
    	if (READ_ONCE(p->on_rq) && ttwu_runnable(p, wake_flags))
    		goto unlock;
    
    	cpu = select_task_rq(p, p->wake_cpu, wake_flags | WF_TTWU);
    	if (task_cpu(p) != cpu) {
    		if (p->in_iowait) {
    			delayacct_blkio_end(p);
    			atomic_dec(&task_rq(p)->nr_iowait);
    		}
    		wake_flags |= WF_MIGRATED;
    		set_task_cpu(p, cpu);
    	}
    
    	ttwu_queue(p, cpu, wake_flags);
    unlock:
    	raw_spin_unlock_irqrestore(&p->pi_lock, flags);
    out:
    	preempt_enable();
    	return success;
    }
    
    int wake_up_process(struct task_struct *p)
    {
    	return try_to_wake_up(p, TASK_NORMAL, 0);
    }
    
    int wake_up_state(struct task_struct *p, unsigned int state)
    {
    	return try_to_wake_up(p, state, 0);
    }
    
    int default_wake_function(wait_queue_entry_t *curr, unsigned mode, int wake_flags,
    			  void *key)
    {
    	WARN_ON_ONCE(IS_ENABLED(CONFIG_SCHED_DEBUG) && wake_flags & ~WF_SYNC);
    	return try_to_wake_up(curr->private, mode, wake_flags);
    }
    

    阻塞唤醒的核心逻辑是try_to_wake_up,但是内核并不是直接用这个函数,而是提供了三个封装函数。wake_up_process是默认的通用的进程唤醒接口,能唤醒TASK_NORMAL状态的进程。TASK_NORMAL就是阻塞状态的进程,包含TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE,前者是前睡眠能被信号唤醒,后者是深睡眠不能被信号唤醒。还有一些特殊状态的进程如被暂停的进程是不能通过wake_up_process来唤醒的,所以内核还提供了接口wake_up_state,可以自己指定唤醒什么状态的进程。还有一个封装函数default_wake_function,它是wait_queue的默认唤醒函数。

    try_to_wake_up函数首先进行一些检测,先检测被唤醒的进程是否为当前进程,如果是的话直接go out。再检测进程的状态是否与state相符合,不符合就不唤醒,再看一下进程是否已经处于唤醒状态了,如果是就没有必要唤醒了。然后调用select_task_rq选择要到哪个CPU的运行队列上去运行,最后调用ttwu_queue把进程放到目标运行队列上去。基本逻辑和wake_up_new_task是一样的。

    2.3 调度时机

    进程放入运行队列之后就等着被调度到CPU上去运行了。但是当前进程正在使用着CPU,它什么时候能把CPU让给其它进程去运行呢?有两种情况:一是当前进程主动让出CPU,这叫主动调度;二是当前进程被动让出CPU,这叫被动调度,也就是进程抢占。

    主动调度:

    主动调度又可以分为自愿性主动调度和非自愿性主动调度。自愿性主动调度是指进程主动调用sched_yield让出CPU,进程本身还会回到运行队列中去等待下次调度。如果运行队列中没有其它进程的话,此进程还会继续运行。非自愿性主动调度是指进程运行时遇到了无法继续运行的情况,只能进行调度让其它进程运行。进程无法继续运行的情况有加锁失败、要读的文件现在不在内存中、进程死亡等。

    下面我们来看一个非自愿性主动调度的例子,信号量获取失败时的操作:
    linux-src/kernel/locking/semaphore.c

    static inline int __sched __down_common(struct semaphore *sem, long state, long timeout)
    {
    	struct semaphore_waiter waiter;
    
    	list_add_tail(&waiter.list, &sem->wait_list);
    	waiter.task = current;
    	waiter.up = false;
    
    	for (;;) {
    		if (signal_pending_state(state, current))
    			goto interrupted;
    		if (unlikely(timeout <= 0))
    			goto timed_out;
    		__set_current_state(state);
    		raw_spin_unlock_irq(&sem->lock);
    		timeout = schedule_timeout(timeout);
    		raw_spin_lock_irq(&sem->lock);
    		if (waiter.up)
    			return 0;
    	}
    
     timed_out:
    	list_del(&waiter.list);
    	return -ETIME;
    
     interrupted:
    	list_del(&waiter.list);
    	return -EINTR;
    }
    

    先定义一个等待项,把自己加入到信号量的等待列表中,然后调用schedule_timeout执行调度。schedule_timeout和普通的调度函数schedule的区别是:schedule只能等着被具体的事件唤醒,schedule_timeout可以被事件唤醒,如果事件在规定的时间没有到来就会被定时器超时唤醒。

    被动调度:

    如果进程自己不调用sched_yield,也不调用任何会阻塞的函数,那么进程岂不是就可以一直霸占着CPU了。所以内核还提供了被动调度,强制进行进程调度,避免一个进程长时间霸占CPU。被动调度是被动的,不能由进程主动去调度,所以被动调度和主动调度的模式差别很大。被动调度的过程分为两步:触发调度和执行调度。触发调度仅仅是做个标记,告诉系统需要调度了。执行调度是系统会在某些特定的点去检查调度标记,如果被设置的话就执行调度。触发调度的点有: 定时器中断、唤醒进程时、迁移进程时、改变进程优先级时。执行调度的点有:从系统调用返回用户空间、从中断返回用户空间、从中断返回内核、禁用抢占临界区结束、禁用软中断临界区结束、cond_resched调用点。

    定时器中断是保证抢占式多任务能实现的关键。因为其它被动调度的触发点是不确定的,只有定时器中断是确定的周期性的,因此定时器中断也被叫做调度tick。定时器中断的频率是个kconfig选项,可选的值有100、250、300、1000。默认选项是250,也就是说每4ms就会有一个定时器中断,这样就能保证被动调度的及时性,不会有进程过长的占用CPU。关于Linux时间管理与调度tick请参看《深入理解Linux时间子系统》

    下面我们来看一下调度tick的流程:
    linux-src/kernel/sched/core.c

    void scheduler_tick(void)
    {
    	int cpu = smp_processor_id();
    	struct rq *rq = cpu_rq(cpu);
    	struct task_struct *curr = rq->curr;
    
    	curr->sched_class->task_tick(rq, curr, 0);
    
    #ifdef CONFIG_SMP
    	rq->idle_balance = idle_cpu(cpu);
    	trigger_load_balance(rq);
    #endif
    }
    

    在低精度定时器、高精度定时器与固定tick、动态tick的不同组合下,定时器中断触发的方式是不同的,但是最终都会调用scheduler_tick。scheduler_tick会调用当前进程的调度类的task_tick函数,此函数根据具体的情况可能会触发调度。task_tick函数的实现细节我们在具体的调度算法中再讲。

    唤醒进程有新建唤醒和阻塞唤醒,它们都有可能触发调度。我们来看一下:
    linux-src/kernel/sched/core.c

    void wake_up_new_task(struct task_struct *p)
    {
    	struct rq_flags rf;
    	struct rq *rq;
    
    	__set_task_cpu(p, select_task_rq(p, task_cpu(p), WF_FORK));
    	activate_task(rq, p, ENQUEUE_NOCLOCK);
    	check_preempt_curr(rq, p, WF_FORK);
    }
    
    static int
    try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)
    {
    	unsigned long flags;
    	int cpu, success = 0;
    
    	cpu = select_task_rq(p, p->wake_cpu, wake_flags | WF_TTWU);
    	if (task_cpu(p) != cpu) {
    			set_task_cpu(p, cpu);
    	}
    	ttwu_queue(p, cpu, wake_flags);
    	return success;
    }
    
    static void ttwu_queue(struct task_struct *p, int cpu, int wake_flags)
    {
    	struct rq *rq = cpu_rq(cpu);
    	struct rq_flags rf;
    
    	ttwu_do_activate(rq, p, wake_flags, &rf);
    }
    
    static void
    ttwu_do_activate(struct rq *rq, struct task_struct *p, int wake_flags,
    		 struct rq_flags *rf)
    {
    	int en_flags = ENQUEUE_WAKEUP | ENQUEUE_NOCLOCK;
    
    	activate_task(rq, p, en_flags);
    	ttwu_do_wakeup(rq, p, wake_flags, rf);
    }
    
    static void ttwu_do_wakeup(struct rq *rq, struct task_struct *p, int wake_flags,
    			   struct rq_flags *rf)
    {
    	check_preempt_curr(rq, p, wake_flags);
    	WRITE_ONCE(p->__state, TASK_RUNNING);
    }
    
    void check_preempt_curr(struct rq *rq, struct task_struct *p, int flags)
    {
    	if (p->sched_class == rq->curr->sched_class)
    		rq->curr->sched_class->check_preempt_curr(rq, p, flags);
    	else if (p->sched_class > rq->curr->sched_class)
    		resched_curr(rq);
    }
    
    void resched_curr(struct rq *rq)
    {
    	struct task_struct *curr = rq->curr;
    	int cpu;
    
    	cpu = cpu_of(rq);
    
    	if (cpu == smp_processor_id()) {
    		set_tsk_need_resched(curr);
    		set_preempt_need_resched();
    		return;
    	}
    }
    

    linux-src/include/linux/sched.h

    static inline void set_tsk_need_resched(struct task_struct *tsk)
    {
    	set_tsk_thread_flag(tsk,TIF_NEED_RESCHED);
    }
    
    static inline void set_tsk_thread_flag(struct task_struct *tsk, int flag)
    {
    	set_ti_thread_flag(task_thread_info(tsk), flag);
    }
    

    可以看到无论是新建唤醒还是阻塞唤醒,最终都是调用check_preempt_curr函数来处理的。如果被唤醒的进程和当前进程是同一个调度类的则会调用调度类的函数来处理,这个逻辑我们在具体调度类中再讲。如果被唤醒的进程比当前进程的调度类高,则会触发调度。resched_curr函数最终会在thread_info的flag中设置TIF_NEED_RESCHED标记。

    下面我们再来看一下执行调度的点,以x86为例。

    系统调用返回用户空间:
    linux-src/arch/x86/entry/common.c

    __visible noinstr void do_syscall_64(struct pt_regs *regs, int nr)
    {
    	nr = syscall_enter_from_user_mode(regs, nr);
    	if (!do_syscall_x64(regs, nr) && !do_syscall_x32(regs, nr) && nr != -1) {
    		/* Invalid system call, but still a system call. */
    		regs->ax = __x64_sys_ni_syscall(regs);
    	}
    	syscall_exit_to_user_mode(regs);
    }
    
    static noinstr bool __do_fast_syscall_32(struct pt_regs *regs)
    {
    	int nr = syscall_32_enter(regs);
    	int res;
    
    	syscall_enter_from_user_mode_prepare(regs);
    	do_syscall_32_irqs_on(regs, nr);
    	syscall_exit_to_user_mode(regs);
    	return true;
    }
    
    __visible noinstr void do_int80_syscall_32(struct pt_regs *regs)
    {
    	int nr = syscall_32_enter(regs);
    
    	nr = syscall_enter_from_user_mode(regs, nr);
    	do_syscall_32_irqs_on(regs, nr);
    	syscall_exit_to_user_mode(regs);
    }
    

    linux-src/kernel/entry/common.c

    __visible noinstr void syscall_exit_to_user_mode(struct pt_regs *regs)
    {
    	instrumentation_begin();
    	__syscall_exit_to_user_mode_work(regs);
    	instrumentation_end();
    	__exit_to_user_mode();
    }
    
    static __always_inline void __syscall_exit_to_user_mode_work(struct pt_regs *regs)
    {
    	syscall_exit_to_user_mode_prepare(regs);
    	local_irq_disable_exit_to_user();
    	exit_to_user_mode_prepare(regs);
    }
    
    static void exit_to_user_mode_prepare(struct pt_regs *regs)
    {
    	unsigned long ti_work = READ_ONCE(current_thread_info()->flags);
    
    
    	if (unlikely(ti_work & EXIT_TO_USER_MODE_WORK))
    		ti_work = exit_to_user_mode_loop(regs, ti_work);
    }
    
    static unsigned long exit_to_user_mode_loop(struct pt_regs *regs,
    					    unsigned long ti_work)
    {
    	while (ti_work & EXIT_TO_USER_MODE_WORK) {
    		if (ti_work & _TIF_NEED_RESCHED)
    			schedule();
    		if (ti_work & (_TIF_SIGPENDING | _TIF_NOTIFY_SIGNAL))
    			handle_signal_work(regs, ti_work);
    		ti_work = READ_ONCE(current_thread_info()->flags);
    	}
    
    	return ti_work;
    }
    

    可以看到系统调用完成之后返回用户空间之前会检测thread_info flag中的_TIF_NEED_RESCHED,如果设置了就会执行调度。关于系统调用请参看《深入理解Linux系统调用》

    中断返回用户空间或者内核空间:
    linux-src/arch/x86/include/asm/idtentry.h

    #define DEFINE_IDTENTRY_IRQ(func)					\
    static void __##func(struct pt_regs *regs, u32 vector);			\
    									\
    __visible noinstr void func(struct pt_regs *regs,			\
    			    unsigned long error_code)			\
    {									\
    	irqentry_state_t state = irqentry_enter(regs);			\
    	u32 vector = (u32)(u8)error_code;				\
    									\
    	instrumentation_begin();					\
    	kvm_set_cpu_l1tf_flush_l1d();					\
    	run_irq_on_irqstack_cond(__##func, regs, vector);		\
    	instrumentation_end();						\
    	irqentry_exit(regs, state);					\
    }
    
    #define DEFINE_IDTENTRY(func)						\
    static __always_inline void __##func(struct pt_regs *regs);		\
    									\
    __visible noinstr void func(struct pt_regs *regs)			\
    {									\
    	irqentry_state_t state = irqentry_enter(regs);			\
    									\
    	instrumentation_begin();					\
    	__##func (regs);						\
    	instrumentation_end();						\
    	irqentry_exit(regs, state);					\
    }
    

    linux-src/kernel/entry/common.c

    noinstr void irqentry_exit(struct pt_regs *regs, irqentry_state_t state)
    {
    	if (user_mode(regs)) {
    		irqentry_exit_to_user_mode(regs);
    	} else if (!regs_irqs_disabled(regs)) {
    		if (IS_ENABLED(CONFIG_PREEMPTION)) {
    			irqentry_exit_cond_resched();
    		}
    	} else {
    		if (state.exit_rcu)
    			rcu_irq_exit();
    	}
    }
    
    noinstr void irqentry_exit_to_user_mode(struct pt_regs *regs)
    {
    	instrumentation_begin();
    	exit_to_user_mode_prepare(regs);
    	instrumentation_end();
    	__exit_to_user_mode();
    }
    
    static void exit_to_user_mode_prepare(struct pt_regs *regs)
    {
    	unsigned long ti_work = READ_ONCE(current_thread_info()->flags);
    
    
    	if (unlikely(ti_work & EXIT_TO_USER_MODE_WORK))
    		ti_work = exit_to_user_mode_loop(regs, ti_work);
    }
    
    static unsigned long exit_to_user_mode_loop(struct pt_regs *regs,
    					    unsigned long ti_work)
    {
    	while (ti_work & EXIT_TO_USER_MODE_WORK) {
    		if (ti_work & _TIF_NEED_RESCHED)
    			schedule();
    		if (ti_work & (_TIF_SIGPENDING | _TIF_NOTIFY_SIGNAL))
    			handle_signal_work(regs, ti_work);
    		ti_work = READ_ONCE(current_thread_info()->flags);
    	}
    
    	return ti_work;
    }
    
    void irqentry_exit_cond_resched(void)
    {
    	if (!preempt_count()) {
    		if (need_resched())
    			preempt_schedule_irq();
    	}
    }
    

    关于中断的原理请参看《深入理解Linux中断机制》。所有中断和异常的入口函数都是通过DEFINE_IDTENTRY_IRQ或DEFINE_IDTENTRY(还有其它一些类似的宏)来定义的,其中一定会调用irqentry_exit。irqentry_exit又会根据寄存器状态来判断是返回到用户空间还是内核空间。如果是返回到用户空间则会调用irqentry_exit_to_user_mode,此函数的操作和从系统调用返回用户空间是相似的,就不再赘述了。如果是返回到内核空间则会调用irqentry_exit_cond_resched,调用此函数会先检测是否配置了CONFIG_PREEMPTION,没配置就不调用。CONFIG_PREEMPTION代表的是内核抢占,在有些场景中会说成抢占,但是要明白其代表的是内核抢占。

    内核有时候为了同步,需要临时禁用抢占,这个禁用的是内核抢占,因为用户抢占永远可以。当代码配置了内核抢占时才有效。禁用抢占有引用计数,释放最后一个引用时才会重新开启内核抢占。禁用抢占和开启抢占分别用宏preempt_disable和preempt_enable。preempt_enable代表临界区的结束,会去检测是否需要调度。

    禁用抢占临界区结束:
    linux-src/include/linux/preempt.h

    #define preempt_disable() \
    do { \
    	preempt_count_inc(); \
    	barrier(); \
    } while (0)
    
    #define preempt_enable() \
    do { \
    	barrier(); \
    	if (unlikely(preempt_count_dec_and_test())) \
    		__preempt_schedule(); \
    } while (0)
    

    preempt_disable增加引用计数,preempt_enable减少引用计数并检测是否为0,如果为0则执行调度。

    禁用软中断临界区结束:
    linux-src/include/linux/bottom_half.h

    static inline void local_bh_enable(void)
    {
    	__local_bh_enable_ip(_THIS_IP_, SOFTIRQ_DISABLE_OFFSET);
    }
    

    linux-src/kernel/softirq.c

    void __local_bh_enable_ip(unsigned long ip, unsigned int cnt)
    {
    	WARN_ON_ONCE(in_irq());
    
    	if (unlikely(!in_interrupt() && local_softirq_pending())) {
    		/*
    		 * Run softirq if any pending. And do it in its own stack
    		 * as we may be calling this deep in a task call stack already.
    		 */
    		do_softirq();
    	}
    
    	preempt_count_dec();
    
    	preempt_check_resched();
    }
    

    linux-src/include/linux/preempt.h

    #define preempt_check_resched() \
    do { \
    	if (should_resched(0)) \
    		__preempt_schedule(); \
    } while (0)
    

    在禁用软中断的过程中有可能其它地方已经触发了调度,因此在重新开启软中断的时候检测一下是否需要调度。

    cond_resched调用点:
    linux-src/include/linux/sched.h

    #define cond_resched() ({			\
    	___might_sleep(__FILE__, __LINE__, 0);	\
    	_cond_resched();			\
    })
    
    static inline int _cond_resched(void)
    {
    	return __cond_resched();
    }
    

    linux-src/kernel/sched/core.c

    int __sched __cond_resched(void)
    {
    	if (should_resched(0)) {
    		preempt_schedule_common();
    		return 1;
    	}
    
    	return 0;
    }
    

    在很多比较耗时的内核操作中都会加上cond_resched调用,用来增加抢占调度的检测点,提高系统的响应性。

    2.4 调度流程

    前面讲了这么多触发调度的时机,现在该执行调度了。执行调度的总体逻辑是很简单的,就两个步骤:选择进程和切换进程。选择进程是一个很麻烦的过程,牵涉到调度类和调度算法,这个在下一节中讲。切换进程虽然不太麻烦,但是还是比较难以理解的,这个在2.7节中讲。执行调度的入口函数是__schedule,无论是从什么途径执行的调度,最终都要调用这个函数。

    下面我们来看一下它的代码:
    linux-src/kernel/sched/core.c

    static void __sched notrace __schedule(unsigned int sched_mode)
    {
    	struct task_struct *prev, *next;
    	struct rq_flags rf;
    	struct rq *rq;
    	int cpu;
    
    	cpu = smp_processor_id();
    	rq = cpu_rq(cpu);
    	prev = rq->curr;
    
    	next = pick_next_task(rq, prev, &rf);
    
    	if (likely(prev != next)) {
    		rq = context_switch(rq, prev, next, &rf);
    	} else {
    		__balance_callbacks(rq);
    	}
    }
    

    代码经过删减,只留下了关键操作。首先是pick_next_task,选择下一个要执行的进程。然后是context_switch,切换进程。

    2.5 调度算法

    这节要讲的是pick_next_task,在讲之前我们要先讲一些概念逻辑。

    内核中有调度类、调度策略、调度算法的概念,这三者是什么意思,又有什么关系呢?调度类代表的是进程对调度器的需求,主要是对调度紧迫性的需求。调度策略是调度类的子类,是对调度类的细分,是在同一个调度需求下的细微区别。调度算法是对调度类的实现,一个调度类一个调度算法。同一个调度类的调度策略是有很强的相似性的,所以在同一个算法中实现,对于它们不同的部分,算法再去进行区分。下面我们画个图来看一下Linux中的所有调度类、调度策略和调度算法。
    在这里插入图片描述
    Linux中一共有五个调度类,分别是stop(禁令调度类)、deadline(限时调度类)、realtime(实时调度类)、time-share(分时调度类)、idle(闲时调度类)。它们的调度紧迫性从上到下,依次降低。其中禁令调度类和闲时调度类有特殊的目的,仅用于内核,没有调度策略,由于这类进程在内核启动时就设置好了,一个CPU一个相应的进程,所以也不需要调度算法。另外三个调度类可用于用户空间进程,有相应的调度策略和调度算法,也有相应的API供用户空间来设置一个进程的调度策略和优先级。调度类之间的关系是有高类的进程可运行的情况下,绝对不会去调度低类的进程,只有当高类无Runnable的进程的时候才会去调度低类的进程。这里面也有一个例外就是内核为了防止实时进程饿死普通进程,提供了一个配置参数,默认值是实时进程如果已经占用了95%的CPU时间,就会把剩余5%的CPU时间分给普通进程。

    禁令调度类是内核用来执行一些特别紧急的事物所使用的。禁令调度类的进程是内核在启动时就创建好的,一个CPU一个进程,名字叫做[migration/n],n是CPU_ID,之后就不能再创建此类进程了。内核提供了一些接口可以向这些进程push work。调度均衡要迁移线程的时候会用到这类进程,所以它的名字叫做migration。

    linux-src/include/linux/stop_machine.h

    int stop_one_cpu(unsigned int cpu, cpu_stop_fn_t fn, void *arg);
    int stop_two_cpus(unsigned int cpu1, unsigned int cpu2, cpu_stop_fn_t fn, void *arg);
    
    int stop_machine(cpu_stop_fn_t fn, void *data, const struct cpumask *cpus);
    int stop_machine_cpuslocked(cpu_stop_fn_t fn, void *data, const struct cpumask *cpus);
    

    由于禁令调度类的进程优先级是最高的,只要此类进程变得Runnable了,就会立马抢占当前进程来运行,所以这几个接口的名字也都叫做stop_cpu、stop_machine之类的。大家不要望文生义地认为这几个接口能暂定CPU或者关机之类的。

    限时调度类属于硬实时,适用于对调度时间有明确要求的进程。它只有一个调度策略,限时调度策略。一个进程必须通过系统调用才能把自己设置为限时调度策略,并且还要提供三个参数:运行周期、运行时间和截止时间。运行周期是说这个进程在多长时间内想要运行一次,运行时间是说这个进程每次想要运行多长时间,截止时间是说这个进程每次运行结束不能晚于什么时间。这三个参数都需要进程根据自己的实际情况向内核提供,而且不是说你提供了就一定能设置成功,内核还要检测与已有的限时调度类进程是否冲突,如果有冲突那就无法满足,就只能返回设置失败。还有一点是,运行时间是程序员要提供预估好的,如果程序实际运行时间超过了预估时间则会被切走,这可能会导致灾难性的后果。

    实时调度类属于软实时,适用于那些只要可运行就希望立马能执行的进程,比如音视频的解码进程。实时调度类又分为两个调度策略,SCHED_FIFO和SCHED_RR。实时调度类的内部逻辑是让实时优先级大的进程先运行,只要有实时优先级大的进程可运行,就不会去调度实时优先级小的进程。当两个实时进程的优先级相同时,SCHED_RR和SCHED_FIFO这两个策略就有区别了,SCHED_FIFO进程如果抢占了CPU,它就会一直占着CPU,不会给同优先级的实时进程让CPU的,而SCHED_RR进程会在运行了一定的时间片之后主动让给同优先级的实时进程。

    分时调度类是给广大的普通进程来用的,大家共同分享CPU。根据优先级的不同,可能有的进程分的多有的进程分的少,但是不会出现一个进程霸占CPU的情况。分时调度类下面有三个调度策略:SCHED_NORMAL、SCHED_BATCH和SCHED_IDLE。它们的基本思想都是分时,但是略有不同,SCHED_BATCH进程希望减少调度次数,每次调度能执行的时间长一点,SCHED_IDLE是优先级特别低的进程,其分到的CPU时间的比例非常低,但是也总是能保证分到。分时调度类现在的算法叫做CFS(完全公平调度),所以分时调度类也叫做公平调度类。

    闲时调度类是给内核用的,当CPU没有其它进程可以执行的时候就会运行闲时调度类的进程。此类进程是在内核启动时就创建好的,一个CPU一个进程,此后就不能再创建此类进程了。闲时调度类的进程也叫做idle进程,它在内核中有些特殊的用途,比如CPUIdle的实现就和idle进程密切相关。

    大家要注意,闲时调度类和分时调度类中SCHED_IDLE调度策略不是一回事,两者没有关系,大家不要弄混淆了。

    系统为每个调度类都定义了一些标准的操作,我们来看一下:
    linux-src/kernel/sched/sched.h

    struct sched_class {
    	void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
    	void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
    	void (*yield_task)   (struct rq *rq);
    	bool (*yield_to_task)(struct rq *rq, struct task_struct *p);
    
    	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_SMP
    	int (*balance)(struct rq *rq, struct task_struct *prev, struct rq_flags *rf);
    	int  (*select_task_rq)(struct task_struct *p, int task_cpu, int flags);
    
    	struct task_struct * (*pick_task)(struct rq *rq);
    
    	void (*migrate_task_rq)(struct task_struct *p, int new_cpu);
    
    	void (*task_woken)(struct rq *this_rq, struct task_struct *task);
    
    	void (*set_cpus_allowed)(struct task_struct *p,
    				 const struct cpumask *newmask,
    				 u32 flags);
    
    	void (*rq_online)(struct rq *rq);
    	void (*rq_offline)(struct rq *rq);
    
    	struct rq *(*find_lock_rq)(struct task_struct *p, struct rq *rq);
    #endif
    
    	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);
    
    	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);
    };
    

    每个调度类在实现自己的算法的时候都要实现这些函数指针,我们在讲到具体算法时再来讲解这些函数指针的含义。

    下面我们来看一下pick_next_task的代码:
    linux-src/kernel/sched/core.c

    static struct task_struct *
    pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
    {
    	return __pick_next_task(rq, prev, rf);
    }
    
    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;
    
    	/*
    	 * Optimization: we know that if all tasks are in the fair class we can
    	 * call that function directly, but only if the @prev task wasn't of a
    	 * higher scheduling class, because otherwise those lose the
    	 * opportunity to pull in more work from other CPUs.
    	 */
    	if (likely(prev->sched_class <= &fair_sched_class &&
    		   rq->nr_running == rq->cfs.h_nr_running)) {
    
    		p = pick_next_task_fair(rq, prev, rf);
    		if (unlikely(p == RETRY_TASK))
    			goto restart;
    
    		/* Assume the next prioritized class is idle_sched_class */
    		if (!p) {
    			put_prev_task(rq, prev);
    			p = pick_next_task_idle(rq);
    		}
    
    		return p;
    	}
    
    restart:
    	put_prev_task_balance(rq, prev, rf);
    
    	for_each_class(class) {
    		p = class->pick_next_task(rq);
    		if (p)
    			return p;
    	}
    
    	/* The idle class should always have a runnable task: */
    	BUG();
    }
    

    __pick_next_task进行了一个优化,因为大部分时间系统中主要存在的都是普通进程,所以先检测运行队列的运行数量和公平运行列队中的运行数量,如果相等的话就说明系统中目前只有普通进程,那么就可以直接调用pick_next_task_fair。接着就是主逻辑了,先从高调度类进行选择,如果有可运行的进程就直接返回,如果没有就去查询下一个调度类。最后一定能返回一个进程的,因为idle进程总是可运行的。

    每个调度类的具体算法逻辑在后面的章节中讲解。

    2.6 进程优先级

    Linux上一共有5种调度类,其中禁令调度类和闲时调度类只在内核里使用,而且一个CPU只有一个线程,所以用不到进程优先级。限时调度类用的是进程设置的三个调度参数作为调度的依据,也用不到进程优先级。所以就只有实时调度类和分时调度类会用到进程优先级。它们使用优先级的方法也并不相同,我们在讲到具体算法时再讲。

    由于历史原因,实时进程和普通进程的优先级并不是一个简单的数值,而是有好几个数值体系和变换规则,我们先来看一下设置进程调度策略和优先级的API。

    #include <sched.h>
    int sched_setscheduler(pid_t pid, int policy, const struct sched_param *param);
    int sched_getscheduler(pid_t pid);
    
    #include <sched.h>
    int sched_setparam(pid_t pid, const struct sched_param *param);
    int sched_getparam(pid_t pid, struct sched_param *param);
    
    struct sched_param {
        int sched_priority;
    };
    
    #include <unistd.h>
    int nice(int inc);
    

    sched_setscheduler能同时设置实时调度类和分时调度类的调度策略和静态优先级,对于实时调度类,其静态优先级范围是1-99,99最大,对于分时调度类,其静态优先级必须设置为0,其动态优先级也就是nice需要通过nice接口来设置。sched_setparam可以设置实时进程的静态优先级,对于分时进程,其静态优先级必须为0。

    我们再来看一下task_struct中记录优先级的字段。
    linux-src/include/linux/sched.h

    struct task_struct {
    	int				prio;
    	int				static_prio;
    	int				normal_prio;
    	unsigned int			rt_priority;
    }
    

    一共有4个字段,rt_priority用来记录实时进程的用户空间的静态优先级,static_prio用来记录分时进程的用户空间的动态优先级并做了转换。然后rt_priority和static_prio一起转化为normal_prio(规范优先级),此时实时进程和分时进程的优先级就在同一个数轴上了。最终起作用的是prio(动态优先级),它的值默认等于normal_prio,一般不会变动。

    下面我们画图来看一下进程的优先级转换:
    在这里插入图片描述
    在用户空间的时候,实时进程和普通进程(分时进程)共享同一个优先级数轴,叫静态优先级,范围是0-99,值越大优先级越高,实时进程占用1-99,普通进程占用0。普通进程自己又新开了一个数轴,叫动态优先级,也叫nice值,范围是 -20 - 19,值越低优先级越高。

    到了内核空间的时候,实时进程有一个实时优先级,直接复制用户空间的静态优先级,普通进程有一个静态优先级,它是用户空间的nice值转换过来的,转换规则是nice+120。然后内核又定义了规范优先级,把它们都统一到同一个数轴上来。普通进程的规范优先级是直接复制其静态优先级,实时进程的规范优先级等于99减去它的实时优先级。在规范优先级的数轴上,所有进程都可以直接比较优先级了,值越小优先级越大。实时进程的规范优先级范围是0-99,但是由于它是从用户空间的优先级计算而来的,所以99这个值就用不到。

    最后是动态优先级,对进程所有的处理都以动态优先级为准,动态优先级默认等于其规范优先级。以前的时候调度算法会去调整进程的动态优先级,现在不会再调了。现在只有使用了优先级继承锁的时候才会去调整进程的动态优先级。

    下面让我们再画一个图总结一下:
    在这里插入图片描述
    对于禁令调度类、限时调度类和闲时调度类,它们用不到进程优先级,但是系统在规范优先级数轴上为它们提供了象征值,其动态优先级是对规范优先级的复制,也只有象征意义。有一个特殊的情况是分时调度类里面的SCHED_IDLE调度策略的进程,它的优先级无法在规范优先级数轴上体现出来,它的优先级是在CFS算法专门处理的,直接设置的调度权重,相当于是nice 26。

    除了这些复杂的优先级体系之外,ps和top命令下的优先级体系也不相同。

    ps命令优先级:
    在这里插入图片描述
    cls代表的是调度策略,含义如下:

    TS SCHED_OTHER/SCHED_NORMAL
    FF SCHED_FIFO
    RR SCHED_RR
    B SCHED_BATCH
    IDL SCHED_IDLE
    DLN SCHED_DEADLINE

    NI代表的是nice值,范围:-20 – 19,-20最大,只有SCHED_NORMAL和SCHED_BATCH有意义。

    RTPRIO代表的实时进程的用户空间优先级,范围:1 – 99,99最大,只有SCHED_FIFO和SCHED_RR有意义。

    PRI,普通进程 pri = 19 - nice, 实时进程 pri = 40 + rtprio,值越大优先级越大,普通进程 0 – 39, 实时进程 41 – 139。

    top命令优先级:
    在这里插入图片描述
    NI列是nice值,只对普通进程有效,对其它进程来说没有意义。

    PR,普通进程 pr = 20 + nice,实时进程 pr = -1 - rt,rt是实时进程的用户空间优先级,PR值越小优先级越大,普通进程 0 – 39,实时进程 -2 – -100,-100会显示为rt,普通进程大于等于0,实时进程小于0。

    2.7 进程切换

    选择好下一个要执行的进程之后,就该切换进程了。切换进程一共分两步:一是切换用户空间,二是切换内核栈。下面我们来看一下代码(代码经过了高度删减):
    linux-src/kernel/sched/core.c

    static __always_inline struct rq *
    context_switch(struct rq *rq, struct task_struct *prev,
    	       struct task_struct *next, struct rq_flags *rf)
    {
    
    	switch_mm_irqs_off(prev->active_mm, next->mm, next);
    
    	switch_to(prev, next, prev);
    
    	return finish_task_switch(prev);
    }	switch_to(prev, next, prev);
    	barrier();
    
    	return finish_task_switch(prev);
    }
    

    其中switch_mm_irqs_off是切换用户空间的,switch_to是切换内核栈的。

    我们继续看切换用户空间是如何执行的。
    linux-src/arch/x86/mm/tlb.c

    void switch_mm_irqs_off(struct mm_struct *prev, struct mm_struct *next,
    			struct task_struct *tsk)
    {
    	load_new_mm_cr3(next->pgd, new_asid, false);
    }
    
    static void load_new_mm_cr3(pgd_t *pgdir, u16 new_asid, bool need_flush)
    {
    	unsigned long new_mm_cr3;
    
    	if (need_flush) {
    		invalidate_user_asid(new_asid);
    		new_mm_cr3 = build_cr3(pgdir, new_asid);
    	} else {
    		new_mm_cr3 = build_cr3_noflush(pgdir, new_asid);
    	}
    
    	write_cr3(new_mm_cr3);
    }
    

    linux-src/arch/x86/include/asm/special_insns.h

    tatic inline void write_cr3(unsigned long x)
    {
    	native_write_cr3(x);
    }
    
    static inline void native_write_cr3(unsigned long val)
    {
    	asm volatile("mov %0,%%cr3": : "r" (val) : "memory");
    }
    

    切换进程地址空间就是给寄存器CR3赋予新的值。CR3中存放的是根页表的物理地址,build_cr3会把虚拟地址转化为物理地址。关于虚拟内存空间的原理请参看《深入理解Linux内存管理》

    下面我们继续看内核栈是如何切换的。
    linux-src/arch/x86/include/asm/switch_to.h

    #define switch_to(prev, next, last)					\
    do {									\
    	((last) = __switch_to_asm((prev), (next)));			\
    } while (0)
    

    linux-src/arch/x86/entry/entry_64.S

    SYM_FUNC_START(__switch_to_asm)
    	/*
    	 * Save callee-saved registers
    	 * This must match the order in inactive_task_frame
    	 */
    	pushq	%rbp
    	pushq	%rbx
    	pushq	%r12
    	pushq	%r13
    	pushq	%r14
    	pushq	%r15
    
    	/* switch stack */
    	movq	%rsp, TASK_threadsp(%rdi)
    	movq	TASK_threadsp(%rsi), %rsp
    
    #ifdef CONFIG_STACKPROTECTOR
    	movq	TASK_stack_canary(%rsi), %rbx
    	movq	%rbx, PER_CPU_VAR(fixed_percpu_data) + stack_canary_offset
    #endif
    
    #ifdef CONFIG_RETPOLINE
    	/*
    	 * When switching from a shallower to a deeper call stack
    	 * the RSB may either underflow or use entries populated
    	 * with userspace addresses. On CPUs where those concerns
    	 * exist, overwrite the RSB with entries which capture
    	 * speculative execution to prevent attack.
    	 */
    	FILL_RETURN_BUFFER %r12, RSB_CLEAR_LOOPS, X86_FEATURE_RSB_CTXSW
    #endif
    
    	/* restore callee-saved registers */
    	popq	%r15
    	popq	%r14
    	popq	%r13
    	popq	%r12
    	popq	%rbx
    	popq	%rbp
    
    	jmp	__switch_to
    SYM_FUNC_END(__switch_to_asm)
    

    切换内核栈是内核中最难理解的地方之一,难以理解的有两点:一是进程执行是如何切换的;二是switch_to宏为何有三个参数,第三个参数为啥又是prev。

    我们先来解释第一个点,进程执行是如何切换的,先来画个图看一下:
    在这里插入图片描述
    如图中所示一样,每个线程都有一个线程栈,代表线程的执行,CPU只有一个(线程切换前后是同一个CPU)。CPU在哪个线程栈上运行,就是在运行在哪个线程,而线程栈上记录的就是线程的运行信息,所以这个线程就可以继续运行下去了。如果从单个进程的角度来看,从switch_to开始,我们的进程就暂停运行了,我们的进程就一直在这等,等到我们被唤醒并调度执行才会继续走下去。如果从CPU的角度来看,switch_to切换了内核栈,就在新的线程上运行了,函数返回的时候就会按照内核栈的调用地址返回,执行的就是新的代码了,就不是原来的代码了。当内核栈不停地返回,就会返回到用户空间,内核栈的底部记录的有用户空间的调用信息,由于前面已经切换了用户空间,所以程序就能返回到之前用户空间进入内核的地方。

    我们再来说第二点,switch_to宏为啥有三个参数,为啥这么难以理解呢?这是因为switch_to实际上包含了三个进程:一个是我们自己prev,一个是即将要切换的进程next,一个是我们下次是从哪个进程切换过来的,我们把这个进程叫做from。而switch_to通过复用prev变量而把from变量给省略了,这就导致了理解上的混乱。我们来修改一下代码,把switch_to宏给展开,并把prev改名为curr,把from变量也给显式地定义出来,来看看效果怎么样。

    static __always_inline struct rq *
    context_switch(struct rq *rq, struct task_struct *curr,
    	       struct task_struct *next, struct rq_flags *rf)
    {
    	switch_mm_irqs_off(curr->active_mm, next->mm, next);
    
    	struct task_struct *from = NULL;
    	from = __switch_to_asm(curr, next);
    	barrier();
    
    	return finish_task_switch(from);
    }
    

    这下就好理解多了。从单个进程的角度来看,__switch_to_asm会切换到next进程去执行,我们的进程就休眠了。很久以后我们的进程醒来又重新开始执行了,__switch_to_asm返回的是把CPU让给我们的那个进程。从CPU的角度来看__switch_to_asm函数前半程在curr进程运行,后半程在next进程运行。由于切换了内核栈,所以from、curr、next这三个变量也变了,它们是不同栈上的同名的局部变量,它们的内存地址是不一样的。当前进程中的curr值会被作为next进程中的from值返回,所以在next进程中就知道了是从哪里切换过来的了。

    __switch_to_asm中最关键的两句代码我们再拿出来分析一下。
    linux-src/arch/x86/entry/entry_64.S

    	/* switch stack */
    	movq	%rsp, TASK_threadsp(%rdi)
    	movq	TASK_threadsp(%rsi), %rsp
    

    linux-src/include/generated/asm-offsets.h

    #define TASK_threadsp 3160 /* offsetof(struct task_struct, thread.sp) */
    

    每个进程的内核栈的栈指针都在task_struct中的thread.sp保存着,第一个mov语句是把当前进程的栈指针保存起来以备后面使用,第二个mov语句是加载next进程的栈指针,这条指令执行之后就意味着进程切换成功了。后面还有一些语句用来加载之前保存在栈上的寄存器信息。

    如果大家对前面修改的代码感兴趣,想打log验证一下,可以参考下面我加的log。

    static __always_inline struct rq *
    context_switch(struct rq *rq, struct task_struct *curr,
    	       struct task_struct *next, struct rq_flags *rf)
    {
    	switch_mm_irqs_off(curr->active_mm, next->mm, next);
    
    	struct task_struct *from = NULL;
    	if (jiffies % 1000 == 0 && 1 == smp_processor_id()) {
    		pr_err("AAAAAA, -------------------------------------------");
    		pr_err("AAAAAA, start");
    		pr_err("AAAAAA, &curr:%p", &curr);
    		pr_err("AAAAAA, &next:%p", &next);
    		pr_err("AAAAAA, &from:%p", &from);
    		pr_err("AAAAAA,  from:%p", from);
    		pr_err("AAAAAA,  curr:%p, pid:%d, comm:%s", curr, curr->pid, curr->comm);
    		pr_err("AAAAAA,  next:%p, pid:%d, comm:%s", next, next->pid, next->comm);
    		dump_stack();
    		pr_err("AAAAAA, -------------------------------------------");
    	}
    	from = __switch_to_asm(curr, next);
    	barrier();
    	if (jiffies % 1000 == 0 && 1 == smp_processor_id()) {
    		pr_err("AAAAAA, &curr:%p", &curr);
    		pr_err("AAAAAA, &next:%p", &next);
    		pr_err("AAAAAA, &from:%p", &from);
    		pr_err("AAAAAA,  from:%p, pid:%d, comm:%s", from, from->pid, from->comm);
    		pr_err("AAAAAA,  curr:%p, pid:%d, comm:%s", curr, curr->pid, curr->comm);
    		pr_err("AAAAAA,  next:%p, pid:%d, comm:%s", next, next->pid, next->comm);
    		dump_stack();
    		pr_err("AAAAAA, end");
    		pr_err("AAAAAA, -------------------------------------------");
    	}
    
    	return finish_task_switch(from);
    }
    

    这里面有两个技巧,一是使用jiffies % 1000 == 0来减少log的数量,内核中进程切换非常频繁,过多的log往往难以分析,二是使用1 == smp_processor_id()把log锁定在一个CPU上,不然的话多个CPU上的切换log会相互干扰,难以理清,我们只看一个CPU上的log,就会发现逻辑很清晰。

    下面我画了一个图模拟了一下单个CPU上的三个进程之间的切换,大家来看一下:
    在这里插入图片描述
    有三个进程pid 分别为1、3、5在CPU0上进行切换,切换顺序是1->3->5->1->5->3->1。图中是按照我修改之后的代码来画的,有from、curr、next三个指针变量。可以看到一个进程它必须先切走才能切回,因为不切走怎么能切回来呢。但是对于刚创建的进程它是没有切走过的,于是内核会为它伪造内核栈也就是切点,使得它可以切回。正常的内核栈是__schedule函数调用了__switch_to_asm函数,__switch_to_asm函数还会返回到__schedule函数。伪造的内核栈是仿佛ret_from_fork调用了__switch_to_asm函数,__switch_to_asm函数在返回的时候就会返回到ret_from_fork函数来执行。对于内核线程和普通线程伪造的栈上的数据是不一样的,对于普通线程其rbx寄存器对应的位置是0,对于内核线程其rbx寄存器对应的位置是入口函数的指针,具体来说是kthread。ret_from_fork先调用schedule_tail,然后根据rbx的不同,其为0时说明是普通进程,调用syscall_exit_to_user_mode,不为0时说明是内核线程,调用rbx也就是kthread。kthread函数一般是不会返回的,但是如果其中调用了kernel_execve建立了用户空间也可以返回,返回到ret_from_fork中后会调用syscall_exit_to_user_mode。

    对于这幅图大家可以只看一个进程的执行情况,按照一个进程pid从上往下看就可以了。也可以看整个CPU的执行情况,按照红色箭头的标号顺序来看,注意观察from、curr、next三个值的变化。

    三、SMP管理

    在继续讲解之前,我们先来说一下多CPU管理(这里的CPU是指逻辑CPU,在很多语境中CPU都是默认指的逻辑CPU,物理CPU要特别强调是物理CPU)。最开始的时候计算机都是单CPU的,叫做UP(Uni-Processor),操作系统也只支持UP。后来计算机慢慢发展成了多CPU(包括多物理CPU和多核技术),于是操作系统也要开始支持多CPU。支持多CPU的方式有两种:一种是AMP(Aymmetrical Multi-Processing)非对称多处理器,是指操作系统给每个CPU分配的工作任务不同,比如有的CPU专门运行中断,有的CPU专门运行普通进程,有的CPU专门运行实时进程;另一种是SMP(Symmetrical Multi-Processing),操作系统对待每个CPU的方式都是一样的,并不会把某个CPU拿来专门做啥任务,每个CPU都有可能处理任何类型的任务。由于AMP的性能和适应性都不太好,所以现在流行的操作系统基本都是SMP的。对于SMP这个词来说,在很长的一段时间内,它既是指CPU在逻辑上是对称的(操作系统对待所有CPU的方式是一样的),也指CPU在物理上是对称的(CPU在性能等所有方面都是一样的),因为当时的多CPU技术实现上每个逻辑CPU的性能等各方面都是相同的。但是后来多CPU技术的实现出现了HMP(Heterogeneous Multi-Processing)异构多处理器,也就是大小核技术,不同的逻辑CPU它们的性能并不相同。现在内核同时支持SMP和HMP,因为两者并不矛盾,SMP指的是所有的CPU在逻辑上都是一样的,每个CPU都有可能执行任何类型的任务,HMP指的是不同的CPU它的能力大小不同,能力大的多干活,能力小的少干活。内核选项CONFIG_SMP控制是否开启SMP,如果不开启的话就是UP,系统就只能在一个CPU上运行。内核选项CONFIG_ENERGY_MODEL控制是否开启HMP,开启了之后就可以为不同的设备建立不同的能耗模型,系统在分配任务就会以此为参考决定如何分配任务,达到效率更高或者更省电的目的。

    3.1 CPU拓扑结构

    我们先从发展的角度来看一看CPU的拓扑结构。最早的时候一个物理CPU就是一个逻辑CPU,一个逻辑CPU包含一个控制器、一个运算器和一些寄存器,一个物理CPU包含一个裸芯片(Die)和外面的封装(Package)。然后出现了多物理CPU,也就是一个主板上有多个CPU插槽,这样计算机中就有多个CPU了。后来发现,没必要做多个物理CPU啊,一个物理CPU(Package)包含多个裸芯片(Die)不也是多CPU嘛,省事又方便。后来又发现,多个裸芯片封装在一起也很麻烦啊,直接在一个裸芯片上做多个逻辑CPU不是也可以嘛,更省事。从这之后x86和ARM的CPU做法就不一样了。在x86上是一个裸芯片(Die)包含多个核(Core),一个核(Core)上包含多个SMT(Simultaneous Multithreading),SMT在Intel的文档里叫做HT(Hyper-Threading),SMT是最终的逻辑CPU。在ARM上是一个裸芯片(Die)包含多个核簇(Cluster),一个核簇(Cluster)包含多个核(Core)。

    3.2 CPUMASK

    不同架构的CPU,其逻辑CPU都有一个硬件ID,此ID一般是多个字段的组合。Linux为了方便管理CPU,提出了逻辑CPU的概念,此逻辑CPU的概念是指CPU的ID是逻辑的,从0来编号一直增长的。内核会把第一个启动的CPU作为CPU0,其它CPU的编号依次为CPU1,CPU2,……。内核定义了结构体cpumask来表示各个CPU编号的集合,cpumask是个bitmap,每一个bit可以代表一个CPU的某种状态。内核中定义了五个cpumask变量,用来表示不同状态下的CPU集合。下面我们来看一下:

    linux-src/include/linux/cpumask.h

    typedef struct cpumask { DECLARE_BITMAP(bits, NR_CPUS); } cpumask_t;
    
    extern struct cpumask __cpu_possible_mask;
    extern struct cpumask __cpu_online_mask;
    extern struct cpumask __cpu_present_mask;
    extern struct cpumask __cpu_active_mask;
    extern struct cpumask __cpu_dying_mask;
    #define cpu_possible_mask ((const struct cpumask *)&__cpu_possible_mask)
    #define cpu_online_mask   ((const struct cpumask *)&__cpu_online_mask)
    #define cpu_present_mask  ((const struct cpumask *)&__cpu_present_mask)
    #define cpu_active_mask   ((const struct cpumask *)&__cpu_active_mask)
    #define cpu_dying_mask    ((const struct cpumask *)&__cpu_dying_mask)
    

    linux-src/kernel/cpu.c

    struct cpumask __cpu_possible_mask __read_mostly;
    EXPORT_SYMBOL(__cpu_possible_mask);
    
    struct cpumask __cpu_online_mask __read_mostly;
    EXPORT_SYMBOL(__cpu_online_mask);
    
    struct cpumask __cpu_present_mask __read_mostly;
    EXPORT_SYMBOL(__cpu_present_mask);
    
    struct cpumask __cpu_active_mask __read_mostly;
    EXPORT_SYMBOL(__cpu_active_mask);
    
    struct cpumask __cpu_dying_mask __read_mostly;
    EXPORT_SYMBOL(__cpu_dying_mask);
    

    cpu_possible_mask代表的是操作系统最多能支持的CPU,cpu_present_mask代表的是计算机上存在的CPU,cpu_online_mask代表的是已经上线的CPU,cpu_active_mask代表的是未被隔离可以参与调度的CPU,cpu_dying_mask代表的是处于热下线过程中的CPU。

    3.3 CPU热插拔

    CPU热插拔会影响调度均衡可用的CPU。

    内容暂略

    3.4 CPU隔离

    CPU隔离会影响调度均衡可用的CPU。

    内容暂略

    四、基本分时调度

    Linux上的分时调度算法叫CFS(Completely Fair Scheduler)完全公平调度。它是内核核心开发者Ingo Molnar基于SD调度器和RSDL调度器的公平调度思想而开发的一款调度器,在版本2.6.23中合入内核。CFS只负责调度普通进程,包括三个调度策略NORMAL、BATCH、IDLE。

    我们这章只讲单个CPU上的调度,多CPU之间的调度均衡在下一章讲。

    4.1 CFS调度模型

    内核文档对CFS的定义是:CFS在真实的硬件上基本模拟了完全理想的多任务处理器。完全理想的多任务处理器是指,如果把CPU的执行能力看成是100%,则N个进程可以同时并行执行,每个进程获得了1/N的CPU执行能力。例如有2个进程在2GHz的CPU上执行了20ms,则每个进程都以1GHz的速度执行了20ms。

    通过CFS的定义很难理解CFS的操作逻辑是什么。我看了很多CFS的博客,也认真看了很多遍CFS的代码,虽然自己心里明白了其中的意思,但是想要给别人说清楚CFS的操作逻辑还是很难。后来我灵光乍现,突然想到了一个很好的类比场景,把这个场景稍微改造一下,就可以打造一个非常完美的CFS调度模型,可以让任何人都能理解CFS的操作逻辑。大家有没有这种生活体验,夏天的时候三四个好友一起去撸串,吃完准备走的时候发现有一瓶啤酒打开了还没喝。此时我们会把这瓶啤酒平分了,具体怎么分呢,比如三个人分,你不可能一次分完,每个杯子正好倒三分之一。我们一般会每个杯子先倒个差不多,然后再把剩余的啤酒来回往各个杯子里面倒,这样啤酒就会分的比较均匀了。也许你没经历过这样的场景,或者认为啤酒随便分就可以了,没必要分那么细。接下来还有一个场景更生动。你有没有经历过或者见过长辈们喝白酒划拳的,此时一般都会拿出5到10个小酒盅,先把每个酒盅都倒个差不多,然后再来回地往各个酒盅里面倒一点,还会去比较酒盅液面的高低,优先往液面低的杯子里面倒。如果你见过或者经历过这种场景,那么接下来的模型就很好理解了。

    我们对倒白酒的这个场景进行改造,把它变成一个实验台。首先把酒盅变成细长(而且非常长)的玻璃杯,再把倒白酒的瓶子变成水龙头,能无限出水的水龙头,有一个桌子可以用来摆放所有的玻璃杯。我们一次只能拿着一个玻璃杯放到水龙头下接水。然后向你提出了第一个要求,在任意时刻所有的玻璃杯的水位高度都要相同或者尽量相同,越接近越好。此时你会怎么办,肯定是不停地切换玻璃杯啊,越快越好,一个玻璃杯接一滴水就立马换下一个。但是这立马会迎来第二个问题,切换玻璃杯的过程水龙头的水会流到地上,过于频繁的切换玻璃杯会浪费大量的水。向你提出的第二个要求就是要尽量地少浪费水,你该怎么办,那肯定是减少玻璃杯的切换啊。但是减少玻璃杯的切换又会使得不同玻璃杯的水位差变大,这真是一个两难的选择。对此我们只能进行折中,切换玻璃杯的频率不能太大也不能太小,太大浪费水,太小容易水位不均。

    我们继续对这个模型进行完善。为了减少水位差我们每次都要去拿水位最低的,怎么能最快的时间拿到最低的玻璃杯呢,肯定是把水杯按照从高到底的顺序排列好,我们直接去拿第一个就好了。玻璃杯代表的是进程,不同进程的优先级不同,分到的CPU时间片也不同,为此我们让不同的玻璃杯有不同的粗细,这样比较粗的玻璃杯就能分到更多的水,因为我们在尽量保证它们的水位相同,横截面积大的玻璃杯就会占优势。进程有就绪、阻塞、运行等状态,为此我们在玻璃杯上面加个盖子,盖子有时候是打开的,有时候是关闭的。盖子关闭的时候玻璃杯是没法接水的,因此我们把它放到一边,直到有人把它的盖子打开我们再把它放到桌子上。

    说到这里,大家在脑海里对这个模型应该已经有个大概的轮廓了,下面我们画图来看一下:
    在这里插入图片描述
    我们继续讲解这个图。我们每次都是从队首拿过来一个玻璃杯开始接水。在接水的过程中有两种情况可能会发生:一是一直接水直到此次接水的份额已经满了,我们把这个玻璃杯再放回到队列中去,由于此时玻璃杯刚接了不少水,水位比较高,所以会排的比较靠后;二是接水的过程中,瓶盖突然关闭了,这时就没法再接水了,我们把玻璃杯送到某个Wait Box中去,等待某个事件的发生。某个事件发生之后会把对应的Wait Box中的一个或者多个玻璃杯的瓶盖打开,然后此玻璃杯就会被送到Ready Table上。玻璃杯被送到Ready Table并不是随便一放就行了,也是要参与排序的。大家从图中可以看到,Wait Box中的玻璃杯的水位都比较低,这是因为Ready Table上的玻璃杯一直在接水,水位肯定会涨的很高,相应的Wait Box中的水位就低了。因此WaitBox中的玻璃杯被唤醒放到ReadyTable上基本都能排第一,这也是好事,让休眠时间长的进程能迅速得到执行。但是这里面也存在一个问题,就是刚开盖的玻璃杯水位太低了,它就能一直得到执行,这对其它玻璃杯来说是不公平的。因此ReadyTable上放了一个最低水位记录,刚开盖的玻璃瓶如果水位比这个值低,我们就往这个玻璃瓶中填充泡沫,使得它的水位看起来和这个最低水位记录一样高。这样新开盖的玻璃杯既能优先接水,又不能过分占便宜,非常好。最低水位记录的值也会一直更新的,正在接水的玻璃杯每次离开的时候都会更新一下这个最低水位记录。

    现在我们对这个玻璃杯接水模型的逻辑已经非常清楚了,下面我们一步一步把它和CFS的代码对应起来,你会发现契合度非常高。

    4.2 CFS运行队列

    所有的就绪进程都要在ReadyTable上按照水位高低排成一排,那么这个队列用什么数据结构来实现呢?先想一下这个队列都有什么需求,首先这个队列是排序的,其次我们经常对这个队列进程插入和删除操作。因此我们可以想到用红黑树来实现,因为红黑树首先是一颗二叉搜索树,是排序的,其次红黑树是平衡的,其插入和删除操作的效率都是O(logn),非常高效。所以CFS的运行队列就是用红黑树来实现的。关于红黑树的原理,请参看《深入理解红黑树》

    下面我们来看一下CFS运行队列的代码:
    linux-src/kernel/sched/sched.h

    struct cfs_rq {
    	struct load_weight	load;
    	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;
    
    	struct rb_root_cached	tasks_timeline;
    
    	struct sched_entity	*curr;
    	struct sched_entity	*next;
    	struct sched_entity	*last;
    	struct sched_entity	*skip;
    
    
    #ifdef CONFIG_SMP
    	struct sched_avg	avg;
    	struct {
    		raw_spinlock_t	lock ____cacheline_aligned;
    		int		nr;
    		unsigned long	load_avg;
    		unsigned long	util_avg;
    		unsigned long	runnable_avg;
    	} removed;
    #endif /* CONFIG_SMP */
    };
    

    字段tasks_timeline就是所有分时进程所排队的队列,类型rb_root_cached就是内核中红黑树的实现,curr就是当前正在CPU上运行的进程。还有一些其它字段我们在讲到时再进行解说。进程在红黑树中排队的键值是虚拟运行时间vruntime,这个在4.5节中讲解。

    4.3 进程状态表示

    我们知道进程在运行的时候一直是在阻塞、就绪、执行三个状态来回转换,如下图所示:
    在这里插入图片描述
    但是Linux中对进程运行状态的定义却和标准的操作系统理论不同。

    Linux中的定义如下(删减了一些状态):
    linux-src/include/linux/sched.h

    /* Used in tsk->state: */
    #define TASK_RUNNING			0x0000
    #define TASK_INTERRUPTIBLE		0x0001
    #define TASK_UNINTERRUPTIBLE		0x0002
    #define TASK_DEAD			0x0080
    #define TASK_NEW			0x0800
    

    在Linux中就绪和执行都用TASK_RUNNING来表示,这让人很疑惑。但是用我们的模型图来看,这一点却很好理解,因为就绪和执行它们都是开盖的,状态一样,区别它们的方法是玻璃杯放置的位置,是放在桌子上还是放在水龙头下,而Linux中也是利用这一点来判断的。如下代码所示:

    linux-src/include/linux/sched.h

    #define task_is_running(task)		(READ_ONCE((task)->__state) == TASK_RUNNING)
    

    linux-src/kernel/sched/sched.h

    static inline long se_runnable(struct sched_entity *se)
    {
    	return !!se->on_rq;
    }
    
    static inline int task_running(struct rq *rq, struct task_struct *p)
    {
    #ifdef CONFIG_SMP
    	return p->on_cpu;
    #else
    	return task_current(rq, p);
    #endif
    }
    
    
    static inline int task_current(struct rq *rq, struct task_struct *p)
    {
    	return rq->curr == p;
    }
    

    task_is_running判断的是进程的状态字段是否等于TASK_RUNNING,代表进程处于就绪或者执行态。如何区分进程到底是处于就绪态还是运行态呢?se_runnable通过字段on_rq判断进程是否处于就绪态,task_running通过字段on_cpu判断进程是否处于运行态。对应起来就是:敞口的玻璃杯通过其位置是在桌子上还是在水龙头下来区分其是否正在接水,TASK_RUNNING状态的进程通过判断其是on_rq还是on_cpu来区分就绪和运行。

    表示进程处于阻塞态的状态有两个:TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE。TASK_UNINTERRUPTIBLE表示只有WaitBox对应的事件能把玻璃杯的盖子打开,其它人谁也打不开。TASK_INTERRUPTIBLE表示除了WaitBox对应的事件之外,信号(signal)也能把盖子打开。关于信号请参看《深入理解Linux信号机制》

    4.4 优先级与权重

    我们在前面讲过进程的优先级,这里只讲分时进程的优先级。优先级是如何影响进程获得CPU时间的多少呢?优先级会转化为进程的权重,进程的权重也就是玻璃杯的粗细。横截面积大的玻璃杯,接收同样容积的水,它的水位增加就比较小,就容易排到队列的前面去,就比较容易获得调度。在一段时间后,所有玻璃杯的水位高度都比较接近,同样的水位高度,横截面积大的玻璃杯装的水就多,也就是进程获得的CPU时间比较多。

    进程(线程)的相关信息是记录在task_struct中的,内核又把和分时调度相关的一些信息抽出来组成了结构体sched_entity,然后把sched_entity内嵌到task_struct当中,sched_entity中包含有权重信息的记录。下面我们来看一下。
    linux-src/include/linux/sched.h

    struct task_struct {
    	struct sched_entity		se;
    }
    
    struct sched_entity {
    	/* For load-balancing: */
    	struct load_weight		load;
    	struct rb_node			run_node;
    	struct list_head		group_node;
    	unsigned int			on_rq;
    
    	u64				exec_start;
    	u64				sum_exec_runtime;
    	u64				vruntime;
    	u64				prev_sum_exec_runtime;
    
    	u64				nr_migrations;
    
    	struct sched_statistics		statistics;
    
    #ifdef CONFIG_FAIR_GROUP_SCHED
    	int				depth;
    	struct sched_entity		*parent;
    	/* rq on which this entity is (to be) queued: */
    	struct cfs_rq			*cfs_rq;
    	/* rq "owned" by this entity/group: */
    	struct cfs_rq			*my_q;
    	/* cached value of my_q->h_nr_running */
    	unsigned long			runnable_weight;
    #endif
    
    #ifdef CONFIG_SMP
    	/*
    	 * Per entity load average tracking.
    	 *
    	 * Put into separate cache line so it does not
    	 * collide with read-mostly values above.
    	 */
    	struct sched_avg		avg;
    #endif
    };
    
    struct load_weight {
    	unsigned long			weight;
    	u32				inv_weight;
    };
    

    可以看到load_weight中有两个字段:weight和inv_weight。weight代表的是权重,inv_weight是为了方便weight参与除法运算时而添加的,它可以把对weight的除法运算转化为对inv_weight的乘法运算。inv_weight = 232/weight,当需要除以weight的时候,你只需要乘以inv_weight然后再右移32就可以了。inv_weight的值可以提前算出来保存在数组里,右移操作是个效率很高的操作,这样就提高了权重相关的运算效率。下面我们先来看一下weight的值是怎么来的。

    nice值的范围是-20到19,是等差数列,转化之后的权重是等比数列,以nice 0作为权重1024,公比为0.8。之前的调度算法都是把nice值转化为等差数列的时间片或者多段等差数列的时间片,为何CFS要把这个转换变为等比数列呢?这是因为人们天然地对相对值比较敏感而不是对绝对值比较敏感,比如你工资两千的时候涨薪200和工资两万的时候涨薪200,心情绝对是不一样的。如果系统中只有两个进程,nice值分别为0和1,时间片分别为200ms和195ms,几乎没啥区别,但是当nice值分为18和19的时候,时间片分别为10ms和5ms,两者的时间差达到了一倍,同样是nice值相差1,它们的时间差的比例却如此之大,是让人无法接受的。因此把nice值转化为等比数列的权重,再按照权重去分配CPU时间是比较合理的。那么公比为何是0.8呢?这是为了让两个nice值只相差1的进程获得的CPU时间比例差为10%。我们用等式来计算一下,假设x、y是权重,y对应的nice值比x大1,我们希望 x/(x+y) - y/(x+y) = 10%,我们做一下运算,看看y与x的比值是多少。

    x/(x+y) - y/(x+y) = 10%
    (x-y)/(x+y) = 0.1
    x-y = 0.1x + 0.1y
    0.9x = 1.1y
    y/x = 0.9/1.1
    y/x = 0.818181
    y/x ≈ 0.8

    那么为什么把nice 0 作为权重1024来进行转换呢?这是为了二进制运算方便。内核里并不是每次优先级转权重都进行运算,而是提前运算好了放在数组,每次用的时候查一下就可以了。反权重的值也提前计算好了放在了数组里。下面我们来看一下:
    linux-src/kernel/sched/core.c

    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,
    };
    
    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,
    };
    

    Nice值从-20到19一共40个数,一排5个权重值,五八四十正好40个权重值。可以看到权重数列的公比并不是标准的0.8,而是作者以0.8为基准从nice 0开始计算,之后又进行了一些调整,主要是为了方便计算。

    下面我们再来看一下设置进程权重的函数:
    linux-src/kernel/sched/core.c

    static void set_load_weight(struct task_struct *p, bool update_load)
    {
    	int prio = p->static_prio - MAX_RT_PRIO;
    	struct load_weight *load = &p->se.load;
    
    	/*
    	 * SCHED_IDLE tasks get minimal weight:
    	 */
    	if (task_has_idle_policy(p)) {
    		load->weight = scale_load(WEIGHT_IDLEPRIO);
    		load->inv_weight = WMULT_IDLEPRIO;
    		return;
    	}
    
    	/*
    	 * SCHED_OTHER tasks have to update their load when changing their
    	 * weight
    	 */
    	if (update_load && p->sched_class == &fair_sched_class) {
    		reweight_task(p, prio);
    	} else {
    		load->weight = scale_load(sched_prio_to_weight[prio]);
    		load->inv_weight = sched_prio_to_wmult[prio];
    	}
    }
    

    我们先看第一行,prio = p->static_prio - MAX_RT_PRIO,由于static_prio = nice + 120,所以prio = nice + 20,nice的范围是 -20 - 19,所以prio的范围是 0 - 39,正好可以作为sched_prio_to_weight数组的下标。然后代码对SCHED_IDLE调度策略的进程进行了特殊处理,直接设置其权重为3,相当于是nice 26,反权重值也直接进行了设置。SCHED_IDLE进程的权重特别小意味其分到的CPU时间会相当的少,正好符合这个调度策略的本意。scale_load和scale_load_down是对权重进行缩放,在32位系统上它们是空操作,在64位系统上它们是放大1024倍和缩小1024倍,主要是为了在运算时提高精度,不影响权重的逻辑。所以在后文中为了叙述方便,我们直接忽略scale_load和scale_load_down。接着往下看,update_load参数会影响代码的流程,当进程是新fork时update_load为false,会走下面的流程直接设置权重和反权重,当用户空间修改进程优先级时update_load为true,会走上面的流程调用reweight_task,reweight_task也会设置进程的权重,同时也会修改运行队列的权重。

    运行队列的权重等于其上所有进程的权重之和。进程在入队出队时也会相应地从运行队列中加上减去其自身的权重。

    下面我们来看一下代码(经过高度删减):
    linux-src/kernel/sched/fair.c

    static void
    enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)
    {
    	enqueue_entity(cfs_rq, se, flags);
    }
    
    static void
    enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
    {
    	account_entity_enqueue(cfs_rq, se);
    }
    
    static void
    account_entity_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
    {
    	update_load_add(&cfs_rq->load, se->load.weight);
    	cfs_rq->nr_running++;
    }
    
    static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags)
    {
    	dequeue_entity(cfs_rq, se, flags);
    }
    
    static void
    dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
    {
    	account_entity_dequeue(cfs_rq, se);
    }
    
    static void
    account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
    {
    	update_load_sub(&cfs_rq->load, se->load.weight);
    	cfs_rq->nr_running--;
    }
    

    可以看到运行队列的总权重和其进程数量是同步更新的。

    4.5 虚拟运行时间

    我们再来看一下玻璃杯的水位是如果表示的。玻璃杯的水位就是进程的虚拟运行时间,是进程进行排队的键值。玻璃杯的水位等于玻璃杯中水的体积除以玻璃杯的横截面积,进程的虚拟运行时间等于进程的实际运行时间除以相对权重。进程的实际运行时间是一段一段的,所以进程的虚拟运行时间也是一段一段增长的。进程的虚拟运行时间还会在进程入队时与运行队列的最小虚拟时间相比较,如果小的话会直接进行增加,并不对应实际的运行时间。这也就是我们前面说的对玻璃杯进行填充泡沫的操作。相对权重是相对于nice 0的权重,所以nice 0的进程其虚拟运行时间和实际运行时间是一致的。但是这种一致只是某一段时间中的一致,因为虚拟运行时间在进程入队时可能会空跳。在更新进程的真实虚拟运行时间的时候也会去更新运行队列的最小运行时间记录,使得运行队列的最小运行时间也在一直增长着。

    进程的虚拟运行时间保存在task_struct中的sched_entity中的vruntime字段。运行队列的最小虚拟运行时间保证在cfs_rq的min_vruntime字段。下面我们来看一下它们的更新方法。
    linux-src/kernel/sched/fair.c

    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;
    	if (unlikely((s64)delta_exec <= 0))
    		return;
    
    	curr->exec_start = now;
    
    	schedstat_set(curr->statistics.exec_max,
    		      max(delta_exec, curr->statistics.exec_max));
    
    	curr->sum_exec_runtime += delta_exec;
    	schedstat_add(cfs_rq->exec_clock, delta_exec);
    
    	curr->vruntime += calc_delta_fair(delta_exec, curr);
    	update_min_vruntime(cfs_rq);
    
    	if (entity_is_task(curr)) {
    		struct task_struct *curtask = task_of(curr);
    
    		trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);
    		cgroup_account_cputime(curtask, delta_exec);
    		account_group_exec_runtime(curtask, delta_exec);
    	}
    
    	account_cfs_rq_runtime(cfs_rq, delta_exec);
    }
    
    static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
    {
    	if (unlikely(se->load.weight != NICE_0_LOAD))
    		delta = __calc_delta(delta, NICE_0_LOAD, &se->load);
    
    	return delta;
    }
    
    /*
     * delta_exec * weight / lw.weight
     *   OR
     * (delta_exec * (weight * lw->inv_weight)) >> WMULT_SHIFT
     *
     * Either weight := NICE_0_LOAD and lw \e sched_prio_to_wmult[], in which case
     * we're guaranteed shift stays positive because inv_weight is guaranteed to
     * fit 32 bits, and NICE_0_LOAD gives another 10 bits; therefore shift >= 22.
     *
     * Or, weight =< lw.weight (because lw.weight is the runqueue weight), thus
     * weight/lw.weight <= 1, and therefore our shift will also be positive.
     */
    static u64 __calc_delta(u64 delta_exec, unsigned long weight, struct load_weight *lw)
    {
    	u64 fact = scale_load_down(weight);
    	u32 fact_hi = (u32)(fact >> 32);
    	int shift = WMULT_SHIFT;
    	int fs;
    
    	__update_inv_weight(lw);
    
    	if (unlikely(fact_hi)) {
    		fs = fls(fact_hi);
    		shift -= fs;
    		fact >>= fs;
    	}
    
    	fact = mul_u32_u32(fact, lw->inv_weight);
    
    	fact_hi = (u32)(fact >> 32);
    	if (fact_hi) {
    		fs = fls(fact_hi);
    		shift -= fs;
    		fact >>= fs;
    	}
    
    	return mul_u64_u32_shr(delta_exec, fact, shift);
    }
    

    update_curr只能更新运行队列的当前进程,如果进程不在运行,没有实际运行时间就没有对应的虚拟运行时间。函数首先获取了当前时间now,然后用当前时间减去进程此次开始执行的时间exec_start,就得到了进程此次运行的实际时间delta_exec。进程的exec_start是在进程即将获取CPU的时候设置的,具体来说是调度流程中的pick_next_task设置的。然后再通过函数calc_delta_fair把实际运行时间转化为虚拟运行时间,把得到的结果加到进程的vruntime上。calc_delta_fair中对nice 0的进程直接返回实际运行时间,对于其它进程则调用__calc_delta进行运算。__calc_delta使用了一些复杂的数学运算技巧,比较难以理解,但是其逻辑是清晰的,就是虚拟运行时间等于实际运行时间乘以NICE_0_LOAD与进程权重的比值(delta_exec * weight / lw.weight)。接着就是更新运行队列的最小虚拟时间记录了,再往下是一些统计代码就不讲了。我们来看一下最小虚拟时间的更新。
    linux-src/kernel/sched/fair.c

    static void update_min_vruntime(struct cfs_rq *cfs_rq)
    {
    	struct sched_entity *curr = cfs_rq->curr;
    	struct rb_node *leftmost = rb_first_cached(&cfs_rq->tasks_timeline);
    
    	u64 vruntime = cfs_rq->min_vruntime;
    
    	if (curr) {
    		if (curr->on_rq)
    			vruntime = curr->vruntime;
    		else
    			curr = NULL;
    	}
    
    	if (leftmost) { /* non-empty tree */
    		struct sched_entity *se = __node_2_se(leftmost);
    
    		if (!curr)
    			vruntime = se->vruntime;
    		else
    			vruntime = min_vruntime(vruntime, se->vruntime);
    	}
    
    	/* ensure we never gain time by being placed backwards. */
    	cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime);
    #ifndef CONFIG_64BIT
    	smp_wmb();
    	cfs_rq->min_vruntime_copy = cfs_rq->min_vruntime;
    #endif
    }
    

    此代码的逻辑是先在当前进程的vruntime和队首进程的vruntime之间选择一个最小值,如果此值大于原先的min_vruntime,就更新cfs_rq->min_vruntime为此值。

    update_curr的调用时机都有哪些? 下面我们来一一说明一下:

    1.定时器中断,更新当前进程的虚拟运行时间,只有更新了之后才知道当前进程的时间片有没有用完。
    2.唤醒抢占时,也要更新当前进程的虚拟运行时间,只有更新了之后才能正确判断是否能抢占。
    3.进程被抢占离开CPU时,从触发抢占到执行抢占还有一段时间,需要更新一下虚拟运行时间。
    4.进程阻塞离开CPU时,需要更新一下虚拟运行时间。
    5.主动让出CPU时,通过sched_yield让出CPU时更新一下虚拟运行时间。
    6.当前进程更改优先级时,更改优先级会改变权重,对已经运行的时间先更新一下虚拟运行时间。
    7.执行fork时,子进程会继承父进程的vruntime,因此要更新一下父进程的vruntime。
    8.用户空间定时器要统计进程的运行时间时。
    9.调度均衡中迁移线程时入队和出队的队列都要调用update_curr,目的是为了更新min_vruntime,因为被迁移的线程要减去旧队列的min_vruntime,加上新队列的min_vruntime,所以min_vruntime的要是最新的才好。

    4.6 调度周期与粒度

    在以往的调度算法中,都会有明确的调度周期和时间片的概念。比如说以1秒为一个调度周期,把1秒按照进程的优先级分成时间片分给各个进程。进程在运行的过程中时间片不断地减少,当减到0的时候就不再参与调度了。当所有进程的时间片都减到0的时候,再重新开启一个调度周期,重新分配时间片。对于在一个调度周期内突然创建或者唤醒的进程,还要进行特殊的处理。在CFS中,你会发现好像没有调度周期和时间片的概念了,但是又好像有。没有,是因为没有统一分配时间片的地方了,也没有时间片递减的逻辑了。有,是因为代码中还有调度周期和时间片的函数和变量。

    在CFS调度模型中玻璃杯的水位是一直在增长的,没有时间片递减的逻辑,也不存在什么调度周期。但是一个玻璃杯总是不能一直接水的,接水时间长了也是要把切走的。在CFS中玻璃杯一次接水的最大量就叫做时间片。这个时间片和传统的时间片是不一样的,这个时间片是个检测量,没有递减的逻辑。那么时间片是怎么计算的呢?这就和调度周期有关,CFS的调度周期也和传统的调度周期不一样,CFS的调度周期仅仅是一个计算量。调度周期的计算又和调度粒度有关。调度粒度是指玻璃杯一次接水的最小量,也就是进程在CPU上至少要运行多少时间才能被抢占。调度粒度指的是被动调度中进程一次运行最少的时间,如果进程阻塞发生主动调度,不受这个限制。时间片的计算依赖调度周期,调度周期的计算依赖调度粒度,所以我们就先来讲讲调度粒度。

    内核中定义了sysctl_sched_min_granularity,代表调度粒度,默认值是0.75毫秒,但这并不最终使用的值,系统在启动的时候还会对这个变量进行赋值。我们来看一下代码。
    linux-src/kernel/sched/fair.c

    unsigned int sysctl_sched_tunable_scaling = SCHED_TUNABLESCALING_LOG;
    
    unsigned int sysctl_sched_min_granularity			= 750000ULL;
    static unsigned int normalized_sysctl_sched_min_granularity	= 750000ULL;
    
    unsigned int sysctl_sched_latency			= 6000000ULL;
    static unsigned int normalized_sysctl_sched_latency	= 6000000ULL;
    static unsigned int sched_nr_latency = 8;
    
    unsigned int sysctl_sched_wakeup_granularity			= 1000000UL;
    static unsigned int normalized_sysctl_sched_wakeup_granularity	= 1000000UL;
    
    void __init sched_init_granularity(void)
    {
    	update_sysctl();
    }
    
    static void update_sysctl(void)
    {
    	unsigned int factor = get_update_sysctl_factor();
    
    	sysctl_sched_min_granularity = factor * normalized_sysctl_sched_min_granularity;
    	sysctl_sched_latency = factor * normalized_sysctl_sched_latency;
    	sysctl_sched_wakeup_granularity = factor * normalized_sysctl_sched_wakeup_granularity;
    }
    
    static unsigned int get_update_sysctl_factor(void)
    {
    	unsigned int cpus = min_t(unsigned int, num_online_cpus(), 8);
    	unsigned int factor;
    
    	switch (sysctl_sched_tunable_scaling) {
    	case SCHED_TUNABLESCALING_NONE:
    		factor = 1;
    		break;
    	case SCHED_TUNABLESCALING_LINEAR:
    		factor = cpus;
    		break;
    	case SCHED_TUNABLESCALING_LOG:
    	default:
    		factor = 1 + ilog2(cpus);
    		break;
    	}
    
    	return factor;
    }
    

    从代码中可以看出,调度粒度、唤醒粒度、调度延迟都是其规范值乘以一个因子。这个因子的值有三种可能:一是固定等于1,二是等于CPU的个数,三是等于1加上CPU个数对2的对数。具体使用哪种情况由变量sysctl_sched_tunable_scaling的值决定,此变量的值可以通过文件/sys/kernel/debug/sched/tunable_scaling来改变,默认值是SCHED_TUNABLESCALING_LOG。我们以8核CPU为例(下文也是如此),factor的值就是4,因此默认的调度粒度就是0.75 * 4 = 3毫秒。也就是说在一个8核系统默认配置下,调度粒度是3毫秒,一个进程如果运行还不到3毫秒是不能被抢占的。

    此代码中还提到了唤醒粒度,我们也顺便讲一下。唤醒粒度是指被唤醒的进程如果其虚拟运行时间比当前进程的虚拟运行时间少的值不大于这个值的虚拟化时间就不进行抢占。唤醒粒度指的不是是否唤醒这个进程,而是唤醒这个进程之后是否进行抢占。只有当被唤醒的进程的虚拟运行时间比当前进程的少的足够多时才会进行抢占。当然这个也要同时满足调度粒度才会进行抢占。唤醒粒度的规范值是1毫秒,乘以4就是4毫秒。

    此代码中还有调度延迟,它和调度周期有关,我们先来计算一下调度延迟的值。调度延迟的规范值是6毫秒,乘以4就是24毫秒。

    调度周期的计算与调度粒度和调度延迟都有关系,所以我们现在才能开始计算调度周期。先来看代码

    linux-src/kernel/sched/fair.c

    static unsigned int sched_nr_latency = 8;
    
    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;
    }
    

    调度延迟24毫秒是个固定值(在默认情况都不变的情况下),当运行队列上的进程个数小于等于8的时候,每个进程至少能分到3毫秒,符合调度粒度是3毫秒的设定。所以当running进程的个数小于等于8时,调度周期就等于调度延迟,每个进程至少能平分到3毫秒时间。当其个数大于8时,调度周期就等于运行进程的个数乘以调度粒度。在一个调度周期内如果是所有进程平分的话,一个进程能分到3毫秒。但是由于有的进程权重高,分到的时间就会大于3毫秒,就会有进程分到的时间少于3毫秒。实际上是这样的吗?我们来看一下计算时间片的代码。

    linux-src/kernel/sched/fair.c

    static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
    {
    	unsigned int nr_running = cfs_rq->nr_running;
    	u64 slice;
    
    	if (sched_feat(ALT_PERIOD))
    		nr_running = rq_of(cfs_rq)->cfs.h_nr_running;
    
    	slice = __sched_period(nr_running + !se->on_rq);
    
    	for_each_sched_entity(se) {
    		struct load_weight *load;
    		struct load_weight lw;
    
    		cfs_rq = cfs_rq_of(se);
    		load = &cfs_rq->load;
    
    		if (unlikely(!se->on_rq)) {
    			lw = cfs_rq->load;
    
    			update_load_add(&lw, se->load.weight);
    			load = &lw;
    		}
    		slice = __calc_delta(slice, se->load.weight, load);
    	}
    
    	if (sched_feat(BASE_SLICE))
    		slice = max(slice, (u64)sysctl_sched_min_granularity);
    
    	return slice;
    }
    

    变量slice被复用了,首先被用来表示调度周期。接下来的for循环,由于我们不考虑组调度,实际上只执行了一遍。slice的值等于调度周期乘以进程权重与运行队列权重的比值。如果进程的权重低于平均权重的话,那么其实将会小于调度粒度。再往下有个判断,由于BASE_SLICE的值默认是true,所以此语句会执行,slice至少等于调度粒度。由此可以得出结论,在默认情况下,进程分到的时间片不会小于调度粒度。那么此时实际的调度周期就会延长了。不过很大概率不会延长的,因为一般都会有进程因为阻塞而进行主动调度从而让出来一部分时间。

    我们再来总结一下调度周期、调度延迟、调度粒度、时间片的概念意义和它们在CFS中的变量意义以及相互之间的关系。调度周期的概念是指运行队列上所有的进程都运行一遍的时间,但是在CFS中没有了标准的调度周期,调度周期是动态的,只是个计算量。调度延迟的概念是指一个进程从加入到运行队列到被放到CPU上去执行之间的时间差,显然这个时间差受进程本身和运行队列长短的影响。在CFS中,调度延迟的概念完全变了,调度延迟变成了调度周期的最小值。时间片的概念是指一个进程一次最多只能运行多长时间,然后就要被抢占了。在CFS中时间片的概念没有变,但是用法和传统的用法不一样。调度粒度是指一个进程一次至少运行多少时间才能被抢占,这个才CFS中也是如此。在CFS中,它们的计算关系是,调度周期等于调度粒度乘以Runnable进程的数量,但是不能小于调度延迟,时间片等调度周期乘以进程权重与运行队列权重的比值。

    4.7 抢占调度

    抢占调度有两个典型的触发点:定时器中断和进程唤醒,还有两个非典型的触发点:迁移线程和改变优先级。我们先来说定时器中断,定时器中断的主要目的就是为了进行抢占调度,防止有的进程一直占着CPU不放手。以前的算法会在定时器中断中检查进程的时间片是否已耗尽,如果耗尽的话就触发调度,不过在CFS中的具体做法与此有所不同。在CFS中不会规定固定的调度周期,调度周期都是即时计算出来的,不会给进程分配时间片进行递减,而是在定时器中断中统计进程此时占据CPU已经运行了多少时间,拿这个时间去给理论上它应当运行的时间比,如果超过了就触发调度。进程的理论运行时间就等于其权重与队列权重之比再乘以调度周期,调度周期的计算方法在上一节中讲过了。因此CFS中的调度周期和时间片与传统调度算法中的概念不同,它是一个动态的概念,只有当发生定时器中断了才会去计算一下,会根据当时的状态进行计算。比如当前进程在函数A中唤醒了很多进程,那么定时器中断是发生在函数A之前还是之后,调度周期和时间片的计算结果会有很大的不同。

    下面我们来看一下定时器中断中的抢占逻辑:
    linux-src/kernel/sched/core.c

    void scheduler_tick(void)
    {
    	int cpu = smp_processor_id();
    	struct rq *rq = cpu_rq(cpu);
    	struct task_struct *curr = rq->curr;
    
    	curr->sched_class->task_tick(rq, curr, 0);
    }
    

    linux-src/kernel/sched/fair.c

    static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
    {
    	struct cfs_rq *cfs_rq;
    	struct sched_entity *se = &curr->se;
    
    	for_each_sched_entity(se) {
    		cfs_rq = cfs_rq_of(se);
    		entity_tick(cfs_rq, se, queued);
    	}
    }
    
    static void
    entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
    {
    	update_curr(cfs_rq);
    	update_load_avg(cfs_rq, curr, UPDATE_TG);
    	update_cfs_group(curr);
    
    	if (cfs_rq->nr_running > 1)
    		check_preempt_tick(cfs_rq, curr);
    }
    
    static void
    check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
    {
    	unsigned long ideal_runtime, delta_exec;
    	struct sched_entity *se;
    	s64 delta;
    
    	ideal_runtime = sched_slice(cfs_rq, curr);
    	delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
    	if (delta_exec > ideal_runtime) {
    		resched_curr(rq_of(cfs_rq));
    		/*
    		 * The current task ran long enough, ensure it doesn't get
    		 * re-elected due to buddy favours.
    		 */
    		clear_buddies(cfs_rq, curr);
    		return;
    	}
    
    	/*
    	 * Ensure that a task that missed wakeup preemption by a
    	 * narrow margin doesn't have to wait for a full slice.
    	 * This also mitigates buddy induced latencies under load.
    	 */
    	if (delta_exec < sysctl_sched_min_granularity)
    		return;
    
    	se = __pick_first_entity(cfs_rq);
    	delta = curr->vruntime - se->vruntime;
    
    	if (delta < 0)
    		return;
    
    	if (delta > ideal_runtime)
    		resched_curr(rq_of(cfs_rq));
    }
    

    定时器中断中会调用scheduler_tick,scheduler_tick会调用当前进程的调度类的task_tick函数指针,对于普通进程来说就是task_tick_fair函数。task_tick_fair会调用entity_tick,我们这里不考虑组调度,因此for循环只会执行一遍。在entity_tick中会先调用update_curr更新进程的运行时间,然后在当运行进程总数大于1的时候调用check_preempt_tick。check_preempt_tick就是定时器抢占的核心了。

    在check_preempt_tick中会先计算出来进程的理论运行时间ideal_runtime和实际运行时间delta_exec。如果实际运行时间大于理论运行时间,就会调用resched_curr来触发抢占。如果不大于的话还会继续处理。先判断实际运行时间是否小于调度粒度,如果小于就返回。如果不小于就继续。此时会计算当前进程的虚拟运行时间与队首进程的虚拟运行时间的差值,如果差值大于前面计算出来的理论运行时间就会调用resched_curr来触发抢占。按照定时器中断的目的的话,后面这个操作是没有必要的,但是按照我们在CFS调度模型中的要求,尽量使所有玻璃杯在任意时刻的水位都尽量相同,这个操作是很有必要的,它能提高公平性。

    下面我们来看一下唤醒抢占,唤醒分为新建唤醒和阻塞唤醒,最后都会调用check_preempt_curr函数来看一下是否需要抢占。下面我们来看一下代码:

    linux-src/kernel/sched/core.c

    void check_preempt_curr(struct rq *rq, struct task_struct *p, int flags)
    {
    	if (p->sched_class == rq->curr->sched_class)
    		rq->curr->sched_class->check_preempt_curr(rq, p, flags);
    	else if (p->sched_class > rq->curr->sched_class)
    		resched_curr(rq);
    }
    

    linux-src/kernel/sched/fair.c

    static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int wake_flags)
    {
    	struct task_struct *curr = rq->curr;
    	struct sched_entity *se = &curr->se, *pse = &p->se;
    	struct cfs_rq *cfs_rq = task_cfs_rq(curr);
    	int scale = cfs_rq->nr_running >= sched_nr_latency;
    	int next_buddy_marked = 0;
    	int cse_is_idle, pse_is_idle;
    
    	if (test_tsk_need_resched(curr))
    		return;
    
    	/* Idle tasks are by definition preempted by non-idle tasks. */
    	if (unlikely(task_has_idle_policy(curr)) &&
    	    likely(!task_has_idle_policy(p)))
    		goto preempt;
    
    	/*
    	 * Batch and idle tasks do not preempt non-idle tasks (their preemption
    	 * is driven by the tick):
    	 */
    	if (unlikely(p->policy != SCHED_NORMAL) || !sched_feat(WAKEUP_PREEMPTION))
    		return;
    
    	update_curr(cfs_rq_of(se));
    	if (wakeup_preempt_entity(se, pse) == 1) {
    		if (!next_buddy_marked)
    			set_next_buddy(pse);
    		goto preempt;
    	}
    
    	return;
    
    preempt:
    	resched_curr(rq);
    	if (unlikely(!se->on_rq || curr == rq->idle))
    		return;
    
    	if (sched_feat(LAST_BUDDY) && scale && entity_is_task(se))
    		set_last_buddy(se);
    }
    
    static int
    wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se)
    {
    	s64 gran, vdiff = curr->vruntime - se->vruntime;
    
    	if (vdiff <= 0)
    		return -1;
    
    	gran = wakeup_gran(se);
    	if (vdiff > gran)
    		return 1;
    
    	return 0;
    }
    
    static unsigned long wakeup_gran(struct sched_entity *se)
    {
    	unsigned long gran = sysctl_sched_wakeup_granularity;
    	return calc_delta_fair(gran, se);
    }
    

    在check_preempt_curr中,同类进程会使用调度类的check_preempt_curr函数进行处理,不同类的进程,高类会抢占低类的进程。分时调度类中的相应函数是check_preempt_wakeup。此函数会先区分不同的调度策略,SCHED_IDLE策略的进程一定会被非SCHED_IDLE的进程抢占,非SCHED_NORMAL的进程一定不会抢占非SCHED_IDLE的进程。接下来会调用update_curr更新一下当前进程的时间统计,然后调用wakeup_preempt_entity来查看一下是否满足唤醒粒度,如果满足就触发调度。满足唤醒粒度的标准是当前进程的虚拟运行时间与被唤醒进程的虚拟运行时间的差值要大于唤醒粒度对应的虚拟时间。

    我们再来画个图对CFS的抢占时机和抢占规则进行一下总结:
    在这里插入图片描述

    4.8 入队与出队

    CFS中排队的进程都是放在红黑树中,我们经常要对其进行出队入队查询队首的操作。

    下面我们先来看一下内核中红黑树的定义与操作:
    linux-src/include/linux/rbtree_types.h

    struct rb_root_cached {
    	struct rb_root rb_root;
    	struct rb_node *rb_leftmost;
    };
    
    struct rb_root {
    	struct rb_node *rb_node;
    };
    
    struct rb_node {
    	unsigned long  __rb_parent_color;
    	struct rb_node *rb_right;
    	struct rb_node *rb_left;
    }
    

    linux-src/include/linux/rbtree.h

    #define rb_first_cached(root) (root)->rb_leftmost
    
    static __always_inline struct rb_node *
    rb_add_cached(struct rb_node *node, struct rb_root_cached *tree,
    	      bool (*less)(struct rb_node *, const struct rb_node *));
    
    static inline struct rb_node *
    rb_erase_cached(struct rb_node *node, struct rb_root_cached *root);
    

    在CFS中经常会对队首进程进行操作,因此rb_root_cached中用rb_leftmost对红黑树的最下角的节点(这个节点就是vruntime最小的节点,就是队首进程)进行了缓存,方便查找。

    我们经常会对运行队列进行入队出队操作,入队出队操作可以分为两类。一类是和调度执行相关的入队出队,叫做pick_next_task和put_prev_task,pick_next_task是选择一个进程把它放到CPU上去运行,put_prev_task是把正在CPU上运行的进程放回到运行队列中去。另一类是和非执行相关的入队出队,叫做enqueue_task和dequeue_task,enqueue_task是把一个非正在CPU上执行的进程放入到队列中去,dequeue_task是把一个进程从队列中拿出来,但不是拿来去CPU上运行的。

    pick_next_task和put_prev_task都是在调度流程中的选择进程过程中调用的。

    下面我们看一下代码(进行了高度删减):
    linux-src/kernel/sched/core.c

    static void __sched notrace __schedule(unsigned int sched_mode)
    {
    	struct task_struct *prev, *next;
    	unsigned long *switch_count;
    	unsigned long prev_state;
    	struct rq_flags rf;
    	struct rq *rq;
    	int cpu;
    
    	cpu = smp_processor_id();
    	rq = cpu_rq(cpu);
    	prev = rq->curr;
    
    	prev_state = READ_ONCE(prev->__state);
    	if (!(sched_mode & SM_MASK_PREEMPT) && prev_state) {
    		if (signal_pending_state(prev_state, prev)) {
    			WRITE_ONCE(prev->__state, TASK_RUNNING);
    		} else {
    			deactivate_task(rq, prev, DEQUEUE_SLEEP | DEQUEUE_NOCLOCK);
    		}
    	}
    
    	next = pick_next_task(rq, prev, &rf);
    
    	if (likely(prev != next)) {
    		rq = context_switch(rq, prev, next, &rf);
    	} else {
    		
    	}
    }
    
    void deactivate_task(struct rq *rq, struct task_struct *p, int flags)
    {
    	p->on_rq = (flags & DEQUEUE_SLEEP) ? 0 : TASK_ON_RQ_MIGRATING;
    
    	dequeue_task(rq, p, flags);
    }
    
    static struct task_struct *
    pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
    {
    	return __pick_next_task(rq, prev, rf);
    }
    
    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;
    
    	if (likely(prev->sched_class <= &fair_sched_class &&
    		   rq->nr_running == rq->cfs.h_nr_running)) {
    		p = pick_next_task_fair(rq, prev, rf);
    		return p;
    	}
    }
    

    linux-src/kernel/sched/fair.c

    struct task_struct *
    pick_next_task_fair(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
    {
    	struct cfs_rq *cfs_rq = &rq->cfs;
    	struct sched_entity *se;
    	struct task_struct *p;
    	int new_tasks;
    
    	if (prev)
    		put_prev_task(rq, prev);
    
    	do {
    		se = pick_next_entity(cfs_rq, NULL);
    		set_next_entity(cfs_rq, se);
    		cfs_rq = group_cfs_rq(se);
    	} while (cfs_rq);
    
    	p = task_of(se);
    
    	return p;
    }
    
    static void put_prev_task_fair(struct rq *rq, struct task_struct *prev)
    {
    	struct sched_entity *se = &prev->se;
    	struct cfs_rq *cfs_rq;
    
    	for_each_sched_entity(se) {
    		cfs_rq = cfs_rq_of(se);
    		put_prev_entity(cfs_rq, se);
    	}
    }
    
    static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev)
    {
    	if (prev->on_rq) {
    		__enqueue_entity(cfs_rq, prev);
    	}
    	cfs_rq->curr = NULL;
    }
    
    static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
    {
    	rb_add_cached(&se->run_node, &cfs_rq->tasks_timeline, __entity_less);
    }
    
    static struct sched_entity *
    pick_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *curr)
    {
    	struct sched_entity *left = __pick_first_entity(cfs_rq);
    	struct sched_entity *se;
    	se = left; /* ideally we run the leftmost entity */
    	return se;
    }
    

    在执行调度的时候会调用到pick_next_task_fair,此函数会先put_prev_task再pick_next_entity。put_prev_task最终会使用rb_add_cached把被抢占的进程放回到队列中去,对于阻塞调度的则不会。pick_next_entity最终会使用rb_first_cached来获取队首进程用来调度。

    enqueue_task和dequeue_task这两个函数会在修改进程优先级、设置进程亲和性、迁移进程等操作中成对使用。enqueue_task在进程唤醒中也会使用,下面我们来看一下代码。
    linux-src/kernel/sched/core.c

    static int
    try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)
    {
    	unsigned long flags;
    	int cpu, success = 0;
    
    	cpu = select_task_rq(p, p->wake_cpu, wake_flags | WF_TTWU);
    	if (task_cpu(p) != cpu) {
    		set_task_cpu(p, cpu);
    	}
    
    	ttwu_queue(p, cpu, wake_flags);
    	return success;
    }
    
    static void ttwu_queue(struct task_struct *p, int cpu, int wake_flags)
    {
    	struct rq *rq = cpu_rq(cpu);
    	struct rq_flags rf;
    
    	ttwu_do_activate(rq, p, wake_flags, &rf);
    }
    
    static void
    ttwu_do_activate(struct rq *rq, struct task_struct *p, int wake_flags,
    		 struct rq_flags *rf)
    {
    	activate_task(rq, p, en_flags);
    	ttwu_do_wakeup(rq, p, wake_flags, rf);
    }
    
    void activate_task(struct rq *rq, struct task_struct *p, int flags)
    {
    	enqueue_task(rq, p, flags);
    
    	p->on_rq = TASK_ON_RQ_QUEUED;
    }
    
    static inline void enqueue_task(struct rq *rq, struct task_struct *p, int flags)
    {
    	p->sched_class->enqueue_task(rq, p, flags);
    }
    

    linux-src/kernel/sched/fair.c

    static void
    enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)
    {
    	struct cfs_rq *cfs_rq;
    	struct sched_entity *se = &p->se;
    
    	for_each_sched_entity(se) {
    		if (se->on_rq)
    			break;
    		cfs_rq = cfs_rq_of(se);
    		enqueue_entity(cfs_rq, se, flags);
    	}
    }
    
    static void
    enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
    {
    	bool renorm = !(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_MIGRATED);
    	bool curr = cfs_rq->curr == se;
    
    	update_curr(cfs_rq);
    	if (!curr)
    		__enqueue_entity(cfs_rq, se);
    	se->on_rq = 1;
    }
    
    static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
    {
    	rb_add_cached(&se->run_node, &cfs_rq->tasks_timeline, __entity_less);
    }
    

    可以看出enqueue_task最终也是调用rb_add_cached把进程放入到运行队列中去的。

    4.9 CFS算法评价

    现在我们对CFS调度算法的各个方面都有了基本的了解,让我们再看一下CFS调度模型图来回忆一下:
    在这里插入图片描述
    回忆完之后,我们对CFS算法进行一下分析和评价。首先CFS取消了对IO密集型和CPU密集型进程的探测,避免了由于误探而产生的问题。虽然没有对IO密集型和CPU密集型进程进行探测区分,但是CFS还是能很好地处理这两类进程。CPU密集型进程总是进程处于Runnable状态,所以能经常运行。由于其经常会运行,水位会比较高,所以就排到后面,就给其它进程留下了机会。IO密集型进程由于经常处于阻塞状态,所以其水位就会比较低,在其唤醒之后进入队列的时候经常能排在队首且很可能会抢占当前进程,所以IO密集型的进程响应性会比较高。

    我们再来看公平性,CFS的名字就叫做完全公平调度,所以肯定是很公平的。公平性主要体现在以下几个方面。一是取消了对IO密集型和CPU密集型进程的探测,不会对IO密集型进程进行特殊的照顾,所以进程都一视同仁。二是优先级转权重的时候采用了等比数列,使得nice值相差1的进程获得的CPU时间比例总是相差10%,很公平。三是低优先级的进程随着别人的水位增长总是会排到前面的,一定会在可观的时间内得到执行,不会产生饥饿。

    再来看适应性,由于采用了红黑树,CFS的出队入队查找操作都是O(logn)的,当进程变得很多时,调度效率也依然良好。与调度效率是O(n)的算法相比,适应性明显很强,和O(1)的算法相比,也不算太差。

    吞吐量和很多因素有关,代码简洁,调度效率是O(logn)也会提高其吞吐量。

    节能性的话,CFS本身并没有考虑这个问题。现在内核已经合入了EAS的代码,EAS是对CFS的扩展,主要是来解决调度器的节能问题的。

    五、分时调度均衡

    下面我们来看一下分时调度类的均衡问题,实时调度类和限时调度类的均衡问题不在这里讨论。

    5.1 均衡模型

    有了前面的CFS调度的知识,再来研究调度均衡的问题就比较方便了。根据前面的CFS调度模型,我画了一些CFS调度均衡模型的图,先来看一下:
    在这里插入图片描述
    很明显两个桌子上的玻璃杯数量相差很大,不太均衡,我们需要想办法让两个桌子上的玻璃杯均衡起来。为了实现负载均衡,我们面临三个问题。第一个问题就是如何度量水龙头0和水龙头1的负载大小。只有把它们的负载大小算出来了,我们才能判断哪个CPU忙哪个CPU闲,才能合理对它们进行负载均衡。第二个问题是如何进行均衡,从图中就可以看出有两种方式,一是Wait Box中的进程醒来去哪个运行队列上,肯定是去负载相对较小的队列上去,这个叫做个体均衡,二是对运行队列上的进程进行迁移,使得多个运行队列的负载达到接近的程度,这个叫做总体均衡。第三个问题是当CPU比较多的时候,在不同的CPU之间迁移进程的代价是不同的,而且如果要一次实现所有CPU上的均衡代价会更大,所以我们要分层次的进行均衡,这个叫做调度域。

    如何计算CPU的负载呢?我们想到的最简单的方法就是计算玻璃杯的数量,让每个运行队列上都有相同的玻璃杯。这样就行了吗?不行,玻璃杯有粗有细,粗的比细的更能装水,所以我们还需要考虑进程的权重问题。数量加权重同时考虑就行了吗?还是不行,试想一下,你刚做完负载均衡,结果一个CPU上的进程全都阻塞休眠去了,另外一个CPU上的进程一个都没休眠都在努力地运行,负载瞬间变得严重不均衡了。这种方法也不行,我们还要考虑进程以后的休眠概率问题。但是我们又不是神仙,也没法预测进程以后的休眠概率。对此我们采取的方法是回顾历史展望未来,通过统计进程之前的运行数据预测其之后的休眠概率。由此可见计算CPU的负载还是一件很麻烦的事。

    个体均衡的触发时机有三个:一是阻塞进程唤醒时(WF_TTWU),二是进程新建唤醒时(WF_FORK),三是进程执行新的程序时(WF_EXEC)。阻塞唤醒和新建唤醒都是进程重新选择运行队列的好时机。进程执行新程序是指进程调用了execve系统调用,此时进程会重新加载程序,老的程序会被抛弃,此时也是一个重新选择运行队列的好时机。

    总体均衡的触发时机有三个:一是在pick_next_task_fair时发现运行队列是空的,此时会触发new idle balance;二是在定时器中断检测负载是否均衡,如果不均衡就进行均衡,这个叫做tick load balance或者periodic load balance;三是在开启动态tick的情况下,如果一个CPU发现自己太忙而有的CPU在idle就会唤醒那个CPU进行负载均衡,这个叫做nohz idle banlance。

    个体均衡与总体均衡的区别在于:个体均衡的出发点是进程,总体均衡的出发点是CPU。

    关于调度均衡的具体细节推荐阅读:
    http://www.wowotech.net/process_management/load_balance.html
    http://www.wowotech.net/process_management/task_placement.html
    http://www.wowotech.net/process_management/load_balance_detail.html
    http://www.wowotech.net/process_management/task_placement_detail.html
    http://www.wowotech.net/process_management/load_balance_function.html

    5.2 负载计算

    暂略

    5.3 调度域

    暂略

    5.4 个体均衡

    暂略

    5.5 总体均衡

    暂略

    六、实时调度

    暂略

    6.1 基本原理


    七、限时调度

    暂略

    7.1 基本原理


    八、调度参数

    暂略

    8.1 编译时参数


    8.2 启动时参数


    8.3 运行时参数


    九、调度统计

    暂略


    ## 9.1 基本原理

    十、总结回顾

    我们在此文中讲了非常多关于进程调度的知识点,下面我们来总结一下。
    在这里插入图片描述
    对着这个图让我们来回顾一下,什么是调度,为什么要调度,为什么能调度。然后是调度时机,包括主动调度和被动调度。再之后是如何调度,包括选择进程和切换进程。切换进程的逻辑是通用的,而选择进程要分为5个调度类来进行选择。讲完了在单个CPU上的调度之后,我们还要在多CPU上进行调度均衡。

    进程调度是操作系统中非常庞大非常难懂但又非常重要的部分,我们要经常理论结合代码结合实践、反复思考琢磨才能更好的理解和掌握它。

    参考文献:

    《Linux Kernel Development》
    《Understanding the Linux Kernel》
    《Professional Linux Kernel Architecture》
    《Mastering Linux Kernel Development》
    《Understanding the Linux Virtual Memory Manager》
    《Linux内核深度解析》
    《Linux操作系统原理与应用》
    《深度探索Linux操作系统》
    《ARM Linux内核源码剖析》
    《奔跑吧Linux内核》
    《Linux内核源代码情景分析》
    《Linux内核设计的艺术》
    《Linux内核完全注释》

    LWN:https://lwn.net/Kernel/Index/
    linux-insides:https://github.com/0xAX/linux-insides
    宋宝华:https://blog.csdn.net/21cnbao
    蜗窝科技:http://www.wowotech.net
    CHENG Jian:https://kernel.blog.csdn.net/
    内核工匠:https://blog.csdn.net/feelabclihu
    DroidPhone:https://blog.csdn.net/DroidPhone
    Bystander_J:https://blog.csdn.net/weixin_42092278
    术道经纬:https://www.zhihu.com/column/c_1108400140804726784
    Kernel Exploring:https://richardweiyang-2.gitbook.io/kernel-exploring/
    Linux Performance:http://linuxperf.com/

    Linux系统标准规范:

    https://refspecs.linuxfoundation.org/
    https://man7.org/linux/man-pages/man7/standards.7.html

    展开全文
  • 前面放完建设四个现代化大数据平台乌托邦理想的大卫星,接下来的文章得谈谈具体...本文重点谈理论,会先从大的场景划分的角度对市面上的各种调度系统进行分类讨论,然后再针对具体的作业调度系统,探讨一下各自的优缺点

    前面放完建设四个现代化大数据平台乌托邦理想的大卫星,接下来的文章得谈谈具体组件的生产大跃进了。



    第一篇,先来讨论一下大数据开发平台的核心组件之一:作业调度系统

    作业调度系统是一个相对复杂的系统,涉及的内容繁杂,针对的场景多种多样,实现的方案千差万别,是一个需要理论和实践并重的系统。

    本文重点谈理论,会先从大的场景划分的角度对市面上的各种调度系统进行分类讨论,然后再针对具体的作业调度系统,探讨一下各自的架构流派和实现方案,并简单分析一下各自的优缺点。希望能让大家对作业调度系统要做什么,该怎么做,有一个大致的了解

    那些调度系统们

    调度系统,更确切地说,作业调度系统(Job Scheduler)或者说工作流调度系统(workflow Scheduler)是任何一个稍微有点规模,不是简单玩玩的大数据开发平台都必不可少的重要组成部分。

    除了Crontab,Quartz这类偏单机的定时调度程序/库。开源的分布式作业调度系统也有很多,比较知名的比如:oozie,azkaban,chronos,zeus等等,此外,还有包括阿里的TBSchedule,SchedulerX,腾讯的Lhotse,当当的elastic-job,唯品会的Saturn等等

    可以说,几乎每家稍微有点规模的数据平台团队,都会有自己的调度系统实现方案,要不然自研,要不然在开源的基础上进行一些封装和改造(比如很多公司采取了封装oozie的方式)。

    在继续讨论作业调度系统之前,首先允许我讨论一下作业调度系统资源调度系统(或者集群调度系统)的区别,因为往往有同学把这两者混为一谈。后者的典型代表比如:Yarn/Mesos/Omega/Borg,还有阿里的伏羲,腾讯的盖娅(Gaia),百度的Normandy等等。

    资源调度系统,它的工作重点是底层物理资源的分配管理,目标是最大化的利用集群机器的CPU/磁盘/网络等硬件资源,所调配和处理的往往是与业务逻辑没有直接关联的通用的程序进程这样的对象。

    而作业调度系统,关注的首要重点是在正确的时间点启动正确的作业,确保作业按照正确的依赖关系及时准确的执行。资源的利用率通常不是第一关注要点,业务流程的正确性才是最重要的。

    作业调度系统有时也会考虑负载均衡问题,但保证负载均衡更多的是为了系统自身的健壮性,而资源的合理利用,作为一个可以优化的点,往往依托底层的资源调度系统来实现。

    那么,为什么市面上会存在这么多的作业调度系统项目,作业调度系统为什么没有像Hdfs/Hive/HBase之类的组件,形成一个相对标准化的解决方案呢?归根到底,还是由作业调度系统的业务复杂性决定的。

    一个成熟易用,便于管理和维护的作业调度系统,需要和大量的周边组件对接,不仅包括各种存储计算框架,还可要处理或使用到包括:血缘管理,权限控制,负载流控,监控报警,质量分析等各种服务或事务。这些事务环节,在每家公司往往都有自己的解决方案,所以作业调度系统所处的整体外部环境,千差万别,再加上各公司各种业务流程的定制化需求进一步加大了环境的差异性,所以,调度系统很难做到既能灵活通用的适配广大用户的各种需求,又不落到太过晦涩难用的地步。

    市面上的各种开源的作业调度系统,要不然就是在某些环节/功能上是缺失的,使用和运维的代价很高,需要大量二次开发;要不然就是只针对特定的业务场景,形态简单,缺乏灵活性;又或者在一些功能环节上是封闭自成体系的,很难和外部系统进行对接。

    那么,理想中,完备的作业调度系统,到底都要处理哪些事务呢?要做好这些事务都有哪些困难要克服,有哪些方案可以选择,市面上的开源调度系统项目又是如何应对这些问题的,容我和大家一起来探讨一下。

    两大类作业调度系统

    首先,让我来对作业调度系统进行一下大的分类。市面上的作业调度系统,根据实际的功能定位,主要分为两大类方向:定时分片类作业调度系统和DAG工作流类作业调度系统

    这两类系统的架构和功能实现通常存在很大的差异。所以下文先做一下两者的简单的比较。

    定时分片类作业调度系统



    定时分片类系统的方向,重点定位于任务的分片执行场景,这类系统的代表包括:TBSchedule,SchedulerX,Elastic-job, Saturn。我司自研的Vacuum也是这样的系统。

    这种功能定位的作业调度系统,其最早的需要来源和出发点往往是做一个分布式的Crontab/Quartz。

    一开始各个业务方八仙过海,自己玩自己的单机定时任务,然后,随着业务的增长,各种定时任务越来越多,分散管理的代价越来越高。再加上有些业务随着数据量的增长,为了提高运行效率,也需要以分布式的方式在多台机器上并发执行。这时候,分布式分片调度系统也就孕育而生了。

    这类系统的实际应用场景,往往和日常维护工作或需要定时执行的业务逻辑有一定关联。比如需要定时批量清理一批机器的磁盘空间,需要定时生成一批商品清单,需要定时批量对一批数据建索引,需要定时对一批用户发送推送通知等等。

    这类系统的核心目标基本上就是两点:

    • 对作业分片逻辑的支持:将一个大的任务拆成多个小任务分配到不同的服务器上执行, 难点在于要做到不漏,不重,保证负载平衡,节点崩溃时自动进行任务迁移等

    • 高可用的精确定时触发要求:因为往往涉及到实际业务流程的及时性和准确性,所以通常需要保证任务触发的强实时和可靠性


    所以,负载均衡,弹性扩容,状态同步和失效转移通常是这类调度系统在架构设计时重点考虑的特性

    从接入方案和流程上来说,因为要支持分片逻辑,要支持失效转移等,这类调度系统,对所调度的任务通常都是有侵入性要求的。

    常见的做法是用户作业需要依赖相关分片调度系统的客户端库函数,拓展一个作业调度类做为作业触发的入口点。一般还需要接收和处理分片信息用于对数据进行正确的分片处理。此外通常还需要实现一些接口用于满足服务端的管理需求,比如注册节点,注册作业,启动任务,停止任务,汇报状态等等。有些系统还要求作业执行节点常驻Daemon进程,用于协调本地作业的管理和通讯。

    从触发实现逻辑的角度来说,为了在海量任务的情况下,保证严格精确定时触发,这类调度系统有一大半,其定时触发逻辑,实际上是由执行节点自身在本地触发的,也就是说要求作业或守护进程处于运行状态,向服务端注册作业,服务端分配分片信息和定时逻辑给到客户端,但定时的触发,是由客户端库函数封装的如Quartz等定时逻辑来实际执行触发的。

    这样做的首要目的当然是为了保证触发的精度和效率,降低服务端负载,此外如果服务端短时间内挂掉,只要作业配置保持不变,作业还是能够在客户端正常触发的。

    也有些系统,比如SchedulerX,是采用服务端触发逻辑的。这对服务端的要求就高了很多,因为这时候,服务端不光要协调分片逻辑,还要维护触发队列。所以服务端触发的系统,首先需要保证服务端的高可用,其次还要保障性能,因此,通常都是采用集群方案

    DAG工作流类调度系统



    这一类系统的方向,重点定位于任务的调度依赖关系的正确处理,分片执行的逻辑通常不是系统关注的核心,或者不是系统核心流程的关键组成部分,如果某些任务真的关注分片逻辑,往往交给后端集群(比如MR任务自带分片能力)或者具体类型的任务执行后端去实现。

    这类系统的代表,包括:oozie,azkaban,chronos,zeus,Lhotse,还有各种大大小小的公有云服务提供的那些可视化工作流定义系统。我司自研的Jarvis调度系统也属于这类系统

    DAG工作流类调度系统所服务的往往是作业繁多,作业之间的流程依赖比较复杂的场景,比如大数据开发平台的离线数仓报表处理业务,从数据采集,清洗,到各个层级的报表的汇总运算,到最后数据导出到外部业务系统,一个完整的业务流程,可能涉及到成百上千个相互交叉依赖关联的作业。

    所以DAG工作流类调度系统关注的重点,通常会包括:

    足够丰富和灵活的依赖触发机制:比如时间触发任务,依赖触发任务,混合触发任务


    • 而依赖触发自身,可能还要考虑,多亲依赖,长短周期依赖(比如小时任务依赖天任务,或者反过来),依赖范围判定(比如所依赖任务最后一次成功就可以触发下游,还是过去一个星期的所有任务都成功才可以触发下游),自身历史任务依赖,串并行触发机制等等


    作业的计划,变更和执行流水的管理和同步


    • 这一条,定时分片类调度系统固然也要考虑,但通常都相对简单。

    • 而在DAG工作流类调度系统中,因为任务触发机制的灵活性和作业依赖关系的复杂性,这个需求就尤为重要,需要提供的功能更加复杂,具体的问题解决起来也困难很多。


    任务的优先级管理,业务隔离,权限管理等


    • 在定时分片类调度系统中,通常情况下,具体执行端的业务的隔离很多情况下是天然的,注册了特定业务的节点才会去执行特定的任务。然后,加上业务链路一般都比较短,以及强实时性要求,所以对优先级的管理通常要求也不高,基本靠资源隔离来实现资源的可用,不太存在竞争资源的问题,权限管理也同理。

    • 而在DAG工作流类调度系统中,往往一大批作业共享资源执行,所以优先级,负载隔离,和权限管控的问题也就突显出来


    各种特殊流程的处理,比如暂停任务,重刷历史数据,人工标注失败/成功,临时任务和周期任务的协同等等


    • 这类需求,本质上也是因为业务流程的复杂性带来的,比如业务逻辑变更啦,脚本写错啦,上游数据有问题啦,下游系统挂掉啦等等,而业务之间的网状关联性,导致处理问题时需要考虑的因素很多,也就要求处理的手段要足够灵活强大


    完备的监控报警通知机制


    • 最简单的比如,任务失败报警,超时报警,再进一步,流量负载监控,业务进度监控和预测,如果做的再完善一点,还可以包括业务健康度监控分析,性能优化建议和问题诊断专家系统等



    小结

    需要注意的是,这两类系统的定位目标,并不是绝对冲突矛盾的。只不过,要同时圆满的支持这两大类需求,从实现的角度来说是很困难的,因为侧重点的不同,在架构上多少会对某些方面做些取舍,当前的系统都没有能够做到完美的两者兼顾。但这不代表他们就一定是不可调和的,好比离线批处理计算框架和流式实时计算框架,长期以来各行其路,但是,随着理论,实践的进步,也开始有依托一种框架统一处理两类计算业务的可能性出现。

    DAG工作流调度系统的两种心法流派



    前面说到,DAG工作流调度系统有很多开源实现,各大公司也往往有自己的系统实现。这些系统,从开发语言,支持的任务类型,调度方式,监控报警,到业务接入的方式,周边管理工具的完备性等角度来说,都是千差万别的。这些差别在很大程度上都是产品形态招式上的差异,但是有一条,不止招式那么简单,我认为是心法流派的差异,它在很大程度上影响了一个系统的核心框架设计思想。

    这个差异就是:具体任务的执行,是依托于一个静态的执行列表还是动态的执行列表,此话怎讲?别急,待我详细解释一下。

    两个概念 : 作业计划(Job Plan)和任务实例(Task Instance)

    要谈执行列表的心法流派问题,首先,得明确作业计划和任务实例两个概念

    通常情况下,既然你把一个作业丢到调度系统上去监管执行,那除了个别一次性作业,多数情况下这些作业都是要周期性重复执行的,只是有些纯粹由时间驱动,有些还有前置任务依赖关系要处理。

    那么什么时候执行这个作业,是每个月月底执行一次,还是每天凌晨2点执行一次,又或者还是早上9点到晚上6点之间,每个小时执行一次?任务触发的条件,是前置任务全部成功,还是任一前置任务成功,又或者要求自身的上一次执行结果也要成功? 回答这些问题的,就是所谓的作业计划(Plan)

    而具体落到某年某月某天,一个作业什么时候真正执行一次?这一次具体的执行,就是所谓的任务执行实例(Instance)

    静态执行列表 v.s. 动态执行列表

    回头继续讨论,所谓的静态执行列表流派,是说一个作业的具体执行实例,是跟据作业计划提前计算并生成执行列表的,然后调度系统按照这个提前生成的执行列表去执行任务。 更进一步,有些系统实际上压根就没有区分作业计划和任务执行列表,两者是和二为一的,人工定义一个确定了依赖和先后关系任务列表,定期执行这整个列表。

    对于实际有作业计划和执行列表之分的系统,常见的做法是在头一天晚上接近凌晨的时候,分析所有作业的时间要求和作业间的依赖关系,然后生成下一天所有需要执行的作业的实例列表,将具体每个任务实例的执行时间点和相互依赖关系固化下来。调度系统执行任务时,遍历检查这个列表,触发满足条件的任务的执行。

    oozie,azkaban和大多数公有云上的workflow服务,和我司的第一代Jarvis调度系统,基本上都是属于这个流派。其中oozie,azkaban基本采用的是作业计划和执行列表一体的方案,我司的Jarvis一代采用的是两者分离,由作业计划定期生成执行列表的方案。

    然后,所谓的动态执行列表流派,是说某个作业的具体执行实例,并没有提前固化计算出来,而是在它的上游任务(纯时间周期任务的话就是上个周期的任务)执行完毕时,根据当时时刻点最新的作业计划和依赖关系动态计算出来的。

    zeus,chronos和我司的第二代Jarvis调度系统,基本上是属于这个流派的。

    这两个流派没有绝对的优劣之分,各有优缺点,各有自己擅长处理的场景和不擅长处理的场景,所以有时候系统的具体实现也不完是绝对互斥的,在某些功能方面也是有变化取舍的。

    那么,为什么会有两种流派?提前生成执行列表还是需要的时候再生成,又有什么关系吗?两种流派各自的主要问题和难点是什么?

    罪恶之源



    之所以会有两种流派,问题的源头在于,作业计划和执行实例列表,这两者服务的对象不同。

    从周期性作业管理的角度来说,你面向的对象当然应该是作业计划,当你想改变一个周期性作业的执行策略时,你修改的是作业的执行计划本身。而做为调度系统,在具体任务的执行过程中,它面向的对象则是任务的一次执行实例,而非计划本身。

    所以当计划产生变更时,就涉及到作业计划和执行列表之间的同步问题。

    对于静态执行列表流派来说,处理确定的任务执行列表是它的长项,因为执行列表一旦生成,那你就可以对它进行任意的修改,可以进行各种Hack,不再需要考虑原有的作业计划依赖关系等等。比如你今天想临时跳过一部分任务的执行,直接把它们从实例列表中删除,并从下游任务的依赖列表中移除依赖关系就好。

    而对于动态执行列表流派来说,这种临时的Hack动作就会比较难处理,因为计划和实例是根据规则强关联的。要影相今天的任务实例,可能就要修改作业的计划,而修改了计划,后续比如明天的任务实例也可能会受到影响。

    但是,对于执行实例或者具体实例的依赖关系难以提前确定和生成的场景,比如不等周期的依赖(比如月底的月任务依赖于每天的日任务)或者任意成功条件即可触发,触发实例个数不确定的情况,就几乎无法提前生成静态的执行列表克。

    再比如在一些短周期任务计划变更,或者任务依赖关系调整,任务列表已经有部分任务执行完毕的情况下,静态执行列表方案能否快速,正确的更新执行列表, 都会遇到很大的挑战。

    再比如,一天的所有任务中,有些任务的修改是临时的,有些任务的修改是长期的,这种情况下,静态执行列表的方案因该如何应对呢? 对于计划和执行列表一体的系统,几乎是没法做的,只能再复制生成一份临时执行列表,却别对待。而对于从计划列表定时生成执行列表的系统,则势必需要部分修改已实例化的任务执行列表,部分修改未实例化的作业计划,在这种模式下,如何保证两边的修改不冲突,如果冲突,以谁为主,甚至能否发现冲突,往往都是很困难的。

    小结

    所以,简单总结来说,静态执行列表方案,擅长处理时间范围确定的(最好是当前周期的),已知的,一次性的任务变更,前提是你对如何Hack执行列表有清楚的认识。动态执行列表方案擅长处理尚未发生的,长期的计划变更,对于不等周期和短周期任务的变更时效性也会好很多,临时的一次性变更则需要通过其它方式来辅助完成。

    当然,这两种流派针对自己不擅长的场景,多少也能找到各种的补救手段来应对,并非完全一筹莫展,只是补救手段的复杂程度和代价大小的问题。

    这两种流派,我们都实践过,总体看来,静态执行列表方案,系统架构相对简单,系统运行逻辑相对直白,容易分析问题,但是能处理的场景也比较有限。动态执行列表方案,能覆盖的场景范围更广,计划变更响应更及时,但是系统架构实现相对复杂,运行逻辑也更加复杂,牵扯的因素较多,有时候不容易一眼理顺逻辑。

    所以,如果是在业务场景比较简单,任务依赖容易理清的场景下,静态执行列表方案的系统维护代价会比较小,反之,则应该考虑构建动态执行列表方案的系统。

    最后,这两种方案也并非完全互斥,我司的jarvis二代调度系统,就在一些局部功能中使用了静态执行列表的思想,来辅助处理一些动态执行列表方案比较难应对的问题。比如,用户需要知道今天有哪些任务将要执行,什么时候执行,这就会需要一个实例化的执行列表,总不能跟用户说我们的任务是动态实例化的,所以还没有执行的任务无法展示吧 :)

    工作流调度系统功能特性和需求分析




    谈完心法再来谈谈招式,不论流派如何,最后落实到系统实现,从系统的角度,需要考虑具备哪些特性,可以提高稳定性,降低管理维护成本,从用户的角度,关心的则是能够提供哪些功能,可以提高工作效率,降低开发使用成本。

    工作流的定义方式

    既然是工作流调度系统,用户首先要面对的问题,当然是如何定义和管理工作流。

    静态显式定义和管理工作流

    多数静态执行列表流派的系统,比如oozie,azkaban以及各种公有云的workflow服务,都会包含创建工作流Flow这样一个过程,用户需要定义一个具体的作业流程里面都包含哪些作业,他们的先后依赖关系如何。所不同的是,用户通过什么手段来定义和描述这个工作流:

    比如oozie要求用户提供XML文件(也可以通过API提交),按照规定的格式描述各个工作流的拓扑逻辑和Job的依赖关系,各种任务类型的细节配置等等。

    Azkaban要求用户定义.job文件来描述作业的依赖关系,然后为每个没有依赖关系的作业及其下游作业创建一个工作流,如果要嵌套子工作流,则需要显式的申明和创建。然后将所有的.job文件和作业执行需要的依赖打包成zip包通过服务器上传,最终在服务器上创建出工作流并展示给用户。

    oozie和Azkaban采取的这两种方式,从系统设计的角度来说,对外部系统的关联和依赖比较小,是一个相对独立封闭的环境,演进起来比较自由。但这两个系统最大的问题是,周边的运维使用工具太过缺乏,易用性很差。作为工具使用可以,但是做为平台服务,缺失了太多内容,工作流的定义和维护成本太高。所以有很多公司是在oozie和Azkaban的基础上对工作流的提交管理进行了二次开发封装,来降低使用难度。

    而各种公有云的workflow服务,则多半是通过图形化拖拽作业节点的方式,来让用户显式的定义工作流,本质上和oozie的方式没有太大区别,只是通过可视化的操作来屏蔽配置的语法细节,降低工作流定义的难度。

    动态隐式定义和管理工作流

    Chronos,Zeus和我司的两代Jarvis调度系统,走的则是另一条路。系统中并没有让用户显式的定义一个工作流。实际上,这些系统的管理维度是作业,用户定义的是作业之间的依赖关系,哪些作业构成一个工作流,系统实际上并不关心,用户也不需要申明,系统只负责按规则将所有满足条件的任务调度起来,将一批任务圈定成一个Flow这种行为,对系统来说并非必需。你甚至可以理解为整个系统里的所有作业就是一个多进多出并发执行的大Flow。

    对比

    你要问那比如权限隔离,调度配置这些,没有了Flow的概念怎么处理? 事实上,这些概念和一组任务的执行链路这个概念压根就没有必然的关系。Flow关注的是的依赖关系,其它上面提到的那些概念关注的是资源的管控,这两者涉及的对象可以重叠,但是并非一定要重叠,有些时候也不适合重叠。

    那两种处理方式各有什么优缺点呢?

    显式定义工作流Flow这种方式,优点是用户明确的知道哪些任务是一组的,适合处理工作流内作业规模较小,工作流之间的作业没有交叉依赖,不会频繁变更的场景,用户的掌控感可能较强,但是反之,作业规模大,关联复杂,变更频繁的场景实际上是不太适合的,另外对依赖和触发逻辑的支持,局限性也较大(下一节详解)

    而不显式定义工作流的方式,用户无需理会和手工定义和处理工作流这个概念,使用灵活,作业之间依赖变更,业务调整等行为,都会自动反映到整体的任务执行流程中,对于用户而言,管理的压力较小,作业流程变更操作简单。相对不足的地方是作业的分组这个概念没有Flow来承接,资源的管理需要通过其它方式来实现。

    作业运行周期的管理

    显式静态定义工作流的系统,对作业运行周期的管理,通常都是以整个工作流为单位来定义和管理的。当调度时间到达时,启动整个工作流,工作流内部的作业按照依赖关系依次执行。所以如果一个工作流内部存在需要按不同周期进行调度的作业,就会很难处理,需要想各种补救手段去间接规避,比如拆分工作流,创建子工作流,或者复制多份作业等。

    非显式动态定义工作流的系统,对作业运行周期的管理,通常是以单个作业为单位的(因为压根就没有固定的Flow这个单位可以管理 ),所以用户只需要按需定义自己作业的运行周期就好了。相对的,对调度系统开发者来说,实现的难度会比较大,因为正确的自动判定依赖触发关系的逻辑会比较复杂。

    作业依赖关系的管理



    在开始讨论依赖管理之前,我们先来看看通常用做判断一个作业的具体任务实例是否可以开始运行的条件都有哪些?

    首先当然是时间依赖,大量的定时触发任务,依托时间来判断是否满足运行条件。其次是任务依赖,需要根据前置任务的执行情况,来决定当前任务是否满足运行条件。

    通常情况下,这两种依赖条件构成了大多数调度系统启动任务运行的核心判定依据。但是有时候还有第三种依赖条件,就是数据依赖,通过判断任务运行所依托的数据是否存在来决定是否启动任务。

    理论上,如果所有生成数据的任务的运行状态和结果都能被调度系统所控制或者感知,那么数据依赖这种依赖关系就是一个伪命题,既非必要,往往也不是最佳解决方案。

    为什么这么说?因为数据依赖意味着对调度系统而言,业务逻辑不再是透明的,一方面,你需要知道获取数据信息的途径,另一方面,如何判定一个任务依赖的数据是否完备了,本身也不是一件容易的事,容错性往往也不好。

    比如你通过文件是否存在来判断,那么文件里的内容是错的呢?或者生成文件的任务跑了一半失败了,文件内容不完整呢?即使你能保证文件的正确性和原子性,那么如果上游任务重跑刷新了数据呢?你如何判定这种情况?

    总体来说,个人认为,一个调度系统,如果对数据依赖这种依赖关系依托得越多,那么相对来说整个系统就越不成熟和完备,需要人工干涉的可能性越高。当然,事事无绝对,也有一些使用数据依赖才是最合理有效的解决方案的场景。而且,退一步说,调度系统再完善,也是一个有边界的系统,总难免一些依赖要通过外部数据的判定来实现。

    回头继续讨论作业依赖关系的管理

    对于采用人工显式定义工作流的系统而言,作业依赖的管理,在很大程度上,其实是通过对工作流的拓扑逻辑的管理来实现的,用户改变工作流的拓扑逻辑的过程,实际上也就改变了作业间的依赖关系。 而作业的任务依赖关系,其边界,基本上就是在当前的工作流范围之类。

    对于非显式定义工作流的系统而言,用户直接管理作业的依赖,所以这类系统一般都会提供给用户配置上游任务和触发条件的接口/界面。用户通过改变作业之间的依赖关系,间接的影响相关联作业的运行流程拓扑逻辑

    所以,你要问,这两种定义和管理作业依赖的方式,看起来只是角度不同而已,换汤不换药,采用那种,只是流程的需要,实际效果没有什么区别吧?实际上,并不完全如此,比如,从用户的角度来说:

    前面一种管理方式,需要用户对工作流内部的作业比较了解,对当前的工作流拓扑逻辑也足够清晰,才能较好的保证将新的作业安排放置到正确的位置上去。但只要满足依赖,作业节点的安排位置也可以比较自由。

    举个简单的例子,比如BC两个作业分别依赖作业A,其它没有相互依赖关系。那么,我可以把BC作业并行的放在A作业后面,也可以为了控制资源使用,让BC作业串联的放置在A后面(相当于人工将作业C改为依赖作业B)。

    而后面一种管理方式,用户只需要关心当前任务的前置任务有哪些就可以了,因此对用户的要求降低了不少。不过这样一来拓扑逻辑图是唯一且自动生成的(上例ABC作业,就只能是BC作业并行放在A作业后面),缺点是你无法自由调整工作流程,但实际上你多半也没有调整的必要。如果是为了控制作业优先级,大可通过其它方式实现

    后者还有一个很大的优势,就是如果你的任务的依赖关系可以自动分析出来的话(比如hive任务,可以通过解析脚本,自动判断上下游数据表,然后再通过数据表关联自动找到上下游任务),那么多数情况下,用户甚至都可以不用配置作业依赖关系,直接添加具体作业就完事了,工作流的拓扑关系全部交给系统自动分析,添加和调整。比如,我司的Jarvis调度系统,结合Hive元数据血缘分析工具,就基本上达到了这样的效果 ;)

    最后,用户显式定义工作流这种模式,对跨工作流的任务依赖也很难处理,原本在一个工作流内部可以通过任务依赖来实现的控制,在跨工作流以后,通常就只能通过数据依赖的手段来辅助实现了,但如前所述,这么做的话,一来用户可能需要定制数据依赖检测逻辑,二来在遇到数据重跑之类的场景,任务的正确执行就需要进一步的人工干预处理了。

    作业异常管理和系统监控



    常在河边走,哪有不湿鞋,运行作业多了,总会出问题。所以对用户来说,作业异常流程管理能力的好坏,也是工作流调度系统是否好用的一个重要考虑因素。

    比如,如果一个中间任务的脚本逻辑有错,需要重跑自身及后续下游任务,该如何处理?用户通过什么样的方式完成这件工作?需要手工重新创建一个新的工作流?还是可以通过勾选作业,自动寻找下游任务的方式实现?

    比如一个任务运行失败,但是结果数据通过其它手段进行了修复,那么如何跳过该任务继续运行后续任务?

    再比如,任务失败是否能够自动重试?重试有什么前提条件,需要做什么预处理,任务失败应该报警,向谁报警?以什么方式报警?什么情况下停止报警?任务运行得慢要不要报警? 怎么知道比以前慢?多慢该报警?不同的任务能否区别对待?等等

    所有这些方面都决定了用户的实际体验和系统的好用/易用程度,同时,对系统的整体流程框架设计也可能会带来一些影响。

    开源的工作流调度系统在这些方面做得通常都相对简单,这也是很多公司二次开发改造的重点方向。

    资源和权限控制



    有人的地方就有江湖。任务多了,势必就需要进行资源和权限管控。

    最直接的问题就是,如果有很多任务都满足运行条件,资源有限的情况下,先跑哪个?任务优先级如何定义和管理?

    再退一步,你怎么知道哪些资源到了瓶颈?如果调度系统管理执行的任务类型很多,任务也可以在不同的机器或集群上运行,你如何判定哪些任务需要多少资源?哪些机器或集群资源不足?能否按照不同的条件区别管理,分类控制并发度或优先级?

    最后,谁能编辑,运行,管理一个任务?用户角色怎么定义?和周边系统,比如Hadoop/Hive系统的权限管理体系如何对接配合?

    这些方面的内容,多数的开源的工作流调度系统也做得并不完善,或者说很难做到通用,因为很多功能需要和周边系统深度配合才可能完成。

    系统运维能力

    系统的运维能力:包括是否有系统自身状态指标的监控,是否有业务操作日志,执行流水等便于分析排查问题,系统维护,升级,上下线,能否快速完成,系统是否具备灰度更新能力等等。

    总结

    工作流调度系统做为大数据开发平台的核心组件,牵扯的周边系统众多,自身的业务逻辑也很复杂,根据目标定位的不同,场景复杂度和侧重点的不同,市面上存在众多的开源方案。

    但也正因为它的重要性和业务环境的高度复杂性,多数有开发能力的公司,还是会二次开发或者自研一套甚至多套系统来支撑自身的业务需求,我司也不例外。关于我司Jarvis调度系统的架构实现,功能设定和产品方案,后续再另写一篇文章详细阐述。


    常按扫描下面的二维码,关注“大数据务虚杂谈”,务虚,我是认真的 ;)

    展开全文
  • 摘要:本文将会从最基础的调度算法说起,逐个分析各种主流调度算法的原理,带大家一起探索CPU调度的奥秘。
  • 机场指挥调度解决方案

    千次阅读 2020-11-06 17:20:26
    然而如何提高后勤人员的工作效率,有效、合理地调度各种资源,在规定的时间内,按照服务标准,完成对飞机的设备更新、燃油的补充,保证飞机的运行,成为机场地面服务迫切需要解决的问题。但是目前机场的指挥调度手段...
  • Linux的进程调度算法简介

    千次阅读 2021-07-16 09:28:57
    文章目录一、调度算法的原理和分类1.进程调度简介2.按不同需求对调度的进程分类3.调度算法分类二、使用步骤1.引入库1.引入库总结 一、调度算法的原理和分类 1.进程调度简介   进程调度的研究是整个操作系统理论的...
  • 使用Go语言开发的轻量级定时任务集中调度和管理系统, 用于替代Linux-crontab 查看文档 原有的延时任务拆分为独立项目延迟队列,小编的qq好友列表获取就是用这个做的定时任务处理。 功能特性: Web界面管理定时...
  • 调度系统,更确切地说,作业调度系统(Job Scheduler)或者说工作调度系统(workflow Scheduler)是任何一个稍微有点规模,不是简单玩玩的大数据开发平台都必不可少的重要组成部分。 除了Crontab,Quartz这类偏...
  • 处理机调度-作业调度

    2019-11-18 16:54:00
    处理机调度-作业调度 作业调度的主要目的-两个转变 1.完成作业从后备状态到执行状态的转变 2.从执行状态到完成状态的转变 作业调度的主要功能 记录系统中各作业的状况 为了从若干的作业中挑选出一个作业来投入运行,...
  • 1.2 处理机调度

    2020-05-05 19:37:51
    1.2.1 分级调度 1.2.2 作业调度 1.2.3 进程调度 1.2.4 调度算法 1.2.5 算法评价 1.2.6 实时系统调度方法 1.2.1 分级调度 作业状态及其转换 一个作业从提交给计算机系统到执行结束退出系统,一般要经历4个阶段:提交...
  • 利用四步算法解决薄板厂生产调度问题,刘洪伟,袁林艳,作为钢铁行业的一部分,薄板厂的收益很受重视,而提高生产效率是改善收益最经济有效的方法,这要求薄板厂做好生产调度工作。本文
  • 1、概述 ... 1.1、为什么需要工作调度系统 一个完整的数据分析系统通常都是由大量任务单元组成: ...为了很好地组织起这样的复杂执行计划,需要一个工作调度系统来调度执行; 例如,我们可能有这样一个需求...
  • 操作系统学习(三) —— CPU调度

    千次阅读 2021-07-20 00:26:44
    第三部分 CPU调度一、相关基本概念引入多程序设计,目的是提高计算机资源利用率,尤其是CPU利用率(CPU utilization)。(前面所讲的多程序和多任务的目的就是让多个进程竞争使用资源,从而使CPU利用率提高。)CPU密集 ...
  • 调度员考试题库.doc

    2021-06-16 08:38:07
    调度员考试题库调度基本知识题库一、填空题1、从“调度”字面上解释,调整、调节、调配称之为“调”, 尺度、权衡称之为“度”。2、当生产现场出现透水、发火、进回风道冒顶、瓦斯超限、主扇故障、主副井提升设备...
  • 日期 内核版本 CPU架构 作者 2019.04.06 Linux-5.0 ...时钟中断是系统中调度和抢占的驱动因素,在时钟中断中会进行进程运行时间的更新等,并更新调度标志,以决定是否进行调度。下面以Pow...
  • 进程的状态、切换、调度: 进程的唯一表征——进程控制块: 标识符:包括此进程的标识符,创建此进程的父进程标识符,用户标识符。 用户可见寄存器。 控制和状态寄存器:包括程序计数器、条件码(最近的运算的结果)...
  • 【Linux】Linux 2.6 对调度器的改进

    万次阅读 2018-07-30 19:21:04
    从进程调度的角度来看,Linux2.6之前的版本有如下的缺点: 由于只设置了一个进程就绪队列,于是在一轮调度中先耗尽时间片的进程虽然已经无法取得处理器控制权,但是还要参与weight值的计算,导致白白浪费了处理器的...
  • golang调度学习-调度流程

    千次阅读 2019-06-20 17:06:29
    调度过程 以下就将会详细介绍golang的调度流程,方便阅读,将会省略部分无关代码。 初始化 调度器的初始化从 schedinit()函数开始,将会设置m最大个数(maxmcount)及p最大个数(GOMAXPROCS)等 func schedinit() { ...
  • 嵌入式操作系统RTOS任务调度原理分析,基于Cortex-M内核
  • 云计算并非无中生有的概念,它将普通的单台PC计算能力通过分布式调度软件连接起来。其最核心的问题是如何把一百台、一千台、一万台机器高效地组织起来,灵活进行任务调度和管理,从而像使用单台机器一样方便地使用多...
  • 引言作为资深的DBA同胞你是否在工作中也存在这样的情况呢?公司要搭建数据平台,首要的...那么如何做好两个数据库之间、不同类型的数据库之间的相互迁移转换呢?今天小编就常用的数据库同步、迁移转换工具进行一个汇...
  • 调度系统批量重跑任务的思考

    千次阅读 2021-01-29 14:35:05
    调度系统中总会遇到这种场景,上游任务出现数据问题,数据缺失,数据重复。这些问题出现的原因有很多,比如上游业务问题,升级某一调度组件测试覆盖不全面,代码bug等。 出现问题的原因,问题的修复,系统针对问题...
  • 比如在保证最终一致性的场景中,往往利用定时任务调度进行一些比对工作;比如一些定时需要生成的报表、邮件;比如一些需要定时清理数据的任务等。 正常使用任务调度,我们都要开发管理界面,方便监控和配置。而XXL-...
  • 所谓作业调度是指按照某种原则,从后备作业队列中选取作业进入内存,并为作业做好运行前的准备工作以及作业完成 后的善后处理工作。设计作业调度算法时应达到如下目标: (1) 某段时间内尽可能运行更多的作业,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 35,714
精华内容 14,285
热门标签
关键字:

如何做好调度工作