计算机操作系统第三章处理机调度与死锁--课件.ppt

第三章第三章 处理机调度与死锁处理机调度与死锁要解决的三个问题：要解决的三个问题：WHAT：：按什么原则分配按什么原则分配CPU？？ —进程调度算法进程调度算法WHEN：：何时分配何时分配CPU？？ —进程调度的时机进程调度的时机HOW：： 如何分配如何分配CPU？？ —CPU调度过程（进程的上下文切换）调度过程（进程的上下文切换）1PPT课件主要内容主要内容u 处理机调度的层次处理机调度的层次u 调度队列模型和调度准则调度队列模型和调度准则u 调度算法调度算法u 实时调度实时调度u 产生死锁的原因和必要条件产生死锁的原因和必要条件u 预防和避免死锁的办法预防和避免死锁的办法u 死锁的检测与解除死锁的检测与解除2PPT课件3.1 处理机调度的层次处理机调度的层次高级调度高级调度1 作业和作业步作业和作业步Ø 作业作业       不仅包含通常的程序和数据，还应配备一份不仅包含通常的程序和数据，还应配备一份作作业说明书业说明书，系统根据作业说明书对程序的运行进程，系统根据作业说明书对程序的运行进程控制在批处理系统中，是以作业为基本单位从外控制。

在批处理系统中，是以作业为基本单位从外存调入内存存调入内存3PPT课件Ø 作业步作业步    作业运行期间，每个作业都必须经过若干个作业运行期间，每个作业都必须经过若干个相对相对独立、又相互关联的顺序加工步骤独立、又相互关联的顺序加工步骤，才能得到结果，，才能得到结果，把其中的每一个加工步骤称为一个作业步把其中的每一个加工步骤称为一个作业步     1）编译）编译     2）连接装配）连接装配     3）运行）运行Ø 作业流作业流     若干个作业进入系统后，被依次存放在外存上，若干个作业进入系统后，被依次存放在外存上，形成形成输入的作业流输入的作业流；在；在OS的控制下，逐个作业进的控制下，逐个作业进行处理，形成了行处理，形成了处理作业流处理作业流   编译程序对源程序编译程序对源程序进行编译，生成若进行编译，生成若干个目标程序段干个目标程序段将目标程序段将目标程序段装配成可执行装配成可执行的目标程序的目标程序将目标程序读将目标程序读入内存并控制入内存并控制其运行其运行4PPT课件2 作业控制块作业控制块        多道批处理系统中，为每个作业配备一个作业多道批处理系统中，为每个作业配备一个作业控制块（控制块（JCB），它），它是作业在系统中存在的标志是作业在系统中存在的标志。

   作业运行期间，系统按照作业运行期间，系统按照JCB中的信息对作业进行中的信息对作业进行控制           JCB中中保存了系统对作业进行管理和调度所需保存了系统对作业进行管理和调度所需的全部信息的全部信息例如：作业标识、用户名称、用户帐例如：作业标识、用户名称、用户帐户、作业类型、作业状态、调度信息、资源需求、户、作业类型、作业状态、调度信息、资源需求、进入系统时间、开始处理时间、作业完成时间、作进入系统时间、开始处理时间、作业完成时间、作业退出时间、资源使用情况等业退出时间、资源使用情况等           5PPT课件3 作业调度（作业调度（高级调度、长程调度、接纳调度高级调度、长程调度、接纳调度））Ø 定义定义          按照一定的算法，从按照一定的算法，从外存的后备队列外存的后备队列中中选取某些作业调入内存，并为它们创建进程、选取某些作业调入内存，并为它们创建进程、分配必要的资源分配必要的资源Ø 两个决定两个决定   1决定接纳决定接纳多少个多少个作业（多道程序度）作业（多道程序度）   2决定接纳决定接纳哪些哪些作业作业数目过多：数目过多：每个进程可以每个进程可以执行的时间片就越小，单执行的时间片就越小，单个进程的周转时间越长；个进程的周转时间越长；数目过少：数目过少：资源利用率和资源利用率和系统吞吐量下降，应考虑系统吞吐量下降，应考虑调度新的进程进入内存。

调度新的进程进入内存选用何种调度算法：先来先服务、选用何种调度算法：先来先服务、短作业优先、基于作业优先级、响短作业优先、基于作业优先级、响应比高者优先应比高者优先6PPT课件注意注意          批处理系统中，作业是首先进入外存，批处理系统中，作业是首先进入外存，然后经由作业调度分批进入内存；然后经由作业调度分批进入内存；           分时系统及实时系统分时系统及实时系统中，由于对响应时中，由于对响应时间有要求，因此用户输入的命令和数据等间有要求，因此用户输入的命令和数据等是直接进入内存的，是直接进入内存的，无须配置作业调度机无须配置作业调度机制制7PPT课件1 定义定义         决定就绪队列中的哪个进程应获得处理机，然决定就绪队列中的哪个进程应获得处理机，然后由分派程序执行把处理机分配给该进程的具体后由分派程序执行把处理机分配给该进程的具体操作          低级调度是最基本的一种调度，多道批处理、低级调度是最基本的一种调度，多道批处理、分时、实时系统中都必须配置分时、实时系统中都必须配置2 主要功能主要功能Ø 保存当前进程的处理机现场信息保存当前进程的处理机现场信息Ø 按某种算法（优先数算法、轮转法）选择进程按某种算法（优先数算法、轮转法）选择进程Ø 将将CPU分配给该进程，恢复新进程的处理机现场，让分配给该进程，恢复新进程的处理机现场，让其从断点开始执行。

其从断点开始执行低级调度低级调度 （进程调度、短程调度）（进程调度、短程调度）8PPT课件3 进程调度机制进程调度机制     Ø 排队器排队器         将系统中的所有就绪进程按某种方式排成一个或多个队列，方便调度程序寻找Ø 分派器分派器 将选中进程从后备队列移出，将处理机分配给它Ø 上下文切换机制上下文切换机制          两次上下文切换：保存当前进程上下文，装入dispatcher上下文；移出dispatcher上下文，装入新选中进程的上下文9PPT课件4 进程调度方式进程调度方式Ø 非抢占方式非抢占方式          一旦把处理机分配给某进程后，一直让它一旦把处理机分配给某进程后，一直让它运行下去，不能因为时钟中断等原因或由其它运行下去，不能因为时钟中断等原因或由其它进程抢占分配给它的处理机直至该进程完成，进程抢占分配给它的处理机直至该进程完成，或因某事件阻塞，才能重新分配处理机或因某事件阻塞，才能重新分配处理机   优点：优点：实现简单，系统开销小；实现简单，系统开销小；   缺点：缺点：难以满足紧急任务的要求，可能造成难难以满足紧急任务的要求，可能造成难以预料的后果。

