1、x EAST CHINA INSTITUTE OF TECHNOLOGY課程設計報告計算機操作系統課程設計題目：磁盤調度算法學生姓名：專 業：班 級：學 號：指導教師：2014年01月10日 TOC o 1-5 h z HYPERLINK l bookmark36 o Current Document 需求分析01 HYPERLINK l bookmark40 o Current Document 總體設計及分類簡介 011）先來先服務（FCFS）算法012）最短尋道時間優先（SSTF）算法013）掃描調度（SCAN）算法014）循環掃描（C-SCAN）算法01課程設計目的01 HYPERLI

2、NK l bookmark51 o Current Document 課程設計要求02詳細設計及算法流程圖021）總流程圖022）先來先服務（FCFS）算法流程圖033）最短尋道時間優先（SSTF）算法流程圖044）掃描調度（SCAN）算法流程圖055）循環掃描（C-SCAN）算法流程圖06 HYPERLINK l bookmark61 o Current Document 課程設計具體步驟071）定義函數部分主要代碼072）先來先服務（FCFS）算法部分主要代碼073）最短尋道時間優先（SSTF）算法部分主要代碼074）掃描調度（SCAN）算法部分主要代碼095）循環掃描（C-SCAN）算法

3、部分主要代碼09課程設計結果顯示101）先來先服務（FCFS）算法測試結果102）最短尋道時間優先（SSTF）算法測試結果113）掃描調度（SCAN）算法測試結果124）循環掃描（C-SCAN）算法測試結果13 HYPERLINK l bookmark74 o Current Document 課程設計總結14 HYPERLINK l bookmark78 o Current Document 9心得體會15 HYPERLINK l bookmark81 o Current Document 10.參考資料15磁盤調度算法需求分析編譯程序運用磁盤的四種調度算法實現對磁盤的調度，四種算法分別為先

4、來 先服務（FCFS）算法，最短尋道時間優先（SSTF）算法，掃描調度（SCAN）算法， 循環掃描（C-SCAN）算法。總體設計及分類簡介磁盤調度中常用的有四種算法，功能分別如下：先來先服務（FCFS）算法。即先來的請求先被響應。FCFS策略看起來似乎 是相當公平的，但是當請求的頻率過高的時候FCFS策略的響應時間就會大大 延長。FCFS策略為我們建立起一個隨機訪問機制的模型，但是假如用這個策略 反復響應從里到外的請求，那么將會消耗大量的時間。為了盡量降低尋道時間， 看來我們需要對等待著的請求進行適當的排序，而不是簡單的使用FCFS策略。 這個過程就叫做磁盤調度管理。有時候FCFS也被看作是最

5、簡單的磁盤調度算法。最短尋道時間優先（SSTF）算法。要求訪問的磁道，與當前磁頭所在的磁 道距離最近，以使每次的尋道時間最短。掃描調度（SCAN）算法。該算法不僅考慮到欲訪問的磁道與當前磁道間的距 離，更優先考慮的是磁頭當前的移動方向。例如，當磁頭正在自里向外移動時， SCAN算法所考慮的下一個訪問對象，應是其欲訪問的磁道，既在當前磁道之外， 又是距離最近的。這樣自里向外的訪問，直至再無更外的磁道需要訪問時，才將 磁道換向自外向里移動。這時，同樣也是每次選擇這樣的進程來調度，也就是要 訪問的當前位置內距離最近者，這樣，磁頭又逐步地從外向里移動，直至再無更 里面的磁道要訪問，從而避免了出現“饑餓

6、”現像。循環掃描（C-SCAN）算法。當磁頭剛從里向外移動而越過了某一磁道時，恰 好又有一進程請求訪問此磁道，這時，該里程就必須等待，為了減少這種延遲， CSCAN算法規定磁頭單向移動，而本實驗過程中我們所設計的是磁頭從里向外移 動，而從外向里移動時只須改方向而已，本實驗未實現。但本實驗已完全能演示 循環掃描的全過程。課程設計目的熟悉并掌握磁盤管理系統的設計方法，加深對所學各種磁盤調度算法及其算法的特點的了解。掌握磁盤調度的基本概念，比較各種磁盤調度算法的優劣課程設計要求從課程設計的目的出發，通過設計工作的各個環節，達到以下設計要求:對系統進行功能模塊分析、控制模塊分析正確；系統設計要實用；編

7、程簡練，可用，功能全面,具有較好的健壯性；說明書、流程圖要清楚。詳細設計及算法流程圖1.總流程圖2.先來先服務（FCFS）算法流程圖最短尋道時間優先（SSTF）算法流程圖while(ak =0 )&(rn)while(ak =0 )&(rn)for(i=0;in;i+)coutai”;sum=an-1-n ow;移動的 總道數*結束課程設計具體步驟定義函數部分主要代碼#include#includeusing namespace std;void FCFS(int a,int n);void SSTF(int a,int n);void SCAN(int a,int n);void CSCAN

