操作系统 —— 处理机调度与死锁

（一）简答题

1.高级调度与低级调度的主要任务是什么？为什么要引人中级调度？

参考答案：

         ①高级调度的对象是作业。它的主要任务是根据某种算法，决定 将外存上处于后备队列中的哪几个作业调入内存，为它们创建进程、 分配必要的资源，并将它们放入就绪队列。 ②低级调度的对象是进程(或内核级线程)。它的主要任务是根据 某种算法,决定就绪队列中的哪个进程获得处理机，并由分派程序将处 理机分配给被选中的进程。
         引入中级调度的主要目的是提高内存利用率和系统吞吐量。为此 应把那些暂时不能运行的进程调至外存等待，把进程状态改为就绪驻外存状态或挂起状态。当它们已具备运行条件且内存又有空间时，由 中级调度来决定把外存上的那些已具备运行条件的就绪进程再重新调入内存，并修改它们的状态为就绪状态，挂在就绪队列上等待。

2.何谓作业和JCB？

答：

作业是一组程序与数据和作业说明书，是高级调度的基本单位。
JCB是作业控制块，是作业存在的表示，包含管理，调度所需的全部信息。

3.在什么情况下需要使用JCB？其中包含了哪些内容？

答： 作业进入系统。

包含系统对作业调度，管理的全部信息。

JCB的使用场景，具体来说：

作业提交: 当一个新的作业进入系统，为了管理和执行这个作业，系统需要为其创建一个JCB。

作业调度: 在作业调度时，调度程序会查看每个JCB的优先级、资源需求等信息，来决定哪个作业应当先执行。

资源分配: 操作系统需要查看JCB中的资源需求信息，以确定为作业分配哪些资源。

进程管理和通信: JCB也用于进程的管理和进程间通信。

JCB通常包含了哪些内容？

作业标识符: 唯一标识每个作业的标识符。

处理器状态: 包括程序计数器、寄存器状态、程序的状态（如就绪、执行、等待等）。

作业优先级: 用于作业调度。

作业的内存需求: 包括作业需要的总内存大小、开始地址、结束地址等。

输入/输出设备需求: 表示作业需要的输入和输出设备。

作业的磁盘存储需求: 如文件存储需求。

计时信息: 包括作业的提交时间、开始时间、结束时间等。

资源需求和状态: 例如，该作业是否需要打印机、磁带驱动器等。

账务信息: 记录作业使用的系统资源，用于计费。

指向下一个和/或前一个JCB的指针: 用于在作业队列中维持JCB的顺序。

其他: 根据特定的操作系统和实现，JCB可能还包括其他信息。

4.在作业调度中应如何确定接纳多少个作业和接纳哪些作业？

答：根据系统规模，运行速度，作业大小以及能否获得较好的系统性能等情况决定接纳多少个作业根据调度算法决定接纳哪些作业。

5.试说明低级调度的主要功能。

低级调度用于决定就绪队列中的哪个进程应获得处理机，并由分派程序把处理机分配给该进程。其主要功能有：

1.保存当前进程的处理机现场信息。

2.按某种算法选择投入执行的新进程

3.恢复新进程的现场，从而将处理机分配给新进程

6.简述引起进程调度的原因。

