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

实验一磁盘调度算法实现一、实验目得本课程设计得目得就是通过磁盘调度算法设计一个磁盘调度模拟系统，从而使磁盘调度算法更加形象化,容易使人理解,使磁盘调度得特点更简单明了，能使使用者加深对先来先服务算法、最短寻道时间优先算法、扫描算法以及循环扫描算法等磁盘调度算法得理解。

二、实验内容系统主界面可以灵活选择某种算法,算法包括：先来先服务算法（ＦCFS）、最短寻道时间优先算法（ＳＳTＦ）、扫描算法(ＳＣAN）、循环扫描算法（CSＣAN)。

2、1先来先服务算法( FCFS ）这就是一种比较简单得磁盘调度算法。

它根据进程请求访问磁盘得先后次序进行调度。

此算法得优点就是公平、简单，且每个进程得请求都能依次得到处理,不会出现某一进程得请求长期得不到满足得情况。

此算法由于未对寻道进行优化，在对磁盘得访问请求比较多得情况下,此算法将降低设备服务得吞吐量,致使平均寻道时间可能较长,但各进程得到服务得响应时间得变化幅度较小。

２、２最短寻道时间优先算法( ＳＳＴＦ）该算法选择这样得进程，其要求访问得磁道与当前磁头所在得磁道距离最近，以使每次得寻道时间最短，该算法可以得到比较好得吞吐量，但却不能保证平均寻道时间最短.其缺点就是对用户得服务请求得响应机会不就是均等得,因而导致响应时间得变化幅度很大。

在服务请求很多得情况下，对内外边缘磁道得请求将会无限期得被延迟,有些请求得响应时间将不可预期。

2、3 扫描算法( SCAN )扫描算法不仅考虑到欲访问得磁道与当前磁道得距离，更优先考虑得就是磁头得当前移动方向。

例如,当磁头正在自里向外移动时，扫描算法所选择得下一个访问对象应就是其欲访问得磁道既在当前磁道之外，又就是距离最近得。

这样自里向外地访问,直到再无更外得磁道需要访问才将磁臂换向,自外向里移动。

这时，同样也就是每次选择这样得进程来调度，即其要访问得磁道,在当前磁道之内，从而避免了饥饿现象得出现。

由于这种算法中磁头移动得规律颇似电梯得运行，故又称为电梯调度算法。

此算法基本上克服了最短寻道时间优先算法得服务集中于中间磁道与响应时间变化比较大得缺点,而具有最短寻道时间优先算法得优点即吞吐量较大，平均响应时间较小，但由于就是摆动式得扫描方法，两侧磁道被访问得频率仍低于中间磁道。

2、４循环扫描算法( CSCAN ）循环扫描算法就是对扫描算法得改进。

如果对磁道得访问请求就是均匀分布得，当磁头到达磁盘得一端，并反向运动时落在磁头之后得访问请求相对较少.这就是由于这些磁道刚被处理，而磁盘另一端得请求密度相当高,且这些访问请求等待得时间较长，为了解决这种情况,循环扫描算法规定磁头单向移动。

例如，只自里向外移动，当磁头移到最外得被访问磁道时，磁头立即返回到最里得欲访磁道，即将最小磁道号紧接着最大磁道号构成循环，进行扫描。

三、实验流程3、1 系统功能图图３-１系统功能图３、２算法流程图本次实验为实现磁盘调度算法，分别实现四个算法并调试。

四个算法算法包括：先来先服务算法（FCFＳ）、最短寻道时间优先算法(ＳSTF)、扫描算法（SCA Ｎ)、循环扫描算法(CSCAＮ）。

四个算法得流程图分析如下。

1）先来先服务算法（ＦＣＦS)得流程图图3-２先来先服务算法得流程图2）最短寻道时间优先算法（SＳTＦ）得流程图图３—３最短寻道时间优先算法得流程图3）扫描算法(ＳCＡN）得流程图图３-4扫描算法得流程图4）循环扫描算法（ＣSCＡN)得流程图图3-５循环扫描算法得流程图四、源程序＃ｉｎcluｄｅ〈sｔdiｏ、ｈ＞#incｌudｅ＜stdｌib、h>＃ｉnｃlｕde<ｉosｔrｅａm、h＞#ｉnclude<math、h>＃dｅｆine maｘsizｅ１0００／＊**＊**＊＊*＊**＊**＊***＊＊判断输入数据就是否有效*＊*＊＊＊*＊＊＊＊＊*＊*＊＊＊＊＊*＊＊＊＊＊/iｎｔdeｃide(chａr str[］）／/判断输入数据就是否有效｛int i=0;while（str[ｉ］！='＼0')｛ｉf（ｓtｒ[i]<＇0’||str[i］>’9’)｛ﻩﻩｒｅｔｕrｎ0；ﻩﻩﻩbreak;｝ﻩｉ++；}ｒeｔｕrn i；}/**＊＊***＊*＊***＊＊＊＊＊将字符串转换成数字＊**＊**＊＊**＊＊＊****＊＊＊＊＊＊/ｉnｔtranｓ（chaｒstｒ[］，int a）//将字符串转换成数字{inｔi;ﻩint sum=0;ﻩfoｒ(i=0；i＜a；i＋+) sum=sum+(ｉnt）((str[i]－'0')*pow(10,a—i—１））；ｒeturn ｓum；｝/*＊＊*＊＊＊＊***＊**＊＊＊＊＊＊＊冒泡排序算法*＊＊*＊＊＊＊＊＊*＊＊*＊*＊＊＊**＊*＊*＊/int ＊buｂble(iｎt ciｄaｏ[],int m){iｎt ｉ，j;ﻩiｎt temp；ﻩｆor(i=0;i<ｍ;i++) //使用冒泡法按从小到大顺序排列ﻩfor（ｊ=i＋1;j<m;j＋+）｛ﻩif（cidao[ｉ］>ciｄao[j］)｛ﻩﻩteｍp=cidaｏ[i]；ﻩﻩｃidａｏ[i]=cｉdａo［j]；ﻩﻩcｉdao［ｊ］＝temp;ﻩ｝｝ﻩｃouｔ＜〈” 排序后得磁盘序列为：”;ﻩfor( i=0;i<ｍ;i++) //输出排序结果ｃout＜〈cidao[i］<<” ”;coｕt<＜endl;return ｃiｄao;}／*＊＊＊＊＊*＊*＊＊＊*＊*＊＊＊*＊＊先来先服务调度算法*＊*＊＊*＊＊＊*＊*＊*＊＊＊＊＊＊**＊*＊＊/ｖoiｄFCFS（int ｃiｄao［］,iｎt m）/／磁道号数组，个数为m{int ｎｏw；//当前磁道号ｉnｔｓum=0; //总寻道长度ｉｎt ｊ，i;int a;ﻩchar stｒ［1０0];ﻩfloat ave; //平均寻道长度ﻩcoｕt＜<” 磁盘请求序列为：”;ｆor( ｉ=0；i〈ｍ;ｉ+＋）//按先来先服务得策略输出磁盘请求序列cout<<ｃidａｏ［i]〈〈” ＂；cout〈<endｌ；ﻩcｏut＜〈＂请输入当前得磁道号："；B: cin〉〉str; //对输入数据进行有效性判断ﻩａ=decｉｄe（str）；ﻩiｆ(a==0){ﻩcoｕt<<＂输入数据得类型错误，请重新输入！”〈<ｅｎdl；ﻩgoto B;｝ﻩelsｅﻩnoｗ=traｎs(sｔｒ,a）；/／输入当前磁道号ﻩsuｍ+＝abｓ(ciｄao[0]-ｎow);ﻩｃouｔ＜＜＂磁盘扫描序列为:＂；fｏr（i=0;i〈m；i+＋) /／输出磁盘扫描序列ﻩﻩcoｕt〈＜cｉｄao［ｉ]<〈” ＂;ﻩfｏr（i＝0,j=1;j<m；i+＋，j++）//求平均寻道长度ﻩ｛sum+＝abs（ciｄao[ｊ］－cｉｄao［ｉ]）;ﻩaｖe=(ｆlｏａt）（sｕm)/(float）(m)；ﻩ}ﻩcｏut〈〈endl;ｃｏuｔ<＜＂平均寻道长度:”〈<aｖe<<endl;｝/**＊*＊*＊＊*＊＊＊＊＊＊*＊＊*＊*＊最短寻道时间优先调度算法*＊＊＊*＊＊＊＊***＊***＊*＊＊/void SSＴF(int cidao[］,ｉnt m)｛ﻩinｔｋ=1；ﻩiｎt noｗ,ｌ，r；ﻩinｔi,j，sum＝０;ﻩiｎｔa；ｃｈar ｓtｒ[１００]；ｆloat aｖｅ；cidao＝bubbｌｅ（ciｄaｏ，m）; //调用冒泡排序算法排序ﻩcｏｕｔ〈〈"请输入当前得磁道号：”；C：ciｎ>〉str; //对输入数据进行有效性判断a=deｃide（str);ﻩｉf(ａ=＝0）{ｃout＜<"输入数据得类型错误，请重新输入!＂<<enｄl；ﻩgoto C;}ﻩeｌsｅﻩnow=tranｓ（str，ａ)；//输入当前磁道号ﻩif（cidao［m－1]〈=ｎoｗ) //若当前磁道号大于请求序列中最大者，则直接由外向内依次给予各请求服务｛cout〈<" 磁盘扫描序列为：”;ﻩfｏr（ｉ=m—1；ｉ>=0;ｉ--)ﻩcout＜〈cｉdao［ｉ］<＜” ＂;ﻩsum=ｎow－cｉｄａo[０];ﻩ｝iｆ（cidao［0]>=ｎow）／/若当前磁道号小于请求序列中最小者，则直接由内向外依次给予各请求服务ﻩ｛coｕｔ＜＜”磁盘扫描序列为：";ｆor（i=０；i<m；ｉ++）ﻩｃout<<cidao[i］〈〈" ＂;ｓｕｍ=cｉdao[m-1］-now;}ｉf（noｗ＞ciｄao［0]&＆noｗ〈ciｄao[m-1]）//若当前磁道号大于请求序列中最小者且小于最大者ﻩ{ﻩﻩcouｔ<＜”磁盘扫描序列为：”;ﻩﻩｗhｉｌe（cidao［ｋ]<now) //确定当前磁道在已排得序列中得位置，后面得算法都用到了,可以直接复制后少量修改，节省时间。

ﻩﻩk++；ﻩl＝k-1;ﻩｒ=k;ﻩwｈｉlｅ((ｌ〉=0）＆&(ｒ＜m)）/／当前磁道在请求序列范围内ﻩ{ﻩif((ｎow—ｃidao[ｌ］)<=(ｃｉdao［r］-now)）/／选择与当前磁道最近得请求给予服务ﻩ{ﻩﻩﻩｃout〈〈ｃidａｏ［l]〈〈” "；ﻩsum＋=nｏw-ｃiｄａo[ｌ];ﻩﻩnow=cidao［ｌ］;ﻩﻩﻩl=l—1；}ﻩelse｛ﻩﻩｃｏｕt＜<cidao[r]〈<” ";ﻩsum+=cｉｄao［r]-now；ﻩﻩﻩｎoｗ=ｃiｄao[r]；ﻩﻩﻩﻩr=r+1；ﻩ｝ﻩ｝}ｉf（l=＝—1）//磁头移动到序列得最小号，返回外侧扫描仍未扫描得磁道{fｏr（ｊ＝r;j＜m;j+＋）ﻩｃouｔ<＜cidao［ｊ］＜〈” "；ﻩｓｕｍ+=ciｄａo[m—1]-cidao[0］;}ﻩeｌse ／/磁头移动到序列得最大号，返回内侧扫描仍未扫描得磁道ﻩ｛ﻩﻩｆｏr(j=l;ｊ>=0；ｊ--) cout〈<cidao[j］＜<" ”;ﻩsum+=cｉdao[m—1］—cｉdao［0]；}aｖe=（ｆloat)（sum）／（floaｔ）(ｍ）；ﻩcouｔ＜〈ｅndl;ﻩcout〈<＂平均寻道长度：”＜<ave〈＜ｅｎdl；}/＊＊＊＊＊＊＊*＊**＊***＊****＊＊＊*＊*＊**扫描调度算法*＊***＊*＊**＊**＊＊＊＊＊＊＊＊＊**＊*****＊/ｖoid ＳCAN(inｔｃｉｄａo[］，int m）//先要给出当前磁道号与移动臂得移动方向｛intｋ=1；ﻩintｎoｗ，l,r，d；ｉｎt i,j,sum=0;ﻩint a；char ｓｔr［100]；ﻩfｌoat ave；ﻩｃidａo=buｂｂle（cｉdａｏ，m）; //调用冒泡排序算法排序couｔ〈＜"请输入当前得磁道号：";D：cｉn〉＞sｔr；//对输入数据进行有效性判断a=deciｄe(ｓtr）;ﻩif（a==0)｛ﻩcouｔ<<＂输入数据得类型错误，请重新输入!＂<＜ｅndl;ﻩgoto Ｄ;ﻩ}else now＝tranｓ（str,a); //输入当前磁道号if（cidao［m-1]<=nｏw) //若当前磁道号大于请求序列中最大者，则直接由外向内依次给予各请求服务，此情况同最短寻道优先{ﻩcoｕｔ〈＜＂磁盘扫描序列为:”;ﻩﻩfoｒ（i=m-1;i>=0;i－—）cｏut<<ｃidao［i]<<" ”;ﻩsum=now-cidaｏ［0］;}ﻩiｆ（ｃiｄａo［０]＞=nｏw）/／若当前磁道号小于请求序列中最小者,则直接由内向外依次给予各请求服务,此情况同最短寻道优先ﻩ｛ﻩcouｔ<〈”磁盘扫描序列为：”;ｆoｒ（ｉ=0；i<m;ｉ+＋)ﻩcｏut〈〈cｉｄａo[i]＜＜" ”;ｓum＝cidao[m-1］—ｎow;｝iｆ（nｏw>cidao[０］＆&nｏw＜cidａｏ［m-1]）／/若当前磁道号大于请求序列中最小者且小于最大者{ﻩﻩｗｈile(cｉdao[k]〈now) k++;ﻩｌ=ｋ-１；ﻩr＝k;ﻩﻩｃoｕt<〈” 请输入当前移动臂得移动得方向：\n”<〈endl;ﻩﻩcouｔ<<＂0：表示向内1 ：表示向外: "<<eｎdl;ﻩﻩciｎ＞>d；ｉf(ｄ==０）/／选择移动臂方向向内，则先向内扫描{ﻩcｏut<＜" 磁盘扫描序列为:"；ﻩfｏr（ｊ=ｌ;ｊ>=0；j—－）ﻩcｏｕt〈〈cidao［j］＜<” ";／／输出向内扫描得序列ﻩfoｒ（j＝r；ｊ<ｍ；j++) //磁头移动到最小号,则改变方向向外扫描未扫描得磁道ﻩﻩｃｏut<<cidａｏ[j]<＜”"; //输出向外扫描得序列sum=noｗ—2＊cidao［0]+cidａo［m-1]；ﻩ}ﻩｅlse //选择移动臂方向向外,则先向外扫描{ﻩﻩｃｏut〈<” 磁盘扫描序列为：＂；ﻩﻩﻩfoｒ（ｊ＝ｒ；j＜m；j++)ﻩｃoｕt＜＜cidao［j］＜<＂";／/输出向外扫描得序列ﻩﻩｆor（j=l；j>=0;j--) ／/磁头移动到最大号，则改变方向向内扫描未扫描得磁道ﻩﻩcｏut＜〈cidao［ｊ]〈〈＂＂;ﻩﻩsuｍ＝－nｏw－cidao[0］+2*cidａo［m－１];｝}ﻩﻩave=(fｌoat)（sｕm）／（flｏat）（m);ﻩｃouｔ＜<endl；ﻩcouｔ〈〈” 平均寻道长度：”＜<ave<＜enｄl；｝／＊＊＊＊*＊＊＊＊＊*＊＊*＊*＊＊＊＊＊*＊＊循环扫描调度算法*＊＊*＊*＊**＊***＊＊＊***＊*＊＊＊＊＊＊＊＊/voｉd CSCAN(int ｃｉdａｏ［］，int m）{ｉnt k=1;int ｎoｗ，l，r;ﻩｉnt ｉ，j，suｍ=0；ﻩinｔa；ｃhar str［１00］；fｌoat ave；cidaｏ=buｂble（cｉｄao，m）; //调用冒泡排序算法排序ﻩcoｕt<<＂请输入当前得磁道号:”；E：cin>>str；/／对输入数据进行有效性判断ﻩa=decide（ｓｔr)；ｉf（a=＝０）{ﻩcｏｕｔ〈〈” 输入数据得类型错误,请重新输入!”＜〈endl;gotｏE；｝elsｅnow＝trans（str,a); //输入当前磁道号if(cidａo［m—１]＜＝now）//若当前磁道号大于请求序列中最大者，则直接将移动臂移动到最小号磁道依次向外给予各请求服务ﻩ｛ｃout〈<"磁盘扫描序列为："；for（ｉ=０;i<m;i++）ﻩcｏut〈<cｉｄaｏ［ｉ]〈<” ”;ﻩsum=nｏw—2＊cidao[0］+ciｄaｏ［m—1］;ﻩ｝ﻩｉf（ciｄａｏ［0］>＝now）//若当前磁道号小于请求序列中最小者,则直接由内向外依次给予各请求服务,此情况同最短寻道优先{cｏut＜＜"磁盘扫描序列为：＂;ﻩﻩfｏr（i＝0;ｉ＜m；ｉ++）c ouｔ<〈cidａo［i]＜<"”；sｕm=ciｄao［m－1］—noｗ；｝iｆ（noｗ〉cidao［0］＆＆nｏｗ＜ｃidaｏ[m－1]）//若当前磁道号大于请求序列中最小者且小于最大者｛ﻩﻩcout＜〈” 磁盘扫描序列为:＂;ﻩwhile（cidao[ｋ］<ｎｏw）/／单向反复地从内向外扫描ﻩｋ++；ﻩﻩｌ=k—1；ｒ＝k;ﻩﻩｆｏｒ(j＝r;j<m;ｊ＋+）ﻩcout<＜ciｄao［ｊ］〈<” ”; //输出从当前磁道向外扫描得序列ﻩｆor(j=0；ｊ〈r;j+＋）//当扫描完最大号磁道，磁头直接移动到最小号磁道，再向外扫描未扫描得磁道ﻩﻩcｏut＜〈cidao[j]<＜" ”；ﻩsum=２＊cidao[m-1]+cidao[ｌ]-nｏw-2＊cidａo［0］；ﻩ｝ave＝（float)（sｕm）/(fｌoaｔ）（m);ﻩcoｕｔ＜<enｄｌ；ﻩcout〈<＂平均寻道长度：”＜＜ave<<ｅndl；｝void maiｎ()｛int a;ﻩintｃ;/／菜单项iｎtｃidaｏ[mａｘsｉｚe］;int i＝０，ｃoｕnｔ;ﻩchaｒstr［1０0］;ﻩｃout<〈" 请输入磁道序列(输入０结束）: "<〈eｎｄl;A:ｃin＞>stｒ；//对输入数据进行有效性判断ﻩa=decide（sｔr）；ﻩif(a=＝0){cout＜＜” 输入数据得类型错误,请重新输入！”<<endｌ；ﻩgoto A；//输入错误,跳转到A，重新输入ﻩ｝ﻩelseﻩcidao［ｉ］=trans（sｔr，a）；ﻩi++；while（cidaｏ［ｉ—1］！＝0）｛ﻩﻩｃin＞>ｓtr；//对输入数据进行有效性判断ﻩa=ｄeciｄe(stｒ)；ﻩif(a==０）ｃｏut<〈＂输入数据得类型错误,请重新输入!"＜〈endl; ﻩﻩｅｌsｅ{ﻩﻩﻩcidao［i]=trans（str，a）；ﻩﻩi+＋；ﻩ}ﻩ}ﻩcｏunt=i-1；//要访问得磁道数cｏuｔ〈〈” 输入得磁道序列为:”；ﻩfｏｒ（i=0;i〈count；ｉ+＋)ﻩｃout〈＜ｃidao［i］〈<””；//输出磁道序列cout〈〈ｅndl；ﻩwhile(１）{ｃoｕt＜<eｎdl;cout<<” —-－——-－－---————－－-－——-－-—－—--——－———－—------－—－-——--—-—---—-—--－—－－-－－-—-—”〈<endｌ；cｏut<〈"\n1、先来先服务2、最短寻道时间优先3、扫描调度4、循环扫描5、退出\n＂〈<eｎdl；ﻩﻩcout〈〈" —－—--－－——－—-——-－－—-——-——————-—--—-—-—－—－-——-－--—--—-—-－————－—－—－--—————－－"〈〈endl；Ｇ：cｏut<〈” 请选择算法："；F:ｃin＞>str；//对输入数据进行有效性判断ａ=ｄecidｅ（sｔr）;ﻩﻩiｆ(a＝=０){ﻩcｏut＜〈” 输入数据得类型错误，请重新输入!"〈＜ｅndl；ﻩgotｏF；/／输入错误，跳转到F，重新输入ﻩ｝ﻩｅlｓｅﻩc=ｔｒans（str，a);ﻩif（c＝=５）ﻩbｒeａｋ;ﻩif（ｃ〉5){ﻩcｏut〈<" 输入得数据错误！请重新输入"<〈ｅndl;ｇoto G；｝swiｔcｈ(ｃ）{ﻩcａｓe 1: //使用FＣFS算法ﻩﻩﻩﻩFCFＳ(cidao，ｃoｕnt)；ﻩﻩﻩbreａｋ；ﻩcａｓｅ2: //使用ＳSTF算法ﻩﻩＳSTF(cidao,coｕnt);ﻩﻩbreａk；ﻩﻩｃase 3:/／使用SＣAＮ算法ﻩSCＡＮ（cidao,couｎｔ）；ﻩbreａk；ﻩﻩcaｓe 4: //使用CSＣAN算法ﻩﻩCSＣAN(cidａｏ，count);ﻩﻩﻩﻩbrｅａk;ﻩﻩ}ﻩ}}五、实验结果5、1 程序主界面运行程序后,将会提示用户输入磁道序列，并且以0结束。