实时系统中，不宜采用该方式以预料的后果实时系统中，不宜采用该方式10PPT课件Ø 抢占方式抢占方式          允许调度程序根据某种原则暂停某个正允许调度程序根据某种原则暂停某个正在执行的进程，将已分配给该进程的处理在执行的进程，将已分配给该进程的处理机重新分配给另一进程机重新分配给另一进程   抢占原则：抢占原则：          优先权、短作业优先、时间片优先权、短作业优先、时间片   优点：优点：防止长进程长时间占用防止长进程长时间占用CPU，为大，为大多数进程提供更公平的服务，特别是能满多数进程提供更公平的服务，特别是能满足实时任务的要求足实时任务的要求   缺点：缺点：与非抢占方式相比，开销较大与非抢占方式相比，开销较大11PPT课件          当被挂起的进程重新具备运行条件且内当被挂起的进程重新具备运行条件且内存稍有空闲时，把外存上的那些具备运行条存稍有空闲时，把外存上的那些具备运行条件的进程重新调入内存，并修改其状态为就件的进程重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待进程调度绪状态，挂在就绪队列上等待进程调度          中级调度中级调度12PPT课件3.2  调度队列模型和调度准则调度队列模型和调度准则仅有进程调度的调度队列模型仅有进程调度的调度队列模型仅具有进程调度的调度队列模型仅具有进程调度的调度队列模型时间片完时间片完就就 绪绪 队队 列列阻阻 塞塞 队队 列列CPU交互用户交互用户进程调度进程调度进程完成进程完成等待事件等待事件事事件件发发生生FIFO队列队列13PPT课件具有高级和低级调度的调度队列模型具有高级和低级调度的调度队列模型…… 具有高、低两级调度的调度队列模型具有高、低两级调度的调度队列模型就就 绪绪 队队 列列阻阻 塞塞 队队 列列CPU时间片完时间片完作业作业调度调度进程调度进程调度进程完成进程完成等待事件等待事件1阻阻 塞塞 队队 列列阻阻 塞塞 队队 列列等待事件等待事件2等待事件等待事件n事件事件1发生发生事件事件2发生发生事件事件n发生发生后后 备备 队队 列列优先权队列优先权队列14PPT课件 具有高、低、中三级调度的调度队列模型具有高、低、中三级调度的调度队列模型就就 绪绪 队队 列列绪绪就就、、 挂挂 起起 队队 列列CPU时间片完时间片完作业作业调度调度进程调度进程调度进程完成进程完成事件出现事件出现阻阻 塞塞 队队 列列挂起挂起等待事件等待事件中级中级调度调度事件发生事件发生后后 备备 队队 列列塞塞阻阻、、 挂挂 起起 队队 列列挂起挂起同时具有三级调度的调度队列模型同时具有三级调度的调度队列模型15PPT课件•面向用户的准则面向用户的准则–周转时间短（批处理）周转时间短（批处理）–响应时间快（分时）响应时间快（分时）–截止时间保证（实时）截止时间保证（实时）–优先权准则（优先权准则（all））选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则带权周转时间：作业的周转时间与带权周转时间：作业的周转时间与系统为它提供服务的时间之比系统为它提供服务的时间之比周转时间周转时间——作业被提交给系作业被提交给系统开始，到作业完成为止的这统开始，到作业完成为止的这段时间间隔。

段时间间隔包括：在外存后包括：在外存后备队列等待调度的时间；在内备队列等待调度的时间；在内存就绪队列等待调度的时间；存就绪队列等待调度的时间；在在CPU上执行的时间；等待上执行的时间；等待I/O操作的时间操作的时间响应时间：用户通过键盘提交请求开始，直至系统首次产生响应响应时间：用户通过键盘提交请求开始，直至系统首次产生响应为止包括：请求信息传送到为止包括：请求信息传送到CPU的时间，的时间，CPU处理请求的时间，处理请求的时间，将响应信息回送到终端显示器的时间将响应信息回送到终端显示器的时间16PPT课件•面向系统的准则面向系统的准则–系统吞吐量高系统吞吐量高–处理机利用率好处理机利用率好–各类资源的平衡利用各类资源的平衡利用吞吐量：单位时间内，系统完成的作业数处理机利用率：一般在40%—90%各类资源：内存、外存和外设的平衡利用17PPT课件3.3 调度算法调度算法          根据系统的资源分配策略所规定的根据系统的资源分配策略所规定的资源资源分配算法分配算法u 先来先服务算法先来先服务算法u 短作业优先算法短作业优先算法u 高优先权优先算法高优先权优先算法u 时间片轮转调度算法时间片轮转调度算法18PPT课件先来先服务（先来先服务（FCFS））•主要用于作业调度，也可用于进程调度。

主要用于作业调度，也可用于进程调度•用于作业调度：用于作业调度：–每次从后备作业队列中选择每次从后备作业队列中选择最先进入的作业最先进入的作业，将它们调入内存，，将它们调入内存，为它们分配资源、创建进程，然后挂到就绪进程队列上为它们分配资源、创建进程，然后挂到就绪进程队列上–有利于长作业，而不利于短作业有利于长作业，而不利于短作业•用于进程调度：用于进程调度：–每次从就绪进程队列中选择每次从就绪进程队列中选择最先进入的进程最先进入的进程，为之分配处理机，，为之分配处理机，使之投入运行使之投入运行–直到运行完成进程才会让出处理机直到运行完成进程才会让出处理机--非抢占式非抢占式•性能评价：性能评价：–周转时间周转时间          = 完成时间完成时间 – 到达时间到达时间–带权周转时间带权周转时间   = 周转时间周转时间 / 服务（运行）时间服务（运行）时间19PPT课件先来先服务（先来先服务（FCFS））进程进程编码编码到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间A010111B110011011001C21101102100100D31001022021991.9920PPT课件短作业短作业 / 进程优先进程优先（（SJ/PF））•短作业优先（短作业优先（SJF））–从后备队列中选择从后备队列中选择估计运行时间最短估计运行时间最短的作业，调入内存运行。

的作业，调入内存运行•短进程优先短进程优先（（SPF））–从就绪队列中选出从就绪队列中选出估计运行时间估计运行时间最短的进程，将处理机分配最短的进程，将处理机分配给它，使它立即执行给它，使它立即执行–直到运行完成进程才会让出处理机直到运行完成进程才会让出处理机--非抢占式非抢占式•缺点：缺点：–对长作业不利对长作业不利，有可能长期不被调度；，有可能长期不被调度；–完全完全没考虑作业的紧迫程度没考虑作业的紧迫程度（某些特殊的）；（某些特殊的）；–用户做出的估计时间带有很大的用户做出的估计时间带有很大的主观性主观性21PPT课件短作业 / 进程优先（SJ/PF） 作调 业 度 情 算 况 法进程名ABCDE平均到达时间01234服务时间43524FCFS完成时间47121418周转时间461011149带权周转时间1225.53.52.8SJ/PF完成时间4918613周转时间4816398带权周转时间12.673.11.52.252.122PPT课件优先级优先级（（FPF））•既能用于作业调度，也可用于进程调度。

既能用于作业调度，也可用于进程调度•调度思想调度思想：：–从队列中选择优先权最高的调度单元，从队列中选择优先权最高的调度单元，装入内存或分配给处理机装入内存或分配给处理机–对进程调度而言，有对进程调度而言，有非抢占式非抢占式和和抢占式抢占式两种把处理机分配给就绪队列中优先权把处理机分配给就绪队列中优先权最高的进程，直至完成或因某种原最高的进程，直至完成或因某种原因阻塞，才让出处理机主要用于因阻塞，才让出处理机主要用于批处理系统批处理系统中中同样是把同样是把CPU分给优先权最高的进程，但在该进程分给优先权最高的进程，但在该进程执行过程中，如有优先级更高的进程到来，则立即执行过程中，如有优先级更高的进程到来，则立即停止当前进程的执行，将停止当前进程的执行，将CPU分配给新到的优先级分配给新到的优先级最高的进程常用于要求比较严格的最高的进程常用于要求比较严格的实时系统实时系统中23PPT课件•优先权优先权(0-255)–静态静态优先权、优先权、动态动态优先权优先权在创建进程时即确定，且在进优先权在创建进程时即确定，且在进程的整个运行期间保持不变程的整个运行期间保持不变创建进程时所赋予的优先权，随进程的推进创建进程时所赋予的优先权，随进程的推进或等待时间的增加而改变或等待时间的增加而改变例如规定：例如规定：就绪队列中的进程，随就绪队列中的进程，随等待时间的延长等待时间的延长，优先，优先权以速率权以速率α增长增长；；执行中的进程，随执行中的进程，随执行时间的延长执行时间的延长，优先权以，优先权以速率速率β下降下降。

24PPT课件•高响应比高响应比优先调度算法优先调度算法–动态优先权，与作业等待时间相关动态优先权，与作业等待时间相关     优先权优先权=响应比（响应比（Rp））                =（等待时间（等待时间+要求服务时间）要求服务时间）/要求服务时间要求服务时间                = 响应时间响应时间/要求服务时间要求服务时间   分析：分析：Ø 等待时间相同，等待时间相同，要求服务时间越短要求服务时间越短，优先级越高有利于短作业优先级越高有利于短作业Ø 要求服务时间相同，要求服务时间相同，等待时间越长等待时间越长，优先级越高即，优先级越高即FCFSØ 对于长作业，优先级对于长作业，优先级随等待时间的延长而升高随等待时间的延长而升高，终能获得处理机终能获得处理机因此，该算法是一种折衷算法因此，该算法是一种折衷算法缺点：频繁计算响应比，增加了系统开销缺点：频繁计算响应比，增加了系统开销25PPT课件时间片轮转时间片轮转•特别适用于特别适用于分时系统分时系统的调度算法的调度算法•实现方法：实现方法：–由计时器发出时钟中断，引起一次轮转调度由计时器发出时钟中断，引起一次轮转调度。

