磁盘调度算法的实现

1、实验五、磁盘调度算法的实现一、实验目的实验程序模拟先来先服务 FCFS最短寻道时间优先SSTFSCA脚口循环SCAN 算法的工作过程。假设有n个磁道号所组成的磁道访问序列，给定开始磁道号m 和磁头移动的方向(正向或者反向)，分别利用不同的磁盘调度算法访问磁道序 列，给出每一次访问的磁头移动距离， 计算每种算法的平均寻道长度，本程序采 用随机数来产生磁道数。二、实验要求算法所需的各种参数由输入产生(手工输入或者随机数产生)。最后的结果 要求是在运行四种算法的程序后，能够输出调度过程、平均寻道长度的正确结果。三、实验说明先来先服务.(FCFS):这是一种简单的磁盘调度算法。它根据进程请求访问磁盘的

2、先后次序进行调 度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出 现某一进程的请求长期得不到满足的情况。但此算法由于未对寻道进行优化，致 使平均寻道时间可能较长。(2)最短寻道时间优先(SSTF):该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最 近，以使每次的寻道时间最短，但这种调度算法却不能保证平均寻道时间最短。扫描算法(SCAN):SCANB法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁 头的当前移动方向。例如，当磁头正在自里向外移动时，SCANT法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访

3、问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。这时，同样也是每次选择这样的进程来调度，即其要访问的磁道，在当前磁道之内， 从而避免了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运行， 故又称为电梯调度算法。(4)循环扫描算法(CSCANCSCANJT法是对扫描算法的改进。如果对磁道的访问请求是均匀分布的， 当 磁头到达磁盘的一端，并反向运动时落在磁头之后的访问请求相对较少。这是由 于这些磁道刚被处理，而磁盘另一端的请求密度相当高， 且这些访问请求等待的 时间较长，为了解决这种情况，循环扫描算法规定磁头单向移动。例如，只自里向外移动，当磁头移到最外的被访问磁道时，磁头立即返

4、回到最里的欲访磁道， 即将最小磁道号紧接着最大磁道号构成循环，进行扫描本系统划分为四个模块：先来先服务算法模块void FCFS(int array,int m)最短寻道时间优先算法模块 void SSTF(int array,int m)扫描算法模块void SCAN(int array,int m)、循环扫描模块 void CSCAN (int Han,int DiscL)系统模块图1先来先服务算法模块：void FCFS(int array,int m)输入磁道号，按先来先服务的策略输出磁盘请求序列，求平均寻道长度，输出移动平均磁道数。2最短寻道时间优先算法模块：void SSTF(in

5、t array,int m)将磁道号用冒泡法从小到大排序， 输出排好序的磁道序列，输入当前磁道号，根 据前磁道在已排的序列中的位置， 选择扫描的顺序，求出平均寻道长度，输出移 动的平均磁道数。3 扫描算法模块：void SCAN(int array,int m)将磁道号用冒泡法从小到大排序， 输出排好序的序列，输入当前磁道号，选择移 动臂的移动方向，根据当前磁道在已排的序列中的位置， 选择扫描的顺序，求出 平均寻道长度，输出移动的平均磁道数。4 循环扫描算法模块：void CSCAN(int array,int m)将磁道号用冒泡法从小到大排序， 输出排好序的序列，输入当前磁道号，规定移 动臂

6、单向反复的从内向外移动，根据当前磁道在已排的序列中的位置， 选择扫描 的顺序，求出平均寻道长度，输出移动的平均磁道数。1、先来先服务(FCFS)这是一种简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理， 不会出现某 一进程的请求长期得不到满足的情况。但此算法由于未对寻道进行优化，致使平 均寻道时间可能较长。实现函数：void FCFS(int Han,int DiscL)先来先服务算法(FCFS流程图：2、最短寻道时间优先(SSTF)该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短

7、，但这种调度算法却不能保证平均寻道时间最短。实现函数：void SSTF(int Han,int DiscL)最短寻道时间优先流程图:输入磁使用冒泡法从小到输出排好序的磁选择与当前磁道 距离最近的磁道移动到最小（大） 号，改向外（内） 移幼扫描未扫描 k>求生物寻道输出移动的平均3、扫描算法（SCAN）SCANB法不仅考虑到欲访问的磁道与当前磁道的距离,更优先考虑的是磁头的当前移动方向。例如，当磁头正在自里向外移动时，SCAN算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。这时， 同样

8、也是每次选择这样的进程来调度， 即其要访问的磁道，在当前磁道之内，从而避免了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运行，故又称为电梯调度算法。实现函数:int SCAN(int Han,int DiscL,int x,int y)(4)循环扫描算法(CSCANcscaNT法在scanB法的基础上规定了刺头单向移动，减少了进程的请求延迟。 例如：只是自理向外移动，当磁头移到最外的磁道并访问后， 磁头立即返回到最 里的欲访问磁道，亦即将最小的磁道号紧接着最大的磁道号构成循环， 进行循环 扫描。实现函数：void CSCAN(int Han,int DiscL)源代码：©/

9、 123123123.cpp :定义控制台应用程序的入口点#include "stdafx.h"#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);

10、/数组Sour把x位置的数删除，并把y前面的数向前移动，y后的数保持不变(即 会出现2个y) void FCFS(int Han, int DiscL); /先来先服务算法 (FCFS)void SSTF(int Han,int DiscL); / 最短寻道时间优先算法(SSTF)int SCAN(nt Han,int DiscL, int x, int y);/ 扫描算法(SCAN)zoid CSCANi(itHan,int DiscL); /循环扫描算法(CSCANvoid N_Step_SCAN(nt Han1, int DiscL); /N步扫描算法(NStepScan) void P

11、aiXu(); /寻道长度由低到高 排序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("请输入初始的磁道数(0<n<65536):");scanf("%d”,&a

12、mp;Hand);printf(" +输入寻找的范围:");scanf("%d",&Limit);if (Limit<= 0|Limit> 65536)printf("超出范围!");)else printf("(>n");printf( "I操作系统课程实验In");printf( " (1磁盘调度算法I、n");printf( " IIIn");printf("<)n");printf("

13、I1. 先来先服务算法(FCFS)n");printf("n");printf("11 n");printf("1n");printf("1n");printf("1n");printf("1n");printf("1n");printf("1n");printf(n");printf("'11)n" );printf("n");scanf("%d"

14、,&n);if (n=0) exit( 0);printf(" " );2.3.4.最短寻道时间优先算法(SSTF)扫描算法(SCAN)循环扫描算法(CSCAN)请输入你的选择的算法(输入0离开)switch (n) (case 1:SetDI(DiscLine);FCFS(Hand,DiscLine); break;case 2:SetDI(DiscLine);SSTF(Hand,DiscLine); break ;case 3:SetDI(DiscLine);SCAN(Hand,DiscLine, break ;case 4: SetDI(DiscLine);

15、CSCAN(Hand,DiscLine);break ; printf( scanf(/随机生成磁道数/先来先服务算法(FCFS)/随机生成磁道数/最短寻道时间优先算法(SSTF)/随机生成磁道数0, 9);/ 扫描算法(SCAN)/随机生成磁道数/循环扫描算法(CSCAN)"+是否继续(按0结束，按1继续)?"); "%5d”,&Con);)/数组Sour复制到数组Dist ,复制到x个数void CopyL( int Sour, intDist , int x)(int i;for (i= 0;i<=x;i+)(Disti=Souri;)/ 打印

16、输出数组 Pri void Print( int Pri, int x)(int i;for (i= 0;i<=x;i+)(printf( "%5d",Prii);/ 随机生成磁道数 void SetDI( int DiscL)(int i;for (i= 0;i<= 9;i+)(DiscLi=rand()%Limit;随机生成 10 个磁道号printf("+需要寻找的磁道号:");Print(DiscL, 9);/输出随机生成的磁道号printf(" n" );/数组Sour把x位置的数删除，并把y前面的数向前移动，y

17、后的数保持不变(即会出现 2 个 y) void DelInq( int Sour, int x, int y)(int i;for (i=x;i<y;i+)(Souri=Souri+ 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);/复制磁道号到临时数组R

18、Lineprintf( " +按照FCFSU法磁道的访问顺序为:");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-;BestJage1=All; /Best

19、1 存放移动磁道数BestJage0=1; /Best0存放算法的序号为:1Jage+; /排序的序号加1Aver=( float ) All)/ 10;/ 求平均寻道次数printf("n");printf(" + 移动磁道数:<%5d> " ,All);printf( "n");printf( " + 平均寻道长度：*%0.2f* n" ,Aver);printf( "n");/ 冒泡排序 int * Bubble( int pArr, int nFirst, int nEnd)

20、 int nTemp=0;for (int i=nFirst;i<nEnd;+i)for (int j=i;j<nEnd;+j)if (pArri>pArrj)nTemp=pArri;pArri=pArrj;pArrj=nTemp;return pArr;/ 最短寻道时间优先算法(SSTF)void SSTF(int Han, int DiscL) int temp;int k= 1 ,n= 10;int l,r;int i,j,all= 0;/将磁道号按递增排序DiscL=Bubble(DiscL, 0, 10);printf( "n+按照SSTF算法磁道的访问顺

21、序为：")；/判断标志位Han左、右两边的偏移量大小if (DiscLn- 1<=Han)/当前磁头位置大于最外围欲访问磁道for (i=n- 1;i>= 0;i-)printf( "%d " ,DiscLi);all=Han-DiscL 0;elseif (DiscL 0>=Han)/当前磁头位置小于最里欲访问磁道for (i= 0;i<n;i+)printf("%d " ,DiscLi);all=DiscLn- 1-Han;elsewhile (DiscLk<Han) /确定当前磁道在已排的序列中的位置k+;l

22、=k-1; /在磁头位置的前一个欲访问磁道r=k;/磁头欲访问磁道while (l>= 0)&&(r<n)if (Han-DiscLl)<=(DiscLr-Han) / 选择离磁头近的磁道 printf("%d " ,DiscLl);all+=Han-DiscLl;Han=DiscLl;l=l-1;elseprintf("%d " ,DiscLr);all+=DiscLr-Han;Han=DiscLr;r=r+ 1;)if (l=- 1)磁头位置里侧的磁道已访问完(for (j=r;j<n;j+)/访问磁头位置外侧

23、的磁道printf("%d " ,DiscLj);) all+=DiscLn-1-DiscL 0;)if (r=n) /磁头位置外侧的磁道已访问完 for (j=k- 1;j>- 1 ;j-)/访问磁头位置里侧的磁道printf( "%d " ,DiscLj);)all+=DiscLn- 1-DiscL 0;)printf( "n + 移动磁道数:<%5d> n" ,all);printf( " + 平均寻道长度：*%0.2f* n",all/ 10.0);)/ 扫描算法(SCAN)nt SCAN

24、nt Han, int DiscL, int x, int y)int temp;int k= 1 ,n= 10;int l,r;int i,j,all= 0;DiscL=Bubble(DiscL,x,y);/printf("按递增顺序排好的磁道为：")；/for( i=0;i<n;i+)/ printf("%d ",DiscLi);/)/以下算法确定磁道访问顺序if (DiscLn- 1<=Han) /磁头位置大于最外围欲访问磁道for (i=n- 1;i>= 0;i-)printf("%d " ,DiscLi);

25、all=Han-DiscL 0;)elseif (DiscL 0>=Han) /磁头位置小于最里欲访问磁道for (i= 0;i<n;i+)printf( all=DiscLn-"%d " ,DiscLi);1-Han;)else/磁头位置在最里侧磁道与最外侧磁道之间int d;while (DiscLk<Han)/确定当前磁道在已排的序列中的位置k+;)l=k-1; /在磁头位置的前一个欲访问磁道r=k;/磁头欲访问磁道printf("n请输入当前磁头移动的方向(0表示向内，1表示向外)："); scanf("%d"

26、;,&d);/确定磁头访问的方向printf("按照SCANT法访问顺序为：");if (d=0|d= 1) if (d=0)磁头向内for (j=l;j>= 0;j-) printf("%d " ,DiscLj);) for (j=r;j<n;j+) printf("%d " ,DiscLj);) all=Han-2*DiscL 0+DiscLn- 1;) if (d=1)/磁头向外for (j=r;j<n;j+)printf("%d " ,DiscLj);) for (j=l;j>

27、;= 0;j-) printf("%d " ,DiscLj);) all=2*DiscLn- 1-Han-DiscL 0;) ) elseprintf("请输入 0 或 1!");)printf( "n +移动磁道数:<%5d> n" ,all);printf( " + 平均寻道长度：*%0.2f* n" ,all/ 10.0);return 0;"/循环扫描算法(CSCANVoid CSCAN(nt Han, int DiscL口) int temp;int l,r;int i,j,all= 0;int k= 1 ,n= 10;/对访问磁道按由小到大顺序排列输出DiscL=Bubble(DiscL, 0, 10);/printf("按递增顺序排好的磁道为：")；/for( i=0;i<n;i+) / printf("%d ",DiscLi);/)if (DiscLn- 1<=Han)/磁头位置