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

1、第三章第三章 处理机调度与死锁处理机调度与死锁要解决的三个问题：要解决的三个问题：WHAT：按什么原则分配按什么原则分配CPU？进程调度算法进程调度算法WHEN：何时分配何时分配CPU？进程调度的时机进程调度的时机HOW：如何分配如何分配CPU？CPU调度过程（进程的上下文切换）调度过程（进程的上下文切换）1PPT课件主要内容主要内容u 处理机调度的层次处理机调度的层次u 调度队列模型和调度准则调度队列模型和调度准则u 调度算法调度算法u 实时调度实时调度u 产生死锁的原因和必要条件产生死锁的原因和必要条件u 预防和避免死锁的办法预防和避免死锁的办法u 死锁的检测与解除死锁的检测与解除2PPT

2、课件3.1 处理机调度的层次处理机调度的层次高级调度高级调度1 作业和作业步作业和作业步 作业作业 不仅包含通常的程序和数据，还应配备一份不仅包含通常的程序和数据，还应配备一份作作业说明书业说明书，系统根据作业说明书对程序的运行进程，系统根据作业说明书对程序的运行进程控制。在批处理系统中，是以作业为基本单位从外控制。在批处理系统中，是以作业为基本单位从外存调入内存。存调入内存。3PPT课件 作业步作业步 作业运行期间，每个作业都必须经过若干个作业运行期间，每个作业都必须经过若干个相对相对独立、又相互关联的顺序加工步骤独立、又相互关联的顺序加工步骤，才能得到结果，才能得到结果，把其中的每一个加工

3、步骤称为一个作业步。把其中的每一个加工步骤称为一个作业步。1）编译）编译 2）连接装配）连接装配 3）运行）运行 作业流作业流 若干个作业进入系统后，被依次存放在外存上，若干个作业进入系统后，被依次存放在外存上，形成形成输入的作业流输入的作业流；在；在OS的控制下，逐个作业进的控制下，逐个作业进行处理，形成了行处理，形成了处理作业流处理作业流。编译程序对源程序编译程序对源程序进行编译，生成若进行编译，生成若干个目标程序段。干个目标程序段。将目标程序段将目标程序段装配成可执行装配成可执行的目标程序的目标程序将目标程序读将目标程序读入内存并控制入内存并控制其运行其运行4PPT课件2 作业控制块作业

4、控制块 多道批处理系统中，为每个作业配备一个作业多道批处理系统中，为每个作业配备一个作业控制块（控制块（JCB），它），它是作业在系统中存在的标志是作业在系统中存在的标志。作业运行期间，系统按照作业运行期间，系统按照JCB中的信息对作业进行中的信息对作业进行控制。控制。JCB中中保存了系统对作业进行管理和调度所需保存了系统对作业进行管理和调度所需的全部信息的全部信息。例如：作业标识、用户名称、用户帐。例如：作业标识、用户名称、用户帐户、作业类型、作业状态、调度信息、资源需求、户、作业类型、作业状态、调度信息、资源需求、进入系统时间、开始处理时间、作业完成时间、作进入系统时间、开始处理时间、作业

5、完成时间、作业退出时间、资源使用情况等。业退出时间、资源使用情况等。5PPT课件3 作业调度（作业调度（高级调度、长程调度、接纳调度高级调度、长程调度、接纳调度）定义定义 按照一定的算法，从按照一定的算法，从外存的后备队列外存的后备队列中中选取某些作业调入内存，并为它们创建进程、选取某些作业调入内存，并为它们创建进程、分配必要的资源分配必要的资源 两个决定两个决定 1决定接纳决定接纳多少个多少个作业（多道程序度）作业（多道程序度）2决定接纳决定接纳哪些哪些作业作业数目过多：数目过多：每个进程可以每个进程可以执行的时间片就越小，单执行的时间片就越小，单个进程的周转时间越长；个进程的周转时间越长；

6、数目过少：数目过少：资源利用率和资源利用率和系统吞吐量下降，应考虑系统吞吐量下降，应考虑调度新的进程进入内存。调度新的进程进入内存。选用何种调度算法：先来先服务、选用何种调度算法：先来先服务、短作业优先、基于作业优先级、响短作业优先、基于作业优先级、响应比高者优先。应比高者优先。6PPT课件注意注意 批处理系统中，作业是首先进入外存，批处理系统中，作业是首先进入外存，然后经由作业调度分批进入内存；然后经由作业调度分批进入内存；分时系统及实时系统分时系统及实时系统中，由于对响应中，由于对响应时间有要求，因此用户输入的命令和数据时间有要求，因此用户输入的命令和数据等是直接进入内存的，等是直接进入内

