3.2 课后习题详解
1高级调度与低级调度的主要任务是什么？为什么要引入中级调度？
答：（1）高级调度和低级调度的主要任务
①高级调度又称为作业调度或长程调度，其主要功能是根据某种算法，把外存上处于后备队列中的那些作业调入内存，也就是说，它的调度对象是作业。
②低级调度用于决定就绪队列中的哪个进程应获得处理机，然后再由分派程序执行把处理机分配给该进程的具体操作。通常也把低级调度称为进程调度或短程调度，它所调度的对象是进程（或内核级线程）。
（2）引入中级调度的目的
引入中级调度的主要目的是为了提高内存利用率和系统吞吐量，中级调度实际上就是存储器管理中的对换功能。
2处理机调度算法的共同目标是什么？批处理系统的调度目标又是什么？
答：（1）处理机调度算法的共同目标
①资源利用率
为提高系统的资源利用率，应使系统中的处理机和其他所有资源都尽可能地保持忙碌状态。
②公平性
公平性是指应使诸进程都获得合理的CPU时间，不会发生进程饥饿现象。
③平衡性
为使系统中的CPU和各种外部设备都能经常处于忙碌状态，调度算法应尽可能保持系统资源使用的平衡性。
④策略强制执行
对所制订的策略其中包括安全策略，只要需要，就必须予以准确地执行，即使会造成某些工作的延迟也要执行。
（2）批处理系统的调度目标
①使程序的平均周转时间短；
②提高系统吞吐量；
③提高处理机利用率。
3何谓作业、作业步和作业流？
答：（1）作业
作业是用户提交给系统的一项相对独立的工作，它不仅包含了通常的程序和数据，而且还应配有一份作业说明书，系统根据该说明书来对程序的运行进行控制。在批处理系统中，是以作业为基本单位从外存调入内存的。
（2）作业步
通常，在作业运行期间，每个作业都必须经过若干个相对独立又相互关联的顺序加工步骤才能得到结果，我们把其中的每一个加工步骤称为一个作业步。
（3）作业流
若干个作业进入系统后，被依次存放在外存上，这便形成了输入的作业流；在操作系统的控制下，逐个对作业进行处理，于是便形成了处理作业流。
4在什么情况下需要使用作业控制块JCB，其中包含了哪些内容？
答：（1）使用JCB的情况
每当作业进入系统时，系统便为每个作业建立一个JCB，根据作业类型将它插入相应的后备队列中。作业调度程序依据一定的调度算法来调度它们，被调度到的作业将会被装入内存。在作业运行期间，系统就按照JCB中的信息对作业进行控制。当一个作业执行结束进入完成状态时，系统负责回收分配给它的资源，撤销它的作业控制块。
（2）JCB包含的内容
在JCB中所包含的内容因系统而异，通常应包含的内容有：作业标识、用户名称、用户帐户、作业类型（CPU繁忙型、I/O繁忙型、批量型、终端型）、作业状态、调度信息（优先级、作业已运行时间）、资源需求（预计运行时间、要求内存大小、要求I/O设备的类型和数量等）、进入系统时间、开始处理时间、作业完成时间、作业退出时间、资源使用情况等。
5在作业调度中应如何确定接纳多少个作业和接纳哪些作业？
答：（1）作业调度每次要接纳多少个作业进入内存，取决于多道程序度，即允许多少个作业同时在内存中运行。当内存中同时运行的作业数目太多时，可能会影响到系统的服务质量。但如果在内存中同时运行作业的数量太少时，又会导致系统的资源利用率和系统吞吐量太低，因此，多道程序度的确定应根据系统的规模和运行速度等情况做适当的折衷。
（2）应将哪些作业从外存调入内存，这将取决于所采用的调度算法。最简单的是先来先服务调度算法，这是指将最早进入外存的作业最先调入内存：较常用的一种算法是短作业优先调度算法，是将外存上最短的作业最先调入内存；另一种较常用的是基于作业优先级的调度算法，该算法是将外存上优先级最高的作业优先调入内存；比较好的一种算法是“响应比高者优先”的调度算法。
6为什么要引入高响应比优先调度算法？它有何优点？
答：（1）引入高响应比优先调度算法的原因
①在批处理系统中，FCFS算法所考虑的只是作业的等待时间，而忽视了作业的运行时间。
②SJF算法只考虑作业的运行时间，而忽视了作业的等待时间。
③高响应比优先调度算法则是既考虑了作业的等待时间，又考虑作业运行时间的调度算法，因此既照顾了短作业，又不致使长作业的等待时间过长，从而改善了处理机调度的性能。
（2）高响应度优先调度算法的优点
①如果作业（进程）的等待时间相同，则要求服务时间最短的作业（进程）的优先权最高，因此它有利于短作业（进程），从而可降低作业（进程）的平均周转时间，提高系统吞吐量。
②如果作业（进程）的要求服务时间相同，则其优先权将取决于作业到达（或进程进入就绪状态）的先后次序，因此体现了公平的原则。
③如果作业（进程）较长，它的优先权将随着等待时间的增长而提高，从而使长作业（进程）不会长期得不到服务。
7试说明低级调度的主要功能。
答：低级调度又称为进程调度或短程调度，其所调度的对象是进程（或内核级线程），它的主要功能如下：
（1）保存处理机的现场信息
在进行进程调度时，首先需要保存当前进程的处理机的现场信息，将它们送入该进程的进程控制块（PCB）中的相应单元。
（2）按某种算法选取进程
低级调度程序按某种算法如优先数算法、轮转法等，从就绪队列中选取一个进程，把它的状态改为运行状态，并准备把处理机分配给它。
（3）把处理器分配给进程
由分派程序（Dispatcher）把处理器分配给进程。此时需为选中的进程恢复处理机现场，即把选中进程的进程控制块内有关处理机现场的信息装入处理器相应的各个寄存器中，把处理器的控制权交给该进程，让它从取出的断点处开始继续运行。
8在抢占调度方式中，抢占的原则是什么？
答：抢占调度方式允许调度程序根据某种原则，去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。抢占的原则有：优先权原则，短作业（进程）优先原则，时间片原则。
9在选择调度方式和调度算法时，应遵循的准则是什么？
答：调度的准则包括：CPU利用率、系统吞吐量、进程周转时间、进程等待时间以及响应时间的长短。
10在批处理系统、分时系统和实时系统中，各采用哪几种进程（作业）调度算法？
答：（1）适合批处理系统的调度算法有短作业优先、优先权、高响应比优先和多级反馈队列调度算法；
（2）分时系统的调度算法有时间片轮转法和多级反馈队列调度算法；
（3）实时系统的调度算法有优先级调度算法、最早截止时间优先即EDF算法和最低松弛度优先即LLF算法。
11何谓静态和动态优先级？确定静态优先级的依据是什么？
答：（1）静态优先级是在创建进程时确定的，且在进程的整个运行期间保持不变。一般地，优先权是利用某一范围内的一个整数来表示的。
（2）动态优先级是指在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。
（3）确定静态优先级的依据
①进程类型，通常，系统进程（如接收进程、对换进程、磁盘I/O进程）的优先权高于一般用户进程的优先权；
②进程对资源的需求；
③用户要求。
12试比较FCFS和SJF两种进程调度算法。
答：（1）先来先服务（FCFS）调度算法
①调度过程
当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。
②适用范围
FCFS算法比较有利于长作业（进程），而不利于短作业（进程）。
（2）短作业优先（SJF）调度算法
①调度过程
短作业优先（SJF）的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先（SPF）调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。
②适用范围
有利于短作业（进程）、不利于长作业（进程）。
13在时间片轮转法中，应如何确定时间片的大小？
答：选择时间片大小时，一般应考虑以下三个因素：
（1）系统对响应时间的要求；
（2）就绪队列中进程的数目；
（3）系统的处理能力。
14通过一个例子来说明通常的优先级调度算法为什么不能适用于实时系统？
答：有两个周期性任务，任务A的周期时间为20ms，每个周期的处理时间为10ms，任务B的周期时间为50ms，每个周期的处理时间为25ms。如表3-1中所示第一行显示出了两个任务的到达时间、最后期限和执行时间图。其中任务A的到达时间为0、20、40、…；任务A的最后期限为20、40、60、…；任务B的到达时间为0、50、100、…（注：单位皆为ms）。
为了说明通常的优先级调度不适用于实时系统，如表3-2所示增加了第二行。在第二行中假定任务A具有较高的优先级，所以在t=0ms时，先调度A1执行，在A1完成后（t=10ms）才调度B1执行；在t=20ms时，调度A2执行；在t=30ms时，A2完成，又调度B1执行；在t=40ms时，调度A3执行；在t=50ms时，虽然A3已完成，但B1已错过了它的最后期限，这说明利用通常的优先级调度已经失败。
表3-1 到达时间，执行时间和最后期限
表3-2 A具有较高优先级
实时系统的调度算法很多，主要是基于任务的开始截止时间和任务紧急/松弛程度的任务优先级调度算法，通常的优先级调度算法不能满足实时系统的调度实时性要求因此不适用于实时系统。
15为什么说多级反馈队列调度算法能较好地满足各方面用户的需要？
答：（1）终端型作业用户
由于终端型作业用户所提交的作业大多属于交互型作业，作业通常较小，系统只要能使这些作业（进程）在第一队列所规定的时间片内完成，便可使终端型作业用户都感到满意。
（2）短批处理作业用户
对于很短的批处理型作业，开始时像终端型作业一样，如果仅在第一队列中执行一个时间片即可完成，便可获得与终端型作业一样的响应时间。对于稍长的作业，通常也只需在第二队列和第三队列各执行一个时间片即可完成，其周转时间仍然较短。
（3）长批处理作业用户
对于长作业，它将依次在第1，2，…，n个队列中运行，然后再按轮转方式运行，用户不必担心其作业长期得不到处理。
16为什么说传统的几种调度算法都不能算是公平调度算法？
答：传统的几种调度算法所保证的只是优先运行，如优先级算法是优先级最高的作业优先运行，但并不保证作业占用了多少处理机时间。另外也未考虑到调度的公平性。
17保证调度算法是如何做到调度的公平性的？
答：保证调度算法是另外一种类型的调度算法，它向用户所做出的保证并不是优先运行，而是明确的性能保证，该算法可以做到调度的公平性。一种比较容易实现的性能保证是处理机分配的公平性。如果在系统中有n个相同类型的进程同时运行，为公平起见，须保证每个进程都获得相同的处理机时间1/n。
18公平分享调度算法又是如何做到调度的公平性的？
答：在公平分享调度算法中，调度的公平性主要是针对用户而言，使所有用户能获得相同的处理机时间，或所要求的时间比例。
19为什么在实时系统中，要求系统（尤其是CPU）具有较强的处理能力？
答：在实时系统中，通常都有着多个实时任务。若处理机的处理能力不够强，则有可能因处理机忙不过来而使某些实时任务不能及时得到处理，从而导致难以预料的后果。解决的方法是提高系统的处理能力，其途径有二：其一仍是采用单处理机系统，但须增强其处理能力，以显著地减少对每一个任务的处理时间；其二是采用多处理机系统，使其并行从而减少对对个实时任务的总处理时间。
20按调度方式可将实时调度算法分为哪几种？
答：按调度方式的不同，实时调度算法可分为非抢占调度算法和抢占调度算法。由于非抢占式调度算法比较简单，易于实现，故在一些小型实时系统或要求不太严格的实时控制系统中经常采用之，可以分为非抢占式轮转调度算法和非抢占式优先调度算法；在要求较严格的（响应时间为数十毫秒以下）的实时系统中，应采用抢占式优先权调度算法，可根据抢占发生时间的不同而进一步分成基于时钟中断的抢占式优先权调度算法和立即抢占的优先权调度算法。
21什么是最早截止时间优先调度算法？举例说明之。
答：（1）最早截止时间优先调度算法的定义
最早截止时间优先调度算法是根据任务的开始截止时间来确定任务的优先级。截止时间愈早，其优先级愈高。该算法要求在系统中保持一个实时任务就绪队列，该队列按各任务截止时间的早晚排序；当然，具有最早截止时间的任务排在队列的最前面。调度程序在选择任务时，总是选择就绪队列中的第一个任务，为之分配处理机，使之投入运行。最早截止时间优先调度算法既可用于抢占式调度，也可用于非抢占式调度方式中。
（2）举例说明
图3-1所示是将该算法用于非抢占调度方式的例子。该例中有四个非周期任务，它们先后到达。系统首先调度任务1执行，在任务1执行期间，任务2、3又先后到达。由于任务3的开始截止时间早于任务2，故系统在任务1后将调度任务3执行。在此期间又到达作业4，其开始截止时间仍是早于任务2的，故在任务3执行完后，系统又调度任务4执行，最后才调度任务2执行。
图3-1 EDF算法用非抢占调度的调度方式
22什么是最低松弛度优先调度算法？举例说明之。
答：（1）最低松弛度优先调度算法的定义
最低松弛度优先调度算法是根据任务紧急（或松弛）的程度，来确定任务的优先级。任务的紧急程度愈高，为该任务所赋予的优先级就愈高，以使之优先执行。
（2）举例说明
①一个任务在200ms时必须完成，而它本身所需的运行时间就有100ms，因此，调度程序必须在100ms之前调度执行，该任务的紧急程度（松弛程度）为100ms。
②一任务在400ms时必须完成，它本身需要运行150ms，则其松弛程度为250ms。在实现该算法时要求系统中有一个按松弛度排序的实时任务就绪队列，松弛度最低的任务排在队列最前面，调度程序总是选择就绪队列中的队首任务执行。
23何谓“优先级倒置”现象，可采取什么方法来解决？
答：当前OS广泛采用优先级调度算法和抢占方式，然而在系统中存在着影响进程运行的资源而可能产生“优先级倒置”的现象，即高优先级进程（或线程）被低优先级进程（或线程）延迟或阻塞。
24试分别说明可重用资源和可消耗资源的性质。
答：（1）可重用性资源
每一个可重用性资源中的单元只能分配给一个进程使用，不允许多个进程共享。进程在使用可重用性资源时，须按照这样的顺序：请求资源、使用资源、释放资源。系统中每一类可重用性资源中的单元数目是相对固定的，进程在运行期间既不能创建也不能删除它。
（2）可消耗性资源
每一类可消耗性资源的单元数目在进程运行期间是可以不断变化的，有时它可以有许多，有时可能为0。进程在运行过程中，可以不断创造可消耗性资源的单元，将它们放入该资源类的缓冲区中，以增加该资源类的单元数目。进程在运行过程中，可以请求若干个可消耗性资源单元，用于进程自己的消耗，不再将它们返回给该资源类中。
25试举例说明竞争不可抢占资源所引起的死锁。
答：例如，系统中有两个进程P1和P2，它们都准备写两个文件F1和F2，而这两者都属于可重用和不可抢占性资源。进程P1先打开F1，然后再打开文件F2；进程P2先打开文件F2，后打开F1，在P1打开F1的同时，P2去打开F2，每个进程都占有一个打开的文件，此时就可能出现问题。因为当P1试图去打开F2，而P2试图去打开F1时，这两个进程都会因文件已被打开而阻塞，它们希望对方关闭自己所需要的文件，但谁也无法运行，因此这两个进程将会无限期地等待下去，而形成死锁。
26为了破坏“请求和保持”条件而提出了两种协议，试比较这两种协议。
答：（1）第一种协议在所有进程开始运行之前，必须一次性地申请其在整个运行过程中所需的全部资源，并且在分配资源时，只要有一种资源不能满足进程的要求，即使其他所需的各种资源都空闲也不分配给该进程，而让该进程等待。因此有资源被严重浪费、进程经常会发生饥饿现象等缺点。
（2）第二种协议是对第一种协议的改进，它允许一个进程只获得运行初期所需的资源后，便开始运行。进程运行过程中再逐步释放已分配给自己的，且已用毕的全部资源，然后再请求新的所需资源。如此便可提高设备的利用率，还可减少进程发生饥饿的概率。
27何谓死锁？产生死锁的原因和必要条件是什么？
答：（1）死锁的定义
死锁是指多个进程因争夺资源而造成的一种僵局（相互等待），若无外力作用，它们都将无法再向前推进。
（2）产生死锁的原因
产生死锁的原因可归结为竞争不可剥夺资源引起进程死锁和进程推进顺序不当引起死锁两个方面。
（3）产生死锁的必要条件
①互斥条件；
②请求和保持条件；
③不剥夺条件；
④环路等待条件。
28在解决死锁问题的几个方法中，哪种方法最易于实现？哪种方法使资源利用率最高？
答：目前，处理死锁的方法可归结为以下四种：
（1）预防死锁；
（2）避免死锁；
（3）检测死锁；
（4）解除死锁。
其中，预防死锁最容易实现，避免死锁使资源利用率最高。
29请详细说明可通过哪些途径预防死锁。
答：预防死锁的方法破坏产生死锁的四个必要条件的一个或几个，而互斥条件是由设备的固有特性所决定的，不仅不能改变，还应加以保证。因此，可以从以下三个方面预防死锁：
（1）破坏“请求和保持”条件
在采用这种方法时，系统规定所有进程在开始运行前，都必须一次性地申请其在整个运行过程所需的全部资源。
（2）破坏“不剥夺”条件
在采用这种方法时，系统规定进程是逐个地提出对资源的要求的。当一个已经保持了某些资源的进程，再提出新的资源请求而不能立即满足时，必须释放它已保持的所有资源，待以后需要时再重新申请。
（3）破坏“环路等待”条件
这种方法中规定，系统将所有资源按照类型进行线性排队，并赋予不同的序号。所有进程对资源的请求必须严格按资源序号递增的次序提出。
30在银行家算法的例子中，如果P0发出的请求向量由Request（0，2，0）改为Request（0，1，0），问系统可否将资源分配给它？
答：可以。银行家算法中各种资源的总数量分别为10、5、7，在T0时刻的资源分配如表3-3所示。
表3-3 资源分配情况
具体分析如下：
（1）Requst0（0，1，0）＜=Need0（7，4，3）；
（2）Requst0（0，1，0）＜=Available（3，3，2）；
系统先假定可为P0分配资源，并修改Available，Allocation0和Need0向量，由此形成的资源变化情况如表3-4所示。
表3-4 资源变化情况
系统按银行家算法进行检查，如表3-5所示。
表3-5 按银行家算法检查结果
得到安全序列＜P1，P3，P4，P0，P2＞，因此系统是安全的，可以将资源分配给它。
31在银行家算法中，若出现下述资源分配情况，试问：
（1）该状态是否安全？
（2）若进程P2提出请求Request（1，2，2，2）后，系统能否将资源分配给它？
答：（1）安全，因为存在安全序列{P0，P3，P4，P1，P2}，如表3-6所示。
表3-6 资源分配情况
（2）分析如下。
①Request（1，2，2，2）＜=Need2（2，3，5，6）；
②Request（1，2，2，2）＜=改成Available2（1，6，2，2）；
③系统先假定可为P2分配资源，并修改Available2，Allocation2和Need2向量，由此形成的资源变化情况如表3-7所示。
表3-7 资源变化情况
④再利用安全性算法检查此时系统是否安全。此时（0，4，0，0）不能满足任何进程的资源请求，因此，在进程P2提出请求Request（1，2，2，2）后，系统不能将资源分配给它。