-
一.银行家算法类
例题
1
:
在银行 家算法中,某
T0
时刻的资源分配情况如下:(有三类资源
A
、
B< br>、
C
,五个
进程
P0
、
P1
、
P2
、
P3
、
P4
)
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
3
3
2
P1
3
2
2
2
0
0
1
2
2
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
试问:
1.
该状态是否安全?
答:这是安全状态:
P1
的需求小于可用资源数,先满足
P1的请求,然后回收
P1
资源:可用资源变为
(
3,3,2)+(
2,0,0
)=(
5,3,2
);
这时
P3
可分配,
P3
结束后回收资源,
可用资源为
(
5,3 ,2
)+
(
2,1,1
)
=(
7,4,3
)
这时
P0
可分配,
P0
结束后回收资源,
可用资源为< br>(
7,4,3
)+
(
0,1,0
)
+(
7, 5,3
)
接下来是
P2
,结束后可用资源为(
7,5,3
)+(
3,0,2
)=(
10,5,5
)
最后分 配
P4
,结束后可用资源为(
10,5,5
)+(
0,0,2
)=(
10,5,7
)
这样得到一个安全序列:
P1
-
P3
-
P0
-
P2
-
P4
,所以
T0
状态是安全的。
2.
在
T0
时刻,
P1
发出请求
Request(1
,
1
,
2)
, 系统能否满足?为什么?
答:
T0
时刻
P1
请求(
1,1,2
)
<
可用资源数(
3,3,2
),可以直接满足。
例题
2
:
某系统有
A
、
B
、
C
、
D
四类资源可供五个进程
P1
、
P2
、
P3
、
P4
、
P5
共享。系统对这四类< br>资源的拥有量为
:A
类
3
个、
B
类
14个、
C
类
12
个、
D
类
12
个。进程 对资源的需求和分配
情况如下:
进程
已占有资源
最大需求数
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
)现在系统中的各类资源还剩余多少
答:剩余:
A:1
B:5
C:2
D:0
因为
P1
已经满足最大需求数,则
P1
资源最终是可回收,则可看做 剩余:
A:1
B:5
C3
D:2
(
2
)现在系统是否处于安全状态?为什么
答:是安全状态;因为按照剩余:
A:1
B:5
C3
D:2< br>(此时
P1
已经结束)分别按照顺序满
足各进程的最大需求是可以把全部进程完 成的(顺序可为:
P3
-->
P4
-->
P5
-->
p2
)
(
3
)如果现在进程
P 2
提出需要
A
类资源
0
个、
B
类资源
4< br>个、
C
类资源
2
个和
D
类资源
0
个 ,系统能否去满足它的请求?请说明原因
系统会去满足;若此时去满足,则剩余资源为:
A:1 B:1 C1 D:2
此时,各进程的状态:
已占有资源
最大需求数
A
B
C
D
A
B
C
D
P1
0
0
0
0
0
0
1
2
(已结束)
P2
1
4
2
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
按照各进程状态以及剩余资源, 可以知道之后
P3
,即可回收已分配的资源,即处安全状态
二.磁道算法类
1.
先来先服务(
FCFS
,
First Come First Servered
)
这是一种最简单的磁盘调度算法。它根据进程请求访问磁盘的先 后次序进行调度。此
算法的优点是公平、简单,且每个进程的请求都能依次地得到处理,不会出现某一进 程
长期得不到满足的情况。
但此算法由于未对寻道进行优化,
致使平均寻道时间可能较 长。
图示有
9
个进程先后提出磁盘
I/O
请求时,
FCFS
算法进行调度的情况,其平均寻道距
离较大,故
FCFS
算法仅适用于请求磁 盘
I/O
的进程数目较少的场合。
(从
100
号磁道开始)
被访问的下一个磁道号
55
58
39
18
90
160
150
38
184
移动距离(磁道数)
45
3
19
21
72
70
10
112
146
平均寻道长度:
55.3
2.
最短寻道时间优先(
SSTF,Shortest Seek Time First
)
该算法选择这样的进程:
其要求访问的磁道与当前磁头所在的 磁道距离最近,
以使每次
寻道的时间最短。但这种算法不能保证平均寻道时间最短。可能导致一 些请求无限期推延,
产生饥饿现象。
(从
100
号磁道开始)
被访问的下一个磁道号
90
58
55
39
38
18
150
160
184
平均寻道长度:
27.5
移动距离(磁道数)
10
32
3
16
1
20
132
10
24
3.
电梯调度算法
S CAN
:
不仅考虑当前磁道
的距离,
更优先考虑在磁道前进方向。
例 如,
当磁头正在自里向外移动时,
SCAN
算法所考虑的下一个访问对象,
应 是其欲访问的磁
道既在当前磁道之外,
又是距离最近的。
这样自里向外地访问,
直至再无更外的磁道需
要访问时,
才将磁臂换向为自外向里移动,
排除磁头在盘面上 的往复运动,
避免了出现
“
饥饿
”
现象。
(从
100
号磁道开始)
被访问的下一个磁道号
150
160
184
90
58
55
39
移动距离(磁道数)
50
10
24
94
32
3
16
38
18
平均寻道长度:
27.8
1
20
4.
循环扫描算法(
CSCAN,Circle Scan
)
(从
100
号磁道开始)
被访问的下一个磁道号
150
160
184
18
38
39
55
58
90
平均寻道长度:
35.8
移动距离(磁道数)
50
10
24
166
20
1
16
3
32
CAN
将进程分成
N
个队列,用
FCFS
算法处理每一个队列,而这堆队列则是SCAN
算法的
处理对象。
FCFS
(处理每个队列)
SCAN
(处理总体)
FCFS
(处理每个队列)
FCFS
(处理每个队列)
将进程分成两个队列,一个是正在处理的,用
SCAN
算法处理 。另一个是
摆放新请求的进程,留待完成正在处理的队列后执行。
例题:
设有三道作业,它们的提交时间及执行时间由下表给出
:
作业号
提交时间
执行时间
1
8.5
2.0
2
9.2
1.6
3
9.4
0.5
试计算在单道程序环境下,采用先来先服 务调度算法和最短作业优先调度算法时的平均
周转时间
(
时间单位
:
小时,以十进制进行计算;要求写出计算过程
)
(
10
分)
FCFS:
作业号
提交时间
执行时间
开始时间
完成时间
周转时间
1
8.5
2.0
8.5
10.5
2.0
2
9.2
1.6
10.5
12.1
2.9
3
9.4
0.5
12.1
12.6
3.2
平均周转时间
=(2.0+2.9+3.2)/3=2.7(
小时
)
SJF:
作业号
提交时间
执行时间
开始时间
完成时间
周转时间
1
8.5
2.0
8.5
10.5
2.0
2
9.2
1.6
11.0
12.6
3.4
3
9.4
0.5
10.5
11.0
1.6
平均周转时间
=(2.0+3.4+1.6)/3=2.3(
小时
)
例题:
假定当前磁头位于
100
号磁道,
进程 对磁道的请求序列依次为
55
,
58
,
39
,
18
,
90
,
160
,
150
,
38
,
180
。
当采用先来先服务和最短寻道时间优先算法时,
总的移动的磁道数 分别是多少?
(请给出寻道次序和每步移动磁道数)
(
8
分)
FCFS:
服务序列依次为
:55
,
58
,
39
,
18
,
90
,
160
,
150
,
38
,
180
移动的磁道数分别是
:
45,
3, 19, 21, 72,
70,
10, 112,142
总的移动的磁道数是
:494
SSTF:
服务序列依次为
:90
,
58
,
55
,
39
,
38
,
18
,
150
,
160
,
180
移动的磁道数分别是
:
10, 32,
3, 16,
1, 20, 132,
10,
20
总的移动的磁道数是
:244
三.信号量实现前趋图类
S2
d
S5
f
g
S6
a
c
S4
S1
b
S3
e
Var
a,b,c,d,e,f,g:semaphore:=0,0,0,0,0,0,0;
begin
parbegin
begin S1;
signal(a);
signal(b);
end;
begin wait(a);
S2;
signal(c);
signal(d);
end;
-
-
-
-
-
-
-
-
本文更新与2021-01-22 16:26,由作者提供,不代表本网站立场,转载请注明出处:https://www.bjmy2z.cn/gaokao/550443.html
-
上一篇:小学1-6年级英语知识点大全
下一篇:价值观量表综述