第3章 处理机调度与死锁

1、第三章 处理机调度与死锁 【教学目的】了解处理机调度的基本概念、调度算法和类型及死锁的概念、产生条件及检测与解除。 【教学重点】1、处理机调度原理及算法。2、死锁的产生原因及检测与解除。 【分配课时】进度计划6学时第三章 处理机调度与死锁3.1 处理机调度的基本概念3.2 进程调度算法3.3 实时调度3.4 多处理机系统中的调度3.5 产生死锁的原因和必要条件3.6 预防死锁的方法和死锁避免3.7 死锁的检测和解除第一节第一节调度的类型和模型调度的类型和模型一、 调度类型1、高级调度（High level Scheduling）（或作业/长程/接纳调度）（1）定义 把外存上处于后备队列中的那些

2、作业调入内存，并为它们创建进程、分配必要的资源，然后，再将新创建的进程排在就绪队列上，准备执行。在批处理系统中，是先驻留在外存上的，因此需要有作业调度，以将它们分批装入内存。在分时系统中，为了能及时响应，用户通过键盘输入的命令或数据等，都是直接送入内存，因而无需配置作业调度。（2）决定作业调度的两个因素 接纳多少个作业 作业调度每次要接纳多少个作业进入内存，取决于多道程序度（Degree of Multiprogramming）,即允许有多少个作业同时在内存中运行。 接纳哪些作业 应将哪些作业从外存调入内存，将取决于所采用的调度算法。最简单的是先来先服务调度算法，较常用的一种是短作业优先调度算

3、法，还有基于作业优先权的调度算法、响应比高者优先的调度算法等。第一节第一节调度的类型和模型调度的类型和模型 2、低级调度（Low Level Scheduling） 低级调度通常又称为进程调度、短程调度（Short-Term Scheduling）在三种类型的OS中都必须配置这级调度。进程调度可采取下述两种方法： (1)非抢占方式（Non-Preemptive Mode） 采取调度方式时，一旦处理机分配某进程后，便让该进程一直执行，直至该进程完成或发生某事件而被阻塞时，才再把处理机分配给其它进程，决不允许某进程抢占已经分配出去的处理机。 这种调度方式的优点是实现简单、系统开销小，适用大于多数的

4、批处理系统环境。但它难于满足紧急任务的要求。(2)抢占方式（Preemptive Mode） 这种调度方式，允许调度程序根据某种原则，去停止某个正在执行的进程，将已分配给该进程的处理机，重新分陪另一进程。第一节第一节调度的类型和模型调度的类型和模型 抢占的原则有： 时间片原则 各进程按时间片运行，当一个时间片用完后，便停止该进程的执行而重新进姓调度。这种原则适用于分时系统、大多数实时系统，以及要求较高的批处理系统。 优先权原则 通常是对一些重要的和紧急的作业赋予较高的优先权。当这种作业到达时，如果其优先权比正在执行进程的优先权高，便停止正在执行的进程，将处理机分配给优先权高的进程，使之执行。短

5、作业（进程）优先原则 当新到达的作业（进程）比正在执行的作业（进程）明显地短时，将剥夺长作业（进程）的执行，将处理机分配给作业（进程），使之优先执行。 第一节第一节调度的类型和模型调度的类型和模型 3、中级调度 又称中程调度 (1)引入中级调度的目的 是为了提高内存的利用率和系统吐量。(2)定义 应使那些暂时不能运行的进程不再占用宝贵的内存空间，而将它们调至外存上去等待，称此时的进程状态为就绪驻外存状态，或挂起状态。当这些进程重又举备运行条件，且内存又稍有空闲时，由中级调度决定，将外存上的那些重又具备运动条件的就绪进程重新调入内存，并修改其状态为就绪态，挂在就绪队列上，等待进程调度。 第一节第

6、一节调度的类型和模型调度的类型和模型 在上述三种调度中，进程调度的运行频率最高，在分时系统中通常是10-100ms便进行一次进程调度，因而进程调度算法不能太复杂，以免占用太多的CPU时间。作业调度往往是发生在一个（批）作业运行完毕，退出系统又需要重新调入一个（批）作业进入内存时，故作业调度的周期校长，大约几分钟一次。因而也允许作业调度算法花费较多时间，中级调度的运行频率基本上介入于上述两种调度之间。第一节第一节调度的类型和模型调度的类型和模型二、 调度队列模型1、仅有进程调度的调度队列模型 在分时系统中通常仅设置了进程调度。用户键入的命令和数据，都直接送入内存。对于命令，由OS为之建立一个进程