26PPT课件基本思想：基本思想：基于时钟的剥夺基于时钟的剥夺　　　　　　以一定的时间间隔周期性产生一个　　以一定的时间间隔周期性产生一个时时钟中断钟中断，当中断发生时，当前正在运行的，当中断发生时，当前正在运行的进程被置于就绪队列末尾，然后进程被置于就绪队列末尾，然后基于基于FCFS选择选择下一个就绪进程运行下一个就绪进程运行　　保证就绪队列中的所有进程在给定的　　保证就绪队列中的所有进程在给定的时间内都能获得时间内都能获得一时间片（一时间片（time slice））的的处理机执行时间处理机执行时间27PPT课件执行过程执行过程1将系统中所有的就绪进程按照将系统中所有的就绪进程按照FCFS原则，原则，排成一个排成一个队列2每次调度时将每次调度时将CPU分派给分派给队首进程队首进程，让其，让其执行一个时间片执行一个时间片时间片的时间片的长度长度从几个从几个ms到几百到几百ms3在一个时间片结束时，发生在一个时间片结束时，发生时钟中断时钟中断4调度程序据此调度程序据此暂停当前进程的执行，暂停当前进程的执行，将其将其送到送到就绪队列的末尾，就绪队列的末尾，并通过上下文切换并通过上下文切换执行当前的队首进程。

执行当前的队首进程5进程可以进程可以未使用完一个时间片未使用完一个时间片，就，就出让出让CPU28PPT课件ABCD…FCPU完成完成超时超时阻塞阻塞时间片轮转调度算法示意图时间片轮转调度算法示意图29PPT课件 最佳时间片的确定最佳时间片的确定　　　　　　时时间间片片的的选选取取是是实实现现各各种种调调度度算算法法的的关关键键之之处处，，而而时时间间片片的的选选定定通通常常应应考考虑虑终终端端数数目目，，处处理理机机能能力力、、各各终终端端任任务务的的急迫程度、外存传输速度等方面的因素急迫程度、外存传输速度等方面的因素 ①①当当时时间间片片很很大大时时，，大大到到一一个个进进程程足足以以完完成成其其全全部部运运行行工作所需的时间，此时轮转调度模式退化为工作所需的时间，此时轮转调度模式退化为FCFSFCFS模式 ②②当当时时间间片片非非常常小小时时，，调调度度程程序序剥剥夺夺处处理理机机的的次次数数增增多多，，这这将将加加重重了了系系统统开开销销，，系系统统性性能能降降低低，，大大多多数数时时间间都都消消耗耗在在处理机的转换上处理机的转换上。

30PPT课件多级反馈队列调度算法多级反馈队列调度算法 •以上介绍的算法，都存在一定的局限性以上介绍的算法，都存在一定的局限性•现在主流的操作系统，如现在主流的操作系统，如UNIX、、Windows NT、、Linux等，都使用一种综合性的调度算法等，都使用一种综合性的调度算法——多级多级反馈队列调度算法反馈队列调度算法•该算法综合了上述三种算法以及多队列调度算法该算法综合了上述三种算法以及多队列调度算法的思想和优点，的思想和优点，总体调度性能优越总体调度性能优越，适于各种类，适于各种类型的作业，但其实现也比较型的作业，但其实现也比较复杂复杂 31PPT课件算法的基本思想是算法的基本思想是： •首首先先：：系系统统按按进进程程优优先先级级设设置置了了多多级级（（比比如如n级级，，n≥2））就就绪绪进进程队列程队列，从第一级队列到最后一级队列，优先级越来越低从第一级队列到最后一级队列，优先级越来越低•其其次次：：每每一一级级就就绪绪队队列列对对应应一一个个不不同同的的时时间间片片优优先先权权越越高高的的队列，进程的时间片越小队列，进程的时间片越小•再再次次：：当当一一个个新新进进程程进进入入内内存存后后，，首首先先被被放放到到第第一一级级队队列列的的队队尾尾。

按按照照FCFS原原则则排排队队等等待待调调度度当当轮轮到到该该进进程程执执行行时时，，如如能能在在时时间间片片内内完完成成，，便便可可准准备备撤撤离离系系统统；；如如果果在在时时间间片片内内未未完完成成，，调调度度程程序序便便将将该该进进程程转转入入第第二二队队列列的的末末尾尾，，再再依依次次按按照照FCFS原则等待调度原则等待调度32PPT课件•最后最后：仅当第一级队列为空时，才调度第二级队列中：仅当第一级队列为空时，才调度第二级队列中的进程；如此下去，的进程；如此下去，仅当前面的仅当前面的n-1级队列全部为空时，级队列全部为空时，才去调度最后第才去调度最后第n级队列中的进程级队列中的进程如果处理机正在第如果处理机正在第i队列中为某进程服务时，又有新的进程进入优先权高队列中为某进程服务时，又有新的进程进入优先权高的队列（第的队列（第1～～(i-1)中任何一队列），则系统中任何一队列），则系统抢占正在抢占正在运行的进程的处理机运行的进程的处理机，由调度程序把正在运行的进程，由调度程序把正在运行的进程放回到刚才所在第放回到刚才所在第i队列的队尾，重新进行处理机调度队列的队尾，重新进行处理机调度。

 33PPT课件•多级反馈队列调度算法的性能–能较好地满足各种类型用户（进程）的需要–终端（交互）型作业用户–短批处理作业用户–长批处理作业用户…… 多级反馈队列调度算法示意图多级反馈队列调度算法示意图CPU时间时间片完片完进程进程调度调度进程完成进程完成就 绪 队 列 一就 绪 队 列 二就 绪 队 列 三就 绪 队 列 n时间时间片完片完时间时间片完片完34PPT课件习题习题          设有两个设有两个优先级相同优先级相同的进程的进程P、、Q，各自运，各自运行的程序如下行的程序如下进程进程PP1 Y：：=1；；P2 Y：：=Y+Z；；P3 V（（S1）；）；P4 Z：：=Y+3；；P5 P（（S2）；）；P6 Y：：=Z+Y；；进程进程1 X：：=1；；Q2 X：：=X+1；；Q3 P（（S1）；）；Q4 X：：=X+Y；；Q5 V（（S2）；）；Q6 Z：：=X+Z；；35PPT课件          其中，其中，S1、、S2为信号量，初值为为信号量，初值为0，已知，已知Z=2，若调度程序执行的策略为，若调度程序执行的策略为FIFO，试问执，试问执行序列和运行结果是什么？行序列和运行结果是什么？X=5，，Y=14，，Z=1136PPT课件3.5 产生死锁的原因和必要条件u　产生死锁的原因u　产生死锁的必要条件u　处理死锁的基本方法37PPT课件死锁死锁p　　多个进程在运行过程中因争夺资源而多个进程在运行过程中因争夺资源而造成的一种造成的一种僵局僵局，当进程处于这种僵持，当进程处于这种僵持状态时，若无外力作用，它们都将无法状态时，若无外力作用，它们都将无法向前推进。

向前推进p　　一组进程中，每个进程都一组进程中，每个进程都无限等待无限等待被被该组进程中另一进程所占有的资源，因该组进程中另一进程所占有的资源，因而永远无法得到资源，这种现象称为而永远无法得到资源，这种现象称为进进程死锁程死锁，这一组进程就称为，这一组进程就称为死锁进程死锁进程38PPT课件3.5.1 产生死锁的产生死锁的原因原因１资源不足１资源不足导致的资源竞争：导致的资源竞争：多个进程所多个进程所共享的资源不足，引起它们对资源的竞共享的资源不足，引起它们对资源的竞争而产生死锁争而产生死锁２并发执行２并发执行的顺序不当：进程运行过程中，的顺序不当：进程运行过程中，请求和释放资源的顺序不当，而导致进请求和释放资源的顺序不当，而导致进程死锁程死锁. 如如P,V操作的顺序不当操作的顺序不当39PPT课件死锁死锁现象举例现象举例40PPT课件一　竞争资源引起死锁一　竞争资源引起死锁 •1．资源的分类：可剥夺和非剥夺性资源．资源的分类：可剥夺和非剥夺性资源• •可剥夺性资源可剥夺性资源可剥夺性资源可剥夺性资源：： CPU和主存和主存• 例如：优先权高的程可以剥夺低优先权进程的处理机例如：优先权高的程可以剥夺低优先权进程的处理机。