7、存的，无须配置作业调度无须配置作业调度机制机制。7PPT课件1 定义定义 决定就绪队列中的哪个进程应获得处理机，然决定就绪队列中的哪个进程应获得处理机，然后由分派程序执行把处理机分配给该进程的具体后由分派程序执行把处理机分配给该进程的具体操作。操作。低级调度是最基本的一种调度，多道批处理、低级调度是最基本的一种调度，多道批处理、分时、实时系统中都必须配置。分时、实时系统中都必须配置。2 主要功能主要功能 保存当前进程的处理机现场信息保存当前进程的处理机现场信息 按某种算法（优先数算法、轮转法）选择进程按某种算法（优先数算法、轮转法）选择进程 将将CPU分配给该进程，恢复新进程的处理机现场，让分

8、配给该进程，恢复新进程的处理机现场，让其从断点开始执行。其从断点开始执行。低级调度低级调度（进程调度、短程调度）（进程调度、短程调度）8PPT课件3 进程调度机制进程调度机制 排队器排队器 将系统中的所有就绪进程按某种方式排成一个或多个队列，方便调度程序寻找。分派器分派器 将选中进程从后备队列移出，将处理机分配给它 上下文切换机制上下文切换机制 两次上下文切换：保存当前进程上下文，装入dispatcher上下文；移出dispatcher上下文，装入新选中进程的上下文。9PPT课件4 进程调度方式进程调度方式 非抢占方式非抢占方式 一旦把处理机分配给某进程后，一直让它一旦把处理机分配给某进程后，

9、一直让它运行下去，不能因为时钟中断等原因或由其它运行下去，不能因为时钟中断等原因或由其它进程抢占分配给它的处理机。直至该进程完成，进程抢占分配给它的处理机。直至该进程完成，或因某事件阻塞，才能重新分配处理机。或因某事件阻塞，才能重新分配处理机。优点：优点：实现简单，系统开销小；实现简单，系统开销小；缺点：缺点：难以满足紧急任务的要求，可能造成难难以满足紧急任务的要求，可能造成难以预料的后果。实时系统中，不宜采用该方式。以预料的后果。实时系统中，不宜采用该方式。10PPT课件 抢占方式抢占方式 允许调度程序根据某种原则暂停某个允许调度程序根据某种原则暂停某个正在执行的进程，将已分配给该进程的处正

10、在执行的进程，将已分配给该进程的处理机重新分配给另一进程。理机重新分配给另一进程。抢占原则：抢占原则：优先权、短作业优先、时间片。优先权、短作业优先、时间片。优点：优点：防止长进程长时间占用防止长进程长时间占用CPU，为大，为大多数进程提供更公平的服务，特别是能满多数进程提供更公平的服务，特别是能满足实时任务的要求。足实时任务的要求。缺点：缺点：与非抢占方式相比，开销较大。与非抢占方式相比，开销较大。11PPT课件 当被挂起的进程重新具备运行条件且内当被挂起的进程重新具备运行条件且内存稍有空闲时，把外存上的那些具备运行条存稍有空闲时，把外存上的那些具备运行条件的进程重新调入内存，并修改其状态为

11、就件的进程重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待进程调度。绪状态，挂在就绪队列上等待进程调度。中级调度中级调度12PPT课件3.2 调度队列模型和调度准则调度队列模型和调度准则仅有进程调度的调度队列模型仅有进程调度的调度队列模型仅具有进程调度的调度队列模型仅具有进程调度的调度队列模型时间片完时间片完就就 绪绪 队队 列列阻阻 塞塞 队队 列列CPU交互用户交互用户进程调度进程调度进程完成进程完成等待事件等待事件事件发生事件发生FIFO队列队列13PPT课件具有高级和低级调度的调度队列模型具有高级和低级调度的调度队列模型 具有高、低两级调度的调度队列模型具有高、低两级调度的调度

12、队列模型就就 绪绪 队队 列列阻阻 塞塞 队队 列列CPU时间片完时间片完作业作业调度调度进程调度进程调度进程完成进程完成等待事件等待事件1阻阻 塞塞 队队 列列阻阻 塞塞 队队 列列等待事件等待事件2等待事件等待事件n事件事件1发生发生事件事件2发生发生事件事件n发生发生后后 备备 队队 列列优先权队列优先权队列14PPT课件 具有高、低、中三级调度的调度队列模型具有高、低、中三级调度的调度队列模型就就 绪绪 队队 列列绪绪就就、挂挂 起起 队队 列列CPU时间片完时间片完作业作业调度调度进程调度进程调度进程完成进程完成事件出现事件出现阻阻 塞塞 队队 列列挂起挂起等待事件等待事件中级中级调

