磁盤調(diào)度操作系統(tǒng)試驗(yàn)報(bào)告

1、實(shí)驗(yàn)一磁盤調(diào)度算法實(shí)現(xiàn)一、實(shí)驗(yàn)?zāi)康谋菊n程設(shè)計(jì)的目的是通過磁盤調(diào)度算法設(shè)計(jì)一個(gè)磁盤調(diào)度模擬系統(tǒng)，從而使磁盤調(diào)度算法更加形象化，容易使人理解，使磁盤調(diào)度的特點(diǎn)更簡(jiǎn)單明了，能使使用者加深對(duì)先來先服務(wù)算法、最短尋道時(shí)間優(yōu)先算法、掃描算法以及循環(huán)掃描算法等磁盤調(diào)度算法的理解。二、實(shí)驗(yàn)內(nèi)容系統(tǒng)主界面可以靈活選擇某種算法，算法包括：先來先服務(wù)算法（FCFS、最短尋道時(shí)間優(yōu)先算法（SSTF、掃描算法（SCAN、循環(huán)掃描算法（CSCAM2.1先來先服務(wù)算法（FCFS）這是一種比較簡(jiǎn)單的磁盤調(diào)度算法。它根據(jù)進(jìn)程請(qǐng)求訪問磁盤的先后次序進(jìn)行調(diào)度。此算法的優(yōu)點(diǎn)是公平、簡(jiǎn)單，且每個(gè)進(jìn)程的請(qǐng)求都能依次得到處理，不會(huì)出現(xiàn)某一

2、進(jìn)程的請(qǐng)求長(zhǎng)期得不到滿足的情況。此算法由于未對(duì)尋道進(jìn)行優(yōu)化，在對(duì)磁盤的訪問請(qǐng)求比較多的情況下，此算法將降低設(shè)備服務(wù)的吞吐量，致使平均尋道時(shí)間可能較長(zhǎng)，但各進(jìn)程得到服務(wù)的響應(yīng)時(shí)間的變化幅度較小。2.2 最短尋道時(shí)間優(yōu)先算法（SSTF）該算法選擇這樣的進(jìn)程，其要求訪問的磁道與當(dāng)前磁頭所在的磁道距離最近，以使每次的尋道時(shí)間最短，該算法可以得到比較好的吞吐量，但卻不能保證平均尋道時(shí)間最短。其缺點(diǎn)是對(duì)用戶的服務(wù)請(qǐng)求的響應(yīng)機(jī)會(huì)不是均等的，因而導(dǎo)致響應(yīng)時(shí)間的變化幅度很大。在服務(wù)請(qǐng)求很多的情況下，對(duì)內(nèi)外邊緣磁道的請(qǐng)求將會(huì)無限期的被延遲，有些請(qǐng)求的響應(yīng)時(shí)間將不可預(yù)期。2.3 掃描算法（SCAN）掃描算法不僅考慮

3、到欲訪問的磁道與當(dāng)前磁道的距離，更優(yōu)先考慮的是磁頭的當(dāng)前移動(dòng)方向。例如，當(dāng)磁頭正在自里向外移動(dòng)時(shí)，掃描算法所選擇的下一個(gè)訪問對(duì)象應(yīng)是其欲訪問的磁道既在當(dāng)前磁道之外，又是距離最近的。這樣自里向外地訪問，直到再無更外的磁道需要訪問才將磁臂換向，自外向里移動(dòng)。這時(shí)，同樣也是每次選擇這樣的進(jìn)程來調(diào)度，即其要訪問的磁道，在當(dāng)前磁道之內(nèi)，從而避免了饑餓現(xiàn)象的出現(xiàn)。由于這種算法中磁頭移動(dòng)的規(guī)律頗似電梯的運(yùn)行，故又稱為電梯調(diào)度算法。此算法基本上克服了最短尋道時(shí)間優(yōu)先算法的服務(wù)集中于中間磁道和響應(yīng)時(shí)間變化比較大的缺點(diǎn)，而具有最短尋道時(shí)間優(yōu)先算法的優(yōu)點(diǎn)即吞吐量較大，平均響應(yīng)時(shí)間較小，但由于是擺動(dòng)式的掃描方法，兩側(cè)

