第三章 处理机调度和死锁(第10、11、12讲)

1、2022-3-12阜阳师范学院计算机与信息学院1第第3章章 处理机调度与死锁处理机调度与死锁l3.1 处理机调度的基本概念处理机调度的基本概念l3.2 调度算法调度算法l3.3 实时调度实时调度l3.4 产生死锁的原因和必要条件产生死锁的原因和必要条件l3.5 预防死锁的方法预防死锁的方法l3.6 死锁的检测与解除死锁的检测与解除 2022-3-12阜阳师范学院计算机与信息学院23.1 处理机调度的基本概念处理机调度的基本概念l3.1.1 高级调度、中级调度、低级调度高级调度、中级调度、低级调度l3.1.2 调度队列模型调度队列模型l3.1.3 选择调度方式和调度算法的若干准则选择调度方式和调

2、度算法的若干准则2022-3-12阜阳师范学院计算机与信息学院32022-3-12阜阳师范学院计算机与信息学院43.1.1 高级、中级和低级调度高级、中级和低级调度经历下述三级调度经历下述三级调度: :1、高级调度（、高级调度（High Scheduling）2、中级调度（、中级调度（Intermediate-Level Scheduling）3、低级调度（、低级调度（Low Level Scheduling）2022-3-12阜阳师范学院计算机与信息学院51. 高级调度高级调度 又称为又称为作业调度、宏观调度作业调度、宏观调度或或长长程调度程调度。用于决定把后备队列中的哪。用于决定把后备队列

3、中的哪些作业调入内存，为他们分配必要的些作业调入内存，为他们分配必要的资源，并创建进程。资源，并创建进程。 批处理系统批处理系统 ：分时系统分时系统 ：实时系统实时系统 ：需要作业调度需要作业调度不需作业调度不需作业调度不需作业调度不需作业调度2022-3-12阜阳师范学院计算机与信息学院61. 高级调度高级调度执行作业调度时，必须作出两个决定：执行作业调度时，必须作出两个决定：l接纳多少作业接纳多少作业每次接纳多少作业进每次接纳多少作业进入内存，取决于入内存，取决于多道程序度多道程序度，即允许多，即允许多少个作业同时在内存中运行。少个作业同时在内存中运行。l接纳哪些作业接纳哪些作业应接纳哪些

4、作业从外应接纳哪些作业从外存调入内存，取决于所采用的存调入内存，取决于所采用的调度算法调度算法。2022-3-12阜阳师范学院计算机与信息学院72. 低级调度低级调度 通常也称为通常也称为进程调度进程调度、微观调度微观调度或或短程调短程调度度。进程调度是最基本的一种调度，在三种。进程调度是最基本的一种调度，在三种OS中都有。用于决定就绪队列中哪个进程应先获中都有。用于决定就绪队列中哪个进程应先获得得处理机，并将处理机分配给选中的进程。处理机，并将处理机分配给选中的进程。为实现进程调度，应具有如下三个基本机制：为实现进程调度，应具有如下三个基本机制： 排队器排队器 分派器分派器 上下文切换上下文

5、切换2022-3-12阜阳师范学院计算机与信息学院82. 低级调度低级调度进程调度可采用下述两种调度方式：进程调度可采用下述两种调度方式：l非抢占方式非抢占方式l抢占方式抢占方式抢占的原则有：抢占的原则有：（1）优先权原则）优先权原则（2）短作业（进程）优先原则）短作业（进程）优先原则（3）时间片原则）时间片原则2022-3-12阜阳师范学院计算机与信息学院93. 中级调度中级调度 中级调度又称为中级调度又称为交换调度交换调度或或中程中程调度。调度。 它按一定的算法将外存中已具备运它按一定的算法将外存中已具备运行条件的进程换入内存，而将内存中行条件的进程换入内存，而将内存中处于阻塞状态的某些进

6、程换出至外存。处于阻塞状态的某些进程换出至外存。运行运行就绪就绪阻塞阻塞挂起阻塞挂起阻塞挂起就绪挂起就绪创建创建退出退出进程调度进程调度中级调度中级调度作业调度作业调度调度的层次调度的层次2022-3-12阜阳师范学院计算机与信息学院113.1.2 调度队列模型调度队列模型1.仅有仅有进程调度进程调度的调度队列模型的调度队列模型2.具有具有高级和低级调度高级和低级调度的调度队列模型的调度队列模型3.同时具有同时具有三级调度三级调度的调度队列模型的调度队列模型2022-3-12阜阳师范学院计算机与信息学院121. 仅有进程调度的调度队列模型仅有进程调度的调度队列模型 在分时系统中在分时系统中就绪