7、，并将它排在就绪队列的末尾，然后按时间片轮转方式执行。每个进程执行时，都可能出现这样三种可能。（1）该任务在该时间片内已经完成，该进程释放处理机后进入完成状态；（2）任务在本其对应的时间内尚未完成，OS便将任务放在就绪队列的后面；（3）在执行期间，进程因某事件而被阻塞后，OS将它们放入阻塞队列。 1.进程调度模型 1) 1)只有进程调度的调度队列模型只有进程调度的调度队列模型图 3 - 1 仅具有进程调度的调度队列模型2、具有高级和低级调度的调度队列模型（见P99图4-2）（1）在OS中不仅引入了进程调度，而且还进入了作业调度。后者从外存的后备队列中选择一批作业调入内存，为之创建进程后，送入就

8、绪队列；（2）在OS中设置多个阻塞队列。当系统中仅设置一个阻塞队列时，可能会使该队列很长，尤其当系统较大时，该队列中可能数百个进程。为了提高队列的操作效率，通常都设置若干个（1，2,.,n）阻塞队列，每个队列对应于一种引起进程阻塞的事件。 2)具有高低级调度的调度队列模型图 3-2 具有高、低两级调度的调度队列模型3、同时具有三级调度的调度队列模型 当在OS中引入中级调度后，可把就绪态分为内存就绪状态、外存就绪状态。可把阻塞状态进一步分成内存阻塞和外存阻塞两种状态。在调出操作的情况下，可使内存就绪转变为外存就绪、内存阻塞转变为外存阻塞；在中级调度的作用下，外存就绪转变为内存就绪。3)具有三级调

9、度的调度队列模型图 3-3 具有三级调度时的调度队列模型三、选择调度方式和算法的若干准则 面向用户的准则：周转时间短；响应时间快；截止时间的保证；优先权准则 面向系统的准则：系统吞吐量高；处理机利用率好；各类资源的平衡利用1、面向用户的准则（1）周转时间短通常把周转时间作为评价批处理系统的性能、选择作业调度方法与算法的准则。定义是指从作业提交给系统开始，到作业完成为止这段时间间隔（称为作业周转时间）。它包括：作业在外存后备队列上等待（作业）调度的时间；进程在就绪队列上等待进程调度的时间；进程在CPU上执行的时间；等待I/O操作完成的时间。 其中，第（2）、（3）、（4）项在一个作业处理过程中，

10、可能发生多次。 对每个用户而言，作业的周转时间最短。但作为计算计系统的管理者，希望平均周转时间最短；这不仅会有效地提高资源利用率，而且还可使大多数用户满意。平均周转时间： T= 带权周转时间:作业周转时间T与系统为它提供的实际服务时间Ts之比，即W=T/Ts称为。而平均带周转时间可表示为：W= （2）响应时间快响应时间是从用户通过键盘提交一个请求开始，直到在屏幕上显示出结果为止的一段时间间隔。它包括：（1）从键盘输入的要求信息传送到处理机的时间；（2）处理机对请求信息进行处理的时间；（3）将所行成的响应回送到终端显示器的时间；（3）截止时间的保证它是用来评价实时系统性的重要指标，因而是选择实时

11、调度算法的重要准则。定义 截止时间：指某任务必须开始执行的最迟时间，或必须完成的最迟时间，对于严格的实时系统，其调度方式和调度算法必须保证这点。否则将可能引起难以预料的后果。（4）优先权准则 让紧急的作业，得到及时的处理。第二节第二节调度算法调度算法 调度算法是指：根据系统的资源分配策略所规定的资源分配算法，对于不同的系统和系统目标，通常采用不同的调度算法。调度算法 先进先出(FIFO)算法 最短CPU运行期优先调度算法 最高优先权优先调度算法 轮转法 多级反馈队列 一、先来先服务调度算法一、先来先服务（FCFS）调度算法1、原理 当在作业调度中采用该算法时，每次调度是从后备作业队列中，选择一

