搜索
第三章处理机调度与死锁1，高级调度与低级调度的主要任务是什么？为什么要引入中级调度？【解】（1）高级调度主要任务是用于决定把外存上处于后备队列中的那些作业调入内存，并为它们创建进程，分配必要的资源，然后再将新创建的进程排在就绪队列上，准备执行。（2）低级调度主要任务是决定就绪队列中的哪个进程将获得处理机，然后由分派程序执行把处理机分配给该进程的操作。（3）引入中级调度的主要目的是为了提高内存的利用率和系统吞吐量。为此，应使那些暂时不能运行的进程不再占用宝贵的内存空间，而将它们调至外存上去等待，称此时的进程状态为就绪驻外存状态或挂起状态。当这些进程重又具备运行条件，且内存又稍有空闲时，由中级调度决定，将外存上的那些重又具备运行条件的就绪进程重新调入内存，并修改其状态为就绪状态，挂在就绪队列上，等待进程调度。3、何谓作业、作业步和作业流？【解】作业包含通常的程序和数据，还配有作业说明书。系统根据该说明书对程序的运行进行控制。批处理系统中是以作业为基本单位从外存调入内存。作业步是指每个作业运行期间都必须经过若干个相对独立相互关联的顺序加工的步骤。作业流是指若干个作业进入系统后依次存放在外存上形成的输入作业流；在操作系统的控制下，逐个作业进程处理，于是形成了处理作业流。4、在什么情冴下需要使用作业控制块JCB？其中包含了哪些内容？【解】每当作业进入系统时，系统便为每个作业建立一个作业控制块JCB，根据作业类型将它插入到相应的后备队列中。JCB包含的内容通常有：1)作业标识2)用户名称3)用户账户4)作业类型（CPU繁忙型、I/O芳名型、批量型、终端型）5)作业状态6)调度信息（优先级、作业已运行）7)资源要求8)进入系统时间9)开始处理时间10)作业完成时间11)作业退出时间12)资源使用情况等5．在作业调度中应如何确定接纳多少个作业和接纳哪些作业？【解】作业调度每次接纳进入内存的作业数，取决于多道程序度。应将哪些作业从外存调入内存，取决于采用的调度算法。最简单的是先来服务调度算法，较常用的是短作业优先调度算法和基于作业优先级的调度算法。7．试说明低级调度的主要功能。【解】（1）保存处理机的现场信息（2）按某种算法选取进程（3）把处理机分配给进程。8、在抢占调度方式中，抢占的原则是什么？【解】剥夺原则有：（1）时间片原则各进程按时间片运行，当一个时间片用完后，便停止该进程的执行而重新进行调度。这种原则适用于分时系统、大多数实时系统，以及要求较高的批处理系统。（2）优先权原则通常是对一些重要的和紧急的作业赋予较高的优先权。当这种作业到达时，如果其优先权比正在执行进程的优先权高，便停止正在执行的进程，将处理机分配给优先权高的进程，使之执行。（3）短作业（进程）优先原则当新到达的作业（进程）比正在执行的作业（进程）明显地短时，将剥夺长作业（进程）的执行，将处理机分配给短作业（进程），使之优先执行。9、选择调度方式和调度算法时，应遵循的准则是什么？【解】应遵循的准则有（1）面向用户的准则：周转时间短，响应时间快，截止时间的保证，优先权准则。（2）面向系统的准则：系统吞吐量高，处理机利用率好，各类资源的平衡利用。10、在批处理系统、分时系统和实时系统中，各采用哪几种进程（作业）调度算法？【解】批处理系统：FCFS算法、最小优先数优先算法、抢占式最小优先数优先算法分时系统：可剥夺调度、轮转调度实时系统：时间片轮转调度算法、非抢占优先权调度算法、基于时钟中断抢占的优先权调度算法、立即抢占的优先权调度。11、何谓静态和动态优先权？确定静态优先权的依据是什么？【解】静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。动态优先权是指，在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。确定静态优先权的依据是：（1）进程类型，通常系统进程的优先权高于一般用户进程的优先权。（2）进程对资源的需要。（3）用户要求，用户进程的紧迫程度及用户所付费用的多少来确定优先权的。12、试比较FCFS和SPF两种进程调度算法。【解】FCFS算法按照作业提交或进程变为就绪状态的先后次序，分派CPU。当前作业或进程占有CPU，直到执行完或阻塞，才让出CPU。在作业或进程唤醒后，并不立即恢复执行，通常等到当前作业或进程让出CPU。FCFS比较有利于长作业，而不利于短作业；有利于CPU繁忙的作业，而不利于I/O繁忙的作业。SPF有利于短进程调度，是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。比FCFS改善了平均周转时间和平均带权周转时间，缩短了作业的等待时间，提高了系统的吞吐量。但SPF有其不容忽视的缺点：该算法对长作业不利；完全未考虑作业的紧迫程度，因而不能保证紧迫性作业（进程）会被及时处理；用户可能会有意无意地干扰作业的运行时间，致使该算法不一定能真正做到短作业优先调度。13、在时间片轮转法中，应如何确定时间片的大小？【解】时间片应略大于一次典型的交互需要的时间。一般应考虑三个因素：系统对相应时间的要求、就绪队列中进程的数目和系统的处理能力。14、通过一个例子来说明通常的优先级调度算法不能适用于实时系统？【解】实时系统的调度算法很多，主要是基于任务的开始截止时间和任务紧急/松弛程度的任务优先级调度算法，通常的优先级调度算法不能满足实时系统的调度实时性要求而不适用。15、为什么说多级反馈队列调度算法能较好地满足各方面用户的需要？【解】（1）对于终端型用户来说，他们提交的大多属于较小的交互型作业，系统只要能使这些作业（进程）在第一队列所规定的时间片内完成，便可使终端型作业用户都感到满意。（2）对短批处理作业用户来说，在第一队列中执行一个时间片或至多只需在第二队列和第三队列中各执行一个时间片即可完成。（3）对长批处理作业用户来说，只要将作业依次在第1，2，„„，n个队列中运行，然后再按轮转方式运行，用户不必担心其作业长期得不到处理。16、19、为什么在实时系统中，要求系统（尤其是CPU）具有较强的处理能力？【解】在实时系统中都存在着若干个实时进程或任务，它们用来反应或控制某个（些）外部事件，往往带有某种程度的紧迫性，因而对实时系统中的调度提出了某些特殊要求。若处理机的处理能力不够强，则有可能因处理机忙不过来而使某些实时任务不能得到及时处理，从而导致发生难以预料的后果。20、按调度方式可将实时调度算法分为哪几种？【解】按调度方式可将实时调度算法分为两大类四小类：（1）非抢占式调度算法：①非抢占式轮转调度算法；②非抢占式优先调度算法；（2）抢占式调度算法：①基于时钟中断的抢占式优先权调度算法；②立即抢占的优先权调度算法。21、什么是最早截止时间优先调度算法？举例说明之。【解】在系统中保持一个实时任务就绪队列，该队列按各任务截止时间的早晚排序，截止时间愈早的优先级愈高，在队列中排列愈靠前，调度程序在选择任务时，总是选择就绪队列中的第一个任务，为之分配处理机，使之投入运行。例：四个非周期任务，它们先后到达。系统首先调度任务1执行，在任务1执行期间，任务2、3又先后到达。由于任务3的开始截止时间早于任务2，系统在任务1后将调度任务3执行。在此期间又到达作业4，其开始截止时间仍是早于任务2的，在任务3执行完后，系统又调度任务4的执行，最后才调度任务2执行。22、什么是最低松弛度优先调度算法？举例说明之。【解】该算法是根据任务紧急(或松弛)的程度，来确定任务的优先级。任务的紧急程度愈高，为该任务所赋予的优先级就愈高，以使之优先执行。例如，一个任务在200ms时必须完成，而它本身所需的运行时间就有100ms，因此，调度程序必须在100ms之前调度执行，该任务的紧急程度(松弛程度)为100ms。又如，另一任务在400ms时必须完成，它本身需要运行150ms，则其松弛程度为250ms。27、何谓死锁？产生死锁的原因和必要条件是什么？【解】所谓死锁，是指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进。产生死锁的原因：（1）竞争资源，当系统中供多个进程所共享的资源，不足以同时满足它们的需要时，引起它们对资源的竞争而产生死锁；（2）进程推进顺序非法，进程在运行过程中，请求和释放资源的顺序不当，导致进程死锁。产生死锁的必要条件：（1）互斥条件进程对所分配到的资源进行排他性使用。如果此时还有其他进程请求该资源，请求者只能阻塞，直到占有该资源的进程释放该资源。（2）请求和保持条件进程已经保持了至少一个资源，但又提出了新的资源要求，而该资源又已被其他进程占有，此时请求进程阻塞，但请求进程又对已经获得的其他资源保持不放。（3）不剥夺条件进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完后由自己释放。（4）环路等待条件在发生死锁时，必然存在一个进程——资源的环形链。29、请详细说明可通过哪些途径预防死锁？【解】可以通过：（1）摒弃“请求和保持”条件，系统要求所有进程要一次性地申请在整个运行过程所需的全部资源。如系统有足够的资源分配给进程，便一次性的把其所需要的所有资源分配给该进程。这样，该进程在整个运行期间，便不会再提出资源要求，从而摒弃了请求条件。但在分配时，只要有一种资源要求得不到满足，则即使是已有的其他资源，也全部不分配给该进程，而让该进程等待。这样，由于等待期间的进程未占有任何资源，因而也摒弃了保持条件，从而可以避免发生死锁。（2）摒弃“不剥夺”条件，进程是在需要资源时才提出请求，这样，一个已经保持了某些资源的进程，当它在提出新的资源要求而不能立即得到满足时，必须释放它已经保持的所有资源，待以后需要时再重新申请。这意味着进程已经占有的资源，在运行过程中可能会暂时释放，也可认为是被剥夺了，从而摒弃了“不剥夺条件”。（3）摒弃“环路等待”条件，系统将所有资源按类型进行线性排队，并赋予不同的序号。所有进程对资源的请求必须严格按资源序号递增的次序提出，这样，在所形成的资源分配图中，不可能再出现环路，从而摒弃了“环路等待”条件。30、在银行家算法的例子中，如果P0发出的请求向量由Request(0,2,0)）改为Request(0,1,0)，问系统可否将资源分配给它？【解】能。request0(0,1,0)≤need0(7,4,3);request0(0,1,0)≤available(2,3,0);系统暂时先假定可为P0分配资源，并修改有关数据，如下所示：allocationneedavailableABCABCABCP0020733220P1302020P2302600P3211011P4002431存在一个安全序列{P1,P3,P0,P2,P4}，故系统是安全的，可以分配资源。31、在银行家算法中，若出现下述资源分配情况：ProcessAllocationNeedAvailableP0003200121622P110001750P213542356P303320652P400140656试问：（1）该状态是否安全？（2）若进程P2提出请求Request（1，2，2，2）后，系统能否将资源分配给它？【解】（1）利用安全性算法对上面的状态进行分析（见下表），找到了一个安全序列{P0,P3,P4,P1,P2}，故系统是安全的。WorkNeedAllocationWork+AllocationFinishP01622001200321654trueP31654065203321986trueP419860656001419910trueP1199101750100029910trueP229910235613543121414true（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，Allo