文章目录
介绍
我只整理了一些比较关键的、考试可能会考的点，有些具体琐碎的内容我没整理到笔记中。后面会持续更新，希望对大家有所帮助！
三、处理机的调度与死锁
处理机组成：中央处理器cpu，主存储器，输入-输出接口
3.1 处理机调度概述
处理机调度层次
高级调度
（长程调度 / 作业调度）
作业
概念比程序更广泛，不仅包含了通常的程序和数据，而且配有一份作业说明书，系统根据该说明书对程序的运行进行控制
Venn图：一个作业可由多个进程组成，且必须至少由一个进程组成
作业控制块（JCB）
它是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息。
内容通常有：作业标志、用户名称、用户账号、作业类型（CPU繁忙型、I/O 繁忙型、批量型、终端型）、作业状态、调度信息（优先级、作业运行时间）、资源需求情况 （预计运行时间、要求内存大小）、资源使用情况等。
中级调度
（中程调度 / 内存调度）
根据运行紧急程度等情况，决定哪些进程放外存，哪些放内存
低级调度
（短程调度 / 进程调度）
根据调度算法， 决定哪些进程获得处理机
进程调度的任务和方式
1．进程调度任务
①保存CPU现场信息
②按某种算法选取进程
③把CPU分配给进程
2．进程调度机制
①排队器
②分派器
③上下文切换器
处理机调度算法的目标
1．共同目标 （1）资源利用率 （2）公平性（3）平衡性 （4）策略强制执行
2．批处理系统的目标 （1）平均周转时间短 （2）系统吞吐量高 （3）处理机利用率高
3．分时系统的目标 （1）保证响应时间快 （2）保证均衡性
4．实时系统的目标 （1）保证满足截止时间的要求 （2）保证可预测性
平均周转时间和平均带权周转时间的计算
- 周转时间 = 作业完成时刻 - 作业到达时刻
- 带权周转时间 = 周转时间 / 服务时间（执行时间）
- 平均周转时间 = 各个作业周转时间之和 / 作业个数
- 平均带权周转时间 = 带权周转总时间 / 作业个数
3.2 调度算法
几种基础的调度算法
先来先服务 短进程优先 优先级 时间片轮转
前三种调度算法可用于作业调度和进程调度
先来先服务（FCFS）
规矩排队，效率是否高得看前面的人是否慢吞吞…
短作业优先（SJF）
抢占式和非抢占式调度算法之间的区别
抢占式
若一个进程突然到来，且它的执行时间 < 当前进程距离完成所需要的时间，那就抢过来，先执行这个新来的进程
非抢占式
哪个作业短就优先执行哪个，执行过程中不能被抢
- 缺点 只考虑时间长短，不考虑紧迫程度，对长作业不利等
优先级（PR）
根据紧迫程度确定优先级，数字小的优先级大
静态优先级：固定的优先级
动态优先级：根据等待时间等因素动态更新优先级
高相应比优先调度算法（HRRN）
HRRN 是介于 FCFS（先来先服务算法）与 SJF（短作业优先算法）之间的折中算法
既考虑作业等待时间又考虑作业运行时间，既照顾短作业又不使长作业等待时间过长，改进了调度性能
响应比
w
a
i
t
+
r
u
n
t
i
m
e
r
u
n
t
i
m
e
=
a
l
l
t
i
m
e
r
u
n
t
i
m
e
\frac {wait + runtime}{runtime} = \frac {alltime}{runtime}
runtimewait+runtime=runtimealltime
折中合理考虑，但每次都要先计算优先级，增加系统开销
时间片轮转（RR）
切分时间片，轮流执行，没执行就插入队尾等待，轮到你再给你一个时间片单位
多级队列
每个队列有自己的调度算法
多级反馈队列
进程能够在不同队列间移动
基于公平规则
1．保证调度算法（对进程公平）
向用户所做的并不是优先运行保证，而是明确的性能保证，该算法可以做到调度的公平性。
2．公平分享调度算法（对用户公平）
如果各用户所拥有的进程数不同，就会发生对用户的不公平问题。
公平分享调度算法能让 所有用户能获得相同的处理机时间或所要求的时间比例
3.3 实时调度
由于在实时系统中都存在着若干个实施进程或任务，它们用来反应或控制某个（些）外部事件，往往带有某种程度的紧迫性
因而对实时系统中的调度提出了某些特殊要求，前面所介绍的多种调度算法，并不能很好的满足实时系统对调度的要求
为此，需要引入一种新的调度，即实时调度。
实时系统中包含两种任务：
硬实时任务（HRT）
指必须满足最后期限的限制，否则会给系统带来不可接受的破坏或者致命错误。
软实时任务（SRT）
也有一个与之关联的最后期限，并希望能满足这个期限的要求，但这并不是强制的，即使超过了最后期限，调度和完成这个任务仍然是有意义的。
实现实时调度的基本条件
1．提供与任务相关的必要信息
①就绪时间：指某任务的状态转换为就绪状态的起始时间，在周期任务的情况下，它是事先预知的 一串时间序列；
②开始截止时间和完成截止时间；
③处理时间：一个任务从开始执行直至完成所需的时间；
④资源要求：任务执行时所需的一组资源；
⑤优先级。
2．系统处理能力强
提高系统处理能力的途径有：
①采用单处理机系统，但须增强其处理能力，以显著减少对每个任务 的处理时间；
②采用多处理机系统
3．采用抢占式调度机制
在含有HRT任务的实时系统中，广泛采用抢占式调度机制，这样便可满足HRT任务对截止时间的要求。
4．采用快速切换机制
该机制应具有如下两方面的能力。
①对中断的快速响应能力。
②快速的任务分派能力
实时调度算法的分类
可按照不同方式对实时调度算法加以分类：
- 根据实时任务性质的不同，分为
HRT 硬实时调度算法和SRT 软实时调度算法 - 根据调度方式的不同，分为
非抢占调度算法和抢占调度算法 - 根据调度程序调度时间的不同，分为
静态调度算法和动态调度算法 - 多处理机环境下，可分为
集中式调度和分布式调度两种算法
（非）抢占式的几种调度算法
非抢占式 轮转 调度算法 非抢占式 优先级 调度算法
基于 时钟中断 的抢占式优先级调度算法 立即抢占 的优先级调度算法
常用的几种实时调度算法
最早截止时间优先 EDF 算法
Earliest Deadline First
贪心算法（会议室问题：尽可能安排结束时间早的会议）
最低松弛度优先 LLF 算法
Least Laxity First
根据任务紧急程度（松弛度）确认优先级
优先级倒置
高优先级的任务被低优先级的任务阻塞或延迟执行的情况
解决办法
采用一些调度策略，比如优先级继承、优先级反转等
3.4 进程调度
包括上面的（非）抢占式调度、优先级调度、轮转、多队列等…
3.5 死锁概述
省流：只有一双筷子，两人吃饭都抢了一只筷子，都在等对方放下筷子好让自己吃饭 … 结果两人都饿死了 …
a用m时，b用了n，a 用 m 后等待用 n，b 用 n 后等待用 m ，但是n被b占用，而b同时也在等待a的m，均等待无结果陷入死锁
死锁的描述
死锁进程中的每个进程都在等待另一个死锁进程所占有的资源，但由于所有这些进程都已无法运行，因此它们谁都不会释放资源，导致这组进程只能无限期地等待下去。
资源问题
可重用资源
每个可重用资源中的单元，只能分配给一个进程使用
可消耗资源
每类可消耗性资源的单元数目在进程运行期间是可以不断变化的
可抢占资源
可抢占资源是指某进程在获得这类资源后，它可以再被其他进程或系统抢占，不会造成死锁，如处理机，内存
不可抢占资源
一直占用直到用好，会造成死锁，如磁带机、打印机
产生死锁的必要条件（考）
互斥条件：不能同时使用
请求和保持条件：有了资源还要请求别的资源，别的资源又被别人死拿着不放
不可抢占条件：拿得死死的，不会被抢
循环等待条件：拿不到就死等（我拿不到，其他人也别想抢到！）
互斥条件、请求和保持条件、不可抢占条件、循环等待条件
处理死锁方法
-
死锁预防与避免，确保不会产生死锁
-
死锁检测与恢复，允许死锁产生，检测到就恢复系统
-
忽略死锁，假装死锁不存在
3.6 预防死锁
破坏死锁的一个或多个必要条件，来防止其产生
由于互斥条件是 非共享设备 所必须具备的条件，不仅不能改变，还应加以保证
因此，预防死锁时主要是破坏产生死锁的后3个条件
破坏 请求和保持 条件
系统必须保证做到：当一个进程在请求资源时，它不能持有不可抢占资源 (该保证可通过以下两个不同的协议实现)
协议1
所有进程在开始运行之前，必须一次性地申请其在整个运行过程中所需的全部资源
要啥资源就一次性说，不要断断续续的！若资源不够，就全都不分配，继续等
缺点 很明显啊，要是我要10000个资源，始终只有9999个资源可用，而我又得不到10000个而死等，那不就浪费了嘛！
协议2
允许一个进程只获得运行初期所需的资源后，便开始运行。进程运行过程中再逐步释放已分配 给自己的、且已用毕的全部资源，然后再请求新的所需资源
就是说你可以不一次性请求完，但是你要请求新的资源之前，要释放之前所占有的
破坏 不可抢占 条件
当一个已占有某些不可抢占资源的进程，请求新资源而不能得到满足时，它必须释放已经保持的所有资源，以后需要时再重新申请
就算说你拿不到就死等可以，先把东西留下，别tm一直死等还占用那些不可抢占资源！
缺点 方法实现比较复杂，且需要付出很大的代价
破坏 循环等待 条件
对系统的所有资源类型进行线性排序，并赋予它 们不同的序号
协议规定：定每个进程必须按序号递增的顺序请求资源，若要请求序号更低的资源，则需先释放序号高的资源
缺点 按顺序比较死板，不够灵活，资源利用率不高
3.7 避免死锁
在资源动态分配时，防止系统进入不安全状态
限制性较弱，无需破坏死锁产生的必要条件，一般会获得较好的系统性能
安全状态
能找到某种递推序列，给进程分配资源使其能顺利完成，必然不会进入死锁
不安全状态
有可能产生死锁，当在安全状态时，又有新的资源请求，就有可能产生不安全状态
死锁与安全状态之间的关系
安全状态下不会死锁；而不安全状态时，可能会进入死锁状态
银行家算法
① 每个新进程在进入系统时，其必须申明在运行过程中可能需要每种资源类型的最大单元数目，该数目<=系统所拥有的资源总量
② 当进程请求一组资源时，系统必须首先确定是否有足够的资源可分配给该进程
③ 若有，则进一步计算在将这些资源分配给该进程后，系统是否会处于不安全状态
④ 如果不会，则将资源分配给该进程，否则让该进程等待
省流：在安全进入不安全状态的情况下多了一层校验，先判断会不会进入不安全状态，再决定要不要给它分配资源
这个判断校验就要用到银行家算法，具体算法案例讲解：
3.8 死锁的检测与解除
检测
画出资源分配图（有向图），若一个进程能够获得所有资源，则资源先给他运行，然后释放，即将其关联的所有边去掉
以此类推，若最终的图无边，则说明可简化，不会造成死锁
若最终的图还有边，说明是 不可完全简化图，说明会造成死锁
解除
终止所有死锁进程
简单粗暴代价高，有些进程可能都快结束了，就被直接秒了…
逐个终止死锁进程
逐步终止，知道资源足够为止，但是需要采用死锁检测算法，代价也不低
死锁检测算法：终止一个进程时，还要判断是否还有死锁，如果有，还要终止其他进程
选择策略最主要的依据：为解除死锁而付出的代价最小
标签：优先级,操作系统,处理机,死锁,调度,算法,进程,资源 From： https://blog.csdn.net/mydaily_/article/details/140186580