操作系统讲义第三章

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

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

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

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

5、统所有就绪进程排成一个或多个队列，方便调度程序最快找到它； （2）分派器（分派程序）：把进程调度程序选定的进程从就绪队列移出，切换上下文，然后把CPU分配给它； （3）上下文切换机制：保存当前程序的上下文，装入分派程序的上下文；移出分派程序，装入新选进程的CPU信息；2022-3-15第二章 进程管理63.1 处理机调度的层次处理机调度的层次进程调度方式进程调度方式 3.低级调度（低级调度（Low Level Scheduling）l非抢占方式：非抢占方式：一旦处理机分配给某个进程，不管它要运行多长时间，都让它一直运行下去，决不会因为其它原因而抢占正在运行进程的处理机。这种方式下引起进程调度的

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

7、主要包括：优先权原则：优先权高的进程可以抢占当前优先权低的进程的CPU；短作业（进程）优先原则：短作业（进程）可以抢占当前较长作业（进程的）CPU；时间片原则：时间片轮转；优点：防止一个长进程长时间占用处理机，公平服务，适优点：防止一个长进程长时间占用处理机，公平服务，适合实时任务的需求；合实时任务的需求；缺点：需要付出较大的开销。缺点：需要付出较大的开销。2022-3-15第二章 进程管理83.2 调度队列模型和调度准则调度队列模型和调度准则仅有进程调度的调度队列模型仅有进程调度的调度队列模型 通常在分时系统分时系统中只设置进程调度，每个用户建立一个进程，系统利用堆栈、树或者链表来管理就绪进

8、程队列，就绪进程以就绪进程以FIFO队列队列形式组织形式组织。 1. 调度队列模型调度队列模型进程执行时可能出现的三种情况：进程执行时可能出现的三种情况：在给定时间片完成，释放处理机进入完成状态；本次时间片内未完成，放入就绪队列尾部；因为某事件被阻塞，放入阻塞队列。就 绪 队 列CPU阻 塞 队 列交互用户时间片完进程调度等待事件进程完成事件出现2022-3-15第二章 进程管理93.2 调度队列模型和调度准则调度队列模型和调度准则具有高级和低级调度的调度队列模型具有高级和低级调度的调度队列模型 在批处理系统批处理系统中，作业调度按照一定的算法从外存的后备队列选择一批作业调入内存，建立进程，送

9、入就绪队列，然后按照一定的进程调度算法选择进程，分配CPU。 1. 调度队列模型调度队列模型就 绪 队 列CPU阻 塞 队 列作业调度时间片完进程调度等待事件1进程完成事件1出现队 列后 备阻 塞 队 列阻 塞 队 列等待事件2等待事件n事件2出现事件n出现队2022-3-15第二章 进程管理103.2 调度队列模型和调度准则调度队列模型和调度准则 1. 调度队列模型调度队列模型具有高级和低级调度的调度队列模型的特点具有高级和低级调度的调度队列模型的特点：（1）采用优先权就绪队列，优先权就绪队列，队首进程优先权最高，或者采用无序 链表方式；（2）设置多个阻塞队列，每个队列对应于某一种进程阻塞事

10、件；2022-3-15第二章 进程管理113.2 调度队列模型和调度准则调度队列模型和调度准则同时具有三级调度的调度队列模型同时具有三级调度的调度队列模型 可把进程的就绪状态分成内存就绪和外存就绪，类似地，阻塞状态也可进一步分成内存阻塞和外存阻塞，调出操作调出操作可使进程状态由内存就绪转为外存就绪，内存阻塞转为外存阻塞；中级调度中级调度可使外存就绪转为内存就绪。 1. 调度队列模型调度队列模型就 绪 队 列CPU绪 挂 起队 列就作业调度时间片完进程调度进程完成事件出现队 列后 备塞挂 队队 列阻阻 塞 队 列等待事件起批量作业挂起事件出现中级调度中级调度2022-3-15第二章 进程管理12

11、3.2 调度队列模型和调度准则调度队列模型和调度准则 面向用户的准则面向用户的准则 （1）周转时间短（批处理系统）周转时间短（批处理系统） 平均周转时间T的计算如下： 平均带权周转时间W的计算如下： （2）响应时间快（分时系统）：）响应时间快（分时系统）：是指从用户通过键盘提交一个请求开始，直到系统首次响应为止的时间必须快； （3）截止时间的保证（实时系统）：）截止时间的保证（实时系统）：是指某任务必须开始执行的最迟时间，或必须完成的最迟时间必须有保证； （4）优先权准则：）优先权准则：遵循优先权准则让某些紧急的作业得到及时处理。 2. 选择调度方式和算法的若干准则选择调度方式和算法的若干准则

