目录
【第三章】处理机调度与死锁
| 本章概念
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，而分配边则始于方框中的一个圆点。
-
每一个进程通过如下方法来使用资源：申请、使用、释放
-
死锁资源分配图如下：
如果图没有环，那么不会有死锁！
如果图有环，那么： 如果每一种资源类型只有一个实例，那么死锁发生； 如果一种资源类型有多个实例，那么可能死锁。
-
当系统为进程分配资源时，若未采取任何限制性措施，则系统必须提供检测和 解除死锁的手段。为此，系统必须：
-
保存有关资源的请求和分配信息；
-
提供一种算法，以利用这些信息来检测系统是否已进入死锁状态
-
-
通过资源分配图的简化，判断是否死锁 的算法：
-
在资源分配图中，找出一个既不阻塞又非独立的进程结点pi 。
-
p1释放资源后，便可使p2获得资源而继续运行，直到p2完成后又释放出 它所占有的全部资源；
-
在进行一系列的简化后，若能消去图中所有的边，使所有进程都成为孤 立结点，则称该图是可完全简化的，即没有死锁
-
-
有关文献已经证明，所有 的简化顺序，都将得到相同的不可简化图
-
死锁定理：当且仅当S状态的资源分配图是不可完全 简化的。
| 本章算法
1.周转时间与带权周转时间的计算公式
2.调度算法 FCFS SJF PR RR
3.实时调度算法 EDF
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的实例
算法流程图
例子
例题
由5个进程组成进程集合P={P0,P1,P2,P3,P4}，且系统中有3类资源A,B,C，假设在某时刻有表3-4的进程资源分配情况。请问当x,y,z取下列值时，系统是否处于安全状态？
| 课后简答题
文章来源：https://www.toymoban.com/news/detail-788663.html
文章来源地址https://www.toymoban.com/news/detail-788663.html
到了这里，关于【第三章 | 处理机调度与死锁】《操作系统 慕课版》课后答案 + 复习的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
