操作系统 I 磁盘调度

《操作系统概念（原书第9版）》

访问时间=传输速率+定位时间

传输速率 每秒数兆字节

在驱动器和计算机之间的数据流的速率

定位时间=寻道时间+旋转延迟 数毫秒

寻道时间

移动磁臂到所要柱面的所需时间

旋转延迟

旋转臂到所要扇区的所需时间

考虑一个磁盘队列，其I/O请求块的柱面的顺序如下：

磁头开始位于柱面53

先来先服务

最短寻道时间优先

选择处理距离当前磁头位置的最短寻道时间的请求

选择最接近磁头位置的待处理请求

扫描算法

磁臂从磁盘的一端开始，向另一端移动；

在移过每个柱面时，处理请求

当到达磁盘的另一端时，磁头移动方向反转，并继续处理

磁臂只需移到一个方向的最远请求为止

循环扫描

移动磁头从磁盘一端到磁盘另一端，并且处理行程上的请求

在移过每个柱面时，处理请求

当磁头到达另一端时，它立即返回到磁盘的开头，而并不处理任何回程上的请求

磁臂只需移到一个方向的最远请求为止

对于磁盘负荷较大的系统，SCAN和C-SCAN表现更好，因为它们不大可能造成饥饿问题

对于任何调度算法，性能在很大程度上取决于请求的数量和类型

1.假定一磁盘有200个柱面，编号为0-199，该磁盘在完成了柱面号为125的磁盘请求后，当前正在处理一个柱面号为143的请求。若后续的磁盘请求队列先后顺序为：

86,147,91,177,94,150,102,175,130

分别使用以下不同磁盘调度算法对该组磁盘请求进行响应，并解答问题。

 (a) FCFS(先来先服务)算法;

 (b) SSTF(最短寻道时间优先)算法;

 (c) SCAN(扫描)算法;

 (d) C-SCAN(循环扫描)算法;

 (e) Look(查找)算法

（1）分别写出利用不同算法调度时，各个请求的响应顺序以及存取臂的移动总量. （5分）

（2）在磁盘匀变速运动的情况下，加速度a、距离d和时间t的关系为。在磁盘的一次寻道中，前一半是匀加速运动，后一半是匀减速运动（加速度大小不变），假设磁盘转速为7200转/分钟，磁盘驱动器的平均延迟时间是多少？

如果寻道时间t与寻道距离L之间的关系可以表示为：，其中时间单位为毫秒，L是以柱面表示的寻道距离，请问在平均延迟时间内，可以寻道多少距离？

请根据上述的5种调度算法，分别计算磁盘请求队列的寻道时间，

并从寻道时间角度说明哪种磁盘调度算法的时间性能更好一些。（5分）

答案:   

（1）

(a) FCFS(先来先服务)算法 : 86,147,91,177,94,150,102,175,130 . 存取臂移动总量：565

(b) SSTF(最短寻道时间优先)算法: 147, 150, 130, 102, 94, 91, 86, 175, 177, 存取臂移动总量：162

(c) SCAN(扫描)算法: 147, 150, 175, 177, 130, 102, 94, 91, 86  ,存取臂移动总量：(199-143)+（199-86）=169 

(d) C-SCAN(循环扫描)算法: 147, 150, 175, 177, 199,0,86,91,94,102,130 ,存取臂移动总量：(199-143)+199+130=385

(e) Look：147, 150, 175, 177, 130, 102, 94, 91, 86,存取臂移动总量：125

（2）

第一问：

由7200 rpm，可以计算得到每秒120转：

7200/60 =120 转/秒

进一步， 转一圈需要8.33毫秒：

1/120*1000 = 8.33毫秒

磁盘驱动的平均延迟时间为8.33/2=4.167毫秒。

第二问：

由于t = 4.167

距离L= [（4.167-0.7561）/0.2439 ]2= 195道

第三问：

从寻道时间看，Look磁盘调度算法时间性能最好,其需要更短的寻道时间。

第四问：

从寻道时间看，Look磁盘调度算法时间性能最好,其需要更短的寻道时间。

2. 某磁盘磁头访问范围为200（编号为0~199），如果在为访问52的请求者服务后，当前正在为访问53号磁道的请求者服务，同时有若干个请求者在等待服务，它们依次要访问的编号为(以请求时间先后顺序排列)：（9分） 98, 183, 37, 122, 14, 124, 65, 67 （1） 请用先来先服务(FCFS)、最短寻道时间优先(SSTF)、扫描(SCAN)和循环扫描(CSCAN)算法进行磁盘调度时，试确定实际的服务次序。（6分） （2） 假设磁臂在寻道时相邻编号移动的平均时间为0.4ms，按实际服务次序计算  (1)中四种算法下磁臂移动的总距离以及总寻道时间。（3分）

