计算机操作系统_第三章_处理机调度与死锁

1、本章讨论处理器资源的管理问题。本章讨论处理器资源的管理问题。处理器调度问题决定着整个系统的综合性能。处理器调度问题决定着整个系统的综合性能。不同的不同的CPU管理方法将为用户提供不同性能的操管理方法将为用户提供不同性能的操作系统。作系统。 从处理器调度的对象、时间、层次等不同角从处理器调度的对象、时间、层次等不同角度，可把处理器调度分成不同类型。度，可把处理器调度分成不同类型。按照调度涉及的层次不同，从用户作业从进按照调度涉及的层次不同，从用户作业从进入系统成为后备作业开始，直到运行结束退出系入系统成为后备作业开始，直到运行结束退出系统为止，可把处理器调度分成：统为止，可把处理器调度分成：高级

2、调度高级调度中级调度中级调度低级调度低级调度高级调度概念高级调度概念也称为也称为、长程调度或接纳调度。、长程调度或接纳调度。按照系统预定的调度策略，决定把外存上处于后备队按照系统预定的调度策略，决定把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程、分配必列中的哪些作业调入内存，并为它们创建进程、分配必要的资源，然后再将创建的进程排在就绪队列上，准备要的资源，然后再将创建的进程排在就绪队列上，准备执行。执行。 在批处理操作系统中，作业首先进入系统在辅存上的在批处理操作系统中，作业首先进入系统在辅存上的后备作业队列等候调度，因此，作业调度是必须的。在后备作业队列等候调度，因此，作业调度是

3、必须的。在纯粹的分时或实时操作系统中，通常不需要配备作业调纯粹的分时或实时操作系统中，通常不需要配备作业调度。度。作业调度时要做的决定：作业调度时要做的决定：（1）接纳多少个作业）接纳多少个作业（2）接纳哪些作业（调度算法）接纳哪些作业（调度算法）作业调度的目标：作业调度的目标：（1）对所有作业尽量做到公平合理）对所有作业尽量做到公平合理（2）高设备利用率）高设备利用率（3）执行尽可能多的作业）执行尽可能多的作业（4）尽量短的响应时间）尽量短的响应时间也称为也称为、短程调度。、短程调度。用于决定就绪队列中的哪个进程获得处理机。低级调用于决定就绪队列中的哪个进程获得处理机。低级调度程序是操作系统

4、最为核心的部分，低级调度策略的优度程序是操作系统最为核心的部分，低级调度策略的优劣直接影响到整个系统的性能。劣直接影响到整个系统的性能。最初的调度对象是传统操作系统中的进程，随着现代最初的调度对象是传统操作系统中的进程，随着现代操作系统引入了多线程技术，进程演变成资源管理的单操作系统引入了多线程技术，进程演变成资源管理的单位，从而只作为中级调度的对象，内核级线程则替代进位，从而只作为中级调度的对象，内核级线程则替代进程成为低级调度的对象。程成为低级调度的对象。 （1）记录系统中所有进程的执行情况）记录系统中所有进程的执行情况（2）选择占有处理机的进程）选择占有处理机的进程(选择算法选择算法)（

5、3）进行进程上下文切换）进行进程上下文切换个进程的上下文个进程的上下文(context)包括进程的状态、包括进程的状态、有关变量和数据结构的值、机器寄存器的值等相关有关变量和数据结构的值、机器寄存器的值等相关程序、数据。当正在执行的进程让出处理机时，系程序、数据。当正在执行的进程让出处理机时，系统要做进程上下文切换，以使另一个进程得以执行。统要做进程上下文切换，以使另一个进程得以执行。 1）非抢占方式）非抢占方式进程一旦获得处理机后便一起执行下去，直至该进进程一旦获得处理机后便一起执行下去，直至该进程完成或发生某事件被阻塞时，才把处理机分配给其他程完成或发生某事件被阻塞时，才把处理机分配给其他

6、进程。决不允许某进程抢占已经分配出去的处理机。进程。决不允许某进程抢占已经分配出去的处理机。当前进程无论在用户态还是核心态都不可以被抢用当前进程无论在用户态还是核心态都不可以被抢用CPU。不可抢先式。不可抢先式OS：Windows98/95，在这些，在这些OS中，进程从运行态退出只能是自愿或阻塞，不能强迫运中，进程从运行态退出只能是自愿或阻塞，不能强迫运行态行态就绪态。就绪态。引起进程调度的因素：引起进程调度的因素：（1）进程执行完毕，或发生某事件不能再继续）进程执行完毕，或发生某事件不能再继续执行执行（2）I/O请求请求（3）进程通信或同步过程中执行了原语操作）进程通信或同步过程中执行了原语

