磁盘调度算法

实验六

磁盘调度算法

【实验目的】

通过这次实验，加深对磁盘调度算法的理解，进一步掌握先来先服务FCFS、最短寻道时间优先SSTF、SCAN和循环SCAN算法的实现方法。

【实验内容】

问题描述：

设计程序模拟先来先服务FCFS、最短寻道时间优先SSTF、SCAN和循环SCAN算法的工作过程。假设有n个磁道号所组成的磁道访问序列，给定开始磁道号m和磁头移动的方向（正向或者反向），分别利用不同的磁盘调度算法访问磁道序列，给出每一次访问的磁头移动距离，计算每种算法的平均寻道长度。

程序要求：

1）利用先来先服务FCFS、最短寻道时间优先SSTF、SCAN和循环SCAN算法模拟磁道访问过程。

2）模拟四种算法的磁道访问过程，给出每个磁道访问的磁头移动距离。

3）输入：磁道个数n和磁道访问序列，开始磁道号m和磁头移动方向（对SCAN和循环SCAN算法有效），算法选择1-FCFS，2-SSTF，3-SCAN，4-循环SCAN。

4）输出：每种算法的平均寻道长度。

实现提示：

用C++语言实现提示：

1）程序中变量定义参考（根据需要可添加）如下：

const int MaxNumber=100; int TrackOrder[MaxNumber]; int MoveDistance[MaxNumber]; double AverageDistance; bool direction;

2）页面置换的实现过程如下： ? 变量初始化；

? 接收用户输入磁道个数n和磁盘访问序列，选择算法1-FCFS，2-SSTF，3-SCAN，4-循环SCAN，输入开始磁盘号m和磁头移动方向；

? 根据用户选择的算法进行磁道访问，输出磁盘调度算法的模拟过程；

? 计算选择每次移动的磁头移动距离和算法的平均寻道长度；

?

输出选择算法的平均寻道长度。

实验要求：

1）上机前认真复习磁盘调度算法，熟悉FCFS、SSTF、SCAN和循环SCAN算法的过程；

2）上机时独立编程、调试程序；

3）根据具体实验要求，完成好实验报告（包括实验的目的、内

容、要求、源程序、实例运行结果截图、发现的问题以及解决方法）。 【实验分析】

需求分析：

(1) 按提示输入磁道个数，不得大于MaxNum；依次输入磁盘访问序列；按提示输入开始磁道号，磁头移动方向（1为磁道号增加方向,0为磁道号减少方向）；根据提示输入要进行的算法类型，1-FCFS，2-SSTF，3-SCAN，4-循环SCAN。

(2) 输出的形式：先输出每次访问的磁道号和移动的磁头移动距离，最后输出平均寻道长度。

(3) 程序所能达到的功能：根据用户选择的算法进行磁道访问，输出磁盘调度算法的模拟过程，输出每次移动的磁头移动距离和算法的平均寻道长度。

(4) 测试数据： 输入数据分别为：9

55 58 39 18 90 160 150 38 184 100 1 输入：1

输出：被访问的下一个磁道号55 移动距离（磁道数）45

被访问的下一个磁道号58 移动距离（磁道数）3 被访问的下一个磁道号39 移动距离（磁道数）19 被访问的下一个磁道号18 移动距离（磁道数）21

被访问的下一个磁道号90 移动距离（磁道数）72 被访问的下一个磁道号160 移动距离（磁道数）70 被访问的下一个磁道号150 移动距离（磁道数）10 被访问的下一个磁道号38 移动距离（磁道数）112 被访问的下一个磁道号184 移动距离（磁道数）146 平均寻道长度：55.3333 输入：2

输出：被访问的下一个磁道号90 移动距离（磁道数）10

被访问的下一个磁道号58 移动距离（磁道数）32 被访问的下一个磁道号55 移动距离（磁道数）3 被访问的下一个磁道号39 移动距离（磁道数）16 被访问的下一个磁道号38 移动距离（磁道数）1 被访问的下一个磁道号18 移动距离（磁道数）20 被访问的下一个磁道号150 移动距离（磁道数）132 被访问的下一个磁道号160 移动距离（磁道数）10 被访问的下一个磁道号184 移动距离（磁道数）24 平均寻道长度：27.5556 输入：3