12、niiTnT11nisiTTnW112022-3-15第二章 进程管理133.2 调度队列模型和调度准则调度队列模型和调度准则面向系统的准则面向系统的准则 2. 选择调度方式和算法的若干准则选择调度方式和算法的若干准则（1）系统吞吐量高：）系统吞吐量高：这个是评价批处理系统性能的另一个重要指标，因此是选择批处理作业调度的重要准则。吞吐量是指单位时间内系统完成的作业数，它直接和作业的平均长度有关；（2）处理机利用率好：）处理机利用率好：CPU价格昂贵，利用率成为衡量系统性能的重要指标；（3）各类资源的平衡利用：）各类资源的平衡利用：不仅要使处理机利用率高，还要有效地利用其它各类资源，如内存、外存

13、和I/O设备，适当的调度方式和算法可以使系统中的各类资源处于忙碌状态。2022-3-15第二章 进程管理143.3 调度算法调度算法是一种最简单的调度算法，适用于作业调度和进程调度，每次调度是一种最简单的调度算法，适用于作业调度和进程调度，每次调度都是从后备队列中选择一个或者多个最先进入该队列的作业，将它都是从后备队列中选择一个或者多个最先进入该队列的作业，将它们调入内存，分配资源，创建进程，然后放入就绪队列。们调入内存，分配资源，创建进程，然后放入就绪队列。 1. 先来先服务调度算法先来先服务调度算法FCFS（First Come First Service）FCFS算法比较有利于长作业（进

14、程），不利于短作业（进程）算法比较有利于长作业（进程），不利于短作业（进程）进程名进程名到达到达 时间时间服务服务 时间时间开始执开始执行时间行时间完成完成 时间时间周转周转 时间时间带权周带权周转时间转时间A010111B110011011001C21101102100100D31001022021991.992022-3-15第二章 进程管理153.3 调度算法调度算法是指对短作业或者短进程优先调度的算法，适用于作业调度和是指对短作业或者短进程优先调度的算法，适用于作业调度和进程调度，进程调度，SJF算法就是从后备队列中选择一个运行时间最短的算法就是从后备队列中选择一个运行时间最短的作业，

15、然后把它们调入内存运行。作业，然后把它们调入内存运行。 2. 短作业优先调度算法短作业优先调度算法SJF（Short Job First）SJF的优点：能有效地降低作业的平均等待时间，提高系统吞吐量；的优点：能有效地降低作业的平均等待时间，提高系统吞吐量；进程名进程名到达到达 时间时间服务服务 时间时间开始执开始执行时间行时间完成完成 时间时间周转周转 时间时间带权周带权周转时间转时间A030331B145982C223531.5D35914112.2SJF的缺点的缺点： 1）对长作业不利；）对长作业不利；2）未考虑作业的紧迫度；）未考虑作业的紧迫度；3）用户）用户估计执行时间的不准确性。估计

16、执行时间的不准确性。2022-3-15第二章 进程管理163.3 调度算法调度算法 3. FCFS和和SJF的性能比较的性能比较算法算法进程名进程名ABCDE平平 均均到达时间到达时间01234服务时间服务时间43524FCFS完成时间完成时间47121418周转时间周转时间461011149带权周转时间带权周转时间1225.53.52.8SJF完成时间完成时间4918613周转时间周转时间4816398带权周转时间带权周转时间12.673.21.52.252.12022-3-15第二章 进程管理173.3 调度算法调度算法是为了照顾紧迫型紧迫型作业，使之在进入系统后便获得优先处理，该算法会把

17、处理机分配给优先级最高优先级最高的作业（或者进程）。 1）非抢占式优先权调度算法）非抢占式优先权调度算法，适用于批处理系统或实时性要求不高的系统； 2）抢占式优先权调度算法）抢占式优先权调度算法，能更好地满足紧迫作业，适合于严格的实时系统或者对性能要求较高的批处理和分时系统中。 4. 高优先权优先调度算法（高优先权优先调度算法（Priority Job First）2022-3-15第二章 进程管理183.3 调度算法调度算法 4. 高优先权优先调度算法（高优先权优先调度算法（Priority Job First）优先权的类型静态优先权：静态优先权：创建进程时确定，在整个运行期间保持不变；进程