7、操作优点：优点：实现实现简单，系统开销小，适用于批实现实现简单，系统开销小，适用于批处理系统。处理系统。缺点：缺点：不能满足紧急任务的要求，不适用于实不能满足紧急任务的要求，不适用于实时系统。时系统。当一个进程正在运行时，调度程序可以基于某当一个进程正在运行时，调度程序可以基于某种原则，剥夺已分配给它的处理机，将之分配给其种原则，剥夺已分配给它的处理机，将之分配给其它进程。它进程。剥夺原则有：剥夺原则有：（1）优先权原则）优先权原则（2）短进程优先原则）短进程优先原则（3）时间片原则。）时间片原则。当前进程在用户态时可随时被抢用当前进程在用户态时可随时被抢用CPU，但，但处于核心态时完全不可以

8、被抢用处于核心态时完全不可以被抢用CPU。如：传统。如：传统的的UNIX和和Windows。这类操作系统通常在系统调用或中断时屏蔽这类操作系统通常在系统调用或中断时屏蔽中断，系统调用返回或中断返回时开放中断。中断，系统调用返回或中断返回时开放中断。当前进程在用户态时随时被抢用当前进程在用户态时随时被抢用CPU，但处，但处于核心态时则大部分时间不可以被抢用于核心态时则大部分时间不可以被抢用CPU，只，只在某些时刻点（可抢先点）可以被抢用在某些时刻点（可抢先点）可以被抢用CPU。如：。如：UNIX SVR4。SVR4内核定义了内核定义了抢先点抢先点：内核代码中的这：内核代码中的这样一些位置，内核的

9、数据结构处在一个稳定的状样一些位置，内核的数据结构处在一个稳定的状态，并且内核马上要开始长时间的、大量的计算。态，并且内核马上要开始长时间的、大量的计算。此时，内核检查是否有实时进程就绪需要运行，此时，内核检查是否有实时进程就绪需要运行，若有则抢先当前进程。若有则抢先当前进程。无论当前进程处于用户态还是核心态，都可无论当前进程处于用户态还是核心态，都可以随时可被抢用以随时可被抢用CPU。如：。如：SUN Solaris（最（最成功的成功的UNIX商业变种之一）。商业变种之一）。为做到完全可抢先，为做到完全可抢先，Solaris对对SVR4的核心的核心代码做了全面修改，大部分的内核全局数据结构代

10、码做了全面修改，大部分的内核全局数据结构都用正确的同步对象如互斥都用正确的同步对象如互斥 锁或信号量来保护，锁或信号量来保护，并通过特殊内核线程实现中断来避免用提高优先并通过特殊内核线程实现中断来避免用提高优先级的方法保护临界区。级的方法保护临界区。Solaris内核中只有极少内核中只有极少的不可抢先代码段。的不可抢先代码段。中级调度实现进程在主存与外存间的对换。反映到中级调度实现进程在主存与外存间的对换。反映到进程状态上就是挂起和解除挂起。进程状态上就是挂起和解除挂起。中级调度将那些暂时不能运行的进程调出主存，此中级调度将那些暂时不能运行的进程调出主存，此时这些进程处于挂起状态。当被挂起的进

11、程具备了运行时这些进程处于挂起状态。当被挂起的进程具备了运行条件，且主存又有空闲区域时，再由中级调度决定一部条件，且主存又有空闲区域时，再由中级调度决定一部分这样的进程重新调回主存工作。分这样的进程重新调回主存工作。中级调度起到短期调整系统负荷的作用，调度的依中级调度起到短期调整系统负荷的作用，调度的依据是存储资源量和进程的当前状态，目的是提高内存利据是存储资源量和进程的当前状态，目的是提高内存利用率和系统吞吐量。用率和系统吞吐量。3.2.1 调度队列模型调度队列模型1只有进程调度的调度队列模型只有进程调度的调度队列模型内存中维护就绪进程队列和阻塞进程队列。系统可内存中维护就绪进程队列和阻塞进

12、程队列。系统可能以栈、树、链表的方式组织队列。能以栈、树、链表的方式组织队列。 外存维护一个后备队列，内存维护就绪进程外存维护一个后备队列，内存维护就绪进程队列和阻塞进程队列。队列和阻塞进程队列。不同类型及目标的操作系统，其采用的调度不同类型及目标的操作系统，其采用的调度方式与调度算法通常不同。方式与调度算法通常不同。1面向用户的准则面向用户的准则2面向系统的准则面向系统的准则（1）周转时间短）周转时间短周转时间：作业提交计算机开始到完成返回周转时间：作业提交计算机开始到完成返回用户为止的时间间隔。用户为止的时间间隔。（2）响应时间快）响应时间快响应时间：从提交一个请求到首次产生响应响应时间：

