操作系统讲义-第三章

1、2021-7-12操作系统讲义1 第第三三章章 处理机调度与死锁处理机调度与死锁 2021-7-12第二章 进程管理2 主要内容主要内容 3.1 处理机调度的层次处理机调度的层次 3.2 调度队列模型和调度准则调度队列模型和调度准则 3.3 几种调度算法几种调度算法 3.4 实时调度实时调度 3.5 产生死锁的原因和必要条件产生死锁的原因和必要条件 3.6 预防死锁的方法预防死锁的方法 3.7 死锁的检测和解除死锁的检测和解除 2021-7-12第二章 进程管理3 3.1 处理机调度的层次处理机调度的层次 作业的基本概念作业的基本概念 1. 高级调度（高级调度（High Level Sched

2、uling） 主要功能：根据某种算法，把外存中把处于后备队列中的 那些作业调入内存，当作业完成时做善后处理。 作业（Job）：包含通常的程序和数据，并且配有作业说明书； 作业步（Job Step）：“编译” - “连接装配” - “运行”； 作业流：若干个作业在系统外存形成的输入流。 作业控制块作业控制块JCB（Job Control Block） 通常包含：作业标识、用户名称、用户账户、作业类型（CPU繁忙， I/O繁忙，批量型，终端型）、作业状态、调度信息（优先级，作业 运行时间）、资源需求（运行时间，内存，I/O类型数量）、进入系 统时间、开始处理时间、作业完成时间、作业退出时间、资源使

3、用 情况。 2021-7-12第二章 进程管理4 3.1 处理机调度的层次处理机调度的层次 1. 高级调度（高级调度（High Level Scheduling） 作业调度：作业调度：是根据作业控制块中的信息，审查系统能否满足用户作业的 资源需求，以及按照一定的算法，从外存后备队列中选取某些作业调入 内存，为它们创建进程、分配必要的资源，然后将进程插入就绪队列， 准备执行。 目的：目的：提高内存利用率和系统吞吐量，使那些暂时不能运行的进程 不再占用内存，把它们调至外存（存储管理中的对换功能）。 1）接收多少个作业到内存：取决于多道程序度 2）接收哪些作业：取决于调度算法 最简单：先来先服务调度

4、算法 最常用：短作业优先调度算法 较常用：优先级调度算法 比较好：响应比高者优先调度算法 2. 中级调度中级调度（Intermediate Level Scheduling） 2021-7-12第二章 进程管理5 3.1 处理机调度的层次处理机调度的层次 3. 低级调度（低级调度（Low Level Scheduling） 它所调度的对象是进程（或内核级线程），当CPU需要重新分配 时，利用一定的算法把它分配给进程，它是最基本的调度。 进程调度的功能进程调度的功能 （1）保存处理机的现场信息； （2）按照某种算法选择进程（如优先数算法，轮转算法） （3）把处理器分配给进程。 进程调度的三个基本

5、机制进程调度的三个基本机制 （1）排队器：事先将系统所有就绪进程排成一个或多个队列， 方便调度程序最快找到它； （2）分派器（分派程序）：把进程调度程序选定的进程从就绪 队列移出，切换上下文，然后把CPU分配给它； （3）上下文切换机制：保存当前程序的上下文，装入分派程序 的上下文；移出分派程序，装入新选进程的CPU信息； 2021-7-12第二章 进程管理6 3.1 处理机调度的层次处理机调度的层次 进程调度方式进程调度方式 3.低级调度（低级调度（Low Level Scheduling） l非抢占方式：非抢占方式：一旦处理机分配给某个进程，不管它要运 行多长时间，都让它一直运行下去，决不

6、会因为其它原 因而抢占正在运行进程的处理机。这种方式下引起进程 调度的因素包括： 执行完毕或者发生某事件不能再执行 执行进程提出I/O请求而暂停执行 在进程通信或者同步过程中执行了某种原语操作，如P，Block等 优点：实现简单，系统开销小，适用于大多数批处理系统；优点：实现简单，系统开销小，适用于大多数批处理系统； 缺点：难以满足紧急任务要求，可能造成难以预料的后果。缺点：难以满足紧急任务要求，可能造成难以预料的后果。 2021-7-12第二章 进程管理7 3.1 处理机调度的层次处理机调度的层次 进程调度方式进程调度方式 3.低级调度（低级调度（Low Level Scheduling）

