课程设计报告
题 目 磁盘调度算法设计
课 程 名 称 操作系统课程设计
院部名称 信息技术学院
专 业 11计算机科学与技术
班 级11计算计科学与技术（2）
学 生 姓 名
学 号
课程设计地点 1318
课程设计学时 20
指 导 教 师
金陵科技学院教务处制
目 录
摘 要... II
1 前 言... 1
1.1目的... 1
1.2背景... 1
1.3 意义... 1
2 正文... 2
2.1课设要求... 2
2.2课设设备、环境... 2
2.3课设方法及步骤... 2
2.3.1设计方法：... 2
2.3.2设计步骤：... 4
2.4 实验、调试及测试结果与分析。... 9
3 结论... 11
4 参考文献... 12
5 附录... 12
摘 要
多道程序设计中，经常是若干个进程同时处于就绪状态，必须依照某种策略来决定那个进程优先占有处理机。因而引起进程调度。本实验模拟在单处理机情况下的处理机调度问题，加深对进程调度的理解。模拟实现FCFS、SSTF、SCAN算法，并计算及比较磁头移动道数。 本实验设计的目的是通过设计一个磁盘调度模拟系统，以加深对FCFS、最短寻道时间以及电梯等磁盘调度算法的理解。让我们更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解，加强动手能力。
本实验设计的目的是通过设计一个磁盘调度模拟系统，以加深对FCFS、最短寻道时间以及电梯等磁盘调度算法的理解。让我们更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解，加强动手能力。
关键字：磁盘调度 fcfs sstf scan算法
1 前 言
1.1目的
磁盘是经常使用的一种重要的外设，对磁盘数据的寻道时间的长短直接影响机器的整体运行速度，本设计要求用C语言（或高级语言）编写程序模拟实现磁盘调度的常用算法。以加深对磁盘调度常用算法的理解和实现技巧。
1.2背景
磁盘驱动调度对磁盘的效率有重要影响。磁盘驱动调度算法的好坏直接影响辅助存储器的效率，从而影响计算机系统的整体效率。磁盘调度在多道程序设计的计算机系统中，各个进程可能会不断提出不同的对磁盘进行读/写操作的请求。由于有时候这些进程的发送请求的速度比磁盘响应的还要快，因此我们有必要为每个磁盘设备建立一个等待队列，常用的磁盘调度算法有以下四种：先来先服务算法（FCFS），最短寻道时间优先算法（SSTF），扫描算法（SCAN），循环扫描算法（CSCAN）
1.3 意义
在多道程序系统中，低效率通常是由于磁盘类旋转设备使用不当造成的。操作系统中，对磁盘的访问要求来自多方面，常常需要排队。这时，对众多的访问要求按一定的次序响应，会直接影响磁盘的工作效率，进而影响系统的性能。访问磁盘的时间因子由3部分构成，它们是查找（查找磁道）时间、等待（旋转等待扇区）时间和数据传输时间，其中查找时间是决定因素。因此，磁盘调度算法先考虑优化查找策略，需要时再优化旋转等待策略。
2 正文
2.1课设要求
1）、设计一个函数完成先来先服务的磁盘调度功能。
2）、设计一个函数完成最短寻道时间优先的磁盘调度功能。
3）、设计一个函数完成电梯算法的磁盘调度功能。
2.2课设设备、环境
奔腾以上计算机，装有Turbo C 2.0软件
2.3课设方法及步骤
2.3.1设计方法：
本系统应该具有功能：设计一个函数完成先来先服务的磁盘调度功能，设计一个函数完成最短寻道时间优先的磁盘调度功能，设计一个函数完成电梯算法的磁盘调度功能，并设计一个函数实现文件保存功能。本系统 具有通用性，界面美观，操作方便考虑到了系统安全问题。相关信息应保存在文件中。本软件的性能很好：通过磁盘调度算法的模拟设计，了解磁盘调度的特点。磁盘调度算法是根据访问都指定的磁道（柱面）位置来决定执行次序的调度。其目的是尽可能地减少操作中的寻道时间。在磁盘盘面上，0磁道在盘面的外圈；号数越大，磁道戛靠近盘片的中心。通常采用FCFS（先来先服务）、SSTF（最短寻道时间）、SCAN（扫描）进行不同的磁盘调度。
该磁盘调度系统流程图如下：
图2.3.1.1
系统模块图如下：
图2.3.1.2
函数调用关系图
图2.3.1.3
2.3.2设计步骤：
下面我将详细地为你讲解本程序的FCFS（先来先服务）、SSTF（最短寻道时间）、SCAN（扫描）、C-SCAN（单向扫描）。
2.3.2.1 FCFS（先来先服务）算法
先来先服务是一种最简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平，简单，且每个进程的请求都能依次地得到处理，不会出现某一进程的请求长期得不到满足的情况。但是，此算法由于未对寻道进行优化，致使平均寻道时间可能较长。图2.4.2展示出有10个进程先后提出磁盘I/O请求时，按先来先服务算法进行调度的情况。这里，将进程号按他们发出请求的先后次序排队。
这样，平均寻道距离为53.1条磁道，与后面将讲到的几种调度算法相比，其平均寻道距离较大，故先来先服务算法仅适用于请求磁盘I/O的进程数目较少的场合。
程序设计流程图为：
图2.3.2.1
我们通过程序
for(i=0;i
{ sum+=abss(p[i]-start);
start=p[i];
}来实现该算法。
2.3.2.2 SSTF（最短寻道时间）算法
该算法选择这样的进程，其要求访问的磁道，与当前磁头所在的磁道距离最近，以使得每次的寻道时间最短，但是这种算法不能保证平均寻道时间最短。图2.4.3展示出最短寻道时间优先算法进行调度时，各进程被调度的次序，每次磁头移动的距离，以及9次磁头平均移动距离。
比较图2.4.2和图2.4.3可以看出，最短寻道时间优先算法的平均每次磁头移动距离，明显低于先来先服务的距离，因而最短寻道时间优先算法较之先来先服务有更好的寻道性能，故过去曾一度被广泛采用。
程序设计流程图为：
图 2.3.2.2
我们通过程序
for(i=0;i
{ min=abss(p[0]-start);
for(j=0;j
{ if(min＞=abss(p[j]-start))
{ min=abss(p[j]-start);
current=j;
}
}
temp[len++]=p[current];
sum+=fabs(p[current]-start);
start=p[current];
for(j=current+1;j
p[j-1]=p[j];
num--;
}来实现最短寻道时间优先算法。
2.3.2.3 SCAN（电梯调度）算法
该算法不仅考虑到欲访问的磁道与当前磁道间的距离，更优先考虑的是磁头当前的移动方向。例如，当磁头正在自里向外移动时，电梯调度算法所考虑的下一个访问对象，应是其欲访问的磁道既在当前磁道之外，又是距离最近的。
这样自里向外地访问，直至再无更外的磁道需要访问时，才将磁臂向为自外向里移动。这时，同样也是每次选择这样的进程来调度，即要访问的磁道在当前位置内距离最近者，这样，磁头又逐步地从外向里移动，直至再无更里面的磁道要访问，从而避免了出现“饥饿”现象。由于在这种算法中磁头移动的规律颇似电梯的运行，因而又常称之为电梯调度算法。
我们使用语句printf("请选择移动臂初始方向(1增加0减小)：");来实现另一个功能，用户可以选择相对当前磁道位置增加或者减少的方向移动，其中用1代表向上移动，0代表向下移动。从而使功能更加强大。
程序设计流程图为：
图 2.3.2.3
我们通过语句
for(i=0;i
temp[i]=max[i];
for(i=0;i
temp[max_len++]=min[i];
for(i=0;i
{ sum+=abss(temp[i]-start);
start=temp[i];
}来实现向增加方向移动功能。
与此相同我们通过语句
for(i=0;i
temp[i]=min[i];
for(i=0;i
temp[min_len++]=max[i];
for(i=0;i
{ sum+=fabs(temp[i]-start);
start=temp[i];
} 来实现向减小方向移动功能。
电梯调度算法既能获得较好的寻道性能，又能防止“饥饿”现象，故被广泛用于大，中，小型机器和网络中的磁盘调度，但是也存在这样的问题：当磁头刚从里向外移动而越过了某一磁道时，恰好又有一进程请求访问此磁道，这时，该进程必须等待，待磁头继续从里向外，然后再从外向里扫描完所有要访问的磁道后，才处理该进程的请求，致使该进程的请求被大大地推迟。
2.3.2.4保存文件
我们通过程序
fp=fopen("cidao.txt","a");
if(fp==NULL)
printf("文件打不开！\n");
else{ fprintf(fp,"%s\n",p);
for(i=0;i
{
if(i)
fprintf(fp,"-＞");
fprintf(fp,"%d",file[i])；
｝
}来实现保存功能。
我们可以将运行的结果存储到记事本中，方便快捷。
2.4 实验、调试及测试结果与分析。
本程序可算是经历了一番周折，最后总算调试成功。下面我来介绍一下本程序的运行方法以及分析运行结果。
为了实现磁盘调度，我们设计了3种算法。另外增加了保存文件功能。如图所示：
图2.4.1
我们程序的主菜单，我们可以通过提示选择我们想要的相关算法
图2.4.2
展示出选择1先来先服务算法的执行结果，屏幕展示出最短寻道时间优先顺序，以及移动的总道数，平均寻道长度，还有提出询问，是否保存文件。
图2.4.3
展示出选择2最短寻道时间优先算法的执行结果，屏幕展示出最短寻道时间优先顺序，以及移动的总道数，平均寻道长度，还有提出询问，是否保存文件。
图2.4.4
展示出选择3电梯调度算法的执行结果，程序给出提示，选择0程序将向相对当前磁道位置减少的方向移动，屏幕上显示出最短寻道时间优先顺序，以及移动的总道数，平均寻道长度，还有提出询问，是否保存文件。
图2.4.5
展示出选择3电梯调度算法的执行结果，程序给出提示，选择1程序将向相对当前磁道位置增加的方向移动，屏幕上显示出最短寻道时间优先顺序，以及移动的总道数，平均寻道长度，还有提出询问，是否保存文件。
3 结论
这个程序基本完成了磁盘调度算法设计的目的与要求。不过其中也有一些不足之处，例如算法有点麻烦，有些句子不是很能理解。但是通过上网查找资料，去图书馆借阅相关书籍解决了这些不足之处。
由于关于磁盘调度的那部分，理论内容很少，所以，这次课程设计，我主要将重点放在实践中，也就是说，我在本次实验中，我是实现了3种磁盘调度算法。我这么做的原因有三个：
一是关于磁盘调度的理论性问题很少，如果仅仅模拟一下磁盘调度，那么实在是对不起辛辛苦苦教我们一学期的老师。
二是既然我们从课堂上学到了理论知识，那么就应该应用于实践，如果仅仅演示一下课堂上讲的理论或算法，那么实在是纸上谈兵。毕竟，程序员做的程序是给客户用的，并不是每个客户都精通计算机，如何完成客户要求的程序，并且客户使用起来方便，那么才可以说是一个比较不错的程序。
三是作为我们这些计算机专业的学生，迟早将面临着毕业设计，到时候我们总不能编写一些算法来敷衍吧，所以我认为在平时的课程设计中不但要真心真意地去做，更为重要的是程序使用并且使用简便，对于用户来说，重要的不是算法，而是程序的结果。作为一个计算机专业的学生，在课堂上要把基本思想熟练掌握，课后在写程序的时候要把思想封装到程序当中，充分体现它的应用价值。
本次课程设计，我利用调度算法完成了磁盘的调度，充分利用了课堂上讲的理论知识，完成了本次设计。至于功能吗，很单一，只不过是演示了一下3种最基本的磁盘调度算法，虽然界面不漂亮，尚且不完整，但是通过这次课程设计使我懂得了如何完成磁盘的调度。
程序最大的不足就是界面不漂亮，，我的设想是：为程序添加一些图像，并设计背景音乐。因为原理问题已经懂了，所以我相信利用管道能够实现更强大功能的软件。
4 参考文献
[1]张尧学。计算机操作系统教程。 出版地：清华大学出版
[2] 任爱华。操作系统实用教程。出版地：清华大学出版
[3] 周苏。操作系统原理实验。出版地：科学出版社
[4] 张尧学、史美林。计算机操作系统教程（第2版）。出版地：清华大学出版社
[5] 曾平、李春葆。操作系统习题与解析.出版地：清华大学出版社
[6] 张尧学、史美林。操作系统系统教程（第2版）习题解答与实验指导.出版地： 清华大学出版社
5 附录
#include
#include
#include
#include
#define M 100
int file[M],total,totalnum,xuan;
void print(int *p,int num) //输出优先顺序
{
int i;
printf("短寻道时间优先顺序是: ");
for(i=0;i
{
if(i)
printf("-＞");
printf("%d",p[i]);
file[i]=p[i];
}
printf("\n");
}
int abss(int a)//绝对值函数
{
if(a＜0)
a*=-1;
return a;
}
void fcfs(int *p,int num,int start)//先来先服务算法FCFS
{
int i;
double sum=0;
for(i=0;i
{
sum+=abss(p[i]-start);
start=p[i];
}
print(p,num);
total=(int)sum;
printf("移动的总道数：%.0lf\n",sum);
printf("平均寻道长度:%lf\n",sum/num);
}
void sstf(int *p,int num,int start)//最短寻道时间优先算法SSTF
{
int i,j,min,current,temp[M],n,len=0;
double sum=0;
n=num;
for(i=0;i
{
min=abss(p[0]-start);
for(j=0;j
{
if(min＞=abss(p[j]-start))
{
min=abss(p[j]-start);
current=j;
}
}
temp[len++]=p[current];
sum+=fabs(p[current]-start);
start=p[current];
for(j=current+1;j
p[j-1]=p[j];
num--;
}
total=(int)sum;
print(temp,n);
printf("移动的总道数：%.0lf\n",sum);
printf("平均寻道长度:%lf\n",sum/n);
}
int cmp1(const void *a,const void *b)
{
return *(int *)a - *(int *)b;
}
int cmp2(const void *a,const void *b)
{
return *(int *)b - *(int *)a;
}
void scan(int *p,int num,int start)//电梯调度算法(扫描算法SCAN)
{
int i,temp[M],max[M],min[M],max_len,min_len;
double sum=0;
max_len=min_len=0;
for(i=0;i
{
if(p[i]＞=start)
max[max_len++]=p[i];
else
min[min_len++]=p[i];
}
while(1)
{
printf("请选择移动臂初始方向(1增加0减小)：");
scanf("%d",&xuan);
if(xuan==1)
{
qsort(max,max_len,sizeof(max[0]),cmp1);
qsort(min,min_len,sizeof(min[0]),cmp2);
for(i=0;i
temp[i]=max[i];
for(i=0;i
temp[max_len++]=min[i];
for(i=0;i
{
sum+=abss(temp[i]-start);
start=temp[i];
}
total=(int)sum;
print(temp,num);
printf("移动的总道数：%.0lf\n",sum);
printf("平均寻道长度:%lf\n",sum/num);
break;
}
else if(xuan==0)
{
qsort(max,max_len,sizeof(max[0]),cmp1);
qsort(min,min_len,sizeof(min[0]),cmp2);
for(i=0;i
temp[i]=min[i];
for(i=0;i
temp[min_len++]=max[i];
for(i=0;i
{
sum+=abss(temp[i]-start);
start=temp[i];
}
total=(int)sum;
print(temp,num);
printf("移动的总道数：%.0lf\n",sum);+
printf("平均寻道长度:%lf\n",sum/num);
break;
}
else
{
printf("选择错误请重新选择！！！\n");
continue;
}
}
}
void save(char *p)//保存文件
{
FILE *fp;
int i;
fp=fopen("cidao.txt","a");
if(fp==NULL)
printf("文件打不开！\n");
else
{
fprintf(fp,"%s\n",p);
for(i=0;i
{
if(i)
fprintf(fp,"-＞");
fprintf(fp,"%d",file[i]);
}
fprintf(fp,"\n");
fprintf(fp,"移动的总道数：%d\n",total);
fprintf(fp,"平均寻道长度：%lf\n\n",total*1.0/totalnum);
printf("保存文件成功！\n");
}
}
int main()
{
int node[M],num,i,start,node2[M];
char c[M],str[M],choose[M];
printf("/*****************磁盘调度算法******************/\n");
printf("请输入磁道个数：");
scanf("%d",&num);
totalnum=num;
printf("请输入各磁道号：");
for(i=0;i
{
scanf("%d",&node[i]);
node2[i]=node[i];
}
printf("请输入当前磁道号：");
scanf("%d",&start);
printf("/*********************菜单**********************/\n");
printf("* *\n");
printf("* 1、先来先服务算法FCFS *\n");
printf("* 2、最短寻道时间优先算法SSTF *\n");
printf("* 3、电梯调度算法(扫描算法SCAN) *\n");
printf("* 0、退出 *\n");
printf("* *\n");
printf("/***********************************************/\n");
remove("cidao.txt");//如果文件已经存在 删除
while(1)
{
printf("请选择:");
scanf("%s",choose);
if(strcmp(choose,"0")==0)
break;
else if(strcmp(choose,"1")==0)
{
for(i=0;i
node2[i]=node[i];
fcfs(node2,num,start);
}
else if(strcmp(choose,"2")==0)
{
for(i=0;i
node2[i]=node[i];
sstf(node2,num,start);
}
else if(strcmp(choose,"3")==0)
{
for(i=0;i
node2[i]=node[i];
scan(node2,num,start);
}
else
{
printf("选择错误！\n");
continue;
}
if(strcmp(choose,"1")==0||strcmp(choose,"2")==0||strcmp(choose,"3")==0)
{
if(strcmp(choose,"1")==0)
strcpy(str,"先来先服务算法FCFS:");
else if(strcmp(choose,"2")==0)
strcpy(str,"最短寻道时间优先算法SSTF:");
else if(xuan==1)
strcpy(str,"电梯调度算法(扫描算法SCAN 移动臂先向增加方向移动):");
else
strcpy(str,"电梯调度算法(扫描算法SCAN 移动臂先向减小方向移动):");
while(1)
{
printf("是否保存文件(Y/N)\n");
scanf("%s",c);
if(strcmp(c,"N")==0||strcmp(c,"n")==0)
break;
else if(strcmp(c,"Y")==0||strcmp(c,"y")==0)
{
save(str);
break;
}
else
printf("输入有误,请重新输入：\n");
}
}
printf("\n");
}
printf("谢谢！！！\n");
return 0;
}