12、个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。 在进程调度中，采用FCFS调度算法时，每次调度是从就绪队列中，选择一个最先进入该进程，把处理分配给它，使之投入运行。该进程一直运行到完或发生某事件阻塞后，才放弃处理机。2、优缺点（1）FCFS算法比较有利于作业（进程），而不利于短作业（进程）。 下表列出了A、B、C、D四个作业分别到达系统的时间、要求服务的时间、开始执行的时间及各自的完成的时间，并计算出各自的周转时间和带权周转时间。从上表可以看出：其中短作业C的带权周转时间竞高达100，这是不能容忍的；而长作业D的带权周转时间仅为1.99。据此可知：（

13、2）FCFS调度算法有利于CPU繁忙型的作业，而不利于I/O繁忙型的作业进程。 CPU繁忙型作业：是指该类作业需要大量的CPU时间进行计算，而很少请求I/O。通常的科学计算便属于CPU繁忙行作业。I/O繁忙行作业：是指CPU进行处理时，又需频繁地请求I/O，而每次I/O的操作时间却又很短。目前的大多数的事务处理，都属于I/O繁忙行作业。1.先进先出(FIFO)算法 该算法总是把处理机分配给最先进入就绪队列的进程，一个进程一旦分得处理机，便执行下去，直到该进程完成或阻塞时，才释放处理机。 优点:实现简单. 缺点:没考虑进程的优先级 2.最短CPU运行期优先调度算法 该算法从就绪队列中选出“下一个

14、CPU执行期”最短的进程，为之分配处理机。 该算法虽可获得较好的调度性能，但难以准确地知道下一个CPU执行期，而只能根据每一个进行的执行历史来预测。图 3-4 FCFS和SJF调度算法的性能 3. FCFS和SJF的性能比较优点（1）短作业（SJF）的调度算法可以照顾到实际上在所有作业中占很大比例的短作业，使它能比长作业优先执行。 （2）SJF调度算法能有效地降低作业的平均等待时间和提高系统的吐量。缺点（1）该算法对长作业非常不利 来的）短作业（进程），将致使长作业（进程）得不到调度。（2）该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业（进程），回得到及时处理；（3）由于作业（进程）的

15、长短只是根据用户所提供的估计执行时间而定，而用户又可能会有意或无意地缩短其作业的估计执行时间，致使该算法不一定能真正做到短作业优先调度。一、优先权调度算法的类型 （1）非抢占式优先权算法 （2）抢占式优先权调度算法 4.最高优先权优先调度算法二、优先权的类型（1）静态优先权 静态优先权是在创建进程时确定的，切规定它在进程的整个运行期间保持不便，。一般，优先权是利用某一范围内的一个整数来表示。确定进程优先权的依据是： 进程类型。 进程对资源的需求。 如进程的估计执行时间及内存需要量少的进程，应赋予较高的优先权。 优缺点 静态优先权法简单易行、系统开销小。 但不够精确，很可能出现优先权低的作业（进

16、程），长期没有调度的情况，因此，仅在要求不太高的系统中，才使用静态优先权。（2）动态优先权 动态优先权是指在创建进程时所赋予的优先权，可以随进程的推进而改变，以变获得更好的性能。 5.高响应比优先调度算法优先权的变化规律可描述为： 由于等待时间与服务时间之和，就是系统对该作业的响应时间，故该优先权又相当于响应比RP。据此，又可表示为： 由上式可以看出：（1）如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业；（2）当要求服务的时间相同时，作业的优先权决定于其等待时间，因而实现了先来先服务；（3）对于长作业，当其等待时间足够长时，其优先权便可升到很高，从而也可获得

17、处理机。 该算法既照顾了短作业，又考虑了作业到达的先后顺序，也不会使作业长期得不到服务。因此，该算法实现了一种较好的折衷。当然，再利用该算法时，每要进行调度之前，都需先进行响应应比的计算，这会增加系统的开销3.2练习练习假如有四道作业，它们的进入时间和运行时间由下表给出，假如有四道作业，它们的进入时间和运行时间由下表给出，在单道程序环境下，分别填写先来先服务、短作业优先和高响在单道程序环境下，分别填写先来先服务、短作业优先和高响应比优先调度算法的完成时间和周转时间，并求出平均周转时应比优先调度算法的完成时间和周转时间，并求出平均周转时间和平均带权周转时间。间和平均带权周转时间。作业作业号号进入

