磁盤調度算法的實現(xiàn)與分析

1、計算機操作系統(tǒng)課程設計設計說明書（題目）磁盤調度算法的實現(xiàn)與分析起止日期： 2013 年12月25日至 2013年12 月 31日學 生班學成 指導教師（簽字）計算機與通信學院2013年12月31日 TOC o 1-5 h z HYPERLINK l bookmark7 o Current Document 1課程設計簡介31.1課程設計的目的31.2課程設計內容3 HYPERLINK l bookmark14 o Current Document 2數據結構的設計4 HYPERLINK l bookmark17 o Current Document 2.1變量和數組的定義4 HYPERLIN

2、K l bookmark20 o Current Document 2.2函數的定義4 HYPERLINK l bookmark23 o Current Document 3功能模塊（或算法）描述4 HYPERLINK l bookmark26 o Current Document 3.1模塊劃分43.2模塊調用關系圖8錯誤！未定義書簽。124程序運行結果5心得體會. HYPERLINK l bookmark43 o Current Document 參考文獻13 HYPERLINK l bookmark52 o Current Document 附源代碼131課程設計簡介1.1課程設計的目的

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

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

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

6、側磁道被訪問 的頻率仍低于中間磁道。4、循環(huán)掃描算法(CSCAN)循環(huán)掃描算法是對掃描算法的改進。如果對磁道的訪問請求是均勻分布的， 當磁頭到達磁盤的一端，并反向運動時落在磁頭之后的訪問請求相對較少。這是 由于這些磁道剛被處理，而磁盤另一端的請求密度相當高，且這些訪問請求等待 的時間較長，為了解決這種情況，循環(huán)掃描算法規(guī)定磁頭單向移動。例如，只自 里向外移動，當磁頭移到最外的被訪問磁道時，磁頭立即返回到最里的欲訪磁道， 即將最小磁道號緊接著最大磁道號構成循環(huán)，進行掃描。2數據結構的設計2.1變量和數組的定義intTrackN;用來存放隨機生成的磁道請求序列int Sum=0;用來存放移動的總磁

7、道數float AverTime=0.0;用來存放平均尋道數2.2函數的定義void Sort(int Track,int Num):冒泡法從小到大排序void Output(int Track,int Num):用于將隨機生成的磁道請求序列和當 前磁道數輸出void FCFS(int Track,int Num):先來先服務算法模塊void SSTF(int Track,int Num):最短尋道時間優(yōu)先算法模塊void SCAN(int Track,int Num)掃描算法模塊void C_SCAN(int Track,int Num):循環(huán)掃描算法模塊3功能模塊(或算法)描述3.1模塊劃

