1、操作系統課程設計磁盤調度算法實踐系 院： 信息工程學院學生姓名：耿萬德 學 號：0934110135專 業：計算機科學與技術年 級：計科0901b完成日期：2011年12月指導教師：劉栓屬性職務姓名學號班級組長耿萬德0934110135計科0901b副組長梁光彩0934110149計科0901b成員楊少鈳0943110114計科0901b一、課程設計的性質與任務1、加深對磁盤調度算法的理解，通過編程模擬不同磁盤調度算法的流程。2、培養學生能夠獨立進行知識綜合，獨立開發較大程序的能力。3、培養提高學生軟件開發能力和軟件的調試技術。4、培養學生開發大型程序的方法和相互合作的精神。5、培養學生的創新

2、意識。6、培養學生的算法設計和算法分析能力。7、培養學生對問題進行文字論述和文字表達的能力。二、課程設計的內容及其要求1、可利用先來先服務算法（fcfs即first come first served）、最短尋道時間優先算法（sstf即shortest seek time first）、掃描算法（scan）、循環掃描算法（cscan），來實現磁盤的訪問順序。2、根據磁盤調度算法的不同的特性做好軟件實現的需求分析。3、可根據問題的實際需要，可模擬數據在磁道的存放位置。4、當系統運行時，能直觀地、動態地反映當前磁盤狀態及不同算法的平均尋道時間。5、要求在系統安全狀態的前提下，用戶指定需要訪問的磁道

3、，軟件自動模擬在不同算法情況下，磁盤尋道順序和平均尋道時間。三、課程設計的時間安排 課程設計總時間：8學時四、課程設計的實驗環境硬件環境：cpu intel(r) core2 duo e4600 2.40ghz，內存 ddr2 1.00gb，硬盤 7200轉 160g ，光驅 16x dvd 軟件環境：windows xp sp sp3, visual c+ 6.0 五、正文1、 實驗程序的結構圖（流程圖）；先來先服務算法（fcfs）流程圖:輸入磁道號求平均尋道長度輸出移動的平均磁道數按輸入順序將磁道序列輸出開始結束 最短尋道時間優先算法（sstf）流程圖: 求平均尋道長度選擇與當前磁道距離最

4、近的磁道進行掃描移動到最小（大）號，改向外（內）移動掃描未掃描的磁道輸出移動的平均磁道數輸出排好序的磁道序列判斷當前磁頭在序列中的位置結束開始輸入磁道號使用冒泡法從小到大排序輸入當前磁道號掃描算法（scan）流程圖：求平均尋道長度選擇移動臂移動方向，開始掃描移動到最小（大）號，改向外（內）移動掃描未掃描的磁道輸出移動的平均磁道數輸出排好序的磁道序列開始結束輸入磁道號使用冒泡法從小到大排序輸入當前磁道號判斷當前磁頭在序列中的位置循環掃描算法（cscan）流程圖：求平均尋道長度掃描到最大號后，直接移動到最小號從內向外掃描未掃描的磁道輸出移動的平均磁道數輸出排好序的磁道序列判斷當前磁頭在序列中的位置

5、規定移動臂單向反復的從內向外掃描開始結束輸入磁道號使用冒泡法從小到大排序輸入當前磁道號2、數據結構及信號量定義的說明；本系統劃分為四個模塊：先來先服務算法模塊void fcfs(int array,int m)、最短尋道時間優先算法模塊void sstf(int array,int m)、掃描算法模塊void scan(int array,int m) 和循環掃描算法模塊：void cscan(int array,int m) 。1 先來先服務算法模塊：void fcfs(int array,int m)輸入磁道號，按先來先服務的策略輸出磁盤請求序列，求平均尋道長度，輸出移動平均磁道數。2 最

6、短尋道時間優先算法模塊：void sstf(int array,int m)將磁道號用冒泡法從小到大排序，輸出排好序的磁道序列，輸入當前磁道號，根據前磁道在已排的序列中的位置，選擇掃描的順序，求出平均尋道長度，輸出移動的平均磁道數。3 掃描算法模塊：void scan(int array,int m)將磁道號用冒泡法從小到大排序，輸出排好序的序列，輸入當前磁道號，選擇移動臂的移動方向，根據當前磁道在已排的序列中的位置，選擇掃描的順序，求出平均尋道長度，輸出移動的平均磁道數。4 循環掃描算法模塊：void cscan(int array,int m)將磁道號用冒泡法從小到大排序，輸出排好序的序列