7、l抢占方式：抢占方式：允许调度程序根据某种原则某种原则去暂停某个正在 执行的进程，这些原则主要包括： 优先权原则：优先权高的进程可以抢占当前优先权低的进程的 CPU； 短作业（进程）优先原则：短作业（进程）可以抢占当前较长 作业（进程的）CPU； 时间片原则：时间片轮转； 优点：防止一个长进程长时间占用处理机，公平服务，适优点：防止一个长进程长时间占用处理机，公平服务，适 合实时任务的需求；合实时任务的需求； 缺点：需要付出较大的开销。缺点：需要付出较大的开销。 2021-7-12第二章 进程管理8 3.2 调度队列模型和调度准则调度队列模型和调度准则 仅有进程调度的调度队列模型仅有进程调度的

8、调度队列模型 通常在分时系统分时系统中只设置进程调度，每个用户建立一个进程，系统 利用堆栈、树或者链表来管理就绪进程队列，就绪进程以就绪进程以FIFO队列队列 形式组织形式组织。 1. 调度队列模型调度队列模型 进程执行时可能出现的三种情况：进程执行时可能出现的三种情况： 在给定时间片完成，释放处理机进入完成状态； 本次时间片内未完成，放入就绪队列尾部； 因为某事件被阻塞，放入阻塞队列。 就 绪 队 列CPU 阻 塞 队 列 交互用户 时间片完 进程调度 等待事件 进程完成 事件出现 2021-7-12第二章 进程管理9 3.2 调度队列模型和调度准则调度队列模型和调度准则 具有高级和低级调度

9、的调度队列模型具有高级和低级调度的调度队列模型 在批处理系统批处理系统中，作业调度按照一定的算法从外存的后备队列选择 一批作业调入内存，建立进程，送入就绪队列，然后按照一定的进 程调度算法选择进程，分配CPU。 1. 调度队列模型调度队列模型 就 绪 队 列CPU 阻 塞 队 列 作业调度 时间片完 进程调度 等待事件1 进程完成 事件1出现 队 列后 备 阻 塞 队 列 阻 塞 队 列 等待事件2 等待事件n 事件2出现 事件n出现 队 2021-7-12第二章 进程管理10 3.2 调度队列模型和调度准则调度队列模型和调度准则 1. 调度队列模型调度队列模型 具有高级和低级调度的调度队列模

10、型的特点具有高级和低级调度的调度队列模型的特点： （1）采用优先权就绪队列，优先权就绪队列，队首进程优先权最高，或者采用无序 链表方式； （2）设置多个阻塞队列，每个队列对应于某一种进程阻塞事件； 2021-7-12第二章 进程管理11 3.2 调度队列模型和调度准则调度队列模型和调度准则 同时具有三级调度的调度队列模型同时具有三级调度的调度队列模型 可把进程的就绪状态分成内存就绪和外存就绪，类似地，阻塞状态 也可进一步分成内存阻塞和外存阻塞，调出操作调出操作可使进程状态由内 存就绪转为外存就绪，内存阻塞转为外存阻塞；中级调度中级调度可使外存 就绪转为内存就绪。 1. 调度队列模型调度队列模型

11、 就 绪 队 列CPU 绪 挂 起队 列就 作业调度 时间片完 进程调度进程完成 事件出现 队 列后 备 塞挂 队队 列阻 阻 塞 队 列 等待事件 起 批量作业 挂起 事件出现 中级调度中级调度 2021-7-12第二章 进程管理12 3.2 调度队列模型和调度准则调度队列模型和调度准则 面向用户的准则面向用户的准则 （1）周转时间短（批处理系统）周转时间短（批处理系统） 平均周转时间T的计算如下： 平均带权周转时间W的计算如下： （2）响应时间快（分时系统）：）响应时间快（分时系统）：是指从用户通过键盘提交一个请求 开始，直到系统首次响应为止的时间必须快； （3）截止时间的保证（实时系统）

12、：）截止时间的保证（实时系统）：是指某任务必须开始执行的最 迟时间，或必须完成的最迟时间必须有保证； （4）优先权准则：）优先权准则：遵循优先权准则让某些紧急的作业得到及时处理。 2. 选择调度方式和算法的若干准则选择调度方式和算法的若干准则 n i i T n T 1 1 n i s i T T n W 1 1 2021-7-12第二章 进程管理13 3.2 调度队列模型和调度准则调度队列模型和调度准则 面向系统的准则面向系统的准则 2. 选择调度方式和算法的若干准则选择调度方式和算法的若干准则 （1）系统吞吐量高：）系统吞吐量高：这个是评价批处理系统性能的另一个重要 指标，因此是选择批处理