7、进程就绪进程组织成组织成FIFO队队列形式，按列形式，按时间片轮转时间片轮转方式运行。方式运行。CPU就就 绪绪 队队 列列阻阻 塞塞 队队 列列时间片完时间片完进程调度进程调度等待事件等待事件进程完成进程完成交互用户交互用户事件出现事件出现2022-3-12阜阳师范学院计算机与信息学院132. 具有高级和低级调度的调度队列模型具有高级和低级调度的调度队列模型CPU就就 绪绪 队队 列列时间片完时间片完进程调度进程调度等待事件等待事件1进程完成进程完成后备队列后备队列等待事件等待事件2等待事件等待事件n事件事件1出现出现事件事件2出现出现事件事件n出现出现作业调度作业调度2022-3-12阜阳

8、师范学院计算机与信息学院143. 3. 同时具有三级调度的调度队列模型同时具有三级调度的调度队列模型CPU就就 绪绪 队队 列列时间片完时间片完进程调度进程调度进程完进程完成成后备队列后备队列等待事件等待事件事件出现事件出现作业调度作业调度批量作业批量作业交互型作业交互型作业中级调度中级调度就绪、挂起队列就绪、挂起队列事件出现事件出现阻阻 塞、挂塞、挂 起起 队队 列列挂起挂起阻阻 塞塞 队队 列列挂起挂起中级调度中级调度2022-3-12阜阳师范学院计算机与信息学院153.1.3 选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则l面向用户的准则面向用户的准则周转时间短周转时间

9、短平均周转时间平均周转时间T T平均带权周转时间（平均带权周转时间（W= W= T(T(周转周转)/Ts(CPU)/Ts(CPU执行执行)响应时间快响应时间快截止时间的保证截止时间的保证优先权准则优先权准则o面向系统的准则面向系统的准则 系统吞吐量高系统吞吐量高 处理机利用率好处理机利用率好 各类资源的平衡利用各类资源的平衡利用2022-3-12阜阳师范学院计算机与信息学院163.2 调度算法调度算法l3.2.1 FCFS3.2.1 FCFS与与SJF/SPFSJF/SPF调度算法调度算法l3.2.2 3.2.2 高优先权优先调度算法高优先权优先调度算法l3.2.3 3.2.3 基于时间片的轮

10、转调度算法基于时间片的轮转调度算法2022-3-12阜阳师范学院计算机与信息学院173.2.1 FCFS3.2.1 FCFS与与SJF/SPFSJF/SPF调度算法调度算法1. 先来先服务调度算先来先服务调度算法法(FCFS) 按进程申请按进程申请CPU（就绪）的次序（就绪）的次序processRun timeP127P23P35P1P2P30 27 30 352022-3-12阜阳师范学院计算机与信息学院18 FCFS实例实例 下表列出了下表列出了A、B、C、D四个作业分别到达四个作业分别到达系统的时间、要求服务的时间、开始执行系统的时间、要求服务的时间、开始执行的时间及各自的完成时间，计算

11、出各自的的时间及各自的完成时间，计算出各自的周转时间和带权周转时间。周转时间和带权周转时间。FCFS（First Come First Serve)2022-3-12阜阳师范学院计算机与信息学院19作业作业名名到达到达时间时间服务服务时间时间开始开始执行执行时间时间完成完成时间时间周转周转时间时间带权带权周转周转时间时间A01B1100C21D3100FCFS（First Come First Serve)0111110110011011021001001022021991.992022-3-12阜阳师范学院计算机与信息学院20FCFSFCFS的特点的特点: : lFCFS调度算法调度算法有利

12、于有利于CPU繁忙型繁忙型的作业，的作业，而不利于而不利于I/O繁忙型的作业（进程）繁忙型的作业（进程）l比较比较有利于长作业有利于长作业，而不利于短作业，而不利于短作业FCFS（First Come First Serve)2022-3-12阜阳师范学院计算机与信息学院212. 2. 短作业（进程）优先调度算法短作业（进程）优先调度算法带权周转时间带权周转时间周转时间周转时间完成时间完成时间 SJF带权周转时间带权周转时间周转时间周转时间完成时间完成时间 FCFS42534服务时间服务时间43210到达时间到达时间平均平均EDCBA作业名作业名 作业情作业情 况况调度算法调度算法441762

13、1210214115.518143.592.8441982.6718163.2631.51392.2582.12022-3-12阜阳师范学院计算机与信息学院222 .2 . 短作业（进程）优先调度算法短作业（进程）优先调度算法SJF调度算法的优缺点：调度算法的优缺点：优点：优点：有效降低作业的平均等待时间，提高系统有效降低作业的平均等待时间，提高系统吞吐量吞吐量缺点：缺点：(1) 对长作业不利对长作业不利(2) 不能保证紧迫性作业（进程）的及时处理不能保证紧迫性作业（进程）的及时处理(3) 不一定能真正做到短作业优先。不一定能真正做到短作业优先。2022-3-12阜阳师范学院计算机与信息学院2

