1、某某大學課程設計報告課程名稱： 操作系統 設計題目： 模擬磁盤調度算法 系 別： 計算機系 專 業： 計算機科學與技術 組 別： 學生姓名: 學 號: 起止日期: 指導教師: 目錄第一章 需求分析11.1課程設計的簡介11.2課程設計的目的11.3磁盤調度主要思想 11.4課程設計內容2 第二章 概要設計32.1設計思想32.2 數據結構32.3模塊調用關系圖32.4子模塊程序流程圖5第三章 詳細設計63.1模塊劃分6第四章 代碼測試94.1先來先服務94.1最短尋道時間優先114.1掃描算法12第五章 心得體會13第六章 致謝13參考文獻1附源代碼2第一章 需求分析1.1課程設計的簡介這是一

2、個用VC+6.0為工具、C+為編程語言而實現模擬先來先服務算法（FCFS）、最短尋道時間優先算法（SSTF）、掃描算法（SCAN）的一個磁盤調度程序。該程序設計系統主界面可以靈活選擇某種算法并算出磁頭移動的總磁道數以及平均磁道數。1.2課程設計的目的本課程設計的目的是通過設計一個磁盤調度模擬系統，從而使磁盤調度算法更加形象化，容易使人理解，使磁盤調度的特點更簡單明了，能使使用者加深對先來先服務算法（FCFS）、最短尋道時間優先算法（SSTF）、掃描算法（SCAN）等磁盤調度算法的理解。1.3磁盤調度主要思想設備的動態分配算法與進程調度相似，也是基于一定的分配策略的。常用的分配策略有先請求先分配

3、、優先級高者先分配等策略。在多道程序系統中，低效率通常是由于磁盤類旋轉設備使用不當造成的。操作系統中，對磁盤的訪問要求來自多方面，常常需要排隊。這時，對眾多的訪問要求按一定的次序響應，會直接影響磁盤的工作效率，進而影響系統的性能。訪問磁盤的時間因子由3部分構成，它們是查找（查找磁道）時間、等待（旋轉等待扇區）時間和數據傳輸時間，其中查找時間是決定因素。因此，磁盤調度算法先考慮優化查找策略，需要時再優化旋轉等待策略。 平均尋道長度（L）為所有磁道所需移動距離之和除以總的所需訪問的磁道數（N），即： L=（M1+M2+Mi+MN）/N。其中Mi為所需訪問的磁道號所需移動的磁道數。 啟動磁盤執行輸入

4、輸出操作時，要把移動臂移動到指定的柱面，再等待指定扇區的旋轉到磁頭位置下，然后讓指定的磁頭進行讀寫，完成信息傳送。因此，執行一次輸入輸出所花的時間有： 尋找時間磁頭在移動臂帶動下移動到指定柱面所花的時間。 延遲時間指定扇區旋轉到磁頭下所需的時間。 傳送時間由磁頭進程讀寫完成信息傳送的時間。 其中傳送信息所花的時間，是在硬件設計就固定的。而尋找時間和延遲時間是與信息在磁盤上的位置有關。 為了減少移動臂進行移動花費的時間，每個文件的信息不是按盤面上的磁道順序存放滿一個盤面后，再放到下一個盤面上。而是按柱面存放，同一柱面上的各磁道被放滿信息后，再放到下一個柱面上。所以各磁盤的編號按柱面順序（從0號柱

5、面開始），每個柱面按磁道順序，每個磁道又按扇區順序進行排序。1.4課程設計內容系統主界面可以靈活選擇某種算法，算法包括：先來先服務算法（FCFS）、最短尋道時間優先算法（SSTF）、掃描算法（SCAN）。并計算及比較磁頭移動總磁道數和平均磁道數。1.4.1、先來先服務算法（FCFS）這是一種比較簡單的磁盤調度算法。它根據進程請求訪問磁盤的先后次序進行調度。此算法的優點是公平、簡單，且每個進程的請求都能依次得到處理，不會出現某一進程的請求長期得不到滿足的情況。此算法由于未對尋道進行優化，在對磁盤的訪問請求比較多的情況下，此算法將降低設備服務的吞吐量，致使平均尋道時間可能較長，但各進程得到服務的響

6、應時間的變化幅度較小。1.4.2、最短尋道時間優先算法（SSTF）該算法選擇這樣的進程，其要求訪問的磁道與當前磁頭所在的磁道距離最近，以使每次的尋道時間最短，該算法可以得到比較好的吞吐量，但卻不能保證平均尋道時間最短。其缺點是對用戶的服務請求的響應機會不是均等的，因而導致響應時間的變化幅度很大。在服務請求很多的情況下，對內外邊緣磁道的請求將會無限期的被延遲，有些請求的響應時間將不可預期。1.4.3、掃描算法（SCAN）掃描算法不僅考慮到欲訪問的磁道與當前磁道的距離，更優先考慮的是磁頭的當前移動方向。例如，當磁頭正在自里向外移動時，掃描算法所選擇的下一個訪問對象應是其欲訪問的磁道既在當前磁道之外

