操作系統(tǒng)磁盤調度算法實驗報告(共26頁)

1、操作系統(tǒng)原理課 程 設 計 報 告 書題 目：磁盤調度 專 業(yè)：網(wǎng)絡工程 學 號： 學生姓名： 指導教師： 完成日期： 目錄第一章 課程設計目的11.1編寫目的1第二章 課程設計內容22.1設計內容22.1.1、先來先服務算法（FCFS）22.1.2、最短尋道時間優(yōu)先算法（SSTF）22.1.3、掃描算法（SCAN）32.1.4、循環(huán)掃描算法（CSCAN）3第三章 系統(tǒng)概要設計43.1模塊調度關系圖43.2模塊程序流程圖43.2.1 FCFS算法53.2.2 SSTF算法63.2.3 SCAN算法73.2.4 CSCAN算法8第四章 程序實現(xiàn)94.1 主函數(shù)的代碼實現(xiàn)94.2.FCFS算法的代

2、碼實現(xiàn)114.3 SSTF算法的代碼實現(xiàn)134.4 SCAN算法的代碼實現(xiàn)154.5 CSCAN算法的代碼實現(xiàn)17第五章 測試數(shù)據(jù)和結果20第六章 總結23第一章 課程設計目的1.1編寫目的本課程設計的目的是通過磁盤調度算法設計一個磁盤調度模擬系統(tǒng)，從而使磁盤調度算法更加形象化，容易使人理解，使磁盤調度的特點更簡單明了，能使使用者加深對先來先服務算法、最短尋道時間優(yōu)先算法、掃描算法以及循環(huán)掃描算法等磁盤調度算法的理解24第二章 課程設計內容2.1設計內容 系統(tǒng)主界面可以靈活選擇某種算法，算法包括：先來先服務算法（FCFS）、最短尋道時間優(yōu)先算法（SSTF）、掃描算法（SCAN）、循環(huán)掃描算法（

3、CSCAN）。2.1.1、先來先服務算法（FCFS）這是一種比較簡單的磁盤調度算法。它根據(jù)進程請求訪問磁盤的先后次序進行調度。此算法的優(yōu)點是公平、簡單，且每個進程的請求都能依次得到處理，不會出現(xiàn)某一進程的請求長期得不到滿足的情況。此算法由于未對尋道進行優(yōu)化，在對磁盤的訪問請求比較多的情況下，此算法將降低設備服務的吞吐量，致使平均尋道時間可能較長，但各進程得到服務的響應時間的變化幅度較小。2.1.2、最短尋道時間優(yōu)先算法（SSTF）該算法選擇這樣的進程，其要求訪問的磁道與當前磁頭所在的磁道距離最近，以使每次的尋道時間最短，該算法可以得到比較好的吞吐量，但卻不能保證平均尋道時間最短。其缺點是對用戶

4、的服務請求的響應機會不是均等的，因而導致響應時間的變化幅度很大。在服務請求很多的情況下，對內外邊緣磁道的請求將會無限期的被延遲，有些請求的響應時間將不可預期。2.1.3、掃描算法（SCAN）掃描算法不僅考慮到欲訪問的磁道與當前磁道的距離，更優(yōu)先考慮的是磁頭的當前移動方向。例如，當磁頭正在自里向外移動時，掃描算法所選擇的下一個訪問對象應是其欲訪問的磁道既在當前磁道之外，又是距離最近的。這樣自里向外地訪問，直到再無更外的磁道需要訪問才將磁臂換向，自外向里移動。這時，同樣也是每次選擇這樣的進程來調度，即其要訪問的磁道，在當前磁道之內，從而避免了饑餓現(xiàn)象的出現(xiàn)。由于這種算法中磁頭移動的規(guī)律頗似電梯的運

5、行，故又稱為電梯調度算法。此算法基本上克服了最短尋道時間優(yōu)先算法的服務集中于中間磁道和響應時間變化比較大的缺點，而具有最短尋道時間優(yōu)先算法的優(yōu)點即吞吐量較大，平均響應時間較小，但由于是擺動式的掃描方法，兩側磁道被訪問的頻率仍低于中間磁道。2.1.4、循環(huán)掃描算法（CSCAN）循環(huán)掃描算法是對掃描算法的改進。如果對磁道的訪問請求是均勻分布的，當磁頭到達磁盤的一端，并反向運動時落在磁頭之后的訪問請求相對較少。這是由于這些磁道剛被處理，而磁盤另一端的請求密度相當高，且這些訪問請求等待的時間較長，為了解決這種情況，循環(huán)掃描算法規(guī)定磁頭單向移動。例如，只自里向外移動，當磁頭移到最外的被訪問磁道時，磁頭立

6、即返回到最里的欲訪磁道，即將最小磁道號緊接著最大磁道號構成循環(huán)，進行掃描第三章 系統(tǒng)概要設計3.1模塊調度關系圖該系統(tǒng)包含的各個模塊及個模塊之間的關系如下圖：3.2模塊程序流程圖3.2.1 FCFS算法（先來先服務）流程圖:3.2.2 SSTF算法（最短尋道時間優(yōu)先算法）算法流程圖：3.2.3 SCAN算法（掃描算法）流程圖：3.2.4 CSCAN算法（循環(huán)掃描算法）流程圖：第四章 程序實現(xiàn)4.1 主函數(shù)的代碼實現(xiàn)主函數(shù)包含了系統(tǒng)的輸入輸出語句，及以及對輸入輸出有效性的判斷，在C語言中不提倡使用go to語句；但是為了實現(xiàn)輸入磁道號錯誤后能夠重新輸入，提高程序的可用性我仍然使用了go to語句