14、33.2.2 高优先权优先调度算法高优先权优先调度算法1. 优先权调度算法的类型优先权调度算法的类型 为照顾紧迫性作业，使之在进入系统后为照顾紧迫性作业，使之在进入系统后便获得优先处理，引入了便获得优先处理，引入了最高优先权优先最高优先权优先（HPF）调度算法。它分为两种：调度算法。它分为两种：l非抢占式优先权算法非抢占式优先权算法l抢占式优先权调度算法抢占式优先权调度算法2022-3-12阜阳师范学院计算机与信息学院243.2.2 高优先权优先调度算法高优先权优先调度算法2. 2. 优先权的类型优先权的类型1)静态优先权：在创建进程时确定的，在进静态优先权：在创建进程时确定的，在进程的整个运

15、行期间保持不变程的整个运行期间保持不变,又称优先数。又称优先数。2)动态优先权：在创建进程时所赋予的优先动态优先权：在创建进程时所赋予的优先权可以随进程的推进或随其等待时间的增权可以随进程的推进或随其等待时间的增加而改变。加而改变。2022-3-12阜阳师范学院计算机与信息学院253. 高响应比优先调度算法高响应比优先调度算法(HRRN) 为每个作业引入动态优先权，并使作为每个作业引入动态优先权，并使作业的优先级随着等待时间的增加而以速率业的优先级随着等待时间的增加而以速率a提高，则可解决问题。见下式：提高，则可解决问题。见下式： 优先权优先权=(等待时间等待时间+要求服务时间要求服务时间)/

16、要求服务时间要求服务时间 响应时间响应时间/要求服务时间要求服务时间 3.2.2 高优先权优先调度算法高优先权优先调度算法2022-3-12阜阳师范学院计算机与信息学院26 作业作业 提交时间提交时间 运行时间运行时间 1 8.0 1.0 2 8.5 0.5 3 9.0 0.2 4 9.1 0.13.2.2 高优先权优先调度算法高优先权优先调度算法2022-3-12阜阳师范学院计算机与信息学院273.2.3 基于时间片的轮转调度算法基于时间片的轮转调度算法(RR) 在分时系统中，为保证能及时响应用在分时系统中，为保证能及时响应用户的请求，必须采用基于户的请求，必须采用基于时间片时间片的轮转式的

17、轮转式进程调度算法。在早期，分时系统中采用进程调度算法。在早期，分时系统中采用的是简单的时间片轮转法，进入的是简单的时间片轮转法，进入90年代后，年代后，广泛采用广泛采用多级反馈队列调度算法多级反馈队列调度算法。2022-3-12阜阳师范学院计算机与信息学院28u将系统中所有的就绪进程按照将系统中所有的就绪进程按照FCFSFCFS原则，排成原则，排成一个一个队列队列。u每次调度时将每次调度时将CPU分派给分派给队首队首进程，让其执行进程，让其执行一个一个时间片时间片。u在一个时间片结束时，将其送到在一个时间片结束时，将其送到就绪队列的末就绪队列的末尾尾，并通过上下文切换执行当前的队首进程。，并

18、通过上下文切换执行当前的队首进程。一、时间片轮转算法一、时间片轮转算法1. 基本原理基本原理2022-3-12阜阳师范学院计算机与信息学院292. 时间片长度的确定时间片长度的确定v时间片长度变化的影响时间片长度变化的影响过长过长退化为退化为FCFS算法。算法。过短过短用户的一次请求需要多个时间片才用户的一次请求需要多个时间片才能处理完，上下文切换次数增加。能处理完，上下文切换次数增加。对响应时间的要求：对响应时间的要求：T(响应时间响应时间)=N(进程数目进程数目)*q(时间片时间片)一、时间片轮转算法一、时间片轮转算法2022-3-12阜阳师范学院计算机与信息学院300 1 2 3 4 5

19、 6 7 8 9 10 11 12 13 14 15 16 17 18ABCDEA AB BABAC ACB ACBDCBDACBDA EBDAECBDAEC DAECBBDAEC DAECDAEC AECAEC EC2022-3-12阜阳师范学院计算机与信息学院31二、多级反馈队列调度算法二、多级反馈队列调度算法 实施过程如下：实施过程如下：（1） 应设置多个队列并为各个队列赋予不同的优应设置多个队列并为各个队列赋予不同的优先级。先级。第一个最高，依次降低第一个最高，依次降低。该算法赋予各个。该算法赋予各个队列中进程执行时间片的大小也不相同，队列中进程执行时间片的大小也不相同，优先权优先权越

20、高，时间片越短。越高，时间片越短。1. 调度算法调度算法2022-3-12阜阳师范学院计算机与信息学院32多级反馈队列调度算法多级反馈队列调度算法 就绪队列1就绪队列2就绪队列3就绪队列nS1S2S3至CPU至CPU至CPU至CPU(时间片：S1 S2 S3)2022-3-12阜阳师范学院计算机与信息学院33二、多级反馈队列调度算法二、多级反馈队列调度算法(2) 当一个当一个新进程新进程进入内存后，首先将它放入进入内存后，首先将它放入第第一队列的末尾一队列的末尾，按，按FCFS原则排队等待调度。如原则排队等待调度。如它在一个时间片结束时尚未完成，调度程序便它在一个时间片结束时尚未完成，调度程序