输出：被访问的下一个磁道号150 移动距离（磁道数）50

被访问的下一个磁道号160 移动距离（磁道数）10 被访问的下一个磁道号184 移动距离（磁道数）24 被访问的下一个磁道号90 移动距离（磁道数）94

被访问的下一个磁道号58 移动距离（磁道数）32 被访问的下一个磁道号55 移动距离（磁道数）3 被访问的下一个磁道号39 移动距离（磁道数）16 被访问的下一个磁道号38 移动距离（磁道数）1 被访问的下一个磁道号18 移动距离（磁道数）20 平均寻道长度：27.7778 输入：4

输出：被访问的下一个磁道号150 移动距离（磁道数）50

被访问的下一个磁道号160 移动距离（磁道数）10 被访问的下一个磁道号184 移动距离（磁道数）24 被访问的下一个磁道号18 移动距离（磁道数）166 被访问的下一个磁道号38 移动距离（磁道数）20 被访问的下一个磁道号39 移动距离（磁道数）1 被访问的下一个磁道号55 移动距离（磁道数）16 被访问的下一个磁道号58 移动距离（磁道数）3 被访问的下一个磁道号90 移动距离（磁道数）32 平均寻道长度：35.7778 概要设计：

(1)本程序中用到的数据的定义：

const int MaxNumber=100;

int TrackOrder[MaxNumber];//存放磁盘访问序列 int MoveDistance[MaxNumber];//存放每次的寻道长度 int VisitOrder[MaxNumber];//存放访问的顺序 bool direction;//磁头移动方向 int n;//磁道个数 int m;//开始磁道号 (2)主程序的流程:

变量初始化=》用户选择执行的算法=》若不符合条件，则退=》若符合，执行算法=》输出结果

(3)各程序模块之间的层次(调用)关系。

主程序调用初始化模块以及算法模块、输出模块

详细设计

实现程序模块的具体算法。 #include using namespace std; const int MaxNumber=100;

int TrackOrder[MaxNumber];//存放磁盘访问序列 int MoveDistance[MaxNumber];//存放每次的寻道长度 int VisitOrder[MaxNumber];//存放访问的顺序 bool direction;//磁头移动方向 int n;//磁道个数 int m;//开始磁道号

出 void init(){//变量初始化 cout<<\输入磁道个数\ cin>>n;

cout<<\磁盘访问序列\ for(int i=0;i>TrackOrder[i]; }

cout<<\输入开始磁道号\ cin>>m;

cout<<\输入磁头移动方向,1为磁道号增加方向,0为磁道号减少方向\

cin>>direction; }

void fcfs(){

for(int i=0;i

MoveDistance[i]=m-TrackOrder[i]; else

MoveDistance[i]=TrackOrder[VisitOrder[i-1]]-TrackOrder[i];//按输入的磁盘访问序列寻道，寻道长度为前一个访问的磁道号减

当前访问的

} }

void shunxu(){//排序，从小到大排列磁盘访问序列 for(int i=1;i

if(TrackOrder[j]>TrackOrder[j+1]){ int temp=TrackOrder[j+1]; TrackOrder[j+1]=TrackOrder[j]; TrackOrder[j]=temp;//冒泡排序

} } } }

void sstf(){ shunxu(); int i; int temp; for(i=0;im){ temp=i;

break; }

}//找到小于开始磁道号的最后一个元素

if(abs(TrackOrder[temp]-m)>abs(TrackOrder[temp+1]-m)){//比较小于开始磁道号的最后一个元素和下一个元素哪个离开始磁道号远

VisitOrder[0]=temp+1;

MoveDistance[0]=TrackOrder[temp+1]-m; temp=temp+1; } else{

VisitOrder[0]=temp;

MoveDistance[0]=TrackOrder[temp]-m; }//取距离小的那个为第一个访问的元素 int h=temp-1; int k=temp+1; i=1;