13、度调度事件发生事件发生后后 备备 队队 列列塞塞阻阻、挂挂 起起 队队 列列挂起挂起同时具有三级调度的调度队列模型同时具有三级调度的调度队列模型15PPT课件 面向用户的准则面向用户的准则 周转时间短（批处理）周转时间短（批处理）响应时间快（分时）响应时间快（分时）截止时间保证（实时）截止时间保证（实时）优先权准则（优先权准则（all）选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则带权周转时间：作业的周转时间与带权周转时间：作业的周转时间与系统为它提供服务的时间之比系统为它提供服务的时间之比niTTsinW11周转时间周转时间作业被提交给系作业被提交给系统开始，到作业完成为止

14、的这统开始，到作业完成为止的这段时间间隔。段时间间隔。包括：在外存后包括：在外存后备队列等待调度的时间；在内备队列等待调度的时间；在内存就绪队列等待调度的时间；存就绪队列等待调度的时间；在在CPU上执行的时间；等待上执行的时间；等待I/O操作的时间。操作的时间。niiTnT11响应时间：用户通过键盘提交请求开始，直至系统首次产生响应响应时间：用户通过键盘提交请求开始，直至系统首次产生响应为止。包括：请求信息传送到为止。包括：请求信息传送到CPU的时间，的时间，CPU处理请求的时间，处理请求的时间，将响应信息回送到终端显示器的时间将响应信息回送到终端显示器的时间16PPT课件 面向系统的准则面向

15、系统的准则系统吞吐量高系统吞吐量高处理机利用率好处理机利用率好各类资源的平衡利用各类资源的平衡利用吞吐量：单位时间内，系统完成的作业数处理机利用率：一般在40%90%各类资源：内存、外存和外设的平衡利用17PPT课件3.3 调度算法调度算法 根据系统的资源分配策略所规定的根据系统的资源分配策略所规定的资源资源分配算法分配算法u 先来先服务算法先来先服务算法u 短作业优先算法短作业优先算法u 高优先权优先算法高优先权优先算法u 时间片轮转调度算法时间片轮转调度算法18PPT课件先来先服务（先来先服务（FCFS）主要用于作业调度，也可用于进程调度。主要用于作业调度，也可用于进程调度。用于作业调度：

16、用于作业调度：每次从后备作业队列中选择每次从后备作业队列中选择最先进入的作业最先进入的作业，将它们调入内存，将它们调入内存，为它们分配资源、创建进程，然后挂到就绪进程队列上。为它们分配资源、创建进程，然后挂到就绪进程队列上。有利于长作业，而不利于短作业有利于长作业，而不利于短作业。用于进程调度：用于进程调度：每次从就绪进程队列中选择每次从就绪进程队列中选择最先进入的进程最先进入的进程，为之分配处理机，为之分配处理机，使之投入运行。使之投入运行。直到运行完成进程才会让出处理机直到运行完成进程才会让出处理机-非抢占式非抢占式。性能评价：性能评价：周转时间周转时间 =完成时间完成时间 到达时间到达时

17、间 带权周转时间带权周转时间 =周转时间周转时间/服务（运行）时间服务（运行）时间19PPT课件先来先服务（先来先服务（FCFS）进程进程编码编码到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间A010111B110011011001C21101102100100D31001022021991.9920PPT课件短作业短作业/进程优先进程优先（SJ/PF）短作业优先（短作业优先（SJF）从后备队列中选择从后备队列中选择估计运行时间最短估计运行时间最短的作业，调入内存运行。的作业，调入内存运行。短进程优先短进程优先（SPF）从就绪队

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

19、418周转时间461011149带权周转时间1225.53.52.8SJ/PF完成时间4918613周转时间4816398带权周转时间12.673.11.52.252.122PPT课件优先级优先级（FPF）既能用于作业调度，也可用于进程调度。既能用于作业调度，也可用于进程调度。调度思想调度思想：从队列中选择优先权最高的调度单元，从队列中选择优先权最高的调度单元，装入内存或分配给处理机。装入内存或分配给处理机。对进程调度而言，有对进程调度而言，有非抢占式非抢占式和和抢占式抢占式两种。两种。把处理机分配给就绪队列中优先权把处理机分配给就绪队列中优先权最高的进程，直至完成或因某种原最高的进程，直至完

