【操作系统】第八课

痛定思痛。 2022-03-21 14:46 383阅读 0赞

> 课程来源《操作系统\_清华大学(向勇、陈渝)》

处理器和CPU调度

1.背景（CPU调度、CPU调度时间）、  
2.调度准则（调度策略、程序执行模型、比较调度算法的准则、吞吐量VS延迟、公平的目标）、  
3.调度算法（一般性的调度算法、针对嵌入式系统的特殊调度算法、多CPU多内核的调度算法）、  
4.实时调度（实时系统、可调度性、单调度性（RM）、截至日期最早优先（EDF））、  
5.多处理器调度、  
6优先级反转

**1.背景**

上下文切换：  
1.切换CPU的当前任务，从一个进程/线程到另一个，  
2.保存当前进程/线程在PCB/TCB中的执行上下文（CPU状态），  
3.读取下一个进程/线程的上下文

**CPU什么时候上下文切换，怎么切换，主要看CPU调度。**

CPU调度：  
1.从就绪队列中挑选一个进程/线程作为CPU将要运行的下一个线程/进程  
2.调度程序：挑选进程/线程的内核函数（通过一切调度策略）使得效率最高，满足用户需求

在进程/线程的生命周期中的什么时候进行调度？ 从一个状态变为另一个状态，特别是和运行（running）相关的状态。

内核运行调度程序的条件：  
1.进程从运行状态切换到等待状态  
2.or终结了（done）

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

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

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

如果在内核中也允许这种抢占，系统调用返回时不是原来的进程而是另一个优先级更高的进程，就是内核中的抢占。

早期是完全不可抢占，后来用户态进程允许抢占，现在内核态进程也可以抢占。

**2.调度原则**

调度原则：调度策略、程序执行模型、比较调度算法的准则、吞吐量VS延迟、公平的目标

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70]

CPU的占用率是波状，CPU大量运算是高峰，而读写I/O时是平稳的低值。

执行模型，程序在CPU突发和I/O中交替：  
1.每个调度决定都是关于下一个CPU突发时将哪个工作交给CPU，  
2.在时间分片下，线程可能在结束当前CPU突发前被迫放弃CPU。

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

选择调度方法的评价指标：  
CPU使用率：CPU处于忙状态的时间百分比  
吞吐量：单位时间内完成的进程数量  
周转时间：一个进程从初始化到结束包括（所有等待时间）所花费的时间，周转时间=等待时间+服务时间  
等待时间：进程在就绪队列中的总时间，进程从就绪态到运行态的时间。  
响应时间：一个请求被提交到第一次响应所花费的总时间

NEED SPEED FOREVER“更快” （高带宽和低时延是独立的）  
1.高带宽：吞吐量高 （例如水龙头总是以最大流水量向外流水）  
2.低延迟：响应时间快（例如水龙头一打开就有水）

用量化的方法来看调度算法：

*  减少响应时间（及时处理用户的输出并且尽快将输出提供给用户）
 *  减少平均响应时间的波动，交互系统中，可预测性比高差异低平均更重要
 *  增加吞吐量，两个方面：
    
     *  1.减少开销（操作系统开销，上下文切换）
     *  2.系统资源的高效利用（CPU,I/O设备）
 *  减少等待时间（减少每个进程的等待时间）

难以每个都做到，只能取平衡。不同需求。

桌面系统要求交互，用低延迟调度增加了交互式表现，但数据中心的 服务器更强调吞吐量，OS要保持吞吐量不受影响，

吞吐量是OS的计算带宽，延迟时间是OS的计算延迟。

要公平 ：  
每个进程都公平地得到CPU的支持，比如占用相同的CPU时间，或等待相同时间。但是，公平通常会增加平均响应时间。

**3.调度算法1**

1.一般性的调度算法  
2.针对嵌入式系统的特殊调度算法  
3.多CPU多内核的调度算法

常用简单调度算法：FCFS（先来先服务）、SPN/SJF/SRT（段进程优先/短作业优先/短剩余时间优先）、HRRN（最高响应比优先）、Round Robin（轮循）、多级反馈队列、公平共享调度

FCFS：First Come，First Served 先来先服务  
SPN：Shortest Process Next 短进程优先  
SJF：Shortest Job First 短作业优先  
SRT：Shortest Remaining Time 短剩余时间优先  
HRRN：Highest Reponse Ratio Next 最高响应比优先  
Round Robin：轮循，使用时间切片和抢占来轮流执行任务  
Multilevel Feedback Queues：多级反馈队列，优先级队列中的轮循  
Fair Share Scheduling：公平共享调度

