操作系统课件：调度与死锁

调度与死锁一个作业从提交到完成通常要经历多级调度4.1调度的层次在不同操作系统中所采用的调度层次不完全相同。有的系统中仅采用一级调度，而在另一些系统中则可能采用两级或三级调度。

处理机的三级调度处理机的三级调度：作业调度进程调度交换调度

调度的层次运行就绪阻塞进程调度挂起阻塞挂起就绪中级调度创建退出作业调度4.1.1作业调度Jobscheduler作业调度又称高级调度、宏观调度或长程调度(Long-termscheduler)，其主要任务是按一定的原则从外存上处于后备状态的作业中选择一个或多个作业，给它们分配内存、输入/输出设备等必要的资源，并建立相应的进程，以使该作业具有获得竞争处理机的权利。作业调度的运行频率较低，通常为几分钟一次。4.1.2进程调度Processscheduler进程调度又称低级调度、微观调度或短程调度(Short-termscheduler)，其主要任务是按照某种策略和方法从就绪队列中选取一个进程，将处理机分配给它。进程调度的运行频率很高，一般几十毫秒要运行一次。

4.1.3中级调度中级调度又称中程调度(Mediumtermscheduling)或交换调度，其功能是将内存中暂时不用的信息移到外存，以腾出空间给内存中的进程使用，或将需要的信息从外存读入内存。引入中程调度的目的是提高内存利用率和系统吞吐量。中级调度的运行频率介于两者之间。4.1.4调度性能评价由于操作系统的类型及目标不同，因此选择的调度策略及算法也不同。调度性能的评价准则有很多评价准则，下面介绍几种主要的评价准则：CPU利用率(CPUutilization)高系统吞吐量大。系统吞吐量(throughput)表示单位时间内CPU完成作业的数量。周转时间(turnaroundtime)短。响应时间快。响应时间(responsetime)是指从用户提交请求到系统首次产生响应所用的时间。周转时间Turnaroundtime作业的周转时间是指从作业提交到作业完成之间的时间间隔。平均周转时间是指多个作业的周转时间的平均值。ｎ个作业的平均周转时间：T=（T1＋T2＋

…

＋Tn）／n（Ti为作业ｉ的周转时间）带权周转时间带权周转时间是指作业周转时间与作业实际运行时间的比。平均带权周转时间是指多个作业的带权周转时间的平均值。ｎ个作业的平均带权周转时间：W＝（W1＋W2＋

…

＋Wn）/n（Wi为作业ｉ的带权周转时间）周转时间及带权周转时间例各作业感受如何?

12.91带权周转时间

6

30

1.5等待时间

1.2

3

3周转时间10.2

11.2

11完成时间0.2

0.12运行时间

9

8.2

8提交时间

C

B

A作业4.2作业调度作业是用户在一次解题或一个事务处理过程中要求计算机系统所做工作的集合，包括用户程序、所需的数据及命令等。计算机系统在完成一个作业的过程中所做的一项相对独立的工作称为一个作业步。例如，在编制程序过程中通常要进行编辑输入、编译、链接、运行几个作业步。

4.2.1作业的状态及转换作业从提交到完成要经历四种状态：提交状态：用户作业由输入设备向系统外存输入时作业所处的状态。后备状态：作业输入到外存后，系统为其建立了作业控制块，并把它插入到后备作业队列中等待调度运行。运行状态：作业在内存中执行。完成状态：作业正常或异常结束，但作业占有的资源还未被系统全部回收。收容作业状态转换图阻塞就绪执行I/O请求I/O完成时间片完提交作业录入后备作业调度进程调度运行状态完成作业调度4.2.2作业调度作业调度程序主要完成以下工作记录进入系统的各个作业情况。从后备作业中挑选一些作业投入执行。为被选中的作业做好执行前的准备工作。在作业运行结束或运行过程中因某种原因需要撤离时，作业调度程序还要完成作业的善后处理工作。作业控制块为管理作业，系统设置了作业控制块。系统通过JCB感知作业的存在，JCB是作业存在的唯一标志。通常作业控制块中包括的主要内容有：资源要求。资源使用情况。作业的控制方式、类型和优先级等。作业名、作业状态。资源要求资源要求是指作业运行需要的资源情况，包括：估计运行时间、最迟完成时间、需要的内存容量、外设类型及数量等。资源使用情况资源使用情况包括作业进入系统的时间、开始运行时间、已运行时间、内存地址、外设台号等。作业控制方式、类型和优先级作业的控制方式有联机作业控制和脱机作业控制。从不同角度出发可以对作业进行不同的分类，如终端型和批量型，作业的优先级是指作业进入系统运行的优先级别，优先级高的作业可以优先进入系统运行。作业名、作业状态记录作业的标识信息及作业的当前状态。4.3进程调度-4.3.1进程调度的功能进程调度程序主要完成以下功能：记录系统中所有进程的状态、优先数和资源情况。选择获得处理机的进程。实施处理机的分配及回收。引起进程调度的原因正在运行进程结束运行进程因某种原因阻塞，如P操作、I/O等从系统调用或中断返回时，有进程进入就绪队列且就绪队列为空，或进程优先级高于当前运行进程且为剥夺调度方式时间片用完4.3.2进程调度的方式进程调度有两种方式：抢占(Preemptive)方式非抢占(Nonpreemptive)方式抢占方式抢占方式：又称剥夺方式、可剥夺方式。这种调度方式是指允许调度程序根据某种原则去停止正在执行的进程，将已分配给该进程的处理机重新分配给其他进程。抢占原则有：优先权、时间片。