20、成或因某种原因阻塞，才让出处理机。主要用于因阻塞，才让出处理机。主要用于批处理系统批处理系统中中同样是把同样是把CPU分给优先权最高的进程，但在该进程分给优先权最高的进程，但在该进程执行过程中，如有优先级更高的进程到来，则立即执行过程中，如有优先级更高的进程到来，则立即停止当前进程的执行，将停止当前进程的执行，将CPU分配给新到的优先级分配给新到的优先级最高的进程。常用于要求比较严格的最高的进程。常用于要求比较严格的实时系统实时系统中。中。23PPT课件 优先权优先权(0-255)静态静态优先权、优先权、动态动态优先权。优先权。优先权在创建进程时即确定，且在进优先权在创建进程时即确定，且在进程

21、的整个运行期间保持不变程的整个运行期间保持不变创建进程时所赋予的优先权，随进程的推进创建进程时所赋予的优先权，随进程的推进或等待时间的增加而改变或等待时间的增加而改变例如规定：例如规定：就绪队列中的进程，随就绪队列中的进程，随等待时间的延长等待时间的延长，优先，优先权以速率权以速率增长增长；执行中的进程，随执行中的进程，随执行时间的延长执行时间的延长，优先权以，优先权以速率速率下降下降。24PPT课件 高响应比高响应比优先调度算法优先调度算法动态优先权，与作业等待时间相关。动态优先权，与作业等待时间相关。优先权优先权=响应比（响应比（Rp）=（等待时间（等待时间+要求服务时间）要求服务时间）/

22、要求服务时间要求服务时间 =响应时间响应时间/要求服务时间要求服务时间 分析：分析：等待时间相同，等待时间相同，要求服务时间越短要求服务时间越短，优先级越高。有利于短作业。，优先级越高。有利于短作业。要求服务时间相同，要求服务时间相同，等待时间越长等待时间越长，优先级越高。即，优先级越高。即FCFS。对于长作业，优先级对于长作业，优先级随等待时间的延长而升高随等待时间的延长而升高，终能获得处理机。，终能获得处理机。因此，该算法是一种折衷算法。因此，该算法是一种折衷算法。缺点：频繁计算响应比，增加了系统开销缺点：频繁计算响应比，增加了系统开销。25PPT课件时间片轮转时间片轮转 特别适用于特别适

23、用于分时系统分时系统的调度算法。的调度算法。实现方法：实现方法：由计时器发出时钟中断，引起一次轮转调度。由计时器发出时钟中断，引起一次轮转调度。26PPT课件基本思想：基本思想：基于时钟的剥夺。基于时钟的剥夺。以一定的时间间隔周期性产生一个以一定的时间间隔周期性产生一个时时钟中断钟中断，当中断发生时，当前正在运行的，当中断发生时，当前正在运行的进程被置于就绪队列末尾，然后进程被置于就绪队列末尾，然后基于基于FCFS选择选择下一个就绪进程运行。下一个就绪进程运行。保证就绪队列中的所有进程在给定的保证就绪队列中的所有进程在给定的时间内都能获得时间内都能获得一时间片（一时间片（time slice）

24、的的处理机执行时间。处理机执行时间。27PPT课件执行过程执行过程1将系统中所有的就绪进程按照将系统中所有的就绪进程按照FCFS原则，原则，排成一个排成一个队列。队列。2每次调度时将每次调度时将CPU分派给分派给队首进程队首进程，让其，让其执行一个时间片执行一个时间片。时间片的。时间片的长度长度从几个从几个ms到几百到几百ms。3在一个时间片结束时，发生在一个时间片结束时，发生时钟中断。时钟中断。4调度程序据此调度程序据此暂停当前进程的执行，暂停当前进程的执行，将其将其送到送到就绪队列的末尾，就绪队列的末尾，并通过上下文切换并通过上下文切换执行当前的队首进程。执行当前的队首进程。5进程可以进程

25、可以未使用完一个时间片未使用完一个时间片，就，就出让出让CPU。28PPT课件ABCDFCPU完成完成超时超时阻塞阻塞时间片轮转调度算法示意图时间片轮转调度算法示意图29PPT课件 最佳时间片的确定最佳时间片的确定时间片的选取是实现各种调度算法的关键之处，而时间时间片的选取是实现各种调度算法的关键之处，而时间片的选定通常应考虑终端数目，处理机能力、各终端任务片的选定通常应考虑终端数目，处理机能力、各终端任务的急迫程度、外存传输速度等方面的因素。的急迫程度、外存传输速度等方面的因素。当时间片很大时当时间片很大时，大到一个进程足以完成其全部运行，大到一个进程足以完成其全部运行工作所需的时间，此时轮

