文档库

最新最全的文档下载
当前位置:文档库 > 第三章 处理机调度与死锁习题及答案 新解析

第三章 处理机调度与死锁习题及答案 新解析

第三章处理机调度与死锁

一.选择题

1.下列算法中,操作系统用于作业调度的算法是。

A.先来先服务算法B.先进先出算法

C.最先适应算法D.时间片轮转算法

2.在批处理系统中,周转时间是指。

A.作业运行时间B.作业等待时间和运行时间之和

C.作业的相对等待时间D.作业被调度进入内存到运行完毕的时间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.需要CPU时间最短的进程先做

11.下面关于优先权大小的论述中,不正确的论述是。

A.计算型作业的优先权,应低于I/O型作业的优先权

B.系统进程的优先权应高于用户进程的优先权

C.资源要求多的作业,其优先权应高于资源要求少的作业

D.在动态优先权时,随着进程运行时间的增加,其优先权降低

12.产生死锁的原因是有关。

A.与多个进程竞争CPU

B.与多个进程释放资源

C.仅由于并发进程的执行速度不当

D.除资源分配策略不当外,也与并发进程执行速度不当

13.有关产生死锁的叙述中,正确的是。

A.V操作可能引起死锁B.P操作不会引起死锁

C.PV操作使用得当不会引起死锁D.以上说法均不正确

14.有关死锁的论述中,是正确的。

A.“系统中仅有一个进程进入了死锁状态”

B.“多个进程由于竞争CPU而进入死锁”

C.“多个进程由于竞争互斥使用的资源又互不相让而进入死锁”

D.“由于进程调用V操作而造成死锁”

15.有关资源分配图中存在环路和死锁关系,正确的说法是。

A.图中无环路则系统可能存在死锁

B.图中无环路则系统可能存在死锁,也可能不存在死锁

C.图中有环路则系统肯定存在死锁

D.图中有环路则系统可能存在死锁,也可能不存在死锁

16.“死锁”问题的讨论是针对的。

A.某个进程申请系统中不存在的资源

B.某个进程申请资源数超过了系统拥有的最大资源数

C.硬件故障

D.多个并发进程竞争独占型资源

17.考虑到公平对待进程和提高系统资源工作的并行度,操作系统会经常调整进程的优先级,通常应提高的进程优先级。

A.需计算时间长B.很少使用外设

C.使用CPU时间长D.启动外设次数多

18.实时系统中的进程调度,通常采用算法。

A.响应比高者优先B.短作业优先

C.时间片轮转D.抢占式的优先数高者优先

19.UNIX操作系统采用的进程调度算法为。

A、不可强占处理机的动态化先数调度算法

B、可强占处理机的动态化先数调度算法

C、不可强占处理机的静态优先数调度算法

D、可强占处理机的静态化先数调度算法

20.当进程调度采用最高优先级调度算法时,从保证系统效率的角度来看,应提高进程的优先级。

A.连续占用处理器时间长的B.在就绪队列中等待时间长的

C.以计算为主的D.用户

21.产生系统死锁的原因可能是由于。

A.进程释放资源B.一个进程进入死循环

C.多个进程竞争资源出现了循环等待D.多个进程竞争共享型设备

22.采用时间片轮转调度算法时,对不同的进程可以规定不同的时间片。一般来说,对进程给一个较小的时间片比较合适。

A.需运算时间长的B.需经常启动外设的

C.不需使用外设的D.排在就绪队列末尾的

23.对资源采用按序分配策略能达到的目的。

A.防止死锁B.避免死锁C.检测死锁D.解除死锁

24.一种既有利于短小作业又兼顾到长作业的作业调度算法是。

A.先来先服务B.轮转C.最高响应比优先D.均衡调度

25.在单处理器的多进程系统中,进程什么时候占用处理器和能占用多长时间,取决于

A.进程相应的程序段的长度B.进程总共需要运行时间多少

C.进程自身和进程调度策略D.进程完成什么功能

26.在解决死锁问题的方法中,属于“死锁避免”策略的是。

A.银行家算法B.死锁检测算法

C.资源有序分配法D.资源分配图化简法

27.系统出现死锁的原因是。

A.计算机系统出现了重大故障

B.有多个等待态的进程同时存在

C.若干进程因竞争资源而无休止地等待着它方释放已占有的资源