18、时进入时间间(时时)运行时运行时间间(小时小时)FCFSSJF完成时完成时间间(时时)周转时周转时间间(小小时时)完成时完成时间间(时时)周转时周转时间间(小时小时)110:000.4210:101310:200.6410:300.26. 轮转法 在通常的轮转法中，系统将所有的就绪进程按先来先服务原则，排成一个队列，每次调度时把CPU分配给对手进程，并令其执行一个时间片。时间片的大小几ms到几百ms。当执行的时间片用完时，有一个计时器发出时中断，调度程序便据此信号来停止该进程的执行并将它送就绪队列的末尾，等待下一次执行；然后，把处理机分配给就绪队列中新的对手进程，同时也让它执行一个时间片。这样

19、就可以保证就绪队列中的所有进程，在一给定的时间（人所能接受的等待时间）内，均能获得一时间片的处理机执行时间。时间片选择问题时间片选择问题： 固定时间片 可变时间片时间片大小的确定时间片大小的确定 在时间片轮转算法中，时间片的大小对计算机性能有很大影响。如果时间片太大，大到每个进程都能在该时间片内执行完毕，则时间片轮转算法边退出为FCFS算法，因而获得令用户满意的响应时间。（1）系统对响应时间的要求 数目N和时间片q成比例，即T=Nq,因此在用户（进程）数一定时，时间作为分时系统首先就是必须满足系统对响应时间的要求。由于响应时间T直接与用户（进程）片的长短将正比于系统所要求的响应时间。（2）就绪

20、队列中进程的数目（3）系统的处理能力：是必须保证用户键入的常用命令能在一个时间片内处理完毕，否则将无法保证得到满意的响应时间 1)简单轮转法的调度模型2)多队列反馈调度算法 将就绪队列分为N级，每个就绪队列分配给不同的时间片，队列级别越高，时间越小，级别越小，时间片越大，最后一级采用时间片轮转，其他队列采用先进先出； 系统从第一级调度，当第一级为空时，系统转向第二个队列，.当运行进程用完一个时间片，放弃CPU时，进入下一级队列；等待进程被唤醒时，进入原来的就绪队列；当进程第一次就绪时，进入第一级队列 * 首先系统中设置多个就绪队列* 每个就绪队列分配给不同时间片，优先级高的为第一级队列，时间片

21、最小，随着队列级别的降低，时间片加大* 各个队列按照先进先出调度算法* 一个新进程就绪后进入第一级队列* 进程由于等待而放弃CPU后，进入等待队列，一旦等待的事件发生，则回到原来的就绪队列* 当有一个优先级更高的进程就绪时，可以抢占CPU，被抢占进程回到原来一级就绪队列末尾* 当第一级队列空时，就去调度第二级队列，如此类推* 当时间片到后，进程放弃CPU，回到下一级队列 3)多队列反馈调度算法8.进程调度的时机当一个进程运行完毕，或由于某种错误而终止运行当一个进程在运行中处于等待状态（等待I/O）分时系统中时间片到当有一个优先级更高的进程就绪（可抢占式） 例如：新创建一个进程，一个等待进程变成

22、就绪在进程通信中，执行中的进程执行了某种原语操作（P操作，阻塞原语，唤醒原语）何时切换进程 只要OS取得对CPU的控制，进程切换就可能发生，如:超级用户调用 来自程序的显式请求来自程序的显式请求 ( (如：打开文件如：打开文件) )，该，该进程通常会被阻塞进程通常会被阻塞陷阱 最末一条指令导致出错，会引起进程移至退最末一条指令导致出错，会引起进程移至退出状态出状态中断 外部因素影响当前指令的执行，控制被转移外部因素影响当前指令的执行，控制被转移至至IHIH（中断处理程序）（中断处理程序）9.引起进程调度的原因 正在执行的进程执行完毕或因发生某事件而不能再继续执行； 执行中的进程因提出I/O请求

