《操作系统》练习题及答案

统进程的优先权高于一般用户进程的优先权（除非用户的进程特别紧迫或重要）

5． 错误

因为摒弃不剥夺条件的方法可预防死锁的发生。 6． 错误

因为，操作系统要兼顾资源的使用效率和安全性两个方面，常见的是，将预防、解除、检测、避免四种处理混合起来使用。举例来说，只有检测死锁而无解除死锁，检测出死锁又有什么用呢？

7． 正确

因为资源的“静态分配”方法，可以摒弃“请求和保持”条件，是可以预防死锁的。 8． 错误

进程是否发生死锁，需要考虑每个进程申请资源的数目、所申请资源的种类、进程推进情况等因素。不能简单地比较进程数目和资源数目就来确定是否死锁。

9． 错误

系统在调用银行家算法进行安全检查时，只要找到一个安全序列就可断定系统是安全的。但安全序列可能不止一个，有的情况下可能是只有一个，有的情况下可能有2个或者更多。

10． 错误

如果进程调度算法选择不当，会造成某些进程的长期等待。我们将这种进程称为“饥饿”进程（长期“饥饿”的极端情况是“饿死”）。“饿死”和“死锁”具有完全不同的含义。

4.3.4 简答题

1．高级调度和低级调度的主要任务以及引入中级调度原因如下：

(1) 高级调度又称为作业调度。它是批处理系统中使用的一种调度。其主要任务是，按照某种算法从外存的后备队列上选择一个或多个作业调入内存，并为它们创建进程、分配必要的资源，然后再将创建的进程控制块挂入就绪队列上。

(2) 低级调度又称进程调度。它是距离硬件最近的一级调度。其主要任务是，按照某种算法从就绪队列上选择一个（或多个）进程，使其获得CPU。

(3) 引入中级调度的目的是为了提高内存利用率和系统吞吐量。其功能是，让那些暂时不能运行的进程不再占用宝贵的内存资源，而是调出到外存上等待。此时的进程状态为挂起状态。当这些进程重新具备运行条件且内存空闲时，由中级调度选择一部分挂起状态的进程调入内存，将其状态变为内存就绪状态。

2．在作业调度中需作出的决定如下：

(1) 作业调度需要按照多道程序度（即，最大道数）决定一次接纳多少作业进入内存。如果太少将导致系统资源利用率低，且系统吞吐量低；太多将导致内存空间紧张，系统服务质量下降，使作业运行周期过长。

(2) 作业调度需要决定接纳哪些作业进入内存。常用的算法是，先来先服务，短作业优先，最高优先级调度、响应比高者优先等。

3．在剥夺进程调度中，剥夺原则如下：

(1) 时间片原则。在轮转算法中，CPU轮流为诸多进程服务，每个进程运行完自己的时间片后，系统就将它的CPU剥夺过来，交给下一个进程使用。

(2) 优先级原则。为紧迫的作业赋予较高的优先级，这种作业到达系统，或者由阻塞状态被唤醒后，若其优先级高于当前运行的进程的优先级，可以剥夺其CPU。

(3) 短作业（进程）优先原则。若一个作业（进程）到达系统，其运行长度比当前运行的进程长度明显的短，则剥夺它的CPU。

4．引起进程调度的主要因素主要有： (1) 一个进程运行完毕；

(2) 一个正在运行的进程被阻塞；

(3) 在抢占式调度中，一个高优先级的进程被创建；

(4) 在抢占式调度中，一个高优先级进程由阻塞被唤醒； (5) 在轮转式调度中，正在运行的进程运行完一个时间片。 5．在选择调度方式和调度算法时，应遵循的原则如下：

- 25 -

(1) 面向用户准则。首先，对于用户的紧迫性作业，系统能够及时地处理，不至于运行延误。其次，对于批处理系统，还应追求作业的周转时间短；分时系统中作业的响应时间块；实时系统中作业的截止时间有保证。

(2) 面向系统准则。系统的吞吐量高，处理机的利用率高，各类系统资源能够得到平衡利用。

6．批处理系统、分时系统和实时系统中的主要调度算法如下：

