关键词不能为空

当前您在: 主页 > 高中公式大全 >

未置可否:习题解答——第4章调度与死锁

作者:高考题库网
来源:https://www.bjmy2z.cn/gaokao
2020-11-12 08:18
tags:死锁公式

中国美术学院要多少分-2019百强市排名

2020年11月12日发(作者:弘皎)
第4章 调度与死锁 思考与练习题


2.考虑下面的进程集合:
(1)
进程名 到达时间 处理时间
A 0 3
B 1 5
C 3 2
D 9 5
E 12 5

(2)
进程名 到达时间 处理时间
A 0 1
B 1 9
C 2 1
D 3 9

分别对以上两个进程集合,计算使用先来先服务(FCFS)、时 间片轮转法(时间片q=1)、短进程
优先(SPN)、最短剩余时间优先(SRT,时间片q=1)、 响应比高者优先(HRRN)及多级反馈队列
(MFQ,第1个队列的时间片为1,第i(i<1)个队 列的时间片q=2(i-1))算法进行CPU调度,请给
出各进程的完成时间、周转时间、带权周转时 间,及所有进程的平均周转时间和平均带权周转
时间。

解答:
(1)
先来先服务:
进程名 到达时间 处理时间 开始时间 完成时间 周转时间 带权周转时间
A 0 3 0 3 3 1
B 1 5 3 8 7 1.4
C 3 2 8 10 7 3.5
D 9 5 10 15 6 1.2
E 12 5 15 20 8 1.6
平均周转时间T=(3+7+7+6+8)5=315=6.2
平均带权周转时间W=(1+1.4+3.5+1.2+1.6)5=8.75=1.74


时间片轮转(q=1):
进程名 到达时间 处理时间 开始时间 完成时间 周转时间 带权周转时间
A 0 1
B 1 2
A 2 3
B 3 4
C 4 5
A 5 6 6-0=6 63=2
B 6 7
C 7 8 8-3=5 52=2.5
B 8 9
D 9 10
B 10 11 11-1=10 105=2
D 11 12
E 12 13
D 13 14
E 14 15
D 15 16
E 16 17
D 17 18 18-9=9 95=1.8
E 18 19
E 19 20 20-12=8 85=1.6
平均周转时间T=(6+5+10+9+8)5=385=7.6
平均带权周转时间W= (2+2.5+2+1.8+1.6)5=9.45=1.98


短进程优先:
进程名 到达时间 处理时间 开始时间 完成时间 周转时间 带权周转时间
A 0 3 0 3 3 33=1
B 1 5 5 10 9 95=1.8
C 3 2 3 5 2 22=1
D 9 5 10 15 6 65=1.2
E 12 5 15 20 8 85=1.6
平均周转时间T=(3+9+2+6+8)5=285=5.6
平均带权周转时间W=(1+1.8+1+1.2+1.6)5=6.65=1.32


最短剩余时间优先:
进程名 到达时间 处理时间 开始时间 完成时间 周转时间 带权周转时间
A 0 3 0 3 3 33=1
B 1 5 5 10 9 95=1.8
C 3 2 3 5 2 22=1
D 9 5 10 15 6 65=1.2
E 12 5 15 20 8 85=1.6
平均周转时间T=(3+9+2+6+8)5=285=5.6
平均带权周转时间W=(1+1.8+1+1.2+1.6)5=6.65=1.32



响应比高者优先:
进程名 到达时间 处理时间 响应比 开始时间 完成时间 周转时间 带权周转时间
A 0 3 0 3 3 33=1
B 1 5 (2+5)5=1.4 3 8 7 75=1.4
C 3 2 (0+2)2=1 8 10 7 72=3.5
D 9 5 10 15 6 65=1.2
E 12 5 15 20 8 85=1.6
平均周转时间T=(3+7+7+6+8)5=315=6.2
平均带权周转时间W=(1+1.4+3.5+1.2+1.6)5=8.75=1.74