21、便将该进程转入第二队列的末尾。将该进程转入第二队列的末尾。(3）仅当第）仅当第1（i-1）队列）队列空闲空闲时，才会调度第时，才会调度第i队列中的进程运行。队列中的进程运行。2022-3-12阜阳师范学院计算机与信息学院342. 多级反馈队列调度算法的性能多级反馈队列调度算法的性能l终端型作业用户终端型作业用户l短批处理作业用户短批处理作业用户l长批处理作业用户长批处理作业用户二、多级反馈队列调度算法二、多级反馈队列调度算法2022-3-12阜阳师范学院计算机与信息学院35第第3章章 处理机调度与死锁处理机调度与死锁l3.3 实时调度实时调度l3.4 产生死锁的原因和必要条件产生死锁的原因和必

22、要条件l3.5 预防死锁的方法预防死锁的方法l3.6 死锁的检测与解除死锁的检测与解除 2022-3-12阜阳师范学院计算机与信息学院363.3 实时调度实时调度l实时调度：实时调度：l合理安排就绪实时任务的执行次序，满足每合理安排就绪实时任务的执行次序，满足每个实时任务时间约束条件的调度。个实时任务时间约束条件的调度。l实时任务：实时任务：l具有明确时间约束的计算任务。具有明确时间约束的计算任务。2022-3-12阜阳师范学院计算机与信息学院373.3 实时调度实时调度l3.3.1 实现实时调度的基本条件实现实时调度的基本条件l3.3.2 实时调度算法的分类实时调度算法的分类l3.3.3 常

23、用的几种实时调度算法常用的几种实时调度算法2022-3-12阜阳师范学院计算机与信息学院383.3.1 实现实时调度的基本条件实现实时调度的基本条件l提供必要的信息提供必要的信息l系统处理能力强系统处理能力强l采用抢占式调度机制采用抢占式调度机制l具有快速切换机制具有快速切换机制2022-3-12阜阳师范学院计算机与信息学院391. 提供必要的信息提供必要的信息 l就绪时间就绪时间l开始截止时间和完成截止时间开始截止时间和完成截止时间l处理时间处理时间l资源要求资源要求l优先级优先级2022-3-12阜阳师范学院计算机与信息学院402. 2. 系统处理能力强系统处理能力强 假如系统中有假如系统

24、中有M个周期性的硬实时任务，个周期性的硬实时任务，处理时间为处理时间为Ci，周期时间表示为，周期时间表示为Pi 则则单机单机系统中必须满足条件系统中必须满足条件 （ Ci / Pi ）1 多处多处理机系统理机系统 （ Ci / Pi ）N2022-3-12阜阳师范学院计算机与信息学院413. 采用抢占式调度机制采用抢占式调度机制l 硬实时任务：硬实时任务： 广泛采用抢占机制广泛采用抢占机制 l小的实时系统：小的实时系统： 可采用非抢占调度机可采用非抢占调度机制（简化调度程序和对任务调度时所制（简化调度程序和对任务调度时所花费的系统开销）花费的系统开销）2022-3-12阜阳师范学院计算机与信息

25、学院424. 具有快速切换机制具有快速切换机制 (1) 对外部中断的快速响应能力对外部中断的快速响应能力(2) 快速的任务分派能力快速的任务分派能力2022-3-12阜阳师范学院计算机与信息学院433.3.2 实时调度算法的分类实时调度算法的分类可以按照不同方式对实时调度算法加以分类：可以按照不同方式对实时调度算法加以分类：l根据根据实时任务性质实时任务性质的不同可分为的不同可分为硬实时硬实时调度调度算法和算法和软实时软实时调度算法；调度算法；l按按调度方式调度方式的不同可分为的不同可分为非抢占非抢占调度算法和调度算法和抢占抢占调度算法；调度算法；2022-3-12阜阳师范学院计算机与信息学院

26、443.3.3 常用的几种实时调度算法常用的几种实时调度算法 l最早截止时间优先最早截止时间优先EDFEDF（Earliest Earliest Deadline FirstDeadline First）算法）算法l最低松弛度优先最低松弛度优先LLFLLF（Least Laxity Least Laxity FirstFirst）算法）算法2022-3-12阜阳师范学院计算机与信息学院45EDFEDF算法用于非抢占调度图示算法用于非抢占调度图示 1 3 4 2t按开始截止时间按开始截止时间早晚的排序早晚的排序任务执行任务执行任务到达任务到达 1 3 4 2 1 2 3 4 1. 最早截止时间优

27、先最早截止时间优先EDF算法算法 截止时间越早，其优先级越高截止时间越早，其优先级越高2022-3-12阜阳师范学院计算机与信息学院462. 最低松弛度优先最低松弛度优先LLF算法算法l松弛度松弛度=完成截止时间完成截止时间运行时间运行时间当前时间当前时间l任务的紧急程度愈高，松弛度愈低，任务的紧急程度愈高，松弛度愈低，优先级愈高。优先级愈高。l该算法主要用于该算法主要用于可抢占可抢占调度方式中调度方式中2022-3-12阜阳师范学院计算机与信息学院47LLF算法例算法例tA1 A2 A3 A4 A5 A6B1 B2 0 20 40 60 80 100 120 假如在一个实时系统中，有两个周期

28、型实时任假如在一个实时系统中，有两个周期型实时任务务A A、B B，任务，任务A A要求每要求每20ms20ms执行一次，执行时间执行一次，执行时间为为10ms10ms；任务；任务B B要求每要求每50ms50ms执行一次，执行时间执行一次，执行时间为为25ms25ms；由此可得知；由此可得知ABAB任务每次必须完成的时任务每次必须完成的时间分别为间分别为A1A1、A2A2、A3A3和和B1B1、B2B2、B3B3如下图：如下图：2022-3-12阜阳师范学院计算机与信息学院48LLF算法例图示算法例图示tt1 t2 t3 t4 t5 t6 t7 t8 0 10 20 30 40 50 60

29、70 80A1(10) A2(10) A3(10) A4 (10) B1(20) B1 (5) B2(15) B2(10) 2022-3-12阜阳师范学院计算机与信息学院493.5 产生死锁的原因和必要条件产生死锁的原因和必要条件l3.5.1 产生死锁的原因产生死锁的原因l3.5.2 产生死锁的必要条件产生死锁的必要条件l3.5.3 处理死锁的基本方法处理死锁的基本方法2022-3-12阜阳师范学院计算机与信息学院50关于死锁关于死锁 死锁死锁是指多个进程在运行过程中因是指多个进程在运行过程中因争争夺资源夺资源而造成的一种僵局，当进程处于这而造成的一种僵局，当进程处于这种状态时，若无外力作用，

30、它们都将无法种状态时，若无外力作用，它们都将无法再向前推进。再向前推进。2022-3-12阜阳师范学院计算机与信息学院513.5.1 产生死锁的原因产生死锁的原因产生死锁的原因可归结为如下两点：产生死锁的原因可归结为如下两点：1.竞争资源竞争资源2.进程间推进顺序非法进程间推进顺序非法可剥夺和可剥夺和非剥夺性资源非剥夺性资源永久性资源和永久性资源和临时性资源临时性资源2022-3-12阜阳师范学院计算机与信息学院52P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)D进程推进顺序不当引起死锁进程推进顺

