第三章 处置机调度与死锁
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算法、最小优先数优先算法、抢占式最小优先
数优先算法 2 分时系统：可剥夺调度、轮转调度 实时系统：时间片
轮转调度算法、非抢占优先权调度算法、基于时钟中断抢 占的优先权调度算法、当即抢占的优先权调度。
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、什么是最低松弛度优先调度算法？举例说明之。
【解】 该算法是按照任务紧急(或松弛)的程度，来肯定任务的优先级。任务的紧急程度愈高，为该任务所给予的优先级就愈高，以使之优先执行。例如，一个任务在200 ms 时必需完成，而它本身所需的运行时间就有100 ms，因此，调度程序必需在100 ms 之前调度执行，该任务的紧急程度(松弛程度)为100 ms。又如，另一任务在400 ms 时必需完成，它本身需要运行 150 ms，则其松弛程度为 250 ms。
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分派资源，并修改有关数据，如下所示： allocation need available A B C A B C A B C P0 0 2 0 7 3 3 2 2 0
P1 3 0 2 0 2 0 P2 3 0 2 6 0 0 P3 2 1 1 0 1 1 P4 0 0 2 4 3 1
存在一个安全序列{P1,P3,P0,P2,P4}，故系统是安全的，可以分派资源。 31、在银行家算法中，若出现下述资源分派情况： Process Allocation Need Available P0 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 3 3 2 0 6 5 2 P4 0 0 1 4 0 6 5 6
试问： （1）该状态是不是安全？ （2）若进程P2提出请求Request（1，
2，2，2）后，系统可否将资源分派给它？
【解】（1）利用安全性算法对上面的状态进行分析（见下表），找到了一个安全序列{P0,P3,P4,P1,P2}，故系统是安全的。
Work Need Allocation Work+Allocation Finish P0 1 6 2 2 0 0 1 2 0 0 3 2 1 6 5 4 true P3 1 6 5 4 0 6 5 2 0 3 3 2 1 9 8 6 true P4 1 9 8 6 0 6 5 6 0 0 1 4 1 9 9 10 true P1 1 9 9 10 1 7 5 0 1 0 0 0 2 9 9 10 true P2 2 9 9 10 2 3 5 6 1 3 5 4 3 12 14 14 true （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向量： Available=(0,4,0,0)
Allocation2=(2,5,7,6) Need2=(1,1,3,4)
④进行安全性检查：此时对于所有的进程，条件Needi≤Available(0,4,0,0)都不成立，即Available不能知足任何进程的请求，故系统进入不安全状态。
因此，当进程P2提出Request(1,2,2,2)后，系统不能将资源分派给它。