23、而暂停执行； 在进程通信或同步过程中执行了某种原语操作如P操作、阻塞、挂起原语等； 在可剥夺式调度中，有比当前进程优先权更高的进程进入就绪队列； 在时间片轮转法中，时间片完。 通常系统是按先来先服务或优先权形式来组织调度队列。 10.进程调度算法 其中，RQ为就绪队列指针，EP为运行队列指针。3.3 3.3 实实 时时 调调 度度 1.实现实时调度的基本条件实现实时调度的基本条件 提供必要的信息(就绪时间、截止时间、处理时间、资源优先级) 系统处理能力强 采用抢占式调度机制 具有快速切换机制： 具有快速响应外部中断的能力； 快速的任务分派：2.实时调度算法的分类 1)非抢占式调度算法非抢占式调

24、度算法: 非抢占式轮转调度算法 非抢占式优先调度算法2)2)抢占式调度算法抢占式调度算法: : 基于时钟中断的抢占优先调度算法 立即抢占优先权调度算法。 图 3-5 实时进程调度 3.常用的几种实时调度算法 1）最早截止时间优先即）最早截止时间优先即EDF(EarliestDeadlineFirst)算法算法图 3-6 EDF算法用于非抢占调度方式 2）最低松弛度优先(LLF)算法 该算法是根据任务紧急(或松弛)的程度，来确定任务的优先级。该算法主要用于可抢占调度方式中。 假如在一个实时系统中，有两个周期性实时任务A和B，任务A要求每 20 ms执行一次，执行时间为 10 ms；任务B只要求每

25、50 ms执行一次，执行时间为 25 ms。 图 3-7 A和B任务每次必须完成的时间 在刚开始时(t1=0)，A1必须在20ms时完成，而它本身运行又需 10 ms，可算出A1的松弛度为10ms；B1必须在50ms时完成， 而它本身运行就需25 ms，可算出B1的松弛度为25 ms，故调度程序应先调度A1执行。在t2=10 ms时，A2的松弛度可按下式算出： A2的松弛度=必须完成时间-其本身的运行时间-当前时间 =40 ms-10 ms-10 ms=20 ms 类似地，可算出B1的松弛度为15ms，调度程序应选择B2运行。t3=30 ms时，A2的松弛度已减为0，B1的松弛度为15 ms，

26、于是调度程序应抢占B1的处理机而调度A2运行.图 3-8 利用ELLF算法进行调度的情况3.4 多处理机系统中的调度一、多处理机系统的类型1、引入原因（1）增加系统的吞吐量：单位时间内的工作总量。（2）节省投资：采用有N个处理机的系统，可以共用一个机箱，电源，和一部分资源（外设和内存）。（3）提高系统的可靠性：当一台处理机发生故障时，系统能够立即将该台处理机上所处理的任务，迁移到其他一个或多个处理机上去，整个系统仍能正常运行。只是系统的性能稍有降低。2、多处理机类型（1）紧密偶合MPS 通过高速总线或高速开关实现过个处理机之间的互连，共享存储器、I/O设备、系统中的所有资源和进程，都由OS实施

27、统一的管理和控制。（2）松散偶合型MPS 通过通道或通信线路实现多台计算机之间的互连，每台计算机都有自己的存储器和I/O设备，并配置了OS来管理本地资源和在本地运行的进程。3、多处理机OS的类型（1）非对称处理机模式 又称为主-从模式，主处理机只有一个，配有OS，管理整个系统资源，并负责为各从处理机分配任务，从处理机有多个，执行预先规定的任务及由主处理机分配的任务。（2）对称处理机模式SMPS 所有处理机都是相同的，在每个处理机上运行一个相同的OS拷贝。二、进程分配方式1、对称多处理机系统中的进程分配方式（同构型）（1）静态分配（Static Assignment） 一个进程从开始执行直至完成