7、，又是距離最近的。這樣自里向外地訪問，直到再無更外的磁道需要訪問才將磁臂換向，自外向里移動。這時，同樣也是每次選擇這樣的進程來調度，即其要訪問的磁道，在當前磁道之內，從而避免了饑餓現象的出現。由于這種算法中磁頭移動的規律頗似電梯的運行，故又稱為電梯調度算法。此算法基本上克服了最短尋道時間優先算法的服務集中于中間磁道和響應時間變化比較大的缺點，而具有最短尋道時間優先算法的優點即吞吐量較大，平均響應時間較小，但由于是擺動式的掃描方法，兩側磁道被訪問的頻率仍低于中間磁道。第二章 概要設計2.1設計思想本次課程設計我們是以面向對象的思想為主，利用Visual C為工具實現模擬磁盤調度。程序主要是利用冒

8、泡排序函數、FCFS函數、SSTF函數、SCAN函數、CSCAN函數實現函數的功能。利用菜單式的選擇界面，方便的用戶操作。最終對每一種模擬磁盤調度輸出磁頭平均移動的磁道數以及總磁道數。2.2 數據結構該程序主要是利用7個函數。Panduan（）函數：對輸入的字符進行判斷是否合法，zhuanhua（）函數：對輸入合法的字符進行轉化，bubble（）函數：對輸入的磁道進行冒泡排序，FCFS（）函數，即先來先服務函數，SSTF（）函數：最短最短尋道時間函數，SCAN（）函數：掃描函數，CSCAN（）函數：循環掃描函數。各函數之間有點可以相互調用，共同實現要求。本程序主要用到的數據結構為數組、字符串，

9、包括對字符串的合法性判斷，利用數組算磁頭移動的總磁道數，平均移動磁道數。2.3模塊調用關系圖磁盤調度模擬系統先來先服務最短尋道時間優先掃描算法退出 圖2-1 磁盤調度模擬系統2.4子模塊程序流程圖2.4.1先來先服務算法（FCFS）流程圖：2.4.2最短尋道時間優先算法（SSTF）流程圖2.4.3掃描算法（SCAN）流程圖第三章 詳細設計3.1模塊劃分本系統劃分為四個模塊：先來先服務算法模塊int FCFS(int array,int m)、最短尋道時間優先算法模塊int SSTF(int array,int m)、掃描算法模塊int SCAN(int array,int m) 3.1.1 先

10、來先服務算法模塊：int FCFS(int array,int m)輸入磁道號，按先來先服務的策略輸出磁盤請求序列，求平均尋道長度，輸出移動平均磁道數。主要代碼：for(i=0,j=1;j<m;i+,j+) sum+=abs(arrayj-arrayi); ave=(float)(sum)/(float)(m);3.1.2 最短尋道時間優先算法模塊：int SSTF(int array,int m)將磁道號用冒泡法從小到大排序，輸出排好序的磁道序列，輸入當前磁道號，根據前磁道在已排的序列中的位置，選擇掃描的順序，求出平均尋道長度，輸出移動的平均磁道數。主要代碼：for(i=0;i<

11、m;i+) /*使用冒泡法按從小到大順序排列*/for(j=i+1;j<m;j+) if(arrayi>arrayj) temp=arrayi; arrayi=arrayj; arrayj=temp; if(arraym-1<=now) /*若當前磁道號大于請求序列中最大者，則直接由外向內依次給予各請求服務*/ for(i=m-1;i>=0;i-) cout<<arrayi<<" " sum=now-array0;else if(array0>=now) /*若當前磁道號小于請求序列中最小者，則直接由內向外依次給予各請求

12、服務*/ while(l>=0)&&(r<m) /*當前磁道在請求序列范圍內*/ if(now-arrayl)<=(arrayr-now) /*選擇與當前磁道最近的請求給予服務*/ cout<<arrayl<<" " sum+=now-arrayl; now=arrayl; l=l-1; 3.1.3 掃描算法模塊：int SCAN(int array,int m)將磁道號用冒泡法從小到大排序，輸出排好序的序列，輸入當前磁道號，選擇移動臂的移動方向，根據當前磁道在已排的序列中的位置，選擇掃描的順序，求出平均尋道長度，輸

13、出移動的平均磁道數。主要代碼：if(d=0) /*選擇移動臂方向向內，則先向內掃描*/ for(j=l;j>=0;j-) cout<<arrayj<<" " /*輸出向內掃描的序列*/ for(j=r;j<m;j+) /*磁頭移動到最小號，則改變方向向外掃描未掃描的磁道*/ cout<<arrayj<<" " /*輸出向外掃描的序列*/ sum=now-2*array0+arraym-1; else /*選擇移動臂方向向外，則先向外掃描*/ for(j=r;j<m;j+) cout<

