Scheduling调度
调度有两个方面：
1）如何从一个进程切换到另一个进程
2）下一个应该运行什么进程
机制：上下文切换（如何切换）
机制：抢占（保持控制）
策略：调度（切换到哪里）
上下文切换是一种允许操作系统存储当前进程状态并切换到另一个先前存储的上下文的机制。
上下文切换的原因：
进程完成/退出
进程执行缓慢的硬件操作（例如，从磁盘加载）并且操作系统切换到另一个就绪任务
硬件需要操作系统帮助并发出中断
操作系统决定抢占该任务并切换到另一个任务（即该进程已用完其时间片）
异步返回的函数调用：进程A开始执行上下文切换，但进程B在函数返回后继续执行。
该函数将所有寄存器保存在暂存区域（在进程的内核堆栈上或任务结构的预定义区域中）。
操作系统切换地址空间。
该函数从暂存区恢复所有寄存器。
操作系统返回到进程B。
如果任务从未放弃控制权 (yield())、退出或执行 I/O，那么它可以永远运行，并且操作系统无法获得控制权。
因此，操作系统在调度进程之前设置一个计时器。如果定时器到期，硬件就会中断进程的执行并切换到内核。然后内核决定该进程是否可以继续。
上下文切换机制负责内核如何从一个进程切换到另一个进程，即通过存储其上下文并恢复另一个进程的上下文。调度策略决定接下来应该运行哪个进程。如果只有一个“就绪”进程，那么答案很简单。如果有更多进程，则策略决定进程的执行顺序。
在分析调度程序策略时，我们使用以下术语：
利用率：CPU 执行程序的时间比例（目标：最大化）
周转时间：完成作业所需的总时间，$T_{completion} − T_{arrival}$（目标：最小化）
响应时间：从作业到达到第一次调度的时间，$T_{firstrun} - T_{arrival}$（目标：最小化）
公平性：所有进程随着时间的推移获得相同数量的 CPU（目标：无饥饿）
进度：允许进程向前推进（目标：最小化内核中断）
让我们逐步了解调度策略。我们从一些简化假设开始
每个作业的运行时间相同
所有作业在同一时间到达 一旦启动，每个作业都会运行到完成
所有作业只使用 CPU（无 I/O）
作业的运行时间已知
调度的三个层次
高级调度
按一定原则从外存的作业后备队列中挑选一个作业调入内存，并创建进程。每个作业只调入一次，调出一次。作业调入时会建立PCB，调出时才撤销PCB。
中级调度
内存中暂时调到外存等待的进程状态为挂起状态。被挂起的进程PCB会被组织成挂起队列
中级调度按照某种策略决定将哪个处于挂起状态的进程重新调入内存。
低级调度（进程调度）
按某种策略从就绪队列中选取一个进程，将处理机分配给它。进程调度是操作系统中最基本的一种调度，进程调度的频率很高，一般几十毫秒一次。
进程调度的时机
- 当前进程主动放弃处理机
- 当前进程被动放弃处理机
不能进行进程调度与切换的情况：
进程调度的方式
- 非抢占式
- 抢占式：优先处理更紧急的进程
进程切换的过程：
- 对原来运行进程各种数据的保存
- 对新的进程各种数据的恢复
进程切换是有代价的
调度程序
决定让谁运行，以及运行多长时间
抢占式调度策略在时钟中断时唤醒调度程序
闲逛进程（idle）：
- 优先级最低
- 可以是0地址指令，占一个完整的指令周期
- 能耗低
CPU利用率
利用率=忙碌的时间/总时间
周转时间：作业被提交给系统开始，到作业完成为止需要的时间。包括四个部分：
- 作业在外存后备队列上等待作业调度（高级调度）的时间
- 进程在就绪队列上等待进程调度的时间
- 进程在CPU上执行的时间
- 进程等待I/O操作完成的时间
平均周转时间：各作业周转时间之和/作业数
等待时间：进程处于等待处理机状态时间之和
响应时间：用户从提出请求到首次产生响应所用的时
调度算法
先来先服务（FCFS）
按照到达的先后顺序，等待时间越久的越先得到服务。
例题：
非抢占式算法
优点：公平，算法实现简单
缺点：排在长作业（进程）后面的短作业需要等待很长时间，带权周转时间很大。即FCFS算法对长作业有利，对短作业不利。
不会导致饥饿
短作业优先（SJF）
每次调度时选择当前已到达且运行时间最短的进程。
例题：
非抢占式算法
抢占式的短作业优先算法：最短剩余时间优先算法（SRTN/STCF）
每当有进程加入，就绪队列改变时就需要调度，如果新到达进程的剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前进程回到就绪队列。
例题：
未特别说明，短作业优先算法默认是非抢占式的。
在所有进程都几乎同时到达时，采用SJF算法的平均等待时间、平均周转时间最少。
抢占式的短作业优先算法的平均等待时间、平均周转时间最少。在所有进程同时到达时，SJF算法等同于抢占式SJF算法。
缺点：可能产生饥饿现象。短作业友好，长作业不友好。
高相应比优先（HRRN）
在调度时计算每个进程的相应比，选择相应比最高的进程为其服务。
非抢占式算法
例题：
综合考虑了等待时间和运行时间
避免了长作业饥饿的问题
时间片轮转（RR）
按各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片（如100ms）。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。
抢占式算法
如果时间片太大，使得每个进程都可以在一个时间片内完成，则时间片轮转调度算法退化为先来先服务算法，并且会增大进程相应时间。
如果时间片太小，会导致进程切换过于频繁。
优先级调度算法
每个进程都有各自的优先级，调度时选择优先级最高的进程。
有抢占式和非抢占式。
会导致饥饿
多级反馈队列调度算法（MLFQ）
设置多级就绪队列，各级队列优先级从高到低，时间片从小到大。
新进程到达时先进入第一级队列，按FCFS原则排队等待被分配时间片。若用完时间片进程还没结束，则进程进入下一级队列队尾。如果此时已经在最下级队列，则重新放回最下级队列队尾。只有在第k级队列为空时，才会为k+1级队头的进程分配时间片
抢占式算法。在k级队列的进程运行过程中，若更上级的队列中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回k级队列队尾。
完全公平调度器（CFS）
对于n个正在运行的任务，当这些任务同时不断地运行时，CPU会尽可能分配给他们1/n的处理时间。CFS是一种基于加权公平排队思想的调度算法
实现：将所有进程保留在红黑树中，按最大执行时间排序（跟踪其正余额） 调度 调度最左边的进程（余额最高的进程） 如果进程退出，则将其从调度树中删除 中断时（时间片或 I/O 结束），将进程重新插入树中的新位置
红黑树是一种特殊的二叉搜索树，也就是左边节点都小于根节点都小于右边节点，递归整个树都满足这一点。也就是说最左边的叶子节点是最小的，最右边的叶子节点是最大的。红黑树相比二叉搜索树多了红色黑色两个颜色的宏定义,红黑树有以下5个性质：
每个结点要么是红的要么是黑的。
根结点是黑的。
每个叶结点都是黑的。
如果一个结点是红的，那么它的两个儿子都是黑的。
对于任意结点而言，其到叶结点的每条路径都包含相同数目的黑结点。
- CFS使用红黑树结构，来存储要调度的任务队列。
- 每个节点代表了一个要调度的任务，节点的key即为虚拟时间（vruntime），虚拟时间由这个人物的运行时间计算而来。
- key越小，也就是vruntime越小的话，红黑树对应的节点就越靠左。
4. CFS scheduler每次都挑选最左边的节点作为下一个要运行的任务，这个节点是“缓存的”——由一个特殊的指针指向；不需要进行O（logn）遍历来查找。也因此，CFS搜索的时间是O(1)。