D.资源数大大少于进程数或进程同时申请的资源数大大超过资源总数

28.在操作系统中,所谓“死锁”是指。

A.程序死循环B.多个进程彼此等待资源而不能前进的状态

C.硬件故障D.时间片太短,进程的调进调出太频繁而效率太低

29.假设有三个进程竞争同类资源,如果每个进程需要2个该类资源,则至少需要提供该类资源_ 个,才能保证不会发生死锁。

A.3 B.4 C.5 D.6

30.以下不属于死锁的必要条件。

A.互斥使用资源B.占有并等待资源

C.不可抢夺资源D.静态分配资源

31.在为多个进程所提供的可共享的系统资源不足时,可能出现死锁。但是,不适当的也可能产生死锁。

A.进程优先权B.资源的静态分配

C.进程的推进顺序D.分配队列优先权

32.采用资源剥夺法可以解除死锁,还可以采用方法解除死锁。

A.执行并行操作B.撤消进程

C.拒绝分配新资源D.修改信号量

33.系统中有4个并发进程,都需要某类资源3个。试问该类资源最少为个时,不会因竞争该资源而发生死锁。

A.9 B.10 C.11 D.12

34.在下列解决死锁的方法中,不属于死锁预防策略的是。

A.资源的有序分配法B.资源的静态分配法

C.分配的资源可剥夺法D.银行家算法

35.分时系统中进程调度算法通常采用。

A.响应比高者优先B.时间片轮转法

C.先来先服务D.短作业优先

36.设有三个作业J1、J2、J3,它们的到达时间和执行时间如下表:

作业名到达时间执行时间

J1 8:00 2小时

J2 8:45 1小时

J3 9:30 0.25小时

它们在一台处理器上按单道运行,若采用短作业优先调度算法,则此三作业的执行次序是。

A.J3,J2,J1 B.J1,J2,J3

C.J1,J3,J2 D.J3,J1,J2

37.在下列作业调度算法中,可能引起作业长时间不能被装入执行的算法是。

A.FCFS算法B.计算时间短的作业优先算法

C.最高响应比优先算法D.动态优先数调度算法

39.在非抢占调度方式下,运行进程执行V原语后,其状态。

A.不变B.要变C.可能要变D.可能不变

40.在多进程的并发系统中,肯定不会因竞争而产生死锁。

A.打印机B.磁带机C.磁盘D.CPU

41.通常不采用方法来解除死锁。

A.终止一个死锁进程B.终止所有死锁进程

C.从死锁进程处抢夺资源D.从非死锁进程处抢夺资源

43.设系统中有P1、P2、P3三个进程,并按P1、P2、P3的优先次序调度运行,它们的内部计算和I/O操作时

间如下:

P1:计算60 ms —I/O 80 ms —计算20 ms P2:计算120 ms —I/O 40ms —计算40ms P3:计算40 ms —I/O 80ms —计算40ms

设调度程序执行时间忽略不计,完成这三个进程比单道运行节省的时间是 。 A .140ms B .160ms C .170ms D .180ms

44.有三个作业A 、B 、C ,它们的到达时间和执行时间依次为(8:50和1.5小时)、(9:00和0.4小时)、(9:30和1小

时)。当作业全部到达后,批处理单道系统按响应比高者优先算法进行调度,则作业被选中的次序为 。 A .(ABC) B .(BAC) C .(BCA) D .(CAB)

45.设系统中有n 个并发进程,竞争资源R ,且每个进程都需要m 个R 类资源,为使该系统不会因竞争该类资

源而死锁,资源R 至少要有 个。 A .n*m+1 B .n*m+n C .n*m+1-n D .无法预计 46.下列选项中,降低进程优先级的合理时机是 。(2010全国试题)

A .进程的时间片用完

B .进程刚完成I/O ,进入就绪队列

C .进程长期处于就绪队列中

D .进程从就绪队列转为运行状态 47.下列进程调度算法中,综合考虑进程等待时间和执行时间的是__________。(2009全国试题)

A .时间片轮转调度算法

B .短进程优先调度算法

C .先来先服务调度算法

D .高响应比优先调度算法

48.某计算机系统中有8台打印机,有k 个进程竞争使用,每个进程最多需要3台打印机。该系统可能会发

