操作系统期末复习之处理机调度与死锁
处理机调度与死锁
处理机是系统最重要的资源，提高处理机的利用率和改善系统性能，在很大程度上取决于处理机调度性能的好坏。
调度的层次
1）高级调度（作业调度，长程调度）
2）低级调度（进程调度，短程调度）
3）中级调度（交换调度， 中程调度）
1、高级调度
▪调度对象：作业
▪又称作业调度、长程调度、接纳调度
▪实现：作业管理程序
▪将外存作业调入内存，创建PCB等，插入就绪队列。
▪用于批处理系统，分/实时系统一般直接入内存，无此环节。
▪频度：最低，分钟级
2、低级调度
▪又称进程调度或短程调度
▪对象：就绪进程（或内核线程）
▪功能：决定就绪队列中的哪个进程应获得处理机，并将处理机分配给选中的进程。
▪实现者 ：分派程序（dispatcher)
▪应用范围：都有
▪频度：最频繁，毫秒级
引起进程调度的因素可归结为这样几个：
①正在执行的进程执行完毕，或因发生某事件而不能再继续执行；
②执行中的进程因提出I/O请求而暂停执行；
③在进程通信或同步过程中执行了某种原语操作，如P操作（wait操作）、Block原语、 Wakeup原语等。
3.中级调度
▪又称内存调度、中程调度
▪对象：挂起的进程
▪功能：把外存上那些已经具备运行条件的就绪进程重新载入内存。从静止就绪到活动就绪。
▪实现：内存管理中的对换进程
▪应用范围：具有对换功能的操作系统
▪频度：中等
调度算法的准则
面向用户的准则
① 周转时间短，周转时间是指从作业被提交给系统开始，到作业完成为止这段时间间隔，它包括四部分：作业在外存后备队列上等待调度的时间，进程在就绪队列上等待进程调度的时间，进程在CPU上执行的时间，进程等待I/O操作完成的时间。
② 响应时间快，从用户通过键盘提交一个请求开始，直到屏幕上显示出处理结果为止的一段时间间隔。包括三个部分：输入时间、处理时间、显示时间。
③ 截止时间的保证，某任务必须开始执行的最迟时间，或必须完成的最迟时间。
④ 优先权准则，让某些紧急的作业能够得到及时处理。
面向系统的准则
① 系统吞吐量高，指在单位时间内系统所完成的作业数。
② 处理机利用率好
③ 各类资源的平衡利用
最优准则
❖最大的CPU利用率
❖最大的吞吐量
❖最短的周转时间
❖最短的等待时间
❖最短的响应时间
CPU利用率 = CPU的有效工作时间 / （CPU有效工作时间 + CPU空闲等待时间）
平均周转时间：
带权周转时间：作业的周转时间T与系统为它提供服务的时间Ts之比。 W = T/Ts
▪带权周转时间标明了作业额外等待和作业执行时间之间的比例。
▪平均带权周转时间：反应调度算法的好坏。
调度算法
先来先服务调度算法
先来先服务调度算法（First Come FirstService，FCFS)：按照作业提交或进程变为就绪状态的先后次序，分派CPU；当前作业或进程占用CPU，直到执行完或阻塞，才主动地出让CPU。 FCFS算法比较有利于长作业（进程），而不利于短作业（进程）。 FCFS调度算法有利于CPU繁忙型的作业，而不利于I/O繁忙型的作业。
可见短作业的带权周转时间明显高于长作业。
短作业优先调度算法
短作业(进程)优先调度算法SJ(P)F，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。
➢短作业优先(SJF)的调度算法，是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。
➢短进程优先(SPF)调度算法，则是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。
优先级调度算法
Priority-scheduling algorithm, PSA，外部赋予作业（进程）相应的优先级，例如以作
业的紧迫程度作为优先级。选择优先级高的进程投入运行。即可用于作业调度算法，也可用于进程调度。分为非抢占式优先级调度算法和抢占式优先级调度算法。
例题：
非抢占式：
0时刻(P1):只有P1到达，P1上处理机。
7时刻(P2、P3，P4):P1运行完成主动放弃处理机，其余进程都已到达，P3优先级最高，P3上处理机。
8时刻(P2、P4):P3完成，P2P4优先级相同，由于P2先到达，因此P2优先上处理机。
抢占式：
0时刻(P1):只有P1到达，P1上处理机。
2时刻(P2):P2到达就绪队列，优先级比P1更高，发生抢占。P1回到就绪队列，P2上处理机。
4时刻(P1、P3):P3到达，优先级比P2更高，P2回到就绪队列，P3抢占处理机。
5时刻(P1、P2、P4):P3完成，主动释放处理机，同时，P4也到达，由于P2比P4更先进入就绪队列，因此选择P2上处理机
7时刻(P1P4):P2完成，就绪队列只剩P1、P4，P4上处理机。11时刻(P1):P4完成，P1上处理机
16时刻():P1完成，所有进程均完成。
高响应比优先调度算法
Highest Response Ratio Next， HRRN，赋予作业动态优先级，优先级随作业等待时间延长而增加，从而使长作业的优先级在等待期间不断增加。
优先级相当于响应比Rp。
如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。对于长作业，作业的优先级可以随等待时间的增加而提高， 从而也可获得处理机。简言之，该算法既照顾了短作业，又考虑了作业到达的先后次序，不会使长作业长期得不到服务。
| 作业 | 到达时间 | 服务时间 |
|---|---|---|
| A | 0 | 6 |
| B | 3 | 2 |
| C | 4 | 4 |
| D | 4 | 1 |
（1）先执行A作业
| 作业 | 到达时间 | 服务时间 | 开始时间 | 结束时间 | 周转时间 | 带权周转时间 |
|---|---|---|---|---|---|---|
| A | 0 | 6 | 0 | 6 | 6 | 1 |
| B | 3 | 2 | ||||
| C | 4 | 4 | ||||
| D | 4 | 1 |
（2）根据响应比，执行D作业
等待时间 = 上一个作业调入完成时间 - 该作业到达的时间
响应比高的先执行
R（B） = 1 + （6 - 3）/ 2 = 2.5
R（C） = 1 + （6 - 4）/ 4 = 1.5
R（D）= 1 + （6 - 4） / 1 = 3
| 作业 | 到达时间 | 服务时间 | 开始时间 | 结束时间 | 周转时间 | 带权周转时间 |
|---|---|---|---|---|---|---|
| A | 0 | 6 | 0 | 6 | 6 | 1 |
| B | 3 | 2 | ||||
| C | 4 | 4 | ||||
| D | 4 | 1 | 6 | 7 | 3 | 3 |
（3）根据响应比，执行B作业
R（B） = 1 + （7 - 3）/ 2 = 3
R（C） = 1 + （7 - 4）/ 4 = 1.75
| 作业 | 到达时间 | 服务时间 | 开始时间 | 结束时间 | 周转时间 | 带权周转时间 |
|---|---|---|---|---|---|---|
| A | 0 | 6 | 0 | 6 | 6 | 1 |
| B | 3 | 2 | 7 | 10 | 7 | 3.5 |
| C | 4 | 4 | ||||
| D | 4 | 1 | 6 | 7 | 3 | 3 |
（4）最后执行C作业
| 作业 | 到达时间 | 服务时间 | 开始时间 | 结束时间 | 周转时间 | 带权周转时间 |
|---|---|---|---|---|---|---|
| A | 0 | 6 | 0 | 6 | 6 | 1 |
| B | 3 | 2 | 7 | 10 | 7 | 3.5 |
| C | 4 | 4 | 10 | 14 | 10 | 2.5 |
| D | 4 | 1 | 6 | 7 | 3 | 3 |
时间片轮转调度算法
RR，系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片，当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信息来停止该进程的执行，将它送到就绪队列末尾，然后，再把处理机分配给就绪队列中心的队首进程，同时也让它执行一个时间片，这样就可以保证就绪队列中的所有进程在一个给定的时间内均能获得一个时间片的处理机执行时间。
多级反馈队列调度算法
（1）设置多个就绪队列，并为各个队列赋予不同的优先级。 第一个最高，以后依次降低。
（2）每个队列中进程执行时间片的大小也各不相同，进程所在队列的优先级越高，其相应的时间片就越短。
（3）当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，……。
（4）仅当第一队列空闲时，调度程序才调度第二队列中的进程运行。
未执行完时间片的进程被抢占后如何处理？
答：不降级，到队列末尾，且下一次运行时仍然是一个完整时间片（该队列对应的）
注意：统一为抢占式。高优先级队列中有进程进入时，会抢占低优先级队列中进程的CPU。被抢占的进程不降级，回到原级队列中，下次仍然执行该级队列的时间片。
例题：假设一个多级反馈队列的实现共有4级，各个队列的时间片长度是1、2、4、6秒，已知当前仅在第一级队列上有一个执行时长为10秒的进程，在两秒后将有一个执行时长为8秒的任务A到达，请算出任务A的周转时间。
A任务结束时间为18秒。A任务的周转时间为16秒。
死锁的概念、原因
所谓死锁（Deadlock），是指多个进程在运行过程中因争夺资源而造成的一种僵局（DeadlyEmbrace），当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。
可重用资源是一种可供用户重复使用多次的资源。
可消耗资源又称为临时性资源。
可抢占性资源，又称可剥夺性资源
一个进程在使用某个资源时,系统可以剥夺其使用权,将该资源分配给其他进程.
典型资源：CPU 、内存
不可抢占性资源，又称非剥夺性资源
某个资源一旦分配给某个进程，则系统不能剥夺进程的使用权，只能由进程释放资源，或者进程终止运行。
典型资源：打印机、光盘刻录机、磁带机
产生死锁的原因
（1）竞争资源
（2）进程间推进顺序非法
产生死锁中的竞争资源之一指的是竞争不可剥夺资源(例如：系统中只有一台打印机，可供进程P1使用，假定P1已占用了打印机，若P2继续要求打印机打印将阻塞)。产生死锁中的竞争资源另外一种资源指的是竞争临时资源(临时资源包括硬件中断、信号、消息、缓冲区内的消息等)，通常消息通信顺序进行不当，则会产生死锁。
产生死锁的原因之一是对计算机操作不当，造成计算机死机。（ ×）
产生死锁的必要条件
死锁的发生必须具备下列四个必要条件：
（1）互斥条件
（2）请求和保持条件
（3）不剥夺条件
（4）环路等待条件
环路等待条件是指，在死锁发生的时候，两个线程获取资源的顺序构成了环形链。比如，线程 A 已经持有资源 2，而想请求资源 1， 线程 B 已经获取了资源 1，而想请求资源 2，这就形成资源请求等待的环形图。
死锁预防
为了不发生死锁，必须设法破坏产生死锁的四个必要条件之一。因为互斥条件是由设备的固有属性所决定的，不仅不能改变，还应加以保证。
破坏“请求和保持”条件
系统规定所有进程在开始运行之前，都必须一次性地申请其在整个运行过程所需的全部资源。从而进程在整个运行期间，便不会再提出资源要求，从而摒弃了请求和保持条件，由此可以避免发生死锁。
优点：简单、易于实现且很安全。缺点：资源被严重浪费，使进程延迟运行
摒弃“不剥夺”条件
当一个已经保持了某些资源的进程，再提出新的资源请求而不能立即得到满足时，必须释放它已经保持了的所有资源。待以后需要时再重新申请。从而摒弃了“不剥夺”条件。
缺点：实现起来比较复杂且要付出很大代价。
一个资源在使用一段时间后，它的被迫释放可能会造成前段工作的失效。会使进程前后两次运行的信息不连续。因反复地申请和释放资源，致使进程执行被无限推迟，延长进程周转时间、增加系统开销、降低吞吐量。
摒弃“环路等待”条件
系统将所有资源按类型进行线性排队，并赋予不同的序号。 所有进程对资源的请求必须严格按照资源序号递增的次序提出。
优点：资源利用率和系统吞吐量都有明显的改善。
存在的问题：首先是为系统中各类资源所分配（确定）的序号，必须相对稳定，这就限制了新类型设备的增加；作业（进程）使用各类资源的顺序，与系统规定的顺序不同，造成对资源的浪费 ;限制用户简单、自主地编程 。
安全状态
所谓安全状态，是指系统能按某种进程顺序，如<P1，P2，…，Pn>，依次为n个进程分配其所需资源，直至其最大需求，使每个进程都可顺利地完成，称系统处于安全状态。称〈P1，P2，…，Pn〉序列为安全序列。否则，如果系统无法找到这样一个安全序列，则称系统处于不安全状态。
如果一个系统在安全状态，就没有死锁。如果一个系统处于不安全状态，就有可能死锁。避免死锁的实质：确保系统不进入不安全状态。
假定系统中有三个进程P1、P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0 时刻进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，在T0时刻系统是否安全？
| 进程 | 最大需求 | 已分配 | 可用 |
|---|---|---|---|
| P1 | 10 | 5 | 3 |
| P2 | 4 | 2 | |
| P3 | 9 | 2 |
T0时刻系统是安全的,存在一个安全序列<P2,P1,P3>
死锁避免
避免死锁的关键在于如何准确的预测是否会出现死锁，从而避免死锁。
银行家算法
例：有四个顾客：A，B，C，D，每个顾客分成若干次借款；并在第一次借款时，顾客提出的最大贷款数量分别为6、5、4、7。银行家知道不是所有顾客都马上需要其全部贷款（6+5+4+7=22）。 因此，他只保留10个单位数量(而不是全部22个单位)为这些顾客服务。
| 顾客 | 拥有 | 最大要求 |
|---|---|---|
| A | 0 | 6 |
| B | 0 | 5 |
| C | 0 | 4 |
| D | 0 | 7 |
银行家拥有量:10
| 顾客 | 拥有 | 最大要求 |
|---|---|---|
| A | 1 | 6 |
| B | 1 | 5 |
| C | 2 | 4 |
| D | 4 | 7 |
当前剩余量: 2
| 顾客 | 拥有 | 最大要求 |
|---|---|---|
| A | 1 | 6 |
| B | 2 | 5 |
| C | 2 | 4 |
| D | 4 | 7 |
当B请求1个时，当前剩余量:1。现在银行家要破产了，剩余的资金贷给谁都不够，因此项目不能完成，银行家不能收回贷款。错误发生在最后贷款给B的1个亿上。
| 顾客 | 拥有 | 最大要求 |
|---|---|---|
| A | 1 | 6 |
| B | 1 | 5 |
| C | 2 | 4 |
| D | 4 | 7 |
当前剩余量: 2
B请求：不贷款；C请求2个亿：可以贷款
C完成项目后，还出4，这个4银行家下次可贷给B，也可贷给D其中的3，不管如何处理，B或D都能完成归还5或归还7；最后贷给A所需资金5。最终，A、B、C、D都完成了项目，银行家得到了贷款利润。存在的安全序列是：C、B、D、A或C、D、B、A
银行家算法能预测一笔贷款业务对银行是否是安全的，该算法也能预测一次资源分配对计算机系统是否是安全的。为实现银行家算法，系统中必须设置若干数据结构。
- n个进程（P1，P2，…，Pn）
- m类资源（R1，R2，…，Rm）
- 可利用资源向量：available[j]=k，资源Rj类有k个可用
- 最大需求矩阵：Max[i, j]=k，进程Pi最大请求k个Rj类资源
- 分配矩阵：Allocation[i, j]=k，进程Pi分配到k个Rj类资源
- 需求矩阵：Need[i, j]=k，进程Pi还需要k个Rj类资源
三个矩阵的关系： Need[i, j] = Max[i, j] – Allocation[i, j]
设Requesti，是进程Pi的请求向量，当Pi发出资源请求后，系统按下述步骤进行检查：
系统所执行的安全性算法可描述如下：
（1）设置两个向量：
①工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目，Work =Available
②Finish：开始时先做Finish[i] = false；当有足够资源分配给进程时，再令Finish[i] = true。
（2）从进程集合中找到一个能满足下述条件的进程：
①Finish[i] = false；
②Need[i,j] ≤ work[j]；
若找到，执行步骤（3)；否则，执行步骤（4）。
（3）当进程只获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：
Work[ j ] = Work[ i ] + Allocation[ i,j ]；
Finish[ i ] = true;
go to step 2；
（4）如果所有进程的Finish[i] ＝ true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。
例题：假定系统中有五个进程{P0，P1，P2，P3，P4} 和三类资源{A ,B,C},各种资源的数量分别为10、5、7，在T0 时刻的资源分配情况
| 进程 | Max (A, B, C) | Allocation (A, B, C) | Need (A, B, C) | Available (A, B, C) |
|---|---|---|---|---|
| P0 | 7 5 3 | 0 1 0 | 7 4 3 | 3 3 2 |
| P1 | 3 2 2 | 2 0 0 | 1 2 2 | |
| P2 | 9 0 2 | 3 0 2 | 6 0 0 | |
| P3 | 2 2 2 | 2 1 1 | 0 1 1 | |
| P4 | 4 3 3 | 0 0 2 | 4 3 1 |
利用安全性算法对T0时刻的资源分配情况进行分析
| 进程 | Work (A, B, C) | Need (A, B, C) | Allocation (A, B, C) | Work+Allocation (A, B, C) | Finish |
|---|---|---|---|---|---|
| P1 | 3 3 2 | 1 2 2 | 2 0 0 | 5 3 2 | TRUE |
| P3 | 5 3 2 | 0 1 1 | 2 1 1 | 7 4 3 | TRUE |
| P4 | 7 4 3 | 4 3 1 | 0 0 2 | 7 4 5 | TRUE |
| P2 | 7 4 5 | 6 0 0 | 3 0 2 | 10 4 7 | TRUE |
| P0 | 10 4 7 | 7 4 3 | 0 1 0 | 10 5 7 | TRUE |
判断请求是否可以满足
P1请求资源：P1发出请求向量Request1(1,0,2),系统按银行家算法进行检查
①Request1（1，0，2）≤Need1（1，2，2）
②Request1（1，0，2）≤Available1（3,3,2)
③系统先假定可为P1分配资源，并修改Available，Allocation1和Need1向量，由此形成的资源变化情况如下表所示。
④再利用安全性算法检查此时系统是否安全。
假设分配后调整表格
| 进程 | Max (A, B, C) | Allocation (A, B, C) | Need (A, B, C) | Available (A, B, C) |
|---|---|---|---|---|
| P0 | 7 5 3 | 0 1 0 | 7 4 3 | 2 3 0 |
| P1 | 3 2 2 | 3 0 2 | 0 2 0 | |
| P2 | 9 0 2 | 3 0 2 | 6 0 0 | |
| P3 | 2 2 2 | 2 1 1 | 0 1 1 | |
| P4 | 4 3 3 | 0 0 2 | 4 3 1 |
P1 申请资源时的安全性检查
| 进程 | Work (A, B, C) | Need (A, B, C) | Allocation (A, B, C) | Work+Allocation (A, B, C) | Finish |
|---|---|---|---|---|---|
| P1 | 2 3 0 | 0 2 0 | 2 0 3 | 5 3 2 | TRUE |
| P3 | 5 3 2 | 0 1 1 | 2 1 1 | 7 4 3 | TRUE |
| P4 | 7 4 3 | 4 3 1 | 0 0 2 | 7 4 5 | TRUE |
| P0 | 7 4 5 | 7 5 5 | 0 1 0 | 7 5 5 | TRUE |
| P2 | 10 5 5 | 6 0 0 | 3 0 2 | 10 5 7 | TRUE |
P4请求资源：P4发出请求向量Request4（3,3,0），系统按银行家算法进行检查：
①Request4（3，3，0）≤Need4（4，3，1）；
②Request4(3，3， 0)≮Available（2，3，0），让P4等待。
P0请求资源：P0发出请求向量Requst0(0,2,0），系统按银行家算法进行检查：
①Request0（0, 2,0）≤Need0（7，4，3）；
②Request0（0,2,0）≤Available（2，3，0）；
③系统暂时先假定可为P0分配资源，并修改有关数据，
如下表所示。
| 进程 | Allocation (A, B, C) | Need (A, B, C) | Available (A, B, C) |
|---|---|---|---|
| P0 | 0 3 0 | 7 2 3 | 2 1 0 |
| P1 | 3 0 2 | 0 2 0 | |
| P2 | 3 0 2 | 6 0 0 | |
| P3 | 2 1 1 | 0 1 1 | |
| P4 | 0 0 2 | 4 3 1 |
进行安全性检查：可用资源Available（2，1，0）已不能满足任何进程的需要，故系统进入不安全状态，此时系统不分配资源。
避免死锁的限制条件
a) 预先必须申明每个进程需要的资源总量；
b) 进程之间相互独立，其执行顺序取决于系统安全，而非进程间的同步要求；
c) 系统必须提供固定数量的资源供进程使用；
补充问题：
死锁检测和解除
检测死锁的基本思想: 利用某种算法对资源请求和分配信息加以检查，以判断是否存
在死锁。
资源分配图 G = (N,E)
（1）把N分为两个互斥的子集，即一组进程结点P={P1,P2，…，Pn）和一组资源结点R={r1, r2, …, rn}，N＝P U R。
（2）凡属于E中的一个边e∈ E都连接着P中的一个结点和R中的一个结点，e＝{Pi,rj} 它表示进程pj请求一个单位的rj资源。 e={rj，Pi} 它表示把一个单位的资源rj分配给进程Pi。
重要结论：如果资源分配图中不存在环路，则系统中不存在死锁；反之，如果资源分配图中存在环路，则系统中可能存在死锁，也可能不存在死锁。
资源分配图加以简化的方法
（1）寻找一个既不阻塞又非孤立的进程结点Pi（能分配给满足Pi要求的资源数），若无，则算法结束；
（2）去除Pi的所有分配边和请求边，使Pi成为一个孤立节点；
（3）转步骤（1）。
若能消去资源分配图中所有结点的连接边，使全部结点都成为孤立结点，则称该图是可完全简化图；若不能使该图完全简化，则称该图是不可完全化简图。 可以证明：当且仅当系统某状态S所对应的资源分配图是不可完全化简的，则S是死锁状态。该充分条件称为死锁定理。
死锁的解除
当发现有进程死锁时，常采用的两种方法是
解除死锁：
（1）剥夺资源。从其它进程剥夺足够数量的资源给死锁进程，以解除死锁状态。
（2）撤消进程。最简单的撤消进程的方法，是使全部死锁进程都夭折掉；或者按照某种顺序（按照解除死锁复杂度递增的顺序）逐个地撤消进程，直至有足够的资源可用，使死锁状态消除为止。
死锁产生，必须要满足四个必要条件，所以，为避免死锁产生，主要注意如何不让这四个必要条件成立，并打破循环等待资源的环路。（×）注意避免与预防的差异
死锁的检测可以通过（资源分配 ）图，利用（ 死锁）定理来实现。
什么叫系统处于安全状态？常用什么方法保持系统处于安全状态？
如果操作系统能保证所有的进程在有限的时间内得到需要的全部资源,则称系统处于安全状态。常用银行家算法动态地检测系统中的资源分配情况和进程对资源的需求情况进行资源分配,确保系统处于安全状态。
系统中有3个进程，4个相同类型的资源，每个进程最多需要2个资源，该系统是否回发生死锁？为什么？
不会发生死锁，6-4<3。
资源分配图如下图，系统是否处于死锁状态？
微信
支付宝
