磁盘调度 操作系统实验报告

《磁盘调度 操作系统实验报告》由会员分享，可在线阅读，更多相关《磁盘调度 操作系统实验报告（16页珍藏版）》请在装配图网上搜索。

1、实验一 磁盘调度算法实现一、实验目的本课程设计的目的是通过磁盘调度算法设计一个磁盘调度模拟系统，从而使 磁盘调度算法更加形象化，容易使人理解，使磁盘调度的特点更简单明了，能使 使用者加深对先来先服务算法、最短寻道时间优先算法、扫描算法以及循环扫描 算法等磁盘调度算法的理解。二、实验内容系统主界面可以灵活选择某种算法，算法包括：先来先服务算法（FCFS）、 最短寻道时间优先算法（SSTF）、扫描算法（SCAN）、循环扫描算法（CSCAN）。2.1 先来先服务算法（ FCFS ）这是一种比较简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进 行调度。此算法的优点是公平、简单，且每个进程的请求都

2、能依次得到处理，不 会出现某一进程的请求长期得不到满足的情况。此算法由于未对寻道进行优化， 在对磁盘的访问请求比较多的情况下，此算法将降低设备服务的吞吐量，致使平 均寻道时间可能较长，但各进程得到服务的响应时间的变化幅度较小。2.2 最短寻道时间优先算法（ SSTF ）该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近 以使每次的寻道时间最短，该算法可以得到比较好的吞吐量，但却不能保证平均 寻道时间最短。其缺点是对用户的服务请求的响应机会不是均等的，因而导致响 应时间的变化幅度很大。在服务请求很多的情况下，对内外边缘磁道的请求将会 无限期的被延迟，有些请求的响应时间将不可预期。

3、2.3 扫描算法（ SCAN ）扫描算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头 的当前移动方向。例如，当磁头正在自里向外移动时，扫描算法所选择的下一个 访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向 外地访问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。这时， 同样也是每次选择这样的进程来调度，即其要访问的磁道，在当前磁道之内，从 而避免了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运行，故 又称为电梯调度算法。此算法基本上克服了最短寻道时间优先算法的服务集中于 中间磁道和响应时间变化比较大的缺点，而具有最短寻道时间优先算法的优点

4、即 吞吐量较大，平均响应时间较小，但由于是摆动式的扫描方法，两侧磁道被访问 的频率仍低于中间磁道。2.4 循环扫描算法（ CSCAN ）循环扫描算法是对扫描算法的改进。如果对磁道的访问请求是均匀分布的， 当磁头到达磁盘的一端，并反向运动时落在磁头之后的访问请求相对较少。这是 由于这些磁道刚被处理，而磁盘另一端的请求密度相当高，且这些访问请求等待 的时间较长，为了解决这种情况，循环扫描算法规定磁头单向移动。例如，只自 里向外移动，当磁头移到最外的被访问磁道时，磁头立即返回到最里的欲访磁道， 即将最小磁道号紧接着最大磁道号构成循环，进行扫描。三、实验流程3.1 系统功能图图 3-1 系统功能图3.

5、2 算法流程图 本次实验为实现磁盘调度算法，分别实现四个算法并调试。四个算法算法包括：先来先服务算法（FCFS）、最短寻道时间优先算法（SSTF）、扫描算法（SCAN）、 循环扫描算法（CSCAN）。四个算法的流程图分析如下。1）先来先服务算法（FCFS ）的流程图图 3-2 先来先服务算法的流程图2）最短寻道时间优先算法（SSTF）的流程图开蛉|低冃冒:电汪甘尹农、-均七度F输的離号图 3-3 最短寻道时间优先算法的流程图3）扫描算法（SCAN）的流程图开曲GE）图3-4扫描算法的流程图4）循环扫描算法（CSCAN ）的流程图|箭曲适乞使用冒泡法排序工井三門卡昇输图 3-5 循环扫描算法的流