28、，都被固定地分配到一台处理机上去执行。每一台处理机设备一专用的就绪进程队列，该队列中的诸进程都被先后分配到该台处理机上执行。缺点是会使各处理机的忙、闲不均。（2）动态分配（Dynamic Assignment） 在系统中仅设置一个公共的就绪队列，系统中的所有就绪进程都被放在该队列中。对一进程，可分配到任意一台处理机上。一个进程的整个运行过程而言，在每次被调度执行时，都是随机分配到一台当时是空闲的处理机上去执行。动态分配的优点是消除了处理机忙闲不均的现象，但调度的开销可能较大。(3)自调度(Self-Scheduling) 在系统中仍只设备一个公共就绪队列，处理机自己去查看公共就绪队列，选择一个

29、进程令其执行。2.非对称MPS中的进程分配方式（异构型） 即OS的核心部分驻留在主机上,而从机（Slave）只是执行用户程序，进程调度主机执行。每当机空闲时，主机发送一要求进程的信号这种主一从方式的进成调度。（1）主/从式进程分配的主要优点： 系统处理比较简单，因为所有进程分配都由一台主机独自处理，使进程间的同步问题得以简化。切进程调度程序也很容易从单处理机的进程调度程序演化而来。（2）主/从式进程分配的主要缺点： 可靠性不高：主机一旦出现故障，将会导致整个系统瘫痪，而且也很容易因主机太忙，来不及处理而形成系统瓶颈。三、进程（线程）调度 在多处理机系统中，比较有代表性的进（线）程调度方式有：自

30、调度方式，成组调度（Gang Scheduling），专用处理机分配方式。1、 自调度方式（1）自调度机制 在处理机系统中的自调度，它是直接由单处理机环境下的调度方式演变而来。在系统中设置有一个公共的进程或线程的就绪队列，所有的处理器在空闲时都可自己到该队列中取得一进程（线程）来运行。（2）优点只要系统中有工作可做，只要就绪队列不空，就不会出现处理机空闲的情况。系统中没有集中的调度机制，任何处理机都可利用OS的调度例程去选择一线程。对就绪队列可按单处理机所采用的各种方式加以组织，其调度算法也可沿用单处理所用的算法。如： FCFS算法 最小优先数优先算法 抢占式最小有限数法 （3）缺点由于FCF

31、S算法简单、开销小，从而使它成为一种较好的自调度算法。自调度算法仍存在以下问题。瓶颈问题。 在整个系统中只设备一个就绪线程队列，供多个处理机共享，这些处理机必须互斥地访问该队列，这就很容易形成系统的瓶颈。低效性。 当线程阻塞后又重新就绪时，又进入唯一的就绪队列，可能要多次更换处理机，因而使高速缓存的使用效率很低。线程切换频繁。 在一应用程序中的若干个线程都属于相互合作型的，但在采用自调度方式时，这些线程很难同时获得处理机而同时运行，这将会使某些线程位能获得处理机运行而阻塞。进而被切换下来。2、成组调度所谓成组调度，是将一个进程中的一组线程，分配到一组处理机上去执行。这种调度方式至少有以下两点好

32、处：（1）如果一组相互合作的线程或进程，能并行执行，则可有效地减少线程（进程）的阻塞情况的发生。从而可以减少线程的切换，使系统性能得到改善。（2）因而每次调度都可以解决一组线程的处理机分配问题，因而可以显著地减少调度频率，从而也就减少了调度开销。在成组调度时，如何为应用程序分配处理机时间，可以考虑采用这样两种方式：面向所有应用程序平均分配处理机时间 假设系统中有N个处理器和M个应用程序。每个应用程序中至多N个线程，则每个应用程序可有1/M的时间占有N个处理机。面向所有的现成平均分配处理机时间 应用程序A中有四个线程，应用程序B中只有1个线程。因此，应为应用程序A分配4/5的时间，只为应用程序B

33、分配1/5的时间。按线程数平均分配时间的方法更有效。3、专用处理机分配 专用处理机分配在一个应用程序执行期间，专门为该应用程序分配一组处理机，每一个线程一个。这组处理机供该应用程序专用直至应用程序完成。这会造成处 理机的严重浪费。但把这种调度方式用于并发程序相当高的多处理机的环境。 3.5产生死锁的原因和必要条件产生死锁的原因和必要条件3.5.1 死锁的概念死锁的概念1.1.死锁例子死锁例子: : 一个由于一个由于申请不同类型资源申请不同类型资源而产生死锁而产生死锁的例子的例子 设系统有一台打印机设系统有一台打印机(R1)(R1)一台扫描仪一台扫描仪(R2)(R2)，两进程共享这两台设备。，两

