一、章节习题
1、在分时系统中,进程调度经常采用______算法。
A 先来先服务 B 最大优先权 C 时间片轮转 D 随机
2、进程调度有各种各样的算法,如果算法处理不当,就会出现____现象。
A 颠簸(抖动) B 饥饿 C 死锁 (竞争资源) D Belady(异常)
3、下列____进程调度算法会引起进程的饥饿问题。
A 先来先服务 B 时间片轮转 C 优先级 D 多级反馈队列
4、在进程调度中,最有利于提高资源的使用率、能使短作业、长作业及交互作业用户都比较满意的调度算法是_______.
A FCFS调度算法 B 短作业优先调度算法
C 时间片轮转法 D 多级反馈队列调度算法
5、进程调度又称低级调度,其主要功能是________.
A 选择一个作业调入内存 B 选择一个主存中的进程调出到外存
C 选择一个外存中的进程调入内存 D 将一个就绪的进程投入运行
6、若进程P一旦被唤醒就能够投入运行,系统可能为______
A 分时系统,进程P的优先权最高
B 抢占调度方式,就绪队列上的所有进程的优先级皆比P的低
C 就绪队列为空队列
D 抢占调度方式,P的优先级高于当前运行的进程
7、_____优先权是在创建进程时确定的,确定之后在整个进程的运行时间不再改变
A 先来先服务 B 静态 C 动态 D 短作业
8、一个进程P被唤醒后,_____
A P就占有了CPU B P的PCB被移到就绪队列的队首
C P的优先级肯定最高 D P的状态变成就绪
9、三种主要类型的操作系统中都必须配置的调度是_________.
A 作业调度 B 中级调度 C 低级调度 D I/O调度
10、在分时操作系统环境下运行的作业为_____
A 长作业 B 短作业 C 批处理型作业 D 终端型作业
11、设有4个作业同时到达,每个作业执行的时间均为1小时,它们在一台处理机上按单道方式运行,则平均周转时间为_______
A 1小时 B 4小时 C 2.5小时 D 10小时
(1+2+3+4)/4=2.5
12、选择作业调度算法时常考虑的因素之一是使系统有最高的吞吐率,为此应该_____
A 不让处理机空闲 B 处理尽可能多的作业
C 使各类用户都满意 D 不使系统过于复杂
13、当作业进入完成状态,操作系统_____
A 将删除该作业并回收其占有资源,同时输出结果
B 将该作业的控制块从当前作业队列中删除,收回其所占资源,并输出结果
C 将收回该作业所占资源并输出结果
D 将结果输出并删除内存中的作业
14、现有3个同时到达的作业J1,J2,J3,它们的执行时间分别是T1,T2,T3,且T1>T2>T3.系统按单道方式运行且采用短作业优先算法,则平均周转时间是____
A T1+T2+T3 B (T1+T2+T3)/3 C(3T1+2T2+T3)/3 D (T1+2T2+3T3)/3
15、在进程调度中,若采用优先级调度算法,为了尽可能使CPU和外部设备并行工作,有如下三个作业:J1以计算为主,J2以输入输出为主,J3以计算和输入输出兼顾,则它们的优先级从高到低的排列顺序是_________。
A J1,J2,J3 B J2,J3,J1 C J3,J2,J1 D J2,J1,J3
解析:本题将作业分为I/O繁忙的作业,CPU繁忙的作业,I/O与CPU均衡的作业三种类型,由系统和管理员根据作业类型指定优先级。(个人认为是提高 以I/O为主的进程优先级。因为I/O为主的进程不会占用太多CPU时间,就会去做I/O的操作,就可以释放CPU了。这样可以让I/O设备和CPU并行执行,提高进程并行度,不就提高了效率)
16、关于优先权大小的论述中,正确的论述是________.
A 计算型进程的优先权,应高于I/O型进程的优先权
B 用户进程的优先权,应高于系统进程的优先权、
C 资源要求多的进程,其优先权应高于资源要求少的进程
D 在动态优先权中,随着进程执行时间的增加,其优先权降低
一般来说,I/O型作业的优先权是高于计算型作业的优先权,这是由于I/O操作需要及时完成,它没有办法长时间保存所要输入/输出的数据,而系统进程的优先权应高于用户进程的优先权。作业的优先权与长作业、短作业或者是系统资源要求的多少没有必然的关系。在动态优先权中,随着进程执行时间的增加其优先权随之降低,随着作业等待时间的增加其优先权应上升。
17、采用按序分配资源的策略可以预防死锁,这是利用了哪个条件不成立?________。
A 互斥 B 循环等待 C 不可抢占 D 占有并等待
解析:在采用这种策略时,总有一个进程占据了较高序号的资源,它继续请求的资源必然是空闲的,因而进程可以一直向前推进。
预防死锁的方法:
资源一次性分配:破坏“请求与保持”条件;
可剥夺资源:破坏“不可剥夺”条件;
资源有序分配:破坏“循环等待”条件;
18、假设系统有相同类型的9个资源被4个进程共享,试分析每个进程最多可以请求多少个资源数时该系统仍无死锁?________
A 1 B 2 C 3 D 4
对于系统中有n个并发进程共享使用m个同类资源时,若每个进程需要的最大资源数量为x,仅当m、n、x满足如下的不等式时,才能保证系统处于安全状态:
已知m和n时,得到x的解:
19、某系统有3个并发程序,都需要同类资源4个,试问该系统不会发生死锁的最少资源数是__________
A 4 B 8 C 10 D 12
3*(4-1)+1=10 也就是n等于3,每个进程需要最大资源数量为4,求共享使用的资源数量,和上一题刚好相反,上一题求每个进程需要的资源数量,这题求共所有进程需要多少资源数量
20、在多道程序所提供的可共享的系统资源不足时,可能出现死锁,但是,不适当的________也可能产生死锁
A 进程推进顺序 B 进程优先权 C 资源的顺序分配 D 程序并发
死锁产生:
1.竞争不可抢占资源 2.竞争可消耗资源 3.进程推进顺序不当
21、 假定某系统中有同类互斥资源m个,可并发执行且共享该类资源的进程有n个,而每个进程申请资源的最大量为x(n≤x≤m),当不等式_____成立时,系统一定不会 发生死锁。
A nx+1≤m B nx≤m C m(x-1)+1≤n D m-nx+n-1≥0同18题公式
22、采用资源剥夺法可以解除死锁,还可以用_________方法解除死锁
A 执行并行操作 B 撤销进程 C 拒绝分配资源 D 修改信号量
死锁的解除:
1.抢占资源(资源剥夺法) 2.终止(撤销)进程
23、 发生死锁的必要条件有4个,其中防止死锁破坏_____条件是不太实际的
A 互斥 B 不剥夺 C 部分分配 D 环路
24、在下列解决死锁的方法中,属于死锁预防策略的是_____(总结在文章末尾)
A 银行家算法(避免死锁) B 资源有序分配法 C 死锁检测法 D 资源分配图化简法(检测死锁)
25、某系统采用了银行家算法,则下列叙述正确的是______
A 系统处于不安全状态时一定会发生死锁
B 系统处于不安全状态时可能发生死锁
C 系统处于安全状态时可能会发生死锁
D 系统处于安全状态时一定会发生死锁
26、银行家算法的实质是_______
A 死锁避免 B 死锁预防 C 死锁检测 D死锁恢复
27、在多进程的并发系统中,肯定不会因竞争________而发生死锁
A CPU B 磁带机 C 磁盘 D 打印机
也不会因为主存发生死锁书本113页
28、以下_____情况我们不考虑死锁的发生 ※
A 只有一个进程在系统中运行 B进程申请的资源不存在
C 硬件故障 D 程序死循环
29、关于资源分配图的说法正确的是_____ ※
A 图中无环路,一定不会有死锁发生
B 有环路则必然有死锁发生
C 有环路死锁不一定发生还得看资源占有情况
D 有两个以上的环路死锁必然发生
二、历年真题
1.下列进程调度算法中,综合考虑进程等待时间和执行时间的是________。(2009年计算机科学与技术学科全国硕士研究生入学统一试卷)
A 时间片轮转调度算法 B 短进程优先调度算法
C 先来先服务调度算法 D 高响应比优先调度算法
2.某计算机系统中有8台打印机,由K个进程竞争使用,每个进程最多需要3台打印机。该系统可能发生死锁的K的最小值是________。(2009年计算机科学与技术学科全国硕士研究生入学统一试卷)
A 2 B 3 C 4 D 5
设m为资源数,n为并发进程,k为每个进程需要多个资源,可以列一个式子 m>=(k-1)n+1
8>=(3-1)*K+1 算出K<=3.5是不会发生死锁的,故发生死锁的最小值为4
3.下列选项中,降低进程优先级的合理时机是( )。(2010年计算机科学与技术学科全国硕士研究生入学统一试卷26题)
A. 进程的时间片用完 B. 进程刚完成I/O,进入就绪队列
C. 进程长期处于就绪队列中 D. 进程从就绪状态转为运行态
完成I/O进入就绪队列的进程尚未执行,不能降低其优先级;长期处于就绪队列的进程应提高其优先级;进程刚刚转入运行态,也不应降低其优先级;当进程的时间片用完,调度程序需要调度其他程序进入处理机执行,此时降低进程优先级是合理的。
4.下列选项中,满足短任务优先且不会发生饥饿的调度算法是( )(2011年计算机科学与技术学科全国硕士研究生入学统一试卷23题)
A. 先来先服务 B. 高响应比优先
C. 时间片轮转 D. 非抢占式短任务优先
5.某时刻进程的资源使用情况如下所示。
此时的安全序列是( )。(2011年计算机科学与技术学科全国硕士研究生入学统一试卷27题)
A. P1, P2, P3, P4 B. P1, P3, P2, P4
C. P1, P4, P3, P2 D. 不存在
可以从图表发现A选项P1满足0 0 1<0 2 1,先执行P1后释放资源为2 2 1,但是2 2 1<P2的1 3 2所以A不对,同理B选项到了P3也是不满足也不对;
C选项中到了P3也不对,所以D
这道题最简单的算法就是因为可用资源0 2 1大于P1,P1加入安全序列后,可用资源为0 2 2会发现不满足P2P3P4任何一个,所以肯定不存在安全序列
6.假设5个进程P0、P1、P2、P3、P4共享三类资源R1、R2、R3,这些资源总数分别为18、6、22。T0时刻的资源分配情况如下表所示,此时存在的一个安全序列是( )。(2012年计算机科学与技术学科全国硕士研究生入学统一试卷27题)
A. P0, P1, P2, P3, P4 B. P1, P0, P3, P4, P2
C. P2, P1, P0, P3, P4 D. P3, P4, P2, P1, P0
Need=最大需求-已经分配; Available(还剩下的资源数)=2 2 3
可以发现,A选项中的P0排第一不可能,因为2 3 7 >2 2 3
B选项中的P1 1 3 3<2 2 3,满足先执行P1,然后释放P1的已分配的4 0 3+2 2 3=6 0 6,然后P0 2 3 7 >6 0 6,不满足;
C选项P2 0 0 6>2 2 3不满足。
D选项同理计算会发现满足,是一个安全序列
7.下列关于银行家算法的叙述中,正确的是( )。(2013年计算机科学与技术学科全国硕士研究生入学统一试卷32题)
A. 银行家算法可以预防死锁(避免死锁)
B. 当系统处于安全状态时,系统中一定无死锁进程
C. 当系统处于不安全状态时,系统中一定会出现死锁进程)(不一定)
D. 银行家算法破坏了死锁必要条件中的“请求和保持”条件
银行家算法是避免死锁的方法,并不可以预防死锁,A不正确。并非所有不安全状态都是死锁状态,但当系统进入不安全状态后,便可能进入死锁状态;反之,只要系统处于安全状态,系统便可避免进入死锁状态;死锁状态必定是不安全状态,C不正确。破坏“请求和保持”条件是预防死锁的方法,而银行家算法是避免死锁的方法,D不正确。
8. 下列调度算法中,不可能导致饥饿现象的是( )。(2014年计算机科学与技术学科全国硕士研究生入学统一试卷23题)
A. 时间片轮转 B. 静态优先数调度
C. 非抢占式短作业优先 D. 抢占式短作业优先
9. 某系统有n台互斥使用的同类设备,三个并发进程分别需要3、4、5台设备。可确保系统不发生死锁的设备数n最小为( )。(2014年计算机科学与技术学科全国硕士研究生入学统一试卷24题)
A. 9 B. 10 C. 11 D.12
三个并发进程分别需要3、4、5台设备,当系统只有(3-1)+(4-1)+(5-1)=9台设备时,第一个进程分配2台,第二个进程分配3台,第三个进程分配4台。这种情况下,三个进程均无法继续执行下去,发生死锁。当系统中再增加1台设备,也就是总共10台设备时,这最后1台设备分配给任意一个进程都可以顺利执行完成,因此保证系统不发生死锁的最小设备数为10。即用公式的话就是1*(3-1)+1*(4-1)+1*(5-1)+1=10
10. 若系统S1采用死锁避免方法,S2采用死锁检测方法。下列叙述中,正确的是( )。
(2015年计算机科学与技术学科全国硕士研究生入学统一试卷26题)
Ⅰ. S1会限制用户申请资源的顺序,而S2不会
Ⅱ. S1需要进程运行所需资源总量信息,而S2不需要
Ⅲ. S1不会给可能导致死锁的进程分配资源,而S2会
A. 仅Ⅰ、Ⅱ B. 仅Ⅱ、Ⅲ C.仅Ⅰ、Ⅲ D.Ⅰ、Ⅱ、Ⅲ
注意Ⅰ中说的是限制申请资源的顺序,死锁预防才会限制申请顺序,死锁避免影响的是资源分配的顺序
11. 系统中有3个不同的临界资源R1、R2和R3,被4个进程P1/P2/P3和P4共享。各进程对资源的需求为:P1申请R1和R2,P2申请R2和R3,P3申请R1和R3,P4申请R2。若出现死锁,则处于死锁状态的进程数至少是( )。(2016年计算机科学与技术学科全国硕士研究生入学统一试卷25题)
A.1 B.2 C.3 D.4
对于本题,先满足一个进程的资源需求,再看其他进程是否能出现死锁状态。因为p4只申请一个资源,当将R2分配给p4后,p4执行完后将R2释放,这时使得系统满足死锁的条件是R1分配给p1,R2分配给p2,R3分配给p3(或者R2分配给p1,R3分配给p2,R1分配给p3)。穷举其他情况如p1申请的资源R1和R2,先都分配给p1,运行完并释放占有的资源后,可以分别将R1、R2和R3分配给p3、p4和p2,也满足系统死锁的条件。各种情况需要使得处于死锁状态的进程数至少为3。(也就是说当先满足一个进程然后再释放出去,这是资源仍然不够进程分配,仍然死锁)
12. 下列有关基于时间片的进程调度的叙述中,错误的______。(2017年计算机科学与技术学科全国硕士研究生入学统一试卷27题)
A 时间片越短,进程切换的次数越多,系统开销也越大
B 当前进程的时间片用完后,该进程状态由执行态变为阻塞态
C 时钟中断发生后,系统会修改当前进程在时间片内的剩余时间
D 影响时间片大小的主要因素包括响应时间、系统开销和进程数量等
进程切换带来系统开销,切换次数越多,开销越大,A正确。当前进程的时间片用完后,它的状态由执行态变为就绪态,B错误。时钟中断是系统中特定的周期性时钟节拍。操作系统通过它来确定时间间隔,实现时间的延时和任务的超时,C正确。现代操作系统为了保证性能最优,通常根据响应时间、系统开销、进程数量、进程运行时间、进程切换开销等等因素确定时间片大小,D正确。
13. 假设4个作业到达系统的时刻和运行时间如下表所示:
系统在t=2时开始作业调度。若分别采用先来先服务和短作业优先调度,则选中的作业分别是( )。2017年计算机科学与技术学科全国硕士研究生入学统一试卷23题)
A.J2,J3 B.J1,J4 C.J2,J4 D.J1,J3
先来先服务调度算法是作业来得越早,优先级越高,因此会选择J1。短作业优先调度算法是作业运行时间越短,优先级越高,因此会选择J3。(注意t=2作业调度,J4还没到来)所以D正确。
14.某系统采用基于优先权的非抢占式进程调度策略,完成一次进程调度和进程切换的系统时间开销为1μs。在T时刻就绪队列中有3个进程P1,P2,P3,其在就绪队列中的等待时间、需要的CPU时间和优先权如下表所示。
若优先权值大的进程优先获得CPU,从T时刻起系统开始进程调度,则系统的平均周转时间为( )。(2018年计算机科学与技术学科全国硕士研究生入学统一试卷24题)
A 56μs B 73μs C 74μs D 75μs
P2 :24
P3:24+18+36+1=79
P1:79+30+12+1=122
(24+79+122)/3=75
另外一种:
由优先权可知,p2-p3-p1,其中p2周转为1+15+24=40,p3为18+1+24+1+36=80,p1为30+1+24+1+36+1+12=105,所以(40+80+105)/3=75,选D
详解:
由题目我们可以知道,调度到进程需要1,而一开始三个进程已经全部在队列中
于是p2的周转时间就是队列等待15,然后调度1,cpu运行的24
接下来是p3,其已经在队列中18,此时正在运行p2进程的调度1和cpu运行的24,所以等p2的调度和cpu运行后才到自己,此时自己的调度需要1,cpu运行需要36
最后是p1,和p3的运行一样,需要等待p2和p3的运行,则需要把p2、p3的调度和cpu时间累加再加上自己的调度和cpu时间
15.假设系统中有4个同类资源,进程P1、P2和P3需要的资源数分别为4、3和1,P1、P2和P3已申请到的资源分别为2、1和0,则执行安全性检测算法的结果是( )。(2018年计算机科学与技术学科全国硕士研究生入学统一试卷26题)
A 不存在安全序列,系统处于不安全状态
B 存在多个安全序列,系统处于安全状态
C 存在唯一安全序列P3、P1、P2,系统处于安全状态
D 存在唯一安全序列P3、P2、P1,系统处于安全状态
剩余1个资源,分配给P3。P3运行结束后释放1个资源,此时P2 P1仍然无法获得需要的资源数,发生死锁
16. 下列关于死锁的叙述中,正确的是( )。(2019年计算机科学与技术学科全国硕士研究生入学统一试卷30题)
Ⅰ.可以通过剥夺进程资源解除死锁
Ⅱ.死锁的预防方法能确保系统不发生死锁
Ⅲ.银行家算法可以判断系统是否处于死锁状态(不是判断,是避免了死锁)
Ⅳ.当系统出现死锁时,必然有两个或两个以上的进程处于阻塞态
A.仅Ⅱ、Ⅲ B.仅Ⅰ、Ⅱ、Ⅳ
C.仅Ⅰ、Ⅱ、Ⅲ D.仅Ⅰ、Ⅲ、Ⅳ
总结:
1. 预防死锁。 (1.破坏请求和保持条件2.破坏不可抢占条件3.破坏循环等待条件)
这是一种较简单和直观的事先预防的方法。方法是通过设置某些限制条件,去破坏产生死锁的四个必要条件中的一个或者几个,来预防发生死锁。预防死锁是一种较易实现的方法,已被广泛使用。但是由于所施加的限制条件往往太严格,可能会导致系统资源利用率和系统吞吐量降低。
2. 避免死锁。 (银行家算法)
该方法同样是属于事先预防的策略,但它并不须事先采取各种限制措施去破坏产生死锁的的四个必要条件,而是在资源的动态分配过程中,用某种方法去防止系统进入不安全状态,从而避免发生死锁。
3. 检测死锁。 (1.资源分配图2.死锁定理3.死锁检测中的数据结构)
这种方法并不须事先采取任何限制性措施,也不必检查系统是否已经进入不安全区,此方法允许系统在运行过程中发生死锁。但可通过系统所设置的检测机构,及时地检测出死锁的发生,并精确地确定与死锁有关的进程和资源,然后采取适当措施,从系统中将已发生的死锁清除掉。
4. 解除死锁。 (1.抢占资源2.终止或者撤销进程)
这是与检测死锁相配套的一种措施。当检测到系统中已发生死锁时,须将进程从死锁状态中解脱出来。常用的实施方法是撤销或挂起一些进程,以便回收一些资源,再将这些资源分配给已处于阻塞状态的进程,使之转为就绪状态,以继续运行。死锁的检测和解除措施,有可能使系统获得较好的资源利用率和吞吐量,但在实现上难度也最大。