生死锁的k 的最小值是__________。(2009全国试题) A .2 B .3 C .4 D .5 49.进程调度的关键问题是 。

A .内存的分配

B .时间片的确定

C .调度算法的确定

D .I/O 设备的分配

50.下列选项中,满足短任务优先且不会发生饥饿现象的调度算法是 。(2011全国试题)

A .先来先服务

B .高响应比优先

C .时间片轮转

D .非抢占式短任务优先 51.某时刻进程的资源使用情况如下表所示。

进程 已分配资源 尚需资源 可用资源 R1 R2 R3 R1 R2 R3 R1

R2

R3

P1 2 0 0 0 0 1 0

2

1

P2 1 2 0 1 3 2 P3 0 1 1 1 3 1 P4

1

2

此时的安全序列是 。

A .P1,P2,P3,P4

B .P1,P3,P2,P4

C .P1,P4,P3,P2

D .不存在

52.设有五个进程P0、P1、P2、P3、P4共享三类资源R1、R2、R3,这些资源总数分别为18、6、22,T0时刻

的资源分配情况如下表所示,此时存在的一个安全序列是 。(2012全国试题)

进程 已分配资源 资源最大需求

R1 R2 R3 R1 R2 R3 P0 3 2 3 5 5 10 P1 4 0 3 5 3 6 P2 4 0 5 4 0 11 P3 2 0 4 4 2 5 P4

3

1

4

4

2

4

A .P0,P2,P4,P1,P3

B .P1,P0,P3,P4,P2

C .P2,P3,P4,P1,P0

D .P3,P4,P2,P1,P0

53.一个多道批处理系统中仅有P1和P2两个作业,P2比P1晚5ms到达,它们的计算和I/O操作顺序如下:P1:计算60ms,I/O80ms,计算20ms

P2:计算120ms,I/O40ms,计算40ms

若不考虑调度和切换时间,则完成两个作业需要的时间最少是。(2012全国试题)

A.240ms B.260ms C.340ms D.360ms

54.某单处理器多进程系统中有多个就绪进程,则下列关于处理机调度的叙述中,错误的是。

A.在进程结束时能进行处理机调度

B.创建新进程后能进行处理机调度

C.在进程处于临界区时不能进行处理机调度

D.在系统调用完成并返回用户态时能进行处理机调度

选择题参考答案:

1.A 2.B 3.A 4.D 5.B 6.D 7.B 8.D 9.D 10.A 11.C 12.D 13.D 14.C 15.D 16.D 17.D 18.D 19.A 20.B 21.C 22.B 23.A 24.C 25.C 26.A 27.C 28.B 29.B 30.D 31.C 32.B 33.A 34.D 35.B 36.C 37.B 39.A 40.D 41.C 43.B 44.B 45.C 46.A 47.D 48.C 49.C 50.B 51.D 52.D 53.B 54.C

二.应用题

1.有一个具有两道作业的批处理系统(最多可有两道作业同时装入内存执行),作业调度采用计算时间短

的作业优先调度算法,进程调度采用以优先数为基础的抢占式调度算法,今有如下作业序列,作业优先数即为进程优先数,优先数越小优先级越高:

作业名到达时间估计运行时间优先数

J1 10 : 10 20分钟 5

J2 10 : 20 30分钟 3

J3 10 : 30 25分钟 4

J4 10 : 50 20分钟 6

(1)列出所有作业进入内存时间及结束时间。(2)计算平均周转时间。

解:先作必要的分析(可在草稿纸上完成,分析过程不计分):

10:10 J1被调入,开始运行

10:20 J2进入内存,因优先级高,开始运行

J1运行了10分钟,还剩10分钟,因优先级低,运行态变就绪态

10:30 J1继续就绪

J2运行了10分钟,还剩20分钟

J3到达,但不能被调入

10:50 J2运行结束,J4到达

调入短作业J4,但因J4优先级比J1低,J1开始继续运行

11:00 J1运行结束

J3被调入,因优先级高,开始运行

J4因优先级低,仍就绪

11:25 J3运行结束,J4开始运行

11:45 J4运行结束

(1)各个作业进入主存时间、结束时间和周转时间如下表所示:(6分)

作业名提交时间进入时间结束时间周转时间

J1 10:10 10:10 11:00 50

J2 10:20 10:20 10:50 30

