操作系统第四章处理机调度.docx
《操作系统第四章处理机调度.docx》由会员分享，可在线阅读，更多相关《操作系统第四章处理机调度.docx（27页珍藏版）》请在冰点文库上搜索。
操作系统第四章处理机调度
第四章处理机调度
一选择最合适的答案
1．某系统采用了银行家算法，则下列叙述正确的是（）。
A.系统处于不安全状态时一定会发生死锁
B.系统处于不安全状态时可能会发生死锁
C.系统处于安全状态时可能会发生死锁
D.系统处于安全状态时一定会发生死锁
2．银行家算法中的数据结构包括有可利用资源向量Available、最大需求矩阵Max、分配矩阵Allocation、需求矩阵Need，下列选项正确的是（）。
A.Max[i,j]=Allocation[i,j]+Need[i,j]
B.Need[i,j]=Allocation[i,j]+Max[i,j]
C.Max[i,j]=Available[i,j]+Need[i,j]
D.Need[i,j]=Available[i,j]+Max[i,j]
3．下列进程调度算法中，（）可能会出现进程长期得不到调度的情况。
A.非抢占式静态优先权法
B.抢占式静态优先权法
C.时间片轮转调度算法
D.非抢占式动态优先权法
4．在下列选项中，属于预防死锁的方法是（）。
A.剥夺资源法B.资源分配图简化法
C.资源随意分配D.银行家算法
5．在下列选项中，属于检测死锁的方法是（）。
A.银行家算法B.消进程法
C.资源静态分配法D.资源分配图简化法
6．在下列选项中，属于解除死锁的方法是（）。
A．剥夺资源法B.资源分配图简化法
C．银行家算法D.资源静态分配法
7．为了照顾紧迫型作业，应采用（）。
A.先来服务调度算法B.短作业优先调度算法
C.时间片轮转调度算法D.优先权调度算法
8．在采用动态优先权的优先权调度算法中，如果所有进程都具有相同优先权初值，则此时的优先权调度算法实际上和（）相同。
A.先来先服务调度算法B.短作业优先调度算法
C.时间片轮转调度算法D.长作业优先调度算法
9．作业从后备作业到被调度程序选中的时间称为（）。
A.周转时间B.响应时间
C.等待调度时间D.运行时间
10．资源静态分配法可以预防死锁的发生，它们使死锁四个条件中的（）不成立。
A.互斥条件B.请求和保持条件
C.不可剥夺条件D.环路等待条件
二选择所有正确答案
1．下列选项中，（）可能是非抢占方式进程调度中引起调度的原因。
A.当前的运行进程调用阻塞原语而进入阻塞状态
B.当前的运行进程提出申请I/O而阻塞
C.有更高优先级的进程到达而从执行状态变为就绪状态
D.正在执行的进程执行了P原语操作，由于资源不足而阻塞
2．选择排队作业中等待时间最长的作业被优先调度，该调度算法不可能是（）。
A.先来先服务调度算法B.高响应比优先调度算法
C.优先权调度算法D.短作业优先调度算法
3．作业控制块JCB连成一串而形成的一个排队队列，该队列称为（）。
A挂起队列B.阻塞队列
C.就绪队列D.后备队列
4．下列哪个选项描述的时间属于响应时间的一部分（）。
A.处理机对请求信息进行处理的时间
B.从键盘输入的请求信息传送到处理机的时间
C.所形成的响应回送到终端显示器的时间
D.用户查看响应回送到的信息
5．下列四个选项描述的时间组成了周转时间，其中可能发生多次的是（）。
A.等待I/O操作完成的时间
B.作业在外存后备队列上等待作业调度的时间
C.进程在CPU上的执行时间
D.进程在就绪队列上等待进程调度的时间
6．下面列出的是选择调度方式和算法的4个面向用户的准则。
其中，不完全适用于实时系统的准则是（）。
A.优先权准则B.响应时间快
C.截止时间的保证D.周转时间短
7．下面列出了选择调度方式和算法的4个准则。
其中，对批处理、分时、实时系统都可以采用的是（）。
A.周转时间短B.响应时间快
C.截止时间的保证D.优先权准则
8．下列选项中，（）是分时系统中确定时间片大小需要考虑的因素。
A.各类资源的平衡利用B.就绪队列中进程的数目
C.系统的处理能力D.系统对响应时间的要求
9．下面列出的选项中，属于可剥夺性资源的有（）。
A.CPUB.内存
C.磁盘D.磁带机
10．在多级队列调度和多级反馈队列调度的叙述中，正确的是（）。
A.多级反馈队列调度中就绪队列的设置不是象多级队列调度一样按作业性质划分，而是按时间片的大小划分
B.多级队列调度用到优先权，而多级反馈队列调度中没有用到优先权
C.多级队列调度中的进程固定在某一个队列中，而多级反馈队列调度中的进程不固定
D.多级队列调度中每个队列按作业性质不同而采用不同的调度算法，而多级反馈队列调度中除了个别队列外，均采用相同的调度算法
三判断正误，简要说明理由
1．作业调度能够使作业获得CPU。
2．在多道程序系统中，系统的现有空闲可用资源能否满足一个后备作业J的资源要求，是选择作业J进入内存的必要条件。
3．短作业（进程）优先调度算法具有最短的平均周转时间，因此这种算法是最好的算法。
4．在优先权调度算法中确定静态优先权时，一般说，计算进程的优先权要高于磁盘I/O进程的优先权。
5．摒弃不可剥夺条件的方法可用于预防多个打印进程死锁的发生。
6．操作系统处理死锁，只要采用预防、解除、检测、避免之中的一种就足够了。
7．如果系统在所有进程运行前，一次性地将其在整个运行过程所需的全部资源分配给进程，即所谓“静态分配”法，是可以预防死锁发生的。
8．多个进程竞争比进程数目少的资源时就可能产生死锁，而当资源数目大于进程数目时就一定不会发生死锁。
9．在银行家算法中，对某时刻的资源分配情况进行安全分析，如果该时刻状态是安全的，则存在一个安全序列，且这个安全序列是唯一的。
10．进程调度算法各种各样，但是如果选择不当，就会造成死锁。
四简答题
1．高级调度和低级调度的主要任务是什么？
为什么要引入中级调度？
2．在作业调度中需作出哪些决定？
3．在剥夺调度中，有哪些剥夺原则？
4．在OS中引起进程调度的主要因素有哪些？
5．在选择调度方式和调度算法时，应遵循的原则是什么？
6．在批处理系统、分时系统和实时系统中，各采用哪几个进程（作业）调度算法？
7．为什么说多级反馈队列能较好地满足各种用户的需要？
8．在多用户分时系统中，时间片轮转调度的算法在确定时间片的大小时，应考虑哪些因素？
9．为实现实时调度，对实时系统提出了哪些要求？
10．目前常用的调度方式和算法，能否应用到实时系统中？
11．在多处理机系统中，比较有代表性的线程调度方式有哪几种？
12．试比较自调度和成组调度？
13．在OS/2中采用哪种调度方式和调度算法？
14．何为死锁？
产生死锁的原因和必要条件是什么？
15．在解决死锁问题的几个方法中，哪种方法最容易实现？
哪种方法使资源的利用率最高？
16．请详细说明可通过哪些途径预防死锁？
17．在银行家算法的例子中，如果P0发出的请求向量由Request0（0,2,0）改为Request0（0,1,0），问系统可否将资源分配给它？
习题解答要点
一选择最合适的答案
1.B2.B3.B4.D5.D6.A7.D8.A9.C10.B
二选择所有正确答案
1.ABD2.BCD3.D4.ABC5.ACD
6.AD7.D8.BCD9.ABC10.ACD
三判断题
1.错误
作业调度是高级调度。
它只能使某作业获得使用CPU的资格。
而只有进程调度或线程调度才能使作业真正获得CPU。
2.错误
多道系统中的资源分配有两种方法：
静态分配：
作业调度的功能之一是审查系统能否满足用户作业的资源要求；之二是按照一定的算法选取作业。
动态分配：
进程所需的资源是在运行中分配的，作业调度并不考虑当前空闲的资源量，只是按照一定的算法选取作业。
3.错误
前半句话讲的正确，但由此说短作业（进程）优先调度算法是最好的，就不正确了。
因为一个算法的好坏要看其是否适于系统的需要而判定。
4.错误
因为磁盘I/O进程属于系统进程。
而系统在确定进程的静态优先权时遵循的原则是：
系统进程的优先权高于一般用户进程的优先权（除非用户的进程特别紧迫或重要）
5.错误
因为摒弃不剥夺条件的方法可预防死锁的发生。
6.错误
因为，操作系统要兼顾资源的使用效率和安全性两个方面，常见的是，将预防、解除、检测、避免四种处理混合起来使用。
举例来说，只有检测死锁而无解除死锁，检测出死锁又有什么用呢？
7.正确
因为资源的“静态分配”方法，可以摒弃“请求和保持”条件，是可以预防死锁的。
8.错误
进程是否发生死锁，需要考虑每个进程申请资源的数目、所申请资源的种类、进程推进情况等因素。
不能简单地比较进程数目和资源数目就来确定是否死锁。
9.错误
系统在调用银行家算法进行安全检查时，只要找到一个安全序列就可断定系统是安全的。
但安全序列可能不止一个，有的情况下可能是只有一个，有的情况下可能有2个或者更多。
10.错误
如果进程调度算法选择不当，会造成某些进程的长期等待。
我们将这种进程称为“饥饿”进程（长期“饥饿”的极端情况是“饿死”）。
“饿死”和“死锁”具有完全不同的含义。
四简答题
1．高级调度和低级调度的主要任务以及引入中级调度原因如下：
高级调度又称为作业调度。
它是批处理系统中使用的一种调度。
其主要任务是，按照某种算法从外存的后备队列上选择一个或多个作业调入内存，并为它们创建进程、分配必要的资源，然后再将创建的进程控制块挂入就绪队列上。
低级调度又称进程调度。
它是距离硬件最近的一级调度。
其主要任务是，按照某种算法从就绪队列上选择一个（或多个）进程，使其获得CPU。
引入中级调度的目的是为了提高内存利用率和系统吞吐量。
其功能是，让那些暂时不能运行的进程不再占用宝贵的内存资源，而是调出到外存上等待。
此时的进程状态为挂起状态。
当这些进程重新具备运行条件且内存空闲时，由中级调度选择一部分挂起状态的进程调入内存，将其状态变为内存就绪状态。
2．在作业调度中需作出的决定如下：
作业调度需要按照多道程序度（即，最大道数）决定一次接纳多少作业进入内存。
如果太少将导致系统资源利用率低，且系统吞吐量低；太多将导致内存空间紧张，系统服务质量下降，使作业运行周期过长。
作业调度需要决定接纳哪些作业进入内存。
常用的算法是，先来先服务，短作业优先，最高优先级调度、响应比高者优先等。
3．在剥夺进程调度中，剥夺原则如下：
时间片原则。
在轮转算法中，CPU轮流为诸多进程服务，每个进程运行完自己的时间片后，系统就将它的CPU剥夺过来，交给下一个进程使用。
优先级原则。
为紧迫的作业赋予较高的优先级，这种作业到达系统，或者由阻塞状态被唤醒后，若其优先级高于当前运行的进程的优先级，可以剥夺其CPU。
短作业（进程）优先原则。
若一个作业（进程）到达系统，其运行长度比当前运行的进程长度明显的短，则剥夺它的CPU。
4．引起进程调度的主要因素主要有：
一个进程运行完毕；
一个正在运行的进程被阻塞；
在抢占式调度中，一个高优先级的进程被创建；
在抢占式调度中，一个高优先级进程由阻塞被唤醒；
在轮转式调度中，正在运行的进程运行完一个时间片。
5．在选择调度方式和调度算法时，应遵循的原则如下：
面向用户准则。
首先，对于用户的紧迫性作业，系统能够及时地处理，不至于运行延误。
其次，对于批处理系统，还应追求作业的周转时间短；分时系统中作业的响应时间块；实时系统中作业的截止时间有保证。
面向系统准则。
系统的吞吐量高，处理机的利用率高，各类系统资源能够得到平衡利用。
6．批处理系统、分时系统和实时系统中的主要调度算法如下：
批处理系统中的作业调度算法有先来先服务（FCFS）、短作业优先（SJF）、优先级调度（HPF）和高响应比优先（RF）。
批处理系统的进程调度算法有：
先进先出（FIFO）、短进程优先（SPF）、优先级调度（PRI）和高响应比优先（RF）。
分时系统中只设有进程调度（不设作业调度），其进程调度算法只有轮转法（RR）一种。
实时系统中只设有进程调度（不设作业调度），其进程调度算法有：
轮转法、优先级调度算法。
前者适用于时间要求不严格的实时系统；后者用于时间要求不严格的实时系统。
后者又可细分为：
非抢占式优先级调度、抢占式优先级调度、基于时钟中断的抢占式优先级调度。
注意，一个纯粹的实时系统是针对特定应用领域设计的专用系统。
作业提交的数量不会超过系统规定的多道程序度，因而可全部进入内存。
若将实时系统与批处理系统结合的话，就可以让作业量超过多道程序度，使优先级低的作业呆在外存的后备队列上。
7．多级反馈队列能较好地满足各种用户的需要的原因：
终端用户的作业一般比较短小精悍，大多数在进入多级队列的第一级队列中后运行一个时间片就可以完成，因而感到满意。
批处理作业用户，其作业进入多级队列的第一级队列中后，若作业较短，运行一个时间片就可以完成。
对于稍长一些的作业，只需在第二或第三队列上各执行一个时间片就可完成，因而感到满意。
对于长作业来说，它将依次在第1，2，…，n个队列上运行，不会因作业太长而长期得不到处理。
8．在多用户分时时间片长度的选择上，既要保证交互性，又要保证系统的效率。
系统对响应时间T的要求（一般应小于等于2~3秒钟）；
就绪队列中的进程数目N（N与终端上的用户数目有关）；
系统的处理能力，一个时间片的长度q应能保证用户的大部分常用命令可处理完；
进程的转换时间p；
三者的关系可表示为：
T=N（q+p）。
9．对实时系统提出了要求如下：
任务要提供必要的调度信息：
主要包括：
开工的最后期限或完工的最后期限、处理时间长度、优先级、就绪时间，以及资源需求。
采用适当的调度方式：
如果实时任务的运行长度较长且时间要求严格，那么实时系统应采用抢占式调度；如果所有的实时任务都比较小，且预知任务的开工最后期限，也可以采用非剥夺式调度。
能够快速响应外部中断：
这要求，硬件上要有较高的中断机制，软件上要使“封中”的时间间隔尽量短，以免贻误时机。
快速的任务分派能力：
尽量减少任务切换时间开销，使得一个任务完成后可以较快地切换到下一个任务去。
10．抢占方式和非抢占方式都可以用于实时系统中。
能够使用的算法有：
轮转算法（RR）和优先级调度算法（HPF）；不可以使用的算法有：
先进先出（FIFO）和短进程优先算法（SPF）。
11．在多处理机系统中，有代表性的线程调度方式有：
自调度方式：
诸多CPU可以共享同一就绪队列，从中获取就绪线程运行。
成组调度方式：
由系统将若干相关的线程同时分配到多台CPU上运行。
线程与CPU一一对应。
专用处理机分配方式：
将若干同属于一个应用程序的线程分配到一组CPU上。
让这组CPU专门处理它们。
12．调度方式的比较如下：
自调度方式中，就绪队列与单机的相同，调度算法也与之相同。
系统没有集中调度机制，任何CPU都可调用系统的调度例程去选择一个线程。
只要就绪队列不空，就不会有空闲的CPU。
它存在的问题是，多CPU共享一个就绪队列将产生瓶颈；各线程在其生命周期中可能要换好几台CPU，每次更换都要将CPU中的高速缓存（Cache）重新拷入现场数据，造成效率低下；由于合作的一组线程很难同时获得CPU，一些运行的线程只好阻塞等待未获得CPU的线程，所以线程切换频繁。
成组调度中，合作的各线程可以同时获得CPU，减少因同步造成的阻塞，减少了切换次数。
同时，也可减少调度的频率。
13．多优先级的抢占式调度，调度的基本单位是线程。
优先级分为3类：
每一类共细分32级，以31级为最高级。
其中：
时间紧迫类为最高类，对应的是实时线程及通信管理等；常规类为中档优先类，对应的是一般线程；空闲时间类为较低类，对应的是紧迫度低的线程。
调度算法：
在同一类的同一优先级中采用轮转算法。
每当运行完一个时间片就检查是否有更高优先级线程到来，若有便抢占CPU。
14．
死锁是指多个进程因竞争资源而造成的一种僵持状态。
若无外力作用，这些进程都将永远处于阻塞状态，不能再运行下去。
产生死锁的原因有：
资源不足资源、进程推进次序不当。
产生死锁的必要条件有：
互斥条件、请求和保持条件、不可剥夺条件、环路等待条件。
15．
预防死锁方法，主要是破坏产生死锁的必要条件。
该方法是最容易实现的，但系统资源利用率较低。
避免死锁方法，比较实用的有银行家算法（BankerAlgorithm）。
该算法需要较多的数据结构，实现起来比较困难，但资源利用率最高。
（3）检测死锁方法是基于死锁定理设计的，定期运行该算法对系统的状态进行检测，发现死锁便予以解除。
其中，需要比较一下各种死锁解除方案的代价，找到代价最小的方案。
该方法最难实现，资源利用率较高。
16．预防死锁方法是破坏产生死锁的必要条件，主要有：
摈弃请求和保持条件。
采用静态分配方案，一次性地分配给进程所请求的全部资源。
进程运行过程中不可再请求新资源。
摈弃不剥夺条件。
采用动态分配方案，进程运行中可以请求新资源。
若进程请求资源不能满足时，就应使其释放已占有的资源。
摈弃环路等待条件。
采用动态分配方案，要求进程请求资源时，按资源序号递增（或递减）顺序提出。
17．系统的资源数量为：
（10，5，7）。
经过一段时间的分配后，资源分配与占用情况见下表所示。
进程
MAXABC
AllocationABC
NeedABC
AvailableABC
P0
753
010
743
332
P1
322
200
122
P2
902
302
600
P3
222
211
011
P4
433
002
431
Request1（1,0,2）：
P1请求满足后的占用情况如下。
进程
MAXABC
AllocationABC
NeedABC
AvailableABC
P0
753
010
743
230
P1
322
302
020
P2
902
302
600
P3
222
211
011
P4
433
002
431
（2）检测系统此刻存在一条安全序列{P1，P3，P4，P0，P2}。
检测过程为：
资源可用量（230），不能满足P0，可满足P1。
资源可用量（532），不能满足P2，可满足P3。
资源可用量（743），可满足P4。
资源可用量（745），可满足P0。
资源可用量（755），可满足P2。
待其完成后使系统的资源可用量达到初始值（10，5，7）。
（3）Request4（3,3,0）：
P4的请求超过系统当前的可用量（2,3,0），应推迟分配。
（4）Request0（0,1,0）：
P0请求满足后的占用情况如下：
进程
MAXABC
AllocationABC
NeedABC
AvailableABC
P0
753
020
733
220
P1
322
302
020
P2
902
302
600
P3
222
211
011
P4
433
002
431
检测系统此刻存在安全序列{P1，P3，P4，P0，P2}。
资源可用量（220），不能满足P0，可满足P1。
资源可用量（522），不能满足P2，可满足P3。
资源可用量（733），可满足P4。
资源可用量（735），可满足P0。
资源可用量（755），可满足P2。
待其完成后使系统的资源可用量达到初始值（10，5，7）。
FCFS
运行时间等待时间周转时间
1：
12001201
2：
601001602.67
3：
301401705.67
4：
1816017810
SJF
运行时间等待时间周转时间
11200120
4187088
33098128
260148208
五考研试题精选及解析
1.在银行家算法中，若出现以下资源分配情况：
（北京理工2002死锁题）
Process
allocation
claim
available
ABC
ABC
ABC
P0
010
753
322
P1
210
322
P2
302
902
P3
211
222
P4
002
433
问：
1该状态是否安全?
2若进程依次有以下资源请求：
p1资源请求：
Request（1,0,2）
p4资源请求：
Request（3,3,0）
p0资源请求：
Request（0,1,0）
则系统如何分配资源可避免死锁?
答：
（1）资源分配情况为：
资源
进程
currentavil
Cki-Aki
allocation
currentavil+allocation
possible
A
B
C
A
B
C
A
B
C
A
B
C
P1
3
2
2
1
1
2
2
1
0
5
3
2
TRUE
P3
5
3
2
0
1
1
2
1
1
7
4
3
TRUE
P0
7
4
3
7
4
3
0
1
0
7
5
3
TRUE
P2
7
5
3
6
0
0
3
0
2
10
5
5
TRUE
P4
10
5
5
4
3
1
0
0
2
10
5
7
TRUE
可见存在一个安全序列{P1,P3,P0,P2,P4}，故为安全状态。
（2）只需考虑进程P1和P0的资源申请。
现在假定进程P1又要申请1个A类资源和2个C类资源，为了判别这个申请能否立即准许，按银行家算法进行检查：
●request1（1,0,2）≤Ck1-Ak1（1,1,2）
●request1（1,0,2）≤Available（3,2,2）
此时，系统可用资源向量为（2,2,0）。
进程p0的资源请求为Request（0,1,0），按银行家算法进行检查：
●request1（0,1,0）≤Ck1-Ak1（7,4,3）
●request1（0,1,0）≤Available（2,2,0）
试分配并修改数据结构，
process
allocation
Cki-Aki
available
ABC
ABC
ABC
P0
020
733
210
P1
312
010
P2
302
600
P3
211
011
P4
002
431
再用安全性算法检查：
资源
进程
currentavil
Cki-Aki
allocation
currentavil+al
升级会员 