while(h>-1&&k

if(abs(TrackOrder[h]-TrackOrder[VisitOrder[i-1]])>abs(TrackOrder[k]-TrackOrder[VisitOrder[i-1]])){

VisitOrder[i]=k;

MoveDistance[i]=TrackOrder[VisitOrder[i-1]]-TrackOrder[k];

++i; k++; } else{

VisitOrder[i]=h;

MoveDistance[i]=TrackOrder[VisitOrder[i-1]]-TrackOrder[h];

++i; h--; } }

if(h==-1){ for(;k

MoveDistance[i]=TrackOrder[VisitOrder[i-1]]-TrackOrder[k];

++i; } } else{

for(;h>-1;--h){ VisitOrder[i]=h;

MoveDistance[i]=TrackOrder[VisitOrder[i-1]]-TrackOrder[h];

++i; } } }

void scan(){ shunxu(); int k,i; k=1;

int temp;

if(direction){//若向磁道号增加方向访问 for(i=0;i

if(TrackOrder[i]>100){//找到第一个大于开始磁道号的元素

temp=i;

VisitOrder[0]=i;

MoveDistance[0]=TrackOrder[i]-100; break; } } ++i;

while(i

MoveDistance[k]=TrackOrder[VisitOrder[k-1]]-TrackOrder[i];

++i; ++k; }

i=temp-1;//遍历完后，回到刚刚第一个大于开始磁道号的元素的前一个向前遍历

while(i>-1){ VisitOrder[k]=i;

MoveDistance[k]=TrackOrder[VisitOrder[k-1]]-TrackOrder[i];

--i; ++k; } }

else{//若向磁道号减小方向访问 for(i=0;i

if(TrackOrder[i+1]>100){//找到最后一个小于磁道号的元素

temp=i;

VisitOrder[0]=i;

MoveDistance[0]=TrackOrder[i]-100; break; } }

--i;//向前遍历 while(i>-1){ VisitOrder[k]=i;

MoveDistance[k]=TrackOrder[VisitOrder[k-1]]-TrackOrder[i];

--i; ++k; }

i=temp+1;//遍历完后，回到刚刚最后一个小于开始磁道号的元素的后一个向后遍历

while(i

MoveDistance[k]=TrackOrder[VisitOrder[k-1]]-TrackOrder[i];

++i; ++k; } } }

void cscan(){

shunxu(); int k,i; k=1; int temp;

if(direction){//若向磁道号增加方向访问 for(i=0;i

if(TrackOrder[i]>100){//找到第一个大于开始磁道号的元素

temp=i;

VisitOrder[0]=i;

MoveDistance[0]=TrackOrder[i]-100; break; } } ++i;

while(i

MoveDistance[k]=TrackOrder[VisitOrder[k-1]]-TrackOrder[i];

++i; ++k;

}

i=0;//遍历完再从第一个元素开始遍历 while(i

MoveDistance[k]=TrackOrder[VisitOrder[k-1]]-TrackOrder[i];

++i; ++k; } }

else{//若向磁道号减小方向访问 for(i=0;i

if(TrackOrder[i+1]>100){//找到最后一个小于磁道号的元素

temp=i;

VisitOrder[0]=i;

MoveDistance[0]=TrackOrder[i]-100; break; } }

--i;//向前遍历

while(i>-1){ VisitOrder[k]=i;

MoveDistance[k]=TrackOrder[VisitOrder[k-1]]-TrackOrder[i];

--i; ++k; }

i=n-1;//遍历完后从最后一个元素向前遍历 while(i>temp){ VisitOrder[k]=i;

MoveDistance[k]=TrackOrder[VisitOrder[k-1]]-TrackOrder[i];

--i; ++k; } } }

void output(){

int sum=0;//求磁道数总和 for(int i=0;i

被

访

问

的

下

一

个

磁

道

号

\移动距离（磁道数）\

sum=sum+abs(MoveDistance[i]); }