13、从提交一个请求到首次产生响应的时间间隔。或者说，用户发送指令给计算机到的时间间隔。或者说，用户发送指令给计算机到计算机返回结果给用户的时间间隔。计算机返回结果给用户的时间间隔。（3）截止时间的保证）截止时间的保证评价实时系统的重要指标。评价实时系统的重要指标。截止时间：任务必须开始执行的最迟时间，或截止时间：任务必须开始执行的最迟时间，或必须完成的最迟时间。必须完成的最迟时间。（4）优先权准则：关键任务得到更好的性能指）优先权准则：关键任务得到更好的性能指标标（5）公平性：确保每个用户每个进程获得合理）公平性：确保每个用户每个进程获得合理的的CPU份额或其他资源份额。份额或其他资源份额。（1）

14、系统吞吐量高）系统吞吐量高吞吐量：单位时间内系统完成的作业数。吞吐量：单位时间内系统完成的作业数。（2）处理机利用率高：大中型系统的主要）处理机利用率高：大中型系统的主要指标指标（3）各类资源的平衡利用）各类资源的平衡利用常用的作业调度算法有：常用的作业调度算法有：常用进程调度算法：常用进程调度算法：最简单的调度算法，基本思想是按进程（作业）最简单的调度算法，基本思想是按进程（作业）到达的先后顺序进行调度。到达的先后顺序进行调度。作业调度：作业调度：按照作业进入系统的先后次序来挑按照作业进入系统的先后次序来挑选作业，先进入系统的作业优先被挑选。选作业，先进入系统的作业优先被挑选。进程调度：进程

15、调度：按照进程进入就绪队列的先后次序按照进程进入就绪队列的先后次序来分配处理器。先进入就绪队列的进程优先被挑选，来分配处理器。先进入就绪队列的进程优先被挑选，运行进程一旦占有处理器将一直运行下去直到运行运行进程一旦占有处理器将一直运行下去直到运行结束或阻塞，即采用非抢占调度方式。结束或阻塞，即采用非抢占调度方式。FCFS的特点：的特点：l比较有利于长作业，而不利于短作业（进比较有利于长作业，而不利于短作业（进程）。程）。l有利于有利于CPU繁忙型作业，而不利于繁忙型作业，而不利于I/O繁忙型繁忙型作业。作业。l实现简单实现简单l平均周转时间长平均周转时间长这是对这是对FCFS算法的改进，其目标

16、是减少平算法的改进，其目标是减少平均周转时间。均周转时间。SJF：从后备队列中选择估计运行时间最短从后备队列中选择估计运行时间最短的一个或几个作业调入内存。的一个或几个作业调入内存。SPF：从就绪队列中选择一个估计运行时间从就绪队列中选择一个估计运行时间最短的进程，将处理机分配给它。最短的进程，将处理机分配给它。短进程优先算法既可以是非抢占式，也可以是短进程优先算法既可以是非抢占式，也可以是抢占式。抢占式。当一个进程正在执行时，一个新进程进入就绪当一个进程正在执行时，一个新进程进入就绪状态，如果新进程需要的状态，如果新进程需要的CPU时间比当前正在执行时间比当前正在执行的进程剩余下来还需的的进

17、程剩余下来还需的CPU时间短，抡占式短进程时间短，抡占式短进程优先算法强行赶走当前正在执行进程，这种方式也优先算法强行赶走当前正在执行进程，这种方式也叫叫最短剩余时间优先算法最短剩余时间优先算法(Shortest Remaining Time First) 。优点：优点：与与FCFS相比，改善平均周转时间和平均带权周转时间，缩相比，改善平均周转时间和平均带权周转时间，缩短作业的平均等待时间。短作业的平均等待时间。易于实现，系统吞吐量高。易于实现，系统吞吐量高。缺点：缺点：忽视了作业等待时间忽视了作业等待时间对长作业非常不利，长作业（进程）可能长时间得不到执行；对长作业非常不利，长作业（进程）可

