清华大学操作系统OS学习（十）——处理机调度

一、处理机调度概念

1、进程切换&＃xff08;上下文切换&＃xff09;&＃xff1a;切换CPU的当前任务&＃xff0c;从一个进程/线程到另一个&＃xff0c;保存当前在PCB/TCB中的执行上下文&＃xff0c;读取下一个的上下文

2、CPU调度&＃xff1a;从就绪队列中挑选一个进程/线程作为CPU将要运行的下一个线程/进程

3、调度程序&＃xff1a;挑选进程/线程的内核函数&＃xff08;通过一切调度策略&＃xff09;使得效率最高&＃xff0c;满足用户需求

4、在进程/线程的生命周期中的什么时候进行调度&＃xff1f;

从一个状态变为另一个状态&＃xff0c;特别是和运行&＃xff08;running&＃xff09;相关的状态。

内核运行调度程序的条件&＃xff1a;进程从运行状态切换到等待状态or终结了&＃xff08;done&＃xff09;

不可抢占调度&＃xff0c;调度必须等待事件/进程结束&＃xff0c;早期OS。

现在多为可以抢占的进程&＃xff0c;OS决定在何时打断进程&＃xff0c;调度程序在中断被响应后执行&＃xff0c;当前进程从运行切换到就绪&＃xff0c;或者一个进程从等待切换到就绪&＃xff0c;可以被换出。

5、针对的是用户态的进程。

进程在内核中通过系统调用执行&＃xff0c;因为系统调用返回时是到发起这个调用的进程继续执行&＃xff0c;所以内核中不会切换&＃xff0c;抢占。只要进程在系统调用时不存在从运行态到阻塞态的变化&＃xff0c;OS可以确保返回正常。

二、调度准则

1、处理机资源的使用模式

CPU的占用率是波状&＃xff0c;CPU大量运算是高峰&＃xff0c;而读写I/O时是平稳的低值。每个调度决定都是关于下一个CPU突发时将哪个工作交给CPU&＃xff0c;在时间分片下&＃xff0c;线程可能在结束当前CPU突发前被迫放弃CPU。 

程序在CPU突发和I/O中交替&＃xff0c;CPU占用率高说明是在充分地使用CPU。

2、比较调度算法的准则

①CPU使用率&＃xff1a;CPU处于忙状态的时间百分比

②吞吐量&＃xff1a;单位时间内完成的进程数量

③周转时间&＃xff1a;一个进程从初始化到结束包括&＃xff08;所有等待时间&＃xff09;所花费的总时间&＃xff0c;周转时间&＃61;等待时间&＃43;服务时间

④等待时间&＃xff1a;进程在就绪队列中的总时间&＃xff0c;进程从就绪态到运行态的时间。

⑤响应时间&＃xff1a;一个请求被提交到第一次响应所花费的总时间

2、吞吐量与延迟

什么是更快&＃xff1f;

①高带宽&＃xff1a;吞吐量高 &＃xff08;传输文件&＃xff09;

②低延迟&＃xff1a;响应时间快&＃xff08;玩游戏&＃xff09;

3、调度算法的响应时间目标

• 减少响应时间&＃xff1a;及时处理用户的输入请求&＃xff0c;尽快发馈给用户
• 减少平均响应时间的波动&＃xff1a;交互系统中&＃xff0c;可预测性比高差异低平均更重要
• 低延迟调度改善用户的交互体验 
• 响应时间是操作系统的计算延迟

4、调度策略的吞吐量目标

①增加吞吐量&＃xff1a;减少开销&＃xff08;操作系统开销&＃xff0c;上下文切换&＃xff09; 、系统资源的高效利用&＃xff08;CPU,I/O设备&＃xff09;

②减少等待时间

5、处理机调度的公平性目标

①公平的定义&＃xff1a;保证每个进程占用相同的CPU时间&＃xff1b;保证每个进程的等待时间相同

②公平通常会增加平均响应时间

三、先来先服务、短进程优先和最高响应比优先调度算法

1、FCFS first come first served先来先服务算法

①依据进程进入就绪状态的先后顺序排列

②如果前面的进程运行的时间长&＃xff0c;后面的进程就只能等着&＃xff0c;导致周转时间慢。如果进程阻塞了&＃xff0c;队列中的下一个会得到CPU

③特征

优点&＃xff1a;简单 

