-
一．银行家算法类
例题
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年级英语知识点大全
下一篇：价值观量表综述