磁盤調算法程序課程設計報告

1、成績 課程設計報告 題 目 磁盤調度算法程序設計 課 程 名 稱 操作系統(tǒng)課程設計 院 部 名 稱 信息技術學院 專 業(yè) 計算機科學與技術 班 級 M11計算機科學與技術 學 生 姓 名 學 號 課程設計地點 A205 課程設計學時 20 指 導 教 師 李 莉 金陵科技學院教務處制目錄一、課程設計的目的和要求21、目的22、要求2二、設計任務介紹及系統(tǒng)需求分析2.1 任務介紹22.2基本需求設計2三、概要設計33.1程序主要流程33.2 程序的函數(shù)調用關系5四、詳細設計54.1數(shù)據(jù)結構描述54.2各功能模塊（或主要過程）分析54.3各子程序流程分析74.3.1 FCFS( )74.3.2 S

2、STF()84.3.3 SCAN( )9五、調試與測試105.1 程序運行初始界面105.2 鍵盤輸入磁道105.3 隨機產(chǎn)生磁道105.4 先來先服務算法105.5 最短尋道時間優(yōu)先算法10 5.6 掃描算法125.6.1先向外掃描115.6.2先向里掃描115.7 退出程序11六、結論與體會12參考文獻12附件：源程序清單13 一、課程設計的目的和要求1.1目的磁盤是經(jīng)常使用的一種重要的外設，對磁盤數(shù)據(jù)的尋道時間的長短直接影響機器的整體運行速度，本設計要求用C語言（或高級語言）編寫程序模擬實現(xiàn)磁盤調度的常用算法。以加深對磁盤調度常用算法的理解和實現(xiàn)技巧。1.2 要求1）、設計一個函數(shù)完成先

3、來先服務的磁盤調度功能。2）、設計一個函數(shù)完成最短尋道時間優(yōu)先的磁盤調度功能。3）、設計一個函數(shù)完成電梯算法的磁盤調度功能。二、系統(tǒng)需求分析2.1 任務介紹1、可利用先來先服務算法（FCFS即first come first served）、最短尋道時間優(yōu)先算法（SSTF即shortest seek time first）、掃描算法（SCAN），來實現(xiàn)磁盤的訪問順序。2、根據(jù)磁盤調度算法的不同的特性做好軟件實現(xiàn)的需求分析。3、可根據(jù)問題的實際需要，可模擬數(shù)據(jù)在磁道的存放位置。4、當系統(tǒng)運行時，能直觀地、動態(tài)地反映當前磁盤狀態(tài)及不同算法的平均尋道時間。5、要求在系統(tǒng)安全狀態(tài)的前提下，用戶指定需要

4、訪問的磁道，軟件自動模擬在不同算法情況下，磁盤尋道順序和平均尋道時間。2.2基本需求設計 系統(tǒng)主界面可以靈活選擇某種算法，算法包括：先來先服務算法（FCFS）、最短尋道時間優(yōu)先算法（SSTF）、掃描算法（SCAN）。1、先來先服務算法（FCFS）這是一種比較簡單的磁盤調度算法。它根據(jù)進程請求訪問磁盤的先后次序進行調度。此算法的優(yōu)點是公平、簡單，且每個進程的請求都能依次得到處理，不會出現(xiàn)某一進程的請求長期得不到滿足的情況。此算法由于未對尋道進行優(yōu)化，在對磁盤的訪問請求比較多的情況下，此算法將降低設備服務的吞吐量，致使平均尋道時間可能較長，但各進程得到服務的響應時間的變化幅度較小。2、最短尋道時間

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

6、道需要訪問才將磁臂換向，自外向里移動。這時，同樣也是每次選擇這樣的進程來調度，即其要訪問的磁道，在當前磁道之內，從而避免了饑餓現(xiàn)象的出現(xiàn)。由于這種算法中磁頭移動的規(guī)律頗似電梯的運行，故又稱為電梯調度算法。此算法基本上克服了最短尋道時間優(yōu)先算法的服務集中于中間磁道和響應時間變化比較大的缺點，而具有最短尋道時間優(yōu)先算法的優(yōu)點即吞吐量較大，平均響應時間較小，但由于是擺動式的掃描方法，兩側磁道被訪問的頻率仍低于中間磁道。三、概要設計3.1程序主要流程下圖3-1為磁盤調度算法總流程圖，程序運行開始，進入選擇界面，輸入磁道數(shù)，然后依次調用decide()函數(shù)和trans()函數(shù)，再進入主循環(huán)界面，選擇調度

