目 录
1. 需求分析..................................................................................................................... 2
2. 数据结构的设计........................................................................................................... 2
2.1 函数介绍............................................................................................................ 2
3.程序概要设计内容........................................................................................................ 2
3.1磁盘调度............................................................................................................ 2
3.1.1先来先服务（FCFS）.............................................................................. 2
3.1.2最短时间优先算法.................................................................................... 3
3.1.3扫描（SCAN）调度算法......................................................................... 3
3.1.4循环扫描（CSCAN）算法....................................................................... 3
4.程序详细设计及流程图................................................................................................. 4
4.1系统流程图......................................................................................................... 4
4.2先来先服务(FCFS).............................................................................................. 4
4.3最短寻道时间优先(SSTF).................................................................................... 5
4.4扫描算法(SCAN).................................................................................................. 5
4.5循环扫描(CSCAN)算法......................................................................................... 7
5.功能模块描述及使用说明.............................................................................................. 8
5.1先来先服务调度(FCFS)...................................................................................... 8
5.2最短寻道时间优先调度(SSTF)........................................................................... 8
5.3扫描调度算法(SCAN)........................................................................................ 9
5.4循环扫描算法(CSCAN).................................................................................... 10
6.心得体会及结束语....................................................................................................... 11
7.参考文献..................................................................................................................... 11
附源代码........................................................................................................................ 12
1. 需求分析
操作系统的任务之一就是有效的使用硬件。对于磁盘驱动器，满足这一要求意味着要有较快的访问速度和较宽的磁盘带宽。访问时间包括两个主要部分：寻道时间，旋转延迟。磁盘带宽是所传递的总的字节数除以从服务请求开始到最后传递结束时的总时间。可以通过使用好的访问顺序来调度磁盘I/O请求，提高访问速度和宽度。本程序模拟四种磁盘调度算法：先来先服务调度(FCFS)，最短寻道时间优先调度(SSTF)，扫描调度算法(SCAN)，循环扫描算法(CSCAN)。并通过比较，了解各种算法的优缺点。
2. 数据结构的设计
2.1 函数介绍
Hand:当前磁道号;
DiscLine[10]:随机生成的磁道号;
void SetDI(int DiscL[])生成随机磁道号算法;
void CopyL(int Sour[],int Dist[] ,int x) 数组Sour复制到数组Dist，复制到x个数（四）详细设计;
void DelInq(int Sour[],int x,int y) 数组Sour把x位置的数删除,x后的数组元素向前挪一位.
void PaiXu()寻道长度由低到高排序
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)
3.程序概要设计内容
3.1磁盘调度
在多道程序设计的计算机系统中，各个进程可能会不断提出不同的对磁盘进行读/写操作的请求。由于有时候这些进程的发送请求的速度比磁盘响应的还要快，因此我们有必要为每个磁盘设备建立一个等待队列。
3.1.1先来先服务（FCFS）
即先来的请求先被响应。FCFS策略看起来似乎是相当"公平"的，但是当请求的频率过高的时候FCFS策略的响应时间就会大大延长。FCFS策略为我们建立起一个随机访问机制的模型，但是假如用这个策略反复响应从里到外的请求，那么将会消耗大量的时间。为了尽量降低寻道时间，看来我们需要对等待着的请求进行适当的排序，而不是简单的使用FCFS策略。这个过程就叫做磁盘调度管理。有时候fcfs也被看作是最简单的磁盘调度算法。
3.1.2最短时间优先算法
要求访问的磁道，与当前磁头所在的磁道距离最近，以使每次的寻道时间最短。
3.1.3扫描（SCAN）调度算法
该算法不仅考虑到欲访问的磁道与当前磁道间的距离，更优先考虑的是磁头当前的移动方向。例如，当磁头正在自里向外移动时，SCAN算法所考虑的下一个访问对象，应是其欲访问的磁道，既在当前磁道之外，又是距离最近的。这样自里向外的访问，直至再无更外的磁道需要访问时，才将磁道换向自外向里移动。这时，同样也是每次选择这样的进程来调度，也就是要访问的当前位置内距离最近者，这样，磁头又逐步地从外向里移动，直至再无更里面的磁道要访问，从而避免了出现“饥饿”现像。
3.1.4循环扫描（CSCAN）算法
当磁头刚从里向外移动而越过了某一磁道时，恰好又有一进程请求访问此磁道，这时，该里程就必须等待，为了减少这种延迟，CSCAN算法规定磁头单向移动，而本实验过程中我们所设计的是磁头从里向外移动，而从外向里移动时只须改方向而已，本实验未实现。但本实验已完全能演示循环扫描的全过程。
4.程序详细设计及流程图
4.1系统流程图：
4.2先来先服务(FCFS):
这是一种简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。但此算法由于未对寻道进行优化，致使平均寻道时间可能较长。
先来先服务算法（FCFS）流程图：
4.3最短寻道时间优先(SSTF):
该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，但这种调度算法却不能保证平均寻道时间最短。
最短寻道时间优先流程图：
4.4扫描算法(SCAN):
SCAN算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。例如，当磁头正在自里向外移动时，SCAN算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。这时，同样也是每次选择这样的进程来调度，即其要访问的磁道，在当前磁道之内，从而避免了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运行，故又称为电梯调度算法。
扫描算法（scan）流程图
4.5循环扫描(CSCAN)算法:
处理该进程的请求，致使该进程的请求被严重地推迟。为了减少这种延迟，CSCAN算法规定磁头单向移动。例如，只自里向外移动，当磁头移到最外的被访问磁道时，磁头立即返回到最里的欲访磁道，即将最小磁道号紧接着最大磁道号构成循环，进行扫描。
循环扫描算法（cscan）流程图：
5.功能模块描述及使用说明
5.1先来先服务调度(FCFS)
输入起始磁道（你可以输入100），点确定，进入第二个界面，再输入你要输入的最大磁道（你可以输入50），然后点确定。选择磁盘调度算法1 2 3 4中的任意一个，若选择1后确认，则随机输出10个小于50的磁道数(41 17 34 0 19 24 28 8 12 14)，则先来先服务调度(FCFS)输出：(41 17 34 0 19 24 28 8 12 14)，在选择1或者0，选着1则继续其它算法的磁盘调度，选着0则结束磁盘调度
运行结果图：
5.2最短寻道时间优先调度(SSTF)
输入起始磁道（你可以输入100），点确定，进入第二个界面，再输入你要输入的最大磁道（你可以输入50），然后点确定。选择磁盘调度算法1 2 3 4中的任意一个，若选择2后确认，则随机输出10个小于50的磁道数 (5 45 31 27 11 41 45 42 27 36) ,则最短寻道时间优先调度(SSTF)：(45 45 42 41 36 31 27 27 11) 。在选择1或者0，选着1则继续其它算法的磁盘调度，选着0则结束磁盘调度.
运行结果图：
5.3扫描调度算法(SCAN)
输入起始磁道（你可以输入100），点确定，进入第二个界面，再输入你要输入的最大磁道（你可以输入50），然后点确定。选择磁盘调度算法1 2 3 4中的任意一个，若选择3后确认，则随机输出10个小于50的磁道数 ：(41 4 2 3 42 32 21 16 18 45)，则扫描调度算法(SCAN)：(45 42 41 32 21 18 16 4 3 2) 。在选择1或者0，选着1则继续其它算法的磁盘调度，选着0则结束磁盘调度。
运行结果图：
5.4循环扫描算法(CSCAN)
输入起始磁道（你可以输入100），点确定，进入第二个界面，再输入你要输入的最大磁道（你可以输入50），然后点确定。选择磁盘调度算法1 2 3 4中的任意一个，若选择4后确认，则随机输出10个小于50的磁道数 ：（47 26 21 38 19 12 17 49 35 44），则循环扫描算法(CSCAN)：（12 17 19 21 26 35 38 44 47 49）。
运行结果图：
6.心得体会及结束语
至此，计算机操作系统课程设计算法已经完成。此次设计基本完成了所规定的功能，但由于这次设计的时间比较仓促，其中不免会有些纰漏，比如在程序的实现上还不够严谨，出错处理不够完善等多方面问题，这些都有进一步改善。
由于平时上课不是很认真许多概念没有理解清楚，导致在做设计时有点无从下手的感觉，只好边实验边看书直到弄懂概念后才开始做设计导致时间有点紧张，最终在同学和老师的指导下我完成了设计，此设计基本能够实现规定的要求但是还是不够完善，很多东西做的不够好，程序不够完善和严谨。此次课程设计中我学到了很多东西，无论在理论上还是实践中，都得到不少的提高，这对于我以后的工作和学习都有一种巨大的帮助。
7.参考文献
（1） 汤小丹 梁红兵 哲凤屏 汤子瀛 编著. 《计算机操作系统》（第三版）.西安电子科技大学出版社. 2007.
（2） 谭浩强 编著.《C程序设计》（第三版）.清华大学出版社.2005
附源代码
#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 N_Step_SCAN(int Han1,int DiscL[]); //N步扫描算法(NStepScan)
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 请输入初始的磁道数(0<n<65536):");
scanf("%d",&Hand);
printf("\n+ 输入寻找的范围:");
scanf("%d",&Limit);
if(Limit>65536){
printf("超出范围!");
}
else{
printf(" *********************************************\n");
printf(" **************** 磁盘调度算法 ******************\n");
printf(" *********************************************\n");
printf(" * 1.先来先服务算法(FCFS) *\n");
printf(" * 2.最短寻道时间优先算法(SSTF) *\n");
printf(" * 3.扫描算法(SCAN) *\n");
printf(" * 4.循环扫描算法(CSCAN) *\n");
printf(" *********************************************\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;
case 4:
SetDI(DiscLine); //随机生成磁道数
CSCAN(Hand,DiscLine); //循环扫描算法(CSCAN)
break;
case 5:
SetDI(DiscLine); //随机生成磁道数
SetDI(DiscLine); //随机生成磁道数
FCFS(Hand,DiscLine); //先来先服务算法(FCFS)
SSTF(Hand,DiscLine); //最短寻道时间优先算法(SSTF)
SCAN(Hand,DiscLine,0,9); //扫描算法(SCAN)
CSCAN(Hand,DiscLine); //循环扫描算法(CSCAN)
PaiXu(); //寻道长度由低到高排序
printf("\n\n+ 寻道长度由低到高排序:");
for(i=0;i<5;i++)
{
printf("%4d ",Best[i][0]);
}
break;
}
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<y;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) //如果每求出一次的移动距离小于Min，执行下一句
{
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)
{
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)
{
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)
{
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);
}
//循环扫描算法(CSCAN)
void CSCAN(int Han,int DiscL[])
{
int j,h,n,Temp,m,k,All,Last,i;
int RLine[10]; //将随机生成的磁道数数组Discl[]复制给数组RLine[]
int Min;
int tmp=0;
m=2;
k=9;
All=0; //统计全部的磁道数变量
Last=Han;
CopyL(DiscL,RLine,9); //复制磁道号到临时数组RLine
printf("\n+ 按照CSCAN算法磁道的访问顺序为:");
while(k>=0)
{
for(j=0;j<=9;j++) //从当前磁道号开始，由内向外搜索离当前磁道最近的磁道号
{
h=-1;
Min=64000;
for(n=0;n<=k;n++)
{
if(RLine[n]>=Han)
{
Temp=RLine[n]-Han;
if(Temp<Min)
{
Min=Temp;
h=n;
}
}
}
if(h!=-1)
{
All=All+Min; //统计一共移动的距离
printf("%5d",RLine[h]);
Han=RLine[h];
Last=RLine[h];
DelInq(RLine,h,k);
k--;
}
}
if(k>=0)
{ tmp=RLine[0];
for(i=0;i<k;i++)//算出剩下磁道号的最小值
{
if(tmp>RLine[i]) tmp=RLine[i];
}
Han=tmp;//把最小的磁道号赋给Han
Temp=Last-tmp;//求出最大磁道号和最小磁道号的距离差
All=All+Temp;
}
}
Best[Jage][1]=All;//Best[][1]存放移动磁道数
Best[Jage][0]=4;//Best[][0]存放算法的序号为:4
Jage++;//排序序号加1
Aver=((float)All)/10;//求平均寻道次数
printf("\n+ 移动磁道数:<%5d> ",All);
printf("\n+ 平均寻道长度:*%0.2f* ",Aver);
}
void PaiXu()
{
int i,j,Temp;
for(i=0;i<5;i++)
{
for(j=0;j<4;j++)
{
if(Best[j][1]>Best[j+1][1]) //如果前一个算法的移动磁道距离大于后一个移动磁道数，执行下面语句
{
Temp=Best[j+1][1]; //从这起下三行执行冒泡法将移动距离大小排序，排完后则执行每个算法的排序
Best[j+1][1]=Best[j][1];
Best[j][1]=Temp;
Temp=Best[j+1][0]; //将每个算法的序号用冒泡法排序
Best[j+1][0]=Best[j][0];
Best[j][0]=Temp;
}
}
}
}