非抢占方式非抢占方式：又称非剥夺方式、不可剥夺方式、不可抢占方式。这种调度方式是指一旦将处理机分配给某进程后，便让该进程一直执行，直到该进程完成或发生某事件而进入阻塞状态，才把处理机分配给其他进程。非抢占方式中引起进程调度的因素有：进程结束、因某种原因而阻塞、执行同步原语等。特点：简单，系统开销小，但无法处理紧急任务。4.4调度算法调度算法(SchedulingAlgorithms)是指根据系统资源分配策略所规定的资源分配算法。本章的算法有些适合作业调度，有些适合进程调度，有些适用于两者。4.4.1先来先服务调度算法先来先服务算法(First-come,first-served)既可用于作业调度，也可用于进程调度。在作业调度中：从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源，创建进程，然后放入就绪队列。进程调度中：从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或因等待某一事件而阻塞时才释放处理机。设有4道作业，它们的提交时间及执行时间如下表，若按先来先服务调度算法进行调度，试计算4个作业的平均周转时间和平均带权周转时间。（时间单位：小时，以十进制计算）。先来先服务调度算法例

作业提交时间估计运行时间1102210.21310.40.5410.50.3作业周转时间及带权周转时间的计算平均周转时间T=(2.0＋2.8＋3.1＋3.3)/4=2.8平均带权周转时间W=(1＋2.8＋6.2＋11)/4=5.25116.22.81带权周转时间3.33.12.82周转时间13.813.51312完成时间13.5131210开始时间0.30.512运行时间10.510.410.210提交时间4321作业先来先服务算法特点算法简单，易于实现，但不利于短作业及I/O繁忙型作业。4.4.2短作业优先调度算法在作业调度中，从后备队列中选择一个或多个估计运行时间最短的作业，将它们调入内存运行。在进程调度中，从就绪队列中选择一个估计运行时间最短的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或因等待某一事件而阻塞时才释放处理机。Shortest-job-first短作业优先调度算法例平均周转时间T=(2.0＋1.8＋2.4＋3.6)/4=2.45平均带权周转时间W=(1＋6＋4.8＋3.6)/4=3.8564.83.61带权周转时间1.82.43.62周转时间12.312.813.812完成时间1212.312.810开始时间0.30.512运行时间10.510.410.210提交时间4321作业短作业优先调度算法的特点算法调度性能较好，如上例中，先来先服务短作业优先平均周转时间2.82.45平均带权周转时间5.25

3.85但对长作业不利，未考虑作业的紧迫程度，运行时间为估计。最短剩余时间优先调度算法最短进程优先调度算法可以是非抢占式的，也可以是抢占式的。若无特别说明，通常是指非抢占式的算法。抢占式的最短进程优先调度算法也称为最短剩余时间优先调度算法(shortest-remaining-time-first)，即当一个新进程进入就绪队列时，若其需要的运行时间比当前运行进程的剩余时间短，则它将抢占CPU。最短剩余时间优先算法例时间：1.42.6712.125带权周转时间724417周转时间1026517完成时间51710开始时间5948运行时间3210提交时间

D

C

B

A作业0A12B34510DA1726C最短剩余时间优先算法例（续）平均周转时间T=(17＋4＋24＋7)/4=13平均带权周转时间W=(2.125＋1＋2.67＋1.4)/4=1.81.42.6712.125带权周转时间724417周转时间1026517完成时间51710开始时间5948运行时间3210提交时间

D

C

B

A作业最短平均周转时间当一批作业同时到达时，最短作业优先调度算法才能获得最短平均周转时间。设一组作业p1、p2、…、pn，其运行时间为t1、t2、…、tn，且假定t1<t2<…<tn，则短作业优先调度算法的总周转时间为：t1+（t1+t2）+…+（t1+…+tn）=n*t1+（n-1）t2+…+tn最短平均周转时间（续）可以证明：若a1≤a2≤…≤an且b1≤b2≤…≤bn，则a1bn+a2bn-1+…+anb1≤a1bi1+a2bi2+…+anbin

≤a1b1+a2b2+…+anbn