13、作业调度的重要准则。吞吐量是 指单位时间内系统完成的作业数，它直接和作业的平均长 度有关； （2）处理机利用率好：）处理机利用率好：CPU价格昂贵，利用率成为衡量系统性 能的重要指标； （3）各类资源的平衡利用：）各类资源的平衡利用：不仅要使处理机利用率高，还要有 效地利用其它各类资源，如内存、外存和I/O设备，适当的 调度方式和算法可以使系统中的各类资源处于忙碌状态。 2021-7-12第二章 进程管理14 3.3 调度算法调度算法 是一种最简单的调度算法，适用于作业调度和进程调度，每次调度是一种最简单的调度算法，适用于作业调度和进程调度，每次调度 都是从后备队列中选择一个或者多个最先进入该

14、队列的作业，将它都是从后备队列中选择一个或者多个最先进入该队列的作业，将它 们调入内存，分配资源，创建进程，然后放入就绪队列。们调入内存，分配资源，创建进程，然后放入就绪队列。 1. 先来先服务调度算法先来先服务调度算法FCFS（First Come First Service） FCFS算法比较有利于长作业（进程），不利于短作业（进程）算法比较有利于长作业（进程），不利于短作业（进程） 进程名进程名到达到达 时间时间 服务服务 时间时间 开始执开始执 行时间行时间 完成完成 时间时间 周转周转 时间时间 带权周带权周 转时间转时间 A010111 B110011011001 C2110110

15、2100100 D31001022021991.99 2021-7-12第二章 进程管理15 3.3 调度算法调度算法 是指对短作业或者短进程优先调度的算法，适用于作业调度和是指对短作业或者短进程优先调度的算法，适用于作业调度和 进程调度，进程调度，SJF算法就是从后备队列中选择一个运行时间最短的算法就是从后备队列中选择一个运行时间最短的 作业，然后把它们调入内存运行。作业，然后把它们调入内存运行。 2. 短作业优先调度算法短作业优先调度算法SJF（Short Job First） SJF的优点：能有效地降低作业的平均等待时间，提高系统吞吐量；的优点：能有效地降低作业的平均等待时间，提高系统吞

16、吐量； 进程名进程名到达到达 时间时间 服务服务 时间时间 开始执开始执 行时间行时间 完成完成 时间时间 周转周转 时间时间 带权周带权周 转时间转时间 A030331 B145982 C223531.5 D35914112.2 SJF的缺点的缺点： 1）对长作业不利；）对长作业不利；2）未考虑作业的紧迫度；）未考虑作业的紧迫度；3）用户）用户 估计执行时间的不准确性。估计执行时间的不准确性。 2021-7-12第二章 进程管理16 3.3 调度算法调度算法 3. FCFS和和SJF的性能比较的性能比较 算法算法进程名进程名ABCDE平平 均均 到达时间到达时间01234 服务时间服务时间4

17、3524 FCFS完成时间完成时间47121418 周转时间周转时间461011149 带权周转时间带权周转时间1225.53.52.8 SJF完成时间完成时间4918613 周转时间周转时间4816398 带权周转时间带权周转时间12.673.21.52.252.1 2021-7-12第二章 进程管理17 3.3 调度算法调度算法 是为了照顾紧迫型紧迫型作业，使之在进入系统后便获得 优先处理，该算法会把处理机分配给优先级最高优先级最高的 作业（或者进程）。 1）非抢占式优先权调度算法）非抢占式优先权调度算法，适用于批处理系统或实 时性要求不高的系统； 2）抢占式优先权调度算法）抢占式优先权调

18、度算法，能更好地满足紧迫作业， 适合于严格的实时系统或者对性能要求较高的批处 理和分时系统中。 4. 高优先权优先调度算法（高优先权优先调度算法（Priority Job First） 2021-7-12第二章 进程管理18 3.3 调度算法调度算法 4. 高优先权优先调度算法（高优先权优先调度算法（Priority Job First） 优先权的类型 静态优先权：静态优先权：创建进程时确定，在整个运行期间保 持不变； 进程类型，系统进程要比用户进程优先级高； 进程对资源的要求，要求少的优先级高； 用户要求，用户进程的紧迫程度。 优点：简单易行，系统开销小 缺点：不够精确，可能使优先权低的作业