34、进程共享这两台设备。 用信号量用信号量S1S1表示表示R1R1是否可用，用信号量是否可用，用信号量S2S2表示表示R2R2是否可用，是否可用， S1S1、 S2S2初值为初值为1 1。 死锁例子死锁例子 这两个进程在并发执行过程中，可这两个进程在并发执行过程中，可能会发生死锁。大家可以思考一下，如能会发生死锁。大家可以思考一下，如何修改，进程才不会发生死锁。何修改，进程才不会发生死锁。2.死锁概念 指多个进程因竞争共享资源而造成的指多个进程因竞争共享资源而造成的一种僵局，若无外力作用，这些进程一种僵局，若无外力作用，这些进程都将永远不能再向前推进。都将永远不能再向前推进。 即：一组进程中，每个

35、进程都无限等即：一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称现象称为进程死锁，这一组进程就称为死锁进程。为死锁进程。 3.关于死锁的一些结论关于死锁的一些结论 参与死锁的进程最少是两个 参与死锁的进程至少有两个已经占有资源 参与死锁的所有进程都在等待资源 参与死锁的进程是当前系统中所有进程的子集注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。 4.永久性资源和临时性资源永久性资源：可以被多个进程多次永久性资源：可以被多个进程多次使用（可再用资源

36、）使用（可再用资源） 可抢占资源可抢占资源 不可抢占资源不可抢占资源临时性资源：只可使用一次的资源；临时性资源：只可使用一次的资源；如信号量如信号量, ,中断信号，同步信号中断信号，同步信号等（可消耗性资源）等（可消耗性资源）“申请申请-分配分配-使用使用-释放释放”模式模式3.5.2 产生死锁的原因1.1.竞争系统资源竞争系统资源2.2.进程的推进顺序不当进程的推进顺序不当 1. 1. 竞争系统资源 若系统中只有一台打印机若系统中只有一台打印机R1R1和一台和一台读卡读卡机机R2R2，可供进程，可供进程P1P1和和P2P2共享。若共享。若形形成环路成环路，这样会产生死锁，这样会产生死锁。 2

37、.2.进程的推进顺序不当 在进程在进程P1P1和和P2P2并发执行时，按照左图曲并发执行时，按照左图曲线线所示顺序推进时，两进程会顺所示顺序推进时，两进程会顺利完成，我们称这种推进顺序是合法的。利完成，我们称这种推进顺序是合法的。若按曲线若按曲线的顺序推进时，进入不安全的顺序推进时，进入不安全区区D D内，两进程再推进会产生死锁。内，两进程再推进会产生死锁。 3.5.3 产生死锁的必要条件 互斥条件互斥条件（资源独占）（资源独占） 请求和保持条件请求和保持条件（部分分配，（部分分配，占有申请）占有申请） 不剥夺条件（不剥夺条件（不可强占）不可强占） 环路等待条件。环路等待条件。解决死锁的基本办

38、法 预防死锁预防死锁 避免死锁避免死锁 检测死锁检测死锁 解除死锁解除死锁 3.6 预防死锁的方法和避免死锁 1.预防死锁的方法 在系统设计时确定资源分配算法，保证不发生死锁。具体的做法是破坏产生死锁的四个必要条件之一。 1)1)资源一次性分配；资源一次性分配；(破坏请求和保持条件) 2)2)可剥夺资源；可剥夺资源；即当某进程新的资源未满足时，释放已占有的资源(破坏不可剥夺条件) 3)3)资源有序分配法资源有序分配法；做法：系统给每类资源赋予一个编号，每一个进程按编号递增的顺序请求资源，释放则相反(破坏环路等待条件)2. 死锁避免 死锁避免定义死锁避免定义:在系统运行过程中，对进程发出的每一个

39、系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。 预防死锁的几种策略，会严重地损害了系统性能。因此要施加较弱的限制，从而获得较满意得系统性能来避免死锁。 由于在避免死锁的策略中，允许进程动态地申请资源。因而，系统在进行资源分配之前预先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，进程等待。其中最具有代表性的避免死锁算法是银行家算法。3. 安全状态与不安全状态 安全状态指系统能按某种进程安全状态指系统能按某种进程顺序来为每个进程分配其所需资顺序来为每个进程分配其所需资源，直至最大需求，