其中i1、i2、…、in是1、2、…、n的一个排列。4.4.3优先级调度算法在作业调度中，从后备作业队列中选择若干优先级高的作业调入内存。在进程调度中，将处理机分配给就绪队列中优先级最高的进程。优先级(Priority)表示进程的重要性及运行优先性，通常用优先数来衡量。在某些系统中，优先数越大优先级越高；而在另一些系统中，优先数越大优先级越小。按调度方式对优先级调度算法分类非抢占式优先级调度算法：系统一旦将处理机分配给就绪队列中优先级最高的进程后，该进程便一直运行下去，直到完成或因发生某事件使该进程放弃处理机时，系统才将处理机分配给另一个更高优先级的进程。抢占式优先级调度算法：将处理机分配给优先级最高的进程，使之运行。在进程运行过程中，一旦出现了另一个优先级更高的进程时，进程调度程序就停止原运行进程，而将处理机分配给新出现的高优先级进程。

优先级的类型优先级分为两种：静态优先级动态优先级静态优先级静态优先级是在创建进程时确定的，确定之后在整个进程运行期间不再改变。确定依据有：进程类型：系统，用户进程对资源的需求：执行时间，资源数量用户要求：紧迫程度特点：简单易行，系统开销小，但不精确。动态优先级动态优先级是指在创建进程时，根据进程的特点及相关情况确定一个优先级，在进程运行过程中再根据情况的变化调整优先级。确定原则有：占用CPU时间，等待时间。例：优先数=CPU使用时间/2+基本优先数CPU使用时间衰减函数:Decay(CPU使用时间)=CPU使用时间/24.4.4时间片轮转调度算法时间片轮转法(RoundRobin)：系统将所有就绪进程按到达时间的先后次序排成一个队列，每次调度时把CPU分配给队首进程，并令其执行一个时间片。当时间片用完时，停止该进程的执行，将它送至就绪队列末尾等待下一次执行，然后再把处理机分配给就绪队列中的新队首进程。如此不断循环，直至完成为止。时间片轮转算法例设有A、B、C、D、E五个进程，其到达时间分别为0、1、2、3、4，要求运行时间依次为3、6、4、5、2，采用时间片轮转调度算法，当时间片大小为1和4时，试计算其平均周转时间和平均带权周转时间。时间片大小为1A、B、C、D、E要求运行时间依次为3、6、4、5、2，到达时间依次为0、1、2、3、4。

1：B运行，A等待；2：A运行，CB等待；3：C运行，BDA等待；4：B运行，DAEC等待；5：D运行，AECB等待；6：A运行，ECBD等待；7：E运行，CBD等待；8：C运行，BDE等待；9：B运行，DEC等待；10：D运行，ECB等待；11：E运行，CBD等待；12：C运行，BD等待；13：B运行，DC等待；14：D运行，CB等待；15：C运行，BD等待；16：B运行，D等待；17：D运行，B等待；18：B运行，D等待；19：D运行，0：A运行；时间片为1的周转时间平均周转时间T=(7＋18＋14＋17+8)/5=12.8平均带权周转时间W=(2.33＋3＋3.5＋3.4+4)/5=3.2463.43.532.33带权周转时间1714187周转时间2016197完成时间5310开始时间5463运行时间3210提交时间

D

C

B

A作业4812724

E时间片大小为4A、B、C、D、E要求运行时间依次为3、6、4、5、2，到达时间依次为0、1、2、3、4。0：A运行，BCD依次到达；3：B运行，CD等待，后E到达；7：C运行，DEB等待；11：D运行，EB等待；15：E运行，BD等待；17：B运行，D等待；19：D运行A、B、C、D、E开始时间依次为0、3、7、11、15；结束时间依次为3、19、11、20、17。时间片为4的周转时间平均周转时间T=(3＋18＋9＋17+13)/5=12平均带权周转时间W=(1＋3＋2.25＋3.4+6.5)/5=3.233.42.2531带权周转时间179183周转时间2011193完成时间11730开始时间5463运行时间3210提交时间

D

C

B

A作业6.513171524

