磁盤(pán)調(diào)度算法試驗(yàn)報(bào)告材料

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

2、調(diào)度算法的理解，進(jìn)一步掌握先來(lái)先 服務(wù) FCFS、最短尋道時(shí)間優(yōu)先 SSTF、 SCAN 和循環(huán) SCAN 算法的 實(shí)現(xiàn)方法。通過(guò)已知開(kāi)始磁道數(shù)、訪問(wèn)磁道總數(shù)、磁道號(hào)訪問(wèn)序列、訪問(wèn)方 向及訪問(wèn)方式得到訪問(wèn)序列及移動(dòng)距離和平均移動(dòng)距離！(1) 輸入的形式；int TrackOrderMaxNumber;/ 被訪問(wèn)的磁道號(hào)序列int direction;/尋道方向int Num;/ 訪問(wèn)的磁道號(hào)數(shù)目int start;/（2） 輸出的形式；int MoveDistanceMaxNumber=0;/ 移動(dòng)距離double AverageDistance=0;/ 平均尋道長(zhǎng)度移動(dòng)的序列！（3） 程序所

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

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

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

6、循環(huán)SCAN： 2 務(wù)動(dòng)順序 移動(dòng)距離7222 3 0 42 0 16 12 23 13 110 0 4 85988568 - ) u u Ik IL IL IL均尋道長(zhǎng)度：46.7?8繼續(xù)；結(jié)束2-SSTF, 3-SCAN, 4-循環(huán)SCAN： 3 ,0；增加；誠(chéng)少： 0:向離 束FS方距 結(jié)FC間動(dòng) 是還2號(hào) 續(xù)迭道繼算磁序0 譯譯入順5選選0 圭冃主冃主51601018424909483255339163811820均尋道長(zhǎng)度：27.77780：繼續(xù)；1：結(jié)束02-SSTF, 3-SCftN, 4-循壞SCAN： 3,0：增加；1：誠(chéng)少： 1;向離 束FS方距 結(jié)FC問(wèn)動(dòng) 是-還號(hào) 繼算

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

8、0;cout 移動(dòng)順序 移動(dòng)距離 endl;for(i=0;itemp)MoveDistancei=TrackOrderi-temp;elseMoveDistancei=temp-TrackOrderi;sum+=MoveDistancei;temp=TrackOrderi;coutTrackOrderi MoveDistanceiendl;coutendl;AverageDistance=sum*1.0/Num;cout 平均尋道長(zhǎng)度： 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 移動(dòng)順序 移動(dòng)距離 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 平均尋道長(zhǎng)度： 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 移動(dòng)順序 移動(dòng)距離 endl;for(i=0

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

13、往前訪問(wèn)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+) /再訪問(wèn) num2 并且從前往后訪問(wèn)s=bi; MoveDistances=TrackOrders-te

14、mp;sum+=MoveDistances;temp=TrackOrders;coutTrackOrders MoveDistances=0;i-)/先訪問(wèn) num2并且從后往前訪問(wèn)s=bi;MoveDistances=temp-TrackOrders; sum+=MoveDistances;temp=TrackOrders; coutTrackOrders MoveDistancesendl;if(chioce=3) /SCAN 算法f or(i=0;inum1;i+)/再訪問(wèn) num1 并且從前往后訪問(wèn)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-)/再訪問(wèn) num1 并且從后往前訪問(wèn) s=ai;MoveDistances=temp-TrackOrders; sum+=MoveDistances;temp=TrackOrders;coutTrackOrders M

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