J3 10:30 11:00 11:25 55

J4 10:50 10:50 11:45 55 (2)平均周转时间:(50+30+55+55)/4=47.5(min)

2.某系统有A,B,C三类资源(数量分别为17,5,20)和P1~P5五个进程,在T0时刻系统状态如下表所示:

进程最大资源需求量已分配资源数量A B C A B C

P1 5 5 9 2 1 2

P2 5 3 6 4 0 2

P3 4 0 11 4 0 5

P4 4 2 5 2 0 4

P5 4 2 4 3 1 4

系统采用银行家算法实施死锁避免策略,请回答下列问题:

①T0时刻是否为安全状态?若是,请给出安全序列。

②在T0时刻若进程P2请求资源(0,3,4),是否能实施资源分配?为什么?

③在②的基础上,若进程P4请求资源(2,0,1),是否能实施资源分配?为什么?

解:①由已知条件可得尚需矩阵Need和可用资源向量Avalable如下:

Need Avalable

A B C A B C

P1 3 4 7 2 3 3

P2 1 3 4

P3 0 0 6

P4 2 2 1

P5 1 1 0

利用银行家算法对此时刻的资源分配情况进行分析如下表:

进程Work Need Allocation Work+Allocation Finish

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

P2 4 3 7 1 3 4 4 0 2 8 3 9 true

P3 8 3 9 0 0 6 4 0 5 12 3 14 true

P5 12 3 14 1 1 0 3 1 4 15 4 18 true

P1 15 4 18 3 4 7 2 1 2 17 5 20 true

从上述分析可知,存在一个安全序列P4,P2,P3,P5,P1,故T0时刻系统是否安全的。

②在T0时刻若进程P2请求资源(0,3,4),不能实施资源分配。因为当前C类资源剩余3个而P2请求4个,

客观条件无法满足它的请求,因此不能实施资源分配,P2阻塞。

③在②的基础上,若进程P4请求资源(2,0,1),可以实施资源分配。因为由①可知,P4是安全序列

中的第一个进程,只要P4的请求量没有超出它的尚需量,系统满足它的请求后仍处于安全状态,即仍然存在安全序列P4,P2,P3,P5,P1。

3.某计算机系统有9台磁带机,它们供N个进程竞争使用,每个进程可能需要3台磁带机。请问N为多少时,

系统没有死锁的危险,并说明其原因。

解:最坏的情况是N个进程每个进程都分得了2台磁带机,若在这种情况下仍有富余的磁带机,可供某一个进程使用,则该进程可得到所需的全部磁带机,从而可运行完成。该进程运行完成后释放的磁带机又可共其他进程使用,从而使得到磁带机的进程运行完成。它们释放的磁带机又可共其他没有完成的进程使用,如此下去,最终可使所有进程得到所需的全部磁带机,从而运行到底。这种情况就没有因竞争磁带机而发生死锁的危险。由上分析,只要满足下式

N(3-1)+1≤9

即 N≤4时,系统没有死锁的危险。

4.用银行家算法考虑下列系统状态:

进程分配矩阵最大需求矩阵资源总数向量

A 3 0 1 1 4 1 1 1 6 3 4 2

B 0 1 0 0 0 2 1 2

C 1 1 1 0 4 2 1 0

D 1 1 0 1 1 1 1 1

E 0 0 0 0 2 1 1 0

问:(1) 系统是否安全?(应说明理由)

(2) 若进程B请求(0,0,1,0),可否立即分配?请分析说明。

(3) 此后进程E也请求(0,0,1,0),可否分配给它?请分析说明。

解:(1) 由已知条件可得Need和Avaiable矩阵如下:

进程分配矩阵尚需矩阵(Need) 可用资源数向量(Avaiable)

A 3 0 1 1 1 1 0 0 1 0 2 0

B 0 1 0 0 0 1 1 2

C 1 1 1 0 3 1 0 0

D 1 1 0 1 0 0 1 0

E 0 0 0 0 2 1 1 0

利用银行家算法对此时刻的资源分配情况进行分析如下表:

进程Work Need Allocation Work+Allocation Finish

D 1 0 2 0 0 0 1 0 1 1 0 1 2 1 2 1 true

A 2 1 2 1 1 1 0 0 3 0 1 1 5 1 3 2 true

