【第三章 | 处理机调度与死锁】《操作系统慕课版》课后答案 + 复习

水深无声 2023-09-28 11:19 84阅读 0赞

**目录**

【第三章】处理机调度与死锁

| 本章概念

1.处理机调度概述

2.调度算法相关概念

3.实时调度相关概念

4.死锁

5.资源分配图

| 本章算法

1.周转时间与带权周转时间的计算公式

2.调度算法 FCFS SJF PR RR

3.实时调度算法 EDF

4.避免死锁 —— 银行家算法

| 课后简答题

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

## **【第三章】处理机调度与死锁** ##

### **| 本章概念** ###

#### **1.处理机调度概述** ####

*  处理机调度类型：
    
    高级调度（长程调度 / 作业调度） 将外存上处于后备队列中的作业调入内存，主要用于多道批处理系统中
    
    低级调度（中程调度 / 进程调度） 根据某种调度算法，决定就绪队列中的哪个进程应获得处理机
    
    中级调度（短程调度 / 内存调度） 内存调度，将暂不运行的进程，调至外存等待；将处于外存上的急需运行的进程，调入内存运行
 *  作业调度
    
     *  作业 VS 进程： 一个作业可由多个进程组成，且必须至少由一个进程组成，反过来不成立。
     *  作业控制块 JCB：JCB作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息
     *  JCB包含的信息有作业标识、用户名称、用户账 号、作业类、作业状态、调度信息、资源需求、资源使用情况等
     *  作业调度的主要任务：接纳多少个作业、接纳哪些作业
 *  进程调度
    
     *  进程调度的主要任务：保存处理机的现场信息、按某种算法选取进程、把处理器分配给进程
     *  进程调度的机制：排队器：用于将就绪进程插入相应的就绪队列；分派器：用于将选定的进程移出就绪队列；上下文切换器：进行新旧进程之间的上下文切换
     *  进程调度的方式： 抢占式（允许调度程序根据某种原则，去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程）、 非抢占式
 *  内存调度：将在第五章存储器管理介绍
 *  处理机调度的目标：
    
     *  共同目标：提高资源利用率、公平性、平衡性、策略强制执行
     *  批处理系统的目标：平均周转时间短、系统吞吐量高、处理机利用率高
     *  分时系统的目标：响应时间快、均衡性
     *  实时系统的目标：截止时间的保证、可预测性

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

#### **2.调度算法相关概念** ####

*  在此介绍一下简称：FCFS先来先服务、SJF短作业优先、PR优先级调度、RR时间片轮转……
 *  作业调度算法：FCFS、SJF、PR、HRRN（PR的特例）……
 *  进程调度算法：FCFS、SJF、PR、RR、……
 *  FCFS
    
     *  介绍：按照作业到达的先后次序来进行调度
 *  SJF
    
     *  分类：抢占式、非抢占式
     *  介绍：对作业：从后备队列中选择若干个估计运行时间最短的作业；对进程：关联到每个进程下次运行的CPU区间长度，调度最短的进程。
     *  优点：比FCFS算法有明显改进，SJF是最优的（对一组指定的进程而言），它给出了最短的平均等待时间。
     *  缺点：对长作业不利、无法实现人机交互、通常用于作业调度
 *  PR
    
     *  介绍：基于作业/进程的紧迫程度，由外部赋予作业相应的优先级，调度算法 根据优先级进行调度。
     *  分类：抢占式、非抢占式；动态优先级、静态优先级
     *  优点：既可用于作业调度，也可用于进程调度。实现简单，考虑了进程的紧迫程度，灵活，可模拟其它算法
     *  缺点：饥饿，低优先级的进程可能永远得不到运行
     *  高响应比优先调度算法是一种优先级调度算法，用于作业调度。
 *  RR
    
     *  介绍：专为分时系统设计，类似于 FCFS，但增加了抢占。为每个进程分配不 超过一个时间片的 CPU。时间片用完后，该进程将被抢占并插入就绪队列 末尾，循环执行

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

#### **3.实时调度相关概念** ####