18、能长时间得不到执行；未能依据作业的紧迫程度来划分执行的优先级；未能依据作业的紧迫程度来划分执行的优先级；难以准确估计作业（进程）的执行时间，从而影响调度性能。难以准确估计作业（进程）的执行时间，从而影响调度性能。短作业优先算法的变型：短作业优先算法的变型：“最短剩余时间优先最短剩余时间优先”(Shortest Remaining Time First) 允许比当前进程剩余时间更短的进程抢占当前进允许比当前进程剩余时间更短的进程抢占当前进程程“最高响应比优先最高响应比优先” (Highest Response Ratio Next) 响应比响应比R = (等待时间等待时间 + 要求执行时间要求执

19、行时间) / 要求要求执行时间执行时间 是是FCFS和和SJF的折衷的折衷作业调度：作业调度：从后备队列中选择若干个优先权从后备队列中选择若干个优先权最高的作业进入内存。最高的作业进入内存。进程调度：进程调度：每一个进程给出一个优先数，处每一个进程给出一个优先数，处理器调度每次选择就绪进程队列中优先数最大者，理器调度每次选择就绪进程队列中优先数最大者，让它占用处理器运行。让它占用处理器运行。（1）非抢占式优先权算法）非抢占式优先权算法系统一旦将处理机分配给优先权最高的进程后，该系统一旦将处理机分配给优先权最高的进程后，该进程便一直执行下去直到完成。主要用于批处理系统，进程便一直执行下去直到完成

20、。主要用于批处理系统，也用于某些实时要求不严的实时系统中。也用于某些实时要求不严的实时系统中。（2）抢占式优先权调度算法）抢占式优先权调度算法系统按最高优先权分配处理机。只要出现另一个优系统按最高优先权分配处理机。只要出现另一个优先权更高的进程，则进程调度程序停止当前进程的执行，先权更高的进程，则进程调度程序停止当前进程的执行，重新将处理机分配给新到的优先权最高的进程。重新将处理机分配给新到的优先权最高的进程。常用于严格的实时系统中，或对性能要求较高的批常用于严格的实时系统中，或对性能要求较高的批处理和分时系统中。处理和分时系统中。（1）静态优先权）静态优先权静态优先权是在创建进程时确定的，在

21、整个运行期静态优先权是在创建进程时确定的，在整个运行期间不再改变。间不再改变。确定优先权的依据有：确定优先权的依据有：进程类型。如系统进程优先权高于用户进程。进程类型。如系统进程优先权高于用户进程。进程对资源的需求。如估计运行时间、内存需求等。进程对资源的需求。如估计运行时间、内存需求等。用户要求。由用户或操作员根据作业的紧急程序指用户要求。由用户或操作员根据作业的紧急程序指定一个优先级。定一个优先级。静态优先权法简单易行，系统开销小，但不够精确。静态优先权法简单易行，系统开销小，但不够精确。（2）动态优先权）动态优先权创建进程时所赋予的优先权，在进程周期内创建进程时所赋予的优先权，在进程周期

22、内可以动态变化。如随等待时间的增加而改变。可以动态变化。如随等待时间的增加而改变。优先权确定依据：优先权确定依据：根据进程占用有根据进程占用有CPU时间的长短来决定。时间的长短来决定。根据就绪进程等待根据就绪进程等待CPU的时间长短来决定。的时间长短来决定。最高响应比优先法（最高响应比优先法（HRN）是对）是对FCFS方式和方式和SJF方式的一种综合平衡。方式的一种综合平衡。 HRN调度策略同时考虑每个作业的等待时间长调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。最高的作业投入执行。响应比响应比=（等

23、待时间（等待时间+要求服务时间）要求服务时间）/要求服务时间要求服务时间特点：特点：（1）在等待时间相同时，此算法是优待短作业）在等待时间相同时，此算法是优待短作业的，实现的是的，实现的是SJF。（2）在要求服务时间相同时，优先权决定于等）在要求服务时间相同时，优先权决定于等待时间，实现的是待时间，实现的是FCFS。（3）长作业在等待足够长时，也可获得处理机。）长作业在等待足够长时，也可获得处理机。这种算法是介于这种算法是介于FCFS和和SJF之间的一种折中算之间的一种折中算法。但是由于每次调度前要计算响应比，系统开销法。但是由于每次调度前要计算响应比，系统开销也要相应增加。也要相应增加。1.

24、 时间片轮转法时间片轮转法系统将所有就绪进程按系统将所有就绪进程按FIFS规则排队，每个进程规则排队，每个进程轮流运行一个相同的时间片。轮流运行一个相同的时间片。每次调度时将每次调度时将CPU分派给队首进程，让其执行一个分派给队首进程，让其执行一个时间片。在一个时间片结束时，发生时钟中断，调度程时间片。在一个时间片结束时，发生时钟中断，调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，序据此暂停当前进程的执行，将其送到就绪队列的末尾，再将处理机分配给就绪队列的队首进程。这样可保证就再将处理机分配给就绪队列的队首进程。这样可保证就绪队列中的所有进程在一定时间内均能获得一时间片的绪队列中的所