(1) 批处理系统中的作业调度算法有先来先服务（FCFS）、短作业优先（SJF）、优先级调度（HPF）和高响应比优先（RF）。批处理系统的进程调度算法有：先进先出（FIFO）、短进程优先（SPF）、优先级调度（PRI）和高响应比优先（RF）。

(2) 分时系统中只设有进程调度（不设作业调度），其进程调度算法只有轮转法（RR）一种。

(3) 实时系统中只设有进程调度（不设作业调度），其进程调度算法有：轮转法、优先级调度算法。前者适用于时间要求不严格的实时系统；后者用于时间要求不严格的实时系统。后者又可细分为：非抢占式优先级调度、抢占式优先级调度、基于时钟中断的抢占式优先级调度。 注意，一个纯粹的实时系统是针对特定应用领域设计的专用系统。作业提交的数量不会超过系统规定的多道程序度，因而可全部进入内存。若将实时系统与批处理系统结合的话，就可以让作业量超过多道程序度，使优先级低的作业呆在外存的后备队列上。

7．多级反馈队列能较好地满足各种用户的需要的原因：

(1) 终端用户的作业一般比较短小精悍，大多数在进入多级队列的第一级队列中后运行一个时间片就可以完成，因而感到满意。

(2) 批处理作业用户，其作业进入多级队列的第一级队列中后，若作业较短，运行一个时间片就可以完成。对于稍长一些的作业，只需在第二或第三队列上各执行一个时间片就可完成，因而感到满意。对于长作业来说，它将依次在第1，2，?，n个队列上运行，不会因作业太长而长期得不到处理。

8．在多用户分时时间片长度的选择上，既要保证交互性，又要保证系统的效率。

(1) 系统对响应时间T的要求（一般应小于等于2~3秒钟）； (2) 就绪队列中的进程数目N（N与终端上的用户数目有关）；

(3) 系统的处理能力，一个时间片的长度q应能保证用户的大部分常用命令可处理完；

(4) 进程的转换时间p；

(5) 三者的关系可表示为：T=N(q+p)。 9．对实时系统提出了要求如下：

(1) 任务要提供必要的调度信息：主要包括：开工的最后期限或完工的最后期限、处理时间长度、优先级、就绪时间，以及资源需求。

(2) 采用适当的调度方式：如果实时任务的运行长度较长且时间要求严格，那么实时系统应采用抢占式调度；如果所有的实时任务都比较小，且预知任务的开工最后期限，也可以采用非剥夺式调度。

(3) 能够快速响应外部中断：这要求，硬件上要有较高的中断机制，软件上要使“封中”的时间间隔尽量短，以免贻误时机。

(4) 快速的任务分派能力：尽量减少任务切换时间开销，使得一个任务完成后可以较快地切换到下一个任务去。 10．抢占方式和非抢占方式都可以用于实时系统中。能够使用的算法有：轮转算法（RR）和优先级调度算法（HPF）；不可以使用的算法有：先进先出（FIFO）和短进程优先算法（SPF）。

11．在多处理机系统中，有代表性的线程调度方式有：

(1) 自调度方式：诸多CPU可以共享同一就绪队列，从中获取就绪线程运行。 (2) 成组调度方式：由系统将若干相关的线程同时分配到多台CPU上运行。线程与CPU一一对应。

(3) 专用处理机分配方式：将若干同属于一个应用程序的线程分配到一组CPU上。让这组CPU专门处理它们。

12．调度方式的比较如下：

- 26 -

(1) 自调度方式中，就绪队列与单机的相同，调度算法也与之相同。系统没有集中调度机制，任何CPU都可调用系统的调度例程去选择一个线程。只要就绪队列不空，就不会有空闲的CPU。它存在的问题是，多CPU共享一个就绪队列将产生瓶颈；各线程在其生命周期中可能要换好几台CPU，每次更换都要将CPU中的高速缓存（Cache）重新拷入现场数据，造成效率低下；由于合作的一组线程很难同时获得CPU，一些运行的线程只好阻塞等待未获得CPU的线程，所以线程切换频繁。

(2) 成组调度中，合作的各线程可以同时获得CPU，减少因同步造成的阻塞，减少了切换次数。同时，也可减少调度的频率。

