一、处理器调度的层次

（一）、不同级别的调度


1、高级调度：它用于确定把后备队列上的哪些作业调入内存,并为之建立进程,分配其所需的资源,然后将它挂在就绪队列上。

2、中级调度：引入中级调度的主要目的是为了提高内存的利用率和系统的吞吐量。内存中不能有太多的进程，把进程从内存移到外存，当内存有足够空间时，再将合适的进程换入内存，等待进程调度。中级调度实际上就是存储器管理中的对调功能。

3、低级调度

完成调度和分派的功能

调度：实现调度策略，决定哪个进程使用CPU

分派：确定如何时分复用CPU，处理上下文交换细节，完成进程/线程和CPU的绑定和放弃的实际工作。

低级调度的类型：剥夺式与非剥夺式

低级调度的算法：

（1）、先来先服务

（2）、最短作业优先：会出现饥饿现象，平均周转时间好

（3）、最短剩余时间优先

（4）、最高响应比优先

（5）、时间片轮转

（6）、多级反馈队列


 

 

（二）、处理器三级调度模型



 （三）、两级调度



 

二、作业、

作业的概念


•作业是任务实体，进程是完成任务的执行实体;没有作业任务，进程无事可干，没有进程，作业任务没法完成。

•作业概念更多地用在批处理操作系统，而进程则可以用在各种多道程序设计系统。

 

处理机调度是操作系统的主要功能之一，它的实现策略决定了操作系统的类型，其调度算法的优劣直接影响整个系统的性能。处理机调度的任务是选出待分派的作业或进程，为之分配处理机。 
一般来说，处理机调度可分为三个级别，分别是高级调度、中级调度和低级调度。 
高级调度又称作业调度，作业就是用户程序及其所需的数据和命令的集合，作业管理就是对作业的执行情况进行系统管理的程序的集合。作业调度程序的主要功能是审查系统是否能满足用户作业的资源要求以及按照一定的算法来选取作业。 
引入中级调度的主要目的是为了提高内存的利用率和系统吞吐量，使得暂时不运行的进程从内存对换到外存上。 
低级调度又称进程调度，其主要功能是根据一定的算法将cpu分派给就绪队列中的一个进程。进程调度是操作系统中最基本的一种调度，其调度策略的优劣直接影响整个系统的性能。 

操作系统第四版课后的全部习题答案，学习通作业答案。

说明：操作系统其他章节的习题答案也在此“操作系统”专栏。

第三章
1．高级调度与低级调度的主要任务是什么？为什么要引入中级调度？
答：高级调度的主要任务是根据某种算法，把外存上处于后备队列中的那些作业调入内存。低级调度是保存处理机的现场信息，按某种算法先取进程，再把处理器分配给进程。引入中级调度的主要目的是为了提高内存利用率和系统吞吐量。使那些暂时不能运行的进程不再占用内存资源，将它们调至外存等待，把进程状态改为就绪驻外存状态或挂起状态。
2．何谓作业、作业步和作业流？
答：作业包含通常的程序和数据，还配有作业说明书。系统根据该说明书对程序的运行进行控制。批处理系统中是以作业为基本单位从外存调入内存。作业步是指每个作业运行期间都必须经过若干个相对独立相互关联的顺序加工的步骤。作业流是指若干个作业进入系统后依次存放在外存上形成的输入作业流；在操作系统的控制下，逐个作业进程处理，于是形成了处理作业流。
3．在什么情况下需要使用作业控制块JCB？其中包含了哪些内容？
答：每当作业进入系统时，系统便为每个作业建立一个作业控制块JCB，根据作业类型将它插入到相应的后备队列中。JCB 包含的内容通常有：1) 作业标识2)用户名称3)用户账户4)作业类型（CPU繁忙型、I/O芳名型、批量型、终端型）5)作业状态6)调度信息（优先级、作业已运行）7)资源要求8)进入系统时间9) 开始处理时间10)作业完成时间11) 作业退出时间12) 资源使用情况等
4．在作业调度中应如何确定接纳多少个作业和接纳哪些作业？
答:作业调度每次接纳进入内存的作业数，取决于多道程序度。应将哪些作业从外存调入内存，取决于采用的调度算法。最简单的是先来服务调度算法，较常用的是短作业优先调度算法和基于作业优先级的调度算法。
5．试说明低级调度的主要功能。
答：（1）保存处理机的现场信息（2）按某种算法选取进程（3）把处理机分配给进程。
6．在抢占调度方式中，抢占的原则是什么？
答：抢占的原则有：时间片原则、优先权原则、短作业优先权原则等。
7．在选择调度方式和调度算法时，应遵循的准则是什么？
答：

