第3章处理机调度与死330锁

1、第三章处理机调度与死锁第三章处理机调度与死锁 3.1 处理机调度的层次和调度算法的目标处理机调度的层次和调度算法的目标 3.2作业与作业调度作业与作业调度 3.3进程调度进程调度 3.4实时调度实时调度 3.5死锁概述死锁概述 3.6预防死锁预防死锁3.7 避免死锁避免死锁3.8 死锁的检测与解除死锁的检测与解除3.1处理机调度的层次处理机调度的层次和调度算法的目标和调度算法的目标处理机调度的层次处理机调度的层次高级调度高级调度 中级调度中级调度 低级调度低级调度3.1处理机调度的层次处理机调度的层次和调度算法的目标和调度算法的目标高级调度（也称作业调度、长程调度）高级调度（也称作业调度、长程

2、调度）u功能功能n选择外存上处于后备队列中的一个或几个作业调入内选择外存上处于后备队列中的一个或几个作业调入内存，并为它们创建进程，分配必要的资源，然后再将存，并为它们创建进程，分配必要的资源，然后再将新创建的进程排入进程就绪队列，准备执行新创建的进程排入进程就绪队列，准备执行u使用系统使用系统n批处理系统批处理系统n分时系统和实时系统不需要分时系统和实时系统不需要u执行频率执行频率n分钟、小时或天分钟、小时或天3.1处理机调度的层次处理机调度的层次和调度算法的目标和调度算法的目标低级调度（也称进程调度、短程调度）低级调度（也称进程调度、短程调度）u功能功能n从进程就绪队列中选择一个进程，然后

3、由分派程序将从进程就绪队列中选择一个进程，然后由分派程序将处理机处理机CPU分配给该进程分配给该进程u使用系统使用系统n各种系统均需要各种系统均需要u执行频率执行频率n毫秒毫秒3.1处理机调度的层次处理机调度的层次和调度算法的目标和调度算法的目标中级调度（也称中程调度、内存调度）中级调度（也称中程调度、内存调度）u功能功能n负责进程在内存和外存对换区之间换进负责进程在内存和外存对换区之间换进/换出换出u是内存对换功能的一部分是内存对换功能的一部分u目的目的n提高内存利用率和系统吞吐量提高内存利用率和系统吞吐量u执行频率执行频率n介于作业调度和进程调度之间介于作业调度和进程调度之间3.1处理机调

4、度的层次处理机调度的层次和调度算法的目标和调度算法的目标处理机调度算法的目标处理机调度算法的目标共同目标共同目标u资源利用率资源利用率u公平性公平性u平衡性平衡性u策略强制执行策略强制执行3.1处理机调度的层次处理机调度的层次和调度算法的目标和调度算法的目标批处理系统的目标批处理系统的目标u平均周转时间短平均周转时间短n作业周转时间是指从作业被提交给系统开始，到作业作业周转时间是指从作业被提交给系统开始，到作业完成为止的这段时间间隔完成为止的这段时间间隔n包括包括作业在外存后备队列上等待作业调度的时间作业在外存后备队列上等待作业调度的时间进程在就绪队列上等待进程调度的时间进程在就绪队列上等待进

5、程调度的时间进程在进程在CPU上执行的时间上执行的时间进程等待进程等待I/O操作完成的时间操作完成的时间3.1处理机调度的层次处理机调度的层次和调度算法的目标和调度算法的目标n平均周转时间平均周转时间n平均带权周转时间平均带权周转时间u系统吞吐量高系统吞吐量高n指在单位时间内系统所完成的作业数指在单位时间内系统所完成的作业数u处理机利用率高处理机利用率高niiTnT11niiTTnW1s13.1处理机调度的层次处理机调度的层次和调度算法的目标和调度算法的目标分时系统的目标分时系统的目标u响应时间快响应时间快n从用户通过键盘提交一个请求开始，直到屏幕上显示从用户通过键盘提交一个请求开始，直到屏幕