18、类型，系统进程要比用户进程优先级高；进程对资源的要求，要求少的优先级高；用户要求，用户进程的紧迫程度。优点：简单易行，系统开销小缺点：不够精确，可能使优先权低的作业（进程）长期得不到调度动态优先权：动态优先权：创建时赋予，可以随着进程的推进或随其等待时间的增加而改变，以便获得更好的调度性能。优点：使调度更加公平，调度性能高缺点：系统开销稍大2022-3-15第二章 进程管理193.3 调度算法调度算法高响应比优先调度算法高响应比优先调度算法 每个作业的优先级动态计算，作业的优先级随等待时间的增加而不断提高。 4. 高优先权优先调度算法（高优先权优先调度算法（Priority Job First

19、）结论：如果作业等待时间相同，要求服务时间越短，优先级越高，该算法利于短作业；如果要求服务时间相同，那么等待时间越长，优先权越高，它实现的是先来先服务；对于长作业，作业的优先级随着等待时间的增加而提高，如果等待时间足够长也可以获得处理机。优点：既照顾了短作业，又考虑了作业的先后顺序，使长作业也可以得到服务；缺点：但优先级的计算增加了系统的开销。响应比RP=等待时间+要求服务时间要求服务时间=响应时间要求服务时间2022-3-15第二章 进程管理203.3 调度算法调度算法基本原理基本原理 系统将所有就绪进程按照先来先服务的原则排成一个队列，每次调度把CPU分配给队首进程，并令其执行一个时间片，

20、当执行时间片用完，调度程序停止其执行，并把它送到队列尾部。 5. 基于时间片的轮转调度算法（基于时间片的轮转调度算法（Round Robin）时间片大小时间片大小如果太小利于短作业，但是会频繁中断，进程上下文切换，增加系统开销；如果太大则每个进程都能在时间片内完成，则退化为FCFS算法，无法满足交互式用户的需求。2022-3-15第二章 进程管理213.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 18ABACBDAECBD

21、AECABCDEECECC2022-3-15第二章 进程管理223.3 调度算法调度算法 队列（队列（q=1） 时间 队列状态时间 队列状态0A10DAECB完成1BA11AECD完成2ACB12ECA完成3CBDA13CE4BDAEC14EC5DAECB15CE6AECBD16EC7ECBDA17CE完成8CBDAE18C完成9BDAEC2022-3-15第二章 进程管理233.3 调度算法调度算法 队列（队列（q=4）时间队列状态0A4BCDEA完成7CDEB完成11DEC13ECD完成17CE完成18C完成2022-3-15第二章 进程管理243.3 调度算法调度算法 5. 时间片轮转法

22、时间片轮转法RR算法算法进程名进程名ABCDE平平 均均到达时间到达时间01234服务时间服务时间43524RRq=1完成时间完成时间1210181117周转时间周转时间1291681311.6带权周转时间带权周转时间333.243.253.29RRq=4完成时间完成时间47181317周转时间周转时间461610139.8带权周转时间带权周转时间123.253.252.892022-3-15第二章 进程管理253.3 调度算法调度算法调度算法的实施过程调度算法的实施过程设置多个就绪队列，赋予不同的优先级，各个队列优先级递减，时间片递增；新进程放入第一个队列尾部，FCFS原则排队调度，时间片内

23、完成则撤离系统，如果没完则转入下个队列尾部，以此类推，在第n个队列采取时间片轮转调度；第一队列空闲，调度第二队列，以此类推，新进程如果优先级高，可抢占处理机。 6. 多级反馈队列调度算法（多级反馈队列调度算法（Round Robin With Multiple Feedback）2022-3-15第二章 进程管理263.3 调度算法调度算法 6. 多级反馈队列调度算法（多级反馈队列调度算法（Round Robin With Multiple Feedback）算法的性能算法的性能终端型作业用户，大多属于交互型作业，作业小；短批处理作业用户，周转时间短；长批处理用户，不用担心作业长期得不到处理。

24、就绪队列1就绪队列2就绪队列3就绪队列4至CPU至CPU至CPU至CPUS1S2S3（时间片：S1S2 S3）新进程2022-3-15第二章 进程管理273.4 实时调度实时调度提供必要的信息提供必要的信息就绪时间，任务就绪的起始时间；开始截止时间和完成截止时间；处理时间，一个任务从开始执行直至完成所需的时间；资源要求，任务执行的时候需要的一组资源；优先级，对紧迫任务设置“绝对绝对”优先级，松弛任务设置“相对相对”优先级。 1. 实现实时调度的基本条件实现实时调度的基本条件2022-3-15第二章 进程管理283.4 实时调度实时调度 1. 实现实时调度的基本条件实现实时调度的基本条件具有快速