==1.FCFS first come first served先来先服务 ==

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 1]  
优点：简单  
缺点：平均等待时间波动大，花费时间少的可能反而排在后面，可能导致CPU和I/O之间的重叠处理，没考虑抢占，CPU密集的进程导致I/O闲置时，I/O密集型进程也在等。

2.SPN/SJF/SRT

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 2]  
不可抢占：SJF SPN  
可抢占：ready queue中的第一个进程正在运行时，来了一个比它的预测完成时间还短的进程，SRT

优点：最小的平均等待时间和周转时间  
缺点：连续的短任务可能导致长任务饥饿，不能保证公平；需要预知未来下一个进程的时间，如何预知，解决方法比如询问用户，如果用户欺骗就杀死进程，如果用户不知道怎么办。

3.HRRN

HRRN：  
在SPN调度的基础上改进；  
不可抢占；  
关注进程等待了多长时间；  
防止无限期推迟。

HRRN 最高相应比优先

priority=(waiting time +estimated running time)/estimated running time 取HIGHER值。

SPN只考虑了执行时间，SERVICE TIME，它还考虑了等待时间。

优点：  
不可抢占，防止无限期延迟即进程饥饿  
交互性，响应性更好

缺点：对抢占性的支持不够，也需要预知service time

**4.调度算法2**

4.Round Robin 轮循

Round Robin 轮循，用时间切片和抢占来轮流执行，强调了公平。

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 3]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 4]  
公平，相对稳定；但平均等待时间较长

RR开销： 额外的上下文切换；

时间量子太大：  
1.等待时间过长，  
2.太大则等待时间过长会退化成FCFS

时间量子太小：  
1.反应迅速但…  
2.吞吐量由于大量的上下文切换开销受影响。

目标：  
选择一个合适的时间量子，经验是维持上下文切换开销处于1%以内，现在LINUX是千分之一秒 。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 5]

5.Multilevel Queues 多级队列：

就绪队列分为相对独立的队列：前台交互，后台/底层批处理

每个队列拥有自己的调度策略：前台交互，RR，后台/底层批处理，FCFS

调度必须在队列间进行：

*  固定优先级：先前台，再处理后台，可能导致饥饿
 *  时间切片：每个队列都得到一个确定的，调度其进程的CPU总时间，如80%给前台，20%给后台

进程和队列都在动态变化，能否动态调整？  
多级反馈队列 优先级队列中的轮循 有动态调整：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 6]

一个进程可以在不同队列中移动，

例如：N级优先级-优先级调度在所有级别中，RP在每个级别中：  
1.时间量子大小随优先级增加而增加，  
2.若当前时间量子中没有完成就给当前任务则降到下一个优先级

优点：  
1.CPU密集型任务的优先级下降很快  
2.I/O密集型任务停留在高优先级

一个进程，先是I/O密集型，提到高优先级，然后变为CPU密集型，就随着不断消耗时间量子就下降到低的优先级，保证I/O密集型任务停留在高优先级 。  
等待时间越长，优先级越高，服务时间越长优先级越低 。  
能动态地根据进程的特征调整队列和调度。

6.公平共享调度：

FSS控制用户对系统资源的访问：  
1.FSS 一些用户组比其他组更重要，  
2.保证不重要的组无法垄断资源，  
3.未使用的资源按照每个组所分配的资源的比例来分配，  
4.没有达到资源使用率目标的组获得更高的优先级

评价调度方法：  
1.确定性建模，对确定的工作量计算每个算法的表现  
2.队列模型：用来处理随机工作负载的数学方法  
3.实现/模拟：建立一个允许算法运行实际数据的系统，最灵活，一般性

最好还是在真实机器上跑一遍，因为和硬件也有关系。

**各个调度算法比较：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 7]

**5.实时调度**

实时调度：实时系统、可调度性、单调速率（RM）、截至日期最早优先（EDF）

应用案例：调度火车，工厂，需要确保任务在规定时间内完成的

实时调度定义：正确性依赖于其时间和功能两方面的一种OS

性能指标：  
时间约束的及时性（deadlines），  
速度和平均性能相对不重要，重点是时间约束的可预测性。

主要特性：  
及时性 时间约束的可预测性