6、上显示出结果为止的一段时间间隔出结果为止的一段时间间隔n包括包括从键盘输入的请求信息传送到处理机的时间从键盘输入的请求信息传送到处理机的时间处理机对请求信息进行处理的时间处理机对请求信息进行处理的时间将所形成的响应信息回送到终端显示器的时间将所形成的响应信息回送到终端显示器的时间u均衡性均衡性3.1处理机调度的层次处理机调度的层次和调度算法的目标和调度算法的目标实时系统的目标实时系统的目标u截止时间的保证截止时间的保证n指某任务必须开始执行的最迟时间，或必须完成的最指某任务必须开始执行的最迟时间，或必须完成的最迟时间迟时间u可预测性可预测性3.2作业与作业调度作业与作业调度 批处理系统中的作业

7、批处理系统中的作业作业和作业步作业和作业步u作业（作业（Job）n所谓作业就是用户一次请求计算机系统为它完成任务所谓作业就是用户一次请求计算机系统为它完成任务所进行的工作总和所进行的工作总和n作业程序数据作业说明书作业程序数据作业说明书n批处理系统中，以作业为基本单位从外存调入内存批处理系统中，以作业为基本单位从外存调入内存u作业步（作业步（Job Step）n一个作业是由若干作业步组成的一个作业是由若干作业步组成的n作业步就是处理作业的各个独立的子任务作业步就是处理作业的各个独立的子任务n系统可以创建若干进程完成各作业步的计算系统可以创建若干进程完成各作业步的计算 3.2作业与作业调度作业与

8、作业调度作业控制块作业控制块JCB（Job Control Block）u是作业在系统中存在的唯一标志是作业在系统中存在的唯一标志u包含的内容包含的内容n作业标识、用户名称、用户帐户作业标识、用户名称、用户帐户n作业类型（作业类型（CPU 繁忙型、繁忙型、I/O 繁忙型、批量型、终端繁忙型、批量型、终端型）、作业状态、调度信息（优先级、作业已运行时型）、作业状态、调度信息（优先级、作业已运行时间）间）n资源需求（预计运行时间、要求内存大小、要求资源需求（预计运行时间、要求内存大小、要求I/O设设备的类型和数量等）、资源使用情况备的类型和数量等）、资源使用情况n进入系统时间、开始处理时间、作业完

9、成时间、作业进入系统时间、开始处理时间、作业完成时间、作业退出时间退出时间3.2作业与作业调度作业与作业调度作业运行的三个阶段和三种状态作业运行的三个阶段和三种状态用户作业录入提交收容完成运行就绪阻塞等待I/OI/O完成进程调度作业调度执行作业调度后备后备运行运行运行运行收容收容完成完成完成完成用户作业录入提交收容完成运行就绪阻塞等待I/OI/O完成进程调度作业调度执行作业调度3.2作业与作业调度作业与作业调度作业调度的主要任务作业调度的主要任务根据根据JCB中的信息，检查系统能否满足用户作业中的信息，检查系统能否满足用户作业的资源需求，以及按照一定的调度算法，从外存的资源需求，以及按照一定的

10、调度算法，从外存的后备队列中选取某些作业调入内存，并为它们的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。然后再将新创建的创建进程、分配必要的资源。然后再将新创建的进程插入就绪队列，准备执行进程插入就绪队列，准备执行也称接纳调度也称接纳调度3.2作业与作业调度作业与作业调度作业调度时要决定作业调度时要决定u一次接纳多少个作业一次接纳多少个作业n取决于多道程序度和资源使用情况取决于多道程序度和资源使用情况u接纳哪些作业接纳哪些作业n取决于作业调度算法和资源使用情况取决于作业调度算法和资源使用情况3.2作业与作业调度作业与作业调度先来先服务（先来先服务（FCFSFirst Co

11、me First Served）调度算法调度算法后备作业队列按后备作业队列按FIFO排列，调度时选择处于队首排列，调度时选择处于队首的作业的作业优点：简单、易于实现优点：简单、易于实现 缺点缺点u有利于长作业，不利于短作业有利于长作业，不利于短作业3.2作业与作业调度作业与作业调度例例作业名作业名 到达时间到达时间 服务时间服务时间 A 0 4 B 1 5 C 2 2 D 3 4A0 40 4开始时间开始时间 完成时间完成时间 周转时间周转时间 带权周转时间带权周转时间 0 4 4 1 4 9 8 1.6 9 11 9 4.5 11 15 12 3平均平均 8.25 2.525 8.25 2.

