磁盤調(diào)度算法實驗報告材料

1、磁盤調(diào)度算法學(xué)生:學(xué)生學(xué)號:專業(yè)班級:指導(dǎo)老師：2013年6月20日1、實驗?zāi)康?：通過這次實驗，加深對磁盤調(diào)度算法的理解，進(jìn)一步掌握先來先 服務(wù)FCFS、最短尋道時間優(yōu)先 SSTF、SCAN和循環(huán)SCAN算法的 實現(xiàn)方法。2、問題描述：設(shè)計程序模擬先來先服務(wù) FCFS、最短尋道時間優(yōu)先SSTF、SCAN 和循環(huán) SCAN 算法的工作過程。假設(shè)有 n 個磁道號所組成的磁道訪 問序列，給定開始磁道號 m 和磁頭移動的方向(正向或者反向) ，分 別利用不同的磁盤調(diào)度算法訪問磁道序列， 給出每一次訪問的磁頭移 動距離，計算每種算法的平均尋道長度。3、需求分析 通過這次實驗，加深對磁盤調(diào)度算法的理解，

2、進(jìn)一步掌握先來先服務(wù)FCFS、最短尋道時間優(yōu)先 SSTF、SCAN和循環(huán)SCAN算法的 實現(xiàn)方法。通過已知開始磁道數(shù)、訪問磁道總數(shù)、磁道號訪問序列、訪問方 向及訪問方式得到訪問序列及移動距離和平均移動距離！(1) 輸入的形式；int TrackOrderMaxNumber;/ 被訪問的磁道號序列int direction;/尋道方向int Num;/ 訪問的磁道號數(shù)目int start;/（2） 輸出的形式；int MoveDistanceMaxNumber=0;/ 移動距離double AverageDistance=0;/ 平均尋道長度移動的序列?。?）程序所能達(dá)到的功能；模擬先來先服務(wù)F

3、CFS、最短尋道時間優(yōu)先SSTF、SCAN和循環(huán)SCAN 算法的工作過程。假設(shè)有 n 個磁道號所組成的磁道訪問序列， 給定開始磁道號 m 和磁頭移動的方向（正向或者反向） ，分別利用不 同的磁盤調(diào)度算法訪問磁道序列，給出每一次訪問的磁頭移動距離， 計算每種算法的平均尋道長度。（4）測試數(shù)據(jù)，包括正確的輸入及其輸出結(jié)果和含有錯誤的輸入及其 輸出結(jié)果。開始磁道號： 100磁道號方向：（0）和外（ 1）磁道號數(shù)目： 9頁面序列： 55 58 39 18 90 160 150 38 1844、概要設(shè)計說明本程序中用到的所有抽象數(shù)據(jù)類型的定義、 主程序的流程以 及各程序模塊之間的層次 （調(diào)用） 關(guān)系。i