B 5 1 3 2 0 1 1 2 0 1 0 0 5 2 3 2 true

C 5 2 3 2 3 1 0 0 1 1 1 0 6 3 4 2 true

E 6 3 4 2 2 1 1 0 0 0 0 0 6 3 4 2 true

从上述分析可知,存在一个安全序列D,A,B,C,E,故当前系统是否安全的。

(2)若进程B请求(0,0,1,0),试分配并修改相应的数据结构,则系统状态变为:

进程分配矩阵尚需矩阵(Need) 可用资源数向量(Avaiable)

A 3 0 1 1 1 1 0 0 1 0 1 0

B 0 1 1 0 0 1 0 2

C 1 1 1 0 3 1 0 0

D 1 1 0 1 0 0 1 0

E 0 0 0 0 2 1 1 0

利用银行家算法对此时刻的资源分配情况进行分析如下表:

进程Work Need Allocation Work+Allocation Finish

D 1 0 1 0 0 0 1 0 1 1 0 1 2 1 1 1 true

A 2 1 1 1 1 1 0 0 3 0 1 1 5 1 2 2 true

B 5 1 2 2 0 1 0 2 0 1 1 0 5 2 3 2 true

C 5 2 3 2 3 1 0 0 1 1 1 0 6 3 4 2 true

E 6 3 4 2 2 1 1 0 0 0 0 0 6 3 4 2 true

从上述分析可知,存在安全序列D,A,B,C,E,故系统仍是否安全的,因此可以立即分配。

(3)此后进程E也请求(0,0,1,0),则系统状态变为:

进程分配矩阵尚需矩阵(Need) 可用资源数向量(Avaiable)

A 3 0 1 1 1 1 0 0 1 0 0 0

B 0 1 1 0 0 1 0 2

C 1 1 1 0 3 1 0 0

D 1 1 0 1 0 0 1 0

E 0 0 1 0 2 1 0 0

此时系统剩余资源(1,0,0,0)已不能满足任何进程的需求,即已找不到一个安全序列,系统状态将变为不安全,故不能分配给E。

5.某系统有A、B、C、D这4类资源供5个进程共享,进程对资源的需求和分配情况如下表所示。现在系统

中A、B、C、D类资源分别还剩1、5、2、0个,请按银行家算法回答下列问题:

进程

已占资源最大需求数

A B C D A B C D

P1 0 0 1 2 0 0 1 2

P2 1 0 0 0 1 7 5 0

P3 1 3 5 4 2 3 5 6

P4 0 6 3 2 0 6 5 2

P5 0 0 1 4 0 6 5 6 现在系统是否处于安全状态? 为什么?

(1)如果现在进程P2提出需要(0,4,2,0)个资源的请求,系统能否满足它的请求?为什么?

解:(1) 由已知条件可得Need矩阵如下:

进程分配矩阵尚需矩阵(Need) 可用资源数向量(Avaiable)

P1 0 0 1 2 0 0 0 0 1 5 2 0

P2 1 0 0 0 0 7 5 0

P3 1 3 5 4 1 0 0 2

P4 0 6 3 2 0 0 2 0

P5 0 0 1 4 0 6 4 2

利用银行家算法对此时刻的资源分配情况进行分析如下表:

进程Work Need Allocation Work+Allocation Finish

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

P3 1 5 3 2 1 0 0 2 1 3 5 4 2 8 8 6 true

P2 2 8 8 6 0 7 5 0 1 0 0 0 3 8 8 6 true

P4 3 8 8 6 0 0 2 0 0 6 3 2 3 14 11 8 true

P5 3 14 11 8 0 6 4 2 0 0 1 4 3 14 12 12 true

从上述分析可知,存在安全序列P1,P3,P2,P4,P5,故系统状态是否安全的。(注:安全序列不唯一)(2)若进程P2请求(0,4,2,0),试分配并修改相应的数据结构,则系统状态变为:

进程分配矩阵尚需矩阵(Need) 可用资源数向量(Avaiable)

P1 0 0 1 2 0 0 0 0 1 1 0 0

P2 1 4 2 0 0 3 3 0

P3 1 3 5 4 1 0 0 2

P4 0 6 3 2 0 0 2 0

P5 0 0 1 4 0 6 4 2