12、525D15 15 B9 9C11113.2作业与作业调度作业与作业调度短作业优先（短作业优先（SJF-Shortest Job First）调度算法）调度算法从后备作业队列中选择估计运行时间最短的作业从后备作业队列中选择估计运行时间最短的作业优点：调度性能较好优点：调度性能较好缺点：缺点：1）不利于长作业）不利于长作业 2）不考虑作业的紧迫程度）不考虑作业的紧迫程度 3）估计运行时间很难准确获得）估计运行时间很难准确获得3.2作业与作业调度作业与作业调度例例作业名作业名 到达时间到达时间 服务时间服务时间 A 0 4 B 1 5 C 2 2 D 3 4开始时间开始时间 完成时间完成时间 周转

13、时间周转时间 带权周转时间带权周转时间 0 4 4 1 10 15 14 2.8 4 6 4 2 6 10 7 1.75平均平均 7.25 1.8875 7.25 1.8875A0 40 4D10 10 B1515C6 63.2作业与作业调度作业与作业调度优先级（优先级（PSA-Priority Scheduling Algorithm）调）调度算法度算法选择优先级最高的后备作业选择优先级最高的后备作业提交作业时说明作业优先级提交作业时说明作业优先级优先级一般利用某一范围内的一个整数来表示优先级一般利用某一范围内的一个整数来表示3.2作业与作业调度作业与作业调度例（数大优先级高）例（数大优先级

14、高）作业名作业名 到达时间到达时间 服务时间服务时间 优先级优先级 A 0 10 3 B 0 1 5 C 0 5 2 D 5 3 4B A D C 0 1 11 14 19 3.2作业与作业调度作业与作业调度高响应比优先调度算法高响应比优先调度算法选择具有最高响应比的后备作业选择具有最高响应比的后备作业响应比响应比优点：既照顾了作业到来的先后，又考虑了要求服优点：既照顾了作业到来的先后，又考虑了要求服务时间的长短，是务时间的长短，是FCFS和和SJF的很好的折衷的很好的折衷缺点：算法较为复杂；每次调度时，均要重新计算缺点：算法较为复杂；每次调度时，均要重新计算响应比响应比要求服务时间要求服务时

15、间等待时间要求服务时间响应时间PR3.2作业与作业调度作业与作业调度例例作业名作业名J1J2J3到达时间到达时间8:008:309:30服务时间服务时间2小时小时1小时小时0.25小时小时 三个作业在一台处理机三个作业在一台处理机上单道运行，上单道运行，9:40 进行作业进行作业调度，问三个作业的执行次调度，问三个作业的执行次序？序？9:40 调度时：调度时：J1：1+100/120 = 1+5/6J2：1+70/60 = 1+7/6J3：1+10/15 = 1+4/6选择选择J2作业调度作业调度10:40（J2完成）调度时：完成）调度时：J1：1+160/120 = 1+4/3J3：1+70

16、/15 = 1+14/3选择选择J3作业调度作业调度执行次序：执行次序：J2、J3、J13.3进程进程调度调度进程调度的任务、机制和方式进程调度的任务、机制和方式进程调度的功能进程调度的功能u从就绪队列中选择一个进程，然后，由分派程序将处理从就绪队列中选择一个进程，然后，由分派程序将处理机机CPU分配给该进程分配给该进程进程调度时只决定进程调度时只决定u选择哪个就绪进程：取决于进程调度算法选择哪个就绪进程：取决于进程调度算法要解决的问题要解决的问题When：何时分配：何时分配CPU 进程调度的时机进程调度的时机What：按什么原则分配：按什么原则分配CPU 进程调度算法进程调度算法How： 如

