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

1、磁盤調(diào)度算法學(xué)生:學(xué)生學(xué)號:專業(yè)班級:指導(dǎo)老師：2013年6 月 20日1、實驗?zāi)康?：通過這次實驗，加深對磁盤調(diào)度算法的理解，進一步掌握先來先 服務(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、需求分析 通過這次實驗，加深對磁盤

2、調(diào)度算法的理解，進一步掌握先來先 服務(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;/ 平均尋道長度移動的序列?。?） 程序所

3、能達到的功能；模擬先來先服務(wù) FCFS、最短尋道時間優(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ù)類型的定義、 主程序的流程以 及

4、各程序模塊之間的層次 （調(diào)用） 關(guān)系。int TrackOrderMaxNumber;/ 被訪問的磁道號序列int MoveDistanceMaxNumber=0;/ 移動距離double AverageDistance=0;/ 平均尋道長度int direction;/ 尋道方向int Num;/ 訪問的磁道號數(shù)目int start;/ 開 始 磁 道 號5、詳細設(shè)計實現(xiàn)程序模塊的具體算法6、調(diào)試分析(1) 調(diào)試過程中遇到的問題以及解決方法，設(shè)計與實現(xiàn)的回顧討 論和分析；在SCAN_CSA算N法中在訪問不同的數(shù)組時沒有注意到上一個磁 道號和要訪問的磁道號的大小比較導(dǎo)致結(jié)果不對， 后來在分析結(jié)

5、果中 找出原因。(2) 算法的性能分析 ( 包括基本操作和其它算法的時間復(fù)雜度和空間復(fù)雜度的分析 ) 及其改進設(shè)想；FCFS：時間復(fù)雜度為 O（1） 空間復(fù)雜度為： O（1）SSTF：時間復(fù)雜度為 O（n2） 空間復(fù)雜度為： O（1）SCAN_CSA：N時間復(fù)雜度為 O（ n2） 空間復(fù)雜度為： O（1） 7、用戶使用說明程序的使用說明，列出每一步的操作步驟（ 1）輸入開始磁道號（ 2）輸入訪問磁道號總數(shù)（ 3）輸入訪問磁道號序列序列（4）選擇算法（ 5）選擇方向（ 6）得出結(jié)果8、測試結(jié)果請塔J繼續(xù)還是結(jié)束，0:繼續(xù)；1:結(jié)束0請選擇算法：1-FCFS, 2-SSTF, 3-SCAN. 4-

6、循環(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 圭冃主冃主51601018424909483255339163811820均尋道長度：27.77780：繼續(xù)；1：結(jié)束02-SSTF, 3-SCftN, 4-循壞SCAN： 3,0：增加；1：誠少： 1;向離 束FS方距 結(jié)FC問動 是-還號 繼算

7、黑 菱入順1032一選選舅土冃主冃主0 8 5391638118201501321601W18424均尋道長度；27.55569、存在問題在求移動距離時，若調(diào)用的庫函數(shù)求絕對值會更方便！10、心得體會首先要明確磁盤調(diào)度的原理， 畫出算法流程圖！ 這樣在解決問題 時更容易 !11、附錄程序源代碼：#include #define MaxNumber 100void FCFS(int TrackOrderMaxNumber,int MoveDistanceMaxNumber,double AverageDistance,int start,int Num)int i,temp=start,sum=

8、0;cout 移動順序 移動距離 endl;for(i=0;itemp)MoveDistancei=TrackOrderi-temp;elseMoveDistancei=temp-TrackOrderi;sum+=MoveDistancei;temp=TrackOrderi;coutTrackOrderi MoveDistanceiendl;coutendl;AverageDistance=sum*1.0/Num;cout 平均尋道長度： AverageDistanceendl;void SSTF(int TrackOrderMaxNumber,int MoveDistanceMaxNumbe

9、r, double AverageDistance,int start,int Num)int temp=start, sum=0,s,count=0,min;int kindMaxNumber=0;cout 移動順序 移動距離 endl;while(countNum)for(int i=0;itemp)min=TrackOrderi-temp;elsemin=temp-TrackOrderi;s=i;break;int temp1;for( i=0;itemp) temp1=TrackOrderi-temp;elsetemp1=temp-TrackOrderi;if(temp1min & k

10、indi=0)min=temp1;s=i;MoveDistancecount=min; sum+=MoveDistances; temp=TrackOrders;coutTrackOrders MoveDistancesendl; kinds=1;count+;coutendl;AverageDistance=sum*1.0/Num;cout 平均尋道長度： AverageDistanceendl;從小到大排序void paixu(int aMaxNumber,int n,int TrackOrderMaxNumber)/int sym=0;while(sym=0)int kind=0;for

11、(int i=0;iTrackOrders2)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,num1=0,num2=0;cout 移動順序 移動距離 endl;for(i=0

12、;i temp)anum1=i;num1+;elsebnum2=i;num2+;paixu(a,num1,TrackOrder);/ 將數(shù)組按從小到達排序 paixu(b,num2,TrackOrder);/ 將數(shù)組按從小到達排序int s;if(direction=0) / 訪問方向向外for(i=0;inum1;i+)/先訪問 num1并從前往后訪問s=ai;MoveDistances=TrackOrders-temp;sum+=MoveDistances;temp=TrackOrders;coutTrackOrders MoveDistances=0;i-) /再訪問 num2 并且從后

13、往前訪問s=bi;MoveDistances=temp-TrackOrders;sum+=MoveDistances;temp=TrackOrders;coutTrackOrders MoveDistancesendl;else /CSAN 算法s=b0;MoveDistances=temp-TrackOrders; sum+=MoveDistances;temp=TrackOrders;coutTrackOrders MoveDistancesendl;for(i=1;inum2;i+) /再訪問 num2 并且從前往后訪問s=bi; MoveDistances=TrackOrders-te

14、mp;sum+=MoveDistances;temp=TrackOrders;coutTrackOrders MoveDistances=0;i-)/先訪問 num2并且從后往前訪問s=bi;MoveDistances=temp-TrackOrders; sum+=MoveDistances;temp=TrackOrders; coutTrackOrders MoveDistancesendl;if(chioce=3) /SCAN 算法f or(i=0;inum1;i+)/再訪問 num1 并且從前往后訪問s=ai;MoveDistances=TrackOrders-temp; sum+=Mo

15、veDistances;temp=TrackOrders;coutTrackOrders MoveDistancesendl;else /CSAN 算法 s=anum1-1;MoveDistances=TrackOrders-temp; sum+=MoveDistances;temp=TrackOrders; coutTrackOrders MoveDistances=0;i-)/再訪問 num1 并且從后往前訪問 s=ai;MoveDistances=temp-TrackOrders; sum+=MoveDistances;temp=TrackOrders;coutTrackOrders M

16、oveDistancesendl;coutendl;AverageDistance=sum*1.0/Num;cout 平均尋道長度： AverageDistanceendl;void main()int TrackOrderMaxNumber;/ 被訪問的磁道號序列int MoveDistanceMaxNumber=0;/ 移動距離double AverageDistance=0;/ 平均尋道長度int direction;/ 尋道方向int Num;/ 訪問的磁道號數(shù)目int start;/ 開始磁道號int kind=0,chioce;coutstart;coutNum;cout 請輸入被訪問的磁道號序列： ;for(int i=0;iTrackOrderi;while(kind=0)coutchioce;if(c