E时间片大小的选择若时间片太大，所有进程都能在一个时间片内完成，则时间片轮转算法退化为先来先服务；若时间片太小，则进程调度频繁，系统开销增加。因此时间片大小选择应适当。现代操作系统的时间片一般为10-100ms，上下文切换时间一般少于10us。确定时间片大小应考虑的因素系统对响应时间的要求：响应时间=时间片*进程数。进程数一定，则时间片与系统响应时间成正比。就绪队列中的进程数目：若响应时间固定，则时间片与就绪进程数成反比。系统处理能力：系统速度快，则时间片可以更短。时间片轮转算法的特点及改进对偏重I/O的进程不公平。为此改进为虚拟时间片轮转算法。虚拟时间片轮转算法：新进程基于FCFS进入就绪队列，进程用完时间片后也进入就绪队列，进程因I/O阻塞进入I/O队列，I/O完成时进程进入附加队列，附加队列的优先级高于就绪队列，当进程从附加队列被调度时，其运行时间不超过上次发生中断时剩余的时间。虚拟时间片轮转调度示意图CPU新进程就绪队列调度超时优先级高附加队列I/O队列请求I/OI/O完成4.4.5高响应比优先调度算法高响应比优先调度算法是对短作业优先调度算法和先来先服务调度算法的一种综合。响应比响应比定义如下：响应比＝作业响应时间/估计运行时间由于响应时间为作业进入系统后的等待时间加上估计运行时间。因此响应比＝1＋作业等待时间/估计运行时间高响应比优先调度算法思想在每次调度作业运行时，先计算后备作业队列中每个作业的响应比，然后挑选响应比最高者投入运行。特点：有利于短作业-----等待时间相同，短作业优先，考虑等待时间----运行时间相同，等待时间长的作业优先运行。最高响应比优先算法例设有A、B、C、D、E五个进程，其到达时间分别为0、1、2、3、4，要求运行时间依次为3、6、4、5、2，采用最高响应比优先调度算法，试计算其平均周转时间和平均带权周转时间。分析作业的调度顺序A、B、C、D、E的到达时间依次为0、1、2、3、4，要求运行时间依次为3、6、4、5、20：A运行，BCD依次到达；3：rB=1+2/6，

rC=1+1/4，

rD=1；B先运行。9：rC=1+7/4，

rD=1+6/5，

rE=1+5/2；E先运行。11：rC=1+9/4，

rD=1+8/5；C先运行。由此可知作业的运行顺序为A、B、E、C、D。周转时间的计算顺序A、B、E、C、D平均周转时间T=(3＋8＋13＋17+7)/5=9.6平均带权周转时间W=(1＋1.33＋3.25＋3.4+3.5)/5=2.4963.43.251.331带权周转时间171383周转时间201593完成时间151130开始时间5463运行时间3210提交时间

D

C

B

A作业3.5711924

E4.4.6多级队列调度算法MultilevelQueueScheduling实现思想：根据作业性质或类型不同，将进程就绪队列分为多个，每个队列采用不同的调度算法。例如：终端型作业为前台作业，批处理作业为后台作业。前台采用时间片轮转算法，后台采用先来先服务，前台作业的优先级高。4.4.7多级反馈队列调度算法MultilevelFeedbackQueueScheduling应设置多个就绪队列，并为每个队列赋予不同的优先级。第1个队列的优先级最高，第2队列次之，其余队列的优先级逐次降低。每个队列中进程执行的时间片大小也各不相同，进程所在队列的优先级越高，其相应的时间片就越短。多级反馈队列调度算法（2）当一个新进程进入系统时，首先将它放入第1个队列的末尾，按先来先服务的原则排队等待调度。当轮到该进程执行时，如能在此时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第2队列的末尾，再同样地按先来先服务原则等待调度执行。如此下去，最后一个队列中使用时间片轮转调度算法。多级反馈队列调度算法（3）仅当第1个队列为空时，调度程序才调度第2队列中的进程运行；仅当第1个至第（i－1）个队列均为空时，才会调度第i个队列中的进程运行。当处理机正在为第i个队列中的某进程服务时，若又有新进程进入优先级较高的队列中，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在执行进程放回第i个队列末尾，重新将处理机分配给新进程。多级反馈队列调度算法示意图就绪队列1CPU就绪队列2就绪队列nCPUCPU完成完成完成多级反馈队列调度算法例设有A、B、C、D、E五个进程，其到达时间分别为0、1、3、4、5，要求运行时间依次为3、8、4、5、7，采用多级反馈队列调度算法，系统中共有3个队列，其时间片依次为1、2和4，试计算其平均周转时间和平均带权周转时间。13：EE运行，BCD等待；调度分析A、B、C、D、E到达时间依次为0、1、3、4、5，要求运行时间依次为3、8、4、5、71：B运行，A等待；2：A运行，B等待；3：C运行，BA等待；4：D运行，BAC等待；5：E运行，BACD等待；6：BB运行，ACDE等待；8：A运行，CDE等待；B等待9：CC运行，DE等待；B等待11：DD运行，E等待；BC等待15：BBBB运行，CDE等待；19：C运行，DEB等待；20：DD运行，EB等待；22：EEEE运行，B等待；0：A运行；26：B运行。周转时间的计算平均周转时间T=(9＋26＋17＋18+21)/5=18.25平均带权周转时间W=(3＋3.25＋4.25＋3.6+3)/5=3.423.64.253.253带权周转时间1817269周转时间2220279完成时间4310开始时间5483运行时间4310提交时间

D

C

B

A作业32126575

E多级反馈队列调度算法的性能多级反馈队列调度算法能较好满足各类用户的需求：终端型用户：大多能在一个时间片内完成，响应时间较短；短批处理作业用户：能在前几个队列完成，周转时间较短；长批处理作业用户：依次在1～n队列中运行，不会长时间得不到处理。4.5死锁Deadlocks