17、何分配如何分配CPU CPU调度过程（进程的上下文切换）调度过程（进程的上下文切换）3.3进程进程调度调度进程调度的任务进程调度的任务u保存处理机的现场信息保存处理机的现场信息u按某种进程调度算法选取一个就绪进程按某种进程调度算法选取一个就绪进程u把处理器分配给该进程把处理器分配给该进程进程调度机制进程调度机制u排队器排队器u分派器分派器u上下文切换器上下文切换器3.3进程进程调度调度进程调度的时机（进程调度的时机（When）1. 当进程从执行态转换到阻塞态时（例如提出当进程从执行态转换到阻塞态时（例如提出I/O请求、等请求、等待子进程结束、待子进程结束、wait操作等）操作等）2. 分时系统

18、中时间片到分时系统中时间片到3. 当有一个优先级更高的进程就绪（例如新创建一个进程，当有一个优先级更高的进程就绪（例如新创建一个进程，一个进程由等待变成就绪）一个进程由等待变成就绪）4. 当一个进程运行完毕，或由于某种错误而终止运行当一个进程运行完毕，或由于某种错误而终止运行3.3进程进程调度调度进程调度方式进程调度方式u非抢占方式（非抢占方式（Nonpreemptive Mode）n一旦把处理机分配给某个进程，便让该进程一直执行，一旦把处理机分配给某个进程，便让该进程一直执行，直至该进程完成或发生某事件而阻塞时，才把处理机直至该进程完成或发生某事件而阻塞时，才把处理机分配给其它进程分配给其它

19、进程u抢占方式（抢占方式（Preemptive Mode）n允许调度程序根据某种原则，去停止某个正在执行的允许调度程序根据某种原则，去停止某个正在执行的进程，将已分配给该进程的处理机，重新分配给另一进程，将已分配给该进程的处理机，重新分配给另一进程进程 时间片时间片原则原则 抢占原则抢占原则 优先权原则优先权原则 短进程优先原则短进程优先原则仅在情况仅在情况 1 1和和4 4 下，才进行调度下，才进行调度在情况在情况 1 1、2 2、3 3、4 4 时均可调度时均可调度3.3进程进程调度调度 先来先服务调度算法先来先服务调度算法（FCFSFirst Come First Served）非抢占方

20、式非抢占方式就绪队列按就绪队列按FIFO排列，调度时选择队首进程排列，调度时选择队首进程优点：简单、易于实现优点：简单、易于实现 缺点：缺点：u有利于长进程，不利于短进程有利于长进程，不利于短进程u有利于有利于CPU繁忙型进程，不利于繁忙型进程，不利于I/O繁忙型进程繁忙型进程3.3进程进程调度调度短进程优先（短进程优先（SPF Shortest Process First）调度）调度算法算法非抢占式或抢占式均可非抢占式或抢占式均可从就绪队列中选择估计运行时间最短的进程从就绪队列中选择估计运行时间最短的进程优点：调度性能较好优点：调度性能较好缺点：缺点：1）不利于长进程）不利于长进程 2）不考

21、虑进程的紧迫程度）不考虑进程的紧迫程度 3）估计运行时间很难准确获得）估计运行时间很难准确获得3.3进程进程调度调度例例进程名进程名 到达时间到达时间 服务时间服务时间 A 0 3 B 0 5 C 0 3 D 0 4 E 8 3抢占方式抢占方式1 1、基于最短服务时间抢占、基于最短服务时间抢占：A C D E D B0 3 6 8 11 13 18 0 3 6 8 11 13 18 A C D E B0 3 6 10 13 18 0 3 6 10 13 18 非抢占方式非抢占方式2 2、基于最短剩余服务时间抢占、基于最短剩余服务时间抢占：A C D E B0 3 6 10 13 18 0 3

22、6 10 13 18 3.3进程进程调度调度时间片轮转调度算法（时间片轮转调度算法（RRRound Robin）抢占方式抢占方式主要为分时系统设计主要为分时系统设计就绪队列按就绪队列按FIFO排列，调度时选择队首进程。但排列，调度时选择队首进程。但该进程占用该进程占用CPU至多执行一个时间片，便放弃至多执行一个时间片，便放弃CPU进程切换时机进程切换时机时间片大小的确定时间片大小的确定3.3进程进程调度调度例：时间片例：时间片=2进程名进程名 到达时间到达时间 服务时间服务时间 A 0 4 B 0 5 C 0 2 D 0 4开始时间开始时间 完成时间完成时间 周转时间周转时间 带权周转时间带权

