这样,至少必须存在一个进程,其need(i)≤0,这显然与题意不符,所以该系统不可能因竞争该类资源而进入死锁状态。
(3)此时系统可能发生死锁,如n=4,m=3时,若P1的Max为0,而其余三个进程的Max都为2,则仍然满足最大需求量之和(即6)小于m+n(即7)的要求,但当除P1以外的其余三个进程各得到一个资源时,这三个进程将进入死锁状态。
【例2】设系统中有3种类型的资源A、B、C和5个进程P0、P1、P2、P3、P4,A资源的数量为10,B资源的数量为5,C资源的数量为7。
在T0时刻系统状态如下表所示。
系统采用银行家算法实施死锁避免策略。
Max
Allocation
Need
Available
A
B
C
A
B
C
A
B
C
A
B
C
P0
P1
P2
P3
P4
7
5
3
0
1
0
7
4
3
3
3
2
3
2
2
2
0
0
1
2
2
9
0
2
3
0
2
6
0
0
2
2
2
2
1
1
0
1
1
4
3
3
0
0
2
4
3
1
(1)T0时刻是否为安全状态若是,请给出安全序列。
(2)在T0时刻若进程P1发出资源请求Request(1,0,2),是否能够实施资源分配
(3)在②的基础上P4发出资源请求Request(3,3,0),是否能够实施资源分配
(4)在③的基础上P0发出资源请求Request(0,2,0),是否能够实施资源分配
答:
(1)利用银行家算法对T0时刻的资源分配情况进行分析,可得此时刻的安全性分析情况:
Work
Need
Allocation
Work+Allocation
Finish
A
B
C
A
B
C
A
B
C
A
B
C
P1
3
3
2
1
2
2
2
0
0
5
3
2
True
P3
5
3
2
0
1
1
2
1
1
7
4
3
True
P4
7
4
3
4
3
1
0
0
2
7
4
5
True
P2
7
4
5
6
0
0
3
0
2
10
4
7
True
P0
10
4
7
7
4
3
0
1
0
10
5
7
True
可知,在T0时刻存在着一个安全序列{P1、P3、P4、P2、P0},故系统是安全的。
(2)P1请求资源Request(1,0,2),系统按银行家算法进行检查:
Request(1,0,2)≤Need(1,2,2)
Request(1,0,2)≤Available(3,3,2)
系统试探分配,修改相应的向量,形成的资源变化情况如下表所示:
Max
Allocation
Need
Available
A
B
C
A
B
C
A
B
C
A
B
C
P0
7
5
3
0
1
0
7
4
3
2
3
0
P1
3
2
2
3
0
2
0
2
0
P2
9
0
2
3
0
2
6
0
0
P3
2
2
2
2
1
1
0
1
1
P4
4
3
3
0
0
2
4
3
1
在利用安全性算法检查此时系统是否安全,如下表所示:
Work
Need
Allocation
Work+Allocation
Finish
A
B
C
A
B
C
A
B
C
A
B
C
P1
2
3
0
0
2
0
3
0
2
5
3
2
True
P3
5
3
2
0
1
1
2
1
1
7
4
3
True
P4
7
4
3
4
3
1
0
0
2
7
4
5
True
P0
7
4
5
7
4
3
0
1
0
7
5
5
True
P2
7
5
5
6
0
0
3
0
2
10
5
7
True
由安全性算法检查可知,可以找到一个安全序列{P1、P3、P4、P0、P2}。
因此,系统是安全的,可以立即把P1所申请的资源分配给它。
(3)P4发出资源请求Request(3,0,0),系统按照银行家算法进行检查:
Request(3,3,0)≤Need(4,3,1)
Request(3,3,0)≮Available(2,3,0),所以让P4等待。
(4)P0发出资源请求Request(0,2,0),系统按照银行家算法进行检查:
Request(0,2,0)≤Need(7,4,3)
Request(0,2,0)≤Available(2,3,0)
系统试探分配,修改相应的向量,形成的资源变化情况如下表所示:
Allocation
Need
Available
A
B
C
A
B
C
A
B
C
P0
0
3
0
7
2
3
2
1
0
P1
3
0
2
0
2
0
P2
3
0
2
6
0
0
P3
2
1
1
0
1
1
P4
0
0
2
4
3
1
进行安全性检查,可用资源Available(2,1,0)已不能满足任何进程的需要,故系统进入不安全状态,此时系统不分配资源。
练习题
一、单项选择题
1.任何时刻总是让具有最高优先数的进程占用处理器,此时采用的进程调度算法是()。
A.非抢占式的优先数调度算法B.时间片轮转调度算法
C.先来先服务调度算法D.抢占式的优先数调度算法
2.抢占式的优先数调度算法在()中很有用。
A.网络操作系统B.分布式系统
C.批处理系统D.实时系统
3.下列算法中,()只能采用非抢占调度方式,()只能采用抢占调度方式,而其余的算法既可采用抢占方式,也可采用非抢占方式。
A.高优先权优先法B.时间片轮转法
调度算法D.短作业优先算法
4.下列进程调度算法中,综合考虑进程等待时间和执行时间的是()。
A.时间片轮转调度算法B.短进程优先调度算法
C.先来先服务调度算法D.高响应比优先调度算法
5.进程调度的关键问题是()
A.时间片大小B.进程调度算法
速度D.内存空间利用率
6.下列选项中,降低进程优先权级的合理时机是()。
A.进程的时间片用完B.进程刚完成I/O,进入就绪队列
C.进程长期处于就绪队列中D.进程从就绪状态转为运行态
7.采用时间片轮转调度算法是为了()
A.多个终端用户能得到系统的及时响应
B.先来先服务
最短的进程先执行
D.优先级高的进程能得到及时调度
8.下面关于优先权大小的叙述中正确的是()。
A.用户进程的优先权,应高于系统进程的优先权
B.在动态优先权中,随着作业的等待时间的增加,其优先权将随之增加
C.资源要求多的作业,其优先权应高于资源要求少的作业
D.长作业的优先权,应高于短作业的优先权
9.作业调度算法的选择常考虑的因素之一是使系统有最高的吞吐量,为此应()。
A.不让处理机空闲B.能够处理尽可能多的作业
C.使用户们都满意D.不使磁头过于复杂
10.在各种作业调度算法中,若所有作业同时到达,则平均等待时间最短的算法是()。
A.先来先服务B.高优先权优先C.短作业优先D.高响应比优先
11.作业调度程序从()队列中选取适当的作业投入运行。
A.就绪B.提交C.运行D.后备
12.在批处理系统中,用户的作业是由()组成的。
A.程序B.程序+数据+作业说明书C.程序+作业说明书D.程序+数据
13.假设下述四个作业同时到达,当使用最高优先数优先调度算法时,作业的平均周转时间为()。
作业
所需运行时间
优先数
1
2
4
2
5
9
3
8
1
4
3
8
A.B.C.D.
14.一作业8:
00到达系统,估计运行时间为1小时,若10:
00开始执行该作业,其响应比是()。
A.2B.1C.3D.
15.下面哪个算法适用于分时系统中的进程调度()。
B.时间片轮转为主的优先D.动态优先数法
16.在多道批处理系统中,为充分利用各种资源,运行的程序应具备的条件是()。
A.适应于内存分配的B.计算量大的
O量大的D.计算型和I/O型均衡的
17.下面的叙述中正确的是()。
A.安全状态是没有死锁的状态,非安全状态是有死锁的状态。
B.安全状态是可能有死锁的状态,非安全状态也是可能有死锁的状态
C.安全状态是可能没有死锁的状态,非安全状态是有死锁的状态
D.安全状态是没有死锁的状态,非安全状态是可能有死锁的状态
18.除了进程竞争资源,因为资源不足可能出现死锁以外,不适当的()也可能产生死锁。
A.进程优先权B.资源的线性分配
C.进程推进顺序D.分配队列优先权
19.发生死锁的必要条件有四个,要防止死锁的发生,可以破坏这四个必要条件,但破坏()条件是不太实际的。
A.互斥B.请求和保持C.不剥夺D.环路等待
20.除了可以采用资源剥夺法解除死锁,还可以采用()方法解除死锁。
A.修改信号量B.拒绝分配新的资源
C.撤销进程D.执行并行操作
21.资源的按序分配策略可以破坏()条件。
A.互斥B.请求和保持C.不剥夺D.环路等待
22.在()的情况下,系统出现死锁。
A.计算机系统发生了重大故障
B.有多个阻塞的进程存在
C.若干个进程因竞争资源而无休止地相互等待他方释放已占有的资源
D.资源数大大小于进程数或进程同时申请的资源数大大超过资源总数
23.某系统中有3个并发进程,都需要同类资源4个,试问该系统不会发生死锁的最少资源数是()。
A.9B.10C.11D.12
24.某计算机系统中有8台打印机,有K个进程竞争使用,每个进程最多需要3台打印机。
该系统可能会发生死锁的K的最小值是()。
A.2B.3C.4D.5
解析:
3k<8+k=>k<4(n个进程共享m个同类资源,若每个进程都需要用该类资源,而且各进程对该类资源的最大需求量之和小于m+n。
则该系统不会因竞争该类资源而阻塞。
)
25.银行家算法是一种()算法。
A.解除死锁B.避免死锁C.预防死锁D.检测死锁
二、填空题
1.进程调度程序按____________从____________中选择一个进程;从而使之占用处理器运行。
2.进程调度算法常用的有____________、____________、____________、高优先权优先等几种。
3.进程的调度方式有两种,一种是____________,另一种是____________。
4.在____________调度算法中,按照进程进入就绪队列的先后顺序来分配处理机。
5.死锁是指在系统中的多个___________无限期等待永远也不会发生的条件。
6.死锁产生的四个必要条件是____________、____________、____________和____________。
7.银行家算法中,当一个进程提出的资源请求将导致系统从____________状态进入____________状态时,系统就拒绝它的资源请求。
8.对待死锁,一般应考虑死锁的预防、避免、检测和解除四个问题。
典型的银行家算法是属于____________,破坏环路等待条件是属于____________,而剥夺资源是____________的基本方法。
三、计算题
1、有4个进程P1,P2,P3,P4,它们进入就绪队列的先后次序为P1、P2、P3、P4,它们的优先数和需要的处理器时间如下表所示。
假定这四个进程执行过程中不会发生等待事件,忽略进行调度等所花费的时间,从某个时刻开始进程调度,请回答下列问题:
①写出分别采用“先来先服务”调度算法选中进程执行的次序、计算出各进程在就绪队列中的等待时间以及的平均等待时间;
②写出分别采用“非抢占式的优先数”(固定优先数)调度算法选中进程执行的次序、计算出各进程在就绪队列中的等待时间以及平均等待时间;
③写出分别采用“时间片轮转”(时间片大小为5)调度算法选中进程执行的次序、计算出各进程在就绪队列中的等待时间以及平均等待时间。
进程
处理器时间
优先数
P1
8
3
P2
6
1
P3
22
5
P4
4
4
2、在一个批处理单道系统中,采用响应比高者优先的作业调度算法。
当一个作业进入系统后就可以开始调度,假定作业都是仅计算,忽略调度花费的时间。
现有三个作业,进入系统的时间和需要计算的时间如表所示:
作业
进入系统时间
需要计算时间
开始时间
完成时间
周转时间
1
9:
00
60分钟
2
9:
10
45分钟
3
9:
25
25分钟
(1)求出每个作业的开始时间、完成时间及周转时间并填入表中。
(2)计算三个作业的平均周转时间应为多少
3、一系统具有150个存储单元,在T0时刻系统按下表所示分配给3个进程。
T0时刻系统资源分配状态表
进程
Maximumdemand
Currentallocation
P1
70
25
P2
60
40
P3
60
45
对下列请求应用银行家算法分别分析判定是否安全
(1)第4个进程P4到达,最大需求60个存储单元,当前请求分配25个单元。
(2)第4个进程P4到达,最大需求50个存储单元,当前请求分配35个单元。
如果是安全的,请给出一个可能的进程安全执行序列;如果是不是安全的,请说明原因。
四、问答题
1、何谓死锁产生死锁的原因和必要条件是什么
2、下列程序执行结果中a=为什么
{
……
a=55;
pid=fork();
if(pid==0){
a=99;
exit(0);
}
else{
wait(NULL);
printf(“a=%d\n”,a);
}
……
}
参考答案
一、单项选择题
1-5:
DDCBDB
6-10:
AABBC
11-15:
DBDCB
16-20:
DDCAC
21-25:
DCBCB
二、填空题
1.某种调度算法就绪队列
2.先来先服务短进程优先时间片轮转调度算法
3.剥夺式非剥夺式
4.先来先服务
5.进程
6.互斥请求和保持不剥夺环路等待
7.安全状态不安全状态
8.避免死锁预防死锁解除死锁
三、计算题
1、答:
先来先服务算法选择进程的顺序依次为P1、P2、P3、P4。
进程P1等待时间为0;
进程P2等待时间为8;
进程P3等待时间为8+6=14;
进程P4等待时间为8+6+22=36。
平均等待时间为(0+8+14+36)/4=
非抢占式的优先数算法选择进程的顺序依次为P3、P4、P1、P2。
进程P1等待时间为4+22=26;
进程P2等待时间为22+4+8=34;
进程P3等待时间为0;
进程P4等待时间为22。
平均等待时间为(26+34+0+22)/4=
时间片轮转进程调度顺序为P1、P2、P3、P4、P1、P2、P3、P3、P3、P3。
进程P1等待两次,时间为0+(5+5+4)=14;
进程P2等待两次,时间为5+(5+4+3)=17;
进程P3等待两次,时间为(5+5)+(4+3+1)=18;
进程P4等待1次,时间为5+5+5=15。
平均等待时间为(14+17+18+15)/4=16
2、
作业
进入系统时间
需要计算时间
开始时间
完成时间
周转时间
1
9:
00
60分钟
9:
00
10:
00
60分钟
2
9:
10
45分钟
10:
25
11:
10
120分钟
3
9:
25
25分钟
10:
00
10:
25
60分钟
平均周转时间:
60分钟+120分钟+60分钟=80分钟
3、
(1)P4的最大需求为60,当前请求分配为25,此刻系统剩余资源为40。
计算是否安全过程略,最终可找到一个安全序列{P3,P2,P1,P4}(结果不唯一)。
(2)P4得到35个单元后,系统剩余资源数为5,此时4个进程的剩余需求量均无法满足,故找不到一个安全序列,所以为不安全状态。
四、问答题
1、(略)
2、a的值是55。
因为父进程在创建子进程时,子进程继承了父进程的存储映像,因此,在子进程中变量a的值开始时均是父进程调用fork之前的值。
由于子进程具有自己的副本,因此修改子进程的变量不会影响父进程的值,反过来也一样。