7、，主函數(shù)代碼如下：void main()int a;int c; /菜單項int cidaomaxsize;int i=0,count;char str100;cout<<"請輸入磁道序列（0結束）："<<endl;A:cin>>str; /對輸入數(shù)據(jù)進行有效性判斷 a=decide(str); if(a=0) cout<<"輸入數(shù)據(jù)的類型錯誤,請重新輸入！"<<endl; goto A;/輸入錯誤，跳轉到A，重新輸入 else cidaoi=trans(str,a); i+; while(ci

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

9、 cout<<endl; cout<<"*"<<endl; cout<<"* 系統(tǒng)菜單 *"<<endl; cout<<"*"<<endl; cout<<"* *"<<endl; cout<<"* 1. 先來先服務 *"<<endl; cout<<"* *"<<endl; cout<<"* 2. 最短

10、尋道時間優(yōu)先 *"<<endl; cout<<"* *"<<endl; cout<<"* 3. 掃描調度 *"<<endl; cout<<"* *"<<endl; cout<<"* 4. 循環(huán)掃描 *"<<endl; cout<<"* *"<<endl; cout<<"* 5. 退出 *"<<endl; cout

11、<<"* *"<<endl; cout<<"*"<<endl; cout<<"*"<<endl;G:cout<<"請選擇算法："F:cin>>str; /對輸入數(shù)據(jù)進行有效性判斷 a=decide(str); if(a=0) cout<<"輸入數(shù)據(jù)的類型錯誤,請重新輸入！"<<endl; goto F;/輸入錯誤，跳轉到F，重新輸入 else c=trans(str,a); i

12、f(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: /使用CSCAN算法 CSCAN(cidao,count); break; 4.2.FCFS算法的代碼實現(xiàn)先來先服務算法比較容易實現(xiàn)，

13、代碼如下：/*先來先服務調度算法*/void FCFS(int cidao,int m) /磁道號數(shù)組，個數(shù)為m int now;/當前磁道號 int sum=0; /總尋道長度 int j,i;int a;char str100; float ave; /平均尋道長度cout<<"磁盤請求序列為：" for( i=0;i<m;i+) /按先來先服務的策略輸出磁盤請求序列 cout<<cidaoi<<" " cout<<endl; cout<<"請輸入當前的磁道號："

14、B: cin>>str; /對輸入數(shù)據(jù)進行有效性判斷 a=decide(str); if(a=0) cout<<"輸入數(shù)據(jù)的類型錯誤,請重新輸入！"<<endl; goto B; else now=trans(str,a); /輸入當前磁道號 sum+=abs(cidao0-now); cout<<"磁盤掃描序列為：" for( i=0;i<m;i+) /輸出磁盤掃描序列 cout<<cidaoi<<" " for(i=0,j=1;j<m;i+,j+)

15、 /求平均尋道長度 sum+=abs(cidaoj-cidaoi); ave=(float)(sum)/(float)(m); cout<<endl; cout<<"平均尋道長度："<<ave<<endl;4.3 SSTF算法的代碼實現(xiàn)最短尋道時間優(yōu)先算法利用每一次尋道是時候都先尋找最容易找到的磁道。首先判斷數(shù)據(jù)有效性，如果數(shù)據(jù)有效則調用排序算法對磁道序列進行排序，然后判斷磁頭所在的位置，按照算法內容進行尋道，最后算出平均尋道時間。/*最短尋道時間優(yōu)先調度算法*/void SSTF(int cidao,int m)int k=

16、1;int now,l,r;int i,j,sum=0;int a;char str100;float ave;cidao=bubble(cidao,m); /調用冒泡排序算法排序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) /若當前

17、磁道號大于請求序列中最大者，則直接由外向內依次給予各請求服務 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=cidaom-1

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

19、daol<<" " sum+=now-cidaol; now=cidaol; l=l-1; else cout<<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;

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

21、0;float ave;cidao=bubble(cidao,m); /調用冒泡排序算法排序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) /若當前磁道號大于請求序列中最大者，則直接由外向內依次給予各請求服務,此情況同最短尋道優(yōu)先 cou

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

23、amp;&now<cidaom-1) /若當前磁道號大于請求序列中最小者且小于最大者 while(cidaok<now) k+; l=k-1; r=k; cout<<"請輸入當前移動臂的移動的方向 (1 表示向外 ，0表示向內) : " cin>>d; if(d=0) /選擇移動臂方向向內，則先向內掃描 cout<<"磁盤掃描序列為：" for(j=l;j>=0;j-) cout<<cidaoj<<" " /輸出向內掃描的序列 for(j=r;j&l

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

25、oj<<" " sum=-now-cidao0+2*cidaom-1; ave=(float)(sum)/(float)(m); cout<<endl; cout<<"平均尋道長度： "<<ave<<endl;4.5 CSCAN算法的代碼實現(xiàn)/*循環(huán)掃描調度算法*/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); /調用冒泡

26、排序算法排序cout<<"請輸入當前的磁道號：" E: 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&

27、lt;m;i+) cout<<cidaoi<<" " sum=now-2*cidao0+cidaom-1; if(cidao0>=now) /若當前磁道號小于請求序列中最小者，則直接由內向外依次給予各請求服務,此情況同最短尋道優(yōu)先 cout<<"磁盤掃描序列為：" for(i=0;i<m;i+) cout<<cidaoi<<" " sum=cidaom-1-now; if(now>cidao0&&now<cidaom-1) /若當前磁道號大于請求序列中最小者且小于最大者 cout<<"磁盤掃描序列為：" while(cidaok<now) /單向反復地從內向外掃描 k+; l=k-1; r=k; for(j=r;j<m;j+) cout<<cidaoj<<" " /輸出從當前磁道向外掃描的序列 for(j=0;j<r;j+) /當掃描完最大號磁道，磁頭直接