23、周转时间 0 10 10 2.5 2 15 15 3 4 6 6 3 6 14 14 3.5A B C D A B D B0 2 4 6 8 10 12 14 15 0 2 4 6 8 10 12 14 15 3.3进程进程调度调度优先级调度算法优先级调度算法非抢占式或抢占式均可非抢占式或抢占式均可选择具有最高优先级的就绪进程选择具有最高优先级的就绪进程优先级（优先权、优先数）优先级（优先权、优先数）u利用某一范围内的一个整数来表示利用某一范围内的一个整数来表示u不同系统的具体用法各异不同系统的具体用法各异u确定进程优先权的依据确定进程优先权的依据n进程类型进程类型n进程对资源的需求进程对资源

24、的需求n用户要求用户要求3.3进程进程调度调度优先级的类型优先级的类型u静态优先级静态优先级n创建进程时确定，在进程的整个运行期间保持不变创建进程时确定，在进程的整个运行期间保持不变n简单易行，系统开销小，但不够精确简单易行，系统开销小，但不够精确n仅在要求不高的系统中才使用仅在要求不高的系统中才使用u动态优先级动态优先级n创建进程时确定初值，运行期间基于某种原则动态改创建进程时确定初值，运行期间基于某种原则动态改变变n灵活，调度性能好，但系统开销大灵活，调度性能好，但系统开销大3.3进程进程调度调度例例进程名进程名 到达时间到达时间 服务时间服务时间 优先级优先级 A 0 10 3 B 0

25、1 5 C 0 5 2 D 5 3 4B A D C 0 1 11 14 19 非抢占方式非抢占方式B A D A C 0 1 5 8 14 19 抢占方式抢占方式3.3进程调度进程调度多队列调度算法多队列调度算法按性质和类型将就绪队列分为若干子队列，每个就按性质和类型将就绪队列分为若干子队列，每个就绪进程固定地分属于一个子队列，每个队列有自己绪进程固定地分属于一个子队列，每个队列有自己的调度算法的调度算法各队列间的调度方式或采用固定优先权抢占调度，各队列间的调度方式或采用固定优先权抢占调度，或为各队列分配一定比例的或为各队列分配一定比例的CPU时间时间3.3进程进程调度调度多级反馈队列调度算

26、法多级反馈队列调度算法抢占方式抢占方式就绪队列就绪队列1（FCFS）s1CPU结束或结束或阻塞阻塞就绪队列就绪队列2（FCFS）s2CPU就绪队列就绪队列n（RR）snCPU提交提交高高优优先先级级低低（时间片（时间片s1s2 使用使用-释放释放 n 命令：命令：request/release，open/close，wait/signalu可消耗性资源（临时性资源）可消耗性资源（临时性资源）n在进程运行期间，由进程动态创建和消耗的资源在进程运行期间，由进程动态创建和消耗的资源3.5死锁概述死锁概述可抢占性资源和不可抢占性资源可抢占性资源和不可抢占性资源u可抢占性资源可抢占性资源n可从拥有它的进

27、程中抢占而不会产生任何副作用可从拥有它的进程中抢占而不会产生任何副作用nCPU、主存、主存u不可抢占性资源不可抢占性资源n从拥有它的进程中抢占会产生错误从拥有它的进程中抢占会产生错误n打印机等打印机等3.5死锁概述死锁概述产生死锁的原因产生死锁的原因竞争资源竞争资源u当系统中供多个进程共享的资源如打印机、公用队列等，当系统中供多个进程共享的资源如打印机、公用队列等，其数目不足以满足诸进程的需要时，会引起诸进程对资其数目不足以满足诸进程的需要时，会引起诸进程对资源的竞争而产生死锁源的竞争而产生死锁进程间推进顺序不当进程间推进顺序不当u进程在运行过程中，请求和释放资源的顺序不当，也同进程在运行过程

