1、實驗磁盤調度算法實現一、實驗目的本課程設計的目的是通過磁盤調度算法設計一個磁盤調度模擬系統， 從而使 磁盤調度算法更加形象化， 容易使人理解， 使磁盤調度的特點更簡單明了， 能使 使用者加深對先來先服務算法、 最短尋道時間優先算法、 掃描算法以及循環掃描 算法等磁盤調度算法的理解。二、實驗內容系統主界面可以靈活選擇某種算法，算法包括：先來先服務算法（FCFS）、最短尋道時間優先算法（SSTF、掃描算法（SCAN、循環掃描算法（CSCAN2.1 先來先服務算法（ FCFS ）這是一種比較簡單的磁盤調度算法。 它根據進程請求訪問磁盤的先后次序進 行調度。此算法的優點是公平、簡單，且每個進程的請求都

2、能依次得到處理，不 會出現某一進程的請求長期得不到滿足的情況。此算法由于未對尋道進行優化， 在對磁盤的訪問請求比較多的情況下， 此算法將降低設備服務的吞吐量， 致使平 均尋道時間可能較長，但各進程得到服務的響應時間的變化幅度較小。2.2 最短尋道時間優先算法（ SSTF 、該算法選擇這樣的進程，其要求訪問的磁道與當前磁頭所在的磁道距離最 近，以使每次的尋道時間最短， 該算法可以得到比較好的吞吐量， 但卻不能保證平均 尋道時間最短。 其缺點是對用戶的服務請求的響應機會不是均等的， 因而導致響 應時間的變化幅度很大。 在服務請求很多的情況下， 對內外邊緣磁道的請求將會 無限期的被延遲，有些請求的響

3、應時間將不可預期。2.3 掃描算法（ SCAN 、掃描算法不僅考慮到欲訪問的磁道與當前磁道的距離， 更優先考慮的是磁頭 的當前移動方向。 例如，當磁頭正在自里向外移動時， 掃描算法所選擇的下一個訪問對象應是其欲訪問的磁道既在當前磁道之外，又是距離最近的。這樣自里向外地訪問，直到再無更外的磁道需要訪問才將磁臂換向，自外向里移動。這時， 同樣也是每次選擇這樣的進程來調度， 即其要訪問的磁道，在當前磁道之內，從 而避免了饑餓現象的出現。由于這種算法中磁頭移動的規律頗似電梯的運行，故又稱為電梯調度算法。此算法基本上克服了最短尋道時間優先算法的服務集中于 中間磁道和響應時間變化比較大的缺點，而具有最短尋

4、道時間優先算法的優點即 吞吐量較大，平均響應時間較小，但由于是擺動式的掃描方法，兩側磁道被訪問 的頻率仍低于中間磁道。2.4循環掃描算法（CSCAN）循環掃描算法是對掃描算法的改進。如果對磁道的訪問請求是均勻分布的， 當磁頭到達磁盤的一端，并反向運動時落在磁頭之后的訪問請求相對較少。這是 由于這些磁道剛被處理，而磁盤另一端的請求密度相當高， 且這些訪問請求等待 的時間較長，為了解決這種情況，循環掃描算法規定磁頭單向移動。例如，只自 里向外移動，當磁頭移到最外的被訪問磁道時，磁頭立即返回到最里的欲訪磁道， 即將最小磁道號緊接著最大磁道號構成循環，進行掃描。三、實驗流程3.1系統功能圖嵐盤調度主界