缺点&＃xff1a;平均等待时间波动大&＃xff0c;花费时间少的可能反而排在后面&＃xff0c;可能导致CPU和I/O之间的重叠处理&＃xff0c;没考虑抢占&＃xff0c;CPU密集的进程导致I/O闲置时&＃xff0c;I/O密集型进程也在等。

2、短进程优先算法

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

②短进程优先算法具有最优平均周转时间

不可抢占&＃xff1a;SJF、SPN

可抢占&＃xff1a;ready queue中的第一个进程正在运行时&＃xff0c;来了一个比它的预测完成时间还短的进程&＃xff0c;SPT

③特征

优点&＃xff1a;最小的平均等待时间和周转时间

缺点&＃xff1a;可能导致长任务饥饿&＃xff0c;不能保证公平&＃xff1b;需要预知未来下一个进程的时间&＃xff0c;比如询问用户&＃xff0c;如果用户欺骗就杀死进程。

④短进程优先算法的执行时间预估

根据执行历史看将来CPU突发的持续时间&＃xff0c;递归展开

3、最高响应比优先算法&＃xff08;HRRN&＃xff09;

①选择就绪队列中响应比R值最高的进程

R&＃61;&＃xff08;w&＃43;s&＃xff09;/s

w:等待时间&＃xff08;waiting time&＃xff09;

s:执行时间&＃xff08;service time)

②在短进程优先算法的基础上改进&＃xff1b;不可抢占&＃xff1b;关注进程的等待时间&＃xff1b;防止无限期推迟。

四、时间轮转、多级反馈队列、公平共享调度算法和ucore调度框架

1、时间片轮换算法&＃xff08;RR&＃xff09;

①、时间片&＃xff1a;分配处理机资源的基本时间单元

②、算法思路&＃xff1a;用时间切片和抢占来轮流执行&＃xff0c;强调了公平 

在量子切片/时间切片的离散单元中分配处理器&＃xff0c;时间片结束时切换到下一个准备好的进程 

③、时间片长度

开销&＃xff1a; 额外的上下文切换&＃xff1b; 时间片太大则等待时间过长会退化成FCFS&＃xff0c;太小反应迅速但吞吐量由于大量的上下文切换开销受影响 &＃xff1b;选择一个合适的时间片&＃xff0c;经验是维持上下文切换开销处于1%以内&＃xff0c;现在LINUX是千分之一秒

2、多级队列调度算法&＃xff08;MQ&＃xff09;

①、就绪队列分为多个相对独立的队列&＃xff0c;前台交互&＃xff0c;RR&＃xff0c;后台/底层批处理&＃xff0c;FCFS&＃xff0c;调度在队列间进行&＃xff0c;每个队列拥有自己的调度策略。

②、队列间的调度&＃xff1a;

Ⅰ、固定优先级&＃xff1a;先前台&＃xff0c;再处理后台&＃xff0c;可能导致饥饿

Ⅱ、时间切片轮转&＃xff1a;每个队列都得到一个确定的&＃xff0c;调度其进程的CPU总时间&＃xff0c;如80%给前台&＃xff0c;20%给后台

3、多级反馈队列算法&＃xff08;MLFQ&＃xff09;

①、优先级队列中的时间片轮换有动态调整&＃xff1a;

一个进程可以在不同队列中移动&＃xff0c;N级优先级

在所有队列中优先级调度&＃xff0c;每个级别内部RR轮换

时间片大小随优先级增加而增加&＃xff0c;若当前时间量子中没有完成就给当前任务则降到下一个优先级

②、一个进程&＃xff0c;先是I/O密集型&＃xff0c;提到高优先级&＃xff0c;然后变为CPU密集型&＃xff0c;就随着不断消耗时间片就下降到低的优先级&＃xff0c;保证I/O密集型任务停留在高优先级 

等待时间越长&＃xff0c;优先级越高&＃xff0c;服务时间越长优先级越低 &＃xff0c;能动态地根据进程的特征调整队列和调度

4、公平共享调度&＃xff08;FSS&＃xff09;

①在用户级别实现公平共享 

②FFS 一些用户组比其他组更重要&＃xff0c;保证不重要的组无法垄断资源&＃xff0c;未使用的资源按照每个组所分配的资源的比例来分配&＃xff0c;没有达到资源使用率目标的组获得更高的优先级

5、评价调度方法