*  实时调度是针对实时任务的调度，分为硬实时任务HRT和软实时任务SRT
 *  实时调度所需的条件
    
     *  必要信息：就绪时间、开始截止时间、处理时间、资源要求、优先级
     *  处理能力强：Σ（处理时间i / 周期时间i）≤ N（N为CPU的个数）
     *  采用抢占式调度机制
     *  采用快速切换机制
 *  实时调度算法的分类：HRT、SRT；抢占式（基于时钟中断的抢占式优先级调度算法、立即抢占的优先级调度算法）、非抢占式（非抢占式轮转调度算法、非抢占式优先调度算法）
 *  常见的实时调度算法：最早截至时间优先（Earliest deadline first , EDF）、最低松弛度优先（不考）

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

#### **4.死锁** ####

*  概念：一组等待的进程，其中每一个进程都持有资源，并且等待着由这个组中其他进程所持有的资源
 *  资源
    
     *  可重用性资源：一次只能分配给一个进程，不允许多个进程共享
     *  可消耗性资源：由进程动态创建和消耗 （进程间通信的消息）。
     *  可抢占性资源：某进程在获得这类资源后，该资源可以再被其他进程或系统抢占，如CPU（处理机）和主存区。
     *  不可抢占资源：当系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自行释放，如打印机、磁带机。
 *  死锁的原因：竞争不可抢占性资源引起死锁、竞争可消耗性资源引起死锁、进程推进顺序不当引起死锁
 *  产生死锁的必要条件：互斥、请求和保持、不可抢占、循环等待
 *  系统层面处理死锁：确保系统永远不会进入死锁状态；允许系统进入死锁状态然后恢复系统、忽略这个问题假装系统中从未出现过死锁
 *  理论层面处理死锁：预防、避免、检测、解除
 *  预防死锁
    
     *  互斥：互斥条件是共享资源必须的，不仅不能改变，还应加以保证
     *  请求和保持：必须保证进程申请资源的时候没有占有其他资源
     *  非抢占：如果一个进程的申请没有实现，它要释放所有占有的资源；
     *  循环等待：对所有的资源类型排序进行线性排序，并赋予不同的序 号，要求进程按照递增顺序申请资源。（可防止出现环路）
 *  避免死锁：银行家算法
    
     *  死锁避免算法动态检查资源分配状态，以确保不会出现循环等待的情况
     *  当进程申请一个有效的资源的时候，系统必须确定分配后是安全的
     *  如果存在一个安全序列，则系统处于安全态

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

#### **5.资源分配图** ####

*  资源分配图：进程用⚪表示，资源用 口 表示。 进程指向资源表示【申请】，资源指向进程表示【占用】
    
    由于一类资源可以包含多个资源实例， 我们用方框中的一个圆点来代表一类资源中的一个资源实例
    
    请求边由进程指向方框中的R，而分配边则始于方框中的一个圆点。

![59f7432a92594e83a0b928052ae24066.png][]

*  每一个进程通过如下方法来使用资源：申请、使用、释放
 *  死锁资源分配图如下：
    
    如果图没有环，那么不会有死锁！
    
    如果图有环，那么： 如果每一种资源类型只有一个实例，那么死锁发生； 如果一种资源类型有多个实例，那么可能死锁。

![e852f7ea026644df977fa8501ce85d28.png][]

*  当系统为进程分配资源时，若未采取任何限制性措施，则系统必须提供检测和 解除死锁的手段。为此，系统必须：
    
     *  保存有关资源的请求和分配信息；
     *  提供一种算法，以利用这些信息来检测系统是否已进入死锁状态
 *  通过资源分配图的简化，判断是否死锁 的算法：
    
     *  在资源分配图中，找出一个既不阻塞又非独立的进程结点pi 。
     *  p1释放资源后，便可使p2获得资源而继续运行，直到p2完成后又释放出 它所占有的全部资源；
     *  在进行一系列的简化后，若能消去图中所有的边，使所有进程都成为孤 立结点，则称该图是可完全简化的，即没有死锁

![52b39a3993d44edf947c247c53cc66fd.png][]

*  有关文献已经证明，所有 的简化顺序，都将得到相同的不可简化图
 *  死锁定理：当且仅当S状态的资源分配图是不可完全 简化的。

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

### | 本章算法 ###

#### 1.周转时间与带权周转时间的计算公式 ####

![65960e72fb3e47aba75a5e1b5303ff11.png][]

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

#### 2.调度算法 FCFS SJF PR RR ####

![4c5de83090304e98afeda74eac8478e8.png][]

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

![9cdeb2f20b85493dbb41f8b59e94f3c7.png][]

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