5、面圖3-1系統功能圖3.2算法流程圖本次實驗為實現磁盤調度算法，分別實現四個算法并調試。四個算法算法包 括：先來先服務算法（FCFS、最短尋道時間優先算法（SSTF、掃描算法（SCAN、 循環掃描算法（CSCA）四個算法的流程圖分析如下。1）先來先服務算法（FCFS的流程圖I幵始）輸入磯適序列T顯示鐵盤錯求序列輸入當前磁道號1顯示磁盤掃描序列T顯示平均昭道長痕（結束）圖3-2先來先服務算法的流程圖2）最短尋道時間優先算法（SSTF的流程圖氓；礫復討輸圖3-3最短尋道時間優先算法的流程圖3）掃描算法（SCAN的流程圖虢輸紳的iWwCEE3圖3-4掃描算法的流程圖4) 循環掃描算法(CSCAN的流

6、程圖CEE)圖3-5循環掃描算法的流程圖四、源程序#i nclude<stdio.h>#i nclude<stdlib.h>#i nclude<iostream.h>#in clude<math.h>#defi ne maxsize 1000判斷輸入數據是否有效int decide(char str) /判斷輸入數據是否有效int i=0;while(stri!='0') if(stri<'0'|stri>'9') return 0; break;i+;return i;/*將字符串轉換

7、成數字 */int trans(char str,int a) /將字符串轉換成數字int i;int sum=0;for(i=0;i<a;i+) sum=sum+(int)(stri-'0')*pow(10,a-i-1);return sum;/*冒泡排序算法 */int *bubble(int cidao,int m)int i,j;int temp;for(i=0;i<m;i+) / 使用冒泡法按從小到大順序排列for(j=i+1;j<m;j+)if(cidaoi>cidaoj) temp=cidaoi; cidaoi=cidaoj; cidaoj

8、=temp;cout<<" 排序后的磁盤序列為： "for( i=0;i<m;i+) / 輸出排序結果cout<<cidaoi<<" "cout<<endl;return cidao;先來先服務調度算法void FCFS(int cidao,int m) / 磁道號數組，個數為 mint now;/ 當前磁道號int sum=0; /總尋道長度int j,i;int a;char str100;float ave; /平均尋道長度cout<<" 磁盤請求序列為： "fo

9、r( i=0;i<m;i+) / 按先來先服務的策略輸出磁盤請求序列cout<<cidaoi<<" "cout<<endl;cout<<" 請輸入當前的磁道號： "B: cin>>str; / 對輸入數據進行有效性判斷a=decide(str);if(a=0)coutvv"輸入數據的類型錯誤，請重新輸入！ "<<endl;goto B;else now=trans(str,a); /輸/ 入當前磁道號sum+=abs(cidao0-now);cout<

10、<" 磁盤掃描序列為： "for( i=0;i<m;i+) / 輸出磁盤掃描序列 cout<<cidaoi<<" "for(i=0,j=1;j<m;i+,j+) / 求平均尋道長度sum+=abs(cidaoj-cidaoi); ave=(float)(sum)/(float)(m);cout<<endl;cout<<" 平均尋道長度： "<<ave<<endl;最短尋道時間優先調度算法 */void SSTF(int cidao,int m)i

11、nt k=1;int now,l,r;int i,j,sum=0;int a;char str100;float ave;cidao=bubble(cidao,m); /調用冒泡排序算法排序cout<<" 請輸入當前的磁道號： "C: cin>>str; /對輸入數據進行有效性判斷a=decide(str);if(a=0)cout<<" 輸入數據的類型錯誤 ,請重新輸入！ "<<endl;goto C;else now=trans(str,a); /輸/ 入當前磁道號if(cidaom-1<=now)

12、 / 若當前磁道號大于請求序列中最大者，則直接由外向 內依次給予各請求服務cout<<" 磁盤掃描序列為： "for(i=m-1;i>=0;i-)cout<<cidaoi<<" "sum=now-cidao0;if(cidao0>=now) / 若當前磁道號小于請求序列中最小者， 則直接由內向外依 次給予各請求服務cout<<" 磁盤掃描序列為： "for(i=0;i<m;i+) cout<<cidaoi<<" "sum=ci

13、daom-1-now;if(now>cidao0&&now<cidaom-1) / 若當前磁道號大于請求序列中最小者 且小于最大者cout<<" 磁盤掃描序列為： "while(cidaok<now) / 確定當前磁道在已排的序列中的位置， 后面的算法 都用到了，可以直接復制后少量修改，節省時間。k+;l=k-1;r=k;while(l>=0)&&(r<m) / 當前磁道在請求序列范圍內if(now-cidaol)<=(cidaor-now) / 選擇與當前磁道最近的請求給予 服務cout<