26、转调度模式退化为工作所需的时间，此时轮转调度模式退化为FCFSFCFS模式。模式。当时间片非常小时当时间片非常小时，调度程序剥夺处理机的次数增多，调度程序剥夺处理机的次数增多，这将加重了系统开销，系统性能降低，大多数时间都消耗这将加重了系统开销，系统性能降低，大多数时间都消耗在处理机的转换上在处理机的转换上。30PPT课件多级反馈队列调度算法多级反馈队列调度算法 以上介绍的算法，都存在一定的局限性。以上介绍的算法，都存在一定的局限性。现在主流的操作系统，如现在主流的操作系统，如UNIX、Windows NT、Linux等，都使用一种综合性的调度算法等，都使用一种综合性的调度算法多多级反馈队列调

27、度算法级反馈队列调度算法。该算法综合了上述三种算法以及多队列调度算法该算法综合了上述三种算法以及多队列调度算法的思想和优点，的思想和优点，总体调度性能优越总体调度性能优越，适于各种类，适于各种类型的作业，但其实现也比较型的作业，但其实现也比较复杂复杂。31PPT课件算法的基本思想是算法的基本思想是：首先：首先：系统按进程优先级设置了系统按进程优先级设置了多级多级（比如（比如n级，级，n2）就绪进就绪进程队列程队列，从第一级队列到最后一级队列，优先级越来越低。，从第一级队列到最后一级队列，优先级越来越低。其次其次：每一级就绪队列对应一个：每一级就绪队列对应一个不同的时间片不同的时间片。优先权越高

28、的。优先权越高的队列，进程的时间片越小。队列，进程的时间片越小。再次：再次：当一个新进程进入内存后，首先被放到第一级队列的队当一个新进程进入内存后，首先被放到第一级队列的队尾。按照尾。按照FCFS原则排队等待调度。当轮到该进程执行时，如原则排队等待调度。当轮到该进程执行时，如能在时间片内完成，便可准备撤离系统；能在时间片内完成，便可准备撤离系统；如果在时间片内未完如果在时间片内未完成，调度程序便将该进程转入第二队列的末尾成，调度程序便将该进程转入第二队列的末尾，再依次按照，再依次按照FCFS原则等待调度。原则等待调度。32PPT课件最后最后：仅当第一级队列为空时，才调度第二级队列中：仅当第一级

29、队列为空时，才调度第二级队列中的进程；如此下去，的进程；如此下去，仅当前面的仅当前面的n-1级队列全部为空时，级队列全部为空时，才去调度最后第才去调度最后第n级队列中的进程级队列中的进程。如果处理机正在第。如果处理机正在第i队列中为某进程服务时，又有新的进程进入优先权高队列中为某进程服务时，又有新的进程进入优先权高的队列（第的队列（第1(i-1)中任何一队列），则系统中任何一队列），则系统抢占正在抢占正在运行的进程的处理机运行的进程的处理机，由调度程序把正在运行的进程，由调度程序把正在运行的进程放回到刚才所在第放回到刚才所在第i队列的队尾，重新进行处理机调度。队列的队尾，重新进行处理机调度。3

30、3PPT课件 多级反馈队列调度算法的性能 能较好地满足各种类型用户（进程）的需要。终端（交互）型作业用户 短批处理作业用户 长批处理作业用户 多级反馈队列调度算法示意图多级反馈队列调度算法示意图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；

31、进程进程QQ1 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多个进程在运行过程中因争夺资源而多个进程在运行过程中因争夺资源而造成的一种造成的一种僵局僵局，当进程处于这种

32、僵持，当进程处于这种僵持状态时，若无外力作用，它们都将无法状态时，若无外力作用，它们都将无法向前推进。向前推进。p一组进程中，每个进程都一组进程中，每个进程都无限等待无限等待被被该组进程中另一进程所占有的资源，因该组进程中另一进程所占有的资源，因而永远无法得到资源，这种现象称为而永远无法得到资源，这种现象称为进进程死锁程死锁，这一组进程就称为，这一组进程就称为死锁进程死锁进程。38PPT课件3.5.1 产生死锁的产生死锁的原因原因资源不足资源不足导致的资源竞争：导致的资源竞争：多个进程所多个进程所共享的资源不足，引起它们对资源的竞共享的资源不足，引起它们对资源的竞争而产生死锁。争而产生死锁。并