19、（进程）长期 得不到调度 动态优先权：动态优先权：创建时赋予，可以随着进程的推进或 随其等待时间的增加而改变，以便获得更好的调度 性能。 优点：使调度更加公平，调度性能高 缺点：系统开销稍大 2021-7-12第二章 进程管理19 3.3 调度算法调度算法 高响应比优先调度算法高响应比优先调度算法 每个作业的优先级动态计算，作业的优先级随等待时间的增加而 不断提高。 4. 高优先权优先调度算法（高优先权优先调度算法（Priority Job First） 结论： 如果作业等待时间相同，要求服务时间越短，优先级越高， 该算法利于短作业； 如果要求服务时间相同，那么等待时间越长，优先权越高， 它实

20、现的是先来先服务； 对于长作业，作业的优先级随着等待时间的增加而提高，如 果等待时间足够长也可以获得处理机。 优点：既照顾了短作业，又考虑了作业的先后顺序， 使长作业也可以得到服务； 缺点：但优先级的计算增加了系统的开销。 响应比RP= 等待时间+要求服务时间 要求服务时间 = 响应时间 要求服务时间 2021-7-12第二章 进程管理20 3.3 调度算法调度算法 基本原理基本原理 系统将所有就绪进程按照先来先服务的原则排成一个 队列，每次调度把CPU分配给队首进程，并令其执行 一个时间片，当执行时间片用完，调度程序停止其执 行，并把它送到队列尾部。 5. 基于时间片的轮转调度算法（基于时间

21、片的轮转调度算法（Round Robin） 时间片大小时间片大小 如果太小利于短作业，但是会频繁中断，进程上下 文切换，增加系统开销； 如果太大则每个进程都能在时间片内完成，则退化 为FCFS算法，无法满足交互式用户的需求。 2021-7-12第二章 进程管理21 3.3 调度算法调度算法 5. 基于时间片的轮转调度算法（基于时间片的轮转调度算法（Round Robin） (a) q=1 (b) q=4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 A B A C B D A E C B D A E C A B C D E E C E C C 202

22、1-7-12第二章 进程管理22 3.3 调度算法调度算法 队列（队列（q=1） 时间 队列状态时间 队列状态 0A10DAECB完成 1BA11AECD完成 2ACB12ECA完成 3CBDA13CE 4BDAEC14EC 5DAECB15CE 6AECBD16EC 7ECBDA17CE完成 8CBDAE18C完成 9BDAEC 2021-7-12第二章 进程管理23 3.3 调度算法调度算法 队列（队列（q=4） 时间队列状态 0A 4BCDEA完成 7CDEB完成 11DEC 13ECD完成 17CE完成 18C完成 2021-7-12第二章 进程管理24 3.3 调度算法调度算法 5.

23、 时间片轮转法时间片轮转法RR 算法算法进程名进程名ABCDE平平 均均 到达时间到达时间01234 服务时间服务时间43524 RR q=1 完成时间完成时间1210181117 周转时间周转时间1291681311.6 带权周转时间带权周转时间333.243.253.29 RR q=4 完成时间完成时间47181317 周转时间周转时间461610139.8 带权周转时间带权周转时间123.253.252.89 2021-7-12第二章 进程管理25 3.3 调度算法调度算法 调度算法的实施过程调度算法的实施过程 设置多个就绪队列，赋予不同的优先级，各个队列优先级递减， 时间片递增； 新进

24、程放入第一个队列尾部，FCFS原则排队调度，时间片内 完成则撤离系统，如果没完则转入下个队列尾部，以此类推， 在第n个队列采取时间片轮转调度； 第一队列空闲，调度第二队列，以此类推，新进程如果优先级 高，可抢占处理机。 6. 多级反馈队列调度算法（多级反馈队列调度算法（Round Robin With Multiple Feedback） 2021-7-12第二章 进程管理26 3.3 调度算法调度算法 6. 多级反馈队列调度算法（多级反馈队列调度算法（Round Robin With Multiple Feedback） 算法的性能算法的性能 终端型作业用户，大多属于交互型作业，作业小； 短