4、磁道被訪問的頻率仍低于中間磁道。2.4 循環(huán)掃描算法（CSCAN）循環(huán)掃描算法是對(duì)掃描算法的改進(jìn)。如果對(duì)磁道的訪問請(qǐng)求是均勻分布的，當(dāng)磁頭到達(dá)磁盤的一端，并反向運(yùn)動(dòng)時(shí)落在磁頭之后的訪問請(qǐng)求相對(duì)較少。這是由于這些磁道剛被處理，而磁盤另一端的請(qǐng)求密度相當(dāng)高，且這些訪問請(qǐng)求等待的時(shí)間較長(zhǎng)，為了解決這種情況，循環(huán)掃描算法規(guī)定磁頭單向移動(dòng)。例如，只自里向外移動(dòng)，當(dāng)磁頭移到最外的被訪問磁道時(shí)，磁頭立即返回到最里的欲訪磁道，即將最小磁道號(hào)緊接著最大磁道號(hào)構(gòu)成循環(huán)，進(jìn)行掃描。三、實(shí)驗(yàn)流程3.1 系統(tǒng)功能圖最短尋道時(shí)間優(yōu)先算法先來先服務(wù)算法磁盤調(diào)度王界面掃描算法循環(huán)掃描算法圖3-1系統(tǒng)功能圖3.2 算法流程圖本

5、次實(shí)驗(yàn)為實(shí)現(xiàn)磁盤調(diào)度算法，分別實(shí)現(xiàn)四個(gè)算法并調(diào)試。四個(gè)算法算法包括：先來先服務(wù)算法（FCFS、最短尋道時(shí)間優(yōu)先算法（SSTF、掃描算法（SCAN、循環(huán)掃描算法（CSCAN四個(gè)算法的流程圖分析如下。1）先來先服務(wù)算法（FCFS的流程圖圖3-2先來先服務(wù)算法的流程圖2）最短尋道時(shí)間優(yōu)先算法（SSTF的流程圖圖3-3最短尋道時(shí)間優(yōu)先算法的流程圖3）掃描算法（SCAN的流程圖圖3-4掃描算法的流程圖4）循環(huán)掃描算法（CSCAN的流程圖隹丹冒咆工桂芋輸加由mm輸刈南苜號(hào)承平解幽港成可場(chǎng)長(zhǎng)魔亓前鸚毒管使用冒泡海庫存圖3-5循環(huán)掃描算法的流程圖四、源程序#include<stdio.h>#inc

6、lude<stdlib.h>#include<iostream.h>#include<math.h>#definemaxsize1000/*判斷輸入數(shù)據(jù)是否有效*/intdecide(charstr)/判斷輸入數(shù)據(jù)是否有效inti=0;while(stri!='0')if(stri<'0'|stri>'9')return0;break;i+;returni;/*將字符串轉(zhuǎn)換成數(shù)字*/inttrans(charstr,inta)將字符串轉(zhuǎn)換成數(shù)字(inti;intsum=0;for(i=0;i<