进程P1已获得全部资源,可运行完成。P1结束归还资源后,系统剩余资源为(1, 1, 1, 2),能满足P3的需求,P3可运行完成。P3结束释放资源后,系统剩余资源为(2, 4, 6, 6),能满足P2的需求,P2可运行完成。P2结束释放资源后,系统剩余资源为(3, 8, 8, 6)。类似地,P4、P5也能获得所需资源而运行完成。因此存在安全序列P1, P3, P2, P4, P5,即系统仍然是否安全的,因此系统能满足P2的请求。

6. 某系统中有10台打印机,有三个进程P1,P2,P3分别需要8台,7台和4台。若P1,P2,P3已申请到4台,2台和2台。试问:按银行家算法能安全分配吗?请说明分配过程。

解:由题目所给条件,可得如下有关数据结构:

进程Max Allocation Need Available

P1 8 4 4 2

P2 7 2 5

P3 4 2 2

故按银行家算法能安全分配。分配过程是:首先将当前剩余的2台打印机全部分配给P3,使P3得到所需的全部打印机数,从而可运行到完成。P3完成后,释放的4台打印机全部分配给P1,使P1也能运行完成;P1完成后释放的打印机可供P2使用,使P2也能运行结束。即系统按P3、P1、P2的顺序分配打印机,就能保证系统状态是安全的。

7. 有5个批处理作业(A,B,C,D,E)几乎同时到达一个计算中心,估计的运行时间分别为10,6,2,4,8分钟,他们的优先数分别为1,2,3,4,5(1为最低优先数)。对下面的各种调度算法,分别计算作业的平均周期时间。

(1)最高优先级优先

(2)短作业优先

解:(1) 采用最高优先级优先调度算法,各进程开始运行的时间、完成时间以及周转时间如下表:

进程开始运行时间完成时间周转时间

A 20 30 30

B 14 20 20

C 12 14 14

D 8 12 12

E 0 8 8

平均周转时间为(30+20+14+12+8)/5=84/5=16.8(ms)

(2) 采用短作业优先调度算法,各进程开始运行的时间、完成时间以及周转时间如下表:

进程开始运行时间完成时间周转时间

A 20 30 30

B 6 12 12

C 0 2 2

D 2 6 6

E 12 20 20

平均周转时间为(30+12+2+6+20)/5=70/5=14 (ms)

8.假定某系统当时的资源分配图如图3-2所示:

图3-2

(1)分析当时系统是否存在死锁。

(2)若进程P3再申请R3时,系统将发生什么变化,说明原因。

解:(1) 因为当时系统的资源分配图中不存在环路.所以不存在死锁。

(2) 当进程P3申请资源R3后,资源分配图中形成环路P2→R2→P3→R3→P2,而R2,R3都是单个资源的类,该

环路无法消除,所以进程P2,P3永远处于等待状态.从而引起死锁。

9.若系统有同类资源m个,供n个进程共享,试问:当m>n和m≤n时,每个进程最多可以申请多少个这

类资源而使系统一定不会发生死锁?

解:设每个进程申请该类资源的最大量为x 个,则只要不等式n(x-1)+1≤m 成立,系统一定不会发生死锁。

因为最坏情况下,每个进程都已获得x-1各资源,则n 个进程共获得n(x-1)个资源,而不等式n(x-1)+1≤m 表示每个进程都已获得x-1各资源后,系统仍有可分配的资源,这样,至少有一个进程可以得到全部资源,从而能执行完成,它完成后释放的资源又可使其它进程执行完成。 解不等式 n(x-1)+1≤m ,可得 x ≤1+(m-1)/n 于是可得

1 当m ≤n

x=

第三章  处理机调度与死锁习题及答案 新解析

1+[(m-1)/n] 当m>n

10.设系统中仅有一类数量为M 的独占资源,系统中N 个进程竞争该类资源,其中各进程对该类资源的最

大需求量为W 。当M 、N 、W 分别取下列值时,试判断哪些情况可能会发生死锁?哪些情况不可能发生死锁?为什么?

①M=2, N=2, W=1 ②M=3, N=2, W=2 ③M=3, N=2, W=3 ④M=5, N=3,W=2 ⑤M=6, N=3, W=3

解:M 、N 、W 满足关系式N(W-1)