cout<<\平均寻道长度：\输出平均寻道长度

}

void main(){ init(); int a;

cout<<\选择算法，1-FCFS，2-SSTF，3-SCAN，4-循环SCAN\

cin>>a; switch(a){ case(1):

fcfs();break; case(2):

sstf();break; case(3):

scan();break; case(4):

cscan();break;

}//根据用户选择的算法进行磁盘调度算法 output(); } 调试分析

1、 执行算法前，要先申请变量。

2、 执行后面三种算法时，要注意先将磁道序列从小到大排序。 3、 执行SSTF算法时，先找到小于开始磁道号的最后一个元素，

以此元素为分割点，向前和向后遍历序列，每次移动一个，比较出离前一个访问的磁道号近的访问。

4、 执行SCAN和CSCAN算法时，要先判断用户输入的是向磁道

号增加的方向执行还是向磁道号减少的方向执行。 5、 时间的复杂度是O(n). 用户使用说明

按提示输入磁道个数，不得大于MaxNum；依次输入磁盘访问序列；按提示输入开始磁道号，磁头移动方向（1为磁道号增加方向,0为磁道号减少方向）；根据提示输入要进行的算法类型，1-FCFS，2-SSTF，3-SCAN，4-循环SCAN。

测试结果

输入数据分别为：9

55 58 39 18 90 160 150 38 184 100 1 输入：1

输出：被访问的下一个磁道号55 移动距离（磁道数）45

被访问的下一个磁道号58 移动距离（磁道数）3 被访问的下一个磁道号39 移动距离（磁道数）19 被访问的下一个磁道号18 移动距离（磁道数）21 被访问的下一个磁道号90 移动距离（磁道数）72 被访问的下一个磁道号160 移动距离（磁道数）70 被访问的下一个磁道号150 移动距离（磁道数）10 被访问的下一个磁道号38 移动距离（磁道数）112 被访问的下一个磁道号184 移动距离（磁道数）146 平均寻道长度：55.3333

输入：2

输出：被访问的下一个磁道号90 移动距离（磁道数）10

被访问的下一个磁道号58 移动距离（磁道数）32 被访问的下一个磁道号55 移动距离（磁道数）3 被访问的下一个磁道号39 移动距离（磁道数）16 被访问的下一个磁道号38 移动距离（磁道数）1 被访问的下一个磁道号18 移动距离（磁道数）20 被访问的下一个磁道号150 移动距离（磁道数）132 被访问的下一个磁道号160 移动距离（磁道数）10 被访问的下一个磁道号184 移动距离（磁道数）24

平均寻道长度：27.5556

输入：3

输出：被访问的下一个磁道号150 移动距离（磁道数）50

被访问的下一个磁道号160 移动距离（磁道数）10 被访问的下一个磁道号184 移动距离（磁道数）24 被访问的下一个磁道号90 移动距离（磁道数）94 被访问的下一个磁道号58 移动距离（磁道数）32

被访问的下一个磁道号55 移动距离（磁道数）3 被访问的下一个磁道号39 移动距离（磁道数）16 被访问的下一个磁道号38 移动距离（磁道数）1 被访问的下一个磁道号18 移动距离（磁道数）20 平均寻道长度：27.7778

输入：4

输出：被访问的下一个磁道号150 移动距离（磁道数）50

被访问的下一个磁道号160 移动距离（磁道数）10 被访问的下一个磁道号184 移动距离（磁道数）24

被访问的下一个磁道号18 移动距离（磁道数）166 被访问的下一个磁道号38 移动距离（磁道数）20 被访问的下一个磁道号39 移动距离（磁道数）1 被访问的下一个磁道号55 移动距离（磁道数）16 被访问的下一个磁道号58 移动距离（磁道数）3 被访问的下一个磁道号90 移动距离（磁道数）32 平均寻道长度：35.7778

本文来源：https://www.bwwdw.com/article/h4y6.html