磁盘调度算法设计报告

1、操作系统课程设计报告题目：磁盘调度算法院系：信息学院班级：信管11-2姓名：王裕辰学号：1101051024指导教师：赵华、概述本次设计的程序主要功能是模拟访问磁盘的过程，实现先来先服务调度算法、最短 寻道时间调度算法、扫描算法、循环扫描算法四个磁盘调度算法，并根据输入的数据和 所选择的调度算法输出每种调度算法的磁盘访问顺序，计算并输出四个算法的平均寻道 长度。本程序主要实现磁盘访问的顺序，输出四种不同的磁盘调度算法的磁盘访问结果， 并计算出各自的平均寻道长度。以此来对四种调度算法的性能进行评价。、设计的基本概念和原理1、基本概念（1）当前磁道号：磁头当前时刻所在磁盘的磁道编号。（2）被访问的

2、下一个磁道号：需要访问的下一个磁盘的磁道编号。（3）移动距离：磁头从当前磁道移动到被访问的下一个磁道号所需移动的磁道数。2、基本原理（1）先来先服务（FCFS，First Come First Served）按照进程请求访问磁盘的先后次序进行从小到大排序，每次访问最先请求访问的磁道。 这样是每个进程的请求都能够依次地得到处理，不会出现某一进程的请求长期得不到满 足的情况（2）最短寻道时间优先（SSTF, Shortest Seek Time First）要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短。磁头每次 都移动到距离当前磁道距离最小的磁道上。（3）扫描算法（SCAN）

3、将请求访问的磁道号进行排序（升序或降序），磁头按照磁道号从大到小或从小到达的 顺序访问磁盘。（4）循环扫描算法（CSCAN）磁头从当前磁道从里向外（或从外向里）访问磁道，当访问到最外（或最里）的磁道并 访问后，磁头立即返回最里的（或最外）的欲访问的磁道，即最小（或最大）的磁道号 紧接着最大（或最小）磁道号构成循环，进行循环扫描。三、总体设计本程序才用了结构化程序设计方法，将程序进行模块化处理。首先将进程访问磁盘的请 求抽象为一个类，用用户所输入的数据来把每个对象来初始化。然后分块地调用不同的 函数实现不同的调度算法。本程序包括以下三个模块：（1）预定义及进程类定义模块定义程序所用到的头文件和常

4、量。定义请求类的类成员，成员函数以及输出请求类的类成员的输出函数（2）主程序模块包括以下五个步骤选择进程调度算法输入请求调用所选的磁盘调度算法计算每个请求的移动距离输出磁盘访问顺序和每个请求的移动距离，计算并输出所选算法的平均寻道长度（3）其它函数模块定义了四种调度算法和程序中调用的其他函数。程序流程图如下图所示四、详细设计每个模块的代码及分析如下：1、预定义及进程类定义模块#include stdafx.h#include #include #include using namespace std;#define Startnumber 100 /开始访问的磁道号#define Max 10

5、0 进程最大值class Requestprivate:intnumber,distance,difference;/ number-被访问的下一个磁道号distance-移动距离difference-被访问的下一 个磁道与当前磁道的距离public:intgetnumber()/返回被访问的下一个磁道号return number;-intgetdistance()/返回移动距离return distance;intgetdifference()/返回被访问的下一个磁道与当前磁道的距离return difference;void setnumber(int t)/设置被访问的下一个磁道号num

6、ber=t;void setdistance(int t)/ 设置移动距离distance=t;void setdifference(int t)/设置被访问的下一个磁道与当前磁道的距离differencevoid show() const 输出被访问的下个磁道号和移动距离coutsetw(17)numbersetw(6)distanceendl;2、主程序模块 int main(intargc, char* argv)inti,c,num,option,choice;double averdis;/平均寻道长度Request requestMax; /请求数组存放请求while(1)cout