14、<arrayj<<" " /*輸出向外掃描的序列*、 for(j=l;j>=0;j-) /*磁頭移動到最大號，則改變方向向內掃描未掃描的磁道*/ cout<<arrayj<<" " sum=-now-array0+2*arraym-1; ave=(float)(sum)/(float)(m);第四章 測試4.1 先來先服務算法輸入磁道序列：65 78 34 23 87 100 18 26當前磁道號：80磁盤掃描序列為：65 78 34 23 87 100 18 26平均尋到長度：31.25磁頭移動總磁道數：

15、2504.2 最短尋道時間優先算法（1）當前磁道號大于磁道序列中的最大的磁道號時 輸入磁道序列：65 78 34 23 87 100 18 26 排序后的磁道序列為：18 23 26 34 65 78 87 100當前磁道號：200磁盤掃描序列為100 87 78 65 34 26 23 18平均尋到長度：22.75磁頭移動總磁道數：182（2）當前磁道號小于磁道序列中的最小的磁道號時輸入磁道序列：65 78 34 23 87 100 18 26排序后的磁道序列為：18 23 26 34 65 78 87 100當前磁道號：10磁盤掃描序列為：18 23 26 34 65 78 87 100平

16、均掃描長度：11.25磁道移動總磁道數：90（3）當前磁道號大于磁道序列中的最小的磁道號且小于最大磁道號時輸入磁道序列：65 78 34 23 87 100 18 26排序后的磁道序列為：18 23 26 34 65 78 87 100當前磁道號：80磁盤掃描序列為：78 87 100 65 34 26 23 18平均掃描長度：13.25磁道移動總磁道數：1064.3 掃描算法（1）當前磁道號大于磁道序列中的最大的磁道號時輸入磁道序列：65 78 34 23 87 100 18 26 排序后的磁道序列為：18 23 26 34 65 78 87 100當前磁道號：200磁盤掃描序列為100 8

17、7 78 65 34 26 23 18平均尋到長度：22.75磁頭移動總磁道數：182（2）當前磁道號小于磁道序列中的最小的磁道號時輸入磁道序列：65 78 34 23 87 100 18 26排序后的磁道序列為：18 23 26 34 65 78 87 100當前磁道號：10磁盤掃描序列為：18 23 26 34 65 78 87 100平均掃描長度：11.25磁道移動總磁道數：90（3）當前磁道號大于磁道序列中的最小的磁道號且小于最大磁道號（磁頭向外）時輸入磁道序列：65 78 34 23 87 100 18 26排序后的磁道序列為：18 23 26 34 65 78 87 100當前磁道

18、號：80請輸入當前移動臂的移動的方向（1表示向外，0表示向內）：1磁盤掃描序列為：87 100 78 65 34 26 23 18平均尋到長度：12.75磁道移動總磁道數：102第五章 心的體會通過這次的課程設計使我認識到要將操作系統這門計算機專業的課學好不僅僅是要把書上的基本知識學好而且還要不斷進行實踐，將所學的跟實踐操作結合起來才能更好地鞏固所學，才能提高自己實踐能力.通過這次的設計使我認識到只停留在表面理解問題是很難使問題得到很好的解決的，實踐能力與理論知識同樣重要。可以說此課程設計的理論難度并不大，但是若要深入發掘其中的東西，并且實際去編程實現，就遇到了相當大的難度。因為與之涉及的很多

19、方面并沒有學過，需要自己去自學和實踐檢驗。通過本次課程設計，通過模擬磁盤調度及進程排隊算法來加深對操作系統中各個磁臂調度算法概念的理解。模擬磁盤調度算法(FCFS,SSTF,SCAN,CSCAN)，實現各種不同調度算法的過程，并計算各算法的平均尋道長度，以便于我們判斷各種算法的優劣以及各種算法使用的場合。對VC+6.0的應用也更加得心應手。第六章 致謝感謝陜粉麗老師和本組成員在這次系統開發過程中對我的幫助參考文獻1 計算機操作系統 高等教育出版社，作者：孫鐘秀，費翔林，駱斌等編著2 VC+深入詳解 電子工業出版社作者：孫鑫，余指導教師評語： 指導教師簽名： 年 月 日成績評定項 目權

20、重成績1、設計過程中出勤、學習態度等方面0.12、設計技術水平0.43、安全程度及可操作程度0.24、設計報告書寫及圖紙規范程度0.3總 成 績 教研室審核意見：教研室主任簽字： 年 月 日教學院（系）審核意見： 主任簽字： 年 月 日附源代碼#include<stdio.h>#include<stdlib.h>#include<iostream.h>#include<math.h>const int maxsize=1000;int panduan(char str); int zhuanhua(char str,int a); int *bu