28、中，请求和释放资源的顺序不当，也同样会导致产生进程死锁样会导致产生进程死锁 3.5死锁概述死锁概述竞争不可抢占性资源可能引发死锁竞争不可抢占性资源可能引发死锁u例：进程例：进程p1和和p2，准备写文件，准备写文件f1和和f2 进程进程p1 进程进程p2 1. open(f1, w); 3. open(f2, w); 2. open(f2, w); 4. open(f1, w); 进程进程p1和和 进程进程p2交替占用交替占用CPU执行时，顺序为执行时，顺序为1234或或3412 不会出错。但为不会出错。但为 1324 时，会死锁。时，会死锁。3.5死锁概述死锁概述竞争临时性资源可能引发死锁竞争

29、临时性资源可能引发死锁u例，进程例，进程P1、P2、P3互发消息互发消息m1、m2和和m3 P1： receive(p2,m1)；send(p3,m3)； P2： receive(p3,m2)；send(p1,m1)； P3： receive(p1,m3)；send(p2,m2)； S2P1S3P3S1P2m3m2m13.5死锁概述死锁概述进程推进顺序不当引发死锁进程推进顺序不当引发死锁u例例p1 req(r1) p1 req(r2) p1 rel(r1) p1 rel(r2)p2 rel(r1)p2 rel(r2)p2 req(r1)p2 req(r2)4 41 12 23 3进程进程p1和

30、进和进程程p2交替占交替占用用CPU执行执行时，顺序为时，顺序为1或或2或或3时，时，不会出错。不会出错。但为但为 4 时，时，会死锁。会死锁。3.5死锁概述死锁概述 死锁的定义死锁的定义如果一组进程中的每一个进程都在等待仅由该组进如果一组进程中的每一个进程都在等待仅由该组进程中的其它一个进程才能引发的事件，那么该组进程中的其它一个进程才能引发的事件，那么该组进程是死锁（程是死锁（Deadlock）的）的3.5死锁概述死锁概述产生死锁的必要条件产生死锁的必要条件互斥条件互斥条件u每个资源要么已分配给了一个进程，要么空闲每个资源要么已分配给了一个进程，要么空闲请求和保持条件请求和保持条件u已经得

31、到资源的进程可以申请新的资源，申请失败时变为阻塞状态，已经得到资源的进程可以申请新的资源，申请失败时变为阻塞状态，此时它仍然保持着原有资源不放此时它仍然保持着原有资源不放不可抢占条件不可抢占条件u已经分配给一个进程的资源不能被抢占，只能由占有它的进程主动已经分配给一个进程的资源不能被抢占，只能由占有它的进程主动释放释放循环等待条件循环等待条件u系统一定有两个或两个以上的进程组成的一条环路，该环路中的每系统一定有两个或两个以上的进程组成的一条环路，该环路中的每个进程都在等待着相邻进程正占用着的资源个进程都在等待着相邻进程正占用着的资源3.5死锁概述死锁概述处理死锁的四种策略处理死锁的四种策略预防

32、死锁预防死锁u通过破除死锁的四个必要条件之一，通过破除死锁的四个必要条件之一，来防止死锁产生来防止死锁产生避免死锁避免死锁u仔细地对资源进行动态分配，以避仔细地对资源进行动态分配，以避免死锁发生免死锁发生检测与解除死锁检测与解除死锁u检测系统中是否出现死锁，若出现检测系统中是否出现死锁，若出现则解除掉则解除掉忽略该问题忽略该问题允许系统发生允许系统发生死锁，然后解除死锁，然后解除假装死锁假装死锁永不发生永不发生保证系统永远保证系统永远不会发生死锁不会发生死锁3.5死锁概述死锁概述鸵鸟算法鸵鸟算法思想：不采取任何措施，对死锁视而不见思想：不采取任何措施，对死锁视而不见实例：实例：UNIX系统（还