40、使每个进程源，直至最大需求，使每个进程都可顺序完成。若系统不存在这都可顺序完成。若系统不存在这样一个序列，则称系统处于不安样一个序列，则称系统处于不安全状态。全状态。 1)安全序列 一个进程序列一个进程序列PP1 1，P Pn n 是安是安全的，如果对于每一个进程全的，如果对于每一个进程P Pi i(1(1i in n），它以后尚需要的资源），它以后尚需要的资源量不超过系统当前剩余资源量与所有量不超过系统当前剩余资源量与所有进程进程P Pj j (j i ) (j i )当前占有资源量之和，当前占有资源量之和，系统处于安全状态。系统处于安全状态。 ( (安全状态一定是没有死锁发生的安全状态一定

41、是没有死锁发生的) )2)安全状态之例安全状态之例 我们通过一个例子来说明安全性。假定系统中有三个进程P1、 P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示： 进 程 最 大 需 求 已 分 配 可 用 P1P2P3104952233)由安全状态向不安全状态的转换由安全状态向不安全状态的转换 如果不按照安全序分配资源，则系统可能会由安全状态进入不安全状态。例如，在T0时刻以后，P3又请求1台磁带机，若此时系统把剩余3台中的1台分配给P3，则系统便进入不

42、安全状态。 因为，此时也无法再找到一个安全序列， 例如，把其余的2台分配给P2，这样，在P2完成后只能释放出4台，既不能满足P1尚需5台的要求，也不能满足P3尚需6台的要求，致使它们都无法推进到完成，彼此都在等待对方释放资源，即陷入僵局，结果导致死锁。 安全状态与不安全状态 不安全状态:不存在一个安全序列，不安全状态一定导致死锁4.利用银行家算法避免死锁1)银行家算法中的数据结构银行家算法中的数据结构 (1) 可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态

43、地改变。如果Availablej=K，则表示系统中现有Rj类资源K个。 (2) 最大需求矩阵Max。这是一个nm的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Maxi,j=K，则表示进程i需要Rj类资源的最大数目为K。 (3) 分配矩阵Allocation。这也是一个nm的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocationi,j=K，则表示进程i当前已分得Rj类资源的数目为K。 (4) 需求矩阵Need。这也是一个nm的矩阵，用以表示每一个进程尚需的各类资源数。如果Needi,j=K，则表示进程i还需要Rj类资源K个，方能完成其任务。

44、Needi,j=Maxi,j-Allocationi,j 2)银行家算法银行家算法 设Requesti是进程Pi的请求向量，如果Requestij=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查： (1) 如果RequestijNeedi,j，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。 (2) 如果RequestijAvailablej，便转向步骤(3)；否则， 表示尚无足够资源，Pi须等待。 (3) 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值： Availablej =Availablej-Requestij

45、; Allocationi,j =Allocationi,j+Requestij; Needi,j =Needi,j-Requestij; (4) 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。 3)安全性算法安全性算法 (1) 设置两个向量： 工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work =Available; Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时

46、先做Finishi =false; 当有足够资源分配给进程时， 再令Finishi =true。 (2) 从进程集合中找到一个能满足下述条件的进程： Finishi=false; Needi,jWorkj； 若找到， 执行步骤(3)， 否则，执行步骤(4)。 (3) 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： Workj =Worki+Allocationi,j; Finishi =true; go to step 2; (4) 如果所有进程的Finishi=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。 4)银行家算法之例银行家算法之例 假定系统中有五个进程P0, P1, P2, P3, P4和三类资源A, B, C，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图 3-15 所示。 图 3-8 T0时刻的资源分配表 (1) T0时刻的安全性： 图 3-9 T0时刻的安全序列 (2) P1请求资源：P1发出请求向量Request1(1，0，2)，系统按银行家算法进行检查： Request1(1, 0, 2)Need1(1, 2, 2) Request1(1, 0, 2)Available1(3, 3, 2) 系统先假定可为P1分配资源，并修改Available, Allocatio