磁盘调度报告

PAGE成绩课程设计报告题目磁盘调度算法设计课程名称操作系统课程设计院部名称信息技术学院专业11计算机科学与技术班级11计算计科学与技术（2）学生姓名宋双学号1105101002课程设计地点1318课程设计学时20指导教师何健金陵科技学院教务处制PAGEII目录TOC\o"1-4"\h\z\u摘要 II1

前言 11.1目的 11.2背景 11.3意义 12正文 22.1课设要求 22.2课设设备、环境 22.3课设方法及步骤 22.3.1设计方法： 22.3.2设计步骤： 42.4

实验、调试及测试结果与分析。 93

结论 114

参考文献 125

附录 12摘要多道程序设计中，经常是若干个进程同时处于就绪状态，必须依照某种策略来决定那个进程优先占有处理机。因而引起进程调度。本实验模拟在单处理机情况下的处理机调度问题，加深对进程调度的理解。模拟实现FCFS、SSTF、SCAN算法，并计算及比较磁头移动道数。本实验设计的目的是通过设计一个磁盘调度模拟系统，以加深对FCFS、最短寻道时间以及电梯等磁盘调度算法的理解。让我们更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解，加强动手能力。本实验设计的目的是通过设计一个磁盘调度模拟系统，以加深对FCFS、最短寻道时间以及电梯等磁盘调度算法的理解。让我们更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解，加强动手能力。关键字：磁盘调度fcfssstfscan算法PAGE181