•　　　　　　存存储储器器管管理理程程序序把把进进程程从从一一个个存存储储区区移移至至另另外外一一个个存存储储区区，，甚甚至至　　　　将一进程从内存调出到外存上将一进程从内存调出到外存上• •不可剥夺性资源不可剥夺性资源不可剥夺性资源不可剥夺性资源：磁带机、打印机等：磁带机、打印机等•          当系统把这类资源分配给某进程后，再不能强行收回，只能在进当系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自动释放程用完后自动释放 41PPT课件　　　　两个进程分别准备打印一个非常大的磁带两个进程分别准备打印一个非常大的磁带文件（文件（双方都拥有部分资源，同时在请求对方双方都拥有部分资源，同时在请求对方已占有的资源已占有的资源打印机R1磁带机R2P1P22．竞争非剥夺性资源．竞争非剥夺性资源42PPT课件3．竞争临时性资源．竞争临时性资源永永久久性性资资源源：：打打印印机机资资源源属属于于可可顺顺序序重重复复使使用的资源用的资源临临时时性性资资源源：：由由一一个个进进程程产产生生，，被被另另一一个个进进程程使使用用一一短短暂暂时时间间后后便便无无用用的的资资源源  例例如如进程通信时的消息。

进程通信时的消息  43PPT课件R1P1R2P2S1P1S2P3S3P244PPT课件二　进程推进顺序不当引起死锁二　进程推进顺序不当引起死锁             资源资源少未必一定产生死锁少未必一定产生死锁　　　就如同两个人过独木桥，如果两个人都要先过，在独木　　　就如同两个人过独木桥，如果两个人都要先过，在独木桥上僵持不肯后退，必然会因竞争资源产生死锁；但是，如桥上僵持不肯后退，必然会因竞争资源产生死锁；但是，如果两个人上桥前先看一看有无对方的人在桥上，当无对方的果两个人上桥前先看一看有无对方的人在桥上，当无对方的人在桥上时自己才上桥，那么问题就解决了人在桥上时自己才上桥，那么问题就解决了       　所以，如果程序设计得不合理，造成　所以，如果程序设计得不合理，造成进程推进的顺序不进程推进的顺序不当当，也会出现死锁也会出现死锁 45PPT课件•如果执行序列为如果执行序列为:P0、、P1、、q0、、q1、、P2、、q2，则发生死锁，则发生死锁46PPT课件p1Req(R1) p1Req(R2)p1ReL(R1)p1ReL(R2)p2Req(R2)p2Req(R1)p2ReL(R2)p2ReL(R1)p1p247PPT课件思考题：（北大思考题：（北大95研研））•一一个个OS有有20个个进进程程，，竞竞争争使使用用65个个同同类类资资源源，，申申请请方方式式是是逐逐个个进进行行的的，，一一旦旦某某个个进进程程获获得得它它所所需需要要的全部资源，则立即归还所有资源。

的全部资源，则立即归还所有资源•每个进程最多使用每个进程最多使用三个三个资源•若若仅仅考考虑虑这这类类资资源源，，该该系系统统有有无无可可能能产产生生死死锁锁，，为为什么？什么？48PPT课件•答：答：不可能不可能•因因为为死死锁锁产产生生的的原原因因有有两两点点：：系系统统资资源源不不足足或或推推进进顺顺序序不不当当，，在在本本题题中中，，进进程程所所需需的的最最大大资资源源数数为为60，，而而系系统统共共有有该该类类资资源源65个，其资源数已足够系统内各进程使用个，其资源数已足够系统内各进程使用49PPT课件•互斥条件互斥条件–指进程对所分配到的资源进行指进程对所分配到的资源进行排它性使用排它性使用, 即在即在一段时间内某资源只能由一个进程占有如果一段时间内某资源只能由一个进程占有如果此时还有其它进程申请该资源此时还有其它进程申请该资源,则它只能阻塞则它只能阻塞, 直至占有该资源的进程释放直至占有该资源的进程释放•占有且等待（请求和保持条件）占有且等待（请求和保持条件）–进程已经进程已经保持了至少一个资源保持了至少一个资源, 但又但又提出了新的提出了新的资源要求资源要求, 而该资源又已被其它进程占有而该资源又已被其它进程占有, 此时此时请求进程阻塞请求进程阻塞, 但又对已经获得的其它资源保但又对已经获得的其它资源保持不放。

持不放3.5.2 产生死锁的产生死锁的必要条件必要条件50PPT课件•非抢占（非剥夺）条件非抢占（非剥夺）条件–进程已获得的资源进程已获得的资源, 在未使用完之前在未使用完之前, 不能被剥不能被剥夺夺, 只能在使用完时由自己释放只能在使用完时由自己释放•循环等待条件循环等待条件–在发生死锁时在发生死锁时, 必然存在一个必然存在一个进程进程-资源的封闭资源的封闭的环形链的环形链即进程集合即进程集合{P0, P1, P2, …, Pn}中的中的P0正在等待一个正在等待一个P1占用的资源占用的资源; P1正在等待正在等待P2占用的资源占用的资源, ……, Pn正在等待已被正在等待已被P0占用的资占用的资源源.51PPT课件  ①①  死死锁的的预防；防；  ②②  死死锁的避免；的避免；③③  死死锁的的检测和解除；和解除；④④  鸵鸟算法算法          当死锁在计算机中很少出现时，比如说每五年或更当死锁在计算机中很少出现时，比如说每五年或更长时间才出现一次时，人们就不必花费更多的精力去长时间才出现一次时，人们就不必花费更多的精力去解决它，而是采用类似鸵鸟一样的办法忽略它解决它，而是采用类似鸵鸟一样的办法忽略它。

3.5.3 处理死锁的基本方法处理死锁的基本方法52PPT课件预防死锁预防死锁•　　通过通过设置某些限制条件设置某些限制条件，破坏产生，破坏产生死锁的４个必要条件中的一个或几个死锁的４个必要条件中的一个或几个条件，来预防发生死锁条件，来预防发生死锁53PPT课件避免死锁避免死锁•在资源的动态分配过程中，用某种在资源的动态分配过程中，用某种方法方法防止系统进入不安全状态防止系统进入不安全状态，从，从而避免发生死锁而避免发生死锁54PPT课件预防死锁与避免死锁的预防死锁与避免死锁的差别差别•　　预防死锁所施加的限制条件比较预防死锁所施加的限制条件比较严严格格，往往会限制进程的并发执行，往往会限制进程的并发执行•　避免死锁所施加的限制条件比较　避免死锁所施加的限制条件比较宽宽松松，给进程的并发执行提供了较好的，给进程的并发执行提供了较好的环境55PPT课件检测死锁检测死锁•事先并不采取任何限制性措施，允事先并不采取任何限制性措施，允许系统在运行过程中发生死锁但许系统在运行过程中发生死锁但系统的系统的检测机构应能及时地检测出检测机构应能及时地检测出死锁的发生死锁的发生，并精确地确定与死锁，并精确地确定与死锁有关的进程和资源。