多道程序的并发执行可以改善系统的资源利用率，但也可能导致死锁的发生。4.5.1死锁的概念死锁是指多个进程因竞争系统资源或相互通信而造成的一种僵局，若无外力作用，这些进程都将永远不能向前推进。死锁例：当两辆车在十字路口逼近时，它们要完全停下来，且在一辆车开走之前，另一辆车不能启动。日常生活中的死锁例假设一条河上有一座独木桥，若桥两端的人相向而行……此时死锁发生了

4.5.2死锁产生的原因和必要条件死锁产生的原因是与资源的使用相关。下面介绍资源分类。可剥夺和非剥夺资源可剥夺资源是指某进程获得这类资源后，该资源可以被其他进程或系统剥夺。如CPU，存储器。非剥夺资源又称不可剥夺资源，是指系统将这类资源分配给进程后，再不能强行收回，只能在进程使用完后主动释放。如打印机、读卡机。注意：竞争可剥夺资源不会产生死锁！永久性资源和消耗性资源永久性资源：可顺序重复使用的资源。如打印机。消耗性资源：由一个进程产生，被另一个进程使用短暂时间后便无用的资源，又称为临时性资源。如消息。竞争永久性资源和临时性资源都可能产生死锁。死锁产生的原因死锁产生的原因是：竞争资源：多个进程竞争资源，而资源又不能同时满足其需求。进程推进顺序不当：进程申请资源和释放资源的顺序不当。竞争非剥夺资源引起的死锁竞争非剥夺资源例。如，打印机R1和读卡机R2供进程P1和P2共享。P1R1R2P2竞争消耗性资源引起的死锁如消息通信按下述顺序进行，则不会发生死锁：P1：...Release(S1)；Request(S2)；...P2：...Release(S2)；Request(S1)；...若按下述顺序，则可能发生死锁：P1：...Request(S2)；Release(S1)；...P2：...Request(S1)；Release(S2)；...P1S2S1P2进程推进顺序不当引起的死锁当进程P1、P2共享资源A、B时，若推进顺序合法则不会产生死锁，否则会产生死锁。合法的推进路线：①②③不合法的推进线路：④P2释放AP2释放BP2申请AP2申请BP1申请AP1申请BP1释放AP1释放B①②③④死锁区死锁点死锁产生的必要条件互斥条件：在一段时间内某资源仅为一个进程所占有。请求和保持条件：又称部分分配条件、占用并等待条件。当进程因请求资源被阻塞时，已分配资源保持不放。不剥夺条件：进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走。循环等待条件：死锁发生时，存在一个进程资源的循环。注意死锁是因资源竞争造成的僵局通常死锁一般至少涉及两个进程死锁与部分进程及资源相关4.5.3处理死锁的基本方法用于处理死锁的方法主要有：忽略死锁。这种处理方式又称鸵鸟算法，指像鸵鸟一样对死锁视而不见。

预防死锁：设置某些限制条件，通过破坏死锁产生的四个必要条件之一来预防死锁。避免死锁：在资源的动态分配过程中，用某种方法来防止系统进入不安全状态。检测死锁及解除：系统定期检测是否出现死锁，若出现则解除死锁。4.5.4死锁的预防预防死锁。通过破坏产生死锁的四个必要条件中的一个或几个条件，来防止发生死锁。特点：较易实现，广泛使用，但限制较严，资源利用率低。破坏互斥条件互斥是设备本身固有的属性，此条件不能破坏。破坏请求和保持条件要求进程一次申请它所需的全部资源，若有足够的资源则分配给进程，否则不分配资源，进程等待。这种方法称为静态资源分配法。特点：简单、安全且易于实现；但资源利用率低，进程延迟运行。破坏不剥夺条件一个已获得某些资源的进程，若新的资源请求得不到满足，则它必须释放已获得的所有资源。特点：实现较复杂，释放已获得资源可能造成前一段工作的失效，重复申请和释放资源会增加系统开销，降低系统吞吐量。

破坏循环等待条件将所有资源按类型排队，并赋予不同序号，要求进程均严格按照序号递增的次序请求资源，同类资源一次申请完。这种方法称为有序资源分配法。特点：比前两种方法资源利用率高，吞吐量大。但要求资源序号相对稳定，从而限制了新设备的增加；使用资源的顺序与系统规定顺序不同，造成资源的浪费；使用资源的次序限制用户编程。为什么有序资源分配法可以防止死锁1假设循环已经出现并且含于环中的进程是p0、…、pn，这意味着pi正占有ri类资源，而请求ri+1类资源，设函数f能获得资源序号，则有f（ri）<f（ri+1），故f（r0）<f（r1）<…<f（rn）<f（r0）。矛盾，原假设不成立。r1pnp0p1r0…rnr2为什么有序资源分配法可以防止死锁2采用有序资源分配法，系统中的进程必须按照资源编号的升序申请资源。因此在任一时刻，系统中总会存在一个进程，它占有已申请资源中编号最高的资源，且它继续请求的资源必定是空闲的，因而它可以一直向前推进直至完成。当该进程运行完成后，即会释放它所占有的全部资源。这样剩余进程集合中又会存在一个进程，它占有已申请资源中编号最高的资源，且它继续请求的资源必定是空闲的，因而它也可以一直向前推进直至完成。以此类推，最终所有进程均可运行完成，故不会发生死锁。4.5.5死锁的避免死锁的避免是在资源的动态分配过程中，用某种方法防止系统进入不安全状态，从而避免死锁的发生。特点：以较弱的限制获得较高的利用率，但实现有一定难度。安全状态在避免死锁的方法中，允许进程动态地申请资源，系统在进行资源分配之前，先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态，便将资源分配给进程，否则进程等待。安全状态是指系统能按某种顺序如<P1、P2…、Pn>来为每个进程分配其所需的资源，直至最大需求，使每个进程都可以顺利完成，则称此时的系统状态为安全状态，称序列<