答：引起进程调度的因素有：
（1）正在执行的进程正常终止或异常终止。
  (2）正在执行的进程因某种原因而阻塞。具体包括：
        提出 I/O请求后被阻塞;
        在调用 wait 操作时因资源不足而阻塞;

        因其他原因执行block原语而阻塞等。

(3）在引入时间片的系统中，时间片用完。
(4）在抢占调度方式中，就绪队列中某进程的优先权变得比当前正在执行的进程高,或者有优先权更高的进程进入就绪队列。

7.在抢占式调度算法中，抢占的原则是什么？

答：时间片原则  短进程优先  优先权原则

8.在选择调度方式和调度算法时，应遵循哪些准则？

答:(1)面向用户的准则:周转时间短、响应时间快、截止时间的保证、优先权准则。

(2)面向系统的准则:系统吞吐量高、处理机利用率好、各类资源的平衡利用。

9.何谓静态优先级和动态优先级？确定进程优先级的依据是什么？

参考答案： ①静态优先级是指在创建进程时确定的、在进程的整个运行期间 保持不变的优先级。 ②动态优先级是指在创建进程之初，先赋予进程一个优先级，然 后其值会随进程的推进或等待时间的增加而改变，如此而为的目的是 获得更好的调度性能。

此外，确定进程优先级，在计算机操作系统习题与考研真题解析的依据有进程类型、进程对资源的需求和用户要求等。

10.试比较FCFS和SJF这两种调度算法。

答:

        FCFS按照进程到达的先后顺序排队,每次调度队首的进程,属于非剥夺调度方式,实现简单,看似公平。但对于那些后进入队列而运行时间较短的进程,或I/O型的进程而言,可能需要等待较长时间。
        SJF属于非剥夺方式调度算法。当需要调度作业(进程)时,通过计算判断就绪队列中哪一个进程预计执行时间最短,或后备作业队列中哪一个或几个作业预计执行时间最短,就调度谁。当某个进程获得处理机,直到其执行完成,或需要等待某个事件而阻塞时,才自动释放处理机,系统又调度新的进程或作业。与FCFS算法比较,短进程优先调度算法改善了系统的性能,降低了系统的平均等待时间,提高了系统的吞吐量。但是该算法也存在一些问题:
(1)很难准确地预测进程的执行时间;
(2)可能导致长进程饥饿,对长进程不利。
(3)采用非剥夺方式, 未考虑进程的紧迫程度,不适合于分时系统或者事务处理系统。

11.在基于时间片的RR调度算法中，应如何确定时间片的大小？

参考答案： 在RR调度算法中，时间片的大小对系统性能有很大的影响。通 常，时间片应略大于一次典型的交互所需的时间，使大多数交互式进 程能在一个时间片内完成，从而获得很小的响应时间。在确定时间片的大小时，一般应考虑3个因素：系统对相应时间的要求、就绪队列 中进程的数目和系统的处理能力。

12.为什么说多级反馈队列调度算法能较好地满足各方面用户的需求？

答:多级反馈队列调度算法能较好地满足各种用户的需要。①对终端型用户而言,用户所提交的作业大都属于交互型作业,作业通常比较小,系统只要能使这些作业在第一队列所规定的时间内完成,便可使终端型用户感到满意。②对于短的批处理作业用户而言,他们的作业开始像终端型作业一样,如果仅在第一队列中执行一个时间片即可完成,便可获得与终端型作业一样的响应时间,对于稍长的作业,通常也只需要在第二队列和第三队列各执行一个时间片即可结束,其周转时间仍然较短。③对于长批处理作业用户而言,他们的长作业将依次在第1,2,---,直到第N 个队列中运行,然后再轮转方式运行,用户不必担心其作业长期得不到处理。

13.为什么在实时系统中要求系统（尤其是CPU）具有较强的处理能力？

答:实时系统中通常有着多个实时任务.若处理机的处理能力不够强,有可能因为处理机忙不过来而使某些实时任务得不到与时处理,导致发生难以预料的后果.

14.按照调度方式可将实时调度算法分为哪几种？

答:可分为非抢占式和抢占式两种算法。而非抢占式算法又分为非抢占式轮转和优先调度算法;抢占式调度算法又分为基于时钟中断的抢占式优先权和立即抢占式优先权调度算法。

15.实时系统常用的调度算法有哪些？请分别介绍它们。

[答案]:实时调度常用4种调度算法:

时间片轮转调度算法,适用于一般的实时信息处理系统;

非抢占的优先级调度算法,适用于实时要求不太严格的实时控制系统;

基于时钟中断抢占的优先级调度算法,适用于大多数实时系统;

立即抢占的优先级调度算法,适用于实时要求比较严格的实时控制系统。

16.在批处理系统、分时系统和实时系统中，各采用哪几种进程（作业）调度算法？

[解答]在批处理系统中,可采用的进程(作业)调度算法有先来先服务调度算法、优先级调度算法、短作业优先调度算法、高响应比优先调度算法等,进程调度还可以采用时间片轮转法。
在分时系统中,只设有进程调度,不设作业调度。通常使用的调度算法是时间片轮转法、多级队列调度算法及多级反馈队列调度算法。
在实时系统中,只设有进程调度,不设作业调度,通常使用基于优先数的优先级调度算法和时间片轮转法。其中,时间片轮转法只适用于对时间要求不太苛刻的实时系统,优先级调度算法适用于对时间要求较为苛刻的实时系统。

17.什么是死锁？产生死锁的原因和必要条件是什么？如何预防死锁？

答：

        死锁是指多个进程在运行过程中因争夺资源而造成的一种情形，当进程处于这种状态的时，若无外力作用，它们都将无法向前推进。

        产生死锁的原因：竞争不可抢占性资源，竞争可消耗资源，进程间推进顺序不当

        产生死锁必须同时具备4个必要条件：互斥条件，请求与保持条件，不可抢占条件，循环等待条件。

        预防死锁是通过破坏死锁的4个必要条件中的一个或者几个来实现的：其中互斥条件是设备固有属性，不能改变，因此主要破坏产生死锁的其他3个必要条件。 ①破坏“请求和保持”条件。当一个进程在请求资源时，它不能持有不可 抢占性资源。 ②破坏“不可抢占”条件。当一个已经保持了某些不可抢占性资源的进程 需要时再重新申请 ③破坏“循环等待”条件。对系统所有资源类型进行线性排序，并赋予它 们不同的序号，规定每个进程必须按序号递增的方式请求资源

18.在解决死锁问题的几个方法中，哪个方法最易于实现？哪个方法可使资源利用率最高？

答：解决死锁问题的方法有预防死锁、避免死锁、检测和解除死锁，其中预防死锁最易于实现，检测和解除死锁可使资源利用率最高。

二、计算题

19.有5个进程（见表3-2）需要调度执行，若采用非抢占式优先级（短进程优先）调度算法，问这5个进程的平均周转时间是多少？
 

答：

20.假定要在一台处理机上执行表3-3所示的作业，且假定这些作业在时刻0以1,2,3,4,5的顺序到达，请说明分别采用FCFS，RR（时间片为1）、SJF及非抢占式优先级调度算法时：这些作业的执行情况（优先级的高低顺序依次为1到5）。针对上述每一种调度算法，给出平均周转时间和平均带权周转时间。

 答：

  

21.将一组进程分为4类，如图3-23所示。各类进程之间采用优先级调度算法，而各类进程的内部采用RR调度算法。请简述P1，P2，P3,P4,Ps，Po，P7，Ps进程的调度过程。

答：从题意可知，各类进程之间采用优先级调度算法，而同类进程部采用时间片轮转调度算法，因此，系统首先对优先级为4的进程P1、P2、P3采用时间片轮转调度算法运行；当P1、P2、P3均运行结束或没有可运行的进程（即P1、P2、P3都处于等待状态；或其中部分进程已运行结束，其余进程处于等待状态）时，则对优先级为3的进程P4、P5采用时间片轮转调度算法运行。在此期间，如果未结束的P1、P2、P3有一个转为就绪状态，则当前时间片用完后又回到优先级4进行调度。类似地，当P1～P5均运行结束或没有可运行进程（即P1～P5都处于等待状态；或其中部分进程已运行结束，其余进程处于等待状态）时，则对优先级为2的进程P6、P7、P8采用时间片轮转调度算法运行，一旦P1～P5中有一个转为就绪状态，则当前时间片用完后立即回到相应的优先级进行时间片轮转调度。

 
22.由5个进程组成进程集合P={P0,P1,P2，P3，P4}，且系统中有3类资源A，B，C，假设在某时
刻有表3-4所示的进程资源分配情况。
 
请问当x，y，z取下列值时，系统是否处于安全状态？（1)1,4,0；（2)0,6,2;（3)1,1,1;(4)0,4,7。