参考答案：

（1）FCFS：

　　　总磁道数：640

　　　寻道时间：640*0.4

（2）SSTF：

　　　总磁道数：236

　　　寻道时间：236*0.4

（3）SCAN：

　　　总磁道数：208

　　　寻道时间：208*0.4

（4）C-SCAN：

　　　总磁道数：382

　　　寻道时间：382*0.4

3.已知磁盘访问队列98, 183, 37, 122, 14, 124, 65, 67（标号为柱面号），当前磁头位置为53。（10分） a) 请写出一种最优的磁头移动序列，并计算磁头移动距离。（5分） b) 请问这一序列和哪种调度算法的结果是一致的？（2分） c) 请问这种调度算法能否保证在任意情况下是最优的？为什么？（3分）

a）53, 37, 14, 65, 67, 98, 122, 124, 183 (53-14)+(183-14)=39+169=208

b）LOOK

c）不能，与磁头移动的初始移动方向有关

4.某磁盘磁头访问范围为1000（编号为0~999），如果在为访问365的请求者服务后，当前正在为访问350的请求者服务，同时有若干个请求者在等待服务，它们依次要访问的编号为(以请求时间先后顺序排列)： 128，879，697，480，110，381 （1） 分别用先来先服务(FCFS)、最短寻道时间优先(SSTF)、扫描(SCAN)和循环扫描(CSCAN)算法进行磁盘调度时，试确定实际的服务次序。 （2） 假设磁臂在寻道时相邻编号移动的平均时间为0.4ms，按实际服务次序计算(1)中四种算法下磁臂移动的总距离以及总寻道时间。

参考答案：

（1）FCFS：

　　　服务次序：(350)128，879，697，480，110，381

　　　总磁道数：(350-128)+(879-128)+(879-110)+(381-110)=2013

　　　寻道时间：2013*0.4=805.2ms

（2）SSTF：

　　　服务次序：(350)381，480，697，879，128，110

　　　总磁道数：(879-350)+(879-110)=1298

　　　寻道时间：1298*0.4=519.2ms

（3）SCAN：

　　　服务次序：(350)128，110，381，480，697，879

　　　总磁道数：(350-110)+(879-110)=1009

　　　寻道时间：1009*0.4=403.6ms

5.（3' x 3）已知磁道访问请求队列：98, 183, 37, 14, 122, 65, 124, 67，当前磁头位置为53，方向为53=>0，请分别计算FIFO（先进先出），SSTF（最短寻道时间优先），SCAN调度下响应所有请求的磁头移动距离，并写出每种调度的响应顺序。

答： FIFO: 53, 98, 183, 37, 14, 122, 65, 124, 67. (98-53)+(183-98)+(183-37)+(37-14)+(122-14)+(122-65)+(124-65)+(124-67)=45+85+146+23+108+57+59+57=580 SSTF: 53, 65, 67, 98, 122, 124, 183, 37, 14. 12+2+31+24+2+59+146+23=299 SCAN: 53, 37, 14, (0), 65, 67,  98, 122, 124, 183. 53+183=236

6.（4'）请问SSTF是否是磁头调度算法中最优的？为什么？（如果是最优的，请证明，否则请举出反例）

答：否。如5中示例。

7.（10'）设现有磁头访问请求队列98，83，137，122，14，124，67，65，当前磁头位置为23。请：

b) SSTF是否是最优的？为什么？（4'）。

答：a）SSTF: |23-14|+|14-65|+|65-67|+|67-83|+|83-98|+|98-122|+|122-124|+|124-137| =9+51+2+16+15+24+2+13=132

SCAN: |23-14|+|14-65|+|65-67|+|67-83|+|83-98|+|98-122|+|122-124|+|124-137|=2+51+2+16+15+24+2+13=132

b）SSTF未必最优，可能引起饥饿和不必要的抖动。（10'）设现有磁头访问请求队列98，83，137，122，14，124，67，65，当前磁头位置为50。请：

b) 请比较以上两种方法的优缺点（4'）。

答：a）SSTF: |50-65|+|65-67|+|67-83|+|83-98|+|98-122|+|122-124|+|124-137|+|137-14|=15+2+16+15+24+2+13+123=210

SCAN: |50-14|+|14-65|+|65-67|+|67-83|+|83-98|+|98-122|+|122-124|+|124-137|=36+51+2+16+15+24+2+13=159

b）SSTF未必最优，反而可能引起饥饿和不必要的抖动。SCAN和方向有关。