8、(int a,int n);先來先服務(FCFS)算法部分主要代碼void FCFS(int a,int n)(int sum=0,j,i,first=0,now;coutnow;/確定當前磁頭所在位置cout磁盤調度順序為：endl;for( i=0;in;i+)(coutai;for(i=0,j=1;jn;i+,j+)(first+=abs(aj-ai);sum+=first+abs(now-a0);coutendl;cout移動的總磁道數為：sumendl;最短尋道時間優先(SSTF)算法部分主要代碼for(i=0;in;i+)for(j=i+1;jaj)(temp=ai;ai=aj;a

9、j=temp;if(an-1=0;i-)coutai;sum二now-a0;if(l=-1)/磁頭位置里側的磁道已訪問完(for(j=r;jn;j+)/訪問磁頭位置外側的磁道(coutaj-1;j-) 訪問磁頭位置里側的磁道(sum+=an-1-a0;coutendl;cout移動的總道數為:sumendl;掃描調度(SCAN)算法部分主要代碼void SCAN(int a,int n)(int temp;int k=1;int now,l,r;int i,j,sum=0;for(i=0;in;i+)if(an-1=0;i-)coutai;sum二now-a0;循環掃描(C-SCAN)算法部分

10、主要代碼void CSCAN(int a,int n)(int temp;int now,l,r;int i,j,sum=0;int k=1;for(i=0;in;i+)if(an-1=now)/磁頭位置大于最外圍欲訪問磁道(for(i=0;in;i+)coutai;sum二now-2*a0+an-1;課程設計結果顯示1.先來先服務(FCFS)算法測試結果2.最短尋道時間優先（SSTF）算法測試結果3.掃描調度（SCAN）算法測試結果4.循環掃描（C-SCAN）算法測試結果課程設計總結計算機磁盤是一種很重要也很常用的外部設備，其分配也有一定的分配策 略。在操作系統中，作業對磁盤的請求常常要排隊

11、，由此需要一些高效率的磁盤 分配策略算法。（1）先來先服務算法為一種最簡單的磁盤調度算法，它直接根據 作業請求磁盤的先后順序對磁盤進行尋訪，公平、簡單，每個作業的磁盤請求都 可以得到處理，不會出現某個作業的請求長期得不到滿足的情況，但未對尋道方 案進行優化；（2）最短尋道時間優先算法優先選擇距離當前磁頭位置最近的作業 磁道請求，可以使得每次尋道時所用的時間都最短，但不能保證平均周轉時間及 帶權周轉時間最短；（3）電梯算法同時考慮下一個作業磁道請求與當前磁頭位置 的距離和當前磁頭移動方向先選擇當前磁頭之外距離其最近的磁道進行訪問，直 到再無更外的磁道請求，再將磁臂換向，訪問磁頭內側距離當前磁頭位

12、置最近的 作業磁道請求，避免了饑餓現象的出現，每個作業的磁盤請求都可以得到處理， 且使每次尋道時間相對較短；（4）N_SCAN算法同時考慮下一個作業磁道請求與 當前磁頭位置的距離和當前磁頭移動方向，但每次磁臂調轉方向時，將同時處理 在磁頭向一側移動過程當中輸入的作業請求，先選擇當前磁頭之外距離其最近的 磁道進行訪問，直到再無更外的磁道請求，接下來一并考慮在磁頭向外側移動過 程當中輸入的作業請求與磁頭內側未被處理的作業磁道請求，此算法對中間磁道 請求比較有利?？傊?，各種算法都有其長處，也各有不足，需要在實際應用中權 衡利弊，擇優使用才能達到最好的效果。九心得體會在這幾天的課程設計中，由于之前做過

13、相似的實驗，所以在一開的實驗設計 流程圖時還是很快就完成了，不過在接下來的編寫代碼的階段里，出現很大的問 題，花費了很多的時間。好在有老師的耐心細心的指導，一步一步的驗證，一點 一點的改正。每一次的運行看到錯誤都在慢慢的減少，正確的設計結果也在不斷 的靠近，最終取得了成功。由于自己的知識和能力還不到位，在課程設計時間里 經歷了很多困難和挑戰，但我認為，在這過程中的每一次的錯誤和故障，都使我 收獲頗豐，使我成長了很多。當然，這個磁盤調度系統的設計遠非完美，還有很多地方可以改進，例如界 面可以更加友好，資源可以更加節約，算法也還有優化的余地，但是時間有限， 經歷也有限，在課程設計時間允許的范圍內只

14、能做到這樣，我會在課余時間自行 完善該磁盤調度算法程序。每一次的課程設計都是自己對所學知識的強化，是一次難得的動手機會。在 課程設計的每一個步驟的執行中，都要認真的反復的去做，因為一個小小的錯誤 都會導致課程設計結果發生巨大的偏差。完成一個成功的設計，會讓自己學會很 多很多的東西，并且能夠很清楚的看到自己的不足，查補缺漏，繼續學習。通過 自己的動手動腦，既增加了知識，又給了我專業知識以及專業技能上的提升，對 提高自己的思維能力和操作能力有很大的幫助。同時我也會更加努力，認真學習， 爭取在以后的課程中做得更好！十.參考資料計算機操作系統清華大學出版社計算機操作系統實驗指導清華大學出版社附錄:#i

15、nclude#include using namespace std;void FCFS(int a,int n);void SSTF(int a,int n);void SCAN(int a,int n);void CSCAN(int a,int n);int main()磁道的個數功能號磁道的個數功能號int s;cout請輸入當前磁道的個數，按Enter鍵顯示生成的隨機磁道號：n;int *a=new intn;cout生成的隨機磁道號為:srand(unsigned)time(NULL);for(int i=0;in;i+) ai=(rand()%100)+1;coutai;coute

16、ndl;while(1) coutendl; TOC o 1-5 h z cout|endl;磁盤調度算法功能列表|11磁盤調度算法功能列表|11、 先來先服務算法(FCFS)| vvendl;12、 最短尋道時間算法(SSTF)| endl;13、 掃描算法(SCAN)| endl;14、循環掃描算法(CSCAN)|endl;cout|endl;cout|cout|endl;cout|cout|endl;cout|cout|endl;cout|endl;coutI endl;0、退出cout 0、退出cout1endl;coutendl;couts;if(s4)cout數據輸入有誤！請重新輸

17、入：endl;elseswitch(s) case 0: exit(0);break ;case 1:FCFS(a,n); break;case 2:SSTF(a, n);break;case 3:SCAN(a, n);break;case 4:CSCAN(a,n);break;return 0;/先來先服務調度算法(FCFS)void FCFS(int a,int n)int sum=0,j,i,first=0,now;coutnow;/確定當前磁頭所在位置cout磁盤調度順序為：endl;for( i=0;in;i+)/按訪問順序輸出磁道號coutai;計算sumfor(i=0,j=1;j

18、n;i+,j+)first+=abs(aj-ai);/外卜圍磁道與最里面磁道的距離sum+=first+abs(now-a0);coutendl;cout”移動的總磁道數為：sumendl;最短尋道時間算法(SSTF)void SSTF(int a,int n) int temp;int k=1;int now,l,r;int i,j,sum=0;/將磁道號按遞增排序for(i=0;in;i+)for(j=i+1;jaj)temp=ai;ai=aj;aj=temp;cout按遞增順序排好的磁道顯示為：endl;for( i=0;in;i+)coutai ”;/輸出排好的磁道順序coutendl

19、;coutnow;/確定當前磁頭所在位置cout磁盤調度順序為：endl;if(an-1=0;i-)coutai=now)/當前磁頭位置小于最里欲訪問磁道for(i=0;in;i+)coutai;sum=an-1-now;elsewhile(ak=0)&(rn)if(now-al)=(ar-now)/選擇離磁頭近的磁道coutal;sum+=now-al;now=al;l=l-1;elsecoutar;sum+=ar-now;now=ar;r=r+1;if(l=-1)/磁頭位置里側的磁道已訪問完for(j=r;jn;j+)/訪問磁頭位置外側的磁道coutaj-1;j-) 訪問磁頭位置里側的磁道

20、coutaj;sum+=an-1-a0;coutendl;cout”移動的總道數為:sumendl;掃描算法(SCAN)void SCAN(int a,int n)int temp;int k=1;int now,l,r;int i,j,sum=0;for(i=0;in;i+)/對訪問磁道按由小到大順序排列輸出for(j=i+1;jaj)temp=ai;ai=aj;aj=temp;cout”按遞增順序排好的磁道為：endl;for( i=0;in;i+)coutai;coutendl;coutnow;以下算法確定磁道訪問順序if(an-1=0;i-)coutai=now) /磁頭位置小于最里欲訪問磁道for(i=0;in;i+)coutai;sum=an-1-now;else磁頭位置在最里側磁道與最外側磁道之間 int d;while(aknow)確定當前磁道在已排的序列中的位置k+;l=k-1;/在磁頭位置的前一個欲訪問磁道r=k;/磁頭欲訪問磁道coutd;確定磁頭訪問的方向cout=0;j-)coutaj;for(j=r;jn;j+)coutaj;sum=now-2*a0+an-1;if(d=1)/磁頭向外for(j=r;jn;j+)coutaj=0;j-)