课程设计报告
题 目 磁盘调度算法
课 程 名 称 操作系统课程设计
院部名称 信息技术学院
专 业 计算机科学与技术
班 级 09计算机科学与技术(1)
学 生 姓 名
学 号
课程设计地点 A105
课程设计学时 20
指 导 教 师
【注：根据课程设计大纲第四项具体要求撰写课程设计报告】
一、 程序设计的目的和要求
磁盘是经常使用的一个外设，对磁盘数据的寻道时间的长短直接影响机器的整体运行速度，本设计要求用C语言(或高级语言)编写程序模拟实现磁盘调度的常用算法。以加深对磁盘调度常用算法的理解和实现技巧。
二、 课程设计环境要求
1、硬件环境
Intel Croe 2 Duo CPU
2、软件环境
Windows7 Turbo C 2.0
三、 设计任务介绍及系统需求分析
1、系统分析
设备的动态分配算法与进程调度相似，也是基于一定的分配策略的。常用的分配策略有先请求先分配、优先级高者先分配等策略。在多道程序系统中，低效率通常是由于磁盘类旋转设备使用不当造成的。操作系统中，对磁盘的访问要求来自多方面，常常需要排队。这时，对众多的访问要求按一定的次序响应，会直接影响磁盘的工作效率，进而影响系统的性能。访问磁盘的时间因子由3部分构成，它们是查找（查找磁道）时间、等待（旋转等待扇区）时间和数据传输时间，其中查找时间是决定因素。因此，磁盘调度算法先考虑优化查找策略，需要时再优化旋转等待策略。
2、系统设计：
(1) 先来先服务．(First-Come，First-Served，FCFS):
这是一种简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。但此算法由于未对寻道进行优化，致使平均寻道时间可能较长。
(2) 最短寻道时间优先(ShortestSeekTimeFirst，SSTF):
该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，但这种调度算法却不能保证平均寻道时间最短。
(3) 扫描(SCAN)算法:
SCAN算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。例如，当磁头正在自里向外移动时，SCAN算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。这时，同样也是每次选择这样的进程来调度，即其要访问的磁道，在当前磁道之内，从而避免了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运行，故又称为电梯调度算法。
四、概要设计
本系统划分为三个模块：先来先服务算法模块void FCFS(int array[],int m)、最短寻道时间优先算法模块void SSTF(int array[],int m)、扫描算法模块void SCAN(int array[],int m)。
系统模块图
五、详细设计
1、先来先服务(FCFS)
这是一种简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。但此算法由于未对寻道进行优化，致使平均寻道时间可能较长。
先来先服务算法（FCFS）流程图：
2、最短寻道时间优先(SSTF)
该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，但这种调度算法却不能保证平均寻道时间最短。
最短寻道时间优先流程图：
3、扫描算法(SCAN)
SCAN算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。例如，当磁头正在自里向外移动时，SCAN算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。这时，同样也是每次选择这样的进程来调度，即其要访问的磁道，在当前磁道之内，从而避免了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运行，故又称为电梯调度算法。
六、测试数据和结果
1、先来先服务调度(FCFS)
输入起始磁道（你可以输入50），点确定，进入第二个界面，再输入你要输入的最大磁道（你可以输入100），然后点确定。选择磁盘调度算法1 2 3 中的任意一个，若选择1后确认，则随机输出10个小于100的磁道数(41 67 34 0 69 24 78 58 62 64)，则先来先服务调度(FCFS)输出：(41 67 34 0 69 24 78 58 62 64)，在选择1或者0，选着1则继续其它算法的磁盘调度，选着0则结束磁盘调度
运行结果图：
2、最短寻道时间优先调度(SSTF)
输入起始磁道（你可以输入50），点确定，进入第二个界面，再输入你要输入的最大磁道（你可以输入100），然后点确定。选择磁盘调度算法1 2 3 中的任意一个，若选择2后确认，则随机输出10个小于100的磁道数 (41 67 34 0 69 24 78 58 62 64) ,则最短寻道时间优先调度(SSTF)：(58 62 64 67 69 78 41 34 24 0) 。在选择1或者0，选着1则继续其它算法的磁盘调度，选着0则结束磁盘调度
运行结果图：
3、扫描调度算法(SCAN)
输入起始磁道（你可以输入50），点确定，进入第二个界面，再输入你要输入的最大磁道（你可以输入100），然后点确定。选择磁盘调度算法1 2 3 中的任意一个，若选择3后确认，则随机输出10个小于100的磁道数 ：(41 67 34 0 69 24 78 58 62 64)，则扫描调度算法(SCAN)：(58 62 64 67 69 78 41 34 24 0) 。
七、结论与体会
至此，计算机操作系统课程设计算法已经完成。此次设计基本完成了所规定的功能，但由于这次设计的时间比较仓促，其中不免会有些纰漏，比如在程序的实现上还不够严谨，出错处理不够完善等多方面问题，这些都有进一步改善。由于平时上课不是很认真许多概念没有理解清楚，导致在做设计时有点无从下手的感觉，只好边实验边看书直到弄懂概念后才开始做，最终在同学和老师的指导下我完成了设计。
此设计基本能够实现规定的要求但是还是不够完善，很多东西做的不够好，程序不够完善和严谨。此次课程设计中我学到了很多东西，无论在理论上还是实践中，都得到不少的提高，这对于我以后的工作和学习都有一种巨大的帮助。
八、参考文献
（1） 胡志刚，谭长庚等. 《计算机操作系统》.中南大学出版社. 2005
（2） 汤子瀛、哲凤屏、汤小丹. 《计算机操作系统》.西安电子科技大学出版社, 2001,8.
（3） 陈向群 杨芙清.《操作系统教程》. 北京大学出版社,2004,7.
（4） 张尧学 史美林.《计算机操作系统教程》. 清华大学出版社, 2000.
（5） 庞丽萍.《操作系统原理》(第三版). 华中理工大学出版社,2000.
（6） 罗宇，邹鹏等.《操作系统》(第2版). 电子工业出版社. 2007.4
附件：源程序清单
#include "stdio.h"
#include "stdlib.h"
void CopyL(int Sour[],int Dist[] ,int x); //数组Sour复制到数组Dist，复制到x个数
void SetDI(int DiscL[]); //随机生成磁道数
void Print(int Pri[],int x); //打印输出数组Pri
void DelInq(int Sour[],int x,int y); //数组Sour把x位置的数删除，并把y前面的数向前移动，y后的数保持不变(即会出现2个y)
void FCFS(int Han,int DiscL[]); //先来先服务算法(FCFS)
void SSTF(int Han,int DiscL[]); //最短寻道时间优先算法(SSTF)
int SCAN(int Han,int DiscL[],int x,int y); //扫描算法(SCAN)
void CSCAN(int Han,int DiscL[]); //循环扫描算法(CSCAN)
void PaiXu(); //寻道长度由低到高排序
void Pri();
int NAll=0;
int Best[5][2]; //用作寻道长度由低到高排序时存放的数组
int Limit=0; //输入寻找的范围磁道数i
int Jage;
float Aver=0;
int main()
{
int i;
int DiscLine[10]; //声明准备要生成的随机磁道号的数组
int Hand; //磁道数
int Con=1;
int n;
while(Con==1)
{
Jage=0;
printf("\n 请输入初始的磁道数:");
scanf("%d",&Hand);
printf("\n+ 输入寻找的范围:");
scanf("%d",&Limit);
if(Limit＞65536){
printf("超出磁道范围!");
}
else{
printf("1.先来先服务算法(FCFS )\n");
printf("2.最短寻道时间优先算法(SSTF)\n");
printf("3.扫描算法(SCAN) \n");
scanf("%d",&n);
if(n==0) exit(0);
printf("\n");
switch(n)
{
case 1:
SetDI(DiscLine); //随机生成磁道数
FCFS(Hand,DiscLine); //先来先服务算法(FCFS)
break;
case 2:
SetDI(DiscLine); //随机生成磁道数
SSTF(Hand,DiscLine); //最短寻道时间优先算法(SSTF)
break;
case 3:
SetDI(DiscLine); //随机生成磁道数
SCAN(Hand,DiscLine,0,9); //扫描算法(SCAN)
break;
SetDI(DiscLine); //随机生成磁道数
FCFS(Hand,DiscLine); //先来先服务算法(FCFS)
SSTF(Hand,DiscLine); //最短寻道时间优先算法(SSTF)
SCAN(Hand,DiscLine,0,9); //扫描算法(SCAN)
}
printf("\n\n+ 是否继续(按0结束,按1继续)?");
scanf("%5d",&Con);
}
}
}
//数组Sour复制到数组Dist，复制到x个数
void CopyL(int Sour[],int Dist[] ,int x)
{
int i;
for(i=0;i＜=x;i++)
{
Dist[i]=Sour[i];
}
}
//打印输出数组Pri
void Print(int Pri[],int x)
{
int i;
for(i=0;i＜=x;i++)
{
printf("%5d",Pri[i]);
}
}
//随机生成磁道数
void SetDI(int DiscL[])
{
int i;
for(i=0;i＜=9;i++)
{
DiscL[i]=rand()%Limit;//随机生成10个磁道号
}
printf("+ 需要寻找的磁道号:");
Print(DiscL,9); //输出随机生成的磁道号
printf("\n");
}
//数组Sour把x位置的数删除，并把y前面的数向前移动，y后的数保持不变(即会出现2个y)
void DelInq(int Sour[],int x,int y)
{
int i;
for(i=x;i
{
Sour[i]=Sour[i+1];
x++;
}
}
//先来先服务算法(FCFS)
void FCFS(int Han,int DiscL[])
{
int RLine[10]; //将随机生成的磁道数数组Discl[]复制给数组RLine[]
int i,k,All,Temp; //Temp是计算移动的磁道距离的临时变量
All=0; //统计全部的磁道数变量
k=9; //限定10个的磁道数
CopyL(DiscL,RLine,9); //复制磁道号到临时数组RLine
printf("\n+ FCFS访问顺序为:");
All=Han-RLine[0];
for(i=0;i＜=9;i++)
{
Temp=RLine[0]-RLine[1];//求出移动磁道数,前一个磁道数减去后一个磁道数得出临时的移动距离
if(Temp＜0)
Temp=(-Temp);//移动磁道数为负数时,算出相反数作为移动磁道数
printf("%5d",RLine[0]);
All=Temp+All;//求全部磁道数的总和
DelInq(RLine,0,k);//每个磁道数向前移动一位
k--;
}
Best[Jage][1]=All;//Best[][1]存放移动磁道数
Best[Jage][0]=1; //Best[][0]存放算法的序号为:1
Jage++;//排序的序号加1
Aver=((float) All)/10;//求平均寻道次数
printf("\n+ 移动磁道数:＜%5d＞ ",All);
printf("\n+ 平均寻道长度:*%0.2f* ",Aver);
}
//最短寻道时间优先算法(SSTF)
void SSTF(int Han,int DiscL[])
{
int i,j,k,h,All;
int Temp; //Temp是计算移动的磁道距离的临时变量
int RLine[10]; //将随机生成的磁道数数组Discl[]复制给数组RLine[]
int Min;
All=0; //统计全部的磁道数变量
k=9; //限定10个的磁道数
CopyL(DiscL,RLine,9); //复制磁道号到临时数组RLine
printf("\n+ SSTF访问顺序为:");
for(i=0;i＜=9;i++)
{
Min=64000;
for(j=0;j＜=k;j++) //内循环寻找与当前磁道号最短寻道的时间的磁道号
{
if(RLine[j]＞Han) //如果第一个随机生成的磁道号大于当前的磁道号，执行下一句
Temp=RLine[j]-Han; //求出临时的移动距离
else
Temp=Han-RLine[j]; //求出临时的移动距离
if(Temp
{
Min=Temp; //Temp临时值赋予Min
h=j; //把最近当前磁道号的数组下标赋予h
}
}
All=All+Min; //统计一共移动的距离
printf("%5d",RLine[h]);
Han=RLine[h];
DelInq(RLine,h,k); //每个磁道数向前移动一位
k--;
}
Best[Jage][1]=All;//Best[][1]存放移动磁道数
Best[Jage][0]=2;//Best[][0]存放算法的序号为:2
Jage++;//排序序号加1
Aver=((float)All)/10;//求平均寻道次数
printf("\n+ 移动磁道数:＜%5d＞ ",All);
printf("\n+ 平均寻道长度:*%0.2f* ",Aver);
}
//扫描算法(SCAN)
int SCAN(int Han,int DiscL[],int x,int y)
{
int j,n,k,h,m,All;
int t=0;
int Temp;
int Min;
int RLine[10]; //将随机生成的磁道数数组Discl[]复制给数组RLine[]
int Order;
Order=1;
k=y;
m=2; //控制while语句的执行，即是一定要使当前磁道向内向外都要扫描到
All=0; //统计全部的磁道数变量
CopyL(DiscL,RLine,9); //复制磁道号到临时数组RLine
printf("\n+ SCAN访问顺序为:");
Min=64000;
for(j=x;j＜=y;j++) //寻找与当前磁道号最短寻道的时间的磁道号
{
if(RLine[j]＞Han) //如果第一个随机生成的磁道号大于当前的磁道号，执行下一句
Temp=RLine[j]-Han; //求出临时的移动距离
else
Temp=Han-RLine[j]; //求出临时的移动距离
if(Temp
{
Min=Temp; //Temp临时值赋予Min
h=j; //把最近当前磁道号的数组下标赋予h
}
}
All=All+Min;
printf("%5d",RLine[h]);
if(RLine[h]＞=Han){ //判动方向，即是由里向外还是由外向里断磁道的移
Order=0;
t=1;
}
Han=RLine[h];
DelInq(RLine,h,k); //每个磁道数向前移动一位
k--;
while(m＞0)
{
if(Order==1) //order是判断磁盘扫描的方向标签，order是1的话，磁道向内移动
{
for(j=x;j＜=y;j++)
{
h=-1;
Min=64000;
for(n=x;n＜=k;n++) //判断离当前磁道最近的磁道号
{
if(RLine[n]＜=Han)
{
Temp=Han-RLine[n];
if(Temp
{
Min=Temp; //Temp临时值赋予Min
h=n; //把最近当前磁道号的数组下标赋予h
}
}
}
if(h!=-1)
{
All=All+Min; //叠加移动距离
printf("%5d",RLine[h]);
Han=RLine[h]; //最近的磁道号作为当前磁道
DelInq(RLine,h,k);
k--;
}
}
Order=0; //当完成向内的移动，order赋予0，执行else语句，使磁道向外移动
m--; //向内完成一次，m减一次，保证while循环执行两次
}
else //order是0的话，磁道向外移动
{
for(j=x;j＜=y;j++)
{
h=-1;
Min=64000;
for(n=x;n＜=k;n++) //判断离当前磁道最近的磁道号
{
if(RLine[n]＞=Han)
{
Temp=RLine[n]-Han;
if(Temp
{
Min=Temp; //Temp临时值赋予Min
h=n; //把最近当前磁道号的数组下标赋予h
}
}
}
if(h!=-1)
{
All=All+Min; //叠加移动距离
printf("%5d",RLine[h]);
Han=RLine[h]; //最近的磁道号作为当前磁道
DelInq(RLine,h,k);
k--;
}
}
Order=1; //当完成向内的移动，order赋予0，执行else语句，使磁道向外移动
m--; //向内完成一次，m减一次，保证while循环执行两次
}
}
NAll=NAll+All;
if((y-x)＞5)
{
Best[Jage][1]=All;//Best[][1]存放移动磁道数
Best[Jage][0]=3;//Best[][0]存放算法的序号为:3
Jage++;//排序序号加1
Aver=((float)All)/10;//求平均寻道次数
printf("\n+ 移动磁道数:＜%5d＞ ",All);
printf("\n+ 平均寻道长度:*%0.2f* ",Aver);
}
if(t==1) printf("\n+ 磁道由内向外移动");
else printf("\n+ 磁道由外向内移动");
return(Han);
}