25、批处理作业用户，周转时间短； 长批处理用户，不用担心作业长期得不到处理。 就绪队列1 就绪队列2 就绪队列3 就绪队列4 至CPU 至CPU 至CPU 至CPU S1 S2 S3 （时间片：S1S2 S3） 新进程 2021-7-12第二章 进程管理27 3.4 实时调度实时调度 提供必要的信息提供必要的信息 就绪时间，任务就绪的起始时间； 开始截止时间和完成截止时间； 处理时间，一个任务从开始执行直至完成所需的 时间； 资源要求，任务执行的时候需要的一组资源； 优先级，对紧迫任务设置“绝对绝对”优先级，松弛 任务设置“相对相对”优先级。 1. 实现实时调度的基本条件实现实时调度的基本条件 2

26、021-7-12第二章 进程管理28 3.4 实时调度实时调度 1. 实现实时调度的基本条件实现实时调度的基本条件 具有快速切换机制具有快速切换机制 对外部中断的快速响应能力； 快速的任务分派能力。 系统处理能力强系统处理能力强 表示周期时间表示处理时间，其中 ii 1 PC1 n i i i P C 采用抢占式调度机制采用抢占式调度机制 采用单处理机系统，增强处理能力，减少每个任务处理时间； 采用多处理机调度 单处理机实时调度条件： 2021-7-12第二章 进程管理29 3.4 实时调度实时调度 非抢占式调度算法非抢占式调度算法 非抢占式轮转调度算法； 非抢占式优先级调度算法。 抢占式调度

27、算法抢占式调度算法 基于时钟中断的抢占式优先权调度算法 立即抢占的优先权调度算法 2. 实时调度算法分类实时调度算法分类 最早截止时间优先最早截止时间优先EDF（Earliest Deadline First）算法）算法 3. 常用的几种实时调度算法常用的几种实时调度算法 最低松弛度优先级最低松弛度优先级LLF（Least Laxity First）算法）算法 任务的松弛度任务的松弛度=必须完成时间必须完成时间 - 其本身运行时间其本身运行时间 - 当前时间当前时间 松弛度松弛度=0表示该任务必须马上执行，否则会造成严重后果。表示该任务必须马上执行，否则会造成严重后果。 2021-7-12第二

28、章 进程管理30 3.5 产生死锁的原因和必要条件产生死锁的原因和必要条件 竞争资源：多个进程共享资源，资源数目不足所引起进竞争资源：多个进程共享资源，资源数目不足所引起进 程对资源的竞争；程对资源的竞争； 可剥夺资源和非剥夺性资源 竞争非剥夺性资源 竞争临时性资源 1. 产生死锁的原因产生死锁的原因 死锁（死锁（Deadlock）：）：是指多个进程在运行过程中因争夺资源 而造成的一种僵局（DeadlyEmbrace），当进程出现这种僵持 状态时，若无外力作用，它们将无法再向前推进。 2021-7-12第二章 进程管理31 3.5 产生死锁的原因和必要条件产生死锁的原因和必要条件 1. 产生死

29、锁的原因产生死锁的原因 进程推进顺序非法：请求和释放资源顺序不当。进程推进顺序非法：请求和释放资源顺序不当。 1）进程推进顺序合法 2）进程推进顺序非法 P1：Request(R1); Request(R2); P1：Release(R1); Release(R2); P2：Request(R1); Request(R2); P2：Release(R1); Release(R2); P1：Request(R1); P2：Request(R2); P1：Request(R2); P2：Request(R1); P1 P2 R1 R2 2021-7-12第二章 进程管理32 3.5 产生死锁的原因

30、和必要条件产生死锁的原因和必要条件 （1） 互斥条件互斥条件，一段时间内某资源只能由一个进程占用； （2） 请求和保持条件请求和保持条件，部分分配资源； （3） 不剥夺条件不剥夺条件，进程已获得资源不能被剥夺，直至使用完毕； （4） 环路等待条件环路等待条件，发生死锁时必然存在进程-资源的环形链。 2. 产生死锁的必要条件产生死锁的必要条件 （1）预防死锁预防死锁：通过设置某些限制条件，去破坏产生死锁的四个必要 条件中的一个或者几个，预防死锁的发生； （2）避免死锁：避免死锁：在资源的动态分配过程中，用某种方法去防止系统进 入不安全状态，从而避免发生死锁； （3）检测死锁：检测死锁：通过系统所

