第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功能功

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

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

5、间作业在外存后备队列上等待作业调度的时间 进程在就绪队列上等待进程调度的时间进程在就绪队列上等待进程调度的时间 进程在进程在CPU上执行的时间上执行的时间 进程等待进程等待I/O操作完成的时间操作完成的时间 3.1处理机调度的层次处理机调度的层次和调度算法的目标和调度算法的目标 n平均周转时间平均周转时间 n平均带权周转时间平均带权周转时间 u系统吞吐量高系统吞吐量高 n指在单位时间内系统所完成的作业数指在单位时间内系统所完成的作业数 u处理机利用率高处理机利用率高 n i i T n T 1 1 n i i T T n W 1 s 1 3.1处理机调度的层次处理机调度的层次和调度算法的目标和

6、调度算法的目标 分时系统的目标分时系统的目标 u响应时间快响应时间快 n从用户通过键盘提交一个请求开始，直到屏幕上显示从用户通过键盘提交一个请求开始，直到屏幕上显示 出结果为止的一段时间间隔出结果为止的一段时间间隔 n包括包括 从键盘输入的请求信息传送到处理机的时间从键盘输入的请求信息传送到处理机的时间 处理机对请求信息进行处理的时间处理机对请求信息进行处理的时间 将所形成的响应信息回送到终端显示器的时间将所形成的响应信息回送到终端显示器的时间 u均衡性均衡性 3.1处理机调度的层次处理机调度的层次和调度算法的目标和调度算法的目标 实时系统的目标实时系统的目标 u截止时间的保证截止时间的保证

7、n指某任务必须开始执行的最迟时间，或必须完成的最指某任务必须开始执行的最迟时间，或必须完成的最 迟时间迟时间 u可预测性可预测性 3.2作业与作业调度作业与作业调度 批处理系统中的作业批处理系统中的作业 作业和作业步作业和作业步 u作业（作业（Job） n所谓作业就是用户一次请求计算机系统为它完成任务所谓作业就是用户一次请求计算机系统为它完成任务 所进行的工作总和所进行的工作总和 n作业程序数据作业说明书作业程序数据作业说明书 n批处理系统中，以作业为基本单位从外存调入内存批处理系统中，以作业为基本单位从外存调入内存 u作业步（作业步（Job Step） n一个作业是由若干作业步组成的一个作业

8、是由若干作业步组成的 n作业步就是处理作业的各个独立的子任务作业步就是处理作业的各个独立的子任务 n系统可以创建若干进程完成各作业步的计算系统可以创建若干进程完成各作业步的计算 3.2作业与作业调度作业与作业调度 作业控制块作业控制块JCB（Job Control Block） u是作业在系统中存在的唯一标志是作业在系统中存在的唯一标志 u包含的内容包含的内容 n作业标识、用户名称、用户帐户作业标识、用户名称、用户帐户 n作业类型（作业类型（CPU 繁忙型、繁忙型、I/O 繁忙型、批量型、终端繁忙型、批量型、终端 型）、作业状态、调度信息（优先级、作业已运行时型）、作业状态、调度信息（优先级、

9、作业已运行时 间）间） n资源需求（预计运行时间、要求内存大小、要求资源需求（预计运行时间、要求内存大小、要求I/O设设 备的类型和数量等）、资源使用情况备的类型和数量等）、资源使用情况 n进入系统时间、开始处理时间、作业完成时间、作业进入系统时间、开始处理时间、作业完成时间、作业 退出时间退出时间 3.2作业与作业调度作业与作业调度 作业运行的三个阶段和三种状态作业运行的三个阶段和三种状态 用户 作业录入 提交收容 完成运行 就绪阻塞 等待 I/O I/O 完成 进程 调度 作业调度 执行 作业调度 后备后备 运行运行 运行运行收容收容 完成完成 完成完成 用户 作业录入 提交收容 完成运行

10、 就绪阻塞 等待 I/O I/O 完成 进程 调度 作业调度 执行 作业调度 3.2作业与作业调度作业与作业调度 作业调度的主要任务作业调度的主要任务 根据根据JCB中的信息，检查系统能否满足用户作业中的信息，检查系统能否满足用户作业 的资源需求，以及按照一定的调度算法，从外存的资源需求，以及按照一定的调度算法，从外存 的后备队列中选取某些作业调入内存，并为它们的后备队列中选取某些作业调入内存，并为它们 创建进程、分配必要的资源。然后再将新创建的创建进程、分配必要的资源。然后再将新创建的 进程插入就绪队列，准备执行进程插入就绪队列，准备执行 也称接纳调度也称接纳调度 3.2作业与作业调度作业与