7、，輸入當前磁道號，規定移動臂單向反復的從內向外移動，根據當前磁道在已排的序列中的位置，選擇掃描的順序，求出平均尋道長度，輸出移動的平均磁道數。3、實驗的步驟；輸入的磁道序列為：12 4 54 7 23 452 141 162 354 21 471 256 45 11 25 3 689 5 241 先來先服務算法當前磁道號：任意（這里取25）平均尋道長度：197.6322 最短尋道時間優先算法（1）當前磁道號大于磁道序列中的最大的磁道號時當前磁道號：890平均尋道長度:46.6482（2）當前磁道號小于磁道序列中的最小的磁道號時當前磁道號：1平均尋道長度：36.2105（3）當前磁道號大于磁道序

8、列中的最小的磁道號且小于最大磁道號時 當前磁道號：255平均尋道長度：49.47373 掃描算法（1）當前磁道號大于磁道序列中的最大的磁道號時當前磁道號：890平均尋道長度:46.6842（2）當前磁道號小于磁道序列中的最小的磁道號時當前磁道號：1平均尋道長度:36.2105（3）當前磁道號大于磁道序列中的最小的磁道號且小于最大磁道號（磁頭向外）時當前磁道號：255平均尋道長度:58.9474（4）當前磁道號大于磁道序列中的最小的磁道號且小于最大磁道號（磁頭向內）時當前磁道號：255平均尋道長度:49.36844 循環掃描算法（1）當前磁道號大于磁道序列中的最大的磁道號時當前磁道號：890平均

9、尋道長度:82.7895（2）當前磁道號小于磁道序列中的最小的磁道號時當前磁道號：1平均尋道長度:36.2105（3）當前磁道號大于磁道序列中的最小的磁道號且小于最大磁道號時當前磁道號：100平均尋道長度:67.31584、實驗源程序關鍵算法；1先來先服務算法模塊：void fcfs(int array,int m)主要代碼：for(i=0,j=1;jm;i+,j+) sum+=abs(arrayj-arrayi); ave=(float)(sum)/(float)(m);2 最短尋道時間優先算法模塊：void sstf(int array,int m)主要代碼：for(i=0;im;i+)

10、/*使用冒泡法按從小到大順序排列*/for(j=i+1;jarrayj) temp=arrayi; arrayi=arrayj; arrayj=temp; if(arraym-1=0;i-) coutarrayi=now) /*若當前磁道號小于請求序列中最小者，則直接由內向外依次給予各請求服務*/ while(l=0)&(rm) /*當前磁道在請求序列范圍內*/ if(now-arrayl)=(arrayr-now) /*選擇與當前磁道最近的請求給予服務*/ coutarrayl=0;j-) coutarrayj ; /*輸出向內掃描的序列*/ for(j=r;jm;j+) /*磁頭移動到最小

11、號，則改變方向向外掃描未掃描的磁道*/ coutarrayj ; /*輸出向外掃描的序列*/ sum=now-2*array0+arraym-1; else /*選擇移動臂方向向外，則先向外掃描*/ for(j=r;jm;j+) coutarrayj=0;j-) /*磁頭移動到最大號，則改變方向向內掃描未掃描的磁道*/ coutarrayj ; sum=-now-array0+2*arraym-1; ave=(float)(sum)/(float)(m);4 循環掃描算法模塊：void cscan(int array,int m)主要代碼：if(arraym-1=now) /*若當前磁道號大于

12、請求序列中最大者，則直接將移動臂移動到最小號磁道依次向外給予各請求服務 */ for(i=0;im;i+) coutarrayi=now) /*若當前磁道號小于請求序列中最小者，則直接由內向外依次給予各請求服務,此情況同最短尋道優先*/ for(i=0;im;i+) coutarrayi ; sum=arraym-1-now; for(j=0;jr;j+) /*當掃描完最大號磁道，磁頭直接移動到最小號磁道，再向外掃描未掃描的磁道*/ coutarrayj ; sum=2*arraym-1-now; ave=(float)(sum)/(float)(m);5、實驗運行圖；算法首頁1 先來先服務算

13、法2最短尋道時間優先算法（1）當前磁道號大于磁道序列中的最大的磁道號時（2）當前磁道號小于磁道序列中的最小的磁道號時（3）當前磁道號大于磁道序列中的最小的磁道號且小于最大磁道號時3 掃描算法（1）當前磁道號大于磁道序列中的最大的磁道號時（2）當前磁道號小于磁道序列中的最小的磁道號時（3）當前磁道號大于磁道序列中的最小的磁道號且小于最大磁道號（磁頭向外）時（4）當前磁道號大于磁道序列中的最小的磁道號且小于最大磁道號（磁頭向內）時4 循環掃描算法（1）當前磁道號大于磁道序列中的最大的磁道號時（2）當前磁道號小于磁道序列中的最小的磁道號時（3）當前磁道號大于磁道序列中的最小的磁道號且小于最大磁道號時