8、分本系統(tǒng)劃分為四個模塊：先來先服務算法模塊void FCFS(int Track口，int Num)、最短尋道時間優(yōu)先算法模塊void SSTF(int Track,int Num)、掃描算 法模塊 void SCAN(int Track,int Num)和循環(huán)掃描算法模塊：void C_SCAN (int Track,int Num)1先來先服務算法模塊：void FCFS(int array,int m)輸入磁道號，按先來先服務的策略輸出磁盤請求序列，求平均尋道長度，輸 出移動平均磁道數。主要代碼：for(i=0;iN;i+)(if(NumTracki)temp二Tracki-Num;el

9、se temp二Num-Tracki;Num二Tracki;Sum+=temp;AverTime=(float)Sum/N;2最短尋道時間優(yōu)先算法模塊：void SSTF(int Track,int Num)首先將隨機生成的磁盤請求序列與當前所在的磁道號進行比較，將所得之差 用數組Ttrack保存起來。然后在求出Ttrack數組中最小的數即為第一個訪問的 磁道。再將訪問過的磁道置-1。再次循環(huán)，求出平均尋道長度，輸出移動的平均 磁道數。主要代碼：for(j=0;jN;j+)for(i=0;iN;i+)(if(Ttracki=-1)continue;else(if(NumTracki)Ttrac

10、ki=Tracki-Num;else Ttracki=Num-Tracki;min=200;minj=0;for(i=0;iN;i+)(if(Ttracki=-1) continue;else(if(Ttrackimin)(min二Ttracki;minj=i;Num二Trackminj;DiskDcount+=Num;Sum=Sum+Ttrackminj;Ttrackminj=-1;AverTime=(float)Sum/N;3 掃描算法模塊：void SCAN(int Track,int Num)將磁道號用冒泡法將隨機生成的磁道請求序列從小到大排序，隨機生成的當 前磁道號，選擇移動臂的移動

11、方向，根據當前磁道在已排的序列中的位置，選擇 掃描的順序，求出平均尋道長度，輸出移動的平均磁道數。主要代碼：Output(Track,Num);for(i=0;iN;i+)tempi=Tracki;Sort(temp,N);/將訪問序列從小到大排序while(tempk=0;j-)(printf( %d ，tempj);for(j=r;jN;j+)(printf( %d ，tempj);Sum二Num-2*temp0+tempN-1;else(printf(磁道訪問的序列為：)；for(j=r;j=0;j-)(printf( %d ，tempj);Sum二Num-temp0+2*tempN-1

12、;AverTime=(float)Sum/N;4 循環(huán)掃描算法模塊：void C_SCAN(int Track口，int Num)將磁道號用冒泡法從小到大排序，輸出排好序的序列，隨機生成的當前磁道 號，規(guī)定移動臂單向反復的從內向外移動，根據當前磁道在已排的序列中的位置， 選擇掃描的順序，求出平均尋道長度，輸出移動的平均磁道數。主要代碼：Output(Track,Num);for(i=0;iN;i+)tempi=Tracki;Sort(temp,N);printf(磁道訪問的序列為：)；while(tempkNum)k+;l=k-1;r=k;for(j=r;jN;j+)(printf( %d ，

13、tempj);for(j=0;jr;j+)printf( %d ，tempj);Sum=2*tempN-1+templ-Num-2*temp0;AverTime=(float)(Sum)/(float)(N);3.2模塊調用關系圖4程序運行結果磁盤調度模擬系統(tǒng)主界面: I：膜作紊統(tǒng)新建文件表Dehug 5.exeX XX XXJJOXJOXXS 京i周，度 畀 j|tJOXJOXXJXXXXXJXXJJOXJOXXJXXJXJXJOXJOXXJXXXJOXJOXXJXXJJOXJOXXJXXJXJXJOXJOXXJXXX請選擇要使用的算法HJC JC HJC JCX JC XXxxxxxXXJ

14、CXXHJC JC HJC JCX JC XX來短描環(huán)用出碧麟蔑驀瀝 鼻法“SN 調匿算法 算法,進行比較XXJXXJJJXJJXXKJXJJXXJXXXXXJXXJJOXJOXXJXXJXJXJOXJOXXJXXXJOXJOXXJXXJJOXJOXXJXXJXJXJOXJOXXJXXXR青選擇算法:選擇第一種算法：先來先服務調度算法 I：涯作系統(tǒng)新建文件夾Deb ugA5.exe請選擇算法：1XKJXJJXXJXXX XXX KN XXX服-務-調音畀；：J XKJXXJXXXJJXJJXXJXXJXJXJJX6 和符： 列號列為 序道道備長 爭 求前道均平46 回NX XXKJXJJ X

15、XXX2 jj j 周，營畀女XXJXXJXJXJJXXXXXJCXXJCXXJCXj 青 j.近 1 莘要,使用的 丟XXX XXX XX XXXJXXXJOXJO蟲 CF算 Is 法調N 算先CA法進 調間法匿法 務時算調算 H 先尋殍五 來：； 先最蓿爨右借可用出-種Afe C匕 s t C-T- 交XXJXJXJOXXX JOCHJC XX JCXXX JOXXJXJXJOXXJXXJXJXJJJXXXJOXJOXJCXXXKJXJJXXJX請選擇算法:選擇第二種算法：最短尋道時間優(yōu)先調度算法請選擇算法：2XX XX XXX XXX XXX XX XXX XXX鈕尋道時間優(yōu)調庶算建 X

16、XX)CX)CXX)CXX)CXX)CX)CXX)C24 5328 639 8826 90 0 2 2 1 182 3 06 0 105 -1 6 2 織務： 列號列為 房道 道留長爭 求前道均平XXXXXJCXJCXXJCXXfl曲調恒7具_；去XXXXJCXXJCXXXHJCJCHJCJCXJCJCXJCJCJCJCHJCJCHJCJCXJCJCXJCHJCJCHJCJCXJCJCXJCHJCJCHJCJCXJCJCXJCJCJCJCHJCJCHJCJCXJCJCXJCHJCJCHJCJC X XX XXJJJXJJXXj青 j 先才羊要使 用的 畀KJXJJXXJXXXKXXKXNNXX

17、NHJC JC HJCHJC JC HJCXXJXXJJOXJ*n來短描環(huán)用出先尋客五B& 調虞算法 算法,進行比較XXJXXJJOXJOXXJXXJXJXJOXJOXXJXXXJOXJOXXJXXJJOXJOXXJXXJXJXJOXJOXXJXXX請選擇算法:選擇第三種算法：掃描調度算法 I：慢作紊統(tǒng)新建文件夾Deb ug45.exe請選擇算法：3JXJXJOXJOXXJXXXJOXJOXXJXXJJO X 才m 寸苗 i 周.庶畀汁 JXJOXXJXXXJOXJOXXJXXJXJXJOXXJXX.:!方,47 和蓋為. 列身列為 房道臂-05 道胃的長 磁*回道訪尋 求鼎道均 也普恩平6

18、0.1 2. 口78120 46 893834 178表示比當前磁道號大的方向138 120 92 89 62 525292 138,。表示比當前磁道小的方向46 38 34NtOCXtOCXNNXNNK2甜i周，帝女XNNXXNtOCXtOCJCHJCJCHJCJCXJCJCXJCHJCJCHJCJCXJCJCXJCJCJCJCHJCJCHJCJCXJCJCXJCHJCJCHJCJCXJCJCXJCHJCJCHJCJCMJCJCXJCJCJCJCHJCJCHJC NX XXX XXKJXJJ X青 j 先 j羊要,使用的 女XKJXXJXXJXJJXXJXXXJOXJC HJC JC H J

19、XXJXXXJO成 CF算AN較 c行 算先CA法進 ts算， 調間法r法 務時算調算 服道驀種 先尋客五 來短描環(huán)用出 r 、 f f f 、 1 2 3 4 5 6XXJXXJXJKX xtocHJC JC HJCXXJXXJXJJCHJCJCHJCJCXJCJCXJCHJCJCHJCJCXJCJCXJCJCJCJCHJCJCHJCJCXJCJCXJCHJCJCHJCJCXJCJCXJCHJCJCHJCJCMJCJCXJCJCJCJCHJCJCHJC請選擇算法:XXNNXNNXXNXXXNNXNNXXNXXNXNXNX者一為： 列口葛列為 序道臂道雷的長 磁*回道訪尋 求辱道均 喜寰平:6

20、2 ：150方向蟲CF算AN較 Is海比 法調Nc行 算先CA法進XJXXJXJXJOXXJXXJWJXXXJXJXJOXJXXJXJXJOXJOXX請選擇算法:選擇第四種算法：循環(huán)掃描調度算法 I：倨作奈統(tǒng)新建文件夾LDeBug45. exe1請選擇算法：4JXJXJOXJOXXJXXXJOXJOXXJ法CF算F度法調算先CA法進算， 調間法M-法 務時算調算 服道驀種 先尋殍五 來短描環(huán)用出 nAN較CLs LuDC亍N m麟 X JC H X JC H JCHJC JC HJCKX xtocXXXXXJCXJCXJJXXJXXJXJJXXJXXXJOXJOXJXXJXXXJOXJOXXJ

21、XXJJOXJOXXJXXJXJXJOXJOXXJXXXJOXJOXXJXXJWJXJOXXJXXJXJ請選擇算法:四種算法比較: I：慢作奈統(tǒng)新建文件表DebugVl5.exe 回XXXXXXX XXX服-務-j周唐7 畀注 JCKXJJJXJJXXJXXJXJXJJXXJXXJ2 2 0 6 0 6 45 - 1 7 - _b 的藤 列號列為 序道 道蓄長 求前道均 也一平JXXJXXXJJX KJXXJXXJXJX X主 R 尋_ j 首 日寸間憂 7 i 周 遺身_ 女 KJXXJXXJXJXJJXXJXXJX9 8826 940 0 2 2 1 182 3 0 6 0 105 - 1

22、 6 的先 列號列為 序道 道蓄長 求前道均 也一平8 64124 53263JCXXJCXXXJOCXJOCXXJCXXJCXJCXJOCXXJCXX X 才m 寸苗 i周.度算 甘生 XJJOXJOXXJXXJXJXJOXXJXXJXXXJOXJEI利蓊為. 列口扈列為 房道臂道胃的長 磁*回道訪尋 求景道均 也胃是平:62 ：150 方向1 :178 47.20120 46 89 38 34 178表示比當前磁道號大的方向138 120 92 89 62 5252 92 138，。表示比當前磁道小的方向46 38 34JXXJXXXJOXJOXXJXXJXJXJO X1盾壬不 Im 才苗

23、調.育畀；女箸 XJJOXJO 箸 XX 箸 XJXJXJO 箸 XX XXXXXXK0 42 3182 7 06 0 165 -1 7 列號列為 序道道蓄長 求前道均 也一平46382 09 2125 25心得體會本系統(tǒng)軟件中的重用代碼，設計成一個函數，實現(xiàn)了代碼重用。本系統(tǒng)是在 dos狀態(tài)下進行編譯執(zhí)行的，沒有圖形化界面。通過此次課程設計，我對操作系統(tǒng)的基礎知識了解得更透徹了，同時對磁盤 調度的四種算法一一先來先服務算法（FCFS）、最短尋道時間優(yōu)先算法（SSTF）、 掃描算法（SCAN）、循環(huán)掃描算法（CSCAN）有了更深刻的理解和掌握，使我能夠 為磁盤調度選擇適當的算法，提高CPU工作

24、效率。設計過程中遇到的困難在老師 和同學的幫助下順利解決并通過了驗收，我深刻認識到算法的邏輯性對程序的重 要影響，算法的準確度對程序運行結果的重要影響，這對我以后在操作系統(tǒng)的學 習中有極大幫助。參考文獻嚴蔚敏，吳偉民，數據結構(C語言版)，北京，清華大學出版社楊樹林，胡潔萍，C#程序設計與案例教程，北京，清華大學出版社譚浩強，C+程序設計，清華大學出版社，2004謝青松.操作系統(tǒng)原理.人民郵電出版社.2004袁寶華.操作系統(tǒng)實驗教程.北京交通大學出版社羅宇，鄒鵬，鄧勝蘭.操作系統(tǒng)】M.北京：電子工業(yè)高等教育出版社，2012附源代碼#include stdio.h#include time.h#

25、include stdlib.h#define N 10void Sort(int Array,int n)冒泡排序算法,從小到大排序int i,j,temp;for(i=1;in;i+)for(j=0;jArrayj+1)temp=Arrayj;Arrayj=Arrayj+1;Arrayj+1=temp;void Output(int Track,int Num)int i;printf(請求的磁道序列為：);for(i=0;iN;i+)printf( %d ”,Tracki); printf(n);printf（當前所在磁道號是:dn”,Num）;/* 先來先服務調度算法 */ void

26、FCFS(int Track,int Num) int i,temp;int Sum=0;來先服務調度算法float AverTime=0.0;printf(* 先“ 3 tl*nn);Output(Track,Num);for(i=0;iN;i+)if(NumTracki)temp=Tracki-Num;else temp=Num-Tracki;Num=Tracki;Sum+=temp;AverTime=(float)Sum/N;printf(-磁道訪問的序列為：)；for(i=0;iN;i+)printf( %d ”,Tracki);printf(n 平均尋道長度為：%.2fnn,Aver

27、Time);/* 最短尋道時間優(yōu)先調度算法 */ void SSTF(int Track,int Num) int i,j,TtrackN,DiskN;int min,minj,Dcount=0;int Sum=0;float AverTime=0.0;printf(*最短尋道時間優(yōu)先調度算法“ 3 tl*nn);Output(Track,Num);for(i=0;iN;i+)Ttracki=0;for(j=0;jN;j+)for(i=0;iN;i+)if(Ttracki=-1)continue;elseif(NumTracki)Ttracki=Tracki-Num;else Ttracki=

28、Num-Tracki;min=200;minj=0;for(i=0;iN;i+)if(Ttracki=-1) continue;elseif(Ttrackimin) min=Ttracki; minj=i;Num=Trackminj;DiskDcount+=Num;Sum=Sum+Ttrackminj;Ttrackminj=-1;AverTime=(float)Sum/N;printf(-磁道訪問的序列為：)；for(i=0;iN;i+)printf( %d ,Diski);printf(n 平均尋道長度為：%.2fnn,AverTime); /* 掃描調度算法 */ void SCAN(in

29、t Track,int Num) int i,j,k=0,r=0,l=0,choose;int tempN;int Sum=0;度算法float AverTime=0.0;printf(* 掃 描“ 3 tl*nn);Output(Track,Num);for(i=0;iN;i+)tempi=Tracki;Sort(temp,N); /將訪問序列從小到大排序 while(tempk=0;j-)printf( %d ,tempj);for(j=r;jN;j+)printf( %d ,tempj);Sum=Num-2*temp0+tempN-1;elseprintf(-磁道訪問的序列為：);for

30、(j=r;j=0;j-)printf( %d ,tempj);Sum=Num-temp0+2*tempN-1;AverTime=(float)Sum/N;printf(n 平均尋道長度為：%.2fnn,AverTime);/* 循環(huán)掃描調度算法 */ void C_SCAN(int Track,int Num) int i,j,k=0,r=0,l=0;int tempN;int Sum=0;掃描調度算法float AverTime=0.0;printf(* 循 環(huán)“ 3 tl*nn);Output(Track,Num);for(i=0;iN;i+)tempi=Tracki;Sort(temp,N);printf(-磁道訪問的序列為：);while(tempkNum)(k+;l=k-1;r=k;for(j=r;jN;j+)printf( %d ,tem