有关的进程和资源56PPT课件解除死锁解除死锁•　与死锁的检测措施配合使用　与死锁的检测措施配合使用•　当检测到死锁发生时，应　当检测到死锁发生时，应能够将进程从能够将进程从死锁状态解脱出来死锁状态解脱出来•　常用的方法是撤消或挂起一切进程，以　常用的方法是撤消或挂起一切进程，以便回收部分资源，再将这些资源分配给被便回收部分资源，再将这些资源分配给被阻塞的进程，使之能继续运行阻塞的进程，使之能继续运行57PPT课件3.6 预防和避免死锁的方法u　死锁的预防u　死锁的避免　　　１系统安全状态　　　２利用银行家算法避免死锁58PPT课件3.6.1 死锁的预防死锁的预防•保证互斥条件保证互斥条件–由设备（非共享资源）的固有特性所决定由设备（非共享资源）的固有特性所决定,不能不能被破坏被破坏, 应加以保证如打印机应加以保证如打印机59PPT课件摒弃摒弃“请求和保持请求和保持”条件条件u采用采用静态资源分配法静态资源分配法u　　系统规定每一个进程在开始运行前，都必须系统规定每一个进程在开始运行前，都必须一次性地一次性地申请申请其在整个运行过程所需的其在整个运行过程所需的全部资源全部资源u　　若系统有足够的资源，便把进程想要的全部　　若系统有足够的资源，便把进程想要的全部资源一次性地分配给它；若不能全部满足进程的资源一次性地分配给它；若不能全部满足进程的资源请求，则一个资源也不分给它。

资源请求，则一个资源也不分给它u　　因此，进程在运行过程中就不会再提出资源　　因此，进程在运行过程中就不会再提出资源请求，从而破坏了请求，从而破坏了““请求和保持请求和保持”” 条件 60PPT课件优点：优点：简单、安全、易实现简单、安全、易实现缺点：缺点： （（1）资源被严重浪费）资源被严重浪费（因为一个进程一次（因为一个进程一次获得其所需的全部资源并且独占，其中有可获得其所需的全部资源并且独占，其中有可能有些资源很少使用，严重恶化了资源利用能有些资源很少使用，严重恶化了资源利用率） （（2）进程延迟运行进程延迟运行当且仅当进程获得（当且仅当进程获得其所需的全部资源后，才能开始运行，但有其所需的全部资源后，才能开始运行，但有可能有些资源长期被其他进程占用，致使需可能有些资源长期被其他进程占用，致使需要该资源的进程迟迟不能运行要该资源的进程迟迟不能运行）） 61PPT课件摒弃摒弃““不可剥夺条件不可剥夺条件””Ø进程逐个提出对资源的请求进程逐个提出对资源的请求即：一个已经保持即：一个已经保持了某些资源的进程，当它再提出新的资源要求而了某些资源的进程，当它再提出新的资源要求而不能立即得到满足时，必须释放它已经保持的所不能立即得到满足时，必须释放它已经保持的所有资源，待以后再需要时再重新申请。

有资源，待以后再需要时再重新申请 Ø实现复杂、代价大实现复杂、代价大, 反复申请反复申请/释放资源释放资源, 系统开销系统开销大大, 降低系统吞吐量降低系统吞吐量 62PPT课件摒弃摒弃““循环等待条件循环等待条件”” （有序资源使用法）（有序资源使用法）v　　系统中的所有资源按类型都被赋予一个　　系统中的所有资源按类型都被赋予一个唯一的编号唯一的编号，每个进程只能按编号的，每个进程只能按编号的升序升序申申请资源v对同一个进程而言，它一旦申请了一个编号对同一个进程而言，它一旦申请了一个编号为为i的资源，就的资源，就不允许不允许再申请编号再申请编号比比i小小的资的资源了，因此，破坏了循环等待条件源了，因此，破坏了循环等待条件63PPT课件v优优点点：：安安全全，，资资源源利利用用率率比比静静态态资资源源分分配配法有所提高法有所提高v缺点：实现较困难，因为难给出合适的资缺点：实现较困难，因为难给出合适的资源编号，不便于系统增添新设备，不便于源编号，不便于系统增添新设备，不便于用户编程，且仍有一定的资源浪费现象用户编程，且仍有一定的资源浪费现象64PPT课件3.6.2 死锁的避免死锁的避免•　　　　死死锁锁的的避避免免是是这这样样一一种种对对付付死死锁锁的的办办法法：：系系统统在在运运行行过过程程中中采采取取动动态态的的资资源源分分配配策策略略，，保保证证系系统统不不进进入入可可能能导导致致系系统统陷陷入入死死锁锁状状态态的所谓不安全状态，以避免死锁发生。

的所谓不安全状态，以避免死锁发生• 65PPT课件•　　死锁的避免与死锁预防策略不同：它　　死锁的避免与死锁预防策略不同：它不对进程申请资源加任何限制，而是不对进程申请资源加任何限制，而是对进对进程提出的每一次资源请求进行动态检查程提出的每一次资源请求进行动态检查，，并根据检查结果决定是否分配资源以满足并根据检查结果决定是否分配资源以满足进程的请求由于采用了动态的资源分配进程的请求由于采用了动态的资源分配策略，所以资源利用率比死锁的防止办法策略，所以资源利用率比死锁的防止办法高 66PPT课件一　系统安全状态一　系统安全状态１　安全状态１　安全状态　　　若在某一时刻，　　　若在某一时刻，系统中存在某种进程序列系统中存在某种进程序列，如，如，如果系统按此序列为每个进程分配，如果系统按此序列为每个进程分配其所需的资源，直至最大需求，每个进程均可顺利其所需的资源，直至最大需求，每个进程均可顺利完成　　　称此时系统的状态为　　　称此时系统的状态为安全状态安全状态，称这样的一个，称这样的一个进程序列进程序列为为安全序列安全序列 67PPT课件p　　安全序列的　　安全序列的实质是实质是：序列中的每一个：序列中的每一个进程进程Pi（（i=1,2,…,n）到以后运行完成尚需）到以后运行完成尚需要的资源量要的资源量不超过不超过系统当前系统当前剩余剩余的资源量的资源量与所有在序列中与所有在序列中排在它前面排在它前面的进程当前所的进程当前所占有的占有的资源量之和资源量之和。

 68PPT课件p　不安全状态不安全状态　　若在某一时刻，系统中若在某一时刻，系统中不存在一个安全不存在一个安全序列序列，则称系统处于不安全状态则称系统处于不安全状态p　安全状态与死锁的关系　安全状态与死锁的关系l只要系统处于安全状态只要系统处于安全状态, 必定不会进入死锁状态；必定不会进入死锁状态；死锁状态是不安全状态死锁状态是不安全状态l不安全状态不一定是死锁状态（不安全状态可不安全状态不一定是死锁状态（不安全状态可能导致死锁）；能导致死锁）； 69PPT课件２安全状态实例２安全状态实例例：假定系统有例：假定系统有三个进程三个进程P1、、P2、、P3，共有，共有12台磁带机台磁带机进程P1总共要求总共要求10台磁带机台磁带机，，P2和和P3分别要求分别要求4台和九台设台和九台设在在T0时刻，进程时刻，进程P1、、P2和和P3已经获得已经获得5台、台、2台和台和2台，还有台，还有3台台空闲没有分配空闲没有分配进程进程最大需求最大需求已分配已分配可用可用P11053P2P34229T0时刻系统时安全的时刻系统时安全的这时存在一个安全序列这时存在一个安全序列70PPT课件注意：注意： ü（（1）系统在某一时刻的安全状态）系统在某一时刻的安全状态可能不唯一可能不唯一，但这不影响，但这不影响对系统安全性的判断。

对系统安全性的判断ü（（2）安全状态是非死锁状态，而不安全状态并不一定是死）安全状态是非死锁状态，而不安全状态并不一定是死锁状态即系统处于安全状态一定可以避免死锁，而系统锁状态即系统处于安全状态一定可以避免死锁，而系统处于不安全状态则仅仅可能进入死锁状态处于不安全状态则仅仅可能进入死锁状态 安全状态安全状态不安全状态不安全状态死锁状态死锁状态71PPT课件二　利用银行家算法避免死锁二　利用银行家算法避免死锁•银行家算法是最有代表性的避免死锁算法，是银行家算法是最有代表性的避免死锁算法，是Dijkstra提提出的其模型基于一个小城镇的银行家，他向一群客户分其模型基于一个小城镇的银行家，他向一群客户分别承诺了一定金额的贷款，而他知道所有客户不可能同时别承诺了一定金额的贷款，而他知道所有客户不可能同时都需要最大的贷款额都需要最大的贷款额•我们可将客户比作进程，银行家比作操作系统银行家算我们可将客户比作进程，银行家比作操作系统银行家算法就是对每一个客户的请求进行检查，检查如果满足它是法就是对每一个客户的请求进行检查，检查如果满足它是否会引起不安全状态假如是，那么不满足该请求；否，否会引起不安全状态。