33、有其它许多系统）系统（还有其它许多系统）由于不预防、避免死锁，故系统中可能发生死锁。由于不预防、避免死锁，故系统中可能发生死锁。而发生时又无法知道（因不检测），造成系统崩溃，而发生时又无法知道（因不检测），造成系统崩溃，需要重启需要重启之所以被某些系统采用，是因为死锁不常发生之所以被某些系统采用，是因为死锁不常发生3.6预防死锁预防死锁预防死锁预防死锁如果能够保证四个必要条件中至少有一个不成立，如果能够保证四个必要条件中至少有一个不成立，那么死锁将不会产生（那么死锁将不会产生（Havender，1968）但其中的但其中的“互斥互斥”条件不能破除条件不能破除3.6预防死锁预防死锁破坏破坏“请求和

34、保持请求和保持”条件条件u第一种协议第一种协议n规定进程在执行前要一次性地申请运行所需全部资源。规定进程在执行前要一次性地申请运行所需全部资源。只有资源全部到手，进程方可运行只有资源全部到手，进程方可运行n优点：简单、易于实现优点：简单、易于实现n 缺点：资源利用率低；进程运行被延迟缺点：资源利用率低；进程运行被延迟u第二种协议第二种协议n允许进程只获得运行初期所需资源后，即可运行。进允许进程只获得运行初期所需资源后，即可运行。进程运行中释放已占用资源后，再申请新的所需资源程运行中释放已占用资源后，再申请新的所需资源3.6预防死锁预防死锁破坏破坏“不可抢占不可抢占”条件条件u方法方法n保持资源

35、的进程申请新资源失败时，在转为阻塞状态保持资源的进程申请新资源失败时，在转为阻塞状态之前，必须释放其占用的全部资源。而该进程自身则之前，必须释放其占用的全部资源。而该进程自身则必须等到重新获得原有资源及新资源后，才能重新运必须等到重新获得原有资源及新资源后，才能重新运行行u缺点缺点n实现复杂，代价大实现复杂，代价大3.6预防死锁预防死锁破坏破坏“循环等待循环等待”条件条件u方法方法n将系统中所有资源赋予一个全局编号，进程申请资源将系统中所有资源赋予一个全局编号，进程申请资源时，必须按编号递增顺序进行时，必须按编号递增顺序进行u缺点缺点n找不出一种人人满意的编号顺序找不出一种人人满意的编号顺序n

36、仍存在资源浪费仍存在资源浪费n用户编程受到限制用户编程受到限制3.7避免死锁避免死锁思路思路允许进程动态的申请资源允许进程动态的申请资源将系统状态分为将系统状态分为 u安全状态：不会发生死锁安全状态：不会发生死锁u不安全状态：可能发生死锁不安全状态：可能发生死锁避免系统进入不安全状态！避免系统进入不安全状态！做法做法u每次进行资源分配时，首先检测一下每次进行资源分配时，首先检测一下资源分配后资源分配后系统处系统处于何种状态，若处于于何种状态，若处于安全安全状态，则正式实施本次状态，则正式实施本次分配分配；若处于若处于不安全不安全状态，则状态，则不予分配不予分配，申请资源的进程阻塞，申请资源的进

37、程阻塞3.7避免死锁避免死锁系统的安全状态系统的安全状态安全状态安全状态u指系统能按某种进程顺序（指系统能按某种进程顺序（P1，P2，Pn），来为每），来为每个进程个进程 Pi 分配其所需资源，直至满足每个进程对资源的分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成最大需求，使每个进程都可顺利地完成u此时称此时称P1，P2，Pn序列为安全序列序列为安全序列如果系统无法找到这样一个安全序列，则称系统处如果系统无法找到这样一个安全序列，则称系统处于不安全状态于不安全状态3.7避免死锁避免死锁u例，系统有三个进程例，系统有三个进程P1、P2和和P3 ，共用，共用12台磁带机

38、。在台磁带机。在T0和和T1时刻，系统的资源分配情况分别如下表时刻，系统的资源分配情况分别如下表a和和b。进程进程 最大需求最大需求 已分配已分配 可用可用 P1 10 5 3 P2 4 2 P3 9 2进程进程 最大需求最大需求 已分配已分配 可用可用 P1 10 5 2 P2 4 2 P3 9 3a ab b3.7避免死锁避免死锁结果：结果：T0时刻系统处于安全状态。（安全序列时刻系统处于安全状态。（安全序列）P1P2 P3可用可用 5(5)2(2)2(7)35(5)4(0)2(7)15(5) 2(7)510(0) 2(7)0 2(7)10 9(0)3 12结果：结果：T1时刻系统处于不安