31、设置的检测机制，及时地检测出死锁的发 生，并精确地确定与死锁有关的进程和资源； （4）解除死锁：解除死锁：与死锁检测配合，通过撤销和挂起一些进程，以便回 收一些资源，再将这些资源分配给处于阻塞状态的进程，使之就绪， 以继续运行。 3. 处理死锁的基本方法处理死锁的基本方法 2021-7-12第二章 进程管理33 3.6 预防死锁的方法预防死锁的方法 （1） 摒弃“请求和保持请求和保持”条件，要么全部分配，要么一个也不分配； （2） 摒弃“不剥夺不剥夺”条件，资源在进程运行过程中可被暂时释放； （3） 摒弃“环路等待环路等待”条件，进程对资源的请求按照某种顺序依次进 行。 1. 预防死锁预防死锁

32、 安全状态安全状态 是指系统能按某种进程顺序（P1，P2， ，Pn），来为每个进程Pi 分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程 都顺利执行。 安全状态实例安全状态实例:假设系统中有三个进程P1，P2，P3，共12台磁带机。 2. 系统安全状态系统安全状态 进程最大需求已分配可用 P1105 3P242 P392 2021-7-12第二章 进程管理34 3.6 预防死锁的方法预防死锁的方法 数据结构数据结构 3. 银行家算法银行家算法 （1）可利用资源向量Available（m个元素的数组），其中 Availablej = k，表示系统中 Rj 类资源有 k 个。 （2）最

33、大需求矩阵Max（nm）的矩阵，Maxi,j=k，表示进程Pi 需要Rj类资源的最大数目是k个。 （3）分配矩阵Allocation（ nm）的矩阵， Allocationi,j=k，表示 Pi已经分得Rj类资源的数目是k个。 （4）需求矩阵Need （ nm）的矩阵， Needi,j=k，表示Pi还需要 Rj类资源的数目是k个。 上述关系：上述关系： Needi,j= Maxi,j - Allocationi,j； 2021-7-12第二章 进程管理35 3.6 预防死锁的方法预防死锁的方法 算法描述算法描述 3. 银行家算法银行家算法 假设Request i 是Pi的请求向量，Reques

34、t i j=k表示Pi请求k个Rj 类资源，Pi申请后，系统进行检查： （1）如果Request i j Need i,j ，则转（2），否则出错（需要资 源超过它宣布的最大值）。 （2）如果Request i j Available j ，则转（3），否则尚无足够的 资源，Pi必须等待。 （3）系统为Pi分配资源（试探性的分配试探性的分配）： Availablej:=Availablej - Request i j ; Allocationi,j:=Allocationi,j + Request i j; Needi,j:=Needi,j - Request i j; （4）执行安全性算法，

35、若安全则分配（为Pi），否则不分配，令Pi 等待。 2021-7-12第二章 进程管理36 3.6 预防死锁的方法预防死锁的方法 安全性算法安全性算法 3. 银行家算法银行家算法 （1）设置两个向量：工作向量Work，表示系统可提供给进程继续运行 所需的各类资源数目，含有m个元素，初始work := Available；向 量Finish，表示系统是否有足够的资源分配给进程，使之运行完成， 初始时Finish:=false，有足够资源分配时，Finish:=true； （2）在进程集合中找到一个能满足下述条件的进程： a）Finishi=false; b）Needi,j Workj；如果找到则

36、转（3），否则转（4）； （3）进程Pi获得资源可顺利完成，并释放资源，则执行 Workj:=Workj + Allocationi,j; Finishi:=true; 转（2）； （4）如果所有进程的Finishi=true都满足，表示系统处于安全状态， 否则系统进入不安全状态。 2021-7-12第二章 进程管理37 3.6 预防死锁的方法预防死锁的方法 假设系统中有五个进程假设系统中有五个进程P0, P1, P2, P3, P4和三类资源和三类资源A, B, C，各，各 种资源的数量分别为种资源的数量分别为10、5、7，在，在T0时刻的资源分配情况下表：时刻的资源分配情况下表： 4. 银

37、行家算法的实例银行家算法的实例 进程进程/资源资源 MaxAllocationNeedAvailable A B CA B CA B CA B C P0 P1 P2 P3 P4 7 5 3 3 2 2 9 0 2 2 2 2 4 3 3 0 1 0 2 0 0 (3 0 2) 3 0 2 2 1 1 0 0 2 7 4 3 1 2 2 (0 2 0) 6 0 0 0 1 1 4 3 1 3 3 2 (2 3 0) 2021-7-12第二章 进程管理38 3.6 预防死锁的方法预防死锁的方法 4. 银行家算法的实例银行家算法的实例 进程进程/ 资源资源 WorkNeedAllocationWor