假如是，那么不满足该请求；否，那么便满足那么便满足72PPT课件银行家算法的实质就是 :•要设法要设法保证系统动态分配资源后不进入不保证系统动态分配资源后不进入不安全状态安全状态，以避免可能产生的死锁以避免可能产生的死锁•即：每当进程提出资源请求且系统的资源即：每当进程提出资源请求且系统的资源能够满足该请求时，系统将能够满足该请求时，系统将判断如果满足判断如果满足此次资源请求系统状态是否安全此次资源请求系统状态是否安全，如果判，如果判断结果为安全，则给该进程分配资源，否断结果为安全，则给该进程分配资源，否则不分配资源，申请资源的进程将阻塞则不分配资源，申请资源的进程将阻塞 73PPT课件v银行家算法的执行有个银行家算法的执行有个前提条件前提条件，即要求进程，即要求进程预先提出自己的最大资源请求，并且假设系统预先提出自己的最大资源请求，并且假设系统拥有固定的资源总量拥有固定的资源总量v银行家算法中所用的主要的数据结构如下银行家算法中所用的主要的数据结构如下：： v(1)可利用资源向量可利用资源向量Available    （（剩剩余余或或可可用用资资源源量量）），，记记录录系系统统中中各各类类资资源源的的当当前前可可利利用用数数目目。

如如果果Available[j]=k，， 表表示示系系统统中中现现有有Rj类资源类资源k个74PPT课件  (2) 最大需求矩阵最大需求矩阵Max 每个进程对各类资源的最大需求量每个进程对各类资源的最大需求量Max[i,j]  (3)Allocation      已已为为每每个个进进程程分分配配的的数数量量或或者者说说每每个个进进程程对对各各类类资资源当前的占有量源当前的占有量Allocation[i,j]  (4)需求矩阵需求矩阵Need        某某进程对各类资源尚需要的数目进程对各类资源尚需要的数目       Need[i,j]=Max[i,j]－－Allocation[i,j] (5)请求向量请求向量Request Requesti记记录录进进程程Pi当当前前对对各各类类资资源源的的申申请请量量，，是是银银行家算法的入口参数行家算法的入口参数  75PPT课件当当Pi发出资源请求后，系统按下述步骤进行检查：发出资源请求后，系统按下述步骤进行检查：1.如果如果Requesti［［j］］ > Need[i,j],则出错则出错2.如果如果Requesti［［j］］ > >Available[i,j],则则Pi 阻塞阻塞；； 3.系系统统试试探探把把要要求求的的资资源源分分配配给给进进程程Pi，，并并修修改改下下面面数数据据结结构构中的数值：中的数值：Available[j]=Available[j]- Requesti［［j］］;       Allocation[i,j]=Allocation[i,j]+ Requesti［［j］］  Need[i,j] = Need[i,j]- Requesti［［j］］ ;4. 系统执行安全性算法，检查此次资源分配后，系统是否处系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。

若安全，正式将资源分配给进程于安全状态若安全，正式将资源分配给进程Pi，以完成，以完成本次分配；否则，将试探分配作废，恢复原来的资源分配本次分配；否则，将试探分配作废，恢复原来的资源分配状态，让进程状态，让进程Pi等待 76PPT课件1.1.设置两个向量设置两个向量 ①①工作向量工作向量Work.Work. 表表示示系系统统可可提提供供给给进进程程继继续续运运行行所所需需要要的的各各类类资资源源的的数数目，开始时目，开始时，，Work:=AvailableWork:=Available ②Finish.②Finish. 它它表表示示系系统统是是否否有有足足够够的的资资源源分分配配给给进进程程，，使使之之运运行行完完成成开开始始时时先先做做Finish[i]:=falseFinish[i]:=false；；当当有有足足够够的的资资源源分分配配给进程给进程时，令时，令Finish[i]:=true.Finish[i]:=true.77PPT课件执行过程的描述：执行过程的描述：(1)初始化：初始化：work=work=availableavailable；；finishfinish［［i i］］=false=false；；(2)若按进程编号顺序找到了一个可加入安全序列的进程若按进程编号顺序找到了一个可加入安全序列的进程 即：满足条件即：满足条件finishfinish［［i i］］=false=false且且 need[i,j]need[i,j]≤work[j≤work[j] ]的进程的进程P Pi i 则则①①假设该进程不久将完成任务归还资源，置假设该进程不久将完成任务归还资源，置 work[j]=work[j]+allocation[i,jwork[j]=work[j]+allocation[i,jwork[j]=work[j]+allocation[i,jwork[j]=work[j]+allocation[i,j] ] ] ] finish[i finish[i finish[i finish[i]=true]=true]=true]=true ② ②重复执行这一步；重复执行这一步；(3)若所有进程的可完成标志若所有进程的可完成标志finish[ifinish[i] ]为真，则为真，则返回逻辑真值返回逻辑真值 （表示系统处于安全状态）；（表示系统处于安全状态）；(4)否则，否则，返回逻辑假值返回逻辑假值（表示不安全）；（表示不安全）； 78PPT课件可以看出：可以看出：•银行家算法从避免死锁的角度上说是银行家算法从避免死锁的角度上说是非常有效非常有效的的•但是，从某种意义上说，它但是，从某种意义上说，它缺乏实用价值缺乏实用价值，因为很少有进，因为很少有进程能够在运行前就知道其所需资源的最大值，而且进程数程能够在运行前就知道其所需资源的最大值，而且进程数也不是固定的，往往在不断地变化（如新用户登录或退出）也不是固定的，往往在不断地变化（如新用户登录或退出），况且原本可用的资源也可能突然间变成不可用（如磁带，况且原本可用的资源也可能突然间变成不可用（如磁带机可能坏掉）。

机可能坏掉）•因此，在实际中，如果有，也只有因此，在实际中，如果有，也只有极少的系统极少的系统使用银行家使用银行家算法来避免死锁算法来避免死锁 79PPT课件银行家算法之例银行家算法之例•假定系统中有四个进程假定系统中有四个进程{P1、、P2、、P3、、P4}和三种类型的资和三种类型的资源源{R1，，R2，，R3}，资源的数量分别为，资源的数量分别为9、、3、、6，在，在T0时刻时刻的资源分配情况如的资源分配情况如图图:资源情况资源情况进程进程MaxR1 R2 R3AllocationR1 R2 R3NeedR1 R2 R3AvailableR1 R2 R3 P1 3 2 2 1 0 0 2 2 2 1 1 2 P2 6 1 3 5 1 1 1 0 2 P3 3 1 4 2 1 1 1 0 3 P4 4 2 2 0 0 2 4 2 0T0时刻时刻是否安是否安全？全？80PPT课件资源情况资源情况进程进程MaxR1 R2 R3AllocationR1 R2 R3NeedR1 R2 R3AvailableR1 R2 R3 P1 3 2 2 1 0 0 2 2 2 1 1 2 P2 6 1 3 5 1 1 1 0 2 P3 3 1 4 2 1 1 1 0 3 P4 4 2 2 0 0 2 4 2 0资源情况资源情况进程进程WorkR1 R2 R3NeedR1 R2 R3AllocaR1 R2 R3Work’R1 R2 R3 P2 1 1 2 1 0 2 5 1 1 6 2 3 P1 6 2 3 2 2 2 1 0 0 7 2 3 P3 7 2 3 1 0 3 2 1 1 9 3 4 P4 9 3 4 4 2 0 0 0 2 9 3 681PPT课件P2发出请求向量发出请求向量request2（（1,0,1）），，系统按银行家算法进行检查：系统按银行家算法进行检查：①①requestrequest2 2（（1,0,11,0,1））≤ ≤ needneed2 2（（1,0,21,0,2）；）；②②requestrequest2 2（（1,0,11,0,1））≤ ≤ availableavailable（（1,1,21,1,2）；）；③③系统先假定可为系统先假定可为P2P2分配资源，并修改分配资源，并修改availableavailable、、allocationallocation2 2和和needneed2 2向量向量  资源情况资源情况进程进程MaxR1 R2 R3AllocationR1 R2 R3NeedR1 R2 R3AvailableR1 R2 R3 P1 3 2 2 1 0 0 2 2 2 0 1 1 P2 6 1 3 6 1 2 0 0 1 P3 3 1 4 2 1 1 1 0 3 P4 4 2 2 0 0 2 4 2 0表表2-2 为为P2试分配资源后的有关资源数据试分配资源后的有关资源数据 82PPT课件④④再利用安全性检测子算法检查此时系统是否安全。