39、全状态。时刻系统处于不安全状态。P1P2 P3可用可用 5(5)2(2)3(6)25(5)4(0)3(6)05(5) 3(6)43.7避免死锁避免死锁利用银行家算法避免死锁利用银行家算法避免死锁数据结构数据结构n个进程个进程 (P1, , Pn)，m类资源类资源(R1, , Rm)u可利用资源向量可利用资源向量Available（m）nAvailablej表示表示 Rj 类资源的可用数目。类资源的可用数目。u最大需求矩阵最大需求矩阵Max（nm）nMaxi, j表示进程表示进程 Pi 对对 Rj 类资源的最大需求量。类资源的最大需求量。u分配矩阵分配矩阵Allocation（nm）nAlloc

40、ation i, j表示已分配给进程表示已分配给进程 Pi 的的 Rj 类资源的数类资源的数目。目。u需求矩阵需求矩阵Need（nm）nNeed i, j表示进程表示进程 Pi 对对 Rj 类资源的剩余需求量。类资源的剩余需求量。uRequesti ：进程：进程 Pi 的请求向量的请求向量3.7避免死锁避免死锁银行家算法：进程银行家算法：进程 Pi 发出资源请求发出资源请求 RequestiRequesti Needi ? 执行安全性算法，检查分配后的系统状态执行安全性算法，检查分配后的系统状态正式分配正式分配安全状态安全状态Requesti Available ?是是 试分配：试分配： Av

41、ailable:= Available Requesti Allocationi:= Allocationi + RequestiNeedi:= Needi Requesti是是将试分配作废；将试分配作废；恢复原资源分配状态；恢复原资源分配状态；进程进程Pi阻塞。阻塞。不安全不安全状态状态错误错误否否否否进程进程Pi 阻塞阻塞3.7避免死锁避免死锁安全性算法安全性算法Work:=Available;Finish i :=false ( i=1,2,n);找一满足下列条件的进程：找一满足下列条件的进程：Finish i =false 且且 Needi Work Work:=Work+Alloca

42、tioni ; Finish i :=true;找到找到 所有进程的所有进程的Finish i =true？找不到找不到是是系统系统状态状态安全安全不是不是系统系统状态状态不安全不安全3.7避免死锁避免死锁例：系统中有五个进程例：系统中有五个进程P0 , P1 , P2 , P3 , P4和三类和三类资源资源A , B , C，每类资源的数量分别为，每类资源的数量分别为10、5、7，在在T0时刻的资源分配情况如下表。问：时刻的资源分配情况如下表。问：P1发出请发出请求向量求向量Request1 (1 ,0 ,2)，能否分配？，能否分配？Process Max Allocation Need A

43、vailable A B C A B C A B C 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 3.7避免死锁避免死锁结论：结论：因分配后的因分配后的系统状态安全，故可以系统状态安全，故可以 立即将立即将P1所申请的资源分配给它。所申请的资源分配给它。 Process Max Allocation Need Available P0 7 5 3 0 1 0 7 4 3 3 3 2 P1 3 2 2 2 0

44、 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 Request1 (1 ,0 ,2)试分配试分配（结果见（结果见红字红字）2 3 00 2 03 0 2安全性算法：安全性算法：Work= 2 3 0 Finish = falsefalsefalsefalsefalsetrue5 3 27 4 3true7 4 5true10 4 7true10 5 7true 3.8死锁的检测与解除死锁的检测与解除 死锁的检测死锁的检测资源分配图资源分配图RAG（Resource Allocation Graph） RAG=(N, E)，其中，其中:结点集结点集N=P R 进程结点子集进程结点子集P=p1,p2,pn，用，用 表示表示 资源结点子集资源结点子集R=r1,r2,rm，用，用 表示，