21、bble(int cidao,int m); int FCFS(int cidao,int m); void SSTF(int cidao,int m);void SCAN(int cidao,int m); int main() int a; int c; int cidaomaxsize; int i=0,count; char str100; cout<<"請輸入磁道序列（0結束）："<<endl; bei1:cin>>str; a=panduan(str); if(a=0) cout<<"輸入數據的類型錯誤,

22、請重新輸入！"<<endl; goto bei1; else cidaoi=zhuanhua(str,a); i+; while(cidaoi-1!=0) cin>>str; a=panduan(str); if(a=0) cout<<"輸入數據的類型錯誤,請重新輸入！"<<endl; else cidaoi=zhuanhua(str,a); i+; count=i-1; cout<<"你輸入的磁道序列為：" for(i=0;i<count;i+) cout<<cid

23、aoi<<" " cout<<endl; while(1) cout<<endl; cout<<"|_|"<<endl; cout<<"| (*_*) 系統菜單 (*_*) |"<<endl; cout<<"|_|"<<endl; cout<<"| |"<<endl; cout<<"| 1. 先來先服務 |"<<endl;

24、 cout<<"| |"<<endl; cout<<"| 2. 最短尋道時間優先 |"<<endl; cout<<"| |"<<endl; cout<<"| 3. 掃描調度 |"<<endl; cout<<"| |"<<endl; cout<<"| 4. 退出 |"<<endl; cout<<"| |"

25、<<endl; cout<<"|_|"<<endl; cout<<"|_|"<<endl; bei7:cout<<"請選擇算法："bei6:cin>>str; a=panduan(str); if(a=0) cout<<"輸入數據的類型錯誤,請重新輸入！"<<endl; goto bei6; else c=zhuanhua(str,a); if(c=5) break; if(c>5) cout<&

26、lt;"數據輸入錯誤！請重新輸入"<<endl; goto bei7; switch(c) case 1: FCFS(cidao,count); break; case 2: SSTF(cidao,count); break; case 3: SCAN(cidao,count); break; return 0;/*判斷輸入數據是否有效*/int panduan(char str) int i=0;while(stri!='0') if(stri<'0'|stri>'9')return 0;break;

27、i+;return i;/*將字符串轉換成數字*/int zhuanhua(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=te

28、mp; cout<<"排序后的磁盤序列為：" for( i=0;i<m;i+) cout<<cidaoi<<" " cout<<endl; return cidao; /*先來先服務調度算法*/int FCFS(int cidao,int m) int now; int sum=0; int j,i;int a;char str100; float ave; cout<<"磁盤請求序列為：" for( i=0;i<m;i+) cout<<cidaoi&

29、lt;<" " cout<<endl; cout<<"請輸入當前的磁道號：" bei2: cin>>str; a=panduan(str); if(a=0) cout<<"輸入數據的類型錯誤,請重新輸入！"<<endl; goto bei2; else now=zhuanhua(str,a); sum+=abs(cidao0-now);cout<<"磁盤掃描序列為：" for( i=0;i<m;i+) cout<<cid

30、aoi<<" " for(i=0,j=1;j<m;i+,j+) sum+=abs(cidaoj-cidaoi); ave=(float)(sum)/(float)(m); cout<<endl; cout<<"平均尋道長度："<<ave<<endl;cout<<"磁頭移動總磁道數："<<sum<<endl;return 0;/*最短尋道時間優先調度算法*/void SSTF(int cidao,int m) int k=1; int

31、now,l,r; int i,j,sum=0; int a; char str100; float ave; cidao=bubble(cidao,m); cout<<"請輸入當前的磁道號：" bei3: cin>>str; a=panduan(str); if(a=0) cout<<"輸入數據的類型錯誤,請重新輸入！"<<endl; goto bei3; else now=zhuanhua(str,a); if(cidaom-1<=now) cout<<"磁盤掃描序列為：&qu

32、ot; 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-now; if(now>cidao0&&now<cidaom-1) cout<<"磁盤掃描序列為：" while(cidaok&

33、lt;now) k+; l=k-1; r=k; while(l>=0)&&(r<m) if(now-cidaol)<=(cidaor-now) cout<<cidaol<<" " 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<<

34、" " sum+=cidaom-1-cidao0; else for(j=l;j>=0;j-) cout<<cidaoj<<" " sum+=cidaom-1-cidao0; ave=(float)(sum)/(float)(m); cout<<endl; cout<<"平均尋道長度： "<<ave<<endl; cout<<"磁頭移動總磁道數："<<sum<<endl;/*掃描調度算法*/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;