类别：  
硬实时系统/强实时系统：如果某个任务没完成有严重后果  
软实时系统/弱实时系统：重要的进程优先级更高，要尽量完成，如看视频，帧数没控制好会掉帧。

任务/工作单元job：一次计算，一次文件读取，一次信息传递等等

属性：取得进展所需要的资源和实时参数

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 8]

release time 进程处于就绪态的时间

relative deadline: 任务是间隔时间段完成，每个任务有个特定的时间，要在特定的时间段内完成

absolute deadline：最终的结束时间

--------------------

周期任务，有规律的重复

周期P=inter-realease time=relative deadline (0 < p)  
执行时间e，最大执行时间< p  
使用率/利用率U=e/p

--------------------

hard real-time—hard deadline（硬实时）：保证确定性  
soft real-time—-soft deadline（软实时）：尽最大努利保证

设计算法满足deadline要求：  
1.决定实时任务执行的顺序，  
2.静态优先级调度（事先确定），  
3.动态优先级调度（优先级会动态变化）

实时系统中常用调度算法：RM、EDF

RM（rate monotonic） 速率单调调度 ：  
静态最佳，根据周期安排优先级，周期越短优先级越高 ，执行周期最短的任务

EDF （earliest deadline first） 最早期限调度 ：  
最佳静态，deadline越早优先级越高，执行deadline最早的任务，动态调整优先级

**6.多处理器调度与优先级反转**

**多处理器调度：**

要考虑：  
1，任务来了，放在哪个CPU上执行？2，怎么考虑公平性？

load balance负载平衡

多处理器的CPU调度更加复杂，多个相同的单处理器组成一个多处理器，优点是负载共享。

对称多处理器(SMP)，每个处理器运行自己的调度程序，需要在调度程序中同步

**优先级反转：**

可发生在任何基于优先级的可抢占的调度机制中，当高优先级任务要等待低优先级任务时发生

优先级反转的持续时间取决于其他不相关任务的不可预测的行为  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 9]

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

优先级反转的解决方法： 优先级继承：  
如果有共享资源，低优先级任务继承等待它所占的资源的最高优先级任务的优先级，当阻塞发生时资源的拥有者的优先级会自动提升，使中间优先级的不能抢占。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 10]

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

另一种方式：priority ceilings  
1.优先级天花板：资源的优先级=所有可以锁定该资源的任务中优先级最高的那个任务的优先级。事先统计。一旦某任务占用该资源，则优先级提升为资源的优先级。不论阻塞是否发生。  
2.除非优先级高于系统中所有被锁定的资源的优先级上限，否则任务在尝试执行临界区的时候会被阻塞。  
3.持有最高优先级上限信号量锁的任务，会继承被该锁阻塞的任务的优先级

补充：  
信号量，S，整数，S大于等于0-→S=可供并发进程使用的资源实体数，S<0-→S=正在等待使用临界区的进程数

互斥量mutex：二元信号灯，提供对资源的独占访问，有0和1两个值，0为锁定，当前对象被锁定，用户如果试图lock临界资源则排队等待，1是空闲，进程可以lock资源，之后1—>0

同一个线程中，为了防止死锁，系统不允许连续两次对mutex加锁。即加锁和解锁需要在同一个线程中完成。

优先级反转：如果任务之间由于有了共享资源出现了竞争或死锁，会引起OS不安全，采用信号量方法对其进行操作系统的优先级反转。

一个任务要用一个共享资源，必须先申请得到这个信号量，高优先级的即使ready但因为得不到S，不能使用该资源。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70]: /images/20220321/373c782ef6c5413e84f365593606f5a0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 1]: /images/20220321/4bf2232b2d884d35b3c8ffee7aa25ed5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 2]: /images/20220321/7d8ab0c64db3425b8f3e26e3805b41ea.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 3]: /images/20220321/c054f73cc0084138a1185fa4bc4f5439.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 4]: /images/20220321/d7fa95dbf64e432986bebf05df505d25.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 5]: /images/20220321/6382a6795d094a0ba8bd8d5dbb1cebec.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 6]: /images/20220321/74d85da108d94559914795326da2b304.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 7]: /images/20220321/bd8b58599c2a4a3a9b7b0b51812375e2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 8]: /images/20220321/14019142725843e2a85f879ea47292fa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 9]: /images/20220321/7a6355bd8eee4feda46c8994e9e5218f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 10]: /images/20220321/42dfceee6a3141b79dd7096d55c5b600.png