6、程图四、源程序#include#include #include #include #define maxsize 1000 /*判断输入数据是否有效*/ int decide(char str) /判断输入数据是否有效int i=0;while(stri!=0) if(stri9) return 0; break; i+; return i;int trans(char str,int a) /将字符串转换成数字int i;int sum=0;for(i=0;ia;i+) sum=sum+(int)(stri-0)*pow(10,a-i-1); return sum;int *bubble(

7、int cidao,int m)int i,j;int temp;for(i=0;im;i+) /使用冒泡法按从小到大顺序排列 for(j=i+1;jcidaoj) temp=cidaoi; cidaoi=cidaoj; cidaoj=temp;cout 排序后的磁盘序列为：;for( i=0;im;i+) /输出排序结果coutcidaoi;coutendl;return cidao;void FCFS(int cidao,int m) /磁道号数组，个数为 m int now;/当前磁道号int sum=0; /总寻道长度int j,i;int a;char str100;float av

8、e; /平均寻道长度 cout 磁盘请求序列为：;for( i=0;im;i+) /按先来先服务的策略输出磁盘请求序列 coutcidaoi;coutendl;coutstr; /对输入数据进行有效性判断 a=decide(str);if(a=0)coutvv输入数据的类型错误，请重新输入！ vvendl; goto B;else now=trans(str，a); /输入当前磁道号 sum+=abs(cidao0-now);coutvv 磁盘扫描序列为：;for( i=0;ivm;i+) /输出磁盘扫描序列 coutvvcidaoivv;for(i=0，j=1;jvm;i+，j+) /求平均

9、寻道长度 sum+=abs(cidaoj-cidaoi); ave=(float)(sum)/(float)(m);coutvvendl; coutvv平均寻道长度：vvavevvendl;void SSTF(int cidao，int m)int k=1;int now，l，r;int i，j，sum=0;int a;char str100;float ave;cidao=bubble(cidao，m); /调用冒泡排序算法排序 coutvv 请输入当前的磁道号： ;C: cinstr; /对输入数据进行有效性判断 a=decide(str);if(a=0)coutvv 输入数据的类型错误，

10、请重新输入！ vvendl; goto C;else now=trans(str，a); /输入当前磁道号if(cidaom-1v=now) /若当前磁道号大于请求序列中最大者，则直接由外向 内依次给予各请求服务cout=0;i-)coutcidaoi=now) /若当前磁道号小于请求序列中最小者，则直接由内向外依 次给予各请求服务cout 磁盘扫描序列为：; for(i=0;im;i+) coutcidaoicidao0&nowcidaom-1) /若当前磁道号大于请求序列中最小者 且小于最大者cout 磁盘扫描序列为：;while(cidaok=0)&(rm) /当前磁道在请求序列范围内

11、if(now-cidaol)=(cidaor-now) /选择与当前磁道最近的请求给予 服务 coutcidaol; sum+=now-cidaol; now=cidaol; l=l-1;else coutcidaor; sum+=cidaor-now; now=cidaor; r=r+1;if(l=-1) /磁头移动到序列的最小号，返回外侧扫描仍未扫描的磁道 for(j=r;jm;j+) coutcidaoj=0;j-) coutcidaoj; sum+=cidaom-1-cidao0;ave=(float)(sum)/(float)(m); coutendl;cout 平均寻道长度： av