![2b06895854a941b883f0132418c2284b.png][]

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

![c8ed3cec95944ea3b740a97e54ab666b.png][]

![34be03e7fd904e25b11cf091eaf3f3d2.png][]

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

#### 3.实时调度算法 EDF ####

![2043679c4ae2416a98e0eee7b1e027ff.png][]

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

#### **4.避免死锁 —— 银行家算法** ####

所需变量

*  Available: 长度为 m的向量。如果available\[ j \]=k,那么资源Rj 有k个实例有效
 *  Max: n x m 矩阵。 如果Max\[ i, j \]=k,那么进程Pi可以最多请求资源Rj 的k个实例
 *  Allocation: n x m 矩阵。 如果Allocation\[ i, j \]=k,那么进程Pi当前分配了k个资 源Rj的实例
 *  Need: n x m 矩阵。如果Need\[ i, j \]=k,那么进程Pi还需要k个资源Rj的实例

算法流程图

![a9fcef2a01494e3aa1ebc9af2904ceae.png][]

例子

![8e47bf9fb5ac479c86e63ff2fb933c9d.png][]

例题

由5个进程组成进程集合P=\{P0,P1,P2,P3,P4\}，且系统中有3类资源A,B,C，假设在某时刻有表3-4的进程资源分配情况。请问当x,y,z取下列值时，系统是否处于安全状态？

![ac4aad5c1aa640da8f70346b07cf0571.png][]

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

### | 课后简答题 ###

![35bd68aceebf40918e4c2188b5850408.png][]

![f328f46b939a4bb49b7b502f0e4ee7a3.png][] ![2696c27f109d4d82ba0e487784c69a2f.png][]

[59f7432a92594e83a0b928052ae24066.png]: https://img-blog.csdnimg.cn/59f7432a92594e83a0b928052ae24066.png
[e852f7ea026644df977fa8501ce85d28.png]: https://img-blog.csdnimg.cn/e852f7ea026644df977fa8501ce85d28.png
[52b39a3993d44edf947c247c53cc66fd.png]: https://img-blog.csdnimg.cn/52b39a3993d44edf947c247c53cc66fd.png
[65960e72fb3e47aba75a5e1b5303ff11.png]: https://img-blog.csdnimg.cn/65960e72fb3e47aba75a5e1b5303ff11.png
[4c5de83090304e98afeda74eac8478e8.png]: https://img-blog.csdnimg.cn/4c5de83090304e98afeda74eac8478e8.png
[9cdeb2f20b85493dbb41f8b59e94f3c7.png]: https://img-blog.csdnimg.cn/9cdeb2f20b85493dbb41f8b59e94f3c7.png
[2b06895854a941b883f0132418c2284b.png]: https://img-blog.csdnimg.cn/2b06895854a941b883f0132418c2284b.png
[c8ed3cec95944ea3b740a97e54ab666b.png]: https://img-blog.csdnimg.cn/c8ed3cec95944ea3b740a97e54ab666b.png
[34be03e7fd904e25b11cf091eaf3f3d2.png]: https://img-blog.csdnimg.cn/34be03e7fd904e25b11cf091eaf3f3d2.png
[2043679c4ae2416a98e0eee7b1e027ff.png]: https://img-blog.csdnimg.cn/2043679c4ae2416a98e0eee7b1e027ff.png
[a9fcef2a01494e3aa1ebc9af2904ceae.png]: https://img-blog.csdnimg.cn/a9fcef2a01494e3aa1ebc9af2904ceae.png
[8e47bf9fb5ac479c86e63ff2fb933c9d.png]: https://img-blog.csdnimg.cn/8e47bf9fb5ac479c86e63ff2fb933c9d.png
[ac4aad5c1aa640da8f70346b07cf0571.png]: https://img-blog.csdnimg.cn/ac4aad5c1aa640da8f70346b07cf0571.png
[35bd68aceebf40918e4c2188b5850408.png]: https://img-blog.csdnimg.cn/35bd68aceebf40918e4c2188b5850408.png
[f328f46b939a4bb49b7b502f0e4ee7a3.png]: https://img-blog.csdnimg.cn/f328f46b939a4bb49b7b502f0e4ee7a3.png
[2696c27f109d4d82ba0e487784c69a2f.png]: https://img-blog.csdnimg.cn/2696c27f109d4d82ba0e487784c69a2f.png