用上述关系式判断,可知①、②、④三种情况不会发生死锁;而③、⑤两种情况可能会发生死锁。 11.某系统有R1、R2和R3共3种资源,在T0时刻P1、P2、P3和P4这4个进程对资源的占用和需求情况

见表1,此时系统的可用资源向量为(2, 1, 2),试问:

(1) 将系统中各种资源总数和此刻各进程对各资源的需求数目用向量或矩阵表示出来;

(2) 如果此时P1和P2均发出资源请求向量(1, 0, 1),为了保证系统的安全性,应该如何分配资源给这两个

进程?说明你所采用策略的原因。

(3) 如果(2)中两个请求立即得到满足后,系统此时是否处于死锁状态?

表1 T0时刻4个进程对资源的占用和需求情况

最大资源需求量Max 已分配资源量Allocation R1 R2 R3 R1 R2 R3 P1 3 2 2 1 0 0 P2 6 1 3 4 1 1 P3 3 1 4 2 1 1 P4

4

2

2

2

解:(1) 系统中资源总数是可用资源数与各进程已分配资源数之和,即

(2, 1, 2) + (1, 0, 0) + (4, 1, 1) + (2, 1, 1) + (0, 0, 2) = (9, 3, 6) 各进程对各资源的需求量为Max 与Allocation 之差,即

?????

???????=????????????-????????????02

4

301202222

20

112114001

22

4

413316223 (2) 若此时P1发出资源请求Request 1 (1, 0, 1),按银行家算法进行检查:

Request 1 (1, 0, 1)≤Need 1 (2, 2, 2) Request 1 (1, 0, 1)≤Available (2, 1, 2)

试分配并修改相应的数据结构,资源分配情况如下: 进程 Allocation Need Available P1 2 0 1 1 2 1 1 1 1 P2 4 1 1 2 0 2 P3

2

1

1

1

3

P4 0 0 2 4 2 0

利用安全性检查算法检查,可知可用资源向量(1, 1, 1)已不能满足任何进程的需求,故若分配给P1,系统将进入不安全状态,因此此时不能将资源分配给P1。

若此时P2发出资源请求Request2 (1, 0, 1),按银行家算法进行检查:

Request2 (1, 0, 1)≤Need2 (2, 0, 2)

Request2 (1, 0, 1)≤Available (2, 1, 2)

试分配并修改相应的数据结构,资源分配情况如下:

进程Allocation Need Available

P1 1 0 0 2 2 2 1 1 1

P2 5 1 2 1 0 1

P3 2 1 1 1 0 3

P4 0 0 2 4 2 0

利用安全性检查算法,可得此时刻的安全性分析情况如下:

进程Work Need Allocation Work+Allocation Finish

P2 1 1 1 1 0 1 5 1 2 6 2 3 true

P3 6 2 3 1 0 3 2 1 1 8 3 4 true

P4 8 3 4 4 2 0 0 0 2 8 3 6 true

P1 8 3 6 2 2 2 1 0 0 9 3 6 true 从上面分析可知,存在一个安全序列{P2, P3, P4, P1},故该状态时安全的,可以立即将P2所申请的资源分配给它。

(3) 如果(2)中两个请求立即得到满足后,系统此时并没有立即进入死锁状态,因为此时所有进程没有提

出新的资源请求,全部进程都没有因资源请求没有得到满足而进入阻塞状态。只有当进程提出新的资源请求且全部进程(指P1-P4)都进入阻塞状态时,系统才处于死锁状态。

12.在单处理机系统中,有多个进程运行:一些以计算为主,一些以输入/输出为主。如何赋予进程占有处理器的优先级才能提高系统的效率,使系统的平均周转时间减少?

答:若计算型进程的优先级高于I/O型进程的优先级,计算型进程一旦占有了CPU便忙于计算,使I/O型进程得不到运行的机会,导致I/O设备空闲,达不到CPU与I/O操作并行的目的;多个I/O型进程在系统中停留时间增加,系统的平均周转时间增加。

若I/O型进程的优先级高于计算型进程的优先级,当它完成一项I/O操作后,便能立即获得CPU,为下次I/O作准备工作,并启动外设。当设备被启动后,它便主动交出CPU,由系统将CPU分配给计算型进程,从而使CPU与I/O设备并行操作,获得较好的运行效率。

因此,应赋予以I/O为主的进程更高的优先级。