4、nt TrackOrderMaxNumber;被訪問的磁道號序列int MoveDista nceMaxNumber二0;/移動距離double AverageDista nce=0;平均尋道長度int directio n;尋道方向int Num;/訪問的磁道號數(shù)目intstart;/開 始 磁 道 號流程圖主因魏出門)5、詳細(xì)設(shè)計實現(xiàn)程序模塊的具體算法1 * S流程圖裝睛道號下標(biāo)iL1oveDistancei| T rackOrder(i-Etart |>sta rt =Tr ackOr d eri 遴行下一個犠道誇i+r晞直號下標(biāo)IT且其是 最小值Fst3rt=TrackOrder

5、fil進(jìn)行下一個蹴道號i卄流 程 圖SCANICS.VJ槪謹(jǐn)號下標(biāo)ickOrder將其赦入.數(shù)爼已中并排序92AIJ加前向后CSAN的入魏組t中并排序內(nèi)品卜:an orCSAI諺問數(shù)組b從前向后-SCAI從后向后訪問數(shù)組b從后向前“到斷下一個晞道號I 直至挾出滿足柔件的 ittii號6、調(diào)試分析(1) 調(diào)試過程中遇到的問題以及解決方法，設(shè)計與實現(xiàn)的回顧討 論和分析；在scan_csAN法中在訪問不同的數(shù)組時沒有注意到上一個磁道號和要訪問的磁道號的大小比較導(dǎo)致結(jié)果不對，后來在分析結(jié)果中找出原因。(2) 算法的性能分析(包括基本操作和其它算法的時間復(fù)雜度和空間復(fù)雜度的分析)及其改進(jìn)設(shè)想;FCFS:

6、時間復(fù)雜度為0( 1)空間復(fù)雜度為：0(1)SSTF:時間復(fù)雜度為0(n八2)空間復(fù)雜度為：0(1)SCAN_CSAN時間復(fù)雜度為0(nA2)空間復(fù)雜度為：0(1)7、用戶使用說明程序的使用說明，列出每一步的操作步驟(1 )輸入開始磁道號(2) 輸入訪問磁道號總數(shù)(3) 輸入訪問磁道號序列序列(4) 選擇算法(5) 選擇方向(6) 得出結(jié)果8、測試結(jié)果卄序 人入入擇順45 冃青青青竣5口問聖i恥直號：100磁道號數(shù)目：*問前磁道號序列：=1-FCFS, 2-SSTF移動距離58 393-£CfiN,381184P 729 199 216016S 112 S4 146匚均尋道長度：55

7、.3333請塔J繼續(xù)還是結(jié)束，0:繼續(xù)；1:結(jié)束0請選擇算法：1-FCFS, 2-SSTF, 3-SCAN. 4-循環(huán)SCAN： 2 務(wù)動順序 移動距離7222 3 0 42 0 16 12 23 13 110 0 4 85988568 - ) u u Ik IL IL IL均尋道長度：46.7?8繼續(xù)；結(jié)束2-SSTF, 3-SCAN, 4-循環(huán)SCAN： 3 ,0；增加；誠少： 0:向離 束FS方距 結(jié)FC間動 是還2號 續(xù)迭道繼算磁序0 譯譯入順5選選0 圭冃主冃主516010184249094£83255339163811820均尋道長度：27.77780：繼續(xù)；1：結(jié)束02

8、-SSTF, 3-SCftN, 4-循壞SCAN： 3,0：增加；1：誠少： 1;向離 束FS方距 結(jié)FC問動 是-還號 繼算黑 菱入順1032一選選舅土冃主冃主0 8£ 5391638118201501321601W18424均尋道長度；27.5556少減*1ff一續(xù)P,増 用T 70 -0 2 " 一，向離 -一艮 S？LOJ -結(jié)FC問動 一是1-喜 一還.號 一繼算幫 一羸入順10 境舅 一青青士 PE. 08 32石 39 lfe918 2084166佃 24弓竊 10F均尋道低度；31-33339、存在問題在求移動距離時，若調(diào)用C + +的庫函數(shù)求絕對值會更方便

9、!10、心得體會首先要明確磁盤調(diào)度的原理，畫出算法流程圖！這樣在解決問題時更容易！11、附錄程序源代碼：#include <iostream.h>#define MaxNumber 100void FCFS(int TrackOrderMaxNumber,int MoveDistanceMaxNumber,double AverageDistance,int start,int Num)int i,temp=start,sum=0;cout<<" 移動順序 移動距離 "<<endl;for(i=0;i<Num;i+)if(Track

10、Orderi>temp)MoveDistancei=TrackOrderi-temp;elseMoveDistancei=temp-TrackOrderi;sum+=MoveDistancei;temp=TrackOrderi;cout<<TrackOrderi<<" "<<MoveDistancei<<endl;cout<<endl;AverageDistance=sum*1.0/Num;cout<<" 平均尋道長度： "<<AverageDistance<

11、<endl;void SSTF(int TrackOrderMaxNumber,int MoveDistanceMaxNumber, double AverageDistance,int start,int Num)int temp=start, sum=0,s,count=0,min;int kindMaxNumber=0;cout<<" 移動順序 移動距離 "<<endl;while(count<Num)for(int i=0;i<Num;i+)if(kindi=0)if(TrackOrderi>temp)min=Trac