25、切换机制具有快速切换机制对外部中断的快速响应能力；快速的任务分派能力。系统处理能力强系统处理能力强表示周期时间表示处理时间，其中ii1PC1niiiPC采用抢占式调度机制采用抢占式调度机制采用单处理机系统，增强处理能力，减少每个任务处理时间；采用多处理机调度单处理机实时调度条件：2022-3-15第二章 进程管理293.4 实时调度实时调度非抢占式调度算法非抢占式调度算法非抢占式轮转调度算法；非抢占式优先级调度算法。抢占式调度算法抢占式调度算法基于时钟中断的抢占式优先权调度算法立即抢占的优先权调度算法 2. 实时调度算法分类实时调度算法分类最早截止时间优先最早截止时间优先EDF（Earlies

26、t Deadline First）算法）算法 3. 常用的几种实时调度算法常用的几种实时调度算法最低松弛度优先级最低松弛度优先级LLF（Least Laxity First）算法）算法 任务的松弛度任务的松弛度=必须完成时间必须完成时间 - 其本身运行时间其本身运行时间 - 当前时间当前时间 松弛度松弛度=0表示该任务必须马上执行，否则会造成严重后果。表示该任务必须马上执行，否则会造成严重后果。2022-3-15第二章 进程管理303.5 产生死锁的原因和必要条件产生死锁的原因和必要条件竞争资源：多个进程共享资源，资源数目不足所引起进竞争资源：多个进程共享资源，资源数目不足所引起进程对资源的竞

27、争；程对资源的竞争；可剥夺资源和非剥夺性资源竞争非剥夺性资源竞争临时性资源 1. 产生死锁的原因产生死锁的原因 死锁（死锁（Deadlock）：）：是指多个进程在运行过程中因争夺资源而造成的一种僵局（DeadlyEmbrace），当进程出现这种僵持状态时，若无外力作用，它们将无法再向前推进。2022-3-15第二章 进程管理313.5 产生死锁的原因和必要条件产生死锁的原因和必要条件 1. 产生死锁的原因产生死锁的原因进程推进顺序非法：请求和释放资源顺序不当。进程推进顺序非法：请求和释放资源顺序不当。1）进程推进顺序合法 2）进程推进顺序非法P1：Request(R1); Request(R2

28、);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); P1P2R1R22022-3-15第二章 进程管理323.5 产生死锁的原因和必要条件产生死锁的原因和必要条件（1） 互斥条件互斥条件，一段时间内某资源只能由一个进程占用；（2） 请求和保持条件请求和保持条件，部分分配资源；（3） 不剥夺条件不剥夺条件，进程已获得资源不能被剥夺，直至使用完毕；（4）

29、 环路等待条件环路等待条件，发生死锁时必然存在进程-资源的环形链。 2. 产生死锁的必要条件产生死锁的必要条件（1）预防死锁预防死锁：通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或者几个，预防死锁的发生；（2）避免死锁：避免死锁：在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁；（3）检测死锁：检测死锁：通过系统所设置的检测机制，及时地检测出死锁的发生，并精确地确定与死锁有关的进程和资源；（4）解除死锁：解除死锁：与死锁检测配合，通过撤销和挂起一些进程，以便回收一些资源，再将这些资源分配给处于阻塞状态的进程，使之就绪，以继续运行。 3. 处理死锁的基本

30、方法处理死锁的基本方法2022-3-15第二章 进程管理333.6 预防死锁的方法预防死锁的方法（1） 摒弃“请求和保持请求和保持”条件，要么全部分配，要么一个也不分配；（2） 摒弃“不剥夺不剥夺”条件，资源在进程运行过程中可被暂时释放；（3） 摒弃“环路等待环路等待”条件，进程对资源的请求按照某种顺序依次进行。 1. 预防死锁预防死锁安全状态安全状态 是指系统能按某种进程顺序（P1，P2， ，Pn），来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都顺利执行。安全状态实例安全状态实例:假设系统中有三个进程P1，P2，P3，共12台磁带机。2. 系统安全状态系统安全

31、状态进程最大需求已分配可用P11053P242P3922022-3-15第二章 进程管理343.6 预防死锁的方法预防死锁的方法数据结构数据结构 3. 银行家算法银行家算法（1）可利用资源向量Available（m个元素的数组），其中Availablej = k，表示系统中 Rj 类资源有 k 个。 （2）最大需求矩阵Max（nm）的矩阵，Maxi,j=k，表示进程Pi需要Rj类资源的最大数目是k个。（3）分配矩阵Allocation（ nm）的矩阵， Allocationi,j=k，表示Pi已经分得Rj类资源的数目是k个。（4）需求矩阵Need （ nm）的矩阵， Needi,j=k，表示P