再利用安全性检测子算法检查此时系统是否安全如表如表2-32-3所示所示 资源资源进程进程WorkR1 R2 R3NeedR1 R2 R3AllocaR1 R2 R3Work’R1 R2 R3 P1 0 1 2 0 0 1 6 1 2 6 2 3 P2 6 2 3 2 2 2 1 0 0 7 2 3 P3 7 2 3 1 0 3 2 1 1 9 3 4 P4 9 3 4 4 2 0 0 0 2 9 3 6FinishTrueTrueTrueTrue83PPT课件例例2.9  某系统有同类互斥资源某系统有同类互斥资源m个，个，供供n个进个进程共享使用如果每个进程最多申请程共享使用。

如果每个进程最多申请x个资源（个资源（1≤x≤m≤x≤m），），证明：证明：当当n(x-1)+1≤m≤m时，系统不会发时，系统不会发生死锁生死锁 84PPT课件•每个进程最多申请每个进程最多申请x个资源，所以最坏情况是每个进程都得个资源，所以最坏情况是每个进程都得到了到了（（x-1））个资源，并且现在均需申请最后一个资源个资源，并且现在均需申请最后一个资源•此时，系统剩余资源此时，系统剩余资源数为数为m-n(x-1)，于是只要系统中至少，于是只要系统中至少还有一个资源可供使用，就可以使还有一个资源可供使用，就可以使这这n个进程中某个进程得个进程中某个进程得到其所需要的全部资源，并能够继续执行到完成，归还资到其所需要的全部资源，并能够继续执行到完成，归还资源可供其他进程使用源可供其他进程使用•因而不会发生死锁因而不会发生死锁•即只要即只要m-n(x-1)≥≥1时，系统就一定不会发生死锁亦即时，系统就一定不会发生死锁亦即当当n(x-1)+1≤m≤m时，系统不会发生死锁时，系统不会发生死锁 证明证明85PPT课件3.6 死锁的检测与解除死锁的检测与解除u　　死锁的检测死锁的检测           １资源分配图１资源分配图　　　２死锁定理　　　２死锁定理            3 死锁检测中的数据结构死锁检测中的数据结构u　死锁的解除　死锁的解除　　　　　　86PPT课件3.6.1 死锁的检测死锁的检测          系统进行资源分配时系统进行资源分配时,若未采取任何限若未采取任何限制措施制措施,则系统必须提供检测和解除死锁的则系统必须提供检测和解除死锁的手段手段,即必须考虑以下两个问题即必须考虑以下两个问题:u  保存有关资源的请求和分配信息保存有关资源的请求和分配信息u  提供一种算法，检测系统是否已经进提供一种算法，检测系统是否已经进入死锁状态入死锁状态 87PPT课件1 资源分配图资源分配图p1p2进程进程资源资源一个单位的该类资源一个单位的该类资源资源请求边资源请求边资源分配边资源分配边88PPT课件2 死锁定理死锁定理•死锁定理死锁定理:•       S为死锁状态的为死锁状态的充分条件充分条件是是:当当且仅当且仅当S状态的资源分配图是状态的资源分配图是不可不可完全简化完全简化的。

的89PPT课件p1p21 找到非孤立不阻塞进程结点找到非孤立不阻塞进程结点       经过一系列化简，如果能够使所有的结点成为经过一系列化简，如果能够使所有的结点成为孤立结点，则称该图是可以完全化简的孤立结点，则称该图是可以完全化简的所有的简化顺序，能够得到相同的不可化简图所有的简化顺序，能够得到相同的不可化简图90PPT课件3 死锁检测中的数据结构死锁检测中的数据结构Work:=available;    L:={Li|allocationi=0 and requesti=0}    for  all Li 不属于不属于 L   do       begin           for all requesti<=work do              begin                  work:=work+allocationi;                  Li并入并入L              end       end若不能把所有若不能把所有Li都都 并入并入L，则存在死锁，则存在死锁91PPT课件 死锁的检测和恢复技术是死锁的检测和恢复技术是指定期启动指定期启动一个软件一个软件检测系统的状态，若发现有死锁检测系统的状态，若发现有死锁存在，则采取措施恢复之。

存在，则采取措施恢复之 由于死锁是系统中的由于死锁是系统中的恶性小概率事件恶性小概率事件，，死锁检测程序的多次执行往往都不会调用死锁检测程序的多次执行往往都不会调用一次死锁解除程序，而这却增加了系统开一次死锁解除程序，而这却增加了系统开销，因此在设计操作系统时需要销，因此在设计操作系统时需要权衡检测权衡检测精度与时间开销精度与时间开销 92PPT课件3.7.2 死锁的解除死锁的解除 常见的死锁解除方法有以下两种常见的死锁解除方法有以下两种： （（1 1）撤消进程法）撤消进程法 撤消全部死锁进程：撤消全部死锁进程： 代价太大，该做法很少用代价太大，该做法很少用 最小代价撤消法：最小代价撤消法： 首先计算死锁进程的首先计算死锁进程的撤消代价撤消代价，然后依次选择，然后依次选择撤消代价最小的进程，逐个撤消死锁进程，回收资撤消代价最小的进程，逐个撤消死锁进程，回收资源给其他进程，直至死锁不复存在源给其他进程，直至死锁不复存在 93PPT课件（（2 2）挂起进程法）挂起进程法 （剥夺资源（剥夺资源））             使用挂起使用挂起/激活机构挂起一些进程，剥夺它们激活机构挂起一些进程，剥夺它们的资源以解除死锁，待条件满足时，再激活进程。

的资源以解除死锁，待条件满足时，再激活进程             目前挂起法比较受到重视目前挂起法比较受到重视 显然，无论哪一种解除死锁的方法，都需要很大显然，无论哪一种解除死锁的方法，都需要很大的开销但是死锁的检测与解除办法不对系统的资源的开销但是死锁的检测与解除办法不对系统的资源分配等加任何限制，因此是对付死锁的诸办法中分配等加任何限制，因此是对付死锁的诸办法中资源资源利用率最高利用率最高的一种办法，在对安全性要求高的大型系的一种办法，在对安全性要求高的大型系统中常用统中常用 94PPT课件习题三习题三95PPT课件•1 某进程被唤醒后某进程被唤醒后,立即投入了立即投入了执行执行,我们说该系统采用了我们说该系统采用了抢先抢先调度方式调度方式,对吗对吗?错误错误96PPT课件2 考虑下列考虑下列资源分配策略：资源分配策略：l     对资源的申请和释放可以在任何时刻进行对资源的申请和释放可以在任何时刻进行l     如果一进程的资源得不到满足，则检查所有如果一进程的资源得不到满足，则检查所有由于等待资源被阻塞的进程由于等待资源被阻塞的进程l     如果它们有申请进程所需要的资源，则将这如果它们有申请进程所需要的资源，则将这些资源取出分配给申请进程。

些资源取出分配给申请进程97PPT课件例如：例如：        考虑一个有考虑一个有3类资源的系统，系统类资源的系统，系统所有可所有可用资源（用资源（4，，2，，2））进程A申请（申请（2，，2，，1），可满足；进程），可满足；进程B请求（请求（1，，0，，1），可），可满足；进程满足；进程A再请求（再请求（0，，0，，1），则被阻塞则被阻塞            此时，此时，若若C请求（请求（2，，0，，0），它可以分到），它可以分到剩余资源（剩余资源（1，，0，，0），并从），并从A已分到的资源已分到的资源中获得一个资源，于是进程中获得一个资源，于是进程A的分配向量变成的分配向量变成（（1，，2，，1），而需求向量变成（），而需求向量变成（1，，0，，1）98PPT课件请问：请问：1 这种分配方式会导致死锁吗？如果会，请举这种分配方式会导致死锁吗？如果会，请举一个例子；如果不会，请说明产生死锁的哪一个例子；如果不会，请说明产生死锁的哪一个条件不成立？一个条件不成立？2 这种分配方式会导致某些进程的无限等待吗这种分配方式会导致某些进程的无限等待吗？为什么？？为什么？99PPT课件答：答：1 该分配方式不会产生死锁，因为它该分配方式不会产生死锁，因为它不满不满足足死锁的第三个必要条件，即死锁的第三个必要条件，即不剥夺条不剥夺条件件。

