先来先服务FCFS
最短寻道时间优先SSTF
扫描调度SCAN
它是一次只响应一个方向上的请求,这个方向上的请求都响应完了,再掉头处理另一个方向上的。
有点像电梯,向上时只要上面楼层还有人在等,就不会向下,故又叫电梯调度算法。
练习题
假设一个磁盘有100个柱面,编号为0~99,在完成了磁道25处的请求后,磁头当前正在磁道43处服务。磁盘请求的柱面按38、6、40、2、20、22、10的次序到达磁盘驱动器,寻道时每移动一个柱面需要10ms,计算以下算法的总寻道时间:
(1)先来先服务算法
(2)最短寻道时间优先算法
(3)电梯调度算法。
【解答】
- 磁盘请求的柱面为38、6、40、2、20、22、10,FCFS算法就按照请求到达地次序依次响应。
被访问的下一个磁道号 |
移动的磁道数 |
38
38
38 |
43
−
38
=
5
43-38=5
43−38=5 |
6
6
6 |
38
−
6
=
32
38-6=32
38−6=32 |
40
40
40 |
40
−
6
=
34
40-6=34
40−6=34 |
2
2
2 |
40
−
2
=
38
40-2=38
40−2=38 |
20
20
20 |
20
−
2
=
18
20-2=18
20−2=18 |
22
22
22 |
22
−
20
=
2
22-20=2
22−20=2 |
10
10
10 |
22
−
10
=
12
22-10=12
22−10=12 |
故先来先服务算法的总寻道时间为
10
∗
(
5
+
32
+
34
+
38
+
18
+
2
+
12
)
=
1410
m
s
10*(5+32+34+38+18+2+12)=1410ms
10∗(5+32+34+38+18+2+12)=1410ms
- 先将磁盘请求按磁道从小到大排个序:2、6、10、20、22、38、40,SSTF算法是先响应离自己(磁头所在磁道)最近的磁道上的请求。
当前在43,最近的是40。
被访问的下一个磁道号 |
移动的磁道数 |
40
40
40 |
43
−
40
=
3
43-40=3
43−40=3 |
38
38
38 |
40
−
38
=
2
40-38=2
40−38=2 |
22
22
22 |
38
−
22
=
16
38-22=16
38−22=16 |
20
20
20 |
22
−
20
=
2
22-20=2
22−20=2 |
10
10
10 |
20
−
10
=
10
20-10=10
20−10=10 |
6
6
6 |
10
−
6
=
4
10-6=4
10−6=4 |
2
2
2 |
6
−
2
=
4
6-2=4
6−2=4 |
故最短寻道时间优先算法的总寻道时间为
10
∗
(
3
+
2
+
16
+
2
+
10
+
4
+
4
)
=
410
m
s
10*(3+2+16+2+10+4+4)=410ms
10∗(3+2+16+2+10+4+4)=410ms
- 还是先将磁盘请求按磁道从小到大排个序:2、6、10、20、22、38、40,题目说了磁头是完成了磁道25处的请求后,当前正在磁道43处服务,可知磁头的移动方向是向外,循环扫描算法是先依次服务完当前方向上的再转头。
但是此时所在磁道43处以外已经没有请求了,所以掉头扫描,和SSTF算法结果一样,总寻道时间为
410
m
s
410ms
410ms。