分类： LINUX
2008-12-09 00:44:58
#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
printf("\n+ 输入寻找的范围:");
scanf("%d",&Limit);
if(Limit>65536){
printf("超出范围!");
}
else{
printf(" ╭═══════════════╮ \n");
printf(" ║ 操作系统课程设计 ║ \n");
printf(" ╭═════┤ 磁盘调度算法 ├═════╮\n");
printf(" ║ ║ ║ ║\n");
printf(" ║ ╰═══════════════╯ ║\n");
printf(" ║ 1.先来先服务算法(FCFS) ║\n");
printf(" ║ ║\n");
printf(" ║ 2.最短寻道时间优先算法(SSTF) ║\n");
printf(" ║ ║\n");
printf(" ║ 3.扫描算法(SCAN) ║\n");
printf(" ║ ║\n");
printf(" ║ 4.循环扫描算法(CSCAN) ║\n");
printf(" ║ ║\n");
printf(" ║ 5.N步扫描算法(NStepScan) ║\n");
printf(" ║ ║\n");
printf(" ║ 6.各类算法的比较 ║\n");
printf(" ║ ║\n");
printf(" ║ ║\n");
printf(" ║ ╭───────────────────────╮ ║\n");
printf(" ╰═┤ 请输入你的选择的算法(输入0离开) ├═╯\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); //随机生成磁道数
N_Step_SCAN(Hand,DiscLine); //N步扫描算法(NStepScan)
break;
case 6:
SetDI(DiscLine); //随机生成磁道数
FCFS(Hand,DiscLine); //先来先服务算法(FCFS)
SSTF(Hand,DiscLine); //最短寻道时间优先算法(SSTF)
SCAN(Hand,DiscLine,0,9); //扫描算法(SCAN)
CSCAN(Hand,DiscLine); //循环扫描算法(CSCAN)
N_Step_SCAN(Hand,DiscLine); //N步扫描算法(NStepScan)
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
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);
}
//循环扫描算法(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=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
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);
}
//N步扫描算法(NStepScan)
void N_Step_SCAN(int Han1,int DiscL[])
{
int i,m,k;
int RLine1[10];
NAll=0;
m=2;
k=9; //限定10个的磁道数
i=-1;
CopyL(DiscL,RLine1,9); //复制磁道号到临时数组RLine
printf("\n+ 按照N_Step_SCAN算法磁道的访问顺序为:");
for(m=0;m<2;m++) //由于限定10磁道数，将10个磁道数分为两组，每组5个磁道数，每个组按照SCAN算法执行，该循环循环2次
{
Han1=SCAN(Han1,RLine1,i+1,i+5);
i=i+5;
}
Best[Jage][1]=NAll;//Best[][1]存放移动磁道数
Best[Jage][0]=5;//Best[][0]存放算法的序号为:5
Aver=((float)NAll)/10;//求平均寻道次数
printf("\n+ 移动磁道数:<%5d> ",NAll);
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;
}
}
}
}
一、设计内容
设计五个算法,分别是先来先服务算法,最短寻道时间优先算法,扫描(SCAN)算法,循环扫描(CSCAN)算法,NStepSCAN算法.由人工输入当前的磁道数,由系统随即生成要访问的磁道.
二、开发环境
操作系统:Rad Hat Linux ,开发环境:C语言.
三、分析设计
（一）实验原理.
磁盘是可被多个进程共享的设备。当有多个进程都请求访问磁盘时，应采用一种适当的调度算法，以使各进程对磁盘的平均访问(主要是寻道)时间最小。由于在访问磁盘的时间中，主要是寻道时间，因此，磁盘调度的目标应是使磁盘的平均寻道时间最少。
(1) 先来先服务．(First-Come，First-Served，FCFS):
这是一种简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。但此算法由于未对寻道进行优化，致使平均寻道时间可能较长。
(2) 最短寻道时间优先(ShortestSeekTimeFirst，SSTF):
该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，但这种调度算法却不能保证平均寻道时间最短。
(3) 扫描(SCAN)算法:
SCAN算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。例如，当磁头正在自里向外移动时，SCAN算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。这时，同样也是每次选择这样的进程来调度，即其要访问的磁道，在当前磁道之内，从而避免了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运行，故又称为电梯调度算法。
(4) 循环扫描(CSCAN)算法:
处理该进程的请求，致使该进程的请求被严重地推迟。为了减少这种延迟，CSCAN算法规定磁头单向移动。例如，只自里向外移动，当磁头移到最外的被访问磁道时，磁头立即返回到最里的欲访磁道，即将最小磁道号紧接着最大磁道号构成循环，进行扫描。
(5) N_Step_SCAN算法:
N步SCAN算法是将磁盘请求队列分成若干个长度为N的子队列,磁盘调度将按FCFS算法依次处理这些子队列.而每处理一个队列时又是按SCAN算法,对一个队列处理完后,再处理其他队列.当正在处理某子队列时,如果又出现新的磁盘I/O请求,便将新请求进程放进其他队列.
（二）程序结构
第一部分:程序的主要流程
(1) 手动输入当前的磁道号,该磁道号在0
(2) 手动输入要寻找磁道的范围.
(3) 主菜单,选择要进行磁道调度算法,此时会随机生成一个在第二步生成磁道范围以内的10个磁道数,由SetDI方法生成,再将生成的随机磁道号以数组形式作为参数被某个算法调用.例如,选择了case 1,则先调用SetDI方法,再执行FCFS算法.如下:
case 1:
SetDI(DiscLine); //随机生成磁道数
FCFS(Hand,DiscLine); //先来先服务算法(FCFS)
break;
第二部分: 部分的代码实现
(1) 就每个算法而言,都有调用一个子算法CopyL把函数SetDI随机生成的磁道数数组复制给RLine[],为什么要复制,原因是在整个程序中的最后一项功能是实现5种算法对一次随即生成的磁道数的比较,所以在每次调用一种算法时需要设置一个临时的数组Rline[]来存放.
(2)在这5个算法中都有一个字函数DelInq，该函数的作用是使每个磁道数向前移动一位，简单地以FCFS算法为例，这里只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--;
}
Han是当前磁道数，RLine[0]是第一个随机磁道数，Han-RLine[0]得到的是一次磁头移动的距离，再赋予All，即All是存放磁头移动的距离总和，for循环是执行10次，Temp变量是求出移动磁道数,前一个磁道数减去后一个磁道数得出临时的移动距离，All=Temp+All是求全部磁道数的总和之后是DelInq函数，使每个磁道数向前移动一位。例如随机生成的磁道数数组RLine是：
583 286 177 115 593 535 586 492 249 421
因为当前的磁道数是500，通过All=Han-RLine[0]语句得到All等于83，接下来是Temp=RLine[0]-RLine[1]，是583-286=297，此时All等于83+297=380，再通过DelInq整个RLine数组的每个元素向前移一位，如下图所示：
(3)如果选择”case 6: 各类算法的比较”,该比较是比较这5种算法的寻道长度的总和,由小到大的排序.算法由PaiXu()函数实现.具体是每种算法的最后都设置Best[][]的二维数组, Best[Jage][1]=All,All是磁道数总和,Jage视每种算法而定,例如FCFS为1,则Jage为1, SSTF为2,则Jage为2,Best[Jage][0]=1(用来唯一标识某个算法) .最后以PaiXu()算法,用冒泡法排序把5个算法的磁道数综合由小到大排序.
（三）数据结构：
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)
void N_Step_SCAN(int Han1,int DiscL[])N步扫描算法(NStepScan)