前言1.1目的磁盘是经常使用的一种重要的外设，对磁盘数据的寻道时间的长短直接影响机器的整体运行速度，本设计要求用C语言（或高级语言）编写程序模拟实现磁盘调度的常用算法。以加深对磁盘调度常用算法的理解和实现技巧。1.2背景磁盘驱动调度对磁盘的效率有重要影响。磁盘驱动调度算法的好坏直接影响辅助存储器的效率，从而影响计算机系统的整体效率。磁盘调度在多道程序设计的计算机系统中，各个进程可能会不断提出不同的对磁盘进行读/写操作的请求。由于有时候这些进程的发送请求的速度比磁盘响应的还要快，因此我们有必要为每个磁盘设备建立一个等待队列，常用的磁盘调度算法有以下四种：先来先服务算法（FCFS），最短寻道时间优先算法（SSTF），扫描算法（SCAN），循环扫描算法（CSCAN）1.3意义在多道程序系统中，低效率通常是由于磁盘类旋转设备使用不当造成的。操作系统中，对磁盘的访问要求来自多方面，常常需要排队。这时，对众多的访问要求按一定的次序响应，会直接影响磁盘的工作效率，进而影响系统的性能。访问磁盘的时间因子由3部分构成，它们是查找（查找磁道）时间、等待（旋转等待扇区）时间和数据传输时间，其中查找时间是决定因素。因此，磁盘调度算法先考虑优化查找策略，需要时再优化旋转等待策略。2正文2.1课设要求1）、设计一个函数完成先来先服务的磁盘调度功能。2）、设计一个函数完成最短寻道时间优先的磁盘调度功能。3）、设计一个函数完成电梯算法的磁盘调度功能。2.2课设设备、环境奔腾以上计算机，装有TurboC2.0软件2.3课设方法及步骤2.3.1设计方法：本系统应该具有功能：设计一个函数完成先来先服务的磁盘调度功能，设计一个函数完成最短寻道时间优先的磁盘调度功能，设计一个函数完成电梯算法的磁盘调度功能，并设计一个函数实现文件保存功能。本系统具有通用性，界面美观，操作方便考虑到了系统安全问题。相关信息应保存在文件中。本软件的性能很好：通过磁盘调度算法的模拟设计，了解磁盘调度的特点。磁盘调度算法是根据访问都指定的磁道（柱面）位置来决定执行次序的调度。其目的是尽可能地减少操作中的寻道时间。在磁盘盘面上，0磁道在盘面的外圈；号数越大，磁道戛靠近盘片的中心。通常采用FCFS（先来先服务）、SSTF（最短寻道时间）、SCAN（扫描）进行不同的磁盘调度。该磁盘调度系统流程图如下：输入数据输入数据选择算法？调用FCFS（）算法调用SSTF（）算法调用SCAN（）算法输出退出是否开始图2.3.1.1系统模块图如下：磁盘调度磁盘调度登陆界面电梯调度算法最短寻道时间优先算法先来先服务算法保存文件图2.3.1.2函数调用关系图main函数main函数FCFS函数SSTF函数SCAN函数FCFS函数SSTF函数SCAN函数输出输出图2.3.1.32.3.2设计步骤：下面我将详细地为你讲解本程序的FCFS（先来先服务）、SSTF（最短寻道时间）、SCAN（扫描）、C-SCAN（单向扫描）。2.3.2.1FCFS（先来先服务）算法先来先服务是一种最简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平，简单，且每个进程的请求都能依次地得到处理，不会出现某一进程的请求长期得不到满足的情况。但是，此算法由于未对寻道进行优化，致使平均寻道时间可能较长。图2.4.2展示出有10个进程先后提出磁盘I/O请求时，按先来先服务算法进行调度的情况。这里，将进程号按他们发出请求的先后次序排队。这样，平均寻道距离为53.1条磁道，与后面将讲到的几种调度算法相比，其平均寻道距离较大，故先来先服务算法仅适用于请求磁盘I/O的进程数目较少的场合。程序设计流程图为：输入各磁道号和当前磁道号start输入各磁道号和当前磁道号start磁头移动距离sum=abss(p[0]-start)磁头移动总距离sum+=abss(p[i]-start)输出磁盘调度序列p目前的位置变为当前的位置start=p[i]i<num输出平均寻道长度asum/num图2.3.2.1我们通过程序for(i=0;i<num;i++){sum+=abss(p[i]-start);start=p[i];}来实现该算法。2.3.2.2SSTF（最短寻道时间）算法该算法选择这样的进程，其要求访问的磁道，与当前磁头所在的磁道距离最近，以使得每次的寻道时间最短，但是这种算法不能保证平均寻道时间最短。图2.4.3展示出最短寻道时间优先算法进行调度时，各进程被调度的次序，每次磁头移动的距离，以及9次磁头平均移动距离。比较图2.4.2和图2.4.3可以看出，最短寻道时间优先算法的平均每次磁头移动距离，明显低于先来先服务的距离，因而最短寻道时间优先算法较之先来先服务有更好的寻道性能，故过去曾一度被广泛采用。程序设计流程图为：输入各磁道号和当前磁道号start输入各磁道号和当前磁道号start设最短距离设最短距离min=abss(p[0]-start)min>=abss(p[j]-start)min>=abss(p[j]-start)j++j++当前磁道所在位置current=j当前磁道所在位置current=j当前临时队列temp[len++]=p[current]当前临时队列temp[len++]=p[current]磁头移动总距离磁头移动总距离sum+=abss(p[current]-start)输出磁盘调度序列temp输出磁盘调度序列temp输出平均寻道长度输出平均寻道长度sum/num图2.3.2.2我们通过程序for(i=0;i<n;i++) {min=abss(p[0]-start);for(j=0;j<num;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<num;j++)p[j-1]=p[j];num--; }来实现最短寻道时间优先算法。2.3.2.3SCAN（电梯调度）算法该算法不仅考虑到欲访问的磁道与当前磁道间的距离，更优先考虑的是磁头当前的移动方向。例如，当磁头正在自里向外移动时，电梯调度算法所考虑的下一个访问对象，应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直至再无更外的磁道需要访问时，才将磁臂向为自外向里移动。这时，同样也是每次选择这样的进程来调度，即要访问的磁道在当前位置内距离最近者，这样，磁头又逐步地从外向里移动，直至再无更里面的磁道要访问，从而避免了出现“饥饿”现象。由于在这种算法中磁头移动的规律颇似电梯的运行，因而又常称之为电梯调度算法。我们使用语句printf("请选择移动臂初始方向(1增加0减小)：");来实现另一个功能，用户可以选择相对当前磁道位置增加或者减少的方向移动，其中用1代表向上移动，0代表向下移动。从而使功能更加强大。程序设计流程图为：输入各磁道号和当前磁道号start输入各磁道号和当前磁道号startp[i]>=start将比当前磁道号大的放入max[max_len++]=p[i]将比当前磁道号小的放入min[min_len++]=p[i]移动臂初始方向case1:将磁道号从小到大排序case0:将磁道号从小到大排序将比当前磁道号大的磁道按顺序赋给临时序列temp[i]=max[i]将比当前磁道号小的磁道接着按顺序赋给临时序列temp[max_len++]=min[i]磁头移动总距离sum+=abss(temp[i]-start)输出平均寻道长度sum/num将比当前磁道号小的磁道按顺序赋给临时序列temp[i]=min[i]将比当前磁道号大的磁道接着按顺序赋给临时序列temp[min_len++]=max[i]图2.3.2.3我们通过语句for(i=0;i<max_len;i++)temp[i]=max[i];for(i=0;i<min_len;i++)temp[max_len++]=min[i]; for(i=0;i<num;i++){sum+=abss(temp[i]-start); start=temp[i];}来实现向增加方向移动功能。与此相同我们通过语句for(i=0;i<min_len;i++)temp[i]=min[i]; for(i=0;i<max_len;i++)temp[min_len++]=max[i]; for(i=0;i<num;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<totalnum;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<stdio.h>#include<string.h>#include<math.h>#include<stdlib.h>#defineM100intfile[M],total,totalnum,xuan;voidprint(int*p,intnum)//输出优先顺序{inti;printf("短寻道时间优先顺序是:"); for(i=0;i<num;i++){ if(i)printf("->");printf("%d",p[i]);file[i]=p[i]; } printf("\n");}intabss(inta)//绝对值函数{ if(a<0)a*=-1;returna;}voidfcfs(int*p,intnum,intstart)//先来先服务算法FCFS{inti;doublesum=0;for(i=0;i<num;i++) {sum+=abss(p[i]-start);start=p[i]; } print(p,num);total=(int)sum;printf("移动的总道数：%.0lf\n",sum);printf("平均寻道长度:%lf\n",sum/num);}voidsstf(int*p,intnum,intstart)//最短寻道时间优先算法SSTF{ inti,j,min,current,temp[M],n,len=0;doublesum=0;n=num;for(i=0;i<n;i++) {min=abss(p[0]-start);for(j=0;j<num;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<num;j++)p[j-1]=p[j];num--; }total=(int)sum;print(temp,n);printf("移动的总道数：%.0lf\n",sum);printf("平均寻道长度:%lf\n",sum/n);}intcmp1(constvoid*a,constvoid*b){return*(int*)a-*(int*)b;}intcmp2(constvoid*a,constvoid*b){return*(int*)b-*(int*)a;}voidscan(int*p,intnum,intstart)//电梯调度算法(扫描算法SCAN){ inti,temp[M],max[M],min[M],max_len,min_len;doublesum=0;max_len=min_len=0; for(i=0;i<num;i++){ if(p[i]>=start)max[max_len++]=p[i]; elsemin[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<max_len;i++) temp[i]=max[i]; for(i=0;i<min_len;i++) temp[max_len++]=min[i]; for(i=0;i<num;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; } elseif(xuan==0) { qsort(max,max_len,sizeof(max[0]),cmp1); qsort(min,min_len,sizeof(min[0]),cmp2); for(i=0;i<min_len;i++) temp[i]=min[i]; for(i=0;i<max_len;i++) temp[min_len++]=max[i]; for(i=0;i<num;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; } }}voidsave(char*p)//保存文件{FILE*fp;inti;fp=fopen("cidao.txt","a"); if(fp==NULL)printf("文件打不开！\n");else{fprintf(fp,"%s\n",p);for(i=0;i<totalnum;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");}}intmain(){intnode[M],num,i,start,node2[M];charc[M],str[M],choose[M]; printf("/*****************磁盘调度算法******************/\n");printf("请输入磁道个数：");scanf("%d",&num);totalnum=num;printf("请输入各磁道号："); for(i=0;i<num;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("请选择:");