7、算法，直到選擇4，程序執(zhí)行完畢退出。開始進入選擇界面，手動輸入還是系統(tǒng)自動生成磁道序列調用decide（）函數(shù)調用trans（）函數(shù)進入while(1)主循環(huán)輸入14中的一數(shù)值，選擇相應操作是輸入是否為4？否判斷鍵值，選擇相應的調度算法，完成相應的功能結束圖3-13.2程序函數(shù)調用關系下圖為磁盤調度算法的函數(shù)之間的調用關系，主函數(shù)調用子函數(shù)，子函數(shù)也可以調用子函數(shù)，進行進程的初始化，排序等等。函數(shù)調用關系圖，如圖3-2：main()decide()SCAN()trans()SSTF()FCFS()Sort()圖3-2四、詳細設計4.1數(shù)據(jù)結構描述 本系統(tǒng)劃分為三個模塊：先來先服務算法模塊voi

8、d FCFS(int cidao,int m)、最短尋道時間優(yōu)先算法模塊void SSTF(int cidao,int m)、掃描算法模塊void SCAN(int cidao,int m) 。1. 先來先服務算法模塊：void FCFS(int cidao,int m)輸入磁道號，按先來先服務的策略輸出磁盤請求序列，求平均尋道長度，輸出移動平均磁道數(shù)。這是一種簡單的磁盤調度算法。它根據(jù)進程請求訪問磁盤的先后次序進行調度。此算法的優(yōu)點是公平、簡單，且每個進程的請求都能依次得到處理，不會出現(xiàn)某一進程的請求長期得不到滿足的情況。但此算法由于未對尋道進行優(yōu)化，致使平均尋道時間可能較長。2 .最短尋道

9、時間優(yōu)先算法模塊：void SSTF(int cidao,int m)將磁道號用冒泡法從小到大排序，輸出排好序的磁道序列，輸入當前磁道號，根據(jù)前磁道在已排的序列中的位置，選擇掃描的順序，求出平均尋道長度，輸出移動的平均磁道數(shù)。該算法選擇這樣的進程，其要求訪問的磁道與當前磁頭所在的磁道距離最近，以使每次的尋道時間最短，但這種調度算法卻不能保證平均尋道時間最短。3 .掃描算法模塊：void SCAN(int cidao,int m)將磁道號用冒泡法從小到大排序，輸出排好序的序列，輸入當前磁道號，選擇移動臂的移動方向，根據(jù)當前磁道在已排的序列中的位置，選擇掃描的順序，求出平均尋道長度，輸出移動的平均

10、磁道數(shù)。SCAN算法不僅考慮到欲訪問的磁道與當前磁道的距離，更優(yōu)先考慮的是磁頭的當前移動方向。例如，當磁頭正在自里向外移動時，SCAN算法所選擇的下一個訪問對象應是其欲訪問的磁道既在當前磁道之外，又是距離最近的。這樣自里向外地訪問，直到再無更外的磁道需要訪問才將磁臂換向，自外向里移動。這時，同樣也是每次選擇這樣的進程來調度，即其要訪問的磁道，在當前磁道之內，從而避免了饑餓現(xiàn)象的出現(xiàn)。由于這種算法中磁頭移動的規(guī)律頗似電梯的運行，故又稱為電梯調度算法。4.2各模塊函數(shù)功能分析由于一開始我們要對鍵盤輸入的磁道數(shù)和要使用的算法進行一次有效性的判斷，我使用了int decide(char str)，如果

11、輸入的信息不是09之間的數(shù)都將被判定為不合法，合法后才能進行下一步。判斷完合法性后，要將我們輸入的字符轉化為數(shù)字，這里我用了int trans(char str,int a)。當然系統(tǒng)自動生成的就不要使用以上兩個函數(shù)了。一切都準備好后，開始選擇要調用哪個算法了，先來先服務調度算法我使用了void FCFS(int cidao,int m)，這個算法主要完成按原來鍵盤輸入的次序或系統(tǒng)自動生成的次序來尋到，然后輸出總的尋道長度和平均尋道長度。以下兩個算法都要用到排序算法，這里我使用了冒泡排序法int *sort(int cidao,int m)，將磁道數(shù)按從小到大的序列排好。最短尋道時間優(yōu)先調度算