33、发执行并发执行的顺序不当：进程运行过程中，的顺序不当：进程运行过程中，请求和释放资源的顺序不当，而导致进请求和释放资源的顺序不当，而导致进程死锁程死锁.如如P,V操作的顺序不当操作的顺序不当39PPT课件死锁死锁现象举例现象举例40PPT课件一竞争资源引起死锁一竞争资源引起死锁 1资源的分类：可剥夺和非剥夺性资源资源的分类：可剥夺和非剥夺性资源：CPU和主存和主存 例如：优先权高的程可以剥夺低优先权进程的处理机。例如：优先权高的程可以剥夺低优先权进程的处理机。存储器管理程序把进程从一个存储区移至另外一个存储区，甚至存储器管理程序把进程从一个存储区移至另外一个存储区，甚至将一进程从内存调出到外存

34、上。将一进程从内存调出到外存上。：磁带机、打印机等：磁带机、打印机等 当系统把这类资源分配给某进程后，再不能强行收回，只能在进当系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自动释放。程用完后自动释放。41PPT课件两个进程分别准备打印一个非常大的磁带两个进程分别准备打印一个非常大的磁带文件（文件（双方都拥有部分资源，同时在请求对方双方都拥有部分资源，同时在请求对方已占有的资源。已占有的资源。）打印机R1磁带机R2P1P22竞争非剥夺性资源竞争非剥夺性资源42PPT课件3竞争临时性资源竞争临时性资源永久性资源永久性资源：打印机资源属于可顺序重复使打印机资源属于可顺序重复使用的资

35、源。用的资源。临时性资源临时性资源：由一个进程产生，被另一个进由一个进程产生，被另一个进程使用一短暂时间后便无用的资源。程使用一短暂时间后便无用的资源。例如例如进程通信时的消息。进程通信时的消息。43PPT课件R1P1R2P2S1P1S2P3S3P244PPT课件二进程推进顺序不当引起死锁二进程推进顺序不当引起死锁 资源资源少未必一定产生死锁。少未必一定产生死锁。就如同两个人过独木桥，如果两个人都要先过，在独木就如同两个人过独木桥，如果两个人都要先过，在独木桥上僵持不肯后退，必然会因竞争资源产生死锁；但是，桥上僵持不肯后退，必然会因竞争资源产生死锁；但是，如果两个人上桥前先看一看有无对方的人在

36、桥上，当无对如果两个人上桥前先看一看有无对方的人在桥上，当无对方的人在桥上时自己才上桥，那么问题就解决了。方的人在桥上时自己才上桥，那么问题就解决了。所以，如果程序设计得不合理，造成所以，如果程序设计得不合理，造成进程推进的顺序进程推进的顺序不当不当，也会出现死锁。，也会出现死锁。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研

37、研）一个一个OS有有20个进程，竞争使用个进程，竞争使用65个同类资源，申个同类资源，申请方式是逐个进行的，一旦某个进程获得它所需请方式是逐个进行的，一旦某个进程获得它所需要的全部资源，则立即归还所有资源。要的全部资源，则立即归还所有资源。每个进程最多使用每个进程最多使用三个三个资源。资源。若仅考虑这类资源，该系统有无可能产生死锁，若仅考虑这类资源，该系统有无可能产生死锁，为什么？为什么？48PPT课件 答：答：不可能不可能。因为死锁产生的原因有两点：系统资源不因为死锁产生的原因有两点：系统资源不足或推进顺序不当，在本题中，进程所需足或推进顺序不当，在本题中，进程所需的最大资源数为的最大资源数

38、为60，而系统共有该类资源，而系统共有该类资源65个，其资源数已足够系统内各进程使用。个，其资源数已足够系统内各进程使用。49PPT课件 互斥条件互斥条件 指进程对所分配到的资源进行指进程对所分配到的资源进行排它性使用排它性使用,即即在一段时间内某资源只能由一个进程占有。如在一段时间内某资源只能由一个进程占有。如果此时还有其它进程申请该资源果此时还有其它进程申请该资源,则它只能阻塞则它只能阻塞,直至占有该资源的进程释放。直至占有该资源的进程释放。占有且等待（请求和保持条件）占有且等待（请求和保持条件）进程已经进程已经保持了至少一个资源保持了至少一个资源,但又但又提出了新提出了新的资源要求的资源

39、要求,而该资源又已被其它进程占有而该资源又已被其它进程占有,此此时请求进程阻塞时请求进程阻塞,但又对已经获得的其它资源但又对已经获得的其它资源保持不放。保持不放。3.5.2 产生死锁的产生死锁的必要条件必要条件50PPT课件 非抢占（非剥夺）条件非抢占（非剥夺）条件 进程已获得的资源进程已获得的资源,在未使用完之前在未使用完之前,不能被剥不能被剥夺夺,只能在使用完时由自己释放。只能在使用完时由自己释放。循环等待条件循环等待条件 在发生死锁时在发生死锁时,必然存在一个必然存在一个进程进程-资源的封闭资源的封闭的环形链的环形链。即进程集合。即进程集合P0,P1,P2,Pn中的中的P0正在等待一个正