P1、P2、…、Pn>为安全序列。不安全状态若某一时刻系统中不存在一个安全序列，则称此时的系统状态为不安全状态。进入不安全状态后，便可能进而进入死锁状态；因此避免死锁的本质是使系统不进入不安全状态。安全状态例T0时刻，系统资源状态如下：进程最大需求已分配需要可用

P110553

P2422P3927这时可用资源能满足P2的需要，P2获得运行需要的所有资源并能顺利运行结束。P2运行结束的系统资源状态这时可用资源能满足P1的需要，P1获得运行需要的所有资源并能顺利运行结束。进程最大需求已分配需要可用

P110555

P2422P3927P2、P1运行结束的统资源状态这时可用资源能满足P3的需要，P3获得运行需要的所有资源并能顺利运行结束。因此存在一个安全序列<P2、P1、P3>，系统状态安全。进程最大需求已分配需要可用

P1105510

P2422P3927由安全状态向不安全状态转换若在T0之后，又将1个资源分配给了P3，则系统进入了不安全状态：进程最大需求已分配需要可用

P110552

P2422P3936银行家算法Banker’sAlgorithm最具代表性的死锁避免算法是Dijkstra的银行家算法。银行家算法要求新进程进入系统时，必须说明其可能需要的每类资源最大数量

假定系统中有n个进程P1、P2、…、Pn

，m类资源R1、R2、…、Rm，银行家算法中使用的数据结构如下：1）可用资源向量Available可利用资源向量Available是一个含有m个元素的数组，其中每一个元素代表一类资源的空闲资源数目。如果Available(j)＝k，表示系统中现有空闲的Rj类资源k个。2）最大需求矩阵Max最大需求矩阵Max是一个n×m的矩阵，定义了系统中每个进程对m类资源的最大需求数目。如果Max(i，j)＝k，表示进程Pi需要Rj类资源的最大数目为k。3）分配矩阵Allocation分配矩阵Allocation是一个n×m的矩阵，定义了系统中每一类资源当前已分配给每一个进程的资源数目。如果Allocation(i，j)＝k，表示进程Pi当前已分到Rj类资源的数目为k。Allocationi表示进程Pi的分配向量，由矩阵Allocation的第i行构成。4）需求矩阵Need需求矩阵Need是一个n×m的矩阵，它定义了系统中每一个进程还需要的各类资源数目。如果Need(i，j)＝k，表示进程Pi还需要Rj类资源k个。Needi表示进程Pi的需求向量，由矩阵Need的第i行构成。三个矩阵间的关系：Need(i，j)＝Max(i，j)－Allocation(i，j)银行家算法设Requesti是进程Pi的请求向量，Requesti(j)＝k表示进程Pi请求分配Rj类资源k个。当Pi发出资源请求后，系统按下述步骤进行检查：银行家算法描述1）如果Requesti≤Needi

，则转向步骤2；否则出错。2）如果Requesti≤Available，则转向步骤3；否则Pi等待。3）试分配并修改数据结构：

Available＝Available－Requesti

；Allocationi＝Allocationi＋Requesti；Needi＝Needi－Requesti；4）系统执行安全性算法，检查此次资源分配是否安全。若安全，才正式分配；否则，试分配作废，让进程Pi等待。安全性算法(1)SafetyAlgorithm1）设置两个向量Work：表示系统可提供给进程继续运行的各类空闲资源数目，含有m个元素，执行安全性算法开始时，Work＝Available。

Finish：表示系统是否有足够的资源分配给进程，使之运行完成，开始时，Finish(i)＝false；当有足够资源分配给进程Pi时，令Finish(i)＝true。2）从进程集合中找到一个能满足下述条件的进程：Finish(i)=false；Needi≤Work；如找到则执行步骤3；否则执行步骤4。安全性算法(2)3）当进程Pi获得资源后，可顺利执行直到完成，并释放出分配给它的资源，故应执行：