• 确定性建模&＃xff0c;对确定的工作量计算每个算法的表现
• 队列模型&＃xff1a;用来处理随机工作负载的数学方法
• 实现/模拟&＃xff1a;建立一个允许算法运行实际数据的系统&＃xff0c;最灵活&＃xff0c;一般性

五、实时调度和多处理器调度

1、实时调度

①、定义&＃xff1a;正确性依赖于其时间和功能两方面的一种OS

②、性能指标&＃xff1a;时间约束的及时性&＃xff08;deadlines&＃xff09;&＃xff0c;速度和平均性能相对不重要&＃xff0c;重点是时间约束的可预测性。

③、实时任务&＃xff1a;任务/工作单元&＃xff08;一次计算&＃xff0c;一次文件读取&＃xff0c;一次信息传递等等&＃xff09; 

任务属性&＃xff1a;取得进展所需要的资源和实时参数 

任务请求时间&＃xff08;release time&＃xff09;&＃xff1a;进程处于就绪态的时间 

相对截止时间&＃xff08;relative deadline&＃xff09;: 任务是间隔时间段完成&＃xff0c;每个任务有个特定的时间&＃xff0c;要在特定的时间段内完成 

绝对截止时间&＃xff08;absolute deadline&＃xff09;&＃xff1a;最终的结束时间

④、周期任务&＃xff1a;一系列相似的任务&＃xff0c;有规律的重复

周期p&＃61;任务请求时间间隔 (0

执行时间e&＃61;最大执行时间&＃xff0c;最大执行时间

使用率/利用率&＃xff1a;U&＃61;e/p

2、类别 

硬实时系统/强实时系统&＃xff1a;如果某个任务没完成有严重后果 

软实时系统/弱实时系统&＃xff1a;重要的进程优先级更高&＃xff0c;要尽量完成&＃xff0c;如看视频&＃xff0c;帧数没控制好会掉帧。

3、实时调度算法

①、速率单调调度算法&＃xff08;RM&＃xff09;&＃xff1a;通过周期安排优先级&＃xff0c;周期越短优先级越高&＃xff0c;执行周期最短的任务&＃xff1b;

②、最早截止时间优化算法&＃xff08;EDF&＃xff09;&＃xff1a;截止时间越早优先级越高&＃xff0c;执行截止时间最早的任务

4、多处理器调度 

要考虑&＃xff1a;1&＃xff0c;任务来了&＃xff0c;放在哪个CPU上执行&＃xff1f;2&＃xff0c;怎么考虑公平性&＃xff1f;load balance负载平衡 

多处理器的CPU调度更加复杂&＃xff0c;多个相同的单处理器组成一个多处理器&＃xff0c;优点是负载共享。对称多处理器(SMP)&＃xff0c;每个处理器运行自己的调度程序&＃xff0c;需要在调度程序中同步

六、优先级反置

①、优先级反转&＃xff1a;可发生在任何基于优先级的可抢占的调度机制中&＃xff0c;当高优先级任务要等待低优先级任务时发生&＃xff0c;优先级反转的持续时间取决于其他不相关任务的不可预测的行为 

②、优先级继承&＃xff1a;如果有共享资源&＃xff0c;低优先级任务继承等待它所占的资源的最高优先级任务的优先级&＃xff0c;当阻塞发生时资源的拥有者的优先级会自动提升&＃xff0c;使中间优先级的不能抢占。

T3先执行&＃xff0c;到t2时访问共享资源&＃xff0c;t3时T1抢占&＃xff0c;开始执行T1&＃xff0c;某时刻需要访问已经被T3占用的共享资源&＃xff0c;但T3还没有释放&＃xff0c;所以不能继续T1开始等待&＃xff0c;t5时T2又抢占执行&＃xff0c;此时T1受制于T2的执行时间&＃xff0c;因为T1必须要等T3&＃xff0c;导致T1的时间延长了&＃xff0c;引起不稳定状态&＃xff0c;系统重启。

T3的优先级继承了T1的优先级

③优先级天花板&＃xff1a;资源的优先级&＃61;所有可以锁定该资源的任务中优先级最高的那个任务的优先级。事先统计。一旦某任务占用该资源&＃xff0c;则优先级提升为资源的优先级。不论阻塞是否发生。

除非优先级高于系统中所有被锁定的资源的优先级上限&＃xff0c;否则任务在尝试执行临界区的时候会被阻塞。

持有最高优先级上限信号量锁的任务&＃xff0c;会继承被该锁阻塞的任务的优先级