31、序不当引起死锁2022-3-12阜阳师范学院计算机与信息学院533.5.2 产生死锁的必要条件产生死锁的必要条件 虽然进程在运行过程中可能发生死锁，但死虽然进程在运行过程中可能发生死锁，但死锁的发生也必须具备一定的条件。可以看出，锁的发生也必须具备一定的条件。可以看出，必须具备以下四个条件必须具备以下四个条件:1. 互斥条件：互斥条件：进程所竞争的资源必须被互斥使用。进程所竞争的资源必须被互斥使用。2. 请求和保持条件：请求和保持条件：指进程已经保持了至少一个指进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程阻塞，

32、但又被其他进程占有，此时请求进程阻塞，但又对自己已获得的其他资源保持不放又对自己已获得的其他资源保持不放。2022-3-12阜阳师范学院计算机与信息学院543.5.2 产生死锁的必要条件产生死锁的必要条件 3. 不剥夺条件：不剥夺条件：指进程已获得的资源，只能指进程已获得的资源，只能在使用完时由自己释放。在使用完时由自己释放。 4. 环路等待条件：环路等待条件：指在发生死锁时，必然存指在发生死锁时，必然存在一个在一个“进程进程资源资源”的环形链，环路的环形链，环路中的每一条边是进程在请求另一进程已经中的每一条边是进程在请求另一进程已经占有的资源。占有的资源。2022-3-12阜阳师范学院计算机

33、与信息学院553.5.3 处理死锁的基本方法处理死锁的基本方法一、预防死锁一、预防死锁消除产生死锁的必要条件消除产生死锁的必要条件二、避免死锁二、避免死锁分配资源时防止进入不安分配资源时防止进入不安全状态全状态三、检测死锁三、检测死锁不预防死锁，出现死锁就不预防死锁，出现死锁就解除解除四、解除死锁四、解除死锁与检测死锁配合使用与检测死锁配合使用2022-3-12阜阳师范学院计算机与信息学院563.6 预防与避免死锁的方法预防与避免死锁的方法l3.6.1 3.6.1 预防死锁预防死锁l3.6.2 3.6.2 系统安全状态系统安全状态l3.6.3 3.6.3 利用银行家算法避免死锁利用银行家算法避