12、kOrderi-temp;elsemin=temp-TrackOrderi;s=i;break;int temp1;for( i=0;i<Num;i+) /找出里此時磁道距離最近的磁道號if(TrackOrderi>temp) temp1=TrackOrderi-temp;elsetemp1=temp-TrackOrderi;if(temp1<min && kindi=0)min=temp1;s=i;MoveDistancecount=min; sum+=MoveDistances; temp=TrackOrders;cout<<TrackOrde

13、rs<<" "<<MoveDistances<<endl; kinds=1;count+;cout<<endl;AverageDistance=sum*1.0/Num;cout<<" 平均尋道長度： "<<AverageDistance<<endl;從小到大排序void paixu(int aMaxNumber,int n,int TrackOrderMaxNumber)/int sym=0;while(sym=0)int kind=0;for(int i=0;i<

14、n-1;i+)int s1=ai;int s2=ai+1;i f(TrackOrders1>TrackOrders2)int s=ai+1;ai+1=ai;ai=s;kind=1;if(kind=0)sym=1;void SCAN_CSAN(int TrackOrderMaxNumber,int MoveDistanceMaxNumber, double AverageDistance,int start,int Num,int direction,int chioce)int sum=0;int aMaxNumber,bMaxNumber;int temp=start;int i,nu

15、m1=0,num2=0;cout<<" 移動順序 移動距離 "<<endl;for(i=0;i<Num;i+)/ 分類if(TrackOrderi> temp)anum1=i;num1+;elsebnum2=i;num2+;paixu(a,num1,TrackOrder);/ 將數(shù)組按從小到達(dá)排序 paixu(b,num2,TrackOrder);/ 將數(shù)組按從小到達(dá)排序int s;if(direction=0) / 訪問方向向外for(i=0;i<num1;i+)先訪問numl并從前往后訪問s=ai;MoveDistances=T

16、rackOrders-temp;sum+=MoveDistances;temp=TrackOrders;cout<<TrackOrders<<" "<<MoveDistances<<endl;if(chioce=3)/SCAN 算法for(i=num2-1;i>=0;i-)/再訪問num2并且從后往前訪問s=bi;MoveDistances=temp-TrackOrders;sum+=MoveDistances;temp=TrackOrders;cout<<TrackOrders<<"

17、"<<MoveDistances<<endl;else /CSAN 算法s=b0;MoveDistances=temp-TrackOrders; sum+=MoveDistances;temp=TrackOrders;cout<<TrackOrders<<" "<<MoveDistances<<endl;for(i=1;i<num2;i+) / 再訪問 num2 并且從前往后訪問s=bi; MoveDistances=TrackOrders-temp;sum+=MoveDistances

18、;temp=TrackOrders;cout<<TrackOrders<<" "<<MoveDistances<<endl;else / 訪問方向向for(i=num2-1;i>=0;i-)先訪問num2并且從后往前訪問s=bi;MoveDistances=temp-TrackOrders; sum+=MoveDistances;temp=TrackOrders; cout<<TrackOrders<<" "<<MoveDistances<<endl;i

19、f(chioce=3) /SCAN 算法for(i=0;i<num1;i+)/ 再訪問 num1 并且從前往后訪問s=ai;MoveDistances=TrackOrders-temp; sum+=MoveDistances;temp=TrackOrders;cout<<TrackOrders<<" "<<MoveDistances<<endl;else /CSAN 算法 s=anum1-1;MoveDistances=TrackOrders-temp; sum+=MoveDistances;temp=TrackOrde

20、rs; cout<<TrackOrders<<" "<<MoveDistances<<endl;f or(i=num1-2;i>=0;i-)/再訪問 num1 并且從后往前訪問 s=ai;MoveDistances=temp-TrackOrders; sum+=MoveDistances;temp=TrackOrders;cout<<TrackOrders<<" "<<MoveDistances<<endl;cout<<endl;AverageDistance=sum*1.0/Num;cout<<" 平均尋道長度： "<<AverageDistance<<endl;void main()int TrackOrderMaxNumber;/ 被訪問的磁道號序列int MoveDistanceMaxNumber=0;/ 移動距離double AverageDistance=0;/ 平均尋道長度int direction;/ 尋道方向int Num;/ 訪問的磁道號數(shù)目int start;/ 開始磁道號int