答：

求Need：

进程	ALLocation	Max	Need	Available
P0	0 0 3	0 0 4	0 0 1	x y z
P1	1 0 0	1 7 5	0 7 5
P2	1 3 5	2 3 5	1 0 0
P3	0 0 2	0 6 4	0 4 2
P4	0 0 1	0 6 5	0 5 4

 当x,y,z=1,4,0时， 找安全序列,显然向量1,4,0   大于   Need的向量的进程只有P2，

进程	ALLocation	Max	Need	Available
P0	0 0 3	0 0 4	0 0 1	1,4,0
P1	1 0 0	1 7 5	0 7 5
P2	1 3 5	2 3 5	1 0 0
P3	0 0 2	0 6 4	0 6 2
P4	0 0 1	0 6 5	0 6 4

故

进程	Work	Need	Allocation	work+Allocation
P2	1 4 0	1 0 0	1 3 5	2 7 5
P0	2 7 5	0 0 1	0 0 3	2 7 8
P1	2 7 8	0 7 5	1 0 0	3 7 8

可以满足进程P2的需求，当P2结束后释放资源，此时Avaliable为（2，7，5）此时可以满足P0，P1，P3，P4中任一进程的需求，所以系统不会出现死锁，当前处于安全状态。

2） 当x,y,z=0,6,2时，满足的进程有P3，P0

