schedule
进程调度是操作系统最重要的内容之一, 也是最不好理解和调试的部分之一, 尤其在多线程多进程多处理器的情况下. 本文试图系统的介绍整个过程
什么是调度?
操作系统的作用之一就是系统资源管理器.CPU作为计算机系统中最重要的资源, 所有进程的运行都需要CPU, 对CPU进行时间分割管理的具体做法就叫做进程调度.
那么调度的是什么呢? 我们知道进程是资源分配的单位,线程是执行的单位.早期的时候没有多线程, 此时进程调度调度的是进程.但是当有了多线程之后,线程变成了执行的单位,进程不再是执行的单位,进程调度调度的就是线程了.
不过由于历史原因,大家都习惯叫进程调度,所以现在这个领域的名称还是叫进程调度.后文中说到调度进程的地方都是调度的线程,由于习惯问题,我们还说调度进程不说调度线程,请大家要注意.
调度可以有两种方式:
- 一种是直接调度线程,不考虑它们所属的进程,这种方式叫做直接调度或者一级调度;
- 另一种是先调度进程,再在进程内部调度线程,这种方式叫做间接调度或者二级调度.
POSIX规定,操作系统可以选择这两种方式中的任何一种都行.Linux选择的是一级调度,主要是为了提高进程的并发性,充分利用多CPU多核的优势.如果使用二级调度的话,看似每个进程之间都公平了,但是有些进程的计算量比较大,就无法通过多开线程提高自己的性能,这样对系统整体的性能是有害的,也不利用发挥计算机多CPU的优势.一级调度看似对有些进程不公平,但是计算量小的进程少开线程,计算量大的进程多开线程,相对还是很公平的.
尽管一级调度可能导致某些进程对CPU资源的过度占用,但Linux引入了cgroups(控制组)来管理和限制进程组的资源使用,从而解决了这个问题, 详见 cgroup
为什么要调度?
在讨论为什么要调度之前, 我们不妨设想一下没有调度会怎么样呢?
最早的计算机是没有调度的,程序只能一个一个地运行,一个进程死亡(结束)之后才能去运行下一个进程.这里面首先存在的问题就是我们没法同时运行多个进程.其次, 就算我们不需要同时运行多个进程,程序在运行的过程中如果要等IO,CPU就只能空转,这也十分浪费CPU资源.
于是最早的多任务: 协作式多任务诞生了,当程序因为等待IO而阻塞时就会去调度执行其它的进程.但是协作式多任务存在着很大的问题,就是每个进程运行的时间片长短是不确定的,而且是很偶然很随机的.如果一个进程它一直在做运算而不进行IO操作,那么它就会一直霸占CPU.针对这个问题,当时想出的方法是道德解决方案.内核向进程提供系统调用 sched_yield,它会使进程主动放弃CPU让其它进程来执行.然后要求所有的程序员在程序中合适的地方尽量多地加入 sched_yield 调用.这个方法在当时是管用的,因为当时计算机的使用者(同时也是程序员)仅限于少数科研机构和政府机关的部分人员,一台电脑的共同使用者都认识,面子上还得过得去.
后来随着计算机的普及,以及计算机的使用者和程序员这两个角色的分离,主要靠道德约束的协作式多任务已经行不通了,我们需要强制性多任务,也就是抢占式多任务.抢占式多任务使得每个进程都可以相对公平地平分CPU时间,如果一个进程运行了过长的时间就会被强制性地调度出去,不管这个进程是否愿意.有了抢占式多任务,我们在宏观上不仅可以同时运行多个进程,而且它们会一起齐头并进地往前运行,不会出现某个进程被饿死的情况,这样我们使用电脑的体验就非常完美了.抢占式多任务和协作式多任务不是对立的,它们是相互独立的,可以同时存在于系统中.
抢占又分为用户抢占和内核抢占.由于抢占对进程来说是异步的,进程被抢占时不一定运行在什么地方,有可能运行在用户空间,也有可能运行在内核空间(进程通过系统调用进入内核空间).如果抢占点是在用户空间,那么抢占就是安全的; 如果在内核空间就不一定安全, 因为对于用户空间来说,如果抢占会导致线程同步问题,那么用户空间有责任使用线程同步机制来保护临界区,只要用户空间做好同步就不会出问题.如果内核也做好了同步措施,内核抢占也不会出问题,但是内核最初的设计就没有考虑内核抢占问题,所以刚开始的时候内核是不能抢占的.后来内核开发者对内核进行了完善,把内核所有的临界区都加上了同步措施,然后内核就是可抢占的了.
内核能抢占了不代表内核一定会抢占,内核会不会抢占由config选项控制(
CONFIG_PREEMPT),可以开启也可以关闭,因为内核抢占还会影响系统的响应性和性能.开启内核抢占会提高系统的响应性但是会降低一点性能,关闭内核抢占会降低系统的响应性但是会提高一点性能.因此把内核抢占做成配置项,可以让大家灵活配置.
服务器系统一般不需要与用户交互,所以会关闭内核抢占来提高性能,桌面系统会开启内核抢占来提高系统的响应性,来增加用户体验.
因此进程调度的目的就在于实现多任务, 让各个进程相对公平的占有 CPU
为什么能调度?
我们把协作式多任务叫做主动调度,抢占式多任务叫做被动调度.
一般来说主动寻求调度很少, 大部分都是被动调度
对于主动调度,调度是进程主动触发的,例如使用 sched_yield; 对于被动调度,在图灵机模型中是做不到的,因为图灵机是一条线性一直往前走的,进程在执行时,进程要是不主动,是不可能跳到其它进程来执行的.被动调度能做到的原因关键就在于中断机制,因为中断是强行在正常的执行流中插入了一段代码,它能改变后续代码的走向.有了中断机制,我们就可以创建一个定时器中断,以固定的时间间隔比如每10ms来触发中断,检测进程是否运行时间过长,如果过长就触发调度.这样任何进程都不可能霸占CPU,所以进程都能公平地共享CPU时间.这里引用其中的一幅图来看一下:
可以看到在纯图灵机模型中,进程如果不主动进行调度,是没有外力强迫进程进行调度的,进程就能一直霸占CPU.有了中断机制之后,在中断的处理中可以触发调度,在中断返回的点可以执行调度,这样就可以避免进程霸占CPU了.
关于中断详见 中断
何时调度
对于主动调度,触发调度和执行调度是同步的、一体的,触发即执行.主动调度发生的时机有IO等待、加锁失败等各种阻塞操作以及用户空间主动调用 sched_yield.
对于被动调度,触发调度和执行调度是异步的、分离的,触发调度并不会立马执行调度,而是做个需要调度的标记(设置 TIF_NEED_RESCHED),然后在之后的某个合适的地方会检测这个标记,如果被设置就进行调度.
简而言之, 主动调度: 触发调度 == 执行调度, 被动调度: 先触发调度, 然后等到执行调度的时刻进行调度
触发调度的点有:
- 在定时器中断中发现当前进程超时了
- 在唤醒进程时发现新进程需要抢占当前进程,
- 在迁移进程时发现新进程需要抢占当前进程
- 在改变进程优先级时发现新进程需要抢占当前进程.
其中第一个触发点是当前进程需要被抢占,它是用来保证公平调度,防止进程霸占CPU的,后三个触发点是新进程需要抢占当前进程,它是用来提高系统响应性的.
执行调度的点有:
- 中断/异常/系统调用完成, 即将返回用户空间之前
- 如果开启了内核抢占的话,中断完成之后即将返回内核
- 如果中断发生在禁止抢占临界区中,那么中断完成之后返回内核是不会执行调度的,而是会在临界区结束的时候执行调度.
由内核返回用户空间之前是非常好的执行进行调度的点, 因为此时刚刚进入内核态处理完成相应的中断/异常/系统调用, 内核可以直接进行调度而不需要单独为了调度进程而从用户态陷入内核.
如果执行位于内核临界区, 比如对于链表节点的增删, 此时需要等待内核完成对应的全部的操作并离开临界区后才会执行调度
如何调度
执行调度包括两部分:选择进程和切换进程.选择进程是通过内核的算法实现的; 进程切换主要是切换执行栈和用户空间,这两个都需要用到CPU特定的指令, 需要软硬件同时结合才可以做到, 现有的 CPU 都支持了这个过程
选择进程需要通过调度算法来实现, 会根据进程不同的状态来选择, 下文进行详细介绍
// include/linux/sched.h
/* 用于 tsk->__state 的标志位 */
#define TASK_RUNNING 0x00000000 // 任务正在运行
#define TASK_INTERRUPTIBLE 0x00000001 // 任务可被中断
#define TASK_UNINTERRUPTIBLE 0x00000002 // 任务不可被中断
#define __TASK_STOPPED 0x00000004 // 任务已停止
#define __TASK_TRACED 0x00000008 // 任务被跟踪
/* 用于 tsk->exit_state 的标志位 */
#define EXIT_DEAD 0x00000010 // 进程已经死亡
#define EXIT_ZOMBIE 0x00000020 // 进程处于僵尸状态
#define EXIT_TRACE (EXIT_ZOMBIE | EXIT_DEAD) // 进程处于跟踪状态,同时是僵尸状态
/* 再次用于 tsk->__state 的标志位 */
#define TASK_PARKED 0x00000040 // 任务处于挂起状态
#define TASK_DEAD 0x00000080 // 任务已死亡
#define TASK_WAKEKILL 0x00000100 // 任务被唤醒并准备被杀死
#define TASK_WAKING 0x00000200 // 任务正在被唤醒
#define TASK_NOLOAD 0x00000400 // 任务不应被调度
#define TASK_NEW 0x00000800 // 任务是新创建的
#define TASK_RTLOCK_WAIT 0x00001000 // 任务正在等待实时锁
#define TASK_FREEZABLE 0x00002000 // 任务可以被冻结
#define __TASK_FREEZABLE_UNSAFE (0x00004000 * IS_ENABLED(CONFIG_LOCKDEP)) // 任务可以被冻结,但可能不安全
#define TASK_FROZEN 0x00008000 // 任务已被冻结
#define TASK_STATE_MAX 0x00010000 // 任务状态的最大值进程选择好了之后就要切换进程了.切换进程分两步:第一步是切换用户空间,第二步是切换执行栈(线程栈).
切换用户空间是一个CPU架构相关的事情,在x86 CPU上是给 CR3 寄存器赋值新进程的页表树的根指针.此时切换的执行栈是线程的内核栈,执行栈代表的是当前线程的执行情况,切换执行栈就是切换线程.线程的用户栈信息都在内核栈里保存着.切换完内核栈之后,线程继续执行就会返回用户空间,由于此时用户空间已经切换完成,内核栈上也保存着用户栈的信息,所以线程能返回到正确的用户空间线程上去.
如果要切换的两个线程属于同一个进程就不需要切换用户空间了.
这里有关进程/线程切换的文字表述含义前文已经说明, 加入线程概念之后实际上操作系统做的是线程的管理和切换, 不过由于历史原因,大家都习惯叫进程调度,所以现在这个领域的名称还是叫进程调度
调度均衡
前面所说的都是针对一个CPU的情况,对于多个CPU来说,每个CPU也是这样的逻辑.但是有一点不同的是,如果一个系统上的多个CPU忙的忙死闲的闲死,显然不太好,因此多个CPU之间会进行调度均衡.
调度均衡可以分为个体均衡和总体均衡.个体均衡是从进程的角度出发选择到一个相对清闲的CPU上去运行.总体均衡是从CPU的角度出发如何从别的CPU上拉取一些进程到自己这来执行,使得所有CPU的工作量尽量平均.
个体均衡的触发点有三个:
- 新进程刚创建时
- 进程要执行新程序时
- 进程被唤醒时
在这三个点进程都可以选择去哪个CPU的运行队列上去等待执行.在个体均衡下,每个进程都尽量选择相对清闲的CPU,所以所有CPU的负载应该还是会比较均衡的.但是时间长了可能还是会出现负载不均衡的情况,此时就要进行总体均衡了.
总体均衡的触发点有三个:
- CPU即将idle前会去找到最忙的CPU然后拉取一些任务过来
- 定时器中断的周期性检测,会检查是否所有的CPU都一样忙,如果忙闲差别太大就会进行进程迁移,使得所有CPU忙闲程度接近
- idle进程中如果CPU发现自己太忙而有的CPU在idle就会唤醒那个CPU进行负载均衡.
调度器评价
狭义的调度器指的是具体的调度算法,广义的调度器指的是整个调度体系.不过两者的评价指标是相同的,所以我们这里不具体区分调度器是指调度算法还是调度体系.调度器的评价指标有以下几个:
- 响应性,当一个进程发生事件需要去处理的时候能否及时被调度.这一点和使用体验是密切相关的,当我们用鼠标点击一个程序的时候,肯定希望程序立即能做出响应,如果程序过了好几秒才有反应,那我们肯定会很烦的.
- 吞吐量,系统在相同的时间内能够运行更多的程序、执行更多的指令.这个首先要求调度器本身的代码要尽量的高效.如果调度器写得非常复杂,运行一次就需要好几毫秒的话,那留给进程运行的时间就不多了.其次进程调度的频率要低,如果进程调度的频率比较高的话,那调度器执行的次数就比较多,从而占用了较多的CPU时间,而且频繁切换进程也会影响缓存的性能.从这一点来看响应性和吞吐量是有矛盾的,提高响应性会增加进程切换的频率,而这会降低系统的吞吐量.
- 公平性,指的是相对公平性,每个进程实际获得的时间份额与应当获得的时间份额都相差不大.不会出现有些进程饥饿的情况,也不会出现有些进程获得过多时间份额的情况.
- 适应性,指的是系统无论是调度几个进程还是调度几万个进程,都能撑得住,都能收放自如,各项指标都不能受到太大的影响.
我们根据必须做出决策的频率来区分长期计划、中期计划和短期计划
长期调度程序或准入调度程序决定哪些作业或进程将被接入就绪队列(在主内存中);也就是说,当尝试执行程序时,长期调度程序会授权或延迟其进入当前正在执行的进程集.因此,此调度程序决定了要在系统上运行的进程、任何时候要支持的并发程度 - 是要同时执行多个还是几个进程,以及如何处理 I/O 密集型进程和 CPU 密集型进程之间的拆分.长期调度器负责控制多重编程的程度
通常,大多数进程可以描述为 I/O 受限或 CPU 受限.I/O 绑定进程是指花在 I/O 上的时间多于花在计算上的时间.相比之下,受 CPU 限制的进程很少生成 I/O 请求,而是将更多时间用于计算.长期调度程序必须选择 I/O 密集型进程和 CPU 密集型进程的良好进程组合.如果所有进程都是 I/O 绑定的,则就绪队列几乎总是空的,短期调度程序将无事可做.另一方面,如果所有进程都受 CPU 限制,则 I/O 等待队列几乎总是空的,设备将闲置,系统将再次不平衡.因此,具有最佳性能的系统将具有 CPU 密集型进程和 I/O 密集型进程的组合.在现代操作系统中,这用于确保实时进程获得足够的 CPU 时间来完成其任务
在批量处理系统、计算机集群、超级计算机和渲染农场等大型系统中,长期调度也很重要.例如,在并发系统中,通常需要对交互进程进行协调度,以防止它们因相互等待而阻塞.在这些情况下,除了操作系统中的任何基础准入计划支持外,通常还使用专用的作业调度软件来协助这些功能.
中期调度程序会暂时从主内存中删除进程,并将它们放在辅助内存(如硬盘驱动器)中,反之亦然,这通常称为换出或换入(也被错误地称为分页或分页).中期调度程序可以决定换掉一段时间未处于活动状态的进程、优先级较低的进程、经常出现页面错误的进程或占用大量内存的进程,以便为其他进程释放主内存,稍后在有更多内存可用时将该进程换回, 或者当进程已解除阻止并且不再等待资源时.
短期调度程序(也称为 CPU 调度程序)决定在时钟中断、I/O 中断、操作系统调用或其他形式的信号之后要执行哪些就绪的内存中进程(分配 CPU).因此,短期调度器比长期或中期调度器更频繁地做出调度决策_调度决策至少必须在每个时间片之后做出,而且这些时间片非常短.此调度程序可以是抢占式的,这意味着当它决定将 CPU 分配给另一个进程时,它能够从 CPU 中强行删除进程,也可以是非抢占式(也称为自愿或合作),在这种情况下,调度程序无法强制进程离开 CPU.
调度器历史
先进先出(FIFO),也称为先到先得(FCFS),是最简单的调度算法.FIFO 只是按照进程到达就绪队列的顺序对进程进行排队.这通常用于任务队列
Priority scheduling 优先级调度, 最早的截止时间优先 (EDF) 或最短时间是实时操作系统中使用的一种动态调度算法,用于将进程置于优先级队列中.每当发生调度事件(任务完成、发布新任务等)时,都会在队列中搜索最接近其截止时间的进程,该进程将是下一个要计划执行的进程.
Shortest remaining time first 最短的剩余时间优先, 类似于最短作业优先 (SJF).使用此策略,调度程序将剩余估计处理时间最少的进程安排为队列中的下一个进程.这需要对完成过程所需时间的高级知识或估计.
Fixed-priority pre-emptive scheduling 固定优先级抢占式调度, 操作系统为每个进程分配一个固定的优先级等级,调度程序按进程的优先级顺序排列就绪队列中的进程.低优先级的进程会被传入的高优先级进程中断
Round-robin scheduling 循环调度, 调度程序为每个进程分配一个固定的时间单位,并循环访问它们.如果进程在该时间片内完成,则该进程将终止,否则在给所有其他进程一个机会后,它将被重新调度.
Multilevel queue scheduling 多级队列调度, 这用于流程容易划分为不同组的情况.例如,在前台(交互式)进程和后台(批处理)进程之间进行了常见的划分.这两种类型的流程具有不同的响应时间要求,因此可能具有不同的调度需求.它对于共享内存问题非常有用