11、作业调度 作业调度时要决定作业调度时要决定 u一次接纳多少个作业一次接纳多少个作业 n取决于多道程序度和资源使用情况取决于多道程序度和资源使用情况 u接纳哪些作业接纳哪些作业 n取决于作业调度算法和资源使用情况取决于作业调度算法和资源使用情况 3.2作业与作业调度作业与作业调度 先来先服务（先来先服务（FCFSFirst Come First Served） 调度算法调度算法 后备作业队列按后备作业队列按FIFO排列，调度时选择处于队首排列，调度时选择处于队首 的作业的作业 优点：简单、易于实现优点：简单、易于实现 缺点缺点 u有利于长作业，不利于短作业有利于长作业，不利于短作业 3.2作业与

12、作业调度作业与作业调度 例例 作业名作业名 到达时间到达时间 服务时间服务时间 A 0 4 B 1 5 C 2 2 D 3 4 A 0 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.525 D 15 15 B 9 9 C 1111 3.2作业与作业调度作业与作业调度 短作业优先（短作业优先（SJF-Shortest Job First）调度算法）调度算法 从后备作业队列中选择估计运行时间最短的作业从后备作业队列中选择估计运行时

13、间最短的作业 优点：调度性能较好优点：调度性能较好 缺点：缺点：1）不利于长作业）不利于长作业 2）不考虑作业的紧迫程度）不考虑作业的紧迫程度 3）估计运行时间很难准确获得）估计运行时间很难准确获得 3.2作业与作业调度作业与作业调度 例例 作业名作业名 到达时间到达时间 服务时间服务时间 A 0 4 B 1 5 C 2 2 D 3 4 开始时间开始时间 完成时间完成时间 周转时间周转时间 带权周转时间带权周转时间 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.8875 A 0 40 4 D 10 10 B 1

14、515 C 6 6 3.2作业与作业调度作业与作业调度 优先级（优先级（PSA-Priority Scheduling Algorithm）调）调 度算法度算法 选择优先级最高的后备作业选择优先级最高的后备作业 提交作业时说明作业优先级提交作业时说明作业优先级 优先级一般利用某一范围内的一个整数来表示优先级一般利用某一范围内的一个整数来表示 3.2作业与作业调度作业与作业调度 例（数大优先级高）例（数大优先级高） 作业名作业名 到达时间到达时间 服务时间服务时间 优先级优先级 A 0 10 3 B 0 1 5 C 0 5 2 D 5 3 4 B A D C 0 1 11 14 19 3.2作业

15、与作业调度作业与作业调度 高响应比优先调度算法高响应比优先调度算法 选择具有最高响应比的后备作业选择具有最高响应比的后备作业 响应比响应比 优点：既照顾了作业到来的先后，又考虑了要求服优点：既照顾了作业到来的先后，又考虑了要求服 务时间的长短，是务时间的长短，是FCFS和和SJF的很好的折衷的很好的折衷 缺点：算法较为复杂；每次调度时，均要重新计算缺点：算法较为复杂；每次调度时，均要重新计算 响应比响应比 要求服务时间 要求服务时间等待时间 要求服务时间 响应时间 P R 3.2作业与作业调度作业与作业调度 例例 作业名作业名 J1 J2 J3 到达时间到达时间 8:00 8:30 9:30

16、服务时间服务时间 2小时小时 1小时小时 0.25小时小时 三个作业在一台处理机三个作业在一台处理机 上单道运行，上单道运行，9:40 进行作业进行作业 调度，问三个作业的执行次调度，问三个作业的执行次 序？序？ 9:40 调度时：调度时： J1：1+100/120 = 1+5/6 J2：1+70/60 = 1+7/6 J3：1+10/15 = 1+4/6 选择选择J2作业调度作业调度 10:40（J2完成）调度时：完成）调度时： J1：1+160/120 = 1+4/3 J3：1+70/15 = 1+14/3 选择选择J3作业调度作业调度 执行次序：执行次序：J2、J3、J1 3.3进程进程