34、免死锁2022-3-12阜阳师范学院计算机与信息学院573.6.1 3.6.1 预防死锁预防死锁1. 摒弃摒弃“请求和保持请求和保持”条件条件l静态资源分配法静态资源分配法l优点优点：算法简单、易于实现且很安全算法简单、易于实现且很安全l缺点缺点：资源浪费严重，进程延迟运行资源浪费严重，进程延迟运行2022-3-12阜阳师范学院计算机与信息学院582. 2. 摒弃摒弃“不剥夺不剥夺”条件条件l资源暂时释放策略资源暂时释放策略:申请新的资源得不到申请新的资源得不到满足则暂时释放已有的所有资源。从而满足则暂时释放已有的所有资源。从而摒弃了摒弃了“不剥夺不剥夺”条件。条件。l该方法实现起来比较复杂且

35、付出很大代该方法实现起来比较复杂且付出很大代价。可能会造成前功尽弃，反复申请和价。可能会造成前功尽弃，反复申请和释放释放(抖动抖动)情况。情况。3.6.1 3.6.1 预防死锁预防死锁2022-3-12阜阳师范学院计算机与信息学院593. 摒弃摒弃“环路等待环路等待”条件条件l有序资源分配法：有序资源分配法：l与前两种策略比较，资源利用率和系统吞吐与前两种策略比较，资源利用率和系统吞吐量都有较明显的改善。量都有较明显的改善。l但也存在严重问题：为资源编号限制新设备但也存在严重问题：为资源编号限制新设备的增加；进程使用设备顺序与申请顺序相反；的增加；进程使用设备顺序与申请顺序相反；限制用户编程自

36、由。限制用户编程自由。r1r2rk.申请次序申请次序rm2022-3-12阜阳师范学院计算机与信息学院60检测检测可满足请求可满足请求 分配分配 不分配不分配安全安全不安全不安全系统处于安全状态系统处于安全状态：存在安全进程序列存在安全进程序列;安全安全不安全不安全死锁死锁1. 1. 安全状态安全状态3.6.2 系统安全状态系统安全状态l避免死锁的实质避免死锁的实质就是系统在进行资源分配时，如就是系统在进行资源分配时，如何使系统不进入不安全状态。何使系统不进入不安全状态。2022-3-12阜阳师范学院计算机与信息学院61C 9 2 72. 安全状态之例安全状态之例 假定系统中有三个进程假定系统

37、中有三个进程A、B和和C，共有，共有12台磁带机。台磁带机。进程进程A总共要求总共要求10台，台，B和和C分别要求分别要求4台和台和9台。假设台。假设在在T0时刻时刻,进程进程A、B和和C已已分别获得分别获得5台、台、2台和台和2台，台，尚有尚有3台未分配，如下表所台未分配，如下表所示：示：进进程程最大最大需求需求已分已分配配还需还需可用可用ABC10495225273进进程程最大最大需求需求已分已分配配还需还需可用可用B 4 2 235A 10 5 510 经分析发现，在经分析发现，在T0时刻系时刻系统是安全的，因为此时存统是安全的，因为此时存在一个安全序列在一个安全序列，即只要系统按此进程

38、序列即只要系统按此进程序列分配资源，就能使每个进分配资源，就能使每个进程都顺利完成。程都顺利完成。122022-3-12阜阳师范学院计算机与信息学院623. 由安全状态向不安全状态的转换由安全状态向不安全状态的转换l如果在如果在T0时刻后，时刻后，C又请又请求到一台磁带机，若此时求到一台磁带机，若此时系统把剩余系统把剩余3台中的台中的1台分台分配给配给C，则系统便进入不，则系统便进入不安全状态。因为，此时再安全状态。因为，此时再也无法找到一个安全序列，也无法找到一个安全序列，结果导致死锁结果导致死锁。进进程程最大最大需求需求已分已分配配还需还需可用可用A10553B422C937o 所以，引入

39、所以，引入安全状态的目的安全状态的目的在于进行资源分配时，要在于进行资源分配时，要使系统不发生死锁，只要保证当前的系统状态是安全的，使系统不发生死锁，只要保证当前的系统状态是安全的，即每次资源分配之后系统都处于安全状态。即每次资源分配之后系统都处于安全状态。 2C 9 3 62022-3-12阜阳师范学院计算机与信息学院633.6.3 利用银行家算法避免死锁利用银行家算法避免死锁l最有代表性的避免死锁的算法，是最有代表性的避免死锁的算法，是Dijkstra的银行的银行家算法。这是由于该算法能用于银行系统现金贷家算法。这是由于该算法能用于银行系统现金贷款的发放而得名的。款的发放而得名的。1.银行

