第4章 调度与死锁在多道程序环境下,进程数目往往多于处理机数目,致使它们争用处理机。这就要求系统能按某种算法动态地把处理机分配给就绪队列中的一个进程,使之执行进程。分配处理机的任务是由进程调度程序完成的。本章讨论进程调度与死锁问题及相关题解。
4.1内容辅导
4.1.1 处理机调度的基本概念
1.调度的类型一个作业从提交开始直到完成,往往要经历下述三级调度:
（1）作业调度 又称宏观调度或高级调度。其主要任务是按一定的原则对外存上处于后备状态的作业进行选择,给选中的作业分配内存、输入输出设备等必要的资源,并建立相应的进程,以使该作业的进程获得竞争处理机的权利。一般在批处理系统中大多配有作业调度,而在其他系统中通常不需配置作业调度。作业调度的执行频率较低,通常为几分钟一次。
（2）进程调度 又称微观调度或低级调度。其主要任务是按照某种策略和方法选取一个处于就绪状态的进程,将处理机分配给它。进程调度的运行频率很高,一般几十毫秒要运行一次。
（3）交换调度 又称中级调度。其主要任务是按照给定的原则和策略,将处于外存对换区中的重又具备运行条件的就绪进程调入内存,或将处于内存就绪状态或内存阻塞状态的进程交换到外存对换区。交换调度主要涉及内存管理与扩充,因此在存储管理部分介绍。
2,进程调度方式所谓进程调度方式是指当某一进程正在处理机上执行时,若有某个更为重要或紧迫的进程需要进行处理,即有优先权更高的进程进入就绪队列,此时应如何分配处理机。通常有两种进程调度方式:
（1）剥夺方式 所谓剥夺调度方式是指当一个进程正在处理机上执行时,若有某个更为重要或紧迫的进程需要使用处理机,则立即暂停正在执行的进程,将处理机分配给这个更重要或紧迫的进程。抢占的原则有:
(1)优先权原则。就绪的高优先权进程有权抢占低优先权进程的CPU。
(2)短作业优先原则。就绪的短作业(进程)有权抢占长作业(进程)的CPU。
(3)时间片原则。一个时间片用完后,系统重新进行进程调度。
（2）非剥夺方式 这种方式是当某一进程正在处理机上执行时,即使有某个更为重要或紧迫的进程进入就绪队列,仍然让正在执行的进程继续执行,直到该进程完成或发生某种事件而进入完成或阻塞状态时,才把处理机分配给更为重要或紧迫的进程。
对不同的调度方式,相应的调度算法也不同,进程调度的核心问题就是采用什么算法将处理机分配给进程。
4.1.2 处理机调度算法
1.先来先服务调度算法这是一种最简单的调度算法,即按照进程进入就绪队列的先后次序来分配处理机。先来先服务算法属于非剥夺的调度方式,一旦一个进程占有处理机,就一直运行下去,直到该进程完成其工作或因等待某一事件而不能继续执行时才释放处理机。采用这种进程调度方式,若一个运行时间长的作业先占有了处理机,则会使很多晚到的运行时间短的作业等待时间过长，引起许多短作业用户的不满。因此这种方式很少被用作主要调度策略,但它常作为一种辅助调度算法使用。
(2)短作业(进程)优先(SJF/SPF)算法该算法是指短作业或短进程优先调度的算法。短进程优先调度算法是选择就绪队列中估计运行时间最短的进程技入执行,它既可采用抢占方式,也可采用非抢占方式。抢占的
SW算法通常也叫做最短剩余时间优先算法。SPF算法能有效地缩短作业的平均周转时间,
提高系统的吞吐量,但不利于长作业和紧迫作业的运行。由于估计的运行时间不一定准确,
因而它不一定能真正做到短作业优先。
（3）高晌应比优先调度(HRRN)算法
（4））最高优先权优先调度算法这是一种最常用的进程调度算法,即把处理机分配给优先权最高的进程。进程的优先权用于表示进程的重要性及运行的优先性,通常分为两种:静态优先权和动态优先权。
静态优先权是在创建进程时确定的;确定之后在整个进程运行期间不再改变。确定静态优先权的依据有进程的类型、进程所使用的资源、进程的估计运行时间等因素。进程所索取的资源越多,估计的运行时间越长,进程的优先权越低。进程类型不同,优先权也不同,如联机用户进程的优先权高于脱机用户进程的优先权。
动态优先权是指在创建进程时,根据系统资源的使用情况和进程的当前特点确定一个优先权,在进程运行过程中再根据情况的变化调整优先权。动态优先权一般根据进程占有CPU时间的长短、进程等待CPU时间的长短等因素确定。占有处理机的时间愈长,则优先权越低；等待时间越长,优先权越高。
基于优先权的调度算法还可按调度方式不同分为非剥夺优先权调度算法和可剥夺优先权调度算法。
（5）时间片轮转调度算法在这种调度算法中,系统将所有就绪进程按到达时间的先后次序排成一个队列,进程调度程序总是选择队列中的第一个进程执行,且仅能执行一个时间片。在使用完一个时间片后,即使进程并未完成其运行,也必须将处理机交给下一个进程。
时间片的长短对计算机系统的影响很大。如果时间片大到让一个进程足以完成其全部工作,这种算法就退化为先来先服务算法。若时间片很小,那么处理机在进程之间的转换工作过于频繁,处理机真正用于运行用户程序的时间将减少。时间片长短的值应能使分时用户得到好的响应时间。
（6）多级反馈队列调度算法在采用多级反馈队列调度算法的系统中,调度算法的实施过程如下：
首先应设置多个就绪队列,并为各个队列赋予不同的优先权。第一个队列的优先权最高,第二队列次之,其余队列的优先权逐个降低。
其次,赋予各个队列中进程执行时间片的大小也各不相同,在优先权愈高的队列中,每个进程的执行时间片就规定得愈小。例如,第i+1队列的时间片是第i队列时间片的两倍。
第三,当一个新进程进入内存后,首先将它放入第一队列的末尾,按先来先服务的原则排队等待调度。当轮到该进程执行时,如能在该时间片内完成,便可准备撤离系统；如果它在一个时间片结束时尚未完成,调度程序便将该进程转入第二队列的末尾,再同样地按先来先服务原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成,再以同样方法将它转入第三队列。如此下去,当一个长作业从第一队列降到最后一个队列后,在最后一个队列中使用时间片轮转方式运行。
第四,仅当第一队列空闲时,调度程序才调度第二队列中的进程运行:仅当第1至(i一1〉
队列均为空时,才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时,
又有新进程进入优先权较高的队列,则此时新进程将抢占正在运行进程的处理机,即由调度程序把正在执行进程放回第i队列末尾,重新将处理机分配给新进程。
4.实时调度实时系统中的任务通常都联系着一个截止时间,实时调度的关键是保证满足实时任务:
对截止时间的要求。
为了保证满足实时任务对截止时间的要求,实时系统必须具备足够强的处理能力和快速的切换机制。通常,在提交实时任务时,系统将该任务的截止时间、所需的处理时间、资源要求和优先级等信息一起提交给调度程序。若系统能及时处理该任务,调度程序便将它接收下来,否则,将拒绝接收该任务。
对不同的实时系统,其调度方式和算法的选择也各不相同。在一些小型实时系统或要求不太严格的实时控制系统中,常采用简单易行的非抢占式轮转调度方式,它可获得数秒至数十秒的响应时间:而在有一定要求的实时控制系统中,可采用非抢占式优先权调度算法,它可获得仅为数秒至数百毫秒级的响应时间。在要求比较严格(响应时间为数十毫秒以下)的实时系统中,应采用比较复杂的抢占调度方式,其中,基于时钟中断的抢占式优先权调度算法,可获得几十毫秒至几毫秒的响应时间,适用于大多数的实时系统:丽立即抢占的优先权调度算法,可将响应时间降到几毫秒至1∞微秒,甚至更低,适用于要求更严格的实时系统。下面将介绍两种常用的高优先权优先的实时调度算法。
(1)最早截止时间优先CEDE币算法：该算法根据任务的开始截止时间来确定任务的优先级,即任务的开始截止时间愈早,其优先级愈高。在实现该算法时,要求系统中保持-个实时任务就绪队列,该队列按各任务的截止时间的早晚排序。EDF算法即可采用非抢占调度方式,也可采用抢占调度方式。在采用抢占调度方式时,如果新到达的任务的开始截止时间比正在执行的任务早,则它将立即抢占CPU。:
(2)最低松弛度优先(LLF)算法。LIF算法根据实时任务的松弛度(松弛度=任务必须完成的时间一任务本身的运行时间一当前时间)来确定任务的优先权,即任务的松弛度愈低,其优先权愈高。在实现该算法时,要求系统中有一个按松弛度排序的实时任务就绪队列。
该算法主要用于可抢占调度方式中,当一任务的最低松弛度减为0时,它便必须立即抢占
CPU,以保证按截止时间的要求完成任务。
5.多处理机系统中的调度
1.进程分配方式在对称多处理器系统(SMPS)中,各处理器单元在功能和结构上都是相同的,因而可把所有的处理器作为一个处理器池?并将进程分配到其中的任干处理器上运行。在进行进程分配时,可采用静态和动态两种分配方式。采用静态分配方式时,一个进程从开始执行直至其完成,都被固定分配到一个处理器上去执行,此时,需要为每个处理器维护一个专用的就绪队列。静态分配方式的优点是调度的开销小,缺点是会使处理器的忙闲不均。采用动态分配方式时,系统中设置有二个公用的就绪队列,所有的就绪进程都被放在该队列中,然后被随机地调度到任一空闲的处理器上去执行,因此,在一个进程生命周期的不同时刻,它可以在不同的处理器上执行,对松散祸合的多处理器系统,此时需要进行进程现场信息的转移,会明显增加调度开销,但动态分配方式能较好地消除处理器忙闲不均的现象。
在配置有多种类型处理器单元的非对称多处理器系统中,常采用主一从式结构,即操作系统的核心驻留在某个特定的处理器(即主处理器)上,而其他的处理器(即从处理器)只用于执行用户程序。进程调度由主处理器执行,从处理器空闲时,便向主处理器发一索求进程的信号,并由主处理器从自己的就绪队列中摘下一个进程分配给请求的从处理器。这种方式的优点是系统处理简单,缺点是主处理器的故障会导致整个系统瘫痪,而且主处理器容易成为系统瓶颈。
2.进程(线程)调度方式在多处理机系统中,常用的进程(线程)调度方式主要有:
(1)自调度方式。-它是指在系统中设置一个公用的进程(或线程)队列,所有的处理器在空闲时,都可自己到该队列中取一进程(或线程)来执行。
(2)成组调度方式。它是指将一组相互合作的进程或隶属于国一个进程的一组线程分配到一组处理器上去同时执行。
(3)专用处理器分配方式。它是指在一个应用程序的执行期间,专门为该应用程序分配一组处理器,每一个线程一个处理器。这组处理器仅供该应用程序专用,直至该应用程序完成。
4.1.3 死 锁
1.死锁的概念所谓死锁是指多个进程因竞争资源而造成的一种僵局,若无外力作用,这些进程都将无法向前推进。死锁是计算机系统和进程所处的一种状态。
2,产生死锁的原因和必要条件
（1）死锁产生的原因死锁产生的原因有以下两点:
①系统资源不足 例如在上面的例子中,若系统中有两台打印机或者两台输入设备可供进程P1和P2使用,当其中任一个进程提出设备请求后,立即可得到满足,显然不会出现死锁状态。这就是说,如果系统中有足够的资源可供每个进程使用,死锁就不会发生。所以说,产生死锁的根本原因是可供多个进程共亭的系统资源不足。当然,只有当进程提出资源请求时,才会发生死锁。
②进程推讲顺序不当 例如在上面的例子中,若进程P2在P1提出使用输入设备的要求之前,已经完成了对输入设备和打印机的使用,并且释放了它们；或者是在进程P2提出使用打印机的请求之前,进程Pl已经完成了对输入设备和打印机的使用,并且释放了它们,则均不会发生死锁。
（2）死锁产生的必要条件发生死锁的必要条件有以下四条：
①互斥条件：造程要求对所分配的资源进行排它性控制,即在一段时间内某资源仅为一个进程所占有。
②不剥夺条件：进程所获得的资源在未使用完毕之前,不能被其他进程强行夺走,即只能由获得该资源的进程自己来释放。
③部分分配条件：进程每次申请它所需要的一部分资源。在等待新资源的同时,进程继续占有己分配到的资源。
④环路条件：存在一种进程资源的循环等待链,链中的每一个进程已获得资源的同时被链中下一个进程所请求。
3.死锁的预防根据以上讨论,要想防止死锁的发生,只需破坏死锁产生的四个必要条件之一即可。
（1）破坏互斥条件破坏互斥条件就是要允许多个进程同时访问资源。但是这受到资源本身固有特性的限制,有些资源根本不能同时访问,只能互斥访问。比如打印机,就不允许多个进程在其运行期间交替打印数据,打印机只能互斥使用。因此,企图通过破坏互斥条件防止死锁的发生是不大可能的。
（2）破坏不剥夺条件为了破坏不剥夺条件,可以制定这样的策略:一个已获得某些资源的进程,若新的资源请求不能立即得到满足,则它必须释放所有己获得的资源,以后需要再重新申请。这意味着,一个进程已获得的资源在运行过程中可被剥夺,从而破坏了不剥夺条件。该策略实现起来比较复杂,释放已获得资源可能造成前一段工作的失效,重复申请和释放资源会增加系统开销,降低系统吞吐量。
（3）破坏部分分配条件为了破坏部分分配条件,就要求所有进程一次性申请它所需要的全部资源。若系统有足够的资源分配给进程,便一次把所有的资源分配给该进程。但在分配时只要有一种资源要求不能满足,则资源全不分配,进程等待。显然这种资源分配方法造成了严重的资源浪费,以打印机为例,一个作业可能只在最后完成时才需要打印计算结果,但在它运行前就把打印机分配给了它,那么在作业的整个执行过程中打印机完全处于闲置状态。
（4）破坏环路条件为了破坏环路条件,可以采用有序资源分配法。即将系统中的所有资源都按类型赋予一个编号,如打印机为1,磁带机为2,等等。并且要求每一个进程均严格地按照编号递增的次序请求资源。也就是说,只要进程提出请求资源Ri,则在以后的请求中,只能请求排在Ri后面的那些资源。为资源编号〉,不能再要求编号低于Ri的那些资源。对资源请求作了这样的限制后,系统中就不会再出现几个进程对资源的请求成为环路的情况。这种方法存在的主要问题是各种资源编号后不宜修改,从而限制了新设备的增加:尽管在为资源编号时己考虑到大多数作业实际使用这些资源的顺序,但也经常会发生作业使用资源的顺序与系统规定顺序不同的情况,从而造成资源的浪费。
4 死锁的避免在预防死锁的方法中所采取的几种策略,总的说来都施加了较强的限制条件,虽然实现起来较为简单,但却严重地损害了系统性能。在避免死锁的方法中,所施加的限制条件较弱,有可能获得较好的系统性能。在该方法中,把系统的状态分为安全状态和不安全状态,只要能使系统始终处于安全状态,便可避免死锁的发生。
（1）安全与不安全状态在避免死锁的方法中,允许进程动态地申请资源,系统在进行资源分配之前,先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态,便将资源分配给进程,否则进程等待。
若在某一时刻,系统能按某种顺序如〈P1、P2、…、Pn〉来为每个进程分配其所需的资源,直至最大需求,使每个进程都可顺利地完成,则称此时的系统状态为安全状态,称序列〈P1、P2、…、pn>为安全序列。若某一时刻系统中不存在这样一个安全序列,则称此时的系统状态为不安全状态。
虽然并非所有不安全状态都是死锁状态,但当系统进入不安全状态后,便可能进入死锁状态:反之,只要系统处于安全状态,系统便可避免进入死锁状态。
（2）利用银行家算法避免死锁
Dijkstra给出的银行家算法是具有代表性的避免死锁算法。为实现银行家算法,系统中必须设置若干数据结构。
银行家算法的数据结构如下:
(1)可利用资源向量Available,它是一个含有m个元素的数组,其中的每一个元素代表一类可利用的资源数目,其初始值是系统中所配置的该类全部可用资源数目。其数值随该类资源的分配和回收而动态地改变。如果Available (j)=K,表示系统中现有Rj类资源k个。
(2)最大需求矩阵Max,这是一个n ×m的矩阵,它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max(i,j〉=k,表示进程i需要Rj类资源的最大数目为k。
(3)分配矩阵Allocation,这是一个n×m的矩阵,它定义了系统中每一类资源当前己分配给每一个进程的资源数。如果Allocation (i,j)=k,表示进程i当前已分到Rj类资源的数目为k。Allocationi表示进程i的分配向量,由矩阵Allocation的第i行构成。
（4）需求矩阵Need,它是一个n×m的矩阵,用以表示每一个进程还需要的各类资源数。如果Need G,j〉哇,表示进程i还需要RJ类资源k个,才能完成其任务。Needi表示进程i的需求向量,由矩阵Need的第i行构成。
上述三个矩阵间存在关系:
Need (i,j)=Max(i,j)-Allocation (i,j)
银行家算法如下:
Requesti是进程Pi的请求向量。Requesti(j)=k表示进程Pi请求分配Rj类资源k个。
当Pi发出资源请求后,系统按下述步骤进行检查z
（1）如果Requesti<=Need,则转向步骤(2);否则,认为出错,因为它所需要的资源数已超过它所宣布的最大值。
(2)如果Requesti<=Available,则转向步骤(3〉;否则,表示系统中尚无足够的资源满足Pi的申请,Pi必须等待。
(3)系统试探把资源分配给进程Pi,并修改下面数据结构中的数值:
Available =Available-Requesti;
Allocationi=Allocationi+Requesti;
Needi=Needi-Requesti;
(4)系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态。若安全,才正式将资源分配给进程Pi,以完成本次分配:否则,将试探分配作废,恢复原来的资源分配状态,让进程Pi等待。
系统所执行的安全性算法描述如下:
(1)设置两个向量。
Work它表示系统可提供给进程继续运行的各类资源数目,它含有m个元素,开始执行安全性算法时,Work =Availabh。
Finish它表示系统是否有足够的资源分配给进程,使之运行完成,开始时,
Finish (i)=false:当有足够资源分配给进程Pi时,令Finish (i)=true.
(2)从进程集合中找到一个能满足下述条件的进程。
Finish (i〉==false:
Needi<=Work:
如找到则执行步骤(3〉:否则,执行步骤(4)。
(3)当进程Pi获得资源后,可顺利执行直到完成,并释放出分配给它的资源,故应执行
Work =work+Allocationi:
Finish (i〉=true:
Goto step2:
(4)若所有进程的Finish(i)都为true,则表示系统处于安全状态:否则,系统处于不安全状态。
5．死锁的检测和解除
（1）死锁的检测前面介绍的死锁预防和避免算法都是在系统为进程分配资源时施加限制条件或进行检测，若系统为进程分配资源时不采取任何措施，则应该提供检测和解除死锁的手段。
发现死锁的原理是考察某一时刻系统状态是否合理,即是否存在一组可以实现的系统状态,能使所有进程都得到它们所申请的资源而运行结束。检测死锁算法的基本思想是:
获得某时刻t系统中各类可利用资源的数目向量w(t〉,对于系统中的一组进程{Pl、P2、…、pn},找出那些对各类资源请求数目均小于系统现在所拥有的各类资源数目的进程。我们可以认为这样的进程可以获得它们所需要的全部资源并运行结束,当它们运行结束后释放所占有的全部资源,从而使可用资源数目增加,这样的进程加入到可运行结束的进程序列L中,然后对剩下的进程再作上述考察。如果一组进程{P1、P2、…、Pn}中有几个进程不在序列L中,那么它们会发生死锁。
检测死锁可以在每次分配后进行。但是,用于检测死锁的算法比较复杂,所花的检测时间长,系统开销大,因此,也可以选取比较长的时间间隔来执行。
（2）死锁的解除一旦系统成为死锁状态,就应将系统从死锁状态解脱出来,即解除死锁,使系统恢复到正常状态。解除死锁的常用方法有两种:
①资源剥夺法：当发现死锁后,从其他进程剥夺足够数量的资源给死锁进程,以解除死锁状态。
② 撤消进程法：此方法是采用强制手段从系统中撤消一个或一部分死锁进程，并剥夺这些进程的资源供其他死锁进程使用。
最简单的撤消进程方法是撤消全部死锁进程,使系统恢复到正常状态。但这种做法付出的代价太大。另一方法是按照某种顺序逐个撤消死锁进程,直到有足够的资源供其他未被撤消的进程使用,消除死锁状态为止。
4.2重点难点学习提示本章的学习目的主要是使学生理解和掌握处理机调度和死锁的基本概念,为此应对以下几个重点、难点问题作认真而深入的学习。
1.高优先权优先调度和基于时间片的轮转调度算法高优先权优先调度和基于时间片的轮转调度算法是目前被广泛使用的两种进程调度算法,读者应对它们有较深入的理解和掌握。
(1)什么是高优先权优先调度算法：这是指将处理机分配给就绪队列中优先权最高的进程的调度算法。在学习时应了解系统是根据哪些因素来确定一个进程的优先权的,在采用动态优先权的系统中又将根据哪些因素来调整运行进程的优先权。
(2)什么是高响应比优先调度算法：这是指以响应比作为进程的优先权的进程调度算法。在学习时应了解高响应比优先调度算法是为了解决什么问题而引入的,它有何优缺点。
(3)什么是时间片轮转算法：这是指让就绪进程以FCFS的方式按时间片轮流使用CPU的调度方式。在学习时应了解时间片的概念是为了解决什么问题而引入的,它是如何解决上述问题的。
(4)什么是多级反馈队列调度算法：该算法设置了多个就绪队列,并给每个队列赋予不同的优先权和时间片。在学习时应了解该算法是如何对各个就绪队列中的进程进行进程调度的,为什么它能较好地满足各种类型用户的需要。
2.常用的几种实时调度算法根据确定实时任务优先权方法的不同,可形成以下两种常用的实时调度算法:
(1)最早截止时间优先(EDF)算法：在学习时应了解EDF算法是根据什么来确定任务的优先权的,或者说它是如何保证满足各任务对截止时间的要求的。
(2)最低松弛度优先(LLF)算法：在学习时应了解LLF算法是根据什么来确定任务的优先级的,在什么情况下,一个进程应抢占被另一进程占用的CPU。
3.多处理机环境下的进程(线程)调度方式多处理机系统己广为流行多年,目前,己出现了多种多处理机环境下的进程(线程)调度方式,故读者应对下述几种比较有代表性的调度方式有较好的了解：
(1)自调度方式：自调度方式是多处理机环境下最简单的一种调度方式,在学习时应了解它是如何为就绪进程(线程)分配处理机的,该方式主要有什么优点,以及它存在哪些缺点
(2)成组调度方式：它将一组相互合作的进程或隶属于同一个进程的一组线程分配到一组处理器上去同时执行,读者应了解为什么成组调度方式的性能会优于自调度方式。
(3)专用处理器分配方式：这种方式有可能造成部分处理机的严重浪费,读者必须了解在并行程度相当高的多处理器环境下,为什么这种浪费是值得的,它换来了什么好处。
4.死锁的基本概念死锁是指多个进程竞争资源而形成的一种僵局,若无外力的作用,这些进程将无法再向前推进。可见,死锁状态不同于一般的阻塞状态。在学习时,读者应对下述两个问题有较深刻的理解和掌握:
(1)产生死锁的原因是什么：产生死锁的根本原因是竞争资源和进程推进顺序非法,在学习时应了解这两个根本原因与OS的两个基本特征并发和其事之间存在着什么样的联系。
(2)产生死锁的必要条件有哪些。产生死锁的必要条件奋互斥条件、请求与保持条件、不剥夺条件和环路等待条件,在学习时请思考如果其中的一个条件不满足,为什么不会产生死锁。
5.预防死锁的方法预防死锁是通过摒弃死锁产生的必要条件来达到防止死锁产生的目的的在学习时应了解下述几个方面的内容:
(1)摒弃"互斥"条件：应了解"互斥"条件为什么很难被摒弃,对某些(极少数的)互斥共享的设备(如打印机)又可通过什么技术来摒弃互斥条件。
（2）摒弃"请求和保持"条件：读者应了解可通过哪些方法来摒弃"请求和保持"条件它们对进程的运行和系统资源的利用率造成了什么样的影响。
(3)摒弃"不剥夺"条件：读者应了解可通过哪些方法来摒弃"不剥夺"条件,这些法有什么缺点。
(4)摒弃"环路等待"条件：读者应了解可通过哪些方法来摒弃"环路等待"条件,它对系统和用户带来了哪些不便,对资源的利用率又有什么影响。
（5）各种方法的比较：读者应从实现的简单性和资源的利用率等方面比较上述几种预防死锁的方法,以了解哪种方法实现最简便,哪种方法可使资源利用率受损最少。
6.利用银行家算法避免死锁银行家算法是一种最有代表性的避免死锁的算法。在学习时应对下述几个方面的内容国有较好的理解：
(1)避免死锁的实质在于如何防止系统进入不安全状态二在学习时,读者必须清晰地认识到,为什么系统处于安全状态便可避免进入死锁状态,而处于不安全状态则极有可能导致死锁状态的产生。
(2)在银行家算法中用到了可利用资源向量Available、最大需求矩阵Max、分配矩阵
Allocation、需求矩阵Need等数据结构，而在安全性检查算法中则还要用到工作向量Work
和完成向量Finish等数据结构,读者应对它们的物理意义和相互关系有较好的理解。
(3)安全性检查算法的目的是寻找一个安全序列。在学习时应了解满足什么条件的进程Pi,其对资源的最大需求可以得到满足,故可顺利完成:当Pi完成后,应如何修改工作向量Work和完成向量Finish。
(4)在利用银行家算法避免死锁时应了解,系统什么时候可以为提出资源请求的进程试行分配资源,什么时候才可以正式将资源分配给进程。
4.3典型问题分析和解答
1.为什么说多级反馈队列调度算法能较好地满足各方面用户的需要?
答:对终端型作业用户而言,他们提交的作业大多属于交互型作业,作业通常较小,系统只要能使这些作业在一个队列所规定的时间片内完成,便可使他们都感到满意。对短批处理作业用户而言,开始时他们的作业像终端型作业一样,如果仅在第一个队列中执行一个时间片即可完成,便可获得与终端型作业一样的响应时间:对于稍长的作业,通常也只需在第二队列和第三队列各执行一个时间片即可完成,其周转时间仍然很短。对长批处理作业用户而言,他们的作业将依次在第1,2,…,n个队列中运行,然后再按轮转方式邑行,用户不必担心其作业长期得不到处理； 而且每往下降一个队列，其得到的时间片将随着增加,故可进一步缩短长作业的等待时间。
2.假设一个系统中有5个进程,它们的到达 表4.1进程到达和需服务时间时间和服务时间如表4.1所示,忽略I/0以及进程
到达时间
服务时间
A
0
3
B
2
6
C
4
4
D
6
5
E
8
2
其他开销时间,若分别按先来先服务(FCFS)、非抢
占及抢占的短进程优先（SPF）、高响应比优先
(HRRN)、时间片轮转(RR,时间片=1)、多级反馈队列(FB,第i级队列的时间片=2^i-1)以及立即枪占的多级反馈队列(FB,第i级队列的时间片=2^i-1)
调度算法进行CPU调度,请给出各进程的完成时间、
周转时间、带权周转时间、平均周转时间和平均带权周转时间。
分析：进程调度的关键是理解和掌握调度所采用的算法。FCFS算法选择最早进入就绪队列的进程投入执行;SPF算法选择估计运行时间最短的进程投入执行,采用抢占方式时,若新就绪的进程运行时间比正在执行的进程的剩余运行时间短,则运行时间+等待时间新进程将抢占CPU;HRRN算法选择响应比(响应比=最高的运行时间+等待时间/运行时间)最高的进程投入执行;RR算法中,就绪进程按FIFO方式排队,CPU总是分配给队首的进程,并只能执行一个时间片;FB算法将就绪进程排成多个不同优先权及时间片的队列,新就绪进程总是按FIFO方式先进入优先权最高的队列,CPU也总是分配给较高优先权队列上的队首进程,若执行一个时间片仍未完成,则转入下一级队列的末尾,最后一级队列则采用时间片轮转方式进行调度。
答：各进程的完成时间、周转时间和带权周转时间(如表4.2所示)
表4.2进程的完成时间和周转时间
进程
A
B
C
D
E
平 均
FCFS
完成时间周转时间带权周转时间
3
3
1.00
9
7
1.17
13
9
2.25
18
12
6.00
20
12
6.00
8.6
2.56
SPF(非抢占)
完成时间周转时间带权周转时间
3
3
1.00
9
7
1.17
15
11
2.75
11
3
1.5
11
3
1.5
7.6
1.84
SPF(抢占)
完成时间周转时间带权周转时间
3
3
1.00
15
13
2.16
8
4
1.00
10
2
1.00
10
2
1.00
7.2
1.59
HRRN
完成时间周转时间带权周转时间
3
3
1.00
9
7
1.17
13
9
2.25
15
7
3.5
15
7
3.5
8
2.14
RR(q=1)
完成时间周转时间带权周转时间
4
4
1.33
17
13
3．25
17
13
3.25
20
14
2.8
15
7
3.5
10.8
2.71
FB(q=2^i-1)
完成时间周转时间带权周转时间
3
3
1
17
15
2.50
18
14
3.50
20
14
2.8
14
6
3.00
10.4
2.56
FB(q=^i-1)
(立即抢占
完成时间周转时间带权周转时间
4
4
1.33
18
16
2.67
15
11
2.75
20
14
2.8
16
8
4.00
10.6
2.87
3.何谓自调度方式?其主要优缺点是什么?
答:自调度方式是多处理器系统中的一种处理机调度方式,它在系统中设置一个公用的进程(或线程)队列,所有的处理器在空闲时,都可自己到该队列中取一进程(或线程)来执行。在自调度方式中,可采用单处理机环境下的进程调度算法(如先来先服务、最高优先权优先、抢占式最高优先权优先调度算法等)来进行进程调度。
自调度算法的主要优点是:①系统中公用就绪队列的组织方式以及具体的进程(或线程)
调度算法都可沿用单处理机中的方式,因而容易实现:②不会发生处理器忙闲不均的现象,因而有利于提高处理器的利用率。
而它的缺点主要是:①公用就绪队列很容易成为整个系统的瓶颈:②一个线程在整个生命期中,可能要多次更换处理器,从而使处理器上的高速缓存使用率降低,并进一步降低整个系统的性能:③相互合作型的线程很难同时获得处理器而同时运行,这将会增加合作线程之间的阻塞频率,从而提高线程切换的频率,增加系统的开销并降低进程的运行速度。
4.何谓成组调度方式?其主要优点是什么?
答:成组调度方式是多处理器系统中的一种处理机调度方式,它将一组相互合作的进程或一个进程的一组线程分配到一组处理器上去同时执行。
成组调度的主要优点是:如果一组相互合作的进程或线程能并行执行,则可有效地减少同步阻塞的现象,从而可以减少进程和线程的切换次数,使系统性能得到改善；另外,由于每次调度都可以解决一组进程或线程的处理器分配问题,因而可显著地减少调度频率,降低调度开销。
5,产生死锁的四个必要条件是什么?试以过河问题中产生的死锁为例加以说明。
答：产生死锁的必要条件如下：
(1)互斥:系统中至少有一个(类)资源必须用非共享方式使用。过河问题中,每一块垫脚石任一时刻仅能为一个人占用。
(2)占用并等待:一个进程至少占有一个资源并正等待得到其他资源,而这些资源已被其他进程所占用.过河问题中,相遇的两个人各自踏在一块垫脚石上,并同时等待踏上对方占用的那一块。
(3)非抢占:资源不可能被抢占.在过河问题中,由于垫脚石不能强行移动,"非抢占"条件满足。
(4)循环等待:存在循环等待情况。从东岸来的人等着从西岸来的人，而从西岸来的人则等着从东岸来的人。
于是,大家都不能过河,每人都等待对方从其占用的垫脚石上移开脚,具备以上四个条件,死锁发生.
6.在哲学家就餐问题中,如果将先拿起左边的筷子的哲学家称为左撇子,而将先拿起右边的筷子的哲学家称为右撇子,请说明在同时存在左撇子和右撇子的情况下,任何就座安排都不会产空死锁。
分析：这类题目的关键是必须证明产生死锁的4个必要条件的其中一个不可能望成立。在本题中,互斥条件、请求与保持条件、不剥夺条件是肯定成立的,因此必须证明"循环等待"条件不成立。
答:对本题,死锁产生的必要条件-一"循环等待"不可能成立。如果存在所有左边的哲学家等待右边的哲学家放下筷子的循环等待链,则每个哲学家肯定已获得左边的筷子,但还没得到右边的筷子,这与存在右撇子的情况不符:同样,也不可能存在相反的循环等待链。而且,系统中也不可能存在5个以下哲学家的循环等待链,因为,不相邻的哲学家之间不竞争资源。因此,不可能产生死锁。
7.假定系统中有五个进程{P0,P1,P2,P3,P4}和三种类型的资源{A,B,C},每一种资源的数量分别为10、5、7,在To时刻的资源分配情况如表4.3所示。
表4.3 To时刻的资源分配表资源情况进程
MAX
Allocation
Need
Available
A B C
A B C
A B C
A B C
PO
P1
P2
P3
P4
7 5 3
3 2 2
0 2
2 2 2
4 3 3
0 1 0
2 0 0
(3 0 2)
3 0 2
2 1 1
0 0 2
7 4 3
1 2 2
(0 2 0)
6 0 0
0 1 1
4 3 1
3 3 2
(2 3 0)
(1)To时刻的安全性利用安全性算法对To时刻的资源分配情况进行分析,可得到如表4.4所示的To时刻的安全性分析,从表中得知,To时刻存在着一个安全序列{Pl、P3、P4、P2、PO}故系统是安全的。 表 4.4 T0时刻的安全序列
资源分配进程
Work
Need
Allocation
Work+Allocation
Finish
A B C
A B C
A B C
A B C
P1
P3
P4
P2
P0
3 2
5 3 2
7 4 2
7 4 5
10 4 7
1 2 2
0 1 1
4 3 1
6 0 0
7 4 3
2 0 0
2 1 1
0 0 2
3 0 2
0 1 0
5 3 2
7 4 3
7 4 5
10 4 7
10 5 7
true
true
trye
true
true
（2）P1请求资源
Pl发出请求向量Request1（0,0,2〉,系统按银行家算法进行检查：
Request1(1,0,2〉<=Need1(1,2,2〉
Request1〈1,0,2〉<=Available (3,3,2)
系统先假定可为P1分配资源,并修改Available、Allocationl、Needl向量,由此形成的资源变化情况如表3.1中的圆括号所示。
我们再利用安全性算法检查此时系统是否安全,可得到如表4.5所示的安全性分析。
表 4.5 P1申请资源时的安全性检查
资源分配进程
Work
Need
Allocation
Work+Allocation
Finish
A B C
A B C
A B C
A B C
P1
P3
P4
P0
P2
3 0
5 3 2
7 4 3
7 4 5
7 5 5
0 2 0
0 1 1
4 3 1
7 4 3
6 0 0
3 0 2
2 1 1
0 0 2
0 1 0
3 0 2
5 3 2
7 4 3
7 4 5
7 5 5
10 5 7
true
true
trye
true
true
从进行的安全性检查得知,可以找到一个安全序列{P1、P3、P4、PO、P2}。因此,系统是安全的,可以立即将P1所申请的资源分配给它。
(3)P4请求资源
P4发出请求向量Requesu(3,3,0),系统按银行家算法进行检查:
Request4(3,3,0)<=Need4(4,3,1)
Request4(3,3,0)>Available (2,3,0),让P4等待。
(4)PO请求资源
PO发出请求向量Requesto(0,2,0),系统按银行家算法进行检查:
Requesto(0,2,0〉<=Needo(7,4,3)
Requesto(0,2,0)<=Available (2,3,0)
系统先假定可为P0分配资源,并修改有关数据,如表4.6所示。
表4.6 P0分配资源后的有关资源数据
资源分配进程
Allocation
Need
Available
A B C
A B C
A B C
P0
P1
P2
P3
P4
3 0
3 0 2
3 0 2
2 1 1
0 0 2
7 2 3
0 2 0
6 0 0
0 1 1
4 3 1
2 1 0
我们再利用安全性算法检查此时系统是否安全。从表3.4中可以看出,可用资源Available {2,1,0}已不能满足任何进程的需要,故系统进入不安全状态,此时系统不分配资源。
8.死锁检测程序的运行频率较高或较低,各有什么优缺点?
答:死锁的检测可非常频繁地在每次资源请求时进行,其优点是：可以尽早地检测到死锁及其所涉及的进程,并有可能找到引起系统死锁的那个(或那几个)进程。其缺点是：频繁的检测会耗费相当多的CFU时间,增加系统的开销。相反,每隔较长时间或当CFU利用率下降到较低程度时进行死锁的检测,则可以降低运行死锁检测程序的开销,但在检测到死锁时可能涉及到很多进程,也难以找到引起死锁的那个进程。
9.假设三个进程共享相同类型的四个资源,每个进程一次只能申请或释放一个资源,每个进程至多需要两个资源,证明该系统不会发生死锁。
证：假定该系统死锁,那么就隐含其中的每一进程已占有一资源并正等待另一资源.由于该系统只有三个进程且有四个资源,因此,必有一进程能获得两个资源,不必等待.于是该进程不再申请资源,而且当它执行完后将归还它占有的资源。故该系统不会发生死锁.
10.在一个实际的计算机系统中,资源可以更新和增减,进程可以创建和撤销。如果系统用banker算法处理死锁,那么,在什么情况下,下列改变可以安全地进行而不会引起死锁发生?
(1)增加Avaiiable(增添新资源):
(2)减少Available (资源永久性地从系统中删除):
(3)增大Max(对一进程而言,它可能希望更多的资源):
(4)减少Max(一进程决定不需要那么多资源):
(5)增加进程数:
(6)减少进程数。
解(1)任何时候都不会引起死锁发生:
(2)仅当每一进程的Max请求数不超过可用资源的总数时,系统才保持在安全态:
(3)仅当每一进程的Max请求数不超过可用资源的总数时,系统才保持在安全态:
(4)任何时候都不会引起死锁发生:
(5)任何时候都不会引起死锁发生:
(6)任何时候都不会引起死锁发生.
4.4 自测题
4.4.1 基本题一、判断题(正确的在括号中记√,错误的记×)
1.死锁就是循环等待。 ( )
2.最适合分时系统的进程调度算法是优先数法。 （ ）
3.不存在只涉及一个进程的死锁。 ( )
4,在分时系统中当用户数一定时，影响响应时间的主要因素是调度算法。 ( )
5.若系统中每一资源类只有一个,只要系统存在任何环路,系统状态就是不安全的。 ( )
6.多级反馈调度算法属于抢占调度方式。 （ ）
7.死锁是多个进程为竞争系统资源或彼此间通信而引起的一种临时性的阻塞现象。 ( )
8.在引入线程的系统中进程程调度负责CPU的分配工作。 （ ）
9.当进程数大于资源数时,进程竞争资源一定会产生死锁。 （ ）
10.实时调度的关键是保证满足实时任务对截止时间的要求。 （ ）
1,Χ 2,Χ 3.√ 4,Χ 5.√ 6,√ 7,Χ 8,Χ 9,Χ 10,√
二、选择题
1.在三种基本类型的操作系统中,都设置了进程调度,在批处理系统中还应设置______调度。
A.作业 B.进程 C.中级 D.多处理机
2.下列算法中,_______只能采用非抢占调度方式。
A．高优先权优先法 B.时间片轮转法 C.FCFS调度算法 D.短作业优先算法
3.下面关于优先权大小的论述中,正确的论述是_____________。
A.计算型作业的优先权,应高于I/O型作业的优先权。
B.用户进程的优先权,应高于系统进程的优先权。
C.资源要求多的作业,其优先权应高于资源要求少的作业。
D.在动态优先权时,随着进程执行时间的增加,其优先权降低。
4.最适合分时系统的进程调度算法是______。
A、FCFS B、SSJF C、优先数法 D、轮转法
5.在分时系统中当用户数一定时，影响响应时间的主要因素是_____。
A、时间片 B、调度算法 C、存储分配方式 D、作业的大小
6.采用“按序分配”策略，可以破坏死锁产生的条件是______。
A、互斥 B、请求和保持 C、非剥夺 D、环路等待
7.下述解决死锁的方法中,属于死锁预防策略的是____________。
A.银行家算法 B.资源有序分配法 C.资源分配图化简法 D.撤消进程法
8.从下面关于安全状态和非安全状态的论述中,正确的论述是________。
A.安全状态是没有死锁的状态,非去全状态是有死锁的状态。
B.安全状态是可能有死锁的状态,非安全状态也是可能有死锁的状态。
C.安全状态是可能没有死锁的状态,非安全状态是有死锁的状态。
D.安全状态是没有死锁的状态,非安全状态是可能有死锁的状态。
9.关于产生死锁的现象,下面的描述最准确是__________。
A.每个进程共享某一个资源
B.每个进程竞争某一个资源
C.每个进程等待着某一个不能得到且不可释放的资源
D.某个进程因资源而无法进行下去
10.采用“按序分配”策略，可以破坏死锁产生的条件是______。
A、互斥 B、请求和保持 C、非剥夺 D、环路等待
11.在选取撤消的进程或抢占的进程时,应尽量选择_______。
A.进程优先级最高的
B.进程已运行的时间最短的
C.进程完成其工作还需要的时间最短的
D.进程已A使用的资源数最少的
12.系统使用的资源,如进程控制块(PCB)一般采用下列_________处理死锁。
A.预分法 B.抢占和交换的方法 C.死锁避免方法 D.资源定序方法
13.在为多道程序所提供的可共享的系统资源不足时,可能出现死锁。但是,不适当的___也可能产生死锁。
A.进程优先权 B.资源的线性分配
c.进程推进顺序 D.分配队列优先权答:C
14.采用资源剥夺法可解除死锁,还可以采用_____方法解除死锁。
A.执行并行操作 B.撤消进程
C.拒绝分配新资源 D.修改信号量答,B
15.发生死锁的必要条件有四个,要防止死锁的发生,可以破坏这四个必要条件,但破坏_____条件是不太实际的。
A.互斥 B.不可抢占 C.部分分配 D.循环等待答:A
16.在_________的情况下,系统出现死锁。
A.计算机系统发生了重大故障 B.有多个封锁的进程同时存在
C.若干进程因竞争资源而无休止地相互等待他方释放已占有的资源
D.资源数大大小于进程数或进程同时申请的资源数大大超过资源总数答,C
17.银行家算法是一种__________算法。
A.死锁解除 B.死锁避免 C.死锁预防 D.死锁检测答:B
18.________优先权是在创建进程时确定的,确定之后在整个进程运行期间不再改变。
A.先来先服务 B.静态 C.动态 D.短作业答:B
19.某系统中有3个并发进程,都需要同类资源4个,试问该系统不会发生死锁的最少资源数是_________。
A.9 B.10 C.11 D.12
答:B
20.以下叙述中正确的是___________。
A.调度原语主要是按照一定的算法,从阻塞队列中选择一个进程,将处理机分配给它。
B.号预防死锁的发生可以通过破坏产生死锁的四个必要条件之一来实现,但破坏互斥条件的可能性不大。
C.进程进入临界区时要执行开锁原语。
D.既考虑作业等待时间,又考虑作业执行时间的调度算法是先来先服务算法。
答:B
三、填空题
1.处理死锁的方法通常有_______、________、_______和________
2.为破坏_______条件,采用资源的静态预分策略,系统对进程申请的资源进行一次性的分配,然后才启动该进程运行.
3.Banker算法是典型的_______算法,要求系统必须知道未来的资源请求信息,进程要预先声明资源的最大需求量。
4.进程的调度方式有两种,一种是_______，另一种是_________。
答:①剥夺方式②非剥夺方式
5.死锁是指在系统中的多个______无限期地等待永远不会发生的条件。
答:进程
6.一种最常用的进程调度算法是把处理机分配给具有最高优先权的进程。而确定优先权的方法概括起来不外乎是基于_______特性和________特性两种方法。前者所得到的是_______优先权,后者所得到的是__________优先权。
答:①静态②动态③静态④动态
7.进程调度负责______的分配工作。
答:处理机
8.在______调度算法中,按照进程进入就绪队列的先后次序来分配处理机。
答:先来先服务;..
9.死锁产生的必要条件有四个,_______、______、_______、____________。
答:①互斥条件②不剥夺条件③部分分配④环路条件
10.解除死锁常用的方法有两种。_______是从其他进程那里剥夺足够数量的资源给__________进程,以解除死锁状态。
答:①资源剥夺法②死锁
11.银行家算法中,当一个进程提出的资源请求将导致系统从______进入_________时,系统就拒绝它的资源请求。
答:①安全状态②不安全状态
12.如果要求所有进程一次性申请它所需要的全部资源。若系统有足够的资源分配给进程,便一次把所有的资源分配给该进程。但在分配时只要有一种资源要求不能满足,则资源全不分配,进程等待。这种死锁预防方法破坏了死锁产生必要条件中的_____条件。
答:部分分配
13.对待死锁,一般应考虑死锁的预防、避免、检测和解除四个问题。典型的银行家算法是属于________,破坏环路等待条件是属于__________,而剥夺资源是__________的基本方法。
答:①死锁的避免②死锁的预防③死锁的解除.
四、简答题
1.进程调度的主要功能有哪些?
2.高级调度与中级调度的主要任务是什么?为什么要引入中级调度?
3.在抢占调度方式中,抢占的原则是什么?
4.在选择调度方式和调度算法时,应遵循的准则是什么?
5.在批处理系统、分时系统和实的系统中,各采用哪几种进程(作业)调度算法?
6.何谓静态和动态优先权?确定静态优先权的依据是什么?
7.试比较FCFS和SPF两种进程调度算法。
8.为什么在实时系统中,要求系统(尤其是CPU)具有较强的处理能力?
9.按调度方式可将实时调度算法分为哪几种?
10.试说明多处理器系统有哪儿种类型。
11.试说明对称MPS中的进程分配方式。
12.何谓死锁?产生死锁的原因和必要条件是什么?
13.是否存在只涉及一个进程的死锁问题?-t
14.在解决死锁问题的几个方法中,哪种方法最易于实现?哪种方法使资源利用率高?
15.考虑一个共有150个存储器单元的系统,内存的分配情况如下:
进程 Max Allocation
Pl 70 45
P2 60 40
P3 60 15
使用银行家算法,以确定是否可以同意下面的任一请求:
(1)第4个进程到达,最多需要60个存储单元,最初需要25个单元;
(2)第4个进程到达,最多需要60个存储单元,最初需要35个单元。
16.不安全状态是否必然导致系统进入死锁状态?
答:不安全状态不一定导致系统进入死锁状态。因为,安全性检查中使用的向量Max是进程执行前提供的,而在实际运行过程中,一进程需要的最大资源量可能小于Max,如一进程对应的程序中有一段进行错误处理的代码,其中需要n个A种资源,若该进程在运行过程中没有碰到相应错误而不需调用该段错误处理代码,则它实际上将完全不会请求这n个A种资源。
1.什么是过河问题中的死锁?试说明四个预防算法都可应用于过河问题。
2.考虑图7.3所示的交通死锁情况.
(1)说明图中导致死锁的四个必要条件成立.
(2)提出一个避免死锁的简单规则。
3.考虑表7-3所示的系统瞬时状态,利用banker算法回答下面的问题:
(1)数组Need的内容是什么?
(2)该系统处于安全态吗?若是,给出一安全序列.
(3)若进程P1的请求(0420)到达,该请求是否能立即满足?
表7-3
进程
allocation
Max
Available
P0
0012
0012
1520
P1
1000
1750
P2
1354
2356
P3
0632
0652
P4
0014
0656
4.4.2 解析题一、论述题
【例24】考虑一个每月运行5000个作业而未采用死锁预防或避免措施的系统.死锁大约每月发生两次,而且每班发生死锁时要求操作员终止或重新运行大约10%的作业,每个作业大约耗费20元(按CPU时间计算)且每个被终止的作业在被撤消时往往都运行了一半。
系统程序员估计,在该系统上配置死锁避免算法(如banker算法)会使每个作业平均执行时间增加大约10%.由于机器当前仍有30%的空闲时间,所以,每个月仍可以运行5000个作业(尽管平均周转时间增加了大约20%)。
(1)赞成配置死锁避免算法的理由是什么?
(2)反对配置死锁避免算法的理由是什么?
解：(1)为了有效地判定在特定环境下是否出现死锁,必须配置死锁预防或避免算法.通过配置死锁避免算法,减少平均等待时间.
(2)若不把重点放在使等待时间变为最少这一点上,那么,不配置死锁预防或避免算法会减少成本。
【例25】考虑下面的死锁分配策略:允许在任何时候申请和释放资源:若因没有可用资源而不能满足对资源的申请,则检查那些因等待资源而被阻塞的进程,若它们占有所需的资源,则从中收回这些资源并将这些资源分给申请这些资源的进程.增加等待进程正等待的资源向量,使其包含那些被收回的资源.例如,考虑这样一种系统,它有3类资源,且向量Available的初值为(4,2,2).若进程A申请(2,2,1),则它将得到满足:若进程B申请(1,0,1),则它也得到满足:然后若进程A又申请(0,0,1),则它被阻塞(无可用资源).如果进程C现要申请(2,0,0),则它得到一个可用资源、(1,0,0)和一个曾分配给A的资源(因A已被阻塞).此时,A的Allocation向量变为(1,2,1),而其Need向量则变为(1,0,1)。试说明:
(1)在这种环境中会出现死锁吗?若会,试举一例:若不会,那么哪个必要条件不可能成立?
(2)会出现无限期地阻塞吗?
解(1)由于采用的是抢占性策略,所以不可能出现死锁。
(2)会的.一个进程可能决不会获得它所需要的全部资源,如果资源被一系列类似过程C的申请接连不断地抢占的话.
【例26】当由于发生死锁而撤离一进程时会出现什么困难?
解:进程必须完全地撤离(中止重新开始)或只是退回到前面的安全态.对于第一种情形,这种撤离的开销由其优先数、它已运行了多长时间、在完成前还需多少时间以及所需的资源类型等因素来决定:对于第二种情形,为了确定进程最近的安全态,系统需要保留有关每一进程的许多信息.
【例27】一个系统能否检测它的哪些进程正处于饥饿状态?若能,则说明如何进行这种检测.若不能,则叙述系统是如何处理饥饿问题的.
解:测饥饿现象事实上需要"未来知识",因为,对进程"过去知识"的统计资料还不能判定进程"前进"与否,但通过使进程"老化"可预防饥饿现象。这意味着对每一进程管理需设置一个撤消计数器,而且在选择进程作为"抢占/撤消"对象时把它作为开销因素的一部分来考虑.
【例28】单资源类的banker算法可从一般的banker算法获得,这只需将各数组的维数减为1即可.试举例说明,多资源类的baI虫er算法不能通过把单资源类的banker算法单独地应用到每一资源类来实现.
解:考虑一系统它具有资源类A,B,C和两个进程Po,pl以及表7.2所示的瞬时状态.该系统不是处于安全态。但是,若把单资源类的banker算法单独地应用到每一资源类,那么,就得到
·序列〈P0,p1〉对资源A满足安全性要求:
·序列<P0,P1>对资源B满足安全性要求:
·序列〈Po,P1>对资源C满足安全性要求.
表7-2
allocation
Max
Need
Available
122
23
112
111
112
233
121
这样,该系统就应处于安全态了,显然与实际情况不符.
二．计算题例76试列出两种破坏"循环等待"条件的方法以防止死锁发生.
解假定对系统资源已进行了线性定序,则有以下两种破坏"循环等待"条件:
(1)进程只能申请具有较高序号数的资源:
(2)当进程申请某个资源时,它必须释放所有较低序号数的资源。
【例18】硬件并不总是可靠的.若设备发生故障,那么,它对处理死锁的三种方法(预防、避免和检测)有何影响?
解:对死锁预防无影响:
对死锁避免有影响,该系统可能不再处于安全状态:
对死锁检测有影响,虽不会产生死锁,但必须更新等待图以反映系统状态的变更.
【例19】试列出资源的四种类型,并给出其对应的处理死锁的典型方法.
解:(1)内部资源:资源定序方法.
(2)主存:抢占和交换的方法
(3)作业资源:死锁避免方法
(4)可交换空间:预分法.
【例20】适当的Spooling技术可能消除死锁.它肯定可以消除读卡机、绘图机、行打机等的竞争,甚至对磁带也可以采用Spooling技术。这样剩下的资源是CPU时间、存储区和盘空间。问:是否会出现涉及到这些资源的死锁?若会,那么在什么情况下发生死锁?哪种(些)处理死锁的方法最适合于处理这类死锁?..
解:仍然可能出现死锁.例如,进程pl占有一些由进程P2所请求的内存页面,而P2占有CPU且pl正在申请CPU.消除这类死锁的最好方法是"抢占式"方法.。
【例14】产生死锁的四个必要条件是否都是独立的?能否给出一个必要条件的最小集合?
解：四个必要条件并非是绝对独立的。"占有并等待"条件蕴含"互斥"条件:"循环等待"条件蕴含"互斥"、"占有并等待"以及"非抢占"条件.前三个条件是导致死锁的必要而非充分条件,它们潜藏着第四个条件.这四个条件一起构成了死锁的充要条件.
【例15】什么是饥饿?死锁和饥饿的主要差别是什么?
解：饥饿是系统并没有死锁,但至少有一个进程被无限期地推迟.饥饿不同于死锁.死锁是这样一种情形,其中某进程正等待一个决不会发生的事件.而饥饿现象是指某进程正等待这样一个事件,它发生了但总是受到其他进程的影响,以致一直轮不到(或很难轮到)该进程.
【例16】设计一个不可能出现饥饿和死锁的过河算法.
解：利用红绿灯和一个计数器.当有人开始过河时,计数器增值:过河后该计数器减值.仅当该计数器之值为0时才开绿灯,否则为红灯,岸上的人看到绿灯方能过河.
2.引起进程调度的因素有哪些?
答:引起进程调度的因素有:
(1)进程正常终止或异常终止。
(2)正在执行的进程因某种原因而阻塞:①提出I/O 请求后被阻塞:②在调用P操作时因资源不足而阻塞:③因其他原因执行block原语而阻塞等。
(3)在引入时间片的系统中,时间片用完。
(4)在抢占调度方式中,就绪队列中某进程的优先权变得比当前正在执行的进程高,或者有优先权更高的进程进入就绪队列。
1.为什么说采用有序资源分配法不会产生死锁?
解:为了便于说明,不妨设系统中有m类资源,n个进程,分别用R1,R2,…,Rm(1,2,…,m可看作资源编号)和P1,P2,…pn表示。根据有序资源分配法可知,进程申请资源时必须按照资源编号的升序进行,即任何进程在占有了Ri类资源后,再申请的资源Rj的编号j一定大于i。因此在任一时刻,系统中至少存在一个进程Pk,它占有了较高编号的资源Rh且它继续请求的资源必然是空闲的,因而Pk可以一直向前推进直至完成,当PK运行完成后即会释放它占有的所有资源:在PK完成之后,剩下的进程集合中同样会存在一个进程,它占有了较高编号的资源,且它继续请求的资源必然是空闲的,因而它可以一直向前推进直至完成:以此类推,所有进程均可运行完成,故不会发生死锁。
【例12】解除死锁,在选择撤消进程或被抢占资源的进程时,可考虑哪些因素?.
答:可考虑的因素有：
(1)优先权；
(2)进程己执行的时间；
（3）估计的剩余执行时间；
(4)己产生的输出量；
(5)已获得的资源量和资源类型；
(6)还需要的资源量；
(7)进程的类型(批处理型或交互型)；
(8)需要被撤消的进程数等。
3.在生产者和消费者问题中,如果对调生产者进程中的两个P操作和两个V操作,则可能发生什么情况?
解:如果对调生产者进程中的两个P操作和两个V操作,则生产者和消费者问题的同步描述为：
int full=0; /*满缓冲单元的数目*/
int empty=n； /*空缓冲单元的数目*/
int mutex=1; /*对有界缓冲区进行操作的互斥信号量*/
main( )
{
parbegin
producer ( );
consumer ( );
parend
}
producer ( )
{
while (生产未完成)
{
生产一个产品:
p(mutex);
p(empty);
送一个产品到有界缓冲区;
v〈full〉;
v(mutex〉;
}
}
consumer ( )
{
while (还要继续消费〉
p〈full〉;
p〈mutex〉;
从有界缓冲区中取产品:
v(mutex〉:
v(empty);
消费一个产品:
}
}
由于V操作是释放资源,因此对调V操作的次序无关紧要。而对调P操作的次序则可能导致死锁。这是因为对调P操作后,有可能出现这样一种特殊情况:在某一时刻缓冲区中己装满了产品且缓冲区中无进程工作(这时信号量如full的值为 n，信号量empty的值为0,信号量mutex的值为1,若系统此时调度生产者进程运行,生产者进程又生产了一个产品,它执行P(mutex)并顺利进入临界区(这时mutex值为0),随后它执行p(empty)时因没有空闲缓冲单元而受阻等待,等待消费者进程进入缓冲区取走产品以释放出缓冲单元;消费者进程执行p(full)后再执行p(mutex〉时,因缓冲区被生产者进程占据而无法进入。这样就形成了生产者进程。在占有临界资源的情况下,等待消费者进程取走产品,而消费者进程又无法进入临界区取走产品的僵局,此时两进程陷入死锁。
6.在银行家算法中，若出现下述资源分配情况：
进 程
Allocation
Need
Available
A B C D
A B C D
A B C D
P0
P1
P2
P3
P4
0 3 2
1 0 0 0
1 3 5 4
0 3 3 2
0 0 1 4
0 0 1 2
1 7 5 0
2 3 5 6
0 6 5 2
0 6 5 6
1 6 2 2
试问:（1)该状态是否安全?
(2)如果进程P2提出请求Request（0,2,2,2〉后,系统能否将资源分配给它?
解:(1)利用银行家算法对此时刻的资源分配情况进行分析,可得此时刻的安全性分析情况。
进 程
Work
Need
Allocation
Work+Allocation
Finish
A B C D
A B C D
A B C D
A B C D
P0
P3
P4
P1
P2
1 6 2 2
1 6 5 4
1 9 8 6
1 9 9 10
2 9 9 10
0 0 1 2
0 6 5 2
0 6 5 6
1 7 5 0
2 3 5 6
0 0 3 2
0 3 3 2
0 0 1 4
1 0 0 0
1 3 5 4
1 6 5 4
1 9 8 6
1 9 9 10
2 9 9 10
3 12 14 14
true
true
trye
true
true
从上述分析中可以看出，此时存在一个安全序列{P0,P3,P4,P1,P2},故该状态是安全的。
（2）P2提出请求Request2(1,2,2,2),按银行家算法进行检查：
Request2(1,2,2,2)≤Need2(2,3,5,6)
Request2(1,2,2,2)≤Available(1,6,2,2)
试分配并修改相应数据结构，资源分配情况如下：
进 程
Allocation
Need
Available
A B C D
A B C D
A B C D
P0
P1
P2
P3
P4
0 3 2
1 0 0 0
2 5 7 6
0 3 3 2
0 0 1 4
0 0 1 2
1 7 5 0
1 1 3 4
0 6 5 2
0 6 5 6
0 4 0 0
再利用安全性算法检查系统是否安全,可用资源Available (0,4,0,0)已不能满足任何进程的需要,故系统进入不安全状态,此时系统不能将资源分配给P2。
7．有相同类型的5个资源被4个进程所共享,且每个进程最多需要2个这样的资源就可以运行完毕。试问该系统是否会由于对这种资源的竞争而产生死锁。
解:该系统不会由于对这种资源的竞争而产生死锁。因为在最坏情况下,每个进手里都需要2个这样的资源,且每个进程都己申请到了1个资源,那么系统中还剩下1个可用资源。无论系统为了满足哪个进程的资源申请而将资源分配给该进程,都会因为该进程己获得了它所需要的全部资源而确保它运行完毕,从而可将它占有的2个资源归还给系统,这就保证了其余三个进程能顺利运行。由此可知,该系统不会由于对这种资源的竞争而产生死锁。
8.己知某系统中的所有资源是相同的,系统中的进程严格按照一次一个的方式申请或薛放资源。在此系统中,没有进程所需要的资源数量超过系统的资源总拥有数量,试对下面列出的各种情况说明是否会发生死锁。
情况序号
系统中进程数
资源总量
a
b
c
d
1
2
2
2
2
1
2
3
解:情况a:因系统中仅在1个进程,且系统中资源总数为2,由题目所给条件可知,该进程的最大资源需求量不超过2,显然情况a不会出现死锁。
情况b：因系统中存在2个进程,且系统中资源总数为1,由题目所给条件可知,每个进程的最大资源需求量不超过1。不妨设两个进程的最大资源需求量为1,若系统将资源分配给其中的一个进程,则此进程已获得它所需要的所有资源并将运行完毕,从而可将分配给它的资源归还给系统,使另一个进程也能顺利执行完成,故不会发生死锁。
情况c：因系统中存在2个进程,且系统中资源总数为2,由题目所给条件可知,每个进程的最大资源需求量不超过2。假设两个进程的最大资源需求量为2,若系统将资源分配给其中的一个进程,则此进程已获得它所需要的所有资源并将运行完毕,从而可将分配给它的资源归还给系统,使另一个进程也能顺利执行完成,以这种方式分配资源不会发生死锁:若系统将资源分配给每个进程1个,在此情况下,每个进程均获得1个资源且系统中己没有空闲资源,当其中的一个进程再次申请1个资源时,因系统中无空闲资源而使其等待,另一个进程的情况也是如此,因此以这种方式分配资源会发生死锁。
情况d：因系统中存在2个进程,且系统中资源总数为3,由题目所给杂件可知,每个进程的最大资源需求量不超过3。假设两个进程的最大资源需求量为3,若系统将资源分配给其中的一个进程,则此进程已获得它所需要的所有资源并将运行完毕,从而可将分配给它的资源归还给系统,使另一个进程也能顺利执行完成,以这种方式分配资源不会发生死锁:若系统将资源分配给其中一个进程1个,另一个进程2个,在此情况下,每个进程均获得部分资源且系统中已没有空闲资源,当其中的一个进程再次申请资源时,因系统中无空闲资源而使其等待,另一个进程的情况也是如此,因此以这种方式分配资源会发生死锁。
9.考虑下列资源分配策略:对资源的申请和释放可以在任何时候进行。如果一个进程提出资源请求时得不到满足,若此时无由于等待资源而被阻塞的进程,则自己就被阻塞:若此时已有等待资源而被阻塞的进程,则检查所有由于等待资源而被阻塞的进程。如果它们有申请进程所需要的资源,则将这些资源取出分配给申请进程。
例如,考虑一个有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)。
①这种分配策略会导致死锁吗?如果会,请举一个例子:如果不会,请说明产生死锁的哪一个必要条件不成立?
②这种分配方式会导致某些进程的无限等待吗?为什么?
【分析及相关知识】所谓死锁是指多个进程因竞争资源而造成的一种僵局,若无外力作用,这些进程都将无法向前推进。死锁是计算机系统和进程所处的一种状态。发生死锁的必要条件有以下四个:互斥条件;不剥夺条件;部分分配条件;环路条件。
解:①本题所给的资源分配策略不会产生死锁。因为本题给出的分配策略规定若一进程的资源得不到满足,则检查所有由于等待资源而被阻塞的进程,如果它们有申请进程所需要的资源,则将这些资源取出分配给申请进程。从而破坏了产生死锁必要条件中的不剥夺条件,这样系统就不会产生死锁。
②这种方法会导致某些进程无限期的等待。因为被阻塞进程的资源可以被剥夺,所以被阻塞进程所拥有的资源数量在其被唤醒之前只可能减少。若系统中不断出现其他进程申请资源,这些进程申请的资源与被阻塞进程申请或拥有的资源类型相同且不被阻塞,则系统无法保证被阻塞进程一定能获得所需要的全部资源。例如,本题中的进程A申请(2,2,1〉后再申请(0,0,1〉被阻塞。此后,进程C又剥夺了进程A的一个资源,使得进程A拥有的资源变为〈1,2,1〉,其需求向量为(1,0,1〉。之后,若再创建的进程总是只申请第1和第3类资源,总是占有系统所剩下的第1和第3类资源的全部且不阻塞,那么进程A将会无限期地等待。
10.一个操作系统有20个进程,竞争使用65个同类资源,申请方式是逐个进行的,一旦某进程获得它所需要的全部资源,则立即归还所有资源。每个进程最多使用3个资源。若仅考虑这类资源,该系统有无可能产生死锁,为什么?
解：在本题中,若仅考虑这一类资源的分配,则不会产生死锁。因为死锁产生的原因有两点：系统资源不足或进程推进顺序不当。在本题介绍的系统中,进程所需要的最大资源数为：2OX3=60,而系统中共有该类资源65个,其资源数目己足够系统内的各进程使用,因此绝不可能发生死锁。
11.一台计算机有8台磁带机。它们由N个进程竞争使用,每个进程可能需要3台磁带机。请问N为多少时,系统没有死锁危险,并说明原因。
解：当N为1,2,3时,系统没有产生死锁的危险。因为,当系统中只有1个进程时,它最多需要3台磁带机,而系统有8台磁带机,其资源数目己足够系统内的1个进程使用,因此绝不可能发生死锁:当系统中有2个进程时,最多需要6台磁带机,而系统有8台磁带机,其资源数目也足够系统内的2个进程使用,因此也不可能发生死锁:当系统中有3个进程时,在最坏情况下,每个进程都需要3个这样的资源,且假定每个进程都己申请到了2个资源,那么系统中还剩下2个可用资源,无论系统为了满足哪个进程的资源申请而将资源分配给该进程,都会因为该进程已获得了它所需要的全部资源而确保它运行完毕,从而可将它占有的3个资源归还给系统,这就保证了其余进程能顺利运行完毕。由此可知,当N为1,2,3时,该系统不会由于对这种资源的竞争而产生死锁。
二、计算题
【例12】在银行家算法中,若出现下面的资源分配情况:
Process Allocation Need Available
PO 0 0 3 2 0 0 1 2 1 6 2 2
P1 1 0 0 0 1 7 5 0
P2 1 3 5 4 2 3 5 6
P3 0 0 3 2 0 6 5 2
P4 0 0 1 4 0 6 5 6
试问:
(1)该状态是否安全?
(2)若进程P2提出请求Request(1,2,2,2)后,系统能否将资源分配给它?
(3)如果系统立即满足P2的上述请求,请间,系统是否立即进入死锁状态?
答:(1)利用安全性算法对上面的状态进行分析(如表33所示),找到了一个安全序列{P0,P3,P4,P1,P2},故系统是安全的。
(2)P2发出请求向量Request(1,2,2,2)后,系统按银行家算法进行检查:
①Request2(1,2,2,2)≤Need2(2,,3,5,6);
②Request2(1,2,2,2) ≤Available(1,6,2,2);
③系统先假定可为P2分配资源,并修改Available,Allocation2和Need2向量:
Avmilable=(O,4,0,0)
Allocation2=(2,5,7,6)
Need2=(1,1,3,4)
④进行安全性检查:此时对所有的进程,条件Needi≤Available(O,4,0,0)都不成立,即
Available不能满足任何进程的请求,故系统进入不安全状态。
因此,当进程P2提出请求Request(1,2,2,2)后,系统不能将资源分配给它。
表3.3安全性检查过程资源情况进程
Work
A B C D
Need
A B C D
Allocation
A B C D
Work+Allocation
A B C D
Finish
P0
P3
P4
P1
P2
6 2 2
6 5 4
6 8 6
6 9 10
2 6 9 10
0 0 1 2
0 6 5 2
0 6 5 6
1 7 5 0
2 3 5 6
0 0 3 2
0 0 3 2
0 0 1 4
1 0 0 0
1 3 5 4
1 6 5 4
1 6 8 6
1 6 9 10
2 6 9 10
3 9 14 14
True
True
True
True
True
(3)系统立即满足进程P2的请求(1,2,2,2)后，并没有马上进入死锁状态。因为，此时上述进程并没有申请新的资源,并因得不到资源而进入阻塞状态。只有当上述进程提出新的请求,并导致所有没执行完的多个进程因得不到资源而阻塞时,系统才进入死锁状态。
12.设系统中有3种类型的资源(A,B,C)和5个进程P1、P2、P3、P4、P5,A资源的数量为17,B资源的数量为5,C资源的数量为20。在To时刻系统状态见表4.5所示。系统采用银行家算法实施死锁避免策略。
进 程
最大资源需求量
已分配资源数量
A B C
A B C
P1
P2
P3
P4
P5
5 5 9
5 3 6
4 0 11
4 2 5
4 2 4
2 1 1
4 0 2
4 2 5
2 0 4
3 1 4
①To时刻是否为安全状态?若是,请给出安全序列。
②在To时刻若进程P2请求资源(0,3,4〉,是否能实施资源分配?为什么?
③在②的基础上,若进程P4请求资源。,0,1〉,是否能实施资源分配?为什么?
④在③的基础上,若进程P1请求资源(0,2,0〉,是否能实施资源分配?为什么?
解：由题目所给出的最大资源需求量和己分配资源数量,可以计算出To时刻各进程的资源需求量Need,Need=最大资源需求量一分配资源数量:
进 程
资源需求量
A B C
P1
P2
P3
P4
P5
3 4 7
1 3 4
0 0 6
2 2 1
1 1 0
（1）利用银行家算法对此时刻的资源分配情况进行分析，可得此时刻的安全序性分析情况：
进 程
Work
A B C
Need
A B C
Allocation
A B C
Work+Allocation
A B C
Finish
P0
P3
P4
P1
P2
3 3
5 7 4
7 4 11
11 4 16
15 4 18
1 1 0
2 2 1
0 0 6
1 3 4
3 4 7
3 1 4
2 0 4
4 0 5
4 0 2
2 1 2
5 4 7
7 4 11
11 4 6
15 4 8
17 5 20
True
True
True
True
True
从上述情况分析中可以看出,此时存在一个安全序列{p5,P4,p3,P2,Pl},故该状态是安全的。
②在To时刻若进程P2请求资源(0,3,4),因请求资源数(0,3,4〉>剩余资源数(2,2,3),所以不能分配。
③在②的基础上,若进程P4请求资源(2,0,1),按银行家算法进行检查:
P4请求资源(2,0,1)<=P4资源需求量(2,2,1)
P4请求资源(2,0,1)<=剩余资源数(2,3,3〉
试分配并修改相应数据结构,资源分配情况如下:
进 程
Allocation
A B C
Need
A B C
Available
A B C
P0
P3
P4
P1
P2
1 2
4 0 2
4 0 5
4 0 5
3 1 4
3 4 7
1 3 4
0 0 6
0 2 0
1 1 0
0 3 2
再利用安全性算法检查系统是否安全，可得此时刻的安全性分析情况：
进 程
Work
A B C
Need
A B C
Allocation
A B C
Work+Allocation
A B C
Finish
P4
P5
P3
P2
P1
0 3 2
4 3 7
7 4 11
11 4 16
15 4 18
0 2 0
1 1 0
0 0 6
1 3 4
3 4 7
4 0 5
3 1 4
4 0 5
4 0 2
2 1 2
5 3 7
7 4 11
11 4 6
15 4 8
17 5 20
True
True
True
True
True
从上述情况分析中可以看出,此时存在一个安全序列{P4,P5,P3,P2,P1},故该状态是安全的,可以立即将P4所申请的资源分配给它。
④在③的基础上,若进程Pl请求资源(0,2,0〉,按银行家算法进行检查:
P1请求资源(0,2,0)<=P1资源需求量(3,4,7)
P1请求资源(0,2,0〉<=剩余资源数(0,3,2)
试分配并修改相应数据结构,资源分配情况如下:
进 程
Allocation
A B C
Need
A B C
Available
A B C
P0
P3
P4
P1
P2
3 2
4 0 2
4 0 5
4 0 5
3 1 4
3 2 7
1 3 4
0 0 6
0 2 0
1 1 0
0 1 2
再利用安全性算法检查系统是否安全,可用资源Available (0,1,2)已不能满足任何进程的资源需求,故系统进入不安全状态,此时系统不能将资源分配给P1。
16.假设有一台计算机,它有lM内存,操作系统占用200K,每个用户进程也占用200K。用户进程等待I/O的时间为80%,若增加lM内存,则CPU的利用率将提高多少?
【分析及相关知识】多道程序设计技术是指同时把多个作业放入内存并允许它交替执行,共享系统中的各类资源,当一道程序因某种原因(如I/0请求)而暂停执行时,CPU立即转去执行另一道程序。从上述定义可以看出多道程序系统具有多道、宏观上并行、微观上串行的特点。
多道程序设计技术使CPU的利用率大为提高。设在内存中有N个进程,每个进程等待I/0的百分比是P,那么N个进程同时等待I/0的概率是p^n(此时CPU空闲),即CPU的利用率为1-p^n,由此可见CPU的利用率是N的函数,称为多道程序度。
解:由题目所给条件可知,当前1M内存可支持4个用户进程,由于每个用户进程等待I/O的时间为80%,故CPU的利用率为,
1一(80%)^4=1一(0.8)^4=59%
若增加1M内存,则系统中可同时运行9个进程,则CPU的利用率为：
1一(0.8)^9=87%
故增加1M内存使CPU的利用率提高了：
87%÷59%=147%
147%-100%=47%
所以增加1M内存使CPU的利用率提高了47%。
17.设某计算机系统有一台输入机、一台打印机。现有两道程序同时投入运行,且程序A先开始运行,程序B后运行。程序A的运行轨迹为:计算50ms,打印信息100ms,再计算5Oms,打印信息100ms,结束。程序B的运行轨迹为:计算5Oms,输入数据8Oms,再计算100ms,结束.试说明:
(l)两道程序运行时,CPU有无空闲等待?若有,在哪段时间内等待?为什么会空闲等待?
(2)程序A、B运行时有无等待现象?若有,在什么时候会发生等待现象?
解:两道程序并发执行时的工作情况如图3.5所示。
中央处理机A计算B计算Atf算.B计算
从图3.5可以看出,两道程序运行期间,CPU存在空闲等待。空闲等待的时间段为程序A开始运行后100ms至150ms之间。在此期间,程序A正在打印信息,而程序B正在输入数据。
程序A启动运行后无等待现象,而在程序B启动运行后存在等待现象。程序B的等待时间段为A开始运行后180ms至200ms之间(或程序B启动运行后130ms至150ms之间〉。
18.设有两个处理机P1和P2,它们各有一个硬件高速缓冲存储器C1、C2,且各有一个主存储器MLM2,其性能如下所示:
C1 C2 M1 M2
存储容量 4KB 4KB 2MB 2MB
存储周期 60ns 80ns 1μs 0.9μs
假定两个处理机的指令系统相同,它们的指令执行时间与存储器的平均存取周期成正比。如果执行某个程序时,所需的指令或数据在缓冲存储器中存取到的概率P是0.7,试问这两个处理机的处理速度哪个快?当P=0.9时,处理机的处理速度哪个快?
解:由题目分析可知,处理机的平均存取时间T为:
T=T1+(1-P)T2
其中,T1为高速缓冲存储器的存取周期,T2为主存储器的存取周期,P为指令或数据在缓冲存储器中存取到的概率。〈1μs=1000nS〉
(1)当P=0.7时,P1的平均存取时间为:
60+(1-0.7)×10^3=360ns
P2的平均存取时间为:
80+(1-0.7)×0.9×10^3=350ns..
根据题意,指令执行时间与存储器的平均存取周期成正比,因此当P=0.7时,P2比P1的处理速度快。
〈2〉当P=0.9时,P1的平均存取时间为:
60+〈1-0.9〉* 10^3=160ns
P2的平均存取时间为:
80+(1-0.9)×0.9×10^3=170ns
因此当P=0.9时,Pl比P2的处理速度快。
19.有两个程序,A程序按顺序使用CPU 10秒,使用设备甲5秒,使用CPU 5秒,使用设备乙10秒,最后使用CPU lO秒。B程序按顺序使用设备甲10秒,使用CPU lO秒,使用设备乙5秒,使用CPU 5秒,使用设备乙10秒。在顺序环境下先执行A程序再执行B程序,CPU的利用率是多少?
解:由题目所给条件可知,两个程序顺序执行,先执行程序A,再执行程序B。
A程序的执行时间为:
10+5+5+10+10=40秒其中使用CPU时间为：
10+5+10=25秒
B程序的执行时间为：
10+10+5+5+10=40秒其中使用CPU时间为：
10+5=15秒两个程序的总执行时间为:
40+40=80秒其中使用CPU时间为:
15+25=40秒故CPU利用率为:
40/80=50%
20.假设就绪队列中有10个进程,系统将时间片设为200ms,CPU进行进程切换要花费10ms,试问系统开销所占的比率约为多少?
解:因就绪队列中有10个进程,它们以时间片轮转的方式使用CPU,时间片长度为200ms。当一个时间片用完时,调度进程将当前运行进程设置为就绪状态并放入就绪队列尾,再从就绪队列队首选择进程投入运行,这一过程(进程切换〉要花费时间10ms。因此系统开销所占比率为:
10/(200+10)=4.8%
4.4.3 自测题答案一、填空题
1.资源可分为可重用资源和消耗型资源两大类型,前者包括处理机、I/O通道、存储器、设备和文件等,后者包括如中断、消息和I/0缓冲区中的信息等.
2.通常情况下,进程对资源的利用是按照请求(申请)资源、使用资源、释放资源的顺序进行的,如打开、使用和关闭文件,分配、占用和回收内存空间等.
3.死锁的四个必要条件是互斥、占用并等待、非抢占和循环等待。
4.处理死锁的方法通常有死锁预防、死锁避免、死锁检测和死锁恢复。
5.为破坏占用并等待条件,采用资源的静态预分策略,系统对进程申请的资源进行一次性的分配,然后才启动该进程运行.
6.Banker算法是典型的死锁避免算法,要求系统必须知道未来的资源请求信息,进程要预先声明资源的最大需求量.
二、判断题j
1.× 2.√ 3,√ 4.×5 √,6.× 7.×
三、选择题
1.b)、d)、e)、f)
2.c)
3.a)、b)、c)、d)
4.a)、c)
5.b)、d)、e)、f)
6.d)
7.a)、b)、d)、e)
四、问答题
1.从河两岸分别过河的两人在河中相遇并踩上同一垫脚石.
①互斥:允许人们共享同一垫脚石.
②占有并等待:在能过河前,人们必须申请使用所有的垫脚石.
③抢占2允许一个人在别人过河时走到一旁的歇脚石上(撤离到安全态),或强行要求过河的另一方撤回(完全撤离).
④循环等待:这实质上意味着只允许用单行道方式过河.为了让两个方向的人都能过洞,得铺设另一串垫脚石供另一方向专用.
2.(1)此例中导致死锁的四个条件成立:
①互斥.每条道路只能被一辆车占用.
②占用并等待。每辆车都占用了一段道路,并等待其前方的道路被释放.
③非抢占.资源不可抢占.单行线,汽车不能抢路超车.
④循环等待.每辆车都等待着前方的汽车把路让出来,且形成了一个环路.
(2)在每个十字路口设置红绿灯,当南北方向的路通车时,东西方向的路上汽车等待.反之亦然.
3.(1)由于Need =Max-Allocation,所以Need的内容是:
0000
0750
1002
0020
0642
(2)是处于安全态,序列〈P。,PI,P2,P3,P4>满足安全性要求.
(3)能立即得到满足,因为
①(0420)<=Available =(1520)
②(0420)<=Maxi =(1750)
③分配后的新系统状态如表7.4所示,且序列〈Po,P1,p2,P3,P4〉满足安全性要求.
表7.4
allocation
Max
Need
Available
0012
0012
0000
1100
1420
1750
0330
1354
2356
1002
0632
0652
0020
0014
0656
0642
4.1内容辅导
4.1.1 处理机调度的基本概念
1.调度的类型一个作业从提交开始直到完成,往往要经历下述三级调度:
（1）作业调度 又称宏观调度或高级调度。其主要任务是按一定的原则对外存上处于后备状态的作业进行选择,给选中的作业分配内存、输入输出设备等必要的资源,并建立相应的进程,以使该作业的进程获得竞争处理机的权利。一般在批处理系统中大多配有作业调度,而在其他系统中通常不需配置作业调度。作业调度的执行频率较低,通常为几分钟一次。
（2）进程调度 又称微观调度或低级调度。其主要任务是按照某种策略和方法选取一个处于就绪状态的进程,将处理机分配给它。进程调度的运行频率很高,一般几十毫秒要运行一次。
（3）交换调度 又称中级调度。其主要任务是按照给定的原则和策略,将处于外存对换区中的重又具备运行条件的就绪进程调入内存,或将处于内存就绪状态或内存阻塞状态的进程交换到外存对换区。交换调度主要涉及内存管理与扩充,因此在存储管理部分介绍。
2,进程调度方式所谓进程调度方式是指当某一进程正在处理机上执行时,若有某个更为重要或紧迫的进程需要进行处理,即有优先权更高的进程进入就绪队列,此时应如何分配处理机。通常有两种进程调度方式:
（1）剥夺方式 所谓剥夺调度方式是指当一个进程正在处理机上执行时,若有某个更为重要或紧迫的进程需要使用处理机,则立即暂停正在执行的进程,将处理机分配给这个更重要或紧迫的进程。抢占的原则有:
(1)优先权原则。就绪的高优先权进程有权抢占低优先权进程的CPU。
(2)短作业优先原则。就绪的短作业(进程)有权抢占长作业(进程)的CPU。
(3)时间片原则。一个时间片用完后,系统重新进行进程调度。
（2）非剥夺方式 这种方式是当某一进程正在处理机上执行时,即使有某个更为重要或紧迫的进程进入就绪队列,仍然让正在执行的进程继续执行,直到该进程完成或发生某种事件而进入完成或阻塞状态时,才把处理机分配给更为重要或紧迫的进程。
对不同的调度方式,相应的调度算法也不同,进程调度的核心问题就是采用什么算法将处理机分配给进程。
4.1.2 处理机调度算法
1.先来先服务调度算法这是一种最简单的调度算法,即按照进程进入就绪队列的先后次序来分配处理机。先来先服务算法属于非剥夺的调度方式,一旦一个进程占有处理机,就一直运行下去,直到该进程完成其工作或因等待某一事件而不能继续执行时才释放处理机。采用这种进程调度方式,若一个运行时间长的作业先占有了处理机,则会使很多晚到的运行时间短的作业等待时间过长，引起许多短作业用户的不满。因此这种方式很少被用作主要调度策略,但它常作为一种辅助调度算法使用。
(2)短作业(进程)优先(SJF/SPF)算法该算法是指短作业或短进程优先调度的算法。短进程优先调度算法是选择就绪队列中估计运行时间最短的进程技入执行,它既可采用抢占方式,也可采用非抢占方式。抢占的
SW算法通常也叫做最短剩余时间优先算法。SPF算法能有效地缩短作业的平均周转时间,
提高系统的吞吐量,但不利于长作业和紧迫作业的运行。由于估计的运行时间不一定准确,
因而它不一定能真正做到短作业优先。
（3）高晌应比优先调度(HRRN)算法
（4））最高优先权优先调度算法这是一种最常用的进程调度算法,即把处理机分配给优先权最高的进程。进程的优先权用于表示进程的重要性及运行的优先性,通常分为两种:静态优先权和动态优先权。
静态优先权是在创建进程时确定的;确定之后在整个进程运行期间不再改变。确定静态优先权的依据有进程的类型、进程所使用的资源、进程的估计运行时间等因素。进程所索取的资源越多,估计的运行时间越长,进程的优先权越低。进程类型不同,优先权也不同,如联机用户进程的优先权高于脱机用户进程的优先权。
动态优先权是指在创建进程时,根据系统资源的使用情况和进程的当前特点确定一个优先权,在进程运行过程中再根据情况的变化调整优先权。动态优先权一般根据进程占有CPU时间的长短、进程等待CPU时间的长短等因素确定。占有处理机的时间愈长,则优先权越低；等待时间越长,优先权越高。
基于优先权的调度算法还可按调度方式不同分为非剥夺优先权调度算法和可剥夺优先权调度算法。
（5）时间片轮转调度算法在这种调度算法中,系统将所有就绪进程按到达时间的先后次序排成一个队列,进程调度程序总是选择队列中的第一个进程执行,且仅能执行一个时间片。在使用完一个时间片后,即使进程并未完成其运行,也必须将处理机交给下一个进程。
时间片的长短对计算机系统的影响很大。如果时间片大到让一个进程足以完成其全部工作,这种算法就退化为先来先服务算法。若时间片很小,那么处理机在进程之间的转换工作过于频繁,处理机真正用于运行用户程序的时间将减少。时间片长短的值应能使分时用户得到好的响应时间。
（6）多级反馈队列调度算法在采用多级反馈队列调度算法的系统中,调度算法的实施过程如下：
首先应设置多个就绪队列,并为各个队列赋予不同的优先权。第一个队列的优先权最高,第二队列次之,其余队列的优先权逐个降低。
其次,赋予各个队列中进程执行时间片的大小也各不相同,在优先权愈高的队列中,每个进程的执行时间片就规定得愈小。例如,第i+1队列的时间片是第i队列时间片的两倍。
第三,当一个新进程进入内存后,首先将它放入第一队列的末尾,按先来先服务的原则排队等待调度。当轮到该进程执行时,如能在该时间片内完成,便可准备撤离系统；如果它在一个时间片结束时尚未完成,调度程序便将该进程转入第二队列的末尾,再同样地按先来先服务原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成,再以同样方法将它转入第三队列。如此下去,当一个长作业从第一队列降到最后一个队列后,在最后一个队列中使用时间片轮转方式运行。
第四,仅当第一队列空闲时,调度程序才调度第二队列中的进程运行:仅当第1至(i一1〉
队列均为空时,才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时,
又有新进程进入优先权较高的队列,则此时新进程将抢占正在运行进程的处理机,即由调度程序把正在执行进程放回第i队列末尾,重新将处理机分配给新进程。
4.实时调度实时系统中的任务通常都联系着一个截止时间,实时调度的关键是保证满足实时任务:
对截止时间的要求。
为了保证满足实时任务对截止时间的要求,实时系统必须具备足够强的处理能力和快速的切换机制。通常,在提交实时任务时,系统将该任务的截止时间、所需的处理时间、资源要求和优先级等信息一起提交给调度程序。若系统能及时处理该任务,调度程序便将它接收下来,否则,将拒绝接收该任务。
对不同的实时系统,其调度方式和算法的选择也各不相同。在一些小型实时系统或要求不太严格的实时控制系统中,常采用简单易行的非抢占式轮转调度方式,它可获得数秒至数十秒的响应时间:而在有一定要求的实时控制系统中,可采用非抢占式优先权调度算法,它可获得仅为数秒至数百毫秒级的响应时间。在要求比较严格(响应时间为数十毫秒以下)的实时系统中,应采用比较复杂的抢占调度方式,其中,基于时钟中断的抢占式优先权调度算法,可获得几十毫秒至几毫秒的响应时间,适用于大多数的实时系统:丽立即抢占的优先权调度算法,可将响应时间降到几毫秒至1∞微秒,甚至更低,适用于要求更严格的实时系统。下面将介绍两种常用的高优先权优先的实时调度算法。
(1)最早截止时间优先CEDE币算法：该算法根据任务的开始截止时间来确定任务的优先级,即任务的开始截止时间愈早,其优先级愈高。在实现该算法时,要求系统中保持-个实时任务就绪队列,该队列按各任务的截止时间的早晚排序。EDF算法即可采用非抢占调度方式,也可采用抢占调度方式。在采用抢占调度方式时,如果新到达的任务的开始截止时间比正在执行的任务早,则它将立即抢占CPU。:
(2)最低松弛度优先(LLF)算法。LIF算法根据实时任务的松弛度(松弛度=任务必须完成的时间一任务本身的运行时间一当前时间)来确定任务的优先权,即任务的松弛度愈低,其优先权愈高。在实现该算法时,要求系统中有一个按松弛度排序的实时任务就绪队列。
该算法主要用于可抢占调度方式中,当一任务的最低松弛度减为0时,它便必须立即抢占
CPU,以保证按截止时间的要求完成任务。
5.多处理机系统中的调度
1.进程分配方式在对称多处理器系统(SMPS)中,各处理器单元在功能和结构上都是相同的,因而可把所有的处理器作为一个处理器池?并将进程分配到其中的任干处理器上运行。在进行进程分配时,可采用静态和动态两种分配方式。采用静态分配方式时,一个进程从开始执行直至其完成,都被固定分配到一个处理器上去执行,此时,需要为每个处理器维护一个专用的就绪队列。静态分配方式的优点是调度的开销小,缺点是会使处理器的忙闲不均。采用动态分配方式时,系统中设置有二个公用的就绪队列,所有的就绪进程都被放在该队列中,然后被随机地调度到任一空闲的处理器上去执行,因此,在一个进程生命周期的不同时刻,它可以在不同的处理器上执行,对松散祸合的多处理器系统,此时需要进行进程现场信息的转移,会明显增加调度开销,但动态分配方式能较好地消除处理器忙闲不均的现象。
在配置有多种类型处理器单元的非对称多处理器系统中,常采用主一从式结构,即操作系统的核心驻留在某个特定的处理器(即主处理器)上,而其他的处理器(即从处理器)只用于执行用户程序。进程调度由主处理器执行,从处理器空闲时,便向主处理器发一索求进程的信号,并由主处理器从自己的就绪队列中摘下一个进程分配给请求的从处理器。这种方式的优点是系统处理简单,缺点是主处理器的故障会导致整个系统瘫痪,而且主处理器容易成为系统瓶颈。
2.进程(线程)调度方式在多处理机系统中,常用的进程(线程)调度方式主要有:
(1)自调度方式。-它是指在系统中设置一个公用的进程(或线程)队列,所有的处理器在空闲时,都可自己到该队列中取一进程(或线程)来执行。
(2)成组调度方式。它是指将一组相互合作的进程或隶属于国一个进程的一组线程分配到一组处理器上去同时执行。
(3)专用处理器分配方式。它是指在一个应用程序的执行期间,专门为该应用程序分配一组处理器,每一个线程一个处理器。这组处理器仅供该应用程序专用,直至该应用程序完成。
4.1.3 死 锁
1.死锁的概念所谓死锁是指多个进程因竞争资源而造成的一种僵局,若无外力作用,这些进程都将无法向前推进。死锁是计算机系统和进程所处的一种状态。
2,产生死锁的原因和必要条件
（1）死锁产生的原因死锁产生的原因有以下两点:
①系统资源不足 例如在上面的例子中,若系统中有两台打印机或者两台输入设备可供进程P1和P2使用,当其中任一个进程提出设备请求后,立即可得到满足,显然不会出现死锁状态。这就是说,如果系统中有足够的资源可供每个进程使用,死锁就不会发生。所以说,产生死锁的根本原因是可供多个进程共亭的系统资源不足。当然,只有当进程提出资源请求时,才会发生死锁。
②进程推讲顺序不当 例如在上面的例子中,若进程P2在P1提出使用输入设备的要求之前,已经完成了对输入设备和打印机的使用,并且释放了它们；或者是在进程P2提出使用打印机的请求之前,进程Pl已经完成了对输入设备和打印机的使用,并且释放了它们,则均不会发生死锁。
（2）死锁产生的必要条件发生死锁的必要条件有以下四条：
①互斥条件：造程要求对所分配的资源进行排它性控制,即在一段时间内某资源仅为一个进程所占有。
②不剥夺条件：进程所获得的资源在未使用完毕之前,不能被其他进程强行夺走,即只能由获得该资源的进程自己来释放。
③部分分配条件：进程每次申请它所需要的一部分资源。在等待新资源的同时,进程继续占有己分配到的资源。
④环路条件：存在一种进程资源的循环等待链,链中的每一个进程已获得资源的同时被链中下一个进程所请求。
3.死锁的预防根据以上讨论,要想防止死锁的发生,只需破坏死锁产生的四个必要条件之一即可。
（1）破坏互斥条件破坏互斥条件就是要允许多个进程同时访问资源。但是这受到资源本身固有特性的限制,有些资源根本不能同时访问,只能互斥访问。比如打印机,就不允许多个进程在其运行期间交替打印数据,打印机只能互斥使用。因此,企图通过破坏互斥条件防止死锁的发生是不大可能的。
（2）破坏不剥夺条件为了破坏不剥夺条件,可以制定这样的策略:一个已获得某些资源的进程,若新的资源请求不能立即得到满足,则它必须释放所有己获得的资源,以后需要再重新申请。这意味着,一个进程已获得的资源在运行过程中可被剥夺,从而破坏了不剥夺条件。该策略实现起来比较复杂,释放已获得资源可能造成前一段工作的失效,重复申请和释放资源会增加系统开销,降低系统吞吐量。
（3）破坏部分分配条件为了破坏部分分配条件,就要求所有进程一次性申请它所需要的全部资源。若系统有足够的资源分配给进程,便一次把所有的资源分配给该进程。但在分配时只要有一种资源要求不能满足,则资源全不分配,进程等待。显然这种资源分配方法造成了严重的资源浪费,以打印机为例,一个作业可能只在最后完成时才需要打印计算结果,但在它运行前就把打印机分配给了它,那么在作业的整个执行过程中打印机完全处于闲置状态。
（4）破坏环路条件为了破坏环路条件,可以采用有序资源分配法。即将系统中的所有资源都按类型赋予一个编号,如打印机为1,磁带机为2,等等。并且要求每一个进程均严格地按照编号递增的次序请求资源。也就是说,只要进程提出请求资源Ri,则在以后的请求中,只能请求排在Ri后面的那些资源。为资源编号〉,不能再要求编号低于Ri的那些资源。对资源请求作了这样的限制后,系统中就不会再出现几个进程对资源的请求成为环路的情况。这种方法存在的主要问题是各种资源编号后不宜修改,从而限制了新设备的增加:尽管在为资源编号时己考虑到大多数作业实际使用这些资源的顺序,但也经常会发生作业使用资源的顺序与系统规定顺序不同的情况,从而造成资源的浪费。
4 死锁的避免在预防死锁的方法中所采取的几种策略,总的说来都施加了较强的限制条件,虽然实现起来较为简单,但却严重地损害了系统性能。在避免死锁的方法中,所施加的限制条件较弱,有可能获得较好的系统性能。在该方法中,把系统的状态分为安全状态和不安全状态,只要能使系统始终处于安全状态,便可避免死锁的发生。
（1）安全与不安全状态在避免死锁的方法中,允许进程动态地申请资源,系统在进行资源分配之前,先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态,便将资源分配给进程,否则进程等待。
若在某一时刻,系统能按某种顺序如〈P1、P2、…、Pn〉来为每个进程分配其所需的资源,直至最大需求,使每个进程都可顺利地完成,则称此时的系统状态为安全状态,称序列〈P1、P2、…、pn>为安全序列。若某一时刻系统中不存在这样一个安全序列,则称此时的系统状态为不安全状态。
虽然并非所有不安全状态都是死锁状态,但当系统进入不安全状态后,便可能进入死锁状态:反之,只要系统处于安全状态,系统便可避免进入死锁状态。
（2）利用银行家算法避免死锁
Dijkstra给出的银行家算法是具有代表性的避免死锁算法。为实现银行家算法,系统中必须设置若干数据结构。
银行家算法的数据结构如下:
(1)可利用资源向量Available,它是一个含有m个元素的数组,其中的每一个元素代表一类可利用的资源数目,其初始值是系统中所配置的该类全部可用资源数目。其数值随该类资源的分配和回收而动态地改变。如果Available (j)=K,表示系统中现有Rj类资源k个。
(2)最大需求矩阵Max,这是一个n ×m的矩阵,它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max(i,j〉=k,表示进程i需要Rj类资源的最大数目为k。
(3)分配矩阵Allocation,这是一个n×m的矩阵,它定义了系统中每一类资源当前己分配给每一个进程的资源数。如果Allocation (i,j)=k,表示进程i当前已分到Rj类资源的数目为k。Allocationi表示进程i的分配向量,由矩阵Allocation的第i行构成。
（4）需求矩阵Need,它是一个n×m的矩阵,用以表示每一个进程还需要的各类资源数。如果Need G,j〉哇,表示进程i还需要RJ类资源k个,才能完成其任务。Needi表示进程i的需求向量,由矩阵Need的第i行构成。
上述三个矩阵间存在关系:
Need (i,j)=Max(i,j)-Allocation (i,j)
银行家算法如下:
Requesti是进程Pi的请求向量。Requesti(j)=k表示进程Pi请求分配Rj类资源k个。
当Pi发出资源请求后,系统按下述步骤进行检查z
（1）如果Requesti<=Need,则转向步骤(2);否则,认为出错,因为它所需要的资源数已超过它所宣布的最大值。
(2)如果Requesti<=Available,则转向步骤(3〉;否则,表示系统中尚无足够的资源满足Pi的申请,Pi必须等待。
(3)系统试探把资源分配给进程Pi,并修改下面数据结构中的数值:
Available =Available-Requesti;
Allocationi=Allocationi+Requesti;
Needi=Needi-Requesti;
(4)系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态。若安全,才正式将资源分配给进程Pi,以完成本次分配:否则,将试探分配作废,恢复原来的资源分配状态,让进程Pi等待。
系统所执行的安全性算法描述如下:
(1)设置两个向量。
Work它表示系统可提供给进程继续运行的各类资源数目,它含有m个元素,开始执行安全性算法时,Work =Availabh。
Finish它表示系统是否有足够的资源分配给进程,使之运行完成,开始时,
Finish (i)=false:当有足够资源分配给进程Pi时,令Finish (i)=true.
(2)从进程集合中找到一个能满足下述条件的进程。
Finish (i〉==false:
Needi<=Work:
如找到则执行步骤(3〉:否则,执行步骤(4)。
(3)当进程Pi获得资源后,可顺利执行直到完成,并释放出分配给它的资源,故应执行
Work =work+Allocationi:
Finish (i〉=true:
Goto step2:
(4)若所有进程的Finish(i)都为true,则表示系统处于安全状态:否则,系统处于不安全状态。
5．死锁的检测和解除
（1）死锁的检测前面介绍的死锁预防和避免算法都是在系统为进程分配资源时施加限制条件或进行检测，若系统为进程分配资源时不采取任何措施，则应该提供检测和解除死锁的手段。
发现死锁的原理是考察某一时刻系统状态是否合理,即是否存在一组可以实现的系统状态,能使所有进程都得到它们所申请的资源而运行结束。检测死锁算法的基本思想是:
获得某时刻t系统中各类可利用资源的数目向量w(t〉,对于系统中的一组进程{Pl、P2、…、pn},找出那些对各类资源请求数目均小于系统现在所拥有的各类资源数目的进程。我们可以认为这样的进程可以获得它们所需要的全部资源并运行结束,当它们运行结束后释放所占有的全部资源,从而使可用资源数目增加,这样的进程加入到可运行结束的进程序列L中,然后对剩下的进程再作上述考察。如果一组进程{P1、P2、…、Pn}中有几个进程不在序列L中,那么它们会发生死锁。
检测死锁可以在每次分配后进行。但是,用于检测死锁的算法比较复杂,所花的检测时间长,系统开销大,因此,也可以选取比较长的时间间隔来执行。
（2）死锁的解除一旦系统成为死锁状态,就应将系统从死锁状态解脱出来,即解除死锁,使系统恢复到正常状态。解除死锁的常用方法有两种:
①资源剥夺法：当发现死锁后,从其他进程剥夺足够数量的资源给死锁进程,以解除死锁状态。
② 撤消进程法：此方法是采用强制手段从系统中撤消一个或一部分死锁进程，并剥夺这些进程的资源供其他死锁进程使用。
最简单的撤消进程方法是撤消全部死锁进程,使系统恢复到正常状态。但这种做法付出的代价太大。另一方法是按照某种顺序逐个撤消死锁进程,直到有足够的资源供其他未被撤消的进程使用,消除死锁状态为止。
4.2重点难点学习提示本章的学习目的主要是使学生理解和掌握处理机调度和死锁的基本概念,为此应对以下几个重点、难点问题作认真而深入的学习。
1.高优先权优先调度和基于时间片的轮转调度算法高优先权优先调度和基于时间片的轮转调度算法是目前被广泛使用的两种进程调度算法,读者应对它们有较深入的理解和掌握。
(1)什么是高优先权优先调度算法：这是指将处理机分配给就绪队列中优先权最高的进程的调度算法。在学习时应了解系统是根据哪些因素来确定一个进程的优先权的,在采用动态优先权的系统中又将根据哪些因素来调整运行进程的优先权。
(2)什么是高响应比优先调度算法：这是指以响应比作为进程的优先权的进程调度算法。在学习时应了解高响应比优先调度算法是为了解决什么问题而引入的,它有何优缺点。
(3)什么是时间片轮转算法：这是指让就绪进程以FCFS的方式按时间片轮流使用CPU的调度方式。在学习时应了解时间片的概念是为了解决什么问题而引入的,它是如何解决上述问题的。
(4)什么是多级反馈队列调度算法：该算法设置了多个就绪队列,并给每个队列赋予不同的优先权和时间片。在学习时应了解该算法是如何对各个就绪队列中的进程进行进程调度的,为什么它能较好地满足各种类型用户的需要。
2.常用的几种实时调度算法根据确定实时任务优先权方法的不同,可形成以下两种常用的实时调度算法:
(1)最早截止时间优先(EDF)算法：在学习时应了解EDF算法是根据什么来确定任务的优先权的,或者说它是如何保证满足各任务对截止时间的要求的。
(2)最低松弛度优先(LLF)算法：在学习时应了解LLF算法是根据什么来确定任务的优先级的,在什么情况下,一个进程应抢占被另一进程占用的CPU。
3.多处理机环境下的进程(线程)调度方式多处理机系统己广为流行多年,目前,己出现了多种多处理机环境下的进程(线程)调度方式,故读者应对下述几种比较有代表性的调度方式有较好的了解：
(1)自调度方式：自调度方式是多处理机环境下最简单的一种调度方式,在学习时应了解它是如何为就绪进程(线程)分配处理机的,该方式主要有什么优点,以及它存在哪些缺点
(2)成组调度方式：它将一组相互合作的进程或隶属于同一个进程的一组线程分配到一组处理器上去同时执行,读者应了解为什么成组调度方式的性能会优于自调度方式。
(3)专用处理器分配方式：这种方式有可能造成部分处理机的严重浪费,读者必须了解在并行程度相当高的多处理器环境下,为什么这种浪费是值得的,它换来了什么好处。
4.死锁的基本概念死锁是指多个进程竞争资源而形成的一种僵局,若无外力的作用,这些进程将无法再向前推进。可见,死锁状态不同于一般的阻塞状态。在学习时,读者应对下述两个问题有较深刻的理解和掌握:
(1)产生死锁的原因是什么：产生死锁的根本原因是竞争资源和进程推进顺序非法,在学习时应了解这两个根本原因与OS的两个基本特征并发和其事之间存在着什么样的联系。
(2)产生死锁的必要条件有哪些。产生死锁的必要条件奋互斥条件、请求与保持条件、不剥夺条件和环路等待条件,在学习时请思考如果其中的一个条件不满足,为什么不会产生死锁。
5.预防死锁的方法预防死锁是通过摒弃死锁产生的必要条件来达到防止死锁产生的目的的在学习时应了解下述几个方面的内容:
(1)摒弃"互斥"条件：应了解"互斥"条件为什么很难被摒弃,对某些(极少数的)互斥共享的设备(如打印机)又可通过什么技术来摒弃互斥条件。
（2）摒弃"请求和保持"条件：读者应了解可通过哪些方法来摒弃"请求和保持"条件它们对进程的运行和系统资源的利用率造成了什么样的影响。
(3)摒弃"不剥夺"条件：读者应了解可通过哪些方法来摒弃"不剥夺"条件,这些法有什么缺点。
(4)摒弃"环路等待"条件：读者应了解可通过哪些方法来摒弃"环路等待"条件,它对系统和用户带来了哪些不便,对资源的利用率又有什么影响。
（5）各种方法的比较：读者应从实现的简单性和资源的利用率等方面比较上述几种预防死锁的方法,以了解哪种方法实现最简便,哪种方法可使资源利用率受损最少。
6.利用银行家算法避免死锁银行家算法是一种最有代表性的避免死锁的算法。在学习时应对下述几个方面的内容国有较好的理解：
(1)避免死锁的实质在于如何防止系统进入不安全状态二在学习时,读者必须清晰地认识到,为什么系统处于安全状态便可避免进入死锁状态,而处于不安全状态则极有可能导致死锁状态的产生。
(2)在银行家算法中用到了可利用资源向量Available、最大需求矩阵Max、分配矩阵
Allocation、需求矩阵Need等数据结构，而在安全性检查算法中则还要用到工作向量Work
和完成向量Finish等数据结构,读者应对它们的物理意义和相互关系有较好的理解。
(3)安全性检查算法的目的是寻找一个安全序列。在学习时应了解满足什么条件的进程Pi,其对资源的最大需求可以得到满足,故可顺利完成:当Pi完成后,应如何修改工作向量Work和完成向量Finish。
(4)在利用银行家算法避免死锁时应了解,系统什么时候可以为提出资源请求的进程试行分配资源,什么时候才可以正式将资源分配给进程。
4.3典型问题分析和解答
1.为什么说多级反馈队列调度算法能较好地满足各方面用户的需要?
答:对终端型作业用户而言,他们提交的作业大多属于交互型作业,作业通常较小,系统只要能使这些作业在一个队列所规定的时间片内完成,便可使他们都感到满意。对短批处理作业用户而言,开始时他们的作业像终端型作业一样,如果仅在第一个队列中执行一个时间片即可完成,便可获得与终端型作业一样的响应时间:对于稍长的作业,通常也只需在第二队列和第三队列各执行一个时间片即可完成,其周转时间仍然很短。对长批处理作业用户而言,他们的作业将依次在第1,2,…,n个队列中运行,然后再按轮转方式邑行,用户不必担心其作业长期得不到处理； 而且每往下降一个队列，其得到的时间片将随着增加,故可进一步缩短长作业的等待时间。
2.假设一个系统中有5个进程,它们的到达 表4.1进程到达和需服务时间时间和服务时间如表4.1所示,忽略I/0以及进程
到达时间
服务时间
A
0
3
B
2
6
C
4
4
D
6
5
E
8
2
其他开销时间,若分别按先来先服务(FCFS)、非抢
占及抢占的短进程优先（SPF）、高响应比优先
(HRRN)、时间片轮转(RR,时间片=1)、多级反馈队列(FB,第i级队列的时间片=2^i-1)以及立即枪占的多级反馈队列(FB,第i级队列的时间片=2^i-1)
调度算法进行CPU调度,请给出各进程的完成时间、
周转时间、带权周转时间、平均周转时间和平均带权周转时间。
分析：进程调度的关键是理解和掌握调度所采用的算法。FCFS算法选择最早进入就绪队列的进程投入执行;SPF算法选择估计运行时间最短的进程投入执行,采用抢占方式时,若新就绪的进程运行时间比正在执行的进程的剩余运行时间短,则运行时间+等待时间新进程将抢占CPU;HRRN算法选择响应比(响应比=最高的运行时间+等待时间/运行时间)最高的进程投入执行;RR算法中,就绪进程按FIFO方式排队,CPU总是分配给队首的进程,并只能执行一个时间片;FB算法将就绪进程排成多个不同优先权及时间片的队列,新就绪进程总是按FIFO方式先进入优先权最高的队列,CPU也总是分配给较高优先权队列上的队首进程,若执行一个时间片仍未完成,则转入下一级队列的末尾,最后一级队列则采用时间片轮转方式进行调度。
答：各进程的完成时间、周转时间和带权周转时间(如表4.2所示)
表4.2进程的完成时间和周转时间
进程
A
B
C
D
E
平 均
FCFS
完成时间周转时间带权周转时间
3
3
1.00
9
7
1.17
13
9
2.25
18
12
6.00
20
12
6.00
8.6
2.56
SPF(非抢占)
完成时间周转时间带权周转时间
3
3
1.00
9
7
1.17
15
11
2.75
11
3
1.5
11
3
1.5
7.6
1.84
SPF(抢占)
完成时间周转时间带权周转时间
3
3
1.00
15
13
2.16
8
4
1.00
10
2
1.00
10
2
1.00
7.2
1.59
HRRN
完成时间周转时间带权周转时间
3
3
1.00
9
7
1.17
13
9
2.25
15
7
3.5
15
7
3.5
8
2.14
RR(q=1)
完成时间周转时间带权周转时间
4
4
1.33
17
13
3．25
17
13
3.25
20
14
2.8
15
7
3.5
10.8
2.71
FB(q=2^i-1)
完成时间周转时间带权周转时间
3
3
1
17
15
2.50
18
14
3.50
20
14
2.8
14
6
3.00
10.4
2.56
FB(q=^i-1)
(立即抢占
完成时间周转时间带权周转时间
4
4
1.33
18
16
2.67
15
11
2.75
20
14
2.8
16
8
4.00
10.6
2.87
3.何谓自调度方式?其主要优缺点是什么?
答:自调度方式是多处理器系统中的一种处理机调度方式,它在系统中设置一个公用的进程(或线程)队列,所有的处理器在空闲时,都可自己到该队列中取一进程(或线程)来执行。在自调度方式中,可采用单处理机环境下的进程调度算法(如先来先服务、最高优先权优先、抢占式最高优先权优先调度算法等)来进行进程调度。
自调度算法的主要优点是:①系统中公用就绪队列的组织方式以及具体的进程(或线程)
调度算法都可沿用单处理机中的方式,因而容易实现:②不会发生处理器忙闲不均的现象,因而有利于提高处理器的利用率。
而它的缺点主要是:①公用就绪队列很容易成为整个系统的瓶颈:②一个线程在整个生命期中,可能要多次更换处理器,从而使处理器上的高速缓存使用率降低,并进一步降低整个系统的性能:③相互合作型的线程很难同时获得处理器而同时运行,这将会增加合作线程之间的阻塞频率,从而提高线程切换的频率,增加系统的开销并降低进程的运行速度。
4.何谓成组调度方式?其主要优点是什么?
答:成组调度方式是多处理器系统中的一种处理机调度方式,它将一组相互合作的进程或一个进程的一组线程分配到一组处理器上去同时执行。
成组调度的主要优点是:如果一组相互合作的进程或线程能并行执行,则可有效地减少同步阻塞的现象,从而可以减少进程和线程的切换次数,使系统性能得到改善；另外,由于每次调度都可以解决一组进程或线程的处理器分配问题,因而可显著地减少调度频率,降低调度开销。
5,产生死锁的四个必要条件是什么?试以过河问题中产生的死锁为例加以说明。
答：产生死锁的必要条件如下：
(1)互斥:系统中至少有一个(类)资源必须用非共享方式使用。过河问题中,每一块垫脚石任一时刻仅能为一个人占用。
(2)占用并等待:一个进程至少占有一个资源并正等待得到其他资源,而这些资源已被其他进程所占用.过河问题中,相遇的两个人各自踏在一块垫脚石上,并同时等待踏上对方占用的那一块。
(3)非抢占:资源不可能被抢占.在过河问题中,由于垫脚石不能强行移动,"非抢占"条件满足。
(4)循环等待:存在循环等待情况。从东岸来的人等着从西岸来的人，而从西岸来的人则等着从东岸来的人。
于是,大家都不能过河,每人都等待对方从其占用的垫脚石上移开脚,具备以上四个条件,死锁发生.
6.在哲学家就餐问题中,如果将先拿起左边的筷子的哲学家称为左撇子,而将先拿起右边的筷子的哲学家称为右撇子,请说明在同时存在左撇子和右撇子的情况下,任何就座安排都不会产空死锁。
分析：这类题目的关键是必须证明产生死锁的4个必要条件的其中一个不可能望成立。在本题中,互斥条件、请求与保持条件、不剥夺条件是肯定成立的,因此必须证明"循环等待"条件不成立。
答:对本题,死锁产生的必要条件-一"循环等待"不可能成立。如果存在所有左边的哲学家等待右边的哲学家放下筷子的循环等待链,则每个哲学家肯定已获得左边的筷子,但还没得到右边的筷子,这与存在右撇子的情况不符:同样,也不可能存在相反的循环等待链。而且,系统中也不可能存在5个以下哲学家的循环等待链,因为,不相邻的哲学家之间不竞争资源。因此,不可能产生死锁。
7.假定系统中有五个进程{P0,P1,P2,P3,P4}和三种类型的资源{A,B,C},每一种资源的数量分别为10、5、7,在To时刻的资源分配情况如表4.3所示。
表4.3 To时刻的资源分配表资源情况进程
MAX
Allocation
Need
Available
A B C
A B C
A B C
A B C
PO
P1
P2
P3
P4
7 5 3
3 2 2
0 2
2 2 2
4 3 3
0 1 0
2 0 0
(3 0 2)
3 0 2
2 1 1
0 0 2
7 4 3
1 2 2
(0 2 0)
6 0 0
0 1 1
4 3 1
3 3 2
(2 3 0)
(1)To时刻的安全性利用安全性算法对To时刻的资源分配情况进行分析,可得到如表4.4所示的To时刻的安全性分析,从表中得知,To时刻存在着一个安全序列{Pl、P3、P4、P2、PO}故系统是安全的。 表 4.4 T0时刻的安全序列
资源分配进程
Work
Need
Allocation
Work+Allocation
Finish
A B C
A B C
A B C
A B C
P1
P3
P4
P2
P0
3 2
5 3 2
7 4 2
7 4 5
10 4 7
1 2 2
0 1 1
4 3 1
6 0 0
7 4 3
2 0 0
2 1 1
0 0 2
3 0 2
0 1 0
5 3 2
7 4 3
7 4 5
10 4 7
10 5 7
true
true
trye
true
true
（2）P1请求资源
Pl发出请求向量Request1（0,0,2〉,系统按银行家算法进行检查：
Request1(1,0,2〉<=Need1(1,2,2〉
Request1〈1,0,2〉<=Available (3,3,2)
系统先假定可为P1分配资源,并修改Available、Allocationl、Needl向量,由此形成的资源变化情况如表3.1中的圆括号所示。
我们再利用安全性算法检查此时系统是否安全,可得到如表4.5所示的安全性分析。
表 4.5 P1申请资源时的安全性检查
资源分配进程
Work
Need
Allocation
Work+Allocation
Finish
A B C
A B C
A B C
A B C
P1
P3
P4
P0
P2
3 0
5 3 2
7 4 3
7 4 5
7 5 5
0 2 0
0 1 1
4 3 1
7 4 3
6 0 0
3 0 2
2 1 1
0 0 2
0 1 0
3 0 2
5 3 2
7 4 3
7 4 5
7 5 5
10 5 7
true
true
trye
true
true
从进行的安全性检查得知,可以找到一个安全序列{P1、P3、P4、PO、P2}。因此,系统是安全的,可以立即将P1所申请的资源分配给它。
(3)P4请求资源
P4发出请求向量Requesu(3,3,0),系统按银行家算法进行检查:
Request4(3,3,0)<=Need4(4,3,1)
Request4(3,3,0)>Available (2,3,0),让P4等待。
(4)PO请求资源
PO发出请求向量Requesto(0,2,0),系统按银行家算法进行检查:
Requesto(0,2,0〉<=Needo(7,4,3)
Requesto(0,2,0)<=Available (2,3,0)
系统先假定可为P0分配资源,并修改有关数据,如表4.6所示。
表4.6 P0分配资源后的有关资源数据
资源分配进程
Allocation
Need
Available
A B C
A B C
A B C
P0
P1
P2
P3
P4
3 0
3 0 2
3 0 2
2 1 1
0 0 2
7 2 3
0 2 0
6 0 0
0 1 1
4 3 1
2 1 0
我们再利用安全性算法检查此时系统是否安全。从表3.4中可以看出,可用资源Available {2,1,0}已不能满足任何进程的需要,故系统进入不安全状态,此时系统不分配资源。
8.死锁检测程序的运行频率较高或较低,各有什么优缺点?
答:死锁的检测可非常频繁地在每次资源请求时进行,其优点是：可以尽早地检测到死锁及其所涉及的进程,并有可能找到引起系统死锁的那个(或那几个)进程。其缺点是：频繁的检测会耗费相当多的CFU时间,增加系统的开销。相反,每隔较长时间或当CFU利用率下降到较低程度时进行死锁的检测,则可以降低运行死锁检测程序的开销,但在检测到死锁时可能涉及到很多进程,也难以找到引起死锁的那个进程。
9.假设三个进程共享相同类型的四个资源,每个进程一次只能申请或释放一个资源,每个进程至多需要两个资源,证明该系统不会发生死锁。
证：假定该系统死锁,那么就隐含其中的每一进程已占有一资源并正等待另一资源.由于该系统只有三个进程且有四个资源,因此,必有一进程能获得两个资源,不必等待.于是该进程不再申请资源,而且当它执行完后将归还它占有的资源。故该系统不会发生死锁.
10.在一个实际的计算机系统中,资源可以更新和增减,进程可以创建和撤销。如果系统用banker算法处理死锁,那么,在什么情况下,下列改变可以安全地进行而不会引起死锁发生?
(1)增加Avaiiable(增添新资源):
(2)减少Available (资源永久性地从系统中删除):
(3)增大Max(对一进程而言,它可能希望更多的资源):
(4)减少Max(一进程决定不需要那么多资源):
(5)增加进程数:
(6)减少进程数。
解(1)任何时候都不会引起死锁发生:
(2)仅当每一进程的Max请求数不超过可用资源的总数时,系统才保持在安全态:
(3)仅当每一进程的Max请求数不超过可用资源的总数时,系统才保持在安全态:
(4)任何时候都不会引起死锁发生:
(5)任何时候都不会引起死锁发生:
(6)任何时候都不会引起死锁发生.
4.4 自测题
4.4.1 基本题一、判断题(正确的在括号中记√,错误的记×)
1.死锁就是循环等待。 ( )
2.最适合分时系统的进程调度算法是优先数法。 （ ）
3.不存在只涉及一个进程的死锁。 ( )
4,在分时系统中当用户数一定时，影响响应时间的主要因素是调度算法。 ( )
5.若系统中每一资源类只有一个,只要系统存在任何环路,系统状态就是不安全的。 ( )
6.多级反馈调度算法属于抢占调度方式。 （ ）
7.死锁是多个进程为竞争系统资源或彼此间通信而引起的一种临时性的阻塞现象。 ( )
8.在引入线程的系统中进程程调度负责CPU的分配工作。 （ ）
9.当进程数大于资源数时,进程竞争资源一定会产生死锁。 （ ）
10.实时调度的关键是保证满足实时任务对截止时间的要求。 （ ）
1,Χ 2,Χ 3.√ 4,Χ 5.√ 6,√ 7,Χ 8,Χ 9,Χ 10,√
二、选择题
1.在三种基本类型的操作系统中,都设置了进程调度,在批处理系统中还应设置______调度。
A.作业 B.进程 C.中级 D.多处理机
2.下列算法中,_______只能采用非抢占调度方式。
A．高优先权优先法 B.时间片轮转法 C.FCFS调度算法 D.短作业优先算法
3.下面关于优先权大小的论述中,正确的论述是_____________。
A.计算型作业的优先权,应高于I/O型作业的优先权。
B.用户进程的优先权,应高于系统进程的优先权。
C.资源要求多的作业,其优先权应高于资源要求少的作业。
D.在动态优先权时,随着进程执行时间的增加,其优先权降低。
4.最适合分时系统的进程调度算法是______。
A、FCFS B、SSJF C、优先数法 D、轮转法
5.在分时系统中当用户数一定时，影响响应时间的主要因素是_____。
A、时间片 B、调度算法 C、存储分配方式 D、作业的大小
6.采用“按序分配”策略，可以破坏死锁产生的条件是______。
A、互斥 B、请求和保持 C、非剥夺 D、环路等待
7.下述解决死锁的方法中,属于死锁预防策略的是____________。
A.银行家算法 B.资源有序分配法 C.资源分配图化简法 D.撤消进程法
8.从下面关于安全状态和非安全状态的论述中,正确的论述是________。
A.安全状态是没有死锁的状态,非去全状态是有死锁的状态。
B.安全状态是可能有死锁的状态,非安全状态也是可能有死锁的状态。
C.安全状态是可能没有死锁的状态,非安全状态是有死锁的状态。
D.安全状态是没有死锁的状态,非安全状态是可能有死锁的状态。
9.关于产生死锁的现象,下面的描述最准确是__________。
A.每个进程共享某一个资源
B.每个进程竞争某一个资源
C.每个进程等待着某一个不能得到且不可释放的资源
D.某个进程因资源而无法进行下去
10.采用“按序分配”策略，可以破坏死锁产生的条件是______。
A、互斥 B、请求和保持 C、非剥夺 D、环路等待
11.在选取撤消的进程或抢占的进程时,应尽量选择_______。
A.进程优先级最高的
B.进程已运行的时间最短的
C.进程完成其工作还需要的时间最短的
D.进程已A使用的资源数最少的
12.系统使用的资源,如进程控制块(PCB)一般采用下列_________处理死锁。
A.预分法 B.抢占和交换的方法 C.死锁避免方法 D.资源定序方法
13.在为多道程序所提供的可共享的系统资源不足时,可能出现死锁。但是,不适当的___也可能产生死锁。
A.进程优先权 B.资源的线性分配
c.进程推进顺序 D.分配队列优先权答:C
14.采用资源剥夺法可解除死锁,还可以采用_____方法解除死锁。
A.执行并行操作 B.撤消进程
C.拒绝分配新资源 D.修改信号量答,B
15.发生死锁的必要条件有四个,要防止死锁的发生,可以破坏这四个必要条件,但破坏_____条件是不太实际的。
A.互斥 B.不可抢占 C.部分分配 D.循环等待答:A
16.在_________的情况下,系统出现死锁。
A.计算机系统发生了重大故障 B.有多个封锁的进程同时存在
C.若干进程因竞争资源而无休止地相互等待他方释放已占有的资源
D.资源数大大小于进程数或进程同时申请的资源数大大超过资源总数答,C
17.银行家算法是一种__________算法。
A.死锁解除 B.死锁避免 C.死锁预防 D.死锁检测答:B
18.________优先权是在创建进程时确定的,确定之后在整个进程运行期间不再改变。
A.先来先服务 B.静态 C.动态 D.短作业答:B
19.某系统中有3个并发进程,都需要同类资源4个,试问该系统不会发生死锁的最少资源数是_________。
A.9 B.10 C.11 D.12
答:B
20.以下叙述中正确的是___________。
A.调度原语主要是按照一定的算法,从阻塞队列中选择一个进程,将处理机分配给它。
B.号预防死锁的发生可以通过破坏产生死锁的四个必要条件之一来实现,但破坏互斥条件的可能性不大。
C.进程进入临界区时要执行开锁原语。
D.既考虑作业等待时间,又考虑作业执行时间的调度算法是先来先服务算法。
答:B
三、填空题
1.处理死锁的方法通常有_______、________、_______和________
2.为破坏_______条件,采用资源的静态预分策略,系统对进程申请的资源进行一次性的分配,然后才启动该进程运行.
3.Banker算法是典型的_______算法,要求系统必须知道未来的资源请求信息,进程要预先声明资源的最大需求量。
4.进程的调度方式有两种,一种是_______，另一种是_________。
答:①剥夺方式②非剥夺方式
5.死锁是指在系统中的多个______无限期地等待永远不会发生的条件。
答:进程
6.一种最常用的进程调度算法是把处理机分配给具有最高优先权的进程。而确定优先权的方法概括起来不外乎是基于_______特性和________特性两种方法。前者所得到的是_______优先权,后者所得到的是__________优先权。
答:①静态②动态③静态④动态
7.进程调度负责______的分配工作。
答:处理机
8.在______调度算法中,按照进程进入就绪队列的先后次序来分配处理机。
答:先来先服务;..
9.死锁产生的必要条件有四个,_______、______、_______、____________。
答:①互斥条件②不剥夺条件③部分分配④环路条件
10.解除死锁常用的方法有两种。_______是从其他进程那里剥夺足够数量的资源给__________进程,以解除死锁状态。
答:①资源剥夺法②死锁
11.银行家算法中,当一个进程提出的资源请求将导致系统从______进入_________时,系统就拒绝它的资源请求。
答:①安全状态②不安全状态
12.如果要求所有进程一次性申请它所需要的全部资源。若系统有足够的资源分配给进程,便一次把所有的资源分配给该进程。但在分配时只要有一种资源要求不能满足,则资源全不分配,进程等待。这种死锁预防方法破坏了死锁产生必要条件中的_____条件。
答:部分分配
13.对待死锁,一般应考虑死锁的预防、避免、检测和解除四个问题。典型的银行家算法是属于________,破坏环路等待条件是属于__________,而剥夺资源是__________的基本方法。
答:①死锁的避免②死锁的预防③死锁的解除.
四、简答题
1.进程调度的主要功能有哪些?
2.高级调度与中级调度的主要任务是什么?为什么要引入中级调度?
3.在抢占调度方式中,抢占的原则是什么?
4.在选择调度方式和调度算法时,应遵循的准则是什么?
5.在批处理系统、分时系统和实的系统中,各采用哪几种进程(作业)调度算法?
6.何谓静态和动态优先权?确定静态优先权的依据是什么?
7.试比较FCFS和SPF两种进程调度算法。
8.为什么在实时系统中,要求系统(尤其是CPU)具有较强的处理能力?
9.按调度方式可将实时调度算法分为哪几种?
10.试说明多处理器系统有哪儿种类型。
11.试说明对称MPS中的进程分配方式。
12.何谓死锁?产生死锁的原因和必要条件是什么?
13.是否存在只涉及一个进程的死锁问题?-t
14.在解决死锁问题的几个方法中,哪种方法最易于实现?哪种方法使资源利用率高?
15.考虑一个共有150个存储器单元的系统,内存的分配情况如下:
进程 Max Allocation
Pl 70 45
P2 60 40
P3 60 15
使用银行家算法,以确定是否可以同意下面的任一请求:
(1)第4个进程到达,最多需要60个存储单元,最初需要25个单元;
(2)第4个进程到达,最多需要60个存储单元,最初需要35个单元。
16.不安全状态是否必然导致系统进入死锁状态?
答:不安全状态不一定导致系统进入死锁状态。因为,安全性检查中使用的向量Max是进程执行前提供的,而在实际运行过程中,一进程需要的最大资源量可能小于Max,如一进程对应的程序中有一段进行错误处理的代码,其中需要n个A种资源,若该进程在运行过程中没有碰到相应错误而不需调用该段错误处理代码,则它实际上将完全不会请求这n个A种资源。
1.什么是过河问题中的死锁?试说明四个预防算法都可应用于过河问题。
2.考虑图7.3所示的交通死锁情况.
(1)说明图中导致死锁的四个必要条件成立.
(2)提出一个避免死锁的简单规则。
3.考虑表7-3所示的系统瞬时状态,利用banker算法回答下面的问题:
(1)数组Need的内容是什么?
(2)该系统处于安全态吗?若是,给出一安全序列.
(3)若进程P1的请求(0420)到达,该请求是否能立即满足?
表7-3
进程
allocation
Max
Available
P0
0012
0012
1520
P1
1000
1750
P2
1354
2356
P3
0632
0652
P4
0014
0656
4.4.2 解析题一、论述题
【例24】考虑一个每月运行5000个作业而未采用死锁预防或避免措施的系统.死锁大约每月发生两次,而且每班发生死锁时要求操作员终止或重新运行大约10%的作业,每个作业大约耗费20元(按CPU时间计算)且每个被终止的作业在被撤消时往往都运行了一半。
系统程序员估计,在该系统上配置死锁避免算法(如banker算法)会使每个作业平均执行时间增加大约10%.由于机器当前仍有30%的空闲时间,所以,每个月仍可以运行5000个作业(尽管平均周转时间增加了大约20%)。
(1)赞成配置死锁避免算法的理由是什么?
(2)反对配置死锁避免算法的理由是什么?
解：(1)为了有效地判定在特定环境下是否出现死锁,必须配置死锁预防或避免算法.通过配置死锁避免算法,减少平均等待时间.
(2)若不把重点放在使等待时间变为最少这一点上,那么,不配置死锁预防或避免算法会减少成本。
【例25】考虑下面的死锁分配策略:允许在任何时候申请和释放资源:若因没有可用资源而不能满足对资源的申请,则检查那些因等待资源而被阻塞的进程,若它们占有所需的资源,则从中收回这些资源并将这些资源分给申请这些资源的进程.增加等待进程正等待的资源向量,使其包含那些被收回的资源.例如,考虑这样一种系统,它有3类资源,且向量Available的初值为(4,2,2).若进程A申请(2,2,1),则它将得到满足:若进程B申请(1,0,1),则它也得到满足:然后若进程A又申请(0,0,1),则它被阻塞(无可用资源).如果进程C现要申请(2,0,0),则它得到一个可用资源、(1,0,0)和一个曾分配给A的资源(因A已被阻塞).此时,A的Allocation向量变为(1,2,1),而其Need向量则变为(1,0,1)。试说明:
(1)在这种环境中会出现死锁吗?若会,试举一例:若不会,那么哪个必要条件不可能成立?
(2)会出现无限期地阻塞吗?
解(1)由于采用的是抢占性策略,所以不可能出现死锁。
(2)会的.一个进程可能决不会获得它所需要的全部资源,如果资源被一系列类似过程C的申请接连不断地抢占的话.
【例26】当由于发生死锁而撤离一进程时会出现什么困难?
解:进程必须完全地撤离(中止重新开始)或只是退回到前面的安全态.对于第一种情形,这种撤离的开销由其优先数、它已运行了多长时间、在完成前还需多少时间以及所需的资源类型等因素来决定:对于第二种情形,为了确定进程最近的安全态,系统需要保留有关每一进程的许多信息.
【例27】一个系统能否检测它的哪些进程正处于饥饿状态?若能,则说明如何进行这种检测.若不能,则叙述系统是如何处理饥饿问题的.
解:测饥饿现象事实上需要"未来知识",因为,对进程"过去知识"的统计资料还不能判定进程"前进"与否,但通过使进程"老化"可预防饥饿现象。这意味着对每一进程管理需设置一个撤消计数器,而且在选择进程作为"抢占/撤消"对象时把它作为开销因素的一部分来考虑.
【例28】单资源类的banker算法可从一般的banker算法获得,这只需将各数组的维数减为1即可.试举例说明,多资源类的baI虫er算法不能通过把单资源类的banker算法单独地应用到每一资源类来实现.
解:考虑一系统它具有资源类A,B,C和两个进程Po,pl以及表7.2所示的瞬时状态.该系统不是处于安全态。但是,若把单资源类的banker算法单独地应用到每一资源类,那么,就得到
·序列〈P0,p1〉对资源A满足安全性要求:
·序列<P0,P1>对资源B满足安全性要求:
·序列〈Po,P1>对资源C满足安全性要求.
表7-2
allocation
Max
Need
Available
122
23
112
111
112
233
121
这样,该系统就应处于安全态了,显然与实际情况不符.
二．计算题例76试列出两种破坏"循环等待"条件的方法以防止死锁发生.
解假定对系统资源已进行了线性定序,则有以下两种破坏"循环等待"条件:
(1)进程只能申请具有较高序号数的资源:
(2)当进程申请某个资源时,它必须释放所有较低序号数的资源。
【例18】硬件并不总是可靠的.若设备发生故障,那么,它对处理死锁的三种方法(预防、避免和检测)有何影响?
解:对死锁预防无影响:
对死锁避免有影响,该系统可能不再处于安全状态:
对死锁检测有影响,虽不会产生死锁,但必须更新等待图以反映系统状态的变更.
【例19】试列出资源的四种类型,并给出其对应的处理死锁的典型方法.
解:(1)内部资源:资源定序方法.
(2)主存:抢占和交换的方法
(3)作业资源:死锁避免方法
(4)可交换空间:预分法.
【例20】适当的Spooling技术可能消除死锁.它肯定可以消除读卡机、绘图机、行打机等的竞争,甚至对磁带也可以采用Spooling技术。这样剩下的资源是CPU时间、存储区和盘空间。问:是否会出现涉及到这些资源的死锁?若会,那么在什么情况下发生死锁?哪种(些)处理死锁的方法最适合于处理这类死锁?..
解:仍然可能出现死锁.例如,进程pl占有一些由进程P2所请求的内存页面,而P2占有CPU且pl正在申请CPU.消除这类死锁的最好方法是"抢占式"方法.。
【例14】产生死锁的四个必要条件是否都是独立的?能否给出一个必要条件的最小集合?
解：四个必要条件并非是绝对独立的。"占有并等待"条件蕴含"互斥"条件:"循环等待"条件蕴含"互斥"、"占有并等待"以及"非抢占"条件.前三个条件是导致死锁的必要而非充分条件,它们潜藏着第四个条件.这四个条件一起构成了死锁的充要条件.
【例15】什么是饥饿?死锁和饥饿的主要差别是什么?
解：饥饿是系统并没有死锁,但至少有一个进程被无限期地推迟.饥饿不同于死锁.死锁是这样一种情形,其中某进程正等待一个决不会发生的事件.而饥饿现象是指某进程正等待这样一个事件,它发生了但总是受到其他进程的影响,以致一直轮不到(或很难轮到)该进程.
【例16】设计一个不可能出现饥饿和死锁的过河算法.
解：利用红绿灯和一个计数器.当有人开始过河时,计数器增值:过河后该计数器减值.仅当该计数器之值为0时才开绿灯,否则为红灯,岸上的人看到绿灯方能过河.
2.引起进程调度的因素有哪些?
答:引起进程调度的因素有:
(1)进程正常终止或异常终止。
(2)正在执行的进程因某种原因而阻塞:①提出I/O 请求后被阻塞:②在调用P操作时因资源不足而阻塞:③因其他原因执行block原语而阻塞等。
(3)在引入时间片的系统中,时间片用完。
(4)在抢占调度方式中,就绪队列中某进程的优先权变得比当前正在执行的进程高,或者有优先权更高的进程进入就绪队列。
1.为什么说采用有序资源分配法不会产生死锁?
解:为了便于说明,不妨设系统中有m类资源,n个进程,分别用R1,R2,…,Rm(1,2,…,m可看作资源编号)和P1,P2,…pn表示。根据有序资源分配法可知,进程申请资源时必须按照资源编号的升序进行,即任何进程在占有了Ri类资源后,再申请的资源Rj的编号j一定大于i。因此在任一时刻,系统中至少存在一个进程Pk,它占有了较高编号的资源Rh且它继续请求的资源必然是空闲的,因而Pk可以一直向前推进直至完成,当PK运行完成后即会释放它占有的所有资源:在PK完成之后,剩下的进程集合中同样会存在一个进程,它占有了较高编号的资源,且它继续请求的资源必然是空闲的,因而它可以一直向前推进直至完成:以此类推,所有进程均可运行完成,故不会发生死锁。
【例12】解除死锁,在选择撤消进程或被抢占资源的进程时,可考虑哪些因素?.
答:可考虑的因素有：
(1)优先权；
(2)进程己执行的时间；
（3）估计的剩余执行时间；
(4)己产生的输出量；
(5)已获得的资源量和资源类型；
(6)还需要的资源量；
(7)进程的类型(批处理型或交互型)；
(8)需要被撤消的进程数等。
3.在生产者和消费者问题中,如果对调生产者进程中的两个P操作和两个V操作,则可能发生什么情况?
解:如果对调生产者进程中的两个P操作和两个V操作,则生产者和消费者问题的同步描述为：
int full=0; /*满缓冲单元的数目*/
int empty=n； /*空缓冲单元的数目*/
int mutex=1; /*对有界缓冲区进行操作的互斥信号量*/
main( )
{
parbegin
producer ( );
consumer ( );
parend
}
producer ( )
{
while (生产未完成)
{
生产一个产品:
p(mutex);
p(empty);
送一个产品到有界缓冲区;
v〈full〉;
v(mutex〉;
}
}
consumer ( )
{
while (还要继续消费〉
p〈full〉;
p〈mutex〉;
从有界缓冲区中取产品:
v(mutex〉:
v(empty);
消费一个产品:
}
}
由于V操作是释放资源,因此对调V操作的次序无关紧要。而对调P操作的次序则可能导致死锁。这是因为对调P操作后,有可能出现这样一种特殊情况:在某一时刻缓冲区中己装满了产品且缓冲区中无进程工作(这时信号量如full的值为 n，信号量empty的值为0,信号量mutex的值为1,若系统此时调度生产者进程运行,生产者进程又生产了一个产品,它执行P(mutex)并顺利进入临界区(这时mutex值为0),随后它执行p(empty)时因没有空闲缓冲单元而受阻等待,等待消费者进程进入缓冲区取走产品以释放出缓冲单元;消费者进程执行p(full)后再执行p(mutex〉时,因缓冲区被生产者进程占据而无法进入。这样就形成了生产者进程。在占有临界资源的情况下,等待消费者进程取走产品,而消费者进程又无法进入临界区取走产品的僵局,此时两进程陷入死锁。
6.在银行家算法中，若出现下述资源分配情况：
进 程
Allocation
Need
Available
A B C D
A B C D
A B C D
P0
P1
P2
P3
P4
0 3 2
1 0 0 0
1 3 5 4
0 3 3 2
0 0 1 4
0 0 1 2
1 7 5 0
2 3 5 6
0 6 5 2
0 6 5 6
1 6 2 2
试问:（1)该状态是否安全?
(2)如果进程P2提出请求Request（0,2,2,2〉后,系统能否将资源分配给它?
解:(1)利用银行家算法对此时刻的资源分配情况进行分析,可得此时刻的安全性分析情况。
进 程
Work
Need
Allocation
Work+Allocation
Finish
A B C D
A B C D
A B C D
A B C D
P0
P3
P4
P1
P2
1 6 2 2
1 6 5 4
1 9 8 6
1 9 9 10
2 9 9 10
0 0 1 2
0 6 5 2
0 6 5 6
1 7 5 0
2 3 5 6
0 0 3 2
0 3 3 2
0 0 1 4
1 0 0 0
1 3 5 4
1 6 5 4
1 9 8 6
1 9 9 10
2 9 9 10
3 12 14 14
true
true
trye
true
true
从上述分析中可以看出，此时存在一个安全序列{P0,P3,P4,P1,P2},故该状态是安全的。
（2）P2提出请求Request2(1,2,2,2),按银行家算法进行检查：
Request2(1,2,2,2)≤Need2(2,3,5,6)
Request2(1,2,2,2)≤Available(1,6,2,2)
试分配并修改相应数据结构，资源分配情况如下：
进 程
Allocation
Need
Available
A B C D
A B C D
A B C D
P0
P1
P2
P3
P4
0 3 2
1 0 0 0
2 5 7 6
0 3 3 2
0 0 1 4
0 0 1 2
1 7 5 0
1 1 3 4
0 6 5 2
0 6 5 6
0 4 0 0
再利用安全性算法检查系统是否安全,可用资源Available (0,4,0,0)已不能满足任何进程的需要,故系统进入不安全状态,此时系统不能将资源分配给P2。
7．有相同类型的5个资源被4个进程所共享,且每个进程最多需要2个这样的资源就可以运行完毕。试问该系统是否会由于对这种资源的竞争而产生死锁。
解:该系统不会由于对这种资源的竞争而产生死锁。因为在最坏情况下,每个进手里都需要2个这样的资源,且每个进程都己申请到了1个资源,那么系统中还剩下1个可用资源。无论系统为了满足哪个进程的资源申请而将资源分配给该进程,都会因为该进程己获得了它所需要的全部资源而确保它运行完毕,从而可将它占有的2个资源归还给系统,这就保证了其余三个进程能顺利运行。由此可知,该系统不会由于对这种资源的竞争而产生死锁。
8.己知某系统中的所有资源是相同的,系统中的进程严格按照一次一个的方式申请或薛放资源。在此系统中,没有进程所需要的资源数量超过系统的资源总拥有数量,试对下面列出的各种情况说明是否会发生死锁。
情况序号
系统中进程数
资源总量
a
b
c
d
1
2
2
2
2
1
2
3
解:情况a:因系统中仅在1个进程,且系统中资源总数为2,由题目所给条件可知,该进程的最大资源需求量不超过2,显然情况a不会出现死锁。
情况b：因系统中存在2个进程,且系统中资源总数为1,由题目所给条件可知,每个进程的最大资源需求量不超过1。不妨设两个进程的最大资源需求量为1,若系统将资源分配给其中的一个进程,则此进程已获得它所需要的所有资源并将运行完毕,从而可将分配给它的资源归还给系统,使另一个进程也能顺利执行完成,故不会发生死锁。
情况c：因系统中存在2个进程,且系统中资源总数为2,由题目所给条件可知,每个进程的最大资源需求量不超过2。假设两个进程的最大资源需求量为2,若系统将资源分配给其中的一个进程,则此进程已获得它所需要的所有资源并将运行完毕,从而可将分配给它的资源归还给系统,使另一个进程也能顺利执行完成,以这种方式分配资源不会发生死锁:若系统将资源分配给每个进程1个,在此情况下,每个进程均获得1个资源且系统中己没有空闲资源,当其中的一个进程再次申请1个资源时,因系统中无空闲资源而使其等待,另一个进程的情况也是如此,因此以这种方式分配资源会发生死锁。
情况d：因系统中存在2个进程,且系统中资源总数为3,由题目所给杂件可知,每个进程的最大资源需求量不超过3。假设两个进程的最大资源需求量为3,若系统将资源分配给其中的一个进程,则此进程已获得它所需要的所有资源并将运行完毕,从而可将分配给它的资源归还给系统,使另一个进程也能顺利执行完成,以这种方式分配资源不会发生死锁:若系统将资源分配给其中一个进程1个,另一个进程2个,在此情况下,每个进程均获得部分资源且系统中已没有空闲资源,当其中的一个进程再次申请资源时,因系统中无空闲资源而使其等待,另一个进程的情况也是如此,因此以这种方式分配资源会发生死锁。
9.考虑下列资源分配策略:对资源的申请和释放可以在任何时候进行。如果一个进程提出资源请求时得不到满足,若此时无由于等待资源而被阻塞的进程,则自己就被阻塞:若此时已有等待资源而被阻塞的进程,则检查所有由于等待资源而被阻塞的进程。如果它们有申请进程所需要的资源,则将这些资源取出分配给申请进程。
例如,考虑一个有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)。
①这种分配策略会导致死锁吗?如果会,请举一个例子:如果不会,请说明产生死锁的哪一个必要条件不成立?
②这种分配方式会导致某些进程的无限等待吗?为什么?
【分析及相关知识】所谓死锁是指多个进程因竞争资源而造成的一种僵局,若无外力作用,这些进程都将无法向前推进。死锁是计算机系统和进程所处的一种状态。发生死锁的必要条件有以下四个:互斥条件;不剥夺条件;部分分配条件;环路条件。
解:①本题所给的资源分配策略不会产生死锁。因为本题给出的分配策略规定若一进程的资源得不到满足,则检查所有由于等待资源而被阻塞的进程,如果它们有申请进程所需要的资源,则将这些资源取出分配给申请进程。从而破坏了产生死锁必要条件中的不剥夺条件,这样系统就不会产生死锁。
②这种方法会导致某些进程无限期的等待。因为被阻塞进程的资源可以被剥夺,所以被阻塞进程所拥有的资源数量在其被唤醒之前只可能减少。若系统中不断出现其他进程申请资源,这些进程申请的资源与被阻塞进程申请或拥有的资源类型相同且不被阻塞,则系统无法保证被阻塞进程一定能获得所需要的全部资源。例如,本题中的进程A申请(2,2,1〉后再申请(0,0,1〉被阻塞。此后,进程C又剥夺了进程A的一个资源,使得进程A拥有的资源变为〈1,2,1〉,其需求向量为(1,0,1〉。之后,若再创建的进程总是只申请第1和第3类资源,总是占有系统所剩下的第1和第3类资源的全部且不阻塞,那么进程A将会无限期地等待。
10.一个操作系统有20个进程,竞争使用65个同类资源,申请方式是逐个进行的,一旦某进程获得它所需要的全部资源,则立即归还所有资源。每个进程最多使用3个资源。若仅考虑这类资源,该系统有无可能产生死锁,为什么?
解：在本题中,若仅考虑这一类资源的分配,则不会产生死锁。因为死锁产生的原因有两点：系统资源不足或进程推进顺序不当。在本题介绍的系统中,进程所需要的最大资源数为：2OX3=60,而系统中共有该类资源65个,其资源数目己足够系统内的各进程使用,因此绝不可能发生死锁。
11.一台计算机有8台磁带机。它们由N个进程竞争使用,每个进程可能需要3台磁带机。请问N为多少时,系统没有死锁危险,并说明原因。
解：当N为1,2,3时,系统没有产生死锁的危险。因为,当系统中只有1个进程时,它最多需要3台磁带机,而系统有8台磁带机,其资源数目己足够系统内的1个进程使用,因此绝不可能发生死锁:当系统中有2个进程时,最多需要6台磁带机,而系统有8台磁带机,其资源数目也足够系统内的2个进程使用,因此也不可能发生死锁:当系统中有3个进程时,在最坏情况下,每个进程都需要3个这样的资源,且假定每个进程都己申请到了2个资源,那么系统中还剩下2个可用资源,无论系统为了满足哪个进程的资源申请而将资源分配给该进程,都会因为该进程已获得了它所需要的全部资源而确保它运行完毕,从而可将它占有的3个资源归还给系统,这就保证了其余进程能顺利运行完毕。由此可知,当N为1,2,3时,该系统不会由于对这种资源的竞争而产生死锁。
二、计算题
【例12】在银行家算法中,若出现下面的资源分配情况:
Process Allocation Need Available
PO 0 0 3 2 0 0 1 2 1 6 2 2
P1 1 0 0 0 1 7 5 0
P2 1 3 5 4 2 3 5 6
P3 0 0 3 2 0 6 5 2
P4 0 0 1 4 0 6 5 6
试问:
(1)该状态是否安全?
(2)若进程P2提出请求Request(1,2,2,2)后,系统能否将资源分配给它?
(3)如果系统立即满足P2的上述请求,请间,系统是否立即进入死锁状态?
答:(1)利用安全性算法对上面的状态进行分析(如表33所示),找到了一个安全序列{P0,P3,P4,P1,P2},故系统是安全的。
(2)P2发出请求向量Request(1,2,2,2)后,系统按银行家算法进行检查:
①Request2(1,2,2,2)≤Need2(2,,3,5,6);
②Request2(1,2,2,2) ≤Available(1,6,2,2);
③系统先假定可为P2分配资源,并修改Available,Allocation2和Need2向量:
Avmilable=(O,4,0,0)
Allocation2=(2,5,7,6)
Need2=(1,1,3,4)
④进行安全性检查:此时对所有的进程,条件Needi≤Available(O,4,0,0)都不成立,即
Available不能满足任何进程的请求,故系统进入不安全状态。
因此,当进程P2提出请求Request(1,2,2,2)后,系统不能将资源分配给它。
表3.3安全性检查过程资源情况进程
Work
A B C D
Need
A B C D
Allocation
A B C D
Work+Allocation
A B C D
Finish
P0
P3
P4
P1
P2
6 2 2
6 5 4
6 8 6
6 9 10
2 6 9 10
0 0 1 2
0 6 5 2
0 6 5 6
1 7 5 0
2 3 5 6
0 0 3 2
0 0 3 2
0 0 1 4
1 0 0 0
1 3 5 4
1 6 5 4
1 6 8 6
1 6 9 10
2 6 9 10
3 9 14 14
True
True
True
True
True
(3)系统立即满足进程P2的请求(1,2,2,2)后，并没有马上进入死锁状态。因为，此时上述进程并没有申请新的资源,并因得不到资源而进入阻塞状态。只有当上述进程提出新的请求,并导致所有没执行完的多个进程因得不到资源而阻塞时,系统才进入死锁状态。
12.设系统中有3种类型的资源(A,B,C)和5个进程P1、P2、P3、P4、P5,A资源的数量为17,B资源的数量为5,C资源的数量为20。在To时刻系统状态见表4.5所示。系统采用银行家算法实施死锁避免策略。
进 程
最大资源需求量
已分配资源数量
A B C
A B C
P1
P2
P3
P4
P5
5 5 9
5 3 6
4 0 11
4 2 5
4 2 4
2 1 1
4 0 2
4 2 5
2 0 4
3 1 4
①To时刻是否为安全状态?若是,请给出安全序列。
②在To时刻若进程P2请求资源(0,3,4〉,是否能实施资源分配?为什么?
③在②的基础上,若进程P4请求资源。,0,1〉,是否能实施资源分配?为什么?
④在③的基础上,若进程P1请求资源(0,2,0〉,是否能实施资源分配?为什么?
解：由题目所给出的最大资源需求量和己分配资源数量,可以计算出To时刻各进程的资源需求量Need,Need=最大资源需求量一分配资源数量:
进 程
资源需求量
A B C
P1
P2
P3
P4
P5
3 4 7
1 3 4
0 0 6
2 2 1
1 1 0
（1）利用银行家算法对此时刻的资源分配情况进行分析，可得此时刻的安全序性分析情况：
进 程
Work
A B C
Need
A B C
Allocation
A B C
Work+Allocation
A B C
Finish
P0
P3
P4
P1
P2
3 3
5 7 4
7 4 11
11 4 16
15 4 18
1 1 0
2 2 1
0 0 6
1 3 4
3 4 7
3 1 4
2 0 4
4 0 5
4 0 2
2 1 2
5 4 7
7 4 11
11 4 6
15 4 8
17 5 20
True
True
True
True
True
从上述情况分析中可以看出,此时存在一个安全序列{p5,P4,p3,P2,Pl},故该状态是安全的。
②在To时刻若进程P2请求资源(0,3,4),因请求资源数(0,3,4〉>剩余资源数(2,2,3),所以不能分配。
③在②的基础上,若进程P4请求资源(2,0,1),按银行家算法进行检查:
P4请求资源(2,0,1)<=P4资源需求量(2,2,1)
P4请求资源(2,0,1)<=剩余资源数(2,3,3〉
试分配并修改相应数据结构,资源分配情况如下:
进 程
Allocation
A B C
Need
A B C
Available
A B C
P0
P3
P4
P1
P2
1 2
4 0 2
4 0 5
4 0 5
3 1 4
3 4 7
1 3 4
0 0 6
0 2 0
1 1 0
0 3 2
再利用安全性算法检查系统是否安全，可得此时刻的安全性分析情况：
进 程
Work
A B C
Need
A B C
Allocation
A B C
Work+Allocation
A B C
Finish
P4
P5
P3
P2
P1
0 3 2
4 3 7
7 4 11
11 4 16
15 4 18
0 2 0
1 1 0
0 0 6
1 3 4
3 4 7
4 0 5
3 1 4
4 0 5
4 0 2
2 1 2
5 3 7
7 4 11
11 4 6
15 4 8
17 5 20
True
True
True
True
True
从上述情况分析中可以看出,此时存在一个安全序列{P4,P5,P3,P2,P1},故该状态是安全的,可以立即将P4所申请的资源分配给它。
④在③的基础上,若进程Pl请求资源(0,2,0〉,按银行家算法进行检查:
P1请求资源(0,2,0)<=P1资源需求量(3,4,7)
P1请求资源(0,2,0〉<=剩余资源数(0,3,2)
试分配并修改相应数据结构,资源分配情况如下:
进 程
Allocation
A B C
Need
A B C
Available
A B C
P0
P3
P4
P1
P2
3 2
4 0 2
4 0 5
4 0 5
3 1 4
3 2 7
1 3 4
0 0 6
0 2 0
1 1 0
0 1 2
再利用安全性算法检查系统是否安全,可用资源Available (0,1,2)已不能满足任何进程的资源需求,故系统进入不安全状态,此时系统不能将资源分配给P1。
16.假设有一台计算机,它有lM内存,操作系统占用200K,每个用户进程也占用200K。用户进程等待I/O的时间为80%,若增加lM内存,则CPU的利用率将提高多少?
【分析及相关知识】多道程序设计技术是指同时把多个作业放入内存并允许它交替执行,共享系统中的各类资源,当一道程序因某种原因(如I/0请求)而暂停执行时,CPU立即转去执行另一道程序。从上述定义可以看出多道程序系统具有多道、宏观上并行、微观上串行的特点。
多道程序设计技术使CPU的利用率大为提高。设在内存中有N个进程,每个进程等待I/0的百分比是P,那么N个进程同时等待I/0的概率是p^n(此时CPU空闲),即CPU的利用率为1-p^n,由此可见CPU的利用率是N的函数,称为多道程序度。
解:由题目所给条件可知,当前1M内存可支持4个用户进程,由于每个用户进程等待I/O的时间为80%,故CPU的利用率为,
1一(80%)^4=1一(0.8)^4=59%
若增加1M内存,则系统中可同时运行9个进程,则CPU的利用率为：
1一(0.8)^9=87%
故增加1M内存使CPU的利用率提高了：
87%÷59%=147%
147%-100%=47%
所以增加1M内存使CPU的利用率提高了47%。
17.设某计算机系统有一台输入机、一台打印机。现有两道程序同时投入运行,且程序A先开始运行,程序B后运行。程序A的运行轨迹为:计算50ms,打印信息100ms,再计算5Oms,打印信息100ms,结束。程序B的运行轨迹为:计算5Oms,输入数据8Oms,再计算100ms,结束.试说明:
(l)两道程序运行时,CPU有无空闲等待?若有,在哪段时间内等待?为什么会空闲等待?
(2)程序A、B运行时有无等待现象?若有,在什么时候会发生等待现象?
解:两道程序并发执行时的工作情况如图3.5所示。
中央处理机A计算B计算Atf算.B计算
从图3.5可以看出,两道程序运行期间,CPU存在空闲等待。空闲等待的时间段为程序A开始运行后100ms至150ms之间。在此期间,程序A正在打印信息,而程序B正在输入数据。
程序A启动运行后无等待现象,而在程序B启动运行后存在等待现象。程序B的等待时间段为A开始运行后180ms至200ms之间(或程序B启动运行后130ms至150ms之间〉。
18.设有两个处理机P1和P2,它们各有一个硬件高速缓冲存储器C1、C2,且各有一个主存储器MLM2,其性能如下所示:
C1 C2 M1 M2
存储容量 4KB 4KB 2MB 2MB
存储周期 60ns 80ns 1μs 0.9μs
假定两个处理机的指令系统相同,它们的指令执行时间与存储器的平均存取周期成正比。如果执行某个程序时,所需的指令或数据在缓冲存储器中存取到的概率P是0.7,试问这两个处理机的处理速度哪个快?当P=0.9时,处理机的处理速度哪个快?
解:由题目分析可知,处理机的平均存取时间T为:
T=T1+(1-P)T2
其中,T1为高速缓冲存储器的存取周期,T2为主存储器的存取周期,P为指令或数据在缓冲存储器中存取到的概率。〈1μs=1000nS〉
(1)当P=0.7时,P1的平均存取时间为:
60+(1-0.7)×10^3=360ns
P2的平均存取时间为:
80+(1-0.7)×0.9×10^3=350ns..
根据题意,指令执行时间与存储器的平均存取周期成正比,因此当P=0.7时,P2比P1的处理速度快。
〈2〉当P=0.9时,P1的平均存取时间为:
60+〈1-0.9〉* 10^3=160ns
P2的平均存取时间为:
80+(1-0.9)×0.9×10^3=170ns
因此当P=0.9时,Pl比P2的处理速度快。
19.有两个程序,A程序按顺序使用CPU 10秒,使用设备甲5秒,使用CPU 5秒,使用设备乙10秒,最后使用CPU lO秒。B程序按顺序使用设备甲10秒,使用CPU lO秒,使用设备乙5秒,使用CPU 5秒,使用设备乙10秒。在顺序环境下先执行A程序再执行B程序,CPU的利用率是多少?
解:由题目所给条件可知,两个程序顺序执行,先执行程序A,再执行程序B。
A程序的执行时间为:
10+5+5+10+10=40秒其中使用CPU时间为：
10+5+10=25秒
B程序的执行时间为：
10+10+5+5+10=40秒其中使用CPU时间为：
10+5=15秒两个程序的总执行时间为:
40+40=80秒其中使用CPU时间为:
15+25=40秒故CPU利用率为:
40/80=50%
20.假设就绪队列中有10个进程,系统将时间片设为200ms,CPU进行进程切换要花费10ms,试问系统开销所占的比率约为多少?
解:因就绪队列中有10个进程,它们以时间片轮转的方式使用CPU,时间片长度为200ms。当一个时间片用完时,调度进程将当前运行进程设置为就绪状态并放入就绪队列尾,再从就绪队列队首选择进程投入运行,这一过程(进程切换〉要花费时间10ms。因此系统开销所占比率为:
10/(200+10)=4.8%
4.4.3 自测题答案一、填空题
1.资源可分为可重用资源和消耗型资源两大类型,前者包括处理机、I/O通道、存储器、设备和文件等,后者包括如中断、消息和I/0缓冲区中的信息等.
2.通常情况下,进程对资源的利用是按照请求(申请)资源、使用资源、释放资源的顺序进行的,如打开、使用和关闭文件,分配、占用和回收内存空间等.
3.死锁的四个必要条件是互斥、占用并等待、非抢占和循环等待。
4.处理死锁的方法通常有死锁预防、死锁避免、死锁检测和死锁恢复。
5.为破坏占用并等待条件,采用资源的静态预分策略,系统对进程申请的资源进行一次性的分配,然后才启动该进程运行.
6.Banker算法是典型的死锁避免算法,要求系统必须知道未来的资源请求信息,进程要预先声明资源的最大需求量.
二、判断题j
1.× 2.√ 3,√ 4.×5 √,6.× 7.×
三、选择题
1.b)、d)、e)、f)
2.c)
3.a)、b)、c)、d)
4.a)、c)
5.b)、d)、e)、f)
6.d)
7.a)、b)、d)、e)
四、问答题
1.从河两岸分别过河的两人在河中相遇并踩上同一垫脚石.
①互斥:允许人们共享同一垫脚石.
②占有并等待:在能过河前,人们必须申请使用所有的垫脚石.
③抢占2允许一个人在别人过河时走到一旁的歇脚石上(撤离到安全态),或强行要求过河的另一方撤回(完全撤离).
④循环等待:这实质上意味着只允许用单行道方式过河.为了让两个方向的人都能过洞,得铺设另一串垫脚石供另一方向专用.
2.(1)此例中导致死锁的四个条件成立:
①互斥.每条道路只能被一辆车占用.
②占用并等待。每辆车都占用了一段道路,并等待其前方的道路被释放.
③非抢占.资源不可抢占.单行线,汽车不能抢路超车.
④循环等待.每辆车都等待着前方的汽车把路让出来,且形成了一个环路.
(2)在每个十字路口设置红绿灯,当南北方向的路通车时,东西方向的路上汽车等待.反之亦然.
3.(1)由于Need =Max-Allocation,所以Need的内容是:
0000
0750
1002
0020
0642
(2)是处于安全态,序列〈P。,PI,P2,P3,P4>满足安全性要求.
(3)能立即得到满足,因为
①(0420)<=Available =(1520)
②(0420)<=Maxi =(1750)
③分配后的新系统状态如表7.4所示,且序列〈Po,P1,p2,P3,P4〉满足安全性要求.
表7.4
allocation
Max
Need
Available
0012
0012
0000
1100
1420
1750
0330
1354
2356
1002
0632
0652
0020
0014
0656
0642