25、有进程在一定时间内均能获得一时间片的处理机，即系统在能在给定时间内响应所有用户的请求。处理机，即系统在能在给定时间内响应所有用户的请求。 好处：好处：使系统及时响应。使系统及时响应。缺点：缺点：轮转法调度是一种剥夺式调度，系统耗轮转法调度是一种剥夺式调度，系统耗费在进程切换上的开销比较大，费在进程切换上的开销比较大，时间片长度变化的影响时间片长度变化的影响:过长过长退化为退化为FCFS算法，进程在一个时间算法，进程在一个时间片内都执行完，响应时间长。片内都执行完，响应时间长。过短过短用户的一次请求需要多个时间片才能用户的一次请求需要多个时间片才能处理完，切换次数增加，系统开销大。处理完，切换次

26、数增加，系统开销大。时间片长度的确定：时间片长度的确定：（1）系统效率）系统效率（2）对响应时间的要求：）对响应时间的要求： T(响应时间响应时间)=N(进程数目进程数目)*q(时间片时间片)（3）就绪进程的数目：数目越多，时间片越小）就绪进程的数目：数目越多，时间片越小（4）CPU的处理能力：应当使用户输入通常在的处理能力：应当使用户输入通常在一个时间片内能处理完，否则使响应时间，一个时间片内能处理完，否则使响应时间，平均周转时间和平均带权周转时间延长。平均周转时间和平均带权周转时间延长。 多级反馈队列算法是时间片轮转算法和多级反馈队列算法是时间片轮转算法和优先级算法的综合和发展。优先级算法

27、的综合和发展。 1）实现）实现（1）系统中设置多个就绪队列，分别赋予不同的优先）系统中设置多个就绪队列，分别赋予不同的优先级，并逐级降低。级，并逐级降低。（2）为不同队列所规定的时间片长度不同，优先权越）为不同队列所规定的时间片长度不同，优先权越高的队列分配的时间片越小。如逐级加倍。高的队列分配的时间片越小。如逐级加倍。（3）新进程进入内存后，先投入队列）新进程进入内存后，先投入队列1的末尾，按的末尾，按FCFS算法排队调度；若按队列算法排队调度；若按队列1的一个时间片未的一个时间片未能执行完，则降低投入到队列能执行完，则降低投入到队列2的末尾。如果在的末尾。如果在队列队列2的时间片内未能完成

28、，则降低投入到队列的时间片内未能完成，则降低投入到队列3；如此下去，降低到最后的队列，则按；如此下去，降低到最后的队列，则按“时间片轮转时间片轮转”算法调度直到完成。算法调度直到完成。（4）仅当较高优先级的队列为空，才调度较低优先级）仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾。把被抢先的进程投入原队列的末尾。（5）阻塞进程被唤醒时，进入原来的就绪队列中。）阻塞进程被唤醒时，进入原来的就绪队列中。（1

29、）终端型作业用户）终端型作业用户提供高的响应时间。提供高的响应时间。（2）短批处理作业用户）短批处理作业用户在第一个或前在第一个或前2个时间片中即可完成，平均周个时间片中即可完成，平均周转时间短。转时间短。（3）长批处理作业用户）长批处理作业用户不会饥饿。不会饥饿。为提高系统吞吐量和缩短平均周转时间而为提高系统吞吐量和缩短平均周转时间而照顾短进程。照顾短进程。为获得较好的为获得较好的I/O设备利用率和缩短响应设备利用率和缩短响应时间而照顾时间而照顾I/O型进程。型进程。不必估计进程的执行时间，动态调节。不必估计进程的执行时间，动态调节。实时系统中存在若干个实时进程或实时任务，实时系统中存在若干

30、个实时进程或实时任务，反应或控制某些外部事件。反应或控制某些外部事件。实时系统要响应的事件（要处理的实时任务）实时系统要响应的事件（要处理的实时任务）可以进一步划分为周期性事件和非周期性事件，可以进一步划分为周期性事件和非周期性事件，都联系着一个截止响应时间。都联系着一个截止响应时间。提供必要的信息提供必要的信息系统处理能力强系统处理能力强多采用抢占式调度机制多采用抢占式调度机制具有快速切换机制具有快速切换机制1非抢占式调度算法非抢占式调度算法（1）非抢占式轮转调度算法）非抢占式轮转调度算法 通过对所有周期性任务的分析预测（到达时间、运行通过对所有周期性任务的分析预测（到达时间、运行时间、结束

