磁盤調(diào)度操作系統(tǒng)實驗報告

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

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

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

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

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

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

7、成數(shù)字 */int trans(char str,int a) /將字符串轉(zhuǎn)換成數(shù)字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+) / 輸出排序結(jié)果cout<<cidaoi<<" "cout<<endl;return cidao;先來先服務調(diào)度算法void FCFS(int cidao,int m) / 磁道號數(shù)組，個數(shù)為 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; / 對輸入數(shù)據(jù)進行有效性判斷a=decide(str);if(a=0)coutvv"輸入數(shù)據(jù)的類型錯誤，請重新輸入！ "<<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;最短尋道時間優(yōu)先調(diào)度算法 */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); /調(diào)用冒泡排序算法排序cout<<" 請輸入當前的磁道號： "C: cin>>str; /對輸入數(shù)據(jù)進行有效性判斷a=decide(str);if(a=0)cout<<" 輸入數(shù)據(jù)的類型錯誤 ,請重新輸入！ "<<endl;goto C;else now=trans(str,a); /輸/ 入當前磁道號if(cidaom-1<=now)

12、 / 若當前磁道號大于請求序列中最大者，則直接由外向 內(nèi)依次給予各請求服務cout<<" 磁盤掃描序列為： "for(i=m-1;i>=0;i-)cout<<cidaoi<<" "sum=now-cidao0;if(cidao0>=now) / 若當前磁道號小于請求序列中最小者， 則直接由內(nèi)向外依 次給予各請求服務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) / 確定當前磁道在已排的序列中的位置， 后面的算法 都用到了，可以直接復制后少量修改，節(jié)省時間。k+;l=k-1;r=k;while(l>=0)&&(r<m) / 當前磁道在請求序列范圍內(nèi)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) / 磁頭移動到序列的最小號，返回外側(cè)掃描仍未掃描的磁道 for(j=r;j<m;j+) cout<<cidaoj<<" " sum+=cidaom-1-cidao0;else /磁頭移動到序列的最大號，返回內(nèi)側(cè)掃描仍未掃描的磁道 for(j=l;j&

15、gt;=0;j-) cout<<cidaoj<<" " sum+=cidaom-1-cidao0;ave=(float)(sum)/(float)(m); cout<<endl;"<<ave<<endl;cout<<" 平均尋道長度：掃描調(diào)度算法/* */ 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); /調(diào)用冒泡排序算法排序cout<<" 請輸入當前的磁道號： "D: cin>>str; / 對輸入數(shù)據(jù)進行有效性判斷a=decide(str);if(a=0)cout<<" 輸入數(shù)據(jù)的類型錯誤 ,請重新輸入！ "<<endl;goto D;else now=trans(str,a); /輸入當前磁道號if(cidaom-1<=now) / 若當前磁道號大于請求序列中最大者，則直接由外向 內(nèi)依次給予各請求服務 ,此情況同最短尋道優(yōu)先cout<<&quo

17、t; 磁盤掃描序列為： "for(i=m-1;i>=0;i-)cout<<cidaoi<<" "sum=now-cidao0;if(cidao0>=now) / 若當前磁道號小于請求序列中最小者， 則直接由內(nèi)向外依次給予各請求服務 ,此情況同最短尋道優(yōu)先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: 表示向內(nèi) 1 :表示向外 : "<<endl;cin>>d;if(d=0) / 選擇移動臂方向向內(nèi)，則先向內(nèi)掃描cout<<" 磁盤掃描序列為： "for(j=l;j>=0;j-) cout<<cidaoj<<" " / 輸出向內(nèi)掃描的序列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-) / 磁頭移動到最大號，則改變方向向內(nèi)掃描未掃描的 磁道cout<<cidaoj<<" &quo

20、t;sum=-now-cidao0+2*cidaom-1;ave=(float)(sum)/(float)(m);cout<<endl;cout<<" 平均尋道長度： "<<ave<<endl;循環(huán)掃描調(diào)度算法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); /調(diào)用冒泡排序算法排序cout<<" 請輸入當前的磁道號： "E

21、: cin>>str; /對輸入數(shù)據(jù)進行有效性判斷a=decide(str);if(a=0)cout<<" 輸入數(shù)據(jù)的類型錯誤 ,請重新輸入！ "<<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) / 若當前磁道號小于請求序列中最小者， 則直接由內(nèi)向外依次給予各請求服務 ,此情況同最短尋道優(yōu)先for(i=0;i<m;i+) cout<<cidaoi<<" " sum=cidaom-1-now;if(now>cidao0&&now<cidaom-1) / 若當前磁道號大于請求序列中最小者且小于最大者cout<<" 磁盤掃描序列為： "while(cidaok<now) / 單

23、向反復地從內(nèi)向外掃描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 結(jié)束 ): "<<endl;A:cin>>str; / 對輸入數(shù)據(jù)進行有效性判斷a=decide(str);if(a=0)cout<<" 輸入數(shù)據(jù)的類型錯誤 ,請重新輸入！ "<<endl;goto A;輸入錯誤，跳轉(zhuǎn)到A，重新輸入else cidaoi

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

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

27、,請重新輸入！ "<<endl;goto F;輸入錯誤，跳轉(zhuǎn)到F,重新輸入else c=trans(str,a); if(c=5) break;if(c>5)cout<<" 輸入的數(shù)據(jù)錯誤！請重新輸入 "<<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;五、實驗結(jié)果5.1程序主界面運行程序后，將會提示用戶輸入磁道序列， 并且以 0 結(jié)束。當用戶輸入磁道所示。請輸/存直序列t輸入瞬頁=L2 34 56 78 8? 23 45 6? 0輸入的磁道序列塊：12 34 56 78 89 23 45 67圖5-1程序主界面5.2先來先服務算法（FCFS運行結(jié)果選擇算法1之后，進入算法1的操作。系統(tǒng)會顯示磁盤的請求序列。用戶需要輸入當前的磁道號，系統(tǒng)會顯示出磁盤的掃描序列和平均尋道長度。由運行結(jié)果可得出，先來先服務算法的平均尋道長度為24.75。先來先服務算法的運行 圖如圖5-2所示。1先來先服務 趴最短尋道時間優(yōu)先 茶掃描調(diào)度 4循環(huán)掃描 退出12號12.7£ M s I i