（1）面向用户的准则：周转时间短、响应时间快、截止时间的保证、优先权准则。

（2）面向系统的准则：系统吞吐量高、处理机利用率好、各类资源的平衡利用。
8．在批处理系统、分时系统和实时系统中，各采用哪几种进程（作业）调度算法？
答：批处理系统的调度算法：短作业优先、优先权、高响应比优先、多级反馈队列调度算法。

分时系统的调度算法：时间片轮转法。

实时系统的调度算法：最早截止时间优先即EDF、最低松弛度优先即LLF算法。
9．何谓静态和动态优先级？确定静态优先级的依据是什么？
答：静态优先级是指在创建进程时确定且在进程的整个运行期间保持不变的优先级。

动态优先级是指在创建进程时赋予的优先权，可以随进程推进或随其等待时间增加而改变的优先级，可以获得更好的调度性能。

确定进程优先级的依据：进程类型、进程对资源的需求和用户要求。
10．试比较FCFS和SPF两种进程调度算法。
答：相同点：两种调度算法都可以用于作业调度和进程调度。

不同点：FCFS调度算法每次都从后备队列中选择一个或多个最先进入该队列的作业，将它们调入内存、分配资源、创建进程、插入到就绪队列。该算法有利于长作业/进程，不利于短作业/进程。SPF算法每次调度都从后备队列中选择一个或若干个估计运行时间最短的作业，调入内存中运行。该算法有利于短作业/进程，不利于长作业/进程。
11．在时间片轮转法中，应如何确定时间片的大小？
答：时间片应略大于一次典型的交互需要的时间。一般应考虑三个因素：系统对相应时间的要求、就绪队列中进程的数目和系统的处理能力。
12．通过一个例子来说明通常的优先级调度算法不能适用于实时系统？
答：实时系统的调度算法很多，主要是基于任务的开始截止时间和任务紧急/松弛程度的任务优先级调度算法，通常的优先级调度算法不能满足实时系统的调度实时性要求而不适用。
13．为什么说多级反馈队列调度算法能较好地满足各方面用户的需求？
答：（1）终端型作业用户提交的作业大多属于较小的交互型作业，系统只要使这些作业在第一队列规定的时间片内完成，终端作业用户就会感到满足。

（2）短批处理作业用户，开始时像终端型作业一样，如果在第一队列中执行一个时间片段即可完成，便可获得与终端作业一样的响应时间。对于稍长作业，通常只需在第二和第三队列各执行一时间片即可完成，其周转时间仍然较短。