31、时间、任务间的优先关系），事先确定一个时间、结束时间、任务间的优先关系），事先确定一个固定的调度方案。这种方法的特点是有效但不灵活。固定的调度方案。这种方法的特点是有效但不灵活。 （2）非抢占式优先级调度算法）非抢占式优先级调度算法2抢占式调度算法抢占式调度算法（1）基于时钟中断的抢占式优先权调度算法。）基于时钟中断的抢占式优先权调度算法。（2）立即抢占的优先权调度算法）立即抢占的优先权调度算法实时调度算法可以分为实时调度算法可以分为动态实时动态实时调度算法和调度算法和静态实时静态实时调度算法两类。动态实时调度算法在运调度算法两类。动态实时调度算法在运行时作出调度决定，静态实时调度算法在系统启

32、行时作出调度决定，静态实时调度算法在系统启动之前完成所有的调度决策。动之前完成所有的调度决策。常用的实时算法都是基于优先权的算法。常用的实时算法都是基于优先权的算法。根据任务的开始截止时间来确定任务的优先级。截根据任务的开始截止时间来确定任务的优先级。截止时间越早，优先级越高。止时间越早，优先级越高。实时任务的就绪队列按优先级排序，调度程序总是实时任务的就绪队列按优先级排序，调度程序总是选择队首进程占有处理机。选择队首进程占有处理机。EDF算法用于非抢占调度方式算法用于非抢占调度方式根据任务的紧急（或松驰）程序来确定任务根据任务的紧急（或松驰）程序来确定任务的优先级。任务紧急程序高，为该任务所

33、赋予的的优先级。任务紧急程序高，为该任务所赋予的优先级愈高。优先级愈高。该算法主要用于抢占式调度方式。该算法主要用于抢占式调度方式。松弛度松弛度=必须完成时间必须完成时间-其本身的运行时间其本身的运行时间-当前时间当前时间假如在一个实时系统中，有两个周期性实时任务假如在一个实时系统中，有两个周期性实时任务A和和B，任务，任务A要求每要求每 20 ms执行一次，执行时间执行一次，执行时间为为 10 ms；任务；任务B只要求每只要求每50 ms执行一次，执执行一次，执行时间为行时间为 25 ms。 A A和和B B任务每次任务每次必须完成的时间必须完成的时间利用利用LLFLLF算法算法进行调度的情

34、况进行调度的情况死锁实例死锁实例设系统有一台打印机设系统有一台打印机(R1)一台扫描仪一台扫描仪(R2)，被并发的，被并发的A、B两进程共享。用信号量两进程共享。用信号量S1、S2表示表示R1、R2是否可是否可用，用， S1、 S2初值为初值为1。A、B并发时就可能产生死并发时就可能产生死锁。锁。 死锁：死锁：多个进程因竞争共享资源而造成的一多个进程因竞争共享资源而造成的一种僵局，若无外力作用，这些进程都将永远不能种僵局，若无外力作用，这些进程都将永远不能再向前推进。再向前推进。一组并发进程彼此互相等待对方所拥有的资一组并发进程彼此互相等待对方所拥有的资源，且这些并发进程在得到对方的资源之前不

35、会源，且这些并发进程在得到对方的资源之前不会释放自己所拥有的资源。从而造成大家都想得到释放自己所拥有的资源。从而造成大家都想得到资源而又都得不到资源，各并发进程不能继续向资源而又都得不到资源，各并发进程不能继续向前推进的状态。这一组进程就称为死锁进程。前推进的状态。这一组进程就称为死锁进程。产生死锁的因素不仅与系统拥有的资源数量有关，而且与资源分配策略，进程对资源的使用要求以及并发进程的速率有关。1.1.竞争系统资源竞争系统资源2.2.进程的推进顺序不当进程的推进顺序不当 可剥夺资源：分配给某进程后又可以被其他进可剥夺资源：分配给某进程后又可以被其他进程或系统剥夺的资源。如处理机、内存。程或系

36、统剥夺的资源。如处理机、内存。非剥夺资源：一旦分配给某进程后不能强行收非剥夺资源：一旦分配给某进程后不能强行收回，只能由进程自行释放的资源。回，只能由进程自行释放的资源。u永久性资源：可以被多个进程多次使用的资源永久性资源：可以被多个进程多次使用的资源（可再用资源）。（可再用资源）。u临时性资源：由一个进程产生，被另一进程使临时性资源：由一个进程产生，被另一进程使用一段时间后便无用的资源。如消息，中断信用一段时间后便无用的资源。如消息，中断信号，同步信号等（可消耗性资源）。号，同步信号等（可消耗性资源）。（1）竞争非剥夺资源）竞争非剥夺资源（2）竞争临时性资源）竞争临时性资源P1P2Reque