Work＝Work＋Allocationi；Finish(i)＝true；Gotostep2；4）若所有进程的Finish(i)都为true，则表示系统处于安全状态；否则，系统处于不安全状态。银行家算法例假定系统中有5个进程P0、P1、P2、P3、P4和三种类型的资源A、B、C，数量分别为12、5、9，在T0时刻的资源分配情况如下所示。资源情况进程

MaxAllocation

Need

Available

ABC

ABC

ABC

ABCP0853110743332

P1323201122

P2903303600

P3222211011

P4533102431T0时刻的安全性利用安全性算法对T0时刻的资源分配情况进行分析，可得如下所示的T0时刻的安全性分析。

T0时刻的安全性检查Need0：7,4,3Need1：1,2,2Need2：6,0,0Need3：0,1,1Need4：4,3,1Alloc0：1,1,0Alloc1：2,0,1Alloc2：3,0,3Alloc3：2,1,1Alloc4：1,0,2Avail332

true

true

true

truetrueFinish533201122332P112591107431149

P01149303600846

P2846102431744

P4

ABC

ABCABCABC744211011533

P3Work+Alloc

AllocNeed

Work资源情况进程T0时刻是安全的从上述分析得知，T0时刻存在着一个安全序列<P1、P3、P4、P2、P0>，故系统是安全的。P1请求资源P1发出请求向量Request1

(1，0，2)，系统按银行家算法进行检查：1）Request1(1，0，2)≤Need1(1，2，2)2）Request1(1，0，2)≤Available(3，3，2)3）系统先假定可为P1分配资源，并修改Available、Allocation1、Need1向量，由此形成的资源变化情况如下所示。

为P1试分配资源后4）再利用安全性算法检查此时系统是否安全，可得如下所示的安全性分析。资源情况进程

MaxAllocation

Need

Available

ABC

ABC

ABC

ABCP0853110743

230

P1323

303

020

P2903303600

P3222211011

P4533102431P1申请资源后的安全性检查Need0：7,4,3Need1：0,2,0Need2：6,0,0Need3：0,1,1Need4：4,3,1Alloc0：1,1,0Alloc1：3,0,3Alloc2：3,0,3Alloc3：2,1,1Alloc4：1,0,2Avail230

true

true

true

truetrueFinish533

303020

230P112591107431149

P01149303600846

P2846102431744

P4

ABC

ABCABCABC744211011533

P3Work+Alloc

AllocNeed

Work资源情况进程可以为P1分配资源从上述分析得知，可以找到安全序列<P1、P3、P4、P0、P2>，系统安全，可以分配。P4请求资源P4发出请求向量Request4(3，3，0)，系统按银行家算法进行检查：1）Request4(3，3，0)≤Need4(4，3，1)2）Request4(3，3，0)＞Available(2，3，0)，让P4等待。P0请求资源P0发出请求向量Request0

(0，2，0)，系统按银行家算法进行检查：1）Request0(0，2，0)≤Need0(7，4，3)2）Request0(0，2，0)≤Available(2，3，0)3）系统先假定可为P0分配资源，并修改有关数据，如下所示。

为P0试分配资源后4）再利用安全性算法检查此时系统是否安全。从上表中可以看出，可用资源Available（2，1，0）已不能满足任何进程的需要，故系统进入不安全状态，此时系统不分配资源。资源情况进程

MaxAllocation

Need

Available

ABC

ABC

ABC

ABCP0853

130

723

210

P1323303020

P2903303600

P3222211011

P45331024314.5.6死锁的检测及解除通过系统的检测机构及时地检测出死锁的发生，然后采取某种措施解除死锁。特点：死锁检测和解除可使系统获得较高的利用率，但是实现难度最大。资源分配图

系统死锁可以利用资源分配图描述。资源分配图(

Resource-AllocationGraph)又称进程—资源图，由一组结点N和一组边E所构成：N被分成两个互斥的子集：进程结点子集P＝{p1，p2，…，pn}，资源结点子集R＝｛r1，r2，…，rm｝。E是边集，它连接着P中的一个结点和R中的一个结点，e＝<pi，rj>是资源请求边，e＝<rj，pi>是资源分配边。

通常，用圆圈代表一个进程，用方框代表一类资源，方框中的一个点代表一类资源中的一个资源。资源分配图例p1p2r1r2死锁判定法则将资源分配图简化可以检测系统状态S是否为死锁状态，方法如下：在资源分配图中，找出一个既不阻塞又非孤立的进程结点pi，进程pi获得了它所需要的全部资源，能运行完成然后释放所有资源。这相当于消去pi的所有请求边和分配边，使之成为孤立结点。进程pi释放资源后，可以唤醒因等待这些资源而阻塞的进程，从而可能使原来阻塞的进程变为非阻塞进程。在进行一系列化简后，若能消去图中所有的边，使所有进程都成为孤立结点，则称该图是可完全简化的；若不能使该图完全化简，则称该图是不可完全简化的。