40、家算法中的数据结构银行家算法中的数据结构（1）可利用资源向量）可利用资源向量Available。这是一个含有。这是一个含有m个元素的个元素的数组，其中的每一个元素代表一类可利用的资源数目，其动数组，其中的每一个元素代表一类可利用的资源数目，其动态初始值是系统中所配置的该类全部可用资源的数目，其数态初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配与回收而动态的改变。如果值随该类资源的分配与回收而动态的改变。如果Availablej=K,则表示系统中现有则表示系统中现有Rj类资源类资源K个。个。（2）最大需求矩阵）最大需求矩阵Max。这是一个。这是一个n*m的矩阵，它定义了系的

41、矩阵，它定义了系统中统中n个进程中的每一个进程对个进程中的每一个进程对m类资源的最大需求。如果类资源的最大需求。如果Maxi,j=K,则表示进程则表示进程i需要需要Rj类资源的最大数目为类资源的最大数目为K。（3）分配矩阵）分配矩阵Allocation。这也是一个。这也是一个n*m的矩阵，它定义的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果了系统中每一类资源当前已分配给每一进程的资源数。如果Allocationi,j=K,则表示进程则表示进程i当前已分得当前已分得Rj类资源的数目为类资源的数目为K。（4）需求矩阵）需求矩阵Need。这也是一个。这也是一个n*m的矩阵，用以表

42、示每一的矩阵，用以表示每一个进程尚需的各类资源数。如果个进程尚需的各类资源数。如果Needi,j=K,则表示进程则表示进程i还需还需要要Rj类资源类资源K个，方能完成其任务。个，方能完成其任务。上述三个矩阵间存在的关系：上述三个矩阵间存在的关系：Needi,j=Maxi,j-Allocationi,j2022-3-12阜阳师范学院计算机与信息学院643.6.3 利用银行家算法避免死锁利用银行家算法避免死锁2.银行家算法银行家算法 设设Requesti是进程是进程Pi的请求向量，如的请求向量，如果果Requesti j=K，表示进程，表示进程Pi需要需要K个个Rj类型的资源。当类型的资源。当Pi

43、发出资源请求后，发出资源请求后，系统按下述步骤进行检查：系统按下述步骤进行检查：2022-3-12阜阳师范学院计算机与信息学院65（1）如果）如果Requestij= Needi,j,便转向步骤便转向步骤2；否则认为；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。出错，因为它所需要的资源数已超过它所宣布的最大值。（2）如果）如果Requestij= Availablej,便转向步骤便转向步骤3；否则，；否则，表示尚无足够资源，表示尚无足够资源，Pi需等待。需等待。 （3）系统试探着把资源分配给进程）系统试探着把资源分配给进程Pi ，并修改下面数据结，并修改下面数据结构中的数值：构中

44、的数值： Availablej:= Availablej- Requestij; Allocationi,j:=Allocationi,j+Requestij; Needi,j:=Needi,j-Requestij;（4）系统执行安全性算法，检查此次资源分配后系统是否）系统执行安全性算法，检查此次资源分配后系统是否出于安全状态以决定是否完成本次分配。出于安全状态以决定是否完成本次分配。银行家算法银行家算法2022-3-12阜阳师范学院计算机与信息学院66Pi请求资源请求资源RequestJ NeedJ请求超量，错返请求超量，错返RequestJ Available不满足，等待不满足，等待Ava

45、ilable:=Available-RequestJAllocationJ:=AllocationJ+RequestJNeedJ:=NeedJ-RequestJ安全安全确认，确认，pi继续继续Available:=Available+RequestJAllocationJ:=AllocationJ-RequestJNeedJ:=NeedJ+RequestJpi等待等待FTFTTF请求的资源是否超请求的资源是否超出实际需求出实际需求是否有足够的是否有足够的资源资源暂时分配资源暂时分配资源恢复原来的资源恢复原来的资源分配状态分配状态2022-3-12阜阳师范学院计算机与信息学院673.6.3 利用

46、银行家算法避免死锁利用银行家算法避免死锁3.安全性算法安全性算法系统所执行的安全性算法可描述如下：系统所执行的安全性算法可描述如下：（1）设置两个向量：）设置两个向量： 工作向量工作向量work：表示系统可提供给进程继续运行：表示系统可提供给进程继续运行所需的各类资源数目，它含有所需的各类资源数目，它含有m个元素，在执行个元素，在执行安全算法开始时，安全算法开始时，work:=Available; Finish: 它表示系统是否有足够的资源分配进程，它表示系统是否有足够的资源分配进程，使之运行完成。开始时先做使之运行完成。开始时先做Finishi:=false;当有当有足够资源分配给进程时，再

47、令足够资源分配给进程时，再令Finishi:=true。2022-3-12阜阳师范学院计算机与信息学院68（2）从进程集合中找到一个能满足下述条件的进程：）从进程集合中找到一个能满足下述条件的进程： Finishi=false;Needi,j=workj;若找到，执行步骤若找到，执行步骤3，否则执行步骤否则执行步骤4。 （3）当进程）当进程Pi获得资源后，可顺利执行，直至完成，并释放获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：出分配给它的资源，故应执行： workj:= worki+ Allocationi,j ; Finishi:=true; goto step 2;