37、st(R1);Request(R2);Request(R2);Request(R1);Releast(R1);Releast(R2);Releast(R2);Releast(R1);1互斥条件：资源独占，排他性使用。互斥条件：资源独占，排他性使用。 2请求和保持条件：当进程因请求资源而阻塞时，请求和保持条件：当进程因请求资源而阻塞时，不释放已占有的资源。不释放已占有的资源。3不剥夺条件：进程已获得的资源不能被剥夺，不剥夺条件：进程已获得的资源不能被剥夺，只能在使用完时由自己释放。只能在使用完时由自己释放。4环路等待条件：在发生死锁时，必然存在一个环路等待条件：在发生死锁时，必然存在一个进程进程

38、-资源的环形循环链，链中每一个进程已资源的环形循环链，链中每一个进程已获得的资源被下一个进程所请求，同时它又获得的资源被下一个进程所请求，同时它又请求上一进程所拥有的资源。请求上一进程所拥有的资源。M预防死锁：设置限制条件，破坏产生死锁的预防死锁：设置限制条件，破坏产生死锁的四个必要条件中的一个或几个条件四个必要条件中的一个或几个条件 。M避免死锁：在每次的资源动态分配过程中，避免死锁：在每次的资源动态分配过程中，对系统能够满足的资源申请进行安全性检查对系统能够满足的资源申请进行安全性检查 ，根据结果决定是否进行此次分配。根据结果决定是否进行此次分配。M检测死锁：允许系统发生死锁，但设置检测检

39、测死锁：允许系统发生死锁，但设置检测机构，及时检测出死锁的发生。机构，及时检测出死锁的发生。M解除死锁：外力推动解除死锁。具体方法有：解除死锁：外力推动解除死锁。具体方法有：撤消或挂起死锁进程、剥夺资源等。撤消或挂起死锁进程、剥夺资源等。 死锁的预防：通过设置限制条件，破坏产生死死锁的预防：通过设置限制条件，破坏产生死锁的四个必要条件中的一个或几个条件，使系统锁的四个必要条件中的一个或几个条件，使系统在任何时刻都不满足死锁的必要条件，从而预防在任何时刻都不满足死锁的必要条件，从而预防死锁的发生。死锁的发生。进程必须在运行前一次性地申请运行期间所进程必须在运行前一次性地申请运行期间所需的全部资源

40、，这样进程在整个运行期间不会再需的全部资源，这样进程在整个运行期间不会再提出资源请求，从而提出资源请求，从而摒弃了请求和保持条件。摒弃了请求和保持条件。优点：简单，易于实现，安全。优点：简单，易于实现，安全。缺点：缺点：（1）资源浪费严重。降低进程并发度。）资源浪费严重。降低进程并发度。（2）进程延迟运行。）进程延迟运行。（3）不适用资源需要未知的进程。）不适用资源需要未知的进程。允许进程逐个申请资源，当进程新的资源请允许进程逐个申请资源，当进程新的资源请求未满足时，必须释放已占有的资源，待以后需求未满足时，必须释放已占有的资源，待以后需要时再重新申请。要时再重新申请。此策略表明进程已占有的资

41、源可被暂时释放，此策略表明进程已占有的资源可被暂时释放，即被剥夺了，从而即被剥夺了，从而摒弃摒弃“不剥夺不剥夺”条件条件。缺点：缺点：（1）复杂，实现困难且代价大。）复杂，实现困难且代价大。（2）延长了进程的周转时间，增加系统开）延长了进程的周转时间，增加系统开销。销。系统给每类资源赋予一个序号，每一个进程严格按系统给每类资源赋予一个序号，每一个进程严格按照序号递增的顺序请求资源，释放则相反。此方法不可照序号递增的顺序请求资源，释放则相反。此方法不可能形成资源占有与请求的环路，从而能形成资源占有与请求的环路，从而破坏环路等待条件破坏环路等待条件。优点：相对而言，系统利用率高，系统吞吐量大。优点