故：

进程	Work	Need	Allocation	work+Allocation
P3	0 6 2	0 6 2	0 0 2	0 6 4
P4	0 6 4	0 6 4	0 0 1	0 6 5（此情况不满足其他进程的需求，舍去）

或

进程	Work	Need	Allocation	work+Allocation
P0	0 6 2	0 0 1	0 0 3	0 6 7
P4	0 6 7	0 6 4	0 0 1	0 6 8
P3	0.68	0 6 2	0 0  2	0 6 10（此情况不满足其他进程的需求，舍去）

 故0 6 2不处于安全状态 ，其余类似 

三、综合应用题

23.假设系统中有下述3种解决死锁的方法：

（1）银行家算法；
（2）检测死锁，终止处于死锁状态的进程，释放该进程所占有的资源；
（3）资源预分配。
简述上述哪种方法允许最大的并发性？请按“并发性”从大到小对上述3种方法进行排序。

答：

        三种办法中，首先，检测死锁允许更多的进程无等待地向前推进。因为该方法允许死锁出现，即允许进程最大限度地申请并分配资源，直至出现死锁，再由系统出面解决。其次是银行家算法，该方法允许进程自由申请资源，只是在某个进程申请时检查系统是否处于安全状态，若是，则可立即分配，若不是，才拒绝。最后是资源预分配，因为此方法要求进程在运行之前申请所需的全部资源才可开始运行，这样会使得许多进程因申请不到资源而无法开始，得到资源的进程也并不是同时需要所占的全部资源，因此导致资源的浪费。

另一种答案：

并发性：检测死锁>银行家算法>资源预分配 

检测死锁：允许进程自由申请资源，直至出现死锁，再由系统解决死锁。 进程无须等待地向前推进 

银行家算法（避免死锁）：允许进程自由申请资源，检查系统是否处于安全状态 若是，则可立即分配；若不是，则拒绝某些进程请求可能被拒绝。

 资源预分配（预防死锁）：要求进程在运行之前申请所需的全部资源。 许多进程因申请不到全部资源而无法开始，得到部分资源的进程也会因未得到全部 资源而不释放已占用的资源。

 
24.某银行要实现一个电子转账系统，基本业务流程是首先对转出方和入方的账户进行加锁，然后办理转账业务，最后对转出方和转入方的账户进行解锁。若不采取任何措施，则系统会不会发生死锁？为什么？请设计一个能够避免死锁的方法。

答：因为对两个账户进行加锁操作是可以分割执行的，若此时有两个用户同时进行转账，P1先对账户A进行加锁，再申请账户B；P2先对账户B进行加锁，再申请账户A，此时死锁。解决的办法是：可以采用资源顺序分配法，将A、B账户进行编号，用户转账时，只能按照编号由小到大进行加锁。也可以采用资源预分配法，要求用户在使用资源之前将所有资源一次性申请到。

25、设有进程P，和进程P并发执行，它们都需要使用资源R和R2，使用资源情
况如表3-5所示。
 

试判断是否会发生死锁，并解释和说明发生死锁的原因与必要条件。

答：这两个进程在不同的推进速度下，可能会产生死锁。比如：进程P1先申请资源R1，P1得到R1后进程P2申请R2，P2得到R2后，P1又申请资源R2，此时则因R2已分配，故P1阻塞。P1和P2两个进程因申请不到所需资源而形成死锁。如果改变进程的运行顺序，则这两个进程可能又不会发生死锁。
因此，产生死锁的原因可归结为两点：①竞争资源；②进程推进顺序非法。产生死锁的必要条件：①互斥条件；②请求和保持条件；③不可抢占条件;④循环等待条件。