40、在等待一个P1占用的资源占用的资源;P1正在等待正在等待P2占用的资源占用的资源,Pn正在等待已被正在等待已被P0占用的资占用的资源源.51PPT课件 死锁的预防；死锁的预防；死锁的避免；死锁的避免；死锁的检测和解除；死锁的检测和解除；鸵鸟算法鸵鸟算法 当死锁在计算机中很少出现时，比如说每五年或更当死锁在计算机中很少出现时，比如说每五年或更长时间才出现一次时，人们就不必花费更多的精力去长时间才出现一次时，人们就不必花费更多的精力去解决它，而是采用类似鸵鸟一样的办法忽略它。解决它，而是采用类似鸵鸟一样的办法忽略它。3.5.3 处理死锁的基本方法处理死锁的基本方法52PPT课件预防死锁预防死锁 通

41、过通过设置某些限制条件设置某些限制条件，破坏产生，破坏产生死锁的个必要条件中的一个或几个死锁的个必要条件中的一个或几个条件，来预防发生死锁。条件，来预防发生死锁。53PPT课件避免死锁避免死锁 在资源的动态分配过程中，用某种在资源的动态分配过程中，用某种方法方法防止系统进入不安全状态防止系统进入不安全状态，从，从而避免发生死锁。而避免发生死锁。54PPT课件预防死锁与避免死锁的预防死锁与避免死锁的差别差别 预防死锁所施加的限制条件比较预防死锁所施加的限制条件比较严严格格，往往会限制进程的并发执行，往往会限制进程的并发执行 避免死锁所施加的限制条件比较避免死锁所施加的限制条件比较宽宽松松，给进程

42、的并发执行提供了较好的，给进程的并发执行提供了较好的环境。环境。55PPT课件检测死锁检测死锁 事先并不采取任何限制性措施，允事先并不采取任何限制性措施，允许系统在运行过程中发生死锁。但许系统在运行过程中发生死锁。但系统的系统的检测机构应能及时地检测出检测机构应能及时地检测出死锁的发生死锁的发生，并精确地确定与死锁，并精确地确定与死锁有关的进程和资源。有关的进程和资源。56PPT课件解除死锁解除死锁 与死锁的检测措施配合使用。与死锁的检测措施配合使用。当检测到死锁发生时，应当检测到死锁发生时，应能够将进程从能够将进程从死锁状态解脱出来死锁状态解脱出来。常用的方法是撤消或挂起一切进程，以常用的方

43、法是撤消或挂起一切进程，以便回收部分资源，再将这些资源分配给被便回收部分资源，再将这些资源分配给被阻塞的进程，使之能继续运行。阻塞的进程，使之能继续运行。57PPT课件3.6 预防和避免死锁的方法u死锁的预防u死锁的避免系统安全状态利用银行家算法避免死锁58PPT课件3.6.1 死锁的预防死锁的预防 保证互斥条件保证互斥条件 由设备（非共享资源）的固有特性所决定由设备（非共享资源）的固有特性所决定,不能不能被破坏被破坏,应加以保证。如打印机。应加以保证。如打印机。59PPT课件摒弃摒弃“请求和保持请求和保持”条件条件u采用采用静态资源分配法静态资源分配法u系统规定每一个进程在开始运行前，都必须

44、系统规定每一个进程在开始运行前，都必须一次性地一次性地申请申请其在整个运行过程所需的其在整个运行过程所需的全部资源全部资源。u若系统有足够的资源，便把进程想要的全部若系统有足够的资源，便把进程想要的全部资源一次性地分配给它；若不能全部满足进程的资源一次性地分配给它；若不能全部满足进程的资源请求，则一个资源也不分给它。资源请求，则一个资源也不分给它。u因此，进程在运行过程中就不会再提出资源因此，进程在运行过程中就不会再提出资源请求，从而破坏了请求，从而破坏了“请求和保持请求和保持”条件。条件。60PPT课件优点：优点：简单、安全、易实现。简单、安全、易实现。缺点：缺点：（1）资源被严重浪费）资源