14、6、實驗結果分析；本系統具有很強的健壯性，當輸入錯誤數據類型時，系統提示用戶輸入的數據類型錯誤，讓用戶重新輸入，保證系統的穩定性，不會因為用戶的誤操作而致使系統癱瘓；雖然是在dos狀態下，但是本系統界面還是設計的比較漂亮的，具有比較好的交互性；對于軟件中的重用代碼，設計成一個函數，實現代碼重用。本系統是在dos狀態下進行編譯執行的，沒有圖形化界面，可以設計出一個圖形化界面，使用戶操作更加簡單，明了。用戶使用時請注意：1、進入系統，用戶根據提示依次輸入磁道號，要結束時輸入“0”，回車，輸入磁盤號結束；2、系統輸出你輸入的磁道序列，用戶核對輸入數據3、系統顯示系統算法菜單；4、用戶選擇相應算法，回

15、車；5、系統要求輸入當前磁道號，用戶輸入磁道號，回車；6、系統輸出磁頭的掃描序列和平均尋道長度；7、用戶繼續選擇系統菜單中的算法；8、當用戶選擇掃描算法時，需要輸入磁道的尋道方向（1表示掃描磁道號大的方向，0表示掃描磁道號小的方向）；六、 結論（應當準確、完整、明確精練；也可以在結論或討論中提出建議、設想、尚待解決問題等。）通過此次課程設計，我對操作系統的基礎知識了解得更透徹了，同時對磁盤調度的四種算法先來先服務算法（fcfs）、最短尋道時間優先算法（sstf）、掃描算法（scan）、循環掃描算法（cscan）有了更深刻的理解和掌握，使我能夠為磁盤調度選擇適當的算法，提高cpu工作效率。設計過

16、程中遇到的困難在小組成員之間進行討論，解決不了的問題，也在老師和同學的幫助下順利解決并通過了驗收，我深刻認識到算法的邏輯性對程序的重要影響，算法的準確度對程序運行結果的重要影響（例如，訪問同樣的磁道，在采用不同的算法，所用的平均尋道長度有明顯差別），這對我以后在操作系統的學習中有極大幫。七、 參考文獻計算機操作系統（第三版）湯小丹 梁紅兵 哲鳳平 湯子瀛 編著 西安電子科技大學出版社程序設計基礎（第二版） 吳文虎 編著 清華大學出版社數據結構c語言描述 耿國華 主編 高等教育出版社八、 指導教師評語 簽名： 年 月 日課程設計成績附：1、課程設計的填寫請按格式要求做；2、文字內容宋體、五號、1

17、.5倍行距；3、程序代碼字體times new roman，五號、1.5倍行距； 附表：源程序代碼#include#include#include#include#define maxsize 1000/*判斷輸入數據是否有效*/int decide(char str) /判斷輸入數據是否有效 int i=0;while(stri!=0) if(stri9)return 0;break;i+;return i;/*將字符串轉換成數字*/int trans(char str,int a) /將字符串轉換成數字int i;int sum=0;for(i=0;ia;i+)sum=sum+(int)(

18、stri-0)*pow(10,a-i-1);return sum;/*冒泡排序算法*/int *bubble(int cidao,int m) int i,j;int temp; for(i=0;im;i+) /使用冒泡法按從小到大順序排列 for(j=i+1;jcidaoj) temp=cidaoi; cidaoi=cidaoj; cidaoj=temp; cout排序后的磁盤序列為：; for( i=0;im;i+) /輸出排序結果 coutcidaoi ; coutendl; return cidao; /*先來先服務調度算法*/void fcfs(int cidao,int m) /磁

19、道號數組，個數為m int now;/當前磁道號 int sum=0; /總尋道長度 int j,i;int a;char str100; float ave; /平均尋道長度cout磁盤請求序列為：; for( i=0;im;i+) /按先來先服務的策略輸出磁盤請求序列 coutcidaoi ; coutendl; coutstr; /對輸入數據進行有效性判斷 a=decide(str); if(a=0) cout輸入數據的類型錯誤,請重新輸入！endl; goto b; else now=trans(str,a); /輸入當前磁道號 sum+=abs(cidao0-now);cout磁盤掃