48、（4）如果所有进程的）如果所有进程的Finishi=true都满足，则表示系统处都满足，则表示系统处于安全状态；否则，系统处于不安全状态。于安全状态；否则，系统处于不安全状态。安全性算法安全性算法2022-3-12阜阳师范学院计算机与信息学院69安全性检测算法安全性检测算法FWork:=Available;Finish:=false; 有满足条件的有满足条件的j:Finishi=falseNeedj WorkFinishi=true;Work:=Work+AllocationjT i ,Finishi=trueTF安全安全不安全不安全赋初值赋初值进程是否完成进程是否完成资源是否够用资源是否够用

49、进程获得资源后，顺进程获得资源后，顺利完成并释放资源利完成并释放资源进程是否进程是否都完成都完成2022-3-12阜阳师范学院计算机与信息学院704. 银行家算法之例银行家算法之例 假定系统中有五个进程假定系统中有五个进程PP0 0,P,P1 1,P,P2 2,P,P3 3,P,P4 4 和三类资和三类资源源A,B,CA,B,C，各种资源的数量分别为，各种资源的数量分别为1010、5 5、7 7，在，在T T0 0时刻的资源分配情况如图所示。时刻的资源分配情况如图所示。4 3 10 0 24 3 3P40 1 12 1 12 2 2P36 0 03 0 29 0 2P21 2 22 0 03

50、2 2P13 3 27 4 30 1 07 5 3P0AvailableA B CNeedA B CAllocationA B CMaxA B C 资源情况资源情况进程进程2022-3-12阜阳师范学院计算机与信息学院714. 4. 银行家算法之例银行家算法之例 T0时刻的安全性：时刻的安全性：利用安全性算法对利用安全性算法对T0时刻的资源分配情时刻的资源分配情况进行分析可知，在况进行分析可知，在T0时刻存在着一个安全序列时刻存在着一个安全序列P1,P3,P4,P2,P0，故系统是安全的。，故系统是安全的。FalseFalseFalseFalseFalseTrue10 5 70 1 07 4

51、310 4 7P0True10 4 73 0 26 0 07 4 5P2True7 4 50 0 24 3 17 4 3P4True 7 4 32 1 10 1 15 3 2P3True5 3 22 0 01 2 23 3 2P1FinishWork+AllocationA B CAllocationA B CNeedA B CWorkA B C 资源情况资源情况进程进程2022-3-12阜阳师范学院计算机与信息学院724. 银行家算法之例银行家算法之例lP1请求资源：请求资源：P1发出请求向量发出请求向量Request1(1， 0， 2),系统按银行家算法进行检查系统按银行家算法进行检查：（

52、1）Request1(1，0，2)=Need1(1，2，2)（2）Request1(1，0，2)=Available1(3，3，2)（3）系统先假定可为）系统先假定可为P1分配资源，并修改分配资源，并修改Available、Allocation1和和Need1向量。向量。 （4）再利用安全性算法检查此时系统是否安全。如）再利用安全性算法检查此时系统是否安全。如下表。下表。2022-3-12阜阳师范学院计算机与信息学院73FalseFalseFalseFalseFalse4. 银行家算法之例银行家算法之例 由所进行的安全性检查得知，可以找到一个安全序由所进行的安全性检查得知，可以找到一个安全序列

53、列P1,P3,P4,P0,P2,因此，系统是安全的，可以立即因此，系统是安全的，可以立即将将P P1 1所申请的资源分配给它。所申请的资源分配给它。True10 5 73 0 26 0 07 5 5P2True7 5 50 1 07 4 37 4 5P0True7 4 50 0 24 3 17 4 3P4True 7 4 32 1 10 1 15 3 2P3True5 3 23 0 20 2 02 3 0P1FinishWork+AllocationA B CAllocationA B CNeedA B CWorkA B C 资源情况资源情况进程进程2022-3-12阜阳师范学院计算机与信息学

54、院744. 银行家算法之例银行家算法之例lP4请求资源：请求资源：P4发出请求向量发出请求向量Request4(3，3，0),系统系统按银行家算法进行检查：按银行家算法进行检查：（1）Request4(3，3，0)=Need4(4，3，1);（2）Request4(3，3，0)=Available(2，3，0),让让P4等待。等待。lP0请求资源：请求资源：P0发出请求向量发出请求向量Request0(0，2，0),系统系统按银行家算法进行检查：按银行家算法进行检查：（1）Request0(0，2，0)=Need0(7，4，3); （2）Request0(0，2，0)=Available(2，3，0)；（3）系统暂时先假定可为）系统暂时先假定可为P0分配资源，并修改有关数据，分配资源，并修改有关数据，如下表所示。如下表所示。2022-3-12阜阳师范学院计算机与信息学院754. 银行家算法之例银行家算法之例l进行