进程所获得的资源在未使用完毕之进程所获得的资源在未使用完毕之前，可以被其他进程剥夺这样，系统前，可以被其他进程剥夺这样，系统就不会产生死锁就不会产生死锁100PPT课件2          这种方法这种方法会导致某些进程无限期的等待会导致某些进程无限期的等待因为被阻塞的进程的资源可以被剥夺，所以被阻塞的进被阻塞的进程的资源可以被剥夺，所以被阻塞的进程所拥有的资源数量不会因为进程的推进而逐渐增程所拥有的资源数量不会因为进程的推进而逐渐增加这样，随着进程的推进，并不能保证进程一定加这样，随着进程的推进，并不能保证进程一定能获得它所需要的全部资源能获得它所需要的全部资源          例如，本题中的进程例如，本题中的进程A申请（申请（2，，2，，1）后再申）后再申请（请（0，，0，，1）被阻塞此后，进程）被阻塞此后，进程C又剥夺了进程又剥夺了进程A的一个资源，使得进程的一个资源，使得进程A的资源变为（的资源变为（1，，2，，1），），其需求向量为（其需求向量为（1，，0，，1）之后，若再创建的进）之后，若再创建的进程总是只申请第一和第三类资源，程总是只申请第一和第三类资源，总是占有系统所总是占有系统所剩余的第一和第三类资源的全部剩余的第一和第三类资源的全部，且不被阻塞，那，且不被阻塞，那么，进程么，进程A将会无限期的等待。

将会无限期的等待101PPT课件3 一台计算机有一台计算机有8台磁带机它们由台磁带机它们由N个进个进程竞争使用，每个进程可能需要程竞争使用，每个进程可能需要3台磁台磁带机请问带机请问N为多少时，系统没有死锁为多少时，系统没有死锁的危险说明其原因？的危险说明其原因？102PPT课件答：答：       当当N<=3的时候，系统没有死锁的危险的时候，系统没有死锁的危险因为当因为当N=3时，最坏的情况下有两个进程可时，最坏的情况下有两个进程可获得获得3台磁带机，一个进程获得台磁带机，一个进程获得2台磁带机，台磁带机，此时该进程只需要等待另两个进程之一执此时该进程只需要等待另两个进程之一执行完毕，释放其所拥有的磁带机即可，所行完毕，释放其所拥有的磁带机即可，所以不会产生死锁以不会产生死锁          当当N=4时，最坏的情况下每个进程都获时，最坏的情况下每个进程都获得得2台磁带机，此时，没有一个进程可以获台磁带机，此时，没有一个进程可以获得足够的资源执行完毕，所有进程均在等得足够的资源执行完毕，所有进程均在等待其它进程释放资源，形成死锁待其它进程释放资源，形成死锁103PPT课件4 假定某计算机系统有假定某计算机系统有R1设备设备3台，台，R2设备设备4台，台，它们被它们被P1、、P2、、P3、、P4这这4个进程共享，且个进程共享，且已知这已知这4个进程均以下面所示的顺序使用现有个进程均以下面所示的顺序使用现有设备。

设备   申请申请R1   申请申请R2   申请申请R1   释放释放R1   释放释放R2    释放释放R1请问：请问：1）说明系统运行过程中是否有产生死锁的可）说明系统运行过程中是否有产生死锁的可能？为什么能？为什么2）如果有，请举例，并画出该死锁状态的进）如果有，请举例，并画出该死锁状态的进程程-资源图104PPT课件答：答：1）） 本题中，系统有本题中，系统有R1设备设备3台，台，R2设备设备4台系统的系统的4个进程需要使用的资源数为个进程需要使用的资源数为R1设备设备各各2台，台，R2设备各设备各1台因此，台因此，系统资源不足系统资源不足，，满足进程死锁的第一个原因，因此可能会产满足进程死锁的第一个原因，因此可能会产生死锁2）当）当3个进程都执行完第一步，开始执行第二个进程都执行完第一步，开始执行第二步，另一个进程会因没有步，另一个进程会因没有R1资源而阻塞；当资源而阻塞；当3个进程都执行完第二步再执行第三步时，全个进程都执行完第二步再执行第三步时，全部阻塞，系统部阻塞，系统进入死锁进入死锁状态105PPT课件P1P4P3P2106PPT课件5 某系统有某系统有R1、、R2、、R3共共3类资源，在类资源，在T0时刻，时刻，P1、、P2、、P3、、P4这这4个进程对资源的占用和个进程对资源的占用和需求情况如下表，此刻系统的可用资源向量为需求情况如下表，此刻系统的可用资源向量为（（2，，1，，2），问题：），问题：1）将系统中）将系统中各种资源总数各种资源总数和此刻各进程对和此刻各进程对各资各资源的需求数目源的需求数目用向量或矩阵表示出来；用向量或矩阵表示出来；2）如果此时）如果此时P1和和P2均发出资源请求向量均发出资源请求向量request(1，，0，，1)，为了保持系统安全性，应该，为了保持系统安全性，应该如何如何分配资源分配资源给这两个进程？说明你所采用的策略给这两个进程？说明你所采用的策略的原因。

的原因3）如果）如果2）中两个请求立刻得到满足后，系统）中两个请求立刻得到满足后，系统此刻此刻是否处于死锁状态是否处于死锁状态？？107PPT课件                 Maxi demand     Current allocaP1             3   2   2                       1  0   0P2             6   1   3                       4   1   1P3             3   1   4                       2   1   1P4             4   2   2                       0   0   2108PPT课件6 Dijkstra 1995年提出的银行家算法的年提出的银行家算法的主要主要思想思想是什么？它能够用来解决实际中的死是什么？它能够用来解决实际中的死锁问题吗？为什么？锁问题吗？为什么？        109PPT课件          银行家算法代表解决死锁问题的一种策银行家算法代表解决死锁问题的一种策略。

在实施资源分配之前，略在实施资源分配之前，先计算该次分先计算该次分配后摒生的状态是否安全，配后摒生的状态是否安全，即是否存在一即是否存在一种顺序，使得所有的进程都能执行结束种顺序，使得所有的进程都能执行结束若安全则分配，否则拒绝分配若安全则分配，否则拒绝分配          该算法虽然具有很好的理论意义，该算法虽然具有很好的理论意义，但在但在实际系统中却很难使用实际系统中却很难使用因为算法所假设因为算法所假设的条件，如进程预知申请资源的最大数目，的条件，如进程预知申请资源的最大数目，系统中进程数目固定大呢感，在现实环境系统中进程数目固定大呢感，在现实环境中并不成立所以，由不成立的前提导出中并不成立所以，由不成立的前提导出的结果很难说明其正确性的结果很难说明其正确性110PPT课件7 在什么条件下，一个进程的在什么条件下，一个进程的解封解封（即由状（即由状态态Blocked变迁为变迁为 Ready)会会立即引起一个立即引起一个进程的被调度进程的被调度（即由状态（即由状态Ready变迁为变迁为 Running））?          111PPT课件•例如，当例如，当CPU空闲，就绪队列为空空闲，就绪队列为空，那么，那么一个进程由于解除封锁而进入就绪时，就一个进程由于解除封锁而进入就绪时，就会立即引起调度。

会立即引起调度• 又比如，系统实行的又比如，系统实行的剥夺式剥夺式调度策略，当调度策略，当一个比运行进程优先级高的进程进入就绪一个比运行进程优先级高的进程进入就绪队列时，就进行重新调度那么队列时，就进行重新调度那么如果解封如果解封进程的优先级高于当前运行进程的优先级进程的优先级高于当前运行进程的优先级，，显然它的解封势必引起一次重新调度显然它的解封势必引起一次重新调度112PPT课件。