12、法我使用了void SSTF(int cidao,int m)，在排好序列磁道中選擇離當前磁道最近的磁道開始尋道，然和再和相鄰的兩個磁道進行比較，看離哪個更近；如果當前磁道是最大值或是最小值，直接按倒敘或是正序尋道，最后輸出總的尋道長度和平均尋道長度。掃描調度算法我使用了void SCAN(int cidao,int m)，在排好序的磁道序列中根據(jù)當前磁道數(shù)，選擇是向外尋道還是向內尋道，如果當前磁道數(shù)是最大值或是最小值，直接向內或向外尋道，最后也要輸出總的尋道長度和平均尋道長度。4.3各子函數(shù)流程分析4.3.1 FCFS()下圖4-1為FCFS函數(shù)的流程圖：開始輸入磁道號或系統(tǒng)隨機生成按原順序

13、將磁道序列輸出求總的尋道長度sum+=abs(cidao0-now)求平均尋道長度ave=sum/m結束圖4-14.3.2 SSTF()下圖4-1為FCFS函數(shù)的流程圖：開始輸入磁道號或系統(tǒng)隨機生成調用sort（）否minnow=now是是按排好的順序直接輸出磁道序列按排好的順序倒序輸出磁道序列按離當前磁道now最短的順序輸出磁道序列求總的尋道長度和平均尋道長度結束圖4-24.3.3 SCAN()下圖4-1為FCFS函數(shù)的流程圖：開始輸入磁道號或系統(tǒng)隨機生成調用sort（）否minnowmax否now=min是是選擇先向外還是向內掃描，再一次輸出磁道序列直接向內掃描，從大到小輸出磁道序列直接向

14、外掃描，按從小到大輸出磁道序列求總的尋道長度和平均尋道長度結束圖4-3 五、調試過程5.1 運行程序初始界面運行程序，顯示初始界面如圖5-1所示，選擇產(chǎn)生磁道的方式。圖5-15.2 隨機產(chǎn)生磁道輸入1可隨機產(chǎn)生磁道數(shù)，如圖5-2所示。圖5-25.3鍵盤輸入磁道輸入2進行鍵盤輸入，并附帶錯誤提醒功能，如圖5-3所示。圖5-35.4先來先服務算法輸入1，選擇先來先服務算法，如圖5-4所示。圖5-45.5最短尋道時間優(yōu)先算法輸入2，選擇最短尋道時間優(yōu)先算法，如圖5-5所示。圖5-55.6掃描算法5.6.1先向外掃描：輸入3后，選擇掃描算法，再輸入1選擇先向外掃描，如圖5-6所示。圖5-65.6.2先

15、向里掃描：輸入3后，選擇掃描算法，再輸入0選擇先向里掃描，如圖5-7所示。圖5-75.7退出程序輸入4退出，如圖5-8所示。圖5-8六、結論與體會這次操作系統(tǒng)的課程設計，從理論到實踐，我學到很多很多的的東西，不僅可以鞏固了以前所學過的知識，而且學到了很多在書本上所沒有學到過的知識。通過這次課程設計使我懂得了理論與實際相結合是很重要的，只有理論知識是遠遠不夠的，只有把所學的理論知識與實踐相結合起來，從理論中得出結論，才能真正為社會服務，從而提高自己的實際動手能力和獨立思考的能力。本次實驗首先要了解磁盤調度的工作原理及四種調度方法的工作原理。在課程設計前的準備工作時，先把這部分工作做完了。在設計總

16、的程序框架的時候，要注意各功能模塊的位置，盡量做到簡潔、有序；各功能模塊與主程序要正確銜接。在設計的過程中遇到許多問題，我設計的是四種調度算法中的后兩種。例如：在最初程序設計時主要有兩種構思：1）選用數(shù)據(jù)結構是鏈表的。2）選用數(shù)組。我最初嘗試了用鏈表，覺得方便易懂，但是在循環(huán)掃描處出現(xiàn)了些問題，后來又轉變了設計思路，選用了數(shù)組，直接進行排序，然后再聯(lián)系到各功能模塊。至此，計算機操作系統(tǒng)課程設計算法已經(jīng)完成。但由于這次設計的時間比較倉促，其中不免會有些紕漏，在設計的過程中我也發(fā)現(xiàn)了自己的不足之處，對以前所學過的知識理解得不夠深刻，掌握得不夠牢固，自身知識的很多漏洞，看到了自己的實踐經(jīng)驗還是比較缺