多级反馈队列:第1个队列的时间片为1,第i(i<1)个队列的时间片q=2(i-1))即:
第1个队列的时间片q=1,第2个队列的时间片q=2, 第3个队列的时间片q=4(假定不可剥夺)
进程名 到达时间 处理时间 开始时间 完成时间 周转时间 带权周转时间
A 0 1
B 1 2
A 2 4 4-0=4 43=1.33
C 4 5
B 5 7
C 7 8 8-3=5 52=2.5
B 8 10 10-1=9 95=1.8
D 10 11
D 11 13
E 13 14
E 14 16
D 16 18 18-9=9 95=1.8
E 18 20 20-12=8 85=1.6
平均周转时间T=(4+5+9+9+8)5=355=7
平均带权周转时间W= (1.33+2.5+1.8+1.8+1.6)5=9.035=1.806

(2)
先来先服务:
进程名 到达时间 处理时间 开始时间 完成时间 周转时间 带权周转时间
A 0 1 0 1 1 1
B 1 9 1 10 9 1
C 2 1 10 11 9 9
D 3 9 11 20 17 1.89
平均周转时间T=(1+9+9+17)4=364=9
平均带权周转时间W=(1+1+9+1.89)4=3.22


时间片轮转(q=1):
进程名 到达时间 处理时间 开始时间 完成时间 周转时间 带权周转时间
A 0 1 1 1
B 1 2
C 2 3 1 1
B 3 4
D 4 5
B 5 6
D 6 7
B 7 8
D 8 9
B 9 10
D 10 11
B 11 12
D 12 13
B 13 14
D 14 15
B 15
D 16
B 17
D 18
D 19
平均周转时间T=(1+17+1+17)4=9
平均带权周转时间W=(1+1.89+1+1.89)4=1.45


短进程优先:
进程名 到达时间 处理时间 开始时间
A 0 1 0
B 1 9 1
C 2 1 10
D 3 9 11
平均周转时间T=9
平均带权周转时间W=3.22


最短剩余时间优先(q=1):
进程名 到达时间 处理时间 开始时间
A 0
B 1
C 2
B 3
… …
B 10
D 11
… …
D 19
平均周转时间T=7.25
平均带权周转时间W=1.25

进程名 到达时间 处理时间 开始时间
A 0 1 0
B 1 9 1
C 2 1 10
D 3 9 11
平均周转时间T=9
平均带权周转时间W=3.22

多级反馈队列:
进程名 到达时间 处理时间 开始时间
A 0
B 1
C 2
D 3
B 4
D 6
16
17
18
19
20


18-1=17

20-3=17


179=1.89

179=1.89
完成时间
1
10
11
20
周转时间
1
9
9
17
带权周转时间
1
1
9
1.89
完成时间
1
2
3
4

11
12

20
周转时间
1-0=1

3-2=1


11-1=10


20-3=17
带权周转时间
1

1


109=1.11


179=1.89
完成时间
1
10
11
20
周转时间
1
9
9
17
带权周转时间
1
1
9
1.89
完成时间
1
2
3
4
6
8
周转时间
1-0=1

3-2=1



带权周转时间
1

1



B
D
B
D
平均周转时间T=9
平均带权周转时间W=1.445



3.考虑系统中出现的情况:

2



P
1

P
2

P
3

P
4

P
5


R
1

0
2
0
2
0
当前状态
R
2
R
3

0 1
0 0
0 3
3 5
3 3
R
4

2
0
4
4
2
R
1

0
2
6
4
0
8
12
16
18
12
16
18
20


18-1=17
20-3=17


179=1.89
179=1.89
可用资源
1 0 0
仍然需求
R
2
R
3
R
4






最大需求
R
2
R
3
R
4

0 1 2
7 5 0
6 5 6
3 5 6
6 5 2
R
1






(1)计算每个进程还可能需要的资源,并填入表的“仍然需要”栏目中。
(2)系统当前是否处于安全状态?为什么?
(3)系统当前是否死锁?为什么?
(4)如果进程P
3
又有新的请求(0,2,0,0),系统是否可以安全地接受此请求?

解答:
14.(1)
进 当前状态 最大需求 仍然需求
R
2
R
3
R
4
R
1
R
2
R
3
R
4
R
1
R
2
R
3
R
4


R
1

P
1
0 0 1 2 0 0 1 2 0 0 0 0
P
2
2 0 0 0 2 7 5 0 0 7 5 0
P
3
0 0 3 4 6 6 5 6 6 6 2 2
P
4
2 3 5 4 4 3 5 6 2 0 0 2
P
5
0 3 3 2 0 6 5 2 0 3 2 0
(2)系统出于安全状态,
存在安全序列

(3)不会发生死锁,因为存在安全序列,进程按此顺序执行可保证不死锁。