17、调度调度 进程调度的任务、机制和方式进程调度的任务、机制和方式 进程调度的功能进程调度的功能 u从就绪队列中选择一个进程，然后，由分派程序将处理从就绪队列中选择一个进程，然后，由分派程序将处理 机机CPU分配给该进程分配给该进程 进程调度时只决定进程调度时只决定 u选择哪个就绪进程：取决于进程调度算法选择哪个就绪进程：取决于进程调度算法 要解决的问题要解决的问题 When：何时分配：何时分配CPU 进程调度的时机进程调度的时机 What：按什么原则分配：按什么原则分配CPU 进程调度算法进程调度算法 How： 如何分配如何分配CPU CPU调度过程（进程的上下文切换）调度过程（进程的上下文切换

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

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

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

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

22、不考虑进程的紧迫程度）不考虑进程的紧迫程度 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 B 0 3 6 8 11 13 18 0 3 6 8 11 13 18 A C D E B 0 3 6 10 13 18 0 3 6 10 13 18 非抢占方式非抢占方式 2 2、基于最短剩余服务时间抢占、基于最短剩余服务时间抢占： A C D E B 0 3 6

23、10 13 18 0 3 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 开始时间开始时间 完

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

25、据确定进程优先权的依据 n进程类型进程类型 n进程对资源的需求进程对资源的需求 n用户要求用户要求 3.3进程进程调度调度 优先级的类型优先级的类型 u静态优先级静态优先级 n创建进程时确定，在进程的整个运行期间保持不变创建进程时确定，在进程的整个运行期间保持不变 n简单易行，系统开销小，但不够精确简单易行，系统开销小，但不够精确 n仅在要求不高的系统中才使用仅在要求不高的系统中才使用 u动态优先级动态优先级 n创建进程时确定初值，运行期间基于某种原则动态改创建进程时确定初值，运行期间基于某种原则动态改 变变 n灵活，调度性能好，但系统开销大灵活，调度性能好，但系统开销大 3.3进程进程调度调

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

27、先权抢占调度， 或为各队列分配一定比例的或为各队列分配一定比例的CPU时间时间 3.3进程进程调度调度 多级反馈队列调度算法多级反馈队列调度算法 抢占方式抢占方式 就绪队列就绪队列1（FCFS） s1 CPU 结束或结束或 阻塞阻塞 就绪队列就绪队列2（FCFS） s2 CPU 就绪队列就绪队列n（RR） sn CPU 提交提交 高高 优优 先先 级级 低低 （时间片（时间片s1s2 使用使用-释放释放 n 命令：命令：request/release，open/close，wait/signal u可消耗性资源（临时性资源）可消耗性资源（临时性资源） n在进程运行期间，由进程动态创建和消耗的资

28、源在进程运行期间，由进程动态创建和消耗的资源 3.5死锁概述死锁概述 可抢占性资源和不可抢占性资源可抢占性资源和不可抢占性资源 u可抢占性资源可抢占性资源 n可从拥有它的进程中抢占而不会产生任何副作用可从拥有它的进程中抢占而不会产生任何副作用 nCPU、主存、主存 u不可抢占性资源不可抢占性资源 n从拥有它的进程中抢占会产生错误从拥有它的进程中抢占会产生错误 n打印机等打印机等 3.5死锁概述死锁概述 产生死锁的原因产生死锁的原因 竞争资源竞争资源 u当系统中供多个进程共享的资源如打印机、公用队列等，当系统中供多个进程共享的资源如打印机、公用队列等， 其数目不足以满足诸进程的需要时，会引起诸进

29、程对资其数目不足以满足诸进程的需要时，会引起诸进程对资 源的竞争而产生死锁源的竞争而产生死锁 进程间推进顺序不当进程间推进顺序不当 u进程在运行过程中，请求和释放资源的顺序不当，也同进程在运行过程中，请求和释放资源的顺序不当，也同 样会导致产生进程死锁样会导致产生进程死锁 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和和

30、 进程进程p2交替占用交替占用CPU执行时，顺序为执行时，顺序为1234 或或3412 不会出错。但为不会出错。但为 1324 时，会死锁。时，会死锁。 3.5死锁概述死锁概述 竞争临时性资源可能引发死锁竞争临时性资源可能引发死锁 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)； S 2 P 1 S 3 P 3 S 1 P 2 m3 m2 m1 3.5死锁概述死锁概述 进程推进顺序不当