32、i还需要Rj类资源的数目是k个。上述关系：上述关系： Needi,j= Maxi,j - Allocationi,j；2022-3-15第二章 进程管理353.6 预防死锁的方法预防死锁的方法算法描述算法描述 3. 银行家算法银行家算法 假设Request i 是Pi的请求向量，Request 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分配资源

33、（试探性的分配试探性的分配）： Availablej:=Availablej - Request i j ; Allocationi,j:=Allocationi,j + Request i j; Needi,j:=Needi,j - Request i j;（4）执行安全性算法，若安全则分配（为Pi），否则不分配，令Pi等待。2022-3-15第二章 进程管理363.6 预防死锁的方法预防死锁的方法安全性算法安全性算法 3. 银行家算法银行家算法（1）设置两个向量：工作向量Work，表示系统可提供给进程继续运行所需的各类资源数目，含有m个元素，初始work := Available；向量Fi

34、nish，表示系统是否有足够的资源分配给进程，使之运行完成，初始时Finish:=false，有足够资源分配时，Finish:=true； （2）在进程集合中找到一个能满足下述条件的进程： a）Finishi=false; b）Needi,j Workj；如果找到则转（3），否则转（4）；（3）进程Pi获得资源可顺利完成，并释放资源，则执行 Workj:=Workj + Allocationi,j; Finishi:=true; 转（2）；（4）如果所有进程的Finishi=true都满足，表示系统处于安全状态，否则系统进入不安全状态。2022-3-15第二章 进程管理373.6 预防死锁的方

35、法预防死锁的方法假设系统中有五个进程假设系统中有五个进程P0, P1, P2, P3, P4和三类资源和三类资源A, B, C，各，各种资源的数量分别为种资源的数量分别为10、5、7，在，在T0时刻的资源分配情况下表：时刻的资源分配情况下表： 4. 银行家算法的实例银行家算法的实例进程进程/资源资源MaxAllocationNeedAvailableA B CA B CA B CA B CP0P1P2P3P47 5 33 2 29 0 22 2 24 3 30 1 02 0 0(3 0 2)3 0 22 1 10 0 27 4 31 2 2(0 2 0)6 0 00 1 14 3 13 3 2

36、(2 3 0)2022-3-15第二章 进程管理383.6 预防死锁的方法预防死锁的方法 4. 银行家算法的实例银行家算法的实例进程进程/资源资源WorkNeedAllocationWork+AllocationFinishA B CA B CA B CA B CP1P3P4P2P03 3 25 3 27 4 37 4 5 10 4 71 2 20 1 14 3 16 0 0 7 4 32 0 02 1 10 0 23 0 2 0 1 05 3 27 4 37 4 510 4 710 5 7truetruetruetruetrue(1) T0时刻的安全性：存在安全序列时刻的安全性：存在安全序列

37、P1 , P3, P4, P2, P0。2022-3-15第二章 进程管理393.6 预防死锁的方法预防死锁的方法 4. 银行家算法的实例银行家算法的实例进程进程/资源资源WorkNeedAllocationWork+AllocationFinishA B CA B CA B CA B CP1P3P4P0P22 3 05 3 27 4 37 4 5 7 5 50 2 00 1 14 3 17 4 3 6 0 0 3 0 22 1 10 0 20 1 0 3 0 2 5 3 27 4 37 4 57 5 510 5 7truetruetruetruetrue(2) P1请求资源，发出请求向量请求

38、资源，发出请求向量Request 1 (1,0,2)，进行检查，进行检查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等待。等待。2022-3-15第二章 进程管理403.6 预防死

39、锁的方法预防死锁的方法 4. 银行家算法的实例银行家算法的实例进程进程/资源资源AllocationNeedAvailableA B CA B CA B CP0P1P2P3P40 3 03 0 23 0 22 1 10 0 27 2 30 2 06 0 00 1 14 3 12 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分配资源，修改相关数据如下。分配资源，修改相

40、关数据如下。(5) 进行安全性检查，进行安全性检查，Available(2, 1, 0)已不能满足任何进程需要，故已不能满足任何进程需要，故系统进入不安全状态。系统进入不安全状态。2022-3-15第二章 进程管理413.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) 资源

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