20、描序列為：; for( i=0;im;i+) /輸出磁盤掃描序列 coutcidaoi ; for(i=0,j=1;jm;i+,j+) /求平均尋道長度 sum+=abs(cidaoj-cidaoi); ave=(float)(sum)/(float)(m); coutendl; cout平均尋道長度：aveendl;/*最短尋道時間優先調度算法*/void sstf(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); /調用冒泡排

21、序算法排序 coutstr; /對輸入數據進行有效性判斷 a=decide(str); if(a=0) cout輸入數據的類型錯誤,請重新輸入！endl; goto c; else now=trans(str,a); /輸入當前磁道號 if(cidaom-1=now) /若當前磁道號大于請求序列中最大者，則直接由外向內依次給予各請求服務 cout=0;i-) coutcidaoi=now) /若當前磁道號小于請求序列中最小者，則直接由內向外依次給予各請求服務 cout磁盤掃描序列為：; for(i=0;im;i+) coutcidaoicidao0&nowcidaom-1) /若當前磁道號大于

22、請求序列中最小者且小于最大者 cout磁盤掃描序列為：; while(cidaok=0)&(rm) /當前磁道在請求序列范圍內 if(now-cidaol)=(cidaor-now) /選擇與當前磁道最近的請求給予服務 coutcidaol ; sum+=now-cidaol; now=cidaol; l=l-1; else coutcidaor ; sum+=cidaor-now; now=cidaor; r=r+1; if(l=-1) /磁頭移動到序列的最小號，返回外側掃描仍未掃描的磁道 for(j=r;jm;j+) coutcidaoj=0;j-) coutcidaoj ; sum+=c

23、idaom-1-cidao0; ave=(float)(sum)/(float)(m); coutendl; cout平均尋道長度： aveendl;/*掃描調度算法*/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; cidao=bubble(cidao,m); /調用冒泡排序算法排序 coutstr; /對輸入數據進行有效性判斷 a=decide(str); if(a=0) cout輸入數據的類型錯誤,請重新

24、輸入！endl; goto d; else now=trans(str,a); /輸入當前磁道號 if(cidaom-1=now) /若當前磁道號大于請求序列中最大者，則直接由外向內依次給予各請求服務,此情況同最短尋道優先 cout=0;i-) coutcidaoi=now) /若當前磁道號小于請求序列中最小者，則直接由內向外依次給予各請求服務,此情況同最短尋道優先 cout磁盤掃描序列為：; for(i=0;im;i+) coutcidaoicidao0&nowcidaom-1) /若當前磁道號大于請求序列中最小者且小于最大者 while(cidaoknow) k+; l=k-1; r=k;

25、 coutd; if(d=0) /選擇移動臂方向向內，則先向內掃描 cout=0;j-) coutcidaoj ; /輸出向內掃描的序列 for(j=r;jm;j+) /磁頭移動到最小號，則改變方向向外掃描未掃描的磁道 coutcidaoj ; /輸出向外掃描的序列 sum=now-2*cidao0+cidaom-1; else /選擇移動臂方向向外，則先向外掃描 cout磁盤掃描序列為：; for(j=r;jm;j+) coutcidaoj=0;j-) /磁頭移動到最大號，則改變方向向內掃描未掃描的磁道 coutcidaoj ; sum=-now-cidao0+2*cidaom-1; ave

26、=(float)(sum)/(float)(m); coutendl; cout平均尋道長度： aveendl;/*循環掃描調度算法*/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); /調用冒泡排序算法排序 coutstr; /對輸入數據進行有效性判斷 a=decide(str); if(a=0) cout輸入數據的類型錯誤,請重新輸入！endl; goto e; else now=trans(str,a)

27、; /輸入當前磁道號 if(cidaom-1=now) /若當前磁道號大于請求序列中最大者，則直接將移動臂移動到最小號磁道依次向外給予各請求服務 cout磁盤掃描序列為：; for(i=0;im;i+) coutcidaoi=now) /若當前磁道號小于請求序列中最小者，則直接由內向外依次給予各請求服務,此情況同最短尋道優先 cout磁盤掃描序列為：; for(i=0;im;i+) coutcidaoicidao0&nowcidaom-1) /若當前磁道號大于請求序列中最小者且小于最大者 cout磁盤掃描序列為：; while(cidaoknow) /單向反復地從內向外掃描 k+; l=k-1; r=k; for(j=r;jm;j+) coutcidaoj ; /輸出從當前磁道向外掃描的序列 for(j=0;jr;j+) /當掃描完最大號磁道，磁頭直接移動到最小號磁道，再向外掃描未掃描的磁道 coutcidaoj ; sum=2*cidaom-1+cidaol-now-2*cidao0; ave=(float)(sum)/(float)(m); coutendl; cout平均尋道長度： aveendl;