7、磁盘调度算法endlendl;cout1.先来先服务2.最短寻道时间优先endl;cout3.扫描算法4.循环扫描算法endl;cout0.退出endl;coutendl;coutchoice; 输入选择的调度算法if(choice=0)return 0;elsecoutc;for(i=0;ic;i+) 输入请求中的数据并初始化请求数组cout请输入第i+1个请求endl;cout被访问的下一个磁道号num;requesti.setnumber(num);if(choice=1)FCFS(request,c); 调用先来先服务 if(choice=2) SSTF(request,c);/调用

8、SSTFFCFS(request,c);/调用先来先服务计算移动距离 if(choice=3|choice=4)/若选择SCAN或CSCAN则需要选择访问方向 cout选择访问方向：endl;cout”1.向磁道号增加方向2.向磁道号递减方向endl;coutoption;/选择访问方向 if(choice=3)SCAN(request,c,option);/调用 SCAN if(choice=4)CSAN(request,c,option);/调用 CSCAN FCFS(request,c);/调用先来先服务计算移动距离averdis=calcuaverage(request,c);/ 计算

9、平均寻道长度coutsetw(20)下一个磁道号setw(6)移动距离(磁道数)endl;for(i=0;ic;i+)/输出调度结果和访问顺序。requesti.show();cout平均寻道长度为：;coutaverdisendl;/输出平均寻道长度return 0;3、其它函数模块void FCFS(Request *req,int count)/先来先服务inti,currentnumber;for(i=0;icount;i+)if(i=0)/第一个请求的移动距离为它的磁道号与Startnumber的差reqi.setdistance(abs(reqi.getnumber()-Start

10、number);currentnumber=reqi.getnumber();else 其他请求的移动距离为其磁道号与上一个请求磁道号的差reqi.setdistance(abs(reqi.getnumber()-currentnumber);currentnumber=reqi.getnumber();double calcuaverage(Request *req,int count)/求平 均寻道长度inti;double aver;aver=0;for(i=0;icount;i+)aver+=reqi.getdistance();aver=aver/count;return aver;

11、void asc(Request *req,int count)/ 按磁道号递增排序inti,j;Request temp;for(i=0;icount;i+)for(j=i;jcount;j+)if(reqj.getnumber()reqi.getnumber()temp=reqj;reqj=reqi;reqi=temp;void dec(Request *req,int count)/ 按磁道号递减排序inti,j;Request temp;for(i=0;icount;i+)for(j=i;jreqi.getnumber()temp=reqj;reqj=reqi;reqi=temp;vo

12、id SSTF(Request *req,int count)/最短寻道时间优先inti,currentnumber,j,k,min,flagminMax,flag;Request mediareqMax;for(i=0;icount;i+)flagmini=0;currentnumber=Startnumber;k=0;for(i=0;icount;i+)求所有磁道号与当前磁道的差for(j=0;jcount;j+)reqj.setdifference(abs(reqj.getnumber()-currentnumber);找磁道差的最小值，并把此请求放入中间数组中，其磁道作为当前磁道for

13、(j=0;jcount;j+) 每次将没有访问的磁道的磁道差作为最小值if(flagminj=0)min=reqj.getdifference();flag=j;break;for(j=0;jcount;j+)/找磁道差的最小值if(reqj.getdifference()min&flagminj=0)/将磁道差小于 min 且没有访问 的磁道差作为最小值min=reqj.getdifference();flag=j;/ flag记录磁道差最小的请求号flagminflag=1;mediareqk+=reqflag;/找到的请求放入中间数组中currentnumber=reqflag.getn

14、umber();/ 磁道号作为当前磁道for(i=0;icount;i+)reqi=mediareqi;void SCAN(Request *req,intcount,int p)/扫描算法inti,j,k,l;Request mediamaxMax,mediaminMax;j=0;k=0;for(i=0;iStartnumber)mediamaxj+=reqi;if(reqi.getnumber()Startnumber)mediamink+=reqi;asc(mediamax,j);dec(mediamin,k);if(p=1)/向磁道号增加的方向访问，先访问大于开始磁道号的磁道，再访问小

15、于Startnumber 的for(i=0;ij;i+)reqi=mediamaxi;for(i=j,l=0;icount,lk;i+,l+)reqi=mediaminl;else向磁道号减少的方向访问，先访问小于Startnumber的磁道，再访问大于Startnumber 的for(i=0;ik;i+)reqi=mediamini;for(i=k,l=0;ivcount,lvj;i+,l+)reqi=mediamaxl;void CSAN(Request *req,intcount,int p)inti,j,k,l;Request mediamaxMax,mediaminMax;j=0;k

16、=0;for(i=0;iStartnumber)mediamaxj+=reqi;if(reqi.getnumber()Startnumber)mediamink+=reqi;if(p=1)/向磁道号增加的方向访问asc(mediamin,k);/将小于Startnumber的磁道的请求按磁道号升序排序asc(mediamax,j);/将大于Startnumber的磁道的请求按磁道号升序排序for(i=0;ij;i+)reqi=mediamaxi;for(i=j,l=0;ivcount,lvk;i+,l+)reqi=mediaminl;elsedec(mediamin,k);/将小于于Start

17、number的磁道的请求按磁道号降序排序dec(mediamax,j);/将大于Startnumber的磁道的请求按磁道号降序排序for(i=0;ik;i+)/将 请求重新排序reqi=mediamini;for(i=k,l=0;ivcount,lvj;i+,l+)reqi=mediamaxl;五、测试与数据分析选择FCFS算法，输入以下请求信息：被访问的下一个磁道号移动距离（磁道数）5545583391918219072160701501038112184146可以得到先来先服务调度算法的平均寻道时间（应为55.3）。选择最短寻道时间调度算法，再次输入上述请求信息。可以得到SSTF的平均寻道

18、 时间（应为27.5）。选择扫描算法，再次输入以上请求信息，选择向磁道号增加的方向访问，则得到扫 描算法的平均寻道长度（应为27.8）。选择循环扫描算法，再次输入上述请求信息，选择向磁道号增加的方向访问，得到 循环扫描算法的平均寻道时间（应为35.8）将上述四个调度算法得到的平均寻道时间进行比较，可以对这四种算法的性能进行 分析和比较，对这四个磁盘调度算法有了更深入的理解。六、完成的情况、简要的使用说明本程序经过了调试，能够正常运行，并能够得到正确的结果。但使用时应注意以下 几个问题：1、选择调度算法的时候只能输入0、1、2、3、4这五个数字，若输入其它字符 将造成程序进入死循环。2、进行扫描

19、算法和循环扫描算法时，选择访问方向只能为1或2,若输入其它 字符将造成程序进入死循环。3、在输入请求信息之前，应确定请求的数目，并输入。4、本程序需要逐个输入请求的信息，对于请求数目比较多的时候会花费较长的 时间。故本程序最好用于请求数目较少的情况。5、程序中的开始磁道号（Startnumber）为常量，用户无法输入但可以在程序代 码中进行修改。七、结果分析运行程序界面如如下图所示C:Use rsWCD es ktop0 深程设计、磋坦调度DI SKDi patchDeb u gDIS KDi patch.ex e藏盘调度算法2遢丑寻道时间优先4 ,循环扫描具法请输羌你选择的调度算法:选择1，

20、输入五测试与数据分析中的数据，得到如下所示C:Use rsWCD es ktop0 深呈设计 L 磋坦调度DI SKDi pate hDeb u gDIS KD i patch .ex e清输zfef尔选择的调度算法:3ir2遢丑寻道时间优先4 ,循环扫描具法下一个磁道号移动距离其磁道数）5545583391918219072160701501S38184112146平均寻道长度为：55.3333磁盘调度算法选择2,再次输入上述数据，得到如下所示C:Use rsWVCDes top0 深程设计、磋坦调度D1 SKDi patchDeb u gDIS KDi patch.exe清输:A你选择的调度算法:2遢短寻道时间优先 4：循环扫箱算法下顷磁道号移动距离笑磁道数）9S58325533916381182S15S1321S18424平均寻道长度为W 27-55S6磁盘调度算法选择3,再输入上述数据，选择向磁道号增加的方向访问，得到如下所示C:Use rsV/YCD es ktop0 深程设计 k 磋坦调度D1 SKDi patchDeb u gDISKOipatch.exe管愕口方向2