7、a;i+)sum=sum+(int)(stri-'0')*pow(10,a-i-1);returnsum;/*冒泡排序算法*/int*bubble(intcidao,intm)(inti,j;inttemp;for(i=0;i<m;i+)/使用冒泡法按從小到大順序排列for(j=i+1;j<m;j+)if(cidaoi>cidaoj)temp=cidaoi;cidaoi=cidaoj;cidaoj=temp;cout<<"排序后的磁盤序列為：for(i=0;i<m;i+)/輸出排序結(jié)果cout<<cidaoi<&l

8、t;""cout<<endl;returncidao;/*先來先服務(wù)調(diào)度算法*/voidFCFS(intcidao,intm)/磁道號(hào)數(shù)組，個(gè)數(shù)為mintnow;當(dāng)前磁道號(hào)intsum=0;/總尋道長(zhǎng)度intj,i;inta;charstr100;floatave;/平均尋道長(zhǎng)度cout<<"磁盤請(qǐng)求序列為："for(i=0;i<m;i+)/按先來先服務(wù)的策略輸出磁盤請(qǐng)求序列cout<<cidaoi<<""cout<<endl;cout<<"請(qǐng)輸入

9、當(dāng)前的磁道號(hào)："8: cin>>str;/對(duì)輸入數(shù)據(jù)進(jìn)行有效性判斷a=decide(str);if(a=0)cout<<"輸入數(shù)據(jù)的類型錯(cuò)誤，請(qǐng)重新輸入！"<<endl;gotoB;elsenow=trans(str,a);瑜入當(dāng)前磁道號(hào)sum+=abs(cidao0-now);cout<<"磁盤掃描序列為："for(i=0;i<m;i+)/輸出磁盤掃描序列cout<<cidaoi<<""for(i=0,j=1;j<m;i+,j+)/求平均尋

10、道長(zhǎng)度sum+=abs(cidaoj-cidaoi);ave=(float)(sum)/(float)(m);cout<<endl;cout<<"平均尋道長(zhǎng)度："<<ave<<endl;/*最短尋道時(shí)間優(yōu)先調(diào)度算法*/voidSSTF(intcidao,intm)intk=1;intnow,l,r;inti,j,sum=0;inta;charstr100;floatave;cidao=bubble(cidao,m);/倜用冒泡排序算法排序cout<<"請(qǐng)輸入當(dāng)前的磁道號(hào)："C: cin>&

11、gt;str;/對(duì)輸入數(shù)據(jù)進(jìn)行有效性判斷a=decide(str);if(a=0)cout<<"輸入數(shù)據(jù)的類型錯(cuò)誤，請(qǐng)重新輸入！"<<endl;gotoC;elsenow=trans(str,a);瑜入當(dāng)前磁道號(hào)if(cidaom-1<=now)/若當(dāng)前磁道號(hào)大于請(qǐng)求序列中最大者，則直接由外向內(nèi)依次給予各請(qǐng)求服務(wù)cout<<"磁盤掃描序列為："for(i=m-1;i>=0;i-)cout<<cidaoi<<""sum=now-cidao0;)if(cidao0&g

12、t;=now)/若當(dāng)前磁道號(hào)小于請(qǐng)求序列中最小者，則直接由內(nèi)向外依次給予各請(qǐng)求服務(wù)cout<<"磁盤掃描序列為："for(i=0;i<m;i+)cout<<cidaoi<<""sum=cidaom-1-now;)if(now>cidao0&&now<cidaom-1)/若當(dāng)前磁道號(hào)大于請(qǐng)求序列中最小者且小于最大者cout<<"磁盤掃描序列為："while(cidaok<now)/確定當(dāng)前磁道在已排的序列中的位置，后面的算法都用到了，可以直接復(fù)制后少

13、量修改，節(jié)省時(shí)間。k+;l=k-1;r=k;while(l>=0)&&(r<m)/當(dāng)前磁道在請(qǐng)求序列范圍內(nèi)if(now-cidaol)<=(cidaor-now)/選擇與當(dāng)前磁道最近的請(qǐng)求給予服務(wù)cout<<cidaol<<""sum+=now-cidaol;now=cidaol;l=l-1;)elsecout<<cidaor<<""sum+=cidaor-now;now=cidaor;r=r+1;)if(l=-1)/磁頭移動(dòng)到序列的最小號(hào)，返回外側(cè)掃描仍未掃描的磁道for