（3）长批处理作业，它将依次在第1，2，…，n个队列中运行，然后再按轮转方式运行，用户不必担心其作业长期得不到处理。所以，多级反馈队列调度算法能满足多用户需求。
14．为什么在实时系统中，要求系统（尤其是CPU）具有较强的处理能力？
答：实时系统中通常有着多个实时任务。若处理机的处理能力不够强，有可能因为处理机忙不过来而使某些实时任务得不到及时处理，导致发生难以预料的后果。
15．按照调度方式可将实时调度算法分为哪几种？
答：可分为非抢占式和抢占式两种算法。而非抢占式算法又分为非抢占式轮转和优先调度算法；抢占式调度算法又分为基于时钟中断的抢占式优先权和立即抢占式优先权调度算法。
16．什么是最早截止时间优先调度算法？举例说明。
答：根据任务的开始截止时间确定的任务优先级调度算法。截止时间越早则优先级越高。该算法要求在系统中保持一个实时任务就绪队列，该队列按各任务截止时间的先后排序。
举例：非抢占式调度方式用于非周期实时任务。图3-9是将该算法用于非抢占调度方式之例。该例中具有四个非周期任务，它们先后到达。系统首先调度任务1执行，在任务1执行期间，任务2、3又先后到达。由于任务3的开始截止时间早于任务2，故系统在任务1后将调度任务3执行。在此期间又到达作业4，其开始截止时间仍是早于任务2的，故在任务3执行完后，系统又调度任务4执行，最后才调度任务2执行。
图3-9 EDF算法用于非抢占调度的调度方式
17．什么是最低松弛度优先调度算法？举例说明之。
答：该算法是根据任务紧急(或松弛)的程度，来确定任务的优先级。任务的紧急程度愈高，为该任务所赋予的优先级就愈高，以使之优先执行。例如，一个任务在200 ms 时必须完成，而它本身所需的运行时间就有100 ms，因此，调度程序必须在100 ms 之前调度执行，该任务的紧急程度(松弛程度)为100 ms。又如，另一任务在400 ms 时必须完成，它本身需要运行 150 ms，则其松弛程度为 250 ms。
18．何谓死锁？产生死锁的原因和必要条件是什么？
答：死锁是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。产生死锁的原因为竞争资源和进程间推进顺序非法。其必要条件是：互斥条件、请求和保持条件、不剥夺条件、环路等待条件。
19．在解决死锁问题的几个方法中，哪种方法最易于实现？哪种方法使资源利用率最高？
答：解决死锁的四种方法即预防、避免、检测和解除死锁中，预防死锁最容易实现；避免死锁使资源的利用率最高。
20．请详细说明可通过哪些途径预防死锁。
答：（1）摈弃“请求和保持”条件，就是如果系统有足够资源，便一次性把进程需要的所有资源分配给它；
（2）摈弃“不剥夺”条件，就是已经拥有资源的进程，当它提出新资源请求而不能立即满足时，必须释放它已保持的所有资源，待以后需要时再重新申请；
（3）摈弃“环路等待”条件，就是将所有资源按类型排序标号，所有进程对资源的请求必须严格按序号递增的次序提出。
21．在银行家算法的例子中，如果P0发出请求向量由Request(0,2,0)改为Request(0,1,0)，问系统可否将资源分配给它？(此答案有点问题，需重新考虑)
答：（1）可以。银行家算法各种资源数量分别为10、5、7，在T0时刻的资源分配如图所示：
（2）具体分析如下：
① Requst0(0,1,0)<=Need0(7,4,3);
②Requst0(0,1,0)<=Available(2,3,0);
系统先假定可为P0分配资源，并修改Available0，Allocation0和Need0向量，由此形成
的资源变化情况如下图所示：
（3）P0请求资源：P0发出请求向量Requst0(0,1,0),系统按银行家算法进行检查：
① Requst0(0,1,0)<=Need0(7,4,3);
②Requst0(0,1,0)<=Available(2,3,0);
③ 系统暂时先假定可为P0分配资源，并修改______________有关数据，如下图所示
综上所述系统可以将资源分配给它。
22．银行家算法中出现以下资源分配，试问（1）该状态是否安全？（2）若进程P2提出Request(1,2,2,2)后，系统能否将资源分配给它？
试问： （1）该状态是否安全？

（2）若进程P2提出请求Request（1,2,2,2）后，系统能否将资源分配给它？(参考答案有错)
答： （1）安全，因为存在安全序列{P0,P3,P4,P1,P2}
（2）系统能分配资源，分析如下。
① Request(1,2,2,2) <=Need2(2,3,5,6);
② Request(1,2,2,2) <=Available2(1,3,5,4)改成Available2(1,6,2,2)；
③系统先假定可为P2分配资源，并修改Available2，Allocation2和Need2向量，
由此形成的资源变化情况如下图所示：
④ 再利用安全性算法检查此时系统是否安全。如下图
由此进行的安全性检查得知，可以找到一个安全序列{P2,P0,P1,P3,P4}。