死锁定理可以证明：所有的简化顺序将得到相同的不可简化图。S为死锁状态的条件是当且仅当S状态的资源分配图是不可完全简化的。该条件称为死锁定理。资源分配图简化例p1p2r1r2p1p2r1r2p1p2r1r2资源分配图简化例2下图是否存在死锁？p1p2p3r1r4r2r3此图不可完全简化，存在死锁。资源分配图简化例3下图是否存在死锁？p2p3p4r1r2p1此图可以完全简化，不存在死锁。死锁检测算法中的数据结构可利用资源向量Available：表示m类资源中每类资源的可用数目。请求矩阵Request：表示每个进程当前对各类资源的请求数目。分配矩阵Allocation：表示每个进程当前已分配的资源数目。工作向量Work：表示系统当前可提供资源数。进程集合L：记录当前已不占用资源的进程。死锁检测的算法Work=Available;L=<Li|Allocationi=0∩Requesti=0>forallLiLdo{if（Requesti≤Work）{Work=Work+Allocationi;L=L∪Li;}}deadlock=(L==<p1,p2,…pn>)死锁解除一旦检测出系统中出现了死锁，就应将陷入死锁的进程从死锁状态中解脱出来，常用的死锁解除方法有两种：资源剥夺法：当发现死锁后，从其他进程那里剥夺足够数量的资源给死锁进程，以解除死锁状态。撤消进程法：最简单的方法是撤消全部死锁进程，使系统恢复到正常状态。但这种做法付出的代价太大。另一方法是按照某种顺序逐个撤消死锁进程，直到有足够的资源供其他未被撤消的进程使用，消除死锁状态为止。处理死锁的综合方法单独使用处理死锁的某种方法不能全面解决OS中遇到的所有死锁问题。综合解决的办法是：将系统中的资源按层次分为若干类，对每一类资源使用最适合它的办法解决死锁问题。即使发生死锁，一个死锁环也只包含某一层次的资源，因此整个系统不会受控于死锁。综合方法例将系统的资源分为四个层次：内部资源：由系统本身使用，如PCB，采用有序资源分配法。主存资源：采用资源剥夺法。作业资源：可分配的设备和文件。采用死锁避免法。交换空间：采用静态分配法。习题P1043（1）3（5）3（6）3（9）选择题1在下列调度层次中，所有操作系统中都必须配置的调度层次是_____。A．作业调度B．进程调度

C．交换调度D．中级调度在分时操作系统中，进程调度经常采用_____算法。A．先来先服务B．最高优先权C．短进程优先D．时间片轮转选择题2_____优先权是在创建进程时确定的，确定之后在整个进程运行期间不再改变。A.静态B.作业C.资源

D.动态设有四个作业同时到达，每个作业的执行时间均为2小时，它们在一台处理器上按单道方式运行，则平均周转时间为_____。A.8小时

B.2.5小时C.5小时

D.1小时选择题3现有3个同时到达的作业J1、J2和J3，它们的执行时间分别是T1、T2和T3，且T1＜T2＜T3。系统按单道方式运行且采用短作业优先算法，则平均周转时间是_____。A.(3T1+2T2+T3)/3B.(T1+T2+T3)/3C.(T1+2T2+3T3)/3D.T1+T2+T3

_____是指从作业提交给系统到作业完成的时间间隔。A.运行时间

B.等待时间C.周转时间D.响应时间选择题4下述作业调度算法中，________调度算法与作业的估计运行时间有关。A.先来先服务

B.短作业优先C.时间片轮转D.多级队列采用时间片轮转法进行进程调度是为了____。A．多个终端都能得到系统的及时响应

B．先来先服务C．优先级较高的进程得到及时响应

D．需要CPU最短的进程先做选择题5假设就绪队列中有10个进程，系统将时间片设为200ms，CPU进行进程切换要花费10ms。则系统开销所占的比率约为_____。

A．1％B．5％C．10％D．20％采用资源剥夺法可以解除死锁，还可以采用_____方法解除死锁。A.拒绝分配新资源

B.修改信号量C.执行并行操作D.撤消进程选择题6要防止死锁的发生，可以通过破坏这四个必要条件之一来实现，但破坏_____条件是不太实际的。A.循环等待

B.部分分配C.不可抢占D.互斥资源的有序分配策略可以破坏_____条件。A.占有且等待资源B.循环等待资源C.非抢夺资源

D.互斥使用资源选择题7在_____的情况下，系统出现死锁。A.计算机系统发生了重大故障B.有多个封锁的进程同时存在C.若干进程因竞争资源而无休止地相互等待他方释放已占有的资源D.资源数大大小于进程数或进程同时申请的资源数大大超过资源总数银行家算法在解决死锁问题中是用于_____的。A.检测死锁B.预防死锁

C.避免死锁D.解除死锁选择题8某系统中有3个并发进程，都需要同类资源4个，试问该系统不会发生死锁的最少资