45、被严重浪费（因为一个进程一次（因为一个进程一次获得其所需的全部资源并且独占，其中有可获得其所需的全部资源并且独占，其中有可能有些资源很少使用，严重恶化了资源利用能有些资源很少使用，严重恶化了资源利用率）。率）。（2）进程延迟运行。）进程延迟运行。（当且仅当进程获得（当且仅当进程获得其所需的全部资源后，才能开始运行，但有其所需的全部资源后，才能开始运行，但有可能有些资源长期被其他进程占用，致使需可能有些资源长期被其他进程占用，致使需要该资源的进程迟迟不能运行要该资源的进程迟迟不能运行）61PPT课件摒弃摒弃“不可剥夺条件不可剥夺条件”进程逐个提出对资源的请求进程逐个提出对资源的请求。即：一个已经

46、保持。即：一个已经保持了某些资源的进程，当它再提出新的资源要求而了某些资源的进程，当它再提出新的资源要求而不能立即得到满足时，必须释放它已经保持的所不能立即得到满足时，必须释放它已经保持的所有资源，待以后再需要时再重新申请。有资源，待以后再需要时再重新申请。实现复杂、代价大实现复杂、代价大,反复申请反复申请/释放资源释放资源,系统开销系统开销大大,降低系统吞吐量降低系统吞吐量 62PPT课件摒弃摒弃“循环等待条件循环等待条件”（有序资源使用（有序资源使用法）法）v系统中的所有资源按类型都被赋予一个系统中的所有资源按类型都被赋予一个唯一的编号唯一的编号，每个进程只能按编号的，每个进程只能按编号的

47、升序升序申申请资源。请资源。v对同一个进程而言，它一旦申请了一个编号对同一个进程而言，它一旦申请了一个编号为为i的资源，就的资源，就不允许不允许再申请编号再申请编号比比i小小的资的资源了，因此，破坏了循环等待条件。源了，因此，破坏了循环等待条件。63PPT课件v优点：安全，资源利用率比静态资源分配优点：安全，资源利用率比静态资源分配法有所提高。法有所提高。v缺点：实现较困难，因为难给出合适的资缺点：实现较困难，因为难给出合适的资源编号，不便于系统增添新设备，不便于源编号，不便于系统增添新设备，不便于用户编程，且仍有一定的资源浪费现象。用户编程，且仍有一定的资源浪费现象。64PPT课件3.6.2

48、 死锁的避免死锁的避免 死锁的避免是这样一种对付死锁的办法：死锁的避免是这样一种对付死锁的办法：系统在运行过程中采取系统在运行过程中采取动态的资源分配策略动态的资源分配策略，保证系统保证系统不进入不进入可能导致系统陷入死锁状态可能导致系统陷入死锁状态的所谓不安全状态，以避免死锁发生。的所谓不安全状态，以避免死锁发生。65PPT课件 死锁的避免与死锁预防策略不同：它死锁的避免与死锁预防策略不同：它不对进程申请资源加任何限制，而是不对进程申请资源加任何限制，而是对进对进程提出的每一次资源请求进行动态检查程提出的每一次资源请求进行动态检查，并根据检查结果决定是否分配资源以满足并根据检查结果决定是否分

49、配资源以满足进程的请求。由于采用了动态的资源分配进程的请求。由于采用了动态的资源分配策略，所以资源利用率比死锁的防止办法策略，所以资源利用率比死锁的防止办法高。高。66PPT课件一系统安全状态一系统安全状态安全状态安全状态若在某一时刻，若在某一时刻，系统中存在某种进程序列系统中存在某种进程序列，如，如，如果系统按此序列为每个进程分配，如果系统按此序列为每个进程分配其所需的资源，直至最大需求，每个进程均可顺利其所需的资源，直至最大需求，每个进程均可顺利完成。完成。称此时系统的状态为称此时系统的状态为安全状态安全状态，称这样的一个，称这样的一个进程序列进程序列为为安全序列安全序列。67PPT课件p

50、安全序列的安全序列的实质是实质是：序列中的每一个：序列中的每一个进程进程Pi（i=1,2,n）到以后运行完成尚需）到以后运行完成尚需要的资源量要的资源量不超过不超过系统当前系统当前剩余剩余的资源量的资源量与所有在序列中与所有在序列中排在它前面排在它前面的进程当前所的进程当前所占有的占有的资源量之和资源量之和。68PPT课件p不安全状态不安全状态若在某一时刻，系统中若在某一时刻，系统中不存在一个安全不存在一个安全序列序列，则称系统处于不安全状态。，则称系统处于不安全状态。p安全状态与死锁的关系安全状态与死锁的关系l只要系统处于安全状态只要系统处于安全状态,必定不会进入死锁状必定不会进入死锁状态；