整理不易，如有帮助请点赞支持！谢谢！关注我，让你学到更多软件工程知识！

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

高级调度的主要任务是根据某种算法，把外存上处于后备队列中的那些作业调入内存。

低级调度是保存处理机的现场信息，按某种算法先取进程，再把处理器分配给进程。

引入中级调度的主要目的是为了提高内存利用率和系统吞吐量。使那些暂时不能运行的进程不再占用内存资源，将他们调至外存等待，把进程状态改为就绪驻外存状态或挂起状态。

2.在选择调度方式和调度算法时，应遵循的准则是什么？

①面向用户的准则：周转时间短、响应时间快、截止时间的保证、优先权准则。

②面向系统的准则：系统吞吐量高，处理机利用率好、各类资源的平衡利用。

3.试比较FCFS和SJF两种进程调度算法。

相同点：两种调度算法都可以用于作业的调度和进程的调度。

不同点：FCFS调度算法每次都从后备队列中选择一个或多个最先进入该队列的作业，将它们调入内存、分配资源、创建进程、插入到就绪队列。该算法有利于长作业进程，不利于短作业进程。

SJF算法每次调度都从后备队列中选择一个或若干个估计运行时间最短的作业，调入内存中运行。该算法有利于短作业进程，不利于长作业进程。

4.何谓死锁？产生死锁的原因和必要条件是什么？

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

产生死锁的原因为竞争资源和进程间推进顺序非法。其必要条件是：互斥条件、请求和保持条件、不可抢占条件、循环等待条件。

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

解决死锁的四种方法即预防、避免、检测和解除。

预防死锁最容易实现；避免死锁使资源的利用率最高。

6.在银行家算法的例子中，如果P0发出的请求向量由Request(0,2,0)改为Request(0,1,0)，问系统可否将资源分配给它？

能。P0发出请求向量Request0(0,1,0)，按银行家算法进行检查：

①Request0(0,1,0)≤Need0(7,4,3)

②Request0(0,1,0)≤Available(2,3,0)

③系统暂时先假定可为P0分配资源，并修改有关数据

Available0=Available0(2,3,0)-Request0(0,1,0)=(2,2,0)

Allocation0=Allocation0(0,1,0)+Request0(0,1,0)=(0,2,0)

Need0=Need0(7,4,3)-Request(0,1,0)=(7,3,3)

④利用安全性算法检查此时系统是否安全




进程
Work A B C
Need A B C
Allocation A B C
Work+Allocation A B C
Finish




P1
2 2 0
0 2 0
3 0 2
5 2 2
true


P3
5 2 2
0 1 1
2 1 1
7 3 3
true


P0
7 3 3
7 3 3
0 2 0
7 5 3
true


P2
7 5 3
6 0 0
3 0 2
10 5 5
true


P4
10 5 5
0 0 2
4 3 1
10 5 7
true


又安全性检查得知，可以找到一个安全序列{P1,P3,P0,P2,P4}，所以系统是安全的，系统可以立即将P1所申请的资源(0,1,0)分配给它。

7.在银行家算法中，若出现下述资源分配情况，试问：（该题网上部分答案有错）




Process
Allocation
Need
Available




P0
0032
0012
1622


P1
1000
1750



P2
1354
2356



P3
0332
0652



P4
0014
0656



（1）该状态是否安全？

（2）若进程P2提出请求Request(1,2,2)后，系统能否将资源分配给它？

（1）该状态时安全的，因为存在一个安全序列{P0,P3,P4,P1,P2}，下表为该时刻的安全序列表。




Process
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)后，系统不能将资源分配给它，因为如果分配给进程P2，系统还剩的资源情况为(0,4,0,0)，此时系统中的资源将无法满足任何一个进程的资源请求，从而导致系统进入不安全状态，容易引起死锁的发生。