42、：相对而言，系统利用率高，系统吞吐量大。缺点：缺点：（1）限制设备扩充。系统事先确定资源序号，限）限制设备扩充。系统事先确定资源序号，限制了新类型设备的增加。制了新类型设备的增加。（2）限制了进程对资源的请求，编程困难。）限制了进程对资源的请求，编程困难。（3）资源浪费。当进程使用顺序与资源序号不相）资源浪费。当进程使用顺序与资源序号不相符时，也会造成资源浪费。符时，也会造成资源浪费。避免死锁的方法就是让系统处于安全状态中。避免死锁的方法就是让系统处于安全状态中。在避免死锁的策略中，允许进程动态地申请在避免死锁的策略中，允许进程动态地申请资源。资源。死锁避免死锁避免：系统对进程运行过程中发出的

43、每：系统对进程运行过程中发出的每一个系统能够满足的资源申请进行安全检查，根一个系统能够满足的资源申请进行安全检查，根据检查结果决定是否分配资源。若此次分配会导据检查结果决定是否分配资源。若此次分配会导致系统进入不安全状态，则不予分配；否则予以致系统进入不安全状态，则不予分配；否则予以分配。分配。1安全状态安全状态安全状态指系统能按某种进程顺序来为每个安全状态指系统能按某种进程顺序来为每个进程分配其所需资源，直至每个进程的最大需求，进程分配其所需资源，直至每个进程的最大需求，使每个进程都可顺序完成。若系统不存在这样一使每个进程都可顺序完成。若系统不存在这样一个序列，则称系统处于不安全状态，不安全

44、状态个序列，则称系统处于不安全状态，不安全状态一般会导致死锁。一般会导致死锁。2安全状态实例安全状态实例 P953由安全状态向不安全状态的转换由安全状态向不安全状态的转换 如果不按照安全序列分配资源，则系统可能如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。会由安全状态进入不安全状态。单种资源的银行家算法描述：假定一个银行家拥有资金，数量为，被N个客户共享。银行家对客户提出下列约束条件：每个客户必须预先说明自己所要求的最大资金量每个客户每次提出部分资金量申请和获得分配如果银行满足了客户对资金的最大需求量，那么，客户在资金运作后，应在有限时间内全部归还银行。银行则保证：若一个客

45、户所要求的最大资金量不超过，则银行一定接纳该客户，并处理他的资金需求；银行在收到一个客户的资金申请时，可能因资金不足而让客户等待，但保证在有限时间内让客户获得资金。（1） 可利用资源向量可利用资源向量Availablem。每一个元素代表一类可利用的资源数目，其初始值每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果该类资源的分配和回收而动态地改变。如果Availablej=K，则表示系统中现有，则表示系统中现有Rj类资源类资源K个。个。 （2） 最大需求矩阵最大需求矩

46、阵Maxnm。定义了系统中定义了系统中n个进程中的每一个进程对个进程中的每一个进程对m类资源类资源的最大需求。如果的最大需求。如果Maxij=K，则表示进程，则表示进程i需要需要Rj类资源的最大数目为类资源的最大数目为K。（3）分配矩阵）分配矩阵Allocationnm定义了系统中每一类资源当前已分配给每一进程的定义了系统中每一类资源当前已分配给每一进程的资源数。如果资源数。如果Allocationij=K，则表示进程，则表示进程i当前当前已分得已分得Rj类资源的数目为类资源的数目为K。（4）需求矩阵）需求矩阵Neednm用以表示每一个进程尚需的各类资源数。如果用以表示每一个进程尚需的各类资源

47、数。如果Needij=K，则表示进程，则表示进程i还需要还需要Rj类资源类资源K个，方个，方能完成任务。能完成任务。Needij=Maxij-Allocationij 设设Requesti是进程是进程Pi的资源请求向量，如果的资源请求向量，如果Requestij =K，表示进程，表示进程Pi需要需要K个个Rj类型的资源。类型的资源。当当Pi发出资源请求后，系统按下述步骤检查：发出资源请求后，系统按下述步骤检查：（1）如果）如果RequestijNeedij ，便转向，便转向步骤步骤2；否则认为出错，因为它所需要的资源数已超；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。过它所宣布的

48、最大值。 （2）如果）如果RequestijAvailablej，便转向，便转向步骤步骤(3)；否则，表示尚无足够资源，；否则，表示尚无足够资源，Pi须等待。须等待。 （3）系统试着把资源分配给进程）系统试着把资源分配给进程Pi，并修，并修改下面数据结构中的数值：改下面数据结构中的数值：Availablej=Availablej-Requestij;Allocationij=Allocationij+Requestij;Needij=Needij-Requestij;（4）系统执行安全性算法，检查此次资源）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程式将资源分配给进程Pi，以完成本次分配；否则，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状将本次的试探分配作