17、乏，理論聯(lián)系實際的能力還急需提高。比如說編語言掌握得不好，應用程序編寫不太會通過這次課程設計之后，一定把以前所學過的知識重新溫故。在此，也感謝在課程設計過程中幫我解惑的老師和同學。七、參考文獻1湯小丹、湯子贏等.計算機操作系統(tǒng).西安：西安電子科技大學出版社，2007.2張麗芬. 操作系統(tǒng)實驗教程M.北京：清華大學出版社，2006.附件：源程序清單磁盤調度算法源程序清單#include#include#include#include#include #define maxsize 100/*判斷輸入數(shù)據(jù)是否有效*/int decide(char str) /判斷輸入數(shù)據(jù)是否有效int i=0;w

18、hile(stri!=0)if(stri9)return 0;break;i+;return i;/*將字符串轉換成數(shù)字*/int trans(char str,int a) /將字符串轉換成數(shù)字int i;int sum=0;for(i=0;ia;i+)sum=sum+(int)(stri-0)*pow(10,a-i-1);return sum;/*冒泡排序算法*/int *sort(int cidao,int m) int i,j;int temp;for(i=0;im;i+) /使用冒泡法按從小到大順序排列for(j=i+1;jcidaoj) temp=cidaoi;cidaoi=cid

19、aoj;cidaoj=temp;return cidao; /*先來先服務調度算法*/void FCFS(int cidao,int m) /磁道號數(shù)組，個數(shù)為mint now=20;/當前磁道號int sum=0; /總尋道長度int j,i;float ave; /平均尋道長度cout磁盤請求序列為：;for( i=0;im;i+) /按先來先服務的策略輸出磁盤請求序列coutcidaoi ;coutendl;sum+=abs(cidao0-now);cout磁盤掃描序列為：;for( i=0;im;i+) /輸出磁盤掃描序列coutcidaoi ;for(i=0,j=1;jm;i+,j+

20、) /求平均尋道長度sum+=abs(cidaoj-cidaoi);ave=(float)(sum)/(float)(m);coutendl;cout總的尋道長度：sumendl;cout平均尋道長度：aveendl;/*最短尋道時間優(yōu)先調度算法*/void SSTF(int cidao,int m)int k=1;int now=20;int l,r;int i,j,sum=0;float ave;cidao=sort(cidao,m); /調用冒泡排序算法排序if(cidaom-1=now) /若當前磁道號大于請求序列中最大者，則直接由外向內依次給予各請求服務cout=0;i-)coutc

21、idaoi=now) /若當前磁道號小于請求序列中最小者，則直接由內向外依次給予各請求服務cout磁盤掃描序列為：;for(i=0;im;i+)coutcidaoicidao0&nowcidaom-1) /若當前磁道號大于請求序列中最小者且小于最大者cout磁盤掃描序列為：;while(cidaok=0)&(rm) /當前磁道在請求序列范圍內if(now-cidaol)=(cidaor-now) /選擇與當前磁道最近的請求給予服務coutcidaol ;sum+=now-cidaol;now=cidaol;l=l-1;elsecoutcidaor ;sum+=cidaor-now;now=ci

22、daor;r=r+1;if(l=-1) /磁頭移動到序列的最小號，返回外側掃描仍未掃描的磁道for(j=r;jm;j+)coutcidaoj=0;j-)coutcidaoj ;sum+=cidaom-1-cidao0;ave=(float)(sum)/(float)(m);coutendl;cout總的尋道長度： sumendl;cout平均尋道長度： aveendl;/*掃描調度算法*/void SCAN(int cidao,int m) /先要給出當前磁道號和移動臂的移動方向int k=1;int now=20;int l,r,d;int i,j,sum=0;float ave;cidao

23、=sort(cidao,m); /調用冒泡排序算法排序if(cidaom-1=now) /若當前磁道號大于請求序列中最大者，則直接由外向內依次給予各請求服務,此情況同最短尋道優(yōu)先 cout=0;i-)coutcidaoi=now) /若當前磁道號小于請求序列中最小者，則直接由內向外依次給予各請求服務,此情況同最短尋道優(yōu)先 cout磁盤掃描序列為：; for(i=0;im;i+)coutcidaoicidao0&nowcidaom-1) /若當前磁道號大于請求序列中最小者且小于最大者while(cidaoknow)k+;l=k-1;r=k;coutd;if(d=0) /選擇移動臂方向向內，則先向

24、內掃描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=(float)(sum)/(float)(m);coutendl;cout總的尋道長度： sumendl;cout平均尋道長度： aveendl;/*主函數(shù)*/void main()int a,b;int c; /菜單項int cidaomaxsize;int i=0,count;char str100;cout * * 歡迎