38、k+Allocation Finish A B CA B CA B CA B C P1 P3 P4 P2 P0 3 3 2 5 3 2 7 4 3 7 4 5 10 4 7 1 2 2 0 1 1 4 3 1 6 0 0 7 4 3 2 0 0 2 1 1 0 0 2 3 0 2 0 1 0 5 3 2 7 4 3 7 4 5 10 4 7 10 5 7 true true true true true (1) T0时刻的安全性：存在安全序列时刻的安全性：存在安全序列P1 , P3, P4, P2, P0。 2021-7-12第二章 进程管理39 3.6 预防死锁的方法预防死锁的方法 4. 银

39、行家算法的实例银行家算法的实例 进程进程/ 资源资源 WorkNeedAllocationWork+Allocation Finish A B CA B CA B CA B C P1 P3 P4 P0 P2 2 3 0 5 3 2 7 4 3 7 4 5 7 5 5 0 2 0 0 1 1 4 3 1 7 4 3 6 0 0 3 0 2 2 1 1 0 0 2 0 1 0 3 0 2 5 3 2 7 4 3 7 4 5 7 5 5 10 5 7 true true true true true (2) P1请求资源，发出请求向量请求资源，发出请求向量Request 1 (1,0,2)，进行检查

40、，进行检查Request 1 (1,0,2) Need 1 (1,2,2); Request 1 (1,0,2) Available 1 (3,3,2);存在存在 安全序列安全序列P1 , P3, P4, P0, P2。 (3) P4请求资源，发出请求向量请求资源，发出请求向量Request 4 (3,3,0)，检查，检查Request 4 (3,3,0) Need 4 (4,3,1); Request 4 (3,3,0) Available 4 (2,3,0); 让让P4等待。等待。 2021-7-12第二章 进程管理40 3.6 预防死锁的方法预防死锁的方法 4. 银行家算法的实例银行家算

41、法的实例 进程进程/资源资源 AllocationNeedAvailable A B CA B CA B C P0 P1 P2 P3 P4 0 3 0 3 0 2 3 0 2 2 1 1 0 0 2 7 2 3 0 2 0 6 0 0 0 1 1 4 3 1 2 1 0 (4) P0请求资源，发出请求向量请求资源，发出请求向量Request 0 (0,2,0)，进行检查，进行检查Request 0 (0,2,0) Need 0 (7,4,3); Request 0 (0,2,0) Available 0 (2,3,0);假定假定 为为P0分配资源，修改相关数据如下。分配资源，修改相关数据如下。

42、 (5) 进行安全性检查，进行安全性检查，Available(2, 1, 0)已不能满足任何进程需要，故已不能满足任何进程需要，故 系统进入不安全状态。系统进入不安全状态。 2021-7-12第二章 进程管理41 3.7 死锁的检测与解除死锁的检测与解除 资源分配图（资源分配图（Resource Allocation Graph） RAG是由一组结点N和一组边E组成的一个对偶RAG=（N，E）， 对它的约定如下： （1） P=p1, p2, , pn R=r1, r2, , rn P 和R是两个互斥的子集，N=PR （2） eE，它连接P中的一个结点和R中的一个结点 e=（pi, rj) 资源

43、请求边（ pi指向rj ）表示pi请求一个单位的 rj ； e=（rj, pi) 资源分配边（ rj 指向pi ）表示pi分配到一个单位 的rj ； 1. 死锁的检测死锁的检测 P1 P2 R1R2 2021-7-12第二章 进程管理42 3.7 死锁的检测与解除死锁的检测与解除 资源分配图的简化资源分配图的简化 （1）从RAG中找出既不阻塞又不是孤点的进程Pi，消去由Pi出发的和指 向Pi的所有边（请求边和分配边），这等价于Pi获得它所需的资源，不断 向前推进，一直运行完毕，释放出它所占有的全部资源。 （2）进程Pi所释放的资源可以唤醒某些阻塞于该资源的进程Pj，消去Pj 所有的边，使之成为孤点。 （3）如此下去，最后，若消去图中所有的边，则称该图是可完全化简的。 （4）若有向图不能通过任何过程予以简化，则称该图是不可完全简化的。 1. 死锁的检测死锁的检测 死锁定理死锁定理 引理：