(4)不可以接受新的请求,因为系统可用资源不足。(R2只有1个,而新请求P3需要2个)。


4.考虑有一个共有150个存储单元的系统,已经如下分配给三个进程:

进程 最大需求 已经占有
1 70 45
2 60 40
3 60 15

试确定下面新的请求是否安全。如果安全,请给出安全序列。
(1)第4个进程到达,它最多需要60个存储单元,最初需要25个单元。
(2)第4个进程到达,它最多需要60个存储单元,最初需要35个单元。

解答:
15.(1)

Need Available
进程 最大需求 已经占有
1 70 45 25
()
2 60 40 20
3 60 15 45
4 60 25 35
由上表可知它是安全的,其中一个安 全序列为;或;

(2)
Need Available
进程 最大需求 已经占有
1 70 45 25
()
2 60 40 20
3 60 15 45
4 60 35 25
由上表可知资源不足,没有安全序列,不安全。


5.有3个进程 共享4个资源,一次只能请求或释放一个资源,每个进程最大需要2个资源,
试说明系统不会发生死锁。
解答:
根据抽屉原理,3个进程分4个资源,总有1个进程得到2个资源,该进程将满足最大 需求而运行
完毕,它释放资源后,系统中剩余2个进程享用4个资源,这2个进程也将满足最大需求,所 以系
统不会发生死锁。



6.N个进程共享M个资源,一次 只能请求或释放一个资源,每个进程最大需要资源数不超过M,
并且所有进程最大需求的总和小于(M+ N),试说明系统不会发生死锁。

解答:方法一:
根据抽屉原理,3个进程分4 个资源,总有1个进程得到2个资源,该进程将满足最大需求而运行
完毕,它释放资源后,系统中剩余2 个进程享用4个资源,这2个进程也将满足最大需求,所以系
统不会发生死锁。


反证法:
设该系统发生死锁,即设k 个线程用尽了M 个资源,但都没达到其最大需求。已经
满足了需求的进程数为 N – K.

Xi 为线程i 所占用的资源数,Yi 为线程i还需要的资源数。Yi > =1 , 形成死锁。


X1 + X2 + X3 + X4 + …… + Xk = M
(X1 + X2 + …… + Xk)+ (Y1 + Y2 + …… + Yk)< M + N – (N – k)


Y1 + Y2 + …… + Yk < k
若Yi > = 1 , Y1 + Y2 + …… + Yk >= k, 矛盾,即该系统不可能发生死锁。

方法二:
(1)进程P1,P2,P3按顺序分别申请一个资源,这时系统中还剩一个资源。 然后P1得到剩下
的那一个资源,运行完毕再释放掉一个资源,这时系统中还是有一个剩余的资源,接下 来进程
P2得到一个资源,运行完毕后释放掉一个资源,最后P3得到P2释放的一个资源得以运行。安 全
序列,所以系统不会发生死锁。
(2)进程Pi,所需的资源数为Si。由题知M≧1,Si≦M
在N个进程中每次让所需资 源最小的进程Pmin(i)运行(每次申请一个资源),它所需的资源数为
Smin(i),运行完后 释放一个资源,此时系统中剩余的资源为M- Smin(i)+1个。Smin(i+1)为系统
中进程所需的第二小的资源数。
只要满足公式M-Smin(i)+1≧Smin(i+1)系统就不会发生死锁
要使M- Smin(i)+1≧Smin(i+1)
只需M+1≧Smin(i+1)+ Smin(i)
只需M+1≧2Smin(i) (放缩Smin(i+1)>Smin(i))
只需Smin(i)≦(M+1)2
因为M≧1 所以 2M≧M+1 即 M≧(M+1)2 所以 Smin(i)≦(M+1)2成立
所以系统不会发生死锁

清代皇帝顺序-乐器种类大全


国内大学-拼音声调表


星期一到星期日的英文-自信的


什么叫普通话-三倍角公式


高中家长会发言稿-送儿子上学


安徽文科分数线-广州服装设计学校


全国中学排名2019-广东省水利电力职业技术学院


英语经典句子-新航道雅思费用是多少



本文更新与2020-11-12 08:18,由作者提供,不代表本网站立场,转载请注明出处:https://www.bjmy2z.cn/gaokao/443196.html

习题解答——第4章调度与死锁的相关文章