31、引发死锁进程推进顺序不当引发死锁 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 4 1 1 2 2 3 3 进程进程p1和进和进 程程p2交替占交替占 用用CPU执行执行 时，顺序为时，顺序为 1或或2或或3时，时， 不会出错。不会出错。 但为但为 4 时，时， 会死锁。会死锁。 3.5死锁概述死锁概述 死锁的定义死锁的定义 如果一组进程中的每一个进程都在等待仅由该组进如果一组进程中的每一个进程都在等待仅由该组进 程中的其它一个进程才能引发的事件，那么该

32、组进程中的其它一个进程才能引发的事件，那么该组进 程是死锁（程是死锁（Deadlock）的）的 3.5死锁概述死锁概述 产生死锁的必要条件产生死锁的必要条件 互斥条件互斥条件 u每个资源要么已分配给了一个进程，要么空闲每个资源要么已分配给了一个进程，要么空闲 请求和保持条件请求和保持条件 u已经得到资源的进程可以申请新的资源，申请失败时变为阻塞状态，已经得到资源的进程可以申请新的资源，申请失败时变为阻塞状态， 此时它仍然保持着原有资源不放此时它仍然保持着原有资源不放 不可抢占条件不可抢占条件 u已经分配给一个进程的资源不能被抢占，只能由占有它的进程主动已经分配给一个进程的资源不能被抢占，只能由

33、占有它的进程主动 释放释放 循环等待条件循环等待条件 u系统一定有两个或两个以上的进程组成的一条环路，该环路中的每系统一定有两个或两个以上的进程组成的一条环路，该环路中的每 个进程都在等待着相邻进程正占用着的资源个进程都在等待着相邻进程正占用着的资源 3.5死锁概述死锁概述 处理死锁的四种策略处理死锁的四种策略 预防死锁预防死锁 u通过破除死锁的四个必要条件之一，通过破除死锁的四个必要条件之一， 来防止死锁产生来防止死锁产生 避免死锁避免死锁 u仔细地对资源进行动态分配，以避仔细地对资源进行动态分配，以避 免死锁发生免死锁发生 检测与解除死锁检测与解除死锁 u检测系统中是否出现死锁，若出现检测

34、系统中是否出现死锁，若出现 则解除掉则解除掉 忽略该问题忽略该问题 允许系统发生允许系统发生 死锁，然后解除死锁，然后解除 假装死锁假装死锁 永不发生永不发生 保证系统永远保证系统永远 不会发生死锁不会发生死锁 3.5死锁概述死锁概述 鸵鸟算法鸵鸟算法 思想：不采取任何措施，对死锁视而不见思想：不采取任何措施，对死锁视而不见 实例：实例：UNIX系统（还有其它许多系统）系统（还有其它许多系统） 由于不预防、避免死锁，故系统中可能发生死锁。由于不预防、避免死锁，故系统中可能发生死锁。 而发生时又无法知道（因不检测），造成系统崩溃，而发生时又无法知道（因不检测），造成系统崩溃， 需要重启需要重启

35、之所以被某些系统采用，是因为死锁不常发生之所以被某些系统采用，是因为死锁不常发生 3.6预防死锁预防死锁 预防死锁预防死锁 如果能够保证四个必要条件中至少有一个不成立，如果能够保证四个必要条件中至少有一个不成立， 那么死锁将不会产生（那么死锁将不会产生（Havender，1968） 但其中的但其中的“互斥互斥”条件不能破除条件不能破除 3.6预防死锁预防死锁 破坏破坏“请求和保持请求和保持”条件条件 u第一种协议第一种协议 n规定进程在执行前要一次性地申请运行所需全部资源。规定进程在执行前要一次性地申请运行所需全部资源。 只有资源全部到手，进程方可运行只有资源全部到手，进程方可运行 n优点：简

36、单、易于实现优点：简单、易于实现 n 缺点：资源利用率低；进程运行被延迟缺点：资源利用率低；进程运行被延迟 u第二种协议第二种协议 n允许进程只获得运行初期所需资源后，即可运行。进允许进程只获得运行初期所需资源后，即可运行。进 程运行中释放已占用资源后，再申请新的所需资源程运行中释放已占用资源后，再申请新的所需资源 3.6预防死锁预防死锁 破坏破坏“不可抢占不可抢占”条件条件 u方法方法 n保持资源的进程申请新资源失败时，在转为阻塞状态保持资源的进程申请新资源失败时，在转为阻塞状态 之前，必须释放其占用的全部资源。而该进程自身则之前，必须释放其占用的全部资源。而该进程自身则 必须等到重新获得原