12、eendl;/*扫描调度算法 void SCAN(int cidao,int m) /先要给出当前磁道号和移动臂的移动方向int k=1;int now,l,r,d;int i,j,sum=0;int a;char str100;float ave; cidao=bubble(cidao,m); /调用冒泡排序算法排序 coutstr; /对输入数据进行有效性判断 a=decide(str);if(a=0)coutvv输入数据的类型错误，请重新输入！ vvendl; goto D;elsenow=trans(str，a); /输入当前磁道号if(cidaom-1v=now) /若当前磁道号大于

13、请求序列中最大者，则直接由外向 内依次给予各请求服务，此情况同最短寻道优先coutvv 磁盘扫描序列为：;for(i=m-1;i=0;i-)coutvvcidaoivv;sum=now-cidao0;if(cidao0=now) /若当前磁道号小于请求序列中最小者，则直接由内向外依 次给予各请求服务，此情况同最短寻道优先coutvv 磁盘扫描序列为：;for(i=0;ivm;i+)coutvvcidaoivv;sum=cidaom-1-now;if(nowcidao0&nowcidaom-1) /若当前磁道号大于请求序列中最小者 且小于最大者while(cidaoknow) k+;l=k-1;

14、r=k;coutvv请输入当前移动臂的移动的方向:nvvendl;cout 0:表示向内 1 :表示向外:d;if(d=0) /选择移动臂方向向内，则先向内扫描cout=0;j-) coutcidaoj; /输出向内扫描的序列 for(j=r;jm;j+) /磁头移动到最小号，则改变方向向外扫描未扫描的 磁道coutcidaoj; /输出向外扫描的序列 sum=now-2*cidao0+cidaom-1;else /选择移动臂方向向外，则先向外扫描cout 磁盘扫描序列为：;for(j=r;jm;j+) coutcidaoj=0;j-) /磁头移动到最大号，则改变方向向内扫描未扫描的 磁道co

15、utcidaoj;sum=-now-cidao0+2*cidaom-1; ave=(float)(sum)/(float)(m);coutendl;cout 平均寻道长度： aveendl;/*循环扫描调度算法/#J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* /void CSCAN(int cidao,int m)int k=1;int now,l,r;int i,j,sum=0;int a;char str10

16、0;float ave;cidao=bubble(cidao,m); /调用冒泡排序算法排序coutstr; /对输入数据进行有效性判断 a=decide(str);if(a=0)coutvv输入数据的类型错误，请重新输入！ vvendl;goto E;else now=trans(str，a); /输入当前磁道号 if(cidaom-1v=now) /若当前磁道号大于请求序列中最大者，则直接将移动 臂移动到最小号磁道依次向外给予各请求服务coutvv 磁盘扫描序列为：;for(i=0;ivm;i+) coutvvcidaoivv;sum=now-2*cidao0+cidaom-1; if(c

17、idao0=now) /若当前磁道号小于请求序列中最小者，则直接由内向外依 次给予各请求服务，此情况同最短寻道优先coutvv 磁盘扫描序列为：;for(i=0;ivm;i+) coutvvcidaoivv;sum=cidaom-1-now; if(nowcidao0&nowvcidaom-1) /若当前磁道号大于请求序列中最小者 且小于最大者coutvv 磁盘扫描序列为：;while(cidaokvnow) /单向反复地从内向外扫描k+;l=k-1;r=k;for(j=r;jvm;j+) coutvvcidaojvv; /输出从当前磁道向外扫描的序列 for(j=0;jvr;j+) /当扫描

18、完最大号磁道，磁头直接移动到最小号磁道，再 向外扫描未扫描的磁道coutvvcidaojvv;sum=2*cidaom-1+cidaol-now-2*cidao0; ave=(float)(sum)/(float)(m);coutvvendl;coutvv 平均寻道长度： vvavevvendl;void main()int a;int c; /菜单项int cidaomaxsize;int i=0,count;char str100;cout 请输入磁道序列(输入 0结束): str; /对输入数据进行有效性判断 a=decide(str);if(a=0)coutvv输入数据的类型错误，请重

19、新输入！ vvendl; goto A;/输入错误，跳转到A,重新输入else cidaoi=trans(str，a);i+; while(cidaoi-1!=0) cinstr; /对输入数据进行有效性判断 a=decide(str);if(a=0) coutvv 输入数据的类型错误，请重新输入！ vvendl; elsecidaoi=trans(str，a);i+;count=i-1; /要访问的磁道数 coutvv 输入的磁道序列为：;for(i=0;ivcount;i+) coutvvcidaoivv; /输出磁道序列 coutvvendl;while(1)coutvvendl;cou

20、tvv vvendl;coutvvn 1.先来先服务2.最短寻道时间优先3.扫描调度4.循环扫描 5.退出 nvvendl;coutvv vvendl;G:coutvv 请选择算法:;F:cinstr; /对输入数据进行有效性判断 a=decide(str);if(a=0)coutvv 输入数据的类型错误，请重新输入！ vvendl; goto F;输入错误，跳转到F,重新输入else c=trans(str，a); if(c=5) break;if(c5)coutvv输入的数据错误！请重新输入vvendl; goto G;switch(c)case 1: 使用FCFS算法 FCFS(cida

21、o,count); break;case 2: /使用SSTF算法 SSTF(cidao,count); break;case 3: /使用 SCAN 算法 SCAN(cidao,count); break;case 4: /使用 CSCAN 算法 CSCAN(cidao,count); break;五、实验结果5.1 程序主界面运行程序后，将会提示用户输入磁道序列，并且以 0结束。当用户输入磁道 序列后，系统将会重新显示用户输入的磁道序列。程序主界面运行图如图 5-1 所示。请输入磁道序列(输入0结束二12 34 56 ?8 89 23 45 6? 0输入的磁道序列为！ 12 34 56 7

22、8 89 23 45 67图 5-1 程序主界面5.2先来先服务算法(FCFS)运行结果选择算法1之后，进入算法1 的操作。系统会显示磁盘的请求序列。用户 需要输入当前的磁道号，系统会显示出磁盘的扫描序列和平均寻道长度。由运行 结果可得出，先来先服务算法的平均寻道长度为24.75。先来先服务算法的运行 图如图5-2 所示。先来先服务z-最短寻道时间优先齐扫描调度 J循环扫描厂退岀6 65 54 143 312昂12.75 一直14 II _1. 1为第： -列的列度 祛序前序长 搓艮扫寻 选盘餐均平7 76 65 54 43 32 2图 5-2 先来先服务算法运行结果图5.3最短寻道时间优先算

23、法 (SSTF)运行结果选择算法2 之后，进入算法 2 的操作。系统会显示磁盘的请求序列。用户 需要输入当前的磁道号，系统会显示出磁盘的扫描序列和平均寻道长度。由运行 结果可得出，先来先服务算法的平均寻道长度为 20.625。最短寻道时间优先算 法的运行图如图5-3 所示。先来先服务2-最短寻道时间优先3.扫描调度4.循环扫描 匚退出2113 5 知环120.6 列道 2 2 : :盘的列度 常前序长 择1扫寻 选4均卷平23 34 45 56 67 7834 45 56 67 78 8989图 5-3 最短寻道时间优先算法运行结果图5.4扫描算法 (SCAN )运行结果选择算法3 之后，进入

24、算法 3 的操作。系统会显示磁盘的请求序列。用户需 要输入当前的磁道号，系统会显示出磁盘的扫描序列和平均寻道长度。由运行结 果可得出，先来先服务算法的平均寻道长度为 11。扫描算法的运行图如图 5-4 所示。为号121S : 1 - :盘的列度 盖前序长 這 择冥扫寻 选taas均 罷平1 先来先服务2.最短寻道时i可优先 皐扫描调度4.循环扫描5-退岀:12 23 34 45 56 67 78 89 ；123 34 45 56 67 78 89图 5-4 扫描算法运行结果图5.5循环扫描算法(CSCAN)运行结果选择算法4 之后，进入算法 4 的操作。系统会显示磁盘的请求序列。用户需 要输入

25、当前的磁道号，系统会显示出磁盘的扫描序列和平均寻道长度。由运行结 果可得出，先来先服务算法的平均寻道长度为 11。扫描算法的运行图如图 5-5 所示。先来先服务 冬最短寻道时间优先 史扫描调度4.循坏扫描 厂退出缩潮|矗|毎序列为:12 23 34 45 56 67 78 89请触入肖前的磯道号：1磁盘扫扌团序列为：12 23 34 45 56 67 78 89平均寻道长度：11图 5-5 循环扫描算法运行结果图六、总结通过本次实验，学习了解磁盘调度四种调度算法（先来先服务算法；最短寻 道时间优先算法；扫描算法；循环扫描算法）的工作原理以及四种调度算法之间 的差异和共性，并且在当中发现了自己的不足，对以前所学过的知识理解得不够 深刻，掌握得不够牢固，看到了自己的实践经验还是比较缺乏，实践能力还需要 提高。