14、;<cidaol<<" "sum+=now-cidaol;now=cidaol;l=l-1;elsecout<<cidaor<<" "sum+=cidaor-now;now=cidaor;r=r+1;if(l=-1) / 磁頭移動到序列的最小號，返回外側掃描仍未掃描的磁道 for(j=r;j<m;j+) cout<<cidaoj<<" " sum+=cidaom-1-cidao0;else /磁頭移動到序列的最大號，返回內側掃描仍未掃描的磁道 for(j=l;j&

15、gt;=0;j-) cout<<cidaoj<<" " sum+=cidaom-1-cidao0;ave=(float)(sum)/(float)(m); cout<<endl;"<<ave<<endl;cout<<" 平均尋道長度：掃描調度算法/* */ void SCAN(int cidao,int m) / 先要給出當前磁道號和移動臂的移動方向 int k=1;int now,l,r,d;int i,j,sum=0;int a;char str100;float ave;cid

16、ao=bubble(cidao,m); /調用冒泡排序算法排序cout<<" 請輸入當前的磁道號： "D: cin>>str; / 對輸入數據進行有效性判斷a=decide(str);if(a=0)cout<<" 輸入數據的類型錯誤 ,請重新輸入！ "<<endl;goto D;else now=trans(str,a); /輸入當前磁道號if(cidaom-1<=now) / 若當前磁道號大于請求序列中最大者，則直接由外向 內依次給予各請求服務 ,此情況同最短尋道優先cout<<&quo

17、t; 磁盤掃描序列為： "for(i=m-1;i>=0;i-)cout<<cidaoi<<" "sum=now-cidao0;if(cidao0>=now) / 若當前磁道號小于請求序列中最小者， 則直接由內向外依次給予各請求服務 ,此情況同最短尋道優先for(i=0;i<m;i+)cout<<cidaoi<<" "sum=cidaom-1-now;if(now>cidao0&&now<cidaom-1) / 若當前磁道號大于請求序列中最小者且小于最大

18、者while(cidaok<now) k+;l=k-1;r=k;cout<<" 請輸入當前移動臂的移動的方向 :n"<<endl;cout<<" 0: 表示向內 1 :表示向外 : "<<endl;cin>>d;if(d=0) / 選擇移動臂方向向內，則先向內掃描cout<<" 磁盤掃描序列為： "for(j=l;j>=0;j-) cout<<cidaoj<<" " / 輸出向內掃描的序列for(j=r;j&

19、lt;m;j+) / 磁頭移動到最小號，則改變方向向外掃描未掃描的磁道cout<<cidaoj<<" " / 輸出向外掃描的序列sum=now-2*cidao0+cidaom-1;cout<<" 磁盤掃描序列為： "for(j=r;j<m;j+) cout<<cidaoj<<" " / 輸出向外掃描的序列for(j=l;j>=0;j-) / 磁頭移動到最大號，則改變方向向內掃描未掃描的 磁道cout<<cidaoj<<" &quo

20、t;sum=-now-cidao0+2*cidaom-1;ave=(float)(sum)/(float)(m);cout<<endl;cout<<" 平均尋道長度： "<<ave<<endl;循環掃描調度算法void CSCAN(int cidao,int m) int k=1;int now,l,r;int i,j,sum=0;int a;char str100;float ave;cidao=bubble(cidao,m); /調用冒泡排序算法排序cout<<" 請輸入當前的磁道號： "E

21、: cin>>str; /對輸入數據進行有效性判斷a=decide(str);if(a=0)cout<<" 輸入數據的類型錯誤 ,請重新輸入！ "<<endl;goto E;else now=trans(str,a); /輸/ 入當前磁道號if(cidaom-1<=now) / 若當前磁道號大于請求序列中最大者，則直接將移動臂移動到最小號磁道依次向外給予各請求服務cout<<" 磁盤掃描序列為： "for(i=0;i<m;i+) cout<<cidaoi<<"

