【操作系统/OS笔记10】进程/线程的调度原则、调度算法、实时调度、多处理器调度、优先级反转
本次笔记内容：
8.1 背景
8.2 调度原则
8.3 调度算法1
8.4 调度算法2
8.5 实时调度
8.6 多处理调度与优先级反转
文章目录
CPU调度背景
上下文切换
- 切换CPU当前任务，从一个进程/线程到另一个；
- 保存当前进程/线程在PCB/TCP中的执行上下文（CPU状态）；
- 读取下一个进程/线程的上下文。
CPU调度
- 从就绪队列中挑选一个进程/线程作为CPU将要运行的下一个进程/线程；
- 调度程序：挑选进程/线程的内核函数（通过一些调度策略）；
- 什么时候进行调度？
在进程/线程的生命周期中什么时候进行调度？
需要调度时，称为调度时机/调度点。
- 内核运行调度程序的条件（满足其一即可）：
- 一个进程从运行状态切换到等待状态；
- 一个进程被终结了。
- 不可抢占：（比如在内核级时不能抢占）
- 调度程序必须等待时间结束。
- 可以抢占：（比如在用户级时可以抢占）
- 调度程序在中断被响应后执行；
- 当前的进程从运行切换到就绪，或者一个进程从等待切换到就绪；
- 当前运行的进程可以被换出。
调度准则
基于什么原则选择进程执行。
进程A在进行I/O时，没有占用CPU；此时希望其他进程能有效利用CPU。使得CPU尽量的忙，充分利用资源。
评价指标
- CPU使用率：CPU处于忙状态所占时间的百分比；
- 吞吐量：在单位时间内完成的进程数量；
- 周转时间：一个进程从初始化到结束，包括所有等待时间所花费的时间；
- 等待时间：进程在就绪队列中的总时间；
- 响应时间：从一个请求被提交到产生第一次相应所发费的总时间。
评价指标间有矛盾
人们通常都需要“更快”地服务：
- 传输文件时的高带宽；
- 玩游戏时的低延迟；
- 这两个因素是独立的。
- 和水管类比：大量的水是带宽，一打开水龙头就流出是低延迟。
评价指标的期望：
- 减少响应时间：及时处理用户的输出并且尽快将输出提供给用户；
- 减少平均响应时间的波动：在交互系统中，可预测性比高差异低平均更重要；
- 增加吞吐量：减少操作系统、上下文切换的开销，并且提高系统资源的利用，如CPU，I/O设备。
- 减少等待时间：减少每个进程的等待时间。
上述指标其实是有矛盾的，比如很难同时满足响应时间和吞吐量：
- 低延迟调度增加了交互式表现：如果移动了鼠标，但是屏幕中的光标没有动，不妥；
- 但是操作系统需要保证吞吐量不受影响：我想要结束长时间的编程，所以操作系统必须不时进行调度，即使存在许多交互任务；
- 吞吐量是操作系统的计算带宽；
- 响应时间是操作系统的计算延迟。
因此，比如linux，desktop与sever应用两套不同的调度算法。
将“公平”作为重要指标
- 保证每个进程都占用相同的CPU时间；
- 这公平么？如果一个用户比其他用户运行更多的进程怎么办？
- 保证每个进程都等待相同的时间；
- 公平通常会增加平均响应时间。
调度算法
面向通用计算机的调度算法
- FCFS（First Come, First Served），先来先服务；
- SPN、SJF、SRT（Shortest Process Next、Shortest Job First、Shortest Remaining Time），短进程优先、短作业优先、短剩余时间优先；
- HRRN（Hightest Response Ratio Next），最高响应比优先；
- Round Robin，轮循，使用时间切片和抢占来轮流执行任务；
- Multilevel Feedback Queues，多级反馈队列，优先级队列中的轮循；
- Fair Share Scheduling，公平共享调度。
FCFS
如图，如果在前面的进程执行时间较长，周转时间会较长，如果用户请求后面的进程，可能会等待较长时间。
FCFS优点：
- 简单。
FCFS缺点：
- 平均等待时间波动较大；
- 花费时间少的任务可能排在花费时间长的任务后面；
- 可能导致I/O和CPU之间的重叠处理：CPU密集型进程会导致I/O设备闲置时，I/O密集型进程也在等待。
短进程优先
在FCFS中，如果把短进程排到前面，周转时间会下降。因此提出短进程优先调度算法。
如果发现某个进程比当前进程剩余时间片还短，运行该进程进行抢占，则此类算法又称：Shortest-Remaining-Time（SRT，最短剩余时间）；如果不可抢占，则放到就绪进程第一个。
如上图，可以从数学上证明SJF可以产生最优平均等待时间。
SJF问题：
- 可能导致饥饿：连续的短任务流会使长任务饥饿，短任务可用时的任何长任务的CPU时间都会增加平均等待时间；
- 需要预知未来：如何预估下一个CPU突发的持续时间？可以询问用户。但如果用户欺骗？就杀死进程。那如果用户不知道怎么办？
如上图，可以由执行历史预估执行时间。
如上图，蓝线为预测结果。
HRRN
- 在SPN调度的基础上改进；
- 不可抢占；
- 关注进程等待了多长时间；
- 防止无限期推迟。
上式中，w为waiting time等待时间；s为service time执行时间。选择R值最高的进程。
HRRN问题：
- 对抢占性的支持不够；
- 依然需要预估service time。
轮循算法
- 在叫作量子（或时间切片）的离散单元中分配处理器；
- 时间片结束时，切换到下一个准备好的进程。
上图为轮循算法的示例。
如上图，P2所需时间为8，小于20，执行结束后自动切换到下一个时间片。
RR问题：
- RR花销：额外的上下文切换；
- 时间量子过大，则等待时间过长，极限情况退化成FCFS；
- 时间量子过小，则反应迅速，但是吞吐量由于大量的上下文切换开销受到影响；（时间量子由经验决定，随着计算机性能的提升，LINUX原来设置为0.01秒，现在是0.001秒）
因此，选择一个合适的时间量子，并且维持上下文切换开销处于1%以内。
如上图，将FCFS与时间片不同的RR作对比，发现FCFS更好。这是因为Best FCFS切换上下文较少，但是没有公平性。
多级反馈队列
多级队列：
- 就绪队列被划分成独立的队列（E.g. 前台（交互），后台（批处理））；
- 每个队列拥有自己的调度策略（E.g. 前台-RR，后台-FCFS）；
- 调度必须在队列间进行：
-
- 固定优先级：先处理前台，然后处理后台，可能导致饥饿；
-
- 时间切片：每个队列都得到一个确定的能够调度其进程的CPU总时间，比如80%给使用RR的前台，20%给使用FCFS的后台。
多级反馈队列：
- 可以根据情况（反馈）调整进程的优先级、队列。
CPU密集型（时间片用的很多）每用一个时间片，降一个优先级；这样，交互性较好的进程可以排到优先级高的就绪队列中。
如此，可以区分进程在动态中反映出的特征。
FFS
- 此算法重点强调公平（多人多用户分时共享）。
- 一些用户组比其他用户组更重要；
- 保证不重要的组无法垄断资源；
- 未使用的资源按照每个组所分配的资源的比例来分配；
- 没有达到资源使用率目标的组获得更高的优先级。
评价算法的机制
如上图，可以通过建立数学模型、概率论中的队列模型、虚拟等方法。现在倾向于实现的方法进行检验，因为很多细节数模无法表达。
实际调度算法比上面提到的六种算法复杂，但也体现着其基本思想。
实时调度
实时系统
实时调度所面对的系统为Real Time System（实时系统）。工控、火车调度等规定时间必须完成的系统为实时系统。
对于实时系统：
- 时间约束的及时性（deadlines）很重要；
- 速度和平均性能相对不重要；
- 时间约束的可预测性是其主要特性。
实时系统可分为：
- 强实时系统：需要在保证的时间内完成重要的任务，必须完成；
- 弱实时系统：要求重要的进程的优先级更高，尽量完成，并非必须。
比如视频掉帧，就是弱实时系统的体现。
任务（工作单元）
- 一次计算，一次文件读取，一次信息传递等等。
如上图，蓝色为具体任务执行时间。
如上图，周期任务，任务的一种实例。
硬时限与软时限
- 硬时限：保证确定性，否则后果严重；
- 软时限：最大努力去完成。
实时调度算法
静态优先级调度
在任务执行开始前，就决定了调度顺序。
如上图，RM是一种较为经典的静态优先级调度算法。
动态优先级调度
在过程中会产生变化。
EDF是一种较为经典的动态优先级调度算法，在任务执行过程中，由任务与Deadline间隔决定该谁执行。
多处理器调度
如今，手机、台式机都是多处理器环境。
多处理器的CPU调度更加复杂：
- 多个相同的单处理器组成一个多处理器；
- 优点：负载共享。
对称多处理器（SMP）：
- 每个处理器运行自己的调度程序；
- 需要在调度程序中同步。
优先级反转
NASA发现火星探测车经常重启，最后发现是操作系统调度相关的原因。
如图，是优先级反转实例：T1优先级最高，T3最低。T3先开始执行，在t2时访问一块共享资源。t3时优先级更高的T1开始执行，执行到t4，需要访问共享资源，但是此时共享资源还在T3中，因此需要T3继续执行，执行到t5，T2开始执行，T3因此开始等待T2，T1继续等待T3。直到t7时T3执行结束，共享资源释放，T1继续执行。
如果系统认为T1断断续续，则认为不稳定，重启系统。
如上图，可以使用优先级继承的方法解决该问题。T3在t3时继承T1的优先级。
如上图，还可以使用“优先级天花板”技术，给资源也赋上优先级。