学号 P1514032 专业 计算机科学与技术 姓名
实验日期 2017.12.7 教师签字 成绩
实验报告
【实验名称】 磁盘调度（二） 【实验目的】
磁盘调度中寻道时间直接影响到数据访问的快慢，处理好磁盘寻道时间是关键。分别采用扫描策略、循环扫描策略处理。
【实验原理】
1. 扫描算法（SCAN算法）
SCAN算法，也就是很形象的电梯调度算法。先按照一个方向(比如从外向内扫描)，扫描的过程中依次调度经过的磁道。当扫描到最里层的一个磁道时反向扫描直至所有磁道都被调度。
2.循环扫描算法（CSCAN算法）
CSCAN算法，循环扫描算法，它的思想是，访问完最里面一个要求服务的序列之后，从最外层的序号开始往里走。也就是始终保持一个方向，故称为循环扫描算法。
【数据结构和符号说明】
（1）数据结构和符号说明
编译语言：C++
数据结构：结构体数组
符号定义：
typedef struct Track//磁道结构体
{
int id;//磁道序列
int state=0;//是否访问过，未被访问置状态为0
} Track;
Track track[N];//最大磁道数为100
Track track1[N];//复制的磁道数组用于输出
int step[N];//移动距离
int num,i,current_track,num1; //当前磁道即部分中间变量
函数说明：
void init()//初始化程序
void input()//输入函数
void sort1()//从小到大排序
int abs(int a,int b)//相减的绝对值
int find_first_bignum()//寻找第一个最大值
int find_first_smallnum()//寻找第一个最小值
void SCAN(int up_or_down) //扫描算法
void CSCAN(int up_or_down) //循环扫描算法
void output(Track a[])//输出函数
void output_average_track()//输出平均寻道时间
int show()//显示用户界面//返回值为输入的选择项
流程图：
SCAN算法：
CSCAN算法（与SCAN算法基本类似）：
代码：
#include#define N 100
typedef struct Track
{
int id;//磁道序列
int state=0;//是否访问过，未被访问置状态为0
} Track;
Track track[N];//最大磁道数为100
Track track1[N];
int step[N];//移动距离
int num,i,current_track,num1;
void init()//初始化程序
{
num=0;
for (i=0; i{track[i].state=-1;//id置为1
track1[i].state=-1;
step[i]=-1;//移动距离为-1
}
}
void input()//输入函数
{
printf(\"输入当前磁道\\n\");
scanf(\"%d\
num1=current_track;
printf(\"输入要访问的磁道数目\\n\");
scanf(\"%d\
printf(\"输入要访问磁道序列\\n\");
for(i=0; iscanf(\"%d\}
void FCFS()//先来先服务
{
for(i=0; i{if((current_track-track[i].id)<0)//求移动距离
step[i]=track[i].id-current_track;
else
step[i]=current_track-track[i].id;//取绝对值
track[i].state=1;//状态置为1
current_track=track[i].id;//更新当前磁道
}
}
int abs(int a,int b)//相减的绝对值
{
return a-b>0?a-b:b-a;
}
int Serch_min_pos()//寻找到当前磁道最短的需求磁道
{
int min=45536;//最小距离标志
int pos;
for(int i=0; iif(track[i].state==1)continue;
else if(min>abs(track[i].id,current_track))//寻找最小距离
{
min=abs(track[i].id,current_track);
pos=i;
}
track[pos].state=1;
return pos;//返回在数组中的位置
}
void SSTF()//最短寻道优先
{
for(i=0; i{track1[i]=track[Serch_min_pos()];//更新到要输出的数组中
step[i]=abs(track1[i].id,current_track);//移动距离
current_track= track1[i].id;//标志
}
}
void output(Track a[])//输出函数
{
printf(\"\\n\\n <从%d号磁道开始>\\n\
printf(\"==================================================\\n\");//排班
printf(\"被访问的下一个磁道\\移动距离（磁道数）\\n\");
for(i=0; iprintf(\"\%4d\\||\%4d\\n\printf(\"==================================================\\n\");
}
void output_average_track()//输出平均寻道时间
{
double sum=0;//和
for(i=0; isum+=step[i];printf(\" 平均寻道长度%3.2f\\n\\n\\n\输出
}
int show()//显示用户界面
{
int choose;//选择
printf(\"\\n******************早期的磁盘调度算法******************\\n\");
printf(\"\\1、先来先服务(FCFS)\\n\");
printf(\"\\2、最短寻道时间优先（SSTF)\\n\");
printf(\"\\3、退出（EXIT）\\n\");
scanf(\"%d\
return choose;
}
int main()
{
do
{
init();
switch(show())//返回值是选择
{
case 1://FCFS
input();
FCFS();
output(track);
output_average_track();
break;
case 2://最短寻道
input();
SSTF();
output(track1);
output_average_track();
break;
case 3://退出
return 0;
default:
break;
}
}
while(1);
return 0;
}
截图：
主界面开始，输入选择先来先服务还是最短寻道优先，输入当前磁道，输入要访问的磁道，输入要访问的磁道序列。
SCAN算法
输入 当前磁道100 ,9个磁道，分别为55 58 39 18 90 160 150 38 184，此时选择方向向上
结果正确。
输入 当前磁道100 ,9个磁道，分别为55 58 39 18 90 160 150 38 184，此时选择方向向下
结果正确。
CSCAN算法
输入 当前磁道100 ,9个磁道，分别为55 58 39 18 90 160 150 38 184，此时选择方向向上
结果正确。
输入 当前磁道100 ,9个磁道，分别为55 58 39 18 90 160 150 38 184，此时选择方向向上
结果正确。
【小结与讨论】
1、扫描算法又称为电梯算法，其原理与电梯运行情况相似，即运行方向上的请求优先，若是访问方向向上，则先依次访问较大的磁道号至顶，再向下访问娇小的磁道号；若是访问方向向下，则先依次访问较小的磁道号至底，再向上访问娇大的磁道号。
2、循环扫描算法又称为单向电梯算法，若是访问方向向上，则向上依次访问完较大的磁道号后，返回最低端，依次向上访问较小的磁道号；若是访问方向向下，则向下依次访问完较小的磁道号后，返回最顶端，依次向下访问较大的磁道号。
3、此次实验我用两个数组分别存放了一个磁道表和复制的磁道表，根据两个算法的原理，只要将其进行排序，然后分别对两个数组进行正向和逆向的访问即可。
4、具体实现时，我将两种算法的两种初始扫描方向写在了一个函数之中，调用时通过参数scan和参数up_or_down设置。并设置了寻找大于当前数组的最近最小值和最近的大值进行选择结果，这是因为初始磁道号将磁道数组分成上下（高低地址）两块，这两块根据不同的扫描方向重新选择高低地址，又结合不同的算法决定正序排列还是反序排列。实现起来还是比较简单的。
5、由于CSCAN算法的思想是，访问完最里面一个要求服务的序列之后，从最外层的序号开始往里走。也就是始终保持一个方向。所以如果用循环队列实现，时间复杂度会更低，效率更高。
6、此次实验虽然较为简单，但还是发现了自己知识点有些方面的不足，让我更好的了解了磁盘调度的原理，使我收获颇多。