13．多优先级的抢占式调度，调度的基本单位是线程。优先级分为3类：每一类共细分32级，以31级为最高级。其中：时间紧迫类为最高类，对应的是实时线程及通信管理等；常规类为中档优先类，对应的是一般线程；空闲时间类为较低类，对应的是紧迫度低的线程。

调度算法：在同一类的同一优先级中采用轮转算法。每当运行完一个时间片就检查是否有更高优先级线程到来，若有便抢占CPU。

14．

(1) 死锁是指多个进程因竞争资源而造成的一种僵持状态。若无外力作用，这些进程都将永远处于阻塞状态，不能再运行下去。

(2) 产生死锁的原因有：资源不足资源、进程推进次序不当。

(3) 产生死锁的必要条件有：互斥条件、请求和保持条件、不可剥夺条件、环路等待条件。

15．

(1) 预防死锁方法，主要是破坏产生死锁的必要条件。该方法是最容易实现的，但系统资源利用率较低。

(2) 避免死锁方法，比较实用的有银行家算法（Banker Algorithm）。该算法需要较多的数据结构，实现起来比较困难，但资源利用率最高。

（3）检测死锁方法是基于死锁定理设计的，定期运行该算法对系统的状态进行检测，发现死锁便予以解除。其中，需要比较一下各种死锁解除方案的代价，找到代价最小的方案。该方法最难实现，资源利用率较高。

16．预防死锁方法是破坏产生死锁的必要条件，主要有：

(1) 摈弃请求和保持条件。采用静态分配方案，一次性地分配给进程所请求的全部资源。进程运行过程中不可再请求新资源。

(2) 摈弃不剥夺条件。采用动态分配方案，进程运行中可以请求新资源。若进程请求资源不能满足时，就应使其释放已占有的资源。

(3) 摈弃环路等待条件。采用动态分配方案，要求进程请求资源时，按资源序号递增（或递减）顺序提出。 17．系统的资源数量为：（10，5，7）。经过一段时间的分配后，资源分配与占用情况见下表所示。

进程 P0 P1 P2 P3 P4 MAX A B C 7 5 3 3 2 2 9 0 2 2 2 2 4 3 3 Allocation A B C 0 1 0 2 0 0 3 0 2 2 1 1 0 0 2 Need Available A B C A B C 7 4 3 1 2 2 6 0 0 0 1 1 4 3 1 3 3 2

（1） Request1(1,0,2)：P1请求满足后的占用情况如下。

进程 P0 P1 MAX A B C 7 5 3 3 2 2 Allocation A B C 0 1 0 3 0 2 Need Available A B C A B C 7 4 3 0 2 0 2 3 0 - 27 -

P2 P3 P4 9 0 2 2 2 2 4 3 3 3 0 2 2 1 1 0 0 2 6 0 0 0 1 1 4 3 1

（2）检测系统此刻存在一条安全序列{P1，P3，P4，P0，P2}。检测过程为： 1) 资源可用量（230），不能满足P0，可满足P1。 2) 资源可用量（532），不能满足P2，可满足P3。 3) 资源可用量（743），可满足P4。 4) 资源可用量（745），可满足P0。 5) 资源可用量（755），可满足P2。待其完成后使系统的资源可用量达到初始值（10，

5，7）。

（3）Request4(3,3,0)：P4的请求超过系统当前的可用量（2,3,0），应推迟分配。 （4）Request0(0,1,0)：P0请求满足后的占用情况如下：

进程 P0 P1 P2 P3 P4 MAX A B C 7 5 3 3 2 2 9 0 2 2 2 2 4 3 3 Allocation A B C 0 2 0 3 0 2 3 0 2 2 1 1 0 0 2 Need Available A B C A B C 7 3 3 0 2 0 6 0 0 0 1 1 4 3 1 2 2 0

检测系统此刻存在安全序列{P1，P3，P4，P0，P2}。

1) 资源可用量（220），不能满足P0，可满足P1。 2) 资源可用量（522），不能满足P2，可满足P3。 3) 资源可用量（733），可满足P4。 4) 资源可用量（735），可满足P0。 5) 资源可用量（755），可满足P2。待其完成后使系统的资源可用量达到初始值

（10，5，7）。

- 28 -