实验5 磁盘调度算法模拟实验
【实验目的】
1）掌握几种常用的磁盘调度算法。 2）学会编写实现算法的C语言程序。
【条件要求】
1）认真阅读和掌握预备知识。 2）上机操作。
【预备知识】 一、磁盘简介
磁盘通常由若干个盘片（每片分两面）组成，每个盘片又划分若干个磁道（典型值为500～2000），每个磁道可以存放相同容量的数据。每个磁道上又分出若干个扇区（典型值为10～100），每个扇区通常都存储512个字节数据。在磁盘上存储数据，必须将磁盘格式化。 1.磁盘的类型
1）固定头磁盘。
这种磁盘在每条磁道上都有一个读/写磁头，所有的磁头都被装在一个刚性磁臂中。通过这些磁头可访问所有磁道，并进行并行读/写，从而有效地提高了磁盘的I/O速度。 这种结构主要用于大容量磁盘上。
2）移动头磁盘。
每一个盘面仅配有一个磁头，也被装入磁臂中。为了能访问该盘面上的所有磁道，该磁头必须能移动以进行寻道。可见，移动磁头仅能以串行方式读/写，致使其I/O速度较慢；但由于其结构简单， 故仍广泛应用于中小型磁盘设备中。 2.磁盘访问时间
磁盘访问时间＝寻道时间+旋转延迟时间+数据传输时间。
1）寻道时间：将磁头定位于相应磁道上的时间。当代磁盘平均为5ms～10ms。 2）转延迟时间：相应扇区旋转到磁头处的时间。与磁盘转速有关，硬盘转速为5400 r/m ～10000r/m，软盘转速为300 r/m ～600r/m。
3）传输时间：把数据从磁盘读出或向磁盘写入数据所经历的时间，速度较快。 对于一个典型磁盘，平均寻道时间为10ms，旋转延迟时间为3ms，读一个扇区所花时间为0.01875ms。可见寻道时间对磁盘性能影响较大。
二、几种常用的磁盘调度算法
磁盘是可供多个进程共享的设备，当有多个进程要求访问磁盘时，应采用一种调度算法，以使各进程对磁盘的平均访问时间尽可能少。而磁盘调度的最终目标是减少磁盘的平均寻道时间。
常用的调度算法有：先来先服务FCFS，最短寻道时间优先SSTF，扫描算法SCAN和循环扫描算法CSCAN。
例如：某磁盘共200个磁道，编号为0～199。某时刻磁头刚从第96磁道移动到第100磁道，目前正停在第100磁道上。之后该磁盘依次接收到的磁道请求分别为：55，58，39，18，90，160，150，38，184。请采用各种磁盘调度算法进行调度。 1.先来先服务FCFS(First-Come, First Served)
1）按照进程请求的先后顺序； 2）对所有进程而言是公平的；
3）当有许多进程时，性能上接近随机调度。 磁头访问次序为：
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)
1）选择磁头臂的移动距当前位置最近的磁盘I/O请求； 2）经常可以获得最小的寻道时间。 磁头访问次序为：
90，58，55，39，38，18，150，160，184 磁头移动距离为：
10，32，3，16，1，20，132，10，24 平均寻道长度为： 27.5
3.扫描(SCAN)算法
1）进程“饥饿”现象。
SSTF算法虽然能获得较好的寻道性能， 但却可能导致某个进程发生“饥饿”（Starvation）现象。因为只要不断有新进程的请求到达， 且其所要访问的磁道与磁头当前所在磁道的距离较近，这种新进程的I/O请求就必须优先满足。对SSTF算法略加修改后所
形成的SCAN算法， 可防止老进程出现“饥饿”现象。
2）SCAN算法。
（1）磁头臂只沿着一个方向移动，并在途中满足所有未完成的请求，直到到 达这个方向上的最后一个磁道；
（2）然后改变方向继续扫描。 磁头访问次序为：
150，160，184，90，58，55，39，38，18 磁头移动距离为：
50， 10， 24， 94，32， 3， 16， 1， 20 平均寻道长度为： 27.8
4.循环扫描(CSCAN)算法
1）限制只在一个方向上扫描；
2）当在一个方向上的最后一个磁道被访问之后，磁头臂返回磁盘的另一端再次开始扫描。
磁头访问次序为：
150，160，184，18，38，39，55，58，90 磁头移动距离为：
50，10，24，166，20，1， 16， 3， 32 平均寻道长度为： 35.8
【实验内容】
1）某磁盘共200个磁道，编号为0～199。某时刻磁头刚从第96磁道移动到第100磁道，目前正停在第100磁道上。之后该磁盘依次接收到的磁道请求分别为：55，58，39，18，90，160，150，38，184。
编写磁盘调度算法，显示磁道的服务顺序、移动的总道数以及平均寻道长度。 2）创建目录“ex17”，然后进入该目录。 # mkdir ex17 # cd ex17
3）使用Vi编辑一个新文件“exam17a.c”。 # vi exam17a.c
实现最短寻道时间优先（SSTF）调度算法，其内容如下： #include \#include \
void sstf(int current,int* queue,int len)
{
int i=0,j=0,count=0,sum=0,min=0; while(1) {
if(count==len) break; i=0;
while(queue[i]==-1) { i++;}
min=abs(current-queue[i]);
for(j=i+1;j if(queue[j]==-1) continue; if(abs(current-queue[j]) printf(\ sum=sum+abs(current-queue[i]); current=queue[i]; queue[i]=-1; count++; } printf(\ printf(\} main() { int current=100; int queue[9]={55,58,39,18,90,160,150,38,184}; sstf(current,queue,9); } 4）使用GCC编译器编译“exam17a.c”。 #gcc exam17a.c –o exam17a 5）执行exam17a。 #./exam17a 显示结果为： 90 58 55 39 38 18 150 160 184 sum＝248 average＝27.555556 6）使用Vi编辑一个新文件“exam17b.c”。 # vi exam17b.c 实现先来先服务（fcfs）磁盘调度算法，编译并执行显示调度后的顺序，要求显示结果如下： 55 58 39 18 90 160 150 38 184 sum＝498 average＝55.333333