22、"sum=now-2*cidao0+cidaom-1;if(cidao0>=now) / 若當前磁道號小于請求序列中最小者， 則直接由內向外依次給予各請求服務 ,此情況同最短尋道優先for(i=0;i<m;i+) cout<<cidaoi<<" " sum=cidaom-1-now;if(now>cidao0&&now<cidaom-1) / 若當前磁道號大于請求序列中最小者且小于最大者cout<<" 磁盤掃描序列為： "while(cidaok<now) / 單

23、向反復地從內向外掃描k+;l=k-1;r=k;for(j=r;j<m;j+) cout<<cidaoj<<" " / 輸出從當前磁道向外掃描的序列for(j=0;j<r;j+) / 當掃描完最大號磁道，磁頭直接移動到最小號磁道，再 向外掃描未掃描的磁道cout<<cidaoj<<" "sum=2*cidaom-1+cidaol-now-2*cidao0;ave=(float)(sum)/(float)(m);cout<<endl;cout<<" 平均尋道長度：

24、"<<ave<<endl;void main()int a;int c; /菜單項int cidaomaxsize;int i=0,count;char str100;cout<<" 請輸入磁道序列 (輸入 0 結束 ): "<<endl;A:cin>>str; / 對輸入數據進行有效性判斷a=decide(str);if(a=0)cout<<" 輸入數據的類型錯誤 ,請重新輸入！ "<<endl;goto A;輸入錯誤，跳轉到A，重新輸入else cidaoi

25、=trans(str,a);i+;while(cidaoi-1!=0)cin>>str; /對輸入數據進行有效性判斷a=decide(str);if(a=0) cout<<" 輸入數據的類型錯誤 ,請重新輸入！ "<<endl; elsecidaoi=trans(str,a);count=i-1; / 要訪問的磁道數cout<<" 輸入的磁道序列為： "for(i=0;i<count;i+) cout<<cidaoi<<" " / 輸出磁道序列cout<

26、;<endl;while(1)cout<<endl;cout<<""<<endl;4.循cout<<"n 1.先來先服務2.最短尋道時間優先3.掃描調度環掃描5.退出 n"<<endl;cout<<" "<<endl;G:cout<<" 請選擇算法 : "F:cin>>str; /對輸入數據進行有效性判斷a=decide(str);if(a=0)cout<<" 輸入數據的類型錯誤

27、,請重新輸入！ "<<endl;goto F;輸入錯誤，跳轉到F,重新輸入else c=trans(str,a); if(c=5) break;if(c>5)cout<<" 輸入的數據錯誤！請重新輸入 "<<endl; goto G;switch(c)case 1: /使用FCFS算法FCFS(cidao,count);break;case 2: /使用 SSTF 算法SSTF(cidao,count);break;case 3: /使用 SCAN 算法SCAN(cidao,count);break;case 4: /使用

28、 CSCAN 算法CSCAN(cidao,count);break;五、實驗結果5.1程序主界面運行程序后，將會提示用戶輸入磁道序列， 并且以 0 結束。當用戶輸入磁道所示。請輸/存直序列t輸入瞬頁=L2 34 56 78 8? 23 45 6? 0輸入的磁道序列塊：12 34 56 78 89 23 45 67圖5-1程序主界面5.2先來先服務算法（FCFS運行結果選擇算法1之后，進入算法1的操作。系統會顯示磁盤的請求序列。用戶需要輸入當前的磁道號，系統會顯示出磁盤的掃描序列和平均尋道長度。由運行結果可得出，先來先服務算法的平均尋道長度為24.75。先來先服務算法的運行 圖如圖5-2所示。1先來先服務 趴最短尋道時間優先 茶掃描調度 4循環掃描 退出12號12.7£ M s I i