37、有资源及新资源后，才能重新运必须等到重新获得原有资源及新资源后，才能重新运 行行 u缺点缺点 n实现复杂，代价大实现复杂，代价大 3.6预防死锁预防死锁 破坏破坏“循环等待循环等待”条件条件 u方法方法 n将系统中所有资源赋予一个全局编号，进程申请资源将系统中所有资源赋予一个全局编号，进程申请资源 时，必须按编号递增顺序进行时，必须按编号递增顺序进行 u缺点缺点 n找不出一种人人满意的编号顺序找不出一种人人满意的编号顺序 n仍存在资源浪费仍存在资源浪费 n用户编程受到限制用户编程受到限制 3.7避免死锁避免死锁 思路思路 允许进程动态的申请资源允许进程动态的申请资源 将系统状态分为将系统状态分

38、为 u安全状态：不会发生死锁安全状态：不会发生死锁 u不安全状态：可能发生死锁不安全状态：可能发生死锁 避免系统进入不安全状态！避免系统进入不安全状态！ 做法做法 u每次进行资源分配时，首先检测一下每次进行资源分配时，首先检测一下资源分配后资源分配后系统处系统处 于何种状态，若处于于何种状态，若处于安全安全状态，则正式实施本次状态，则正式实施本次分配分配； 若处于若处于不安全不安全状态，则状态，则不予分配不予分配，申请资源的进程阻塞，申请资源的进程阻塞 3.7避免死锁避免死锁 系统的安全状态系统的安全状态 安全状态安全状态 u指系统能按某种进程顺序（指系统能按某种进程顺序（P1，P2，Pn），

39、来为每），来为每 个进程个进程 Pi 分配其所需资源，直至满足每个进程对资源的分配其所需资源，直至满足每个进程对资源的 最大需求，使每个进程都可顺利地完成最大需求，使每个进程都可顺利地完成 u此时称此时称P1，P2，Pn序列为安全序列序列为安全序列 如果系统无法找到这样一个安全序列，则称系统处如果系统无法找到这样一个安全序列，则称系统处 于不安全状态于不安全状态 3.7避免死锁避免死锁 u例，系统有三个进程例，系统有三个进程P1、P2和和P3 ，共用，共用12台磁带机。在台磁带机。在 T0和和T1时刻，系统的资源分配情况分别如下表时刻，系统的资源分配情况分别如下表a和和b。 进程进程 最大需求

40、最大需求 已分配已分配 可用可用 P1 10 5 3 P2 4 2 P3 9 2 进程进程 最大需求最大需求 已分配已分配 可用可用 P1 10 5 2 P2 4 2 P3 9 3 a a b b 3.7避免死锁避免死锁 结果：结果：T0时刻系统处于安全状态。（安全序列时刻系统处于安全状态。（安全序列） P1 P2 P3 可用可用 5(5) 2(2) 2(7) 3 5(5) 4(0) 2(7) 1 5(5) 2(7) 5 10(0) 2(7) 0 2(7) 10 9(0) 3 12 结果：结果：T1时刻系统处于不安全状态。时刻系统处于不安全状态。 P1 P2 P3 可用可用 5(5) 2(2)

41、 3(6) 2 5(5) 4(0) 3(6) 0 5(5) 3(6) 4 3.7避免死锁避免死锁 利用银行家算法避免死锁利用银行家算法避免死锁 数据结构数据结构n个进程个进程 (P1, , Pn)，m类资源类资源(R1, , Rm) u可利用资源向量可利用资源向量Available（m） nAvailablej表示表示 Rj 类资源的可用数目。类资源的可用数目。 u最大需求矩阵最大需求矩阵Max（nm） nMaxi, j表示进程表示进程 Pi 对对 Rj 类资源的最大需求量。类资源的最大需求量。 u分配矩阵分配矩阵Allocation（nm） nAllocation i, j表示已分配给进程表

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

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

44、rk+Allocationi ; 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)，能否分配？，能否分配？ Pro

45、cess Max Allocation Need Available 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

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