14、(j=r;j<m;j+)cout<<cidaoj<<""sum+=cidaom-1-cidao0;)else/B頭移動(dòng)到序列的最大號(hào)，返回內(nèi)側(cè)掃描仍未掃描的磁道(for(j=l;j>=0;j-)cout<<cidaoj<<""sum+=cidaom-1-cidao0;)ave=(float)(sum)/(float)(m);cout<<endl;cout<<"平均尋道長(zhǎng)度："<<ave<<endl;)掃描調(diào)度算法/*/voidS

15、CAN(intcidao,intm)/先要給出當(dāng)前磁道號(hào)和移動(dòng)臂的移動(dòng)方向(intk=1;intnow,l,r,d;inti,j,sum=0;inta;charstr100;floatave;cidao=bubble(cidao,m);/倜用冒泡排序算法排序cout<<"請(qǐng)輸入當(dāng)前的磁道號(hào)："D: cin>>str;/對(duì)輸入數(shù)據(jù)進(jìn)行有效性判斷a=decide(str);if(a=0)cout<<"輸入數(shù)據(jù)的類型錯(cuò)誤，請(qǐng)重新輸入！"<<endl;gotoD;)elsenow=trans(str,a);/輸入當(dāng)

16、前磁道號(hào)if(cidaom-1<=now)/若當(dāng)前磁道號(hào)大于請(qǐng)求序列中最大者，則直接由外向內(nèi)依次給予各請(qǐng)求服務(wù)，此情況同最短尋道優(yōu)先cout<<"磁盤掃描序列為："for(i=m-1;i>=0;i-)cout<<cidaoi<<""sum=now-cidao0;)if(cidao0>=now)/若當(dāng)前磁道號(hào)小于請(qǐng)求序列中最小者，則直接由內(nèi)向外依次給予各請(qǐng)求服務(wù)，此情況同最短尋道優(yōu)先cout<<"磁盤掃描序列為："for(i=0;i<m;i+)cout<<

17、;cidaoi<<""sum=cidaom-1-now;if(now>cidao0&&now<cidaom-1)/若當(dāng)前磁道號(hào)大于請(qǐng)求序列中最小者且小于最大者(while(cidaok<now)k+;l=k-1;r=k;cout<<"請(qǐng)輸入當(dāng)前移動(dòng)臂的移動(dòng)的方向：n"<<endl;cout<<"0:表示向內(nèi)1:表示向外："<<endl;cin>>d;if(d=0)/選擇移動(dòng)臂方向向內(nèi)，則先向內(nèi)掃描(cout<<&quo

18、t;磁盤掃描序列為："for(j=l;j>=0;j-)cout<<cidaoj<<""/輸出向內(nèi)掃描的序列for(j=r;j<m;j+)/磁頭移動(dòng)到最小號(hào)，則改變方向向外掃描未掃描的磁道cout<<cidaoj<<""/輸出向外掃描的序列sum=now-2*cidao0+cidaom-1;else砒擇移動(dòng)臂方向向外，則先向外掃描(cout<<"磁盤掃描序列為："for(j=r;j<m;j+)cout<<cidaoj<<&qu

19、ot;"/輸出向外掃描的序列for(j=l;j>=0;j-)/磁頭移動(dòng)到最大號(hào)，則改變方向向內(nèi)掃描未掃描的磁道cout<<cidaoj<<""sum=-now-cidao0+2*cidaom-1;ave=(float)(sum)/(float)(m);cout<<endl;cout<<"平均尋道長(zhǎng)度："<<ave<<endl;/*循環(huán)掃描調(diào)度算法*/voidCSCAN(intcidao,intm)(intk=1;intnow,l,r;inti,j,sum=0;inta

20、;charstr100;floatave;cidao=bubble(cidao,m);/倜用冒泡排序算法排序cout<<"請(qǐng)輸入當(dāng)前的磁道號(hào)："E: cin>>str;/對(duì)輸入數(shù)據(jù)進(jìn)行有效性判斷a=decide(str);if(a=0)cout<<"輸入數(shù)據(jù)的類型錯(cuò)誤，請(qǐng)重新輸入！"<<endl;gotoE;elsenow=trans(str,a);瑜入當(dāng)前磁道號(hào)if(cidaom-1<=now)/若當(dāng)前磁道號(hào)大于請(qǐng)求序列中最大者，則直接將移動(dòng)臂移動(dòng)到最小號(hào)磁道依次向外給予各請(qǐng)求服務(wù)cout<&

21、lt;"磁盤掃描序列為："for(i=0;i<m;i+)cout<<cidaoi<<""sum=now-2*cidao0+cidaom-1;if(cidao0>=now)/若當(dāng)前磁道號(hào)小于請(qǐng)求序列中最小者，則直接由內(nèi)向外依次給予各請(qǐng)求服務(wù)，此情況同最短尋道優(yōu)先cout<<"磁盤掃描序列為："for(i=0;i<m;i+)cout<<cidaoi<<""sum=cidaom-1-now;if(now>cidao0&&n

22、ow<cidaom-1)/若當(dāng)前磁道號(hào)大于請(qǐng)求序列中最小者且小于最大者cout<<"磁盤掃描序列為："while(cidaok<now)/單向反復(fù)地從內(nèi)向外掃描k+;l=k-1;r=k;for(j=r;j<m;j+)cout<<cidaoj<<""/輸出從當(dāng)前磁道向外掃描的序列for(j=0;j<r;j+)/當(dāng)掃描完最大號(hào)磁道，磁頭直接移動(dòng)到最小號(hào)磁道，冉向外掃描未掃描的磁道cout<<cidaoj<<""sum=2*cidaom-1+cidaol-n

23、ow-2*cidao0;ave=(float)(sum)/(float)(m);cout<<endl;cout<<"平均尋道長(zhǎng)度："<<ave<<endl;voidmain()inta;intc;/菜單項(xiàng)intcidaomaxsize;inti=0,count;charstr100;cout<<"請(qǐng)輸入磁道序列(輸入0結(jié)束)："<<endl;A:cin>>str;/對(duì)輸入數(shù)據(jù)進(jìn)行有效性判斷a=decide(str);if(a=0)cout<<"輸入數(shù)

24、據(jù)的類型錯(cuò)誤，請(qǐng)重新輸入！"<<endl;gotoA;/輸入錯(cuò)誤，跳轉(zhuǎn)到A,重新輸入elsecidaoi=trans(str,a);i+;while(cidaoi-1!=0)cin>>str;/對(duì)輸入數(shù)據(jù)進(jìn)行有效性判斷a=decide(str);if(a=0)cout<<"輸入數(shù)據(jù)的類型錯(cuò)誤，請(qǐng)重新輸入！"<<endl;elsecidaoi=trans(str,a);i+;count=i-1;/要訪問的磁道數(shù)cout<<"輸入的磁道序列為："for(i=0;i<count;i+)

25、cout<<cidaoi<<""/輸出磁道序列cout<<endl;while(1)cout<<endl;cout<<"“<<endl;cout<<"n1.先來先服務(wù)2.最短尋道時(shí)間優(yōu)先3.掃描調(diào)度4.循環(huán)掃描5.退出n"<<endl;cout<<"“<<endl;G:cout<<"請(qǐng)選擇算法："F:cin>>str;/對(duì)輸入數(shù)據(jù)進(jìn)行有效性判斷a=decide(str);i

26、f(a=0)cout<<"輸入數(shù)據(jù)的類型錯(cuò)誤，請(qǐng)重新輸入！"<<endl;gotoF;/輸入錯(cuò)誤，跳轉(zhuǎn)到F,重新輸入elsec=trans(str,a);if(c=5)break;if(c>5)cout<<"輸入的數(shù)據(jù)錯(cuò)誤！請(qǐng)重新輸入"<<endl;gotoG;)switch(c)case 1: /使用FCFS算法FCFS(cidao,count);break;case 2: /使用SSTF算法SSTF(cidao,count);break;case 3: /使用SCAN算法SCAN(cidao,co

27、unt);break;case 4: /使用CSCAN算法CSCAN(cidao,count);break;)五、實(shí)驗(yàn)結(jié)果4.1 程序主界面運(yùn)行程序后，將會(huì)提示用戶輸入磁道序列，并且以0結(jié)束。當(dāng)用戶輸入磁道序列后，系統(tǒng)將會(huì)重新顯示用戶輸入的磁道序列。程序主界面運(yùn)行圖如圖5-1所示。請(qǐng)輸入峽道序列輸入日結(jié)束”234£67899234567B輸入的瞳道序列為！1234567889234567圖5-1程序主界面4.2 先來先服務(wù)算法(FCFS運(yùn)行結(jié)果選擇算法1之后，進(jìn)入算法1的操作。系統(tǒng)會(huì)顯示磁盤的請(qǐng)求序列。用戶需要輸入當(dāng)前的磁道號(hào)，系統(tǒng)會(huì)顯示出磁盤的掃描序列和平均尋道長(zhǎng)度。由運(yùn)行結(jié)果可得出，先來先服務(wù)算法的平均尋道長(zhǎng)度為24.75o先來先服務(wù)算法的運(yùn)行圖如圖5-2所示。1.先來先服務(wù)2.最短尋道時(shí)間優(yōu)先3.掃描