磁盤調(diào)算法程序課程設(shè)計報告

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

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

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

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

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

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

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

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

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

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

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

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

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

14、外掃描，按從小到大輸出磁道序列求總的尋道長度和平均尋道長度結(jié)束圖4-3 五、調(diào)試過程5.1 運(yùn)行程序初始界面運(yùn)行程序，顯示初始界面如圖5-1所示，選擇產(chǎn)生磁道的方式。圖5-15.2 隨機(jī)產(chǎn)生磁道輸入1可隨機(jī)產(chǎn)生磁道數(shù)，如圖5-2所示。圖5-25.3鍵盤輸入磁道輸入2進(jìn)行鍵盤輸入，并附帶錯誤提醒功能，如圖5-3所示。圖5-35.4先來先服務(wù)算法輸入1，選擇先來先服務(wù)算法，如圖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六、結(jié)論與體會這次操作系統(tǒng)的課程設(shè)計，從理論到實踐，我學(xué)到很多很多的的東西，不僅可以鞏固了以前所學(xué)過的知識，而且學(xué)到了很多在書本上所沒有學(xué)到過的知識。通過這次課程設(shè)計使我懂得了理論與實際相結(jié)合是很重要的，只有理論知識是遠(yuǎn)遠(yuǎn)不夠的，只有把所學(xué)的理論知識與實踐相結(jié)合起來，從理論中得出結(jié)論，才能真正為社會服務(wù)，從而提高自己的實際動手能力和獨立思考的能力。本次實驗首先要了解磁盤調(diào)度的工作原理及四種調(diào)度方法的工作原理。在課程設(shè)計前的準(zhǔn)備工作時，先把這部分工作做完了。在設(shè)計總

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

17、乏，理論聯(lián)系實際的能力還急需提高。比如說編語言掌握得不好，應(yīng)用程序編寫不太會通過這次課程設(shè)計之后，一定把以前所學(xué)過的知識重新溫故。在此，也感謝在課程設(shè)計過程中幫我解惑的老師和同學(xué)。七、參考文獻(xiàn)1湯小丹、湯子贏等.計算機(jī)操作系統(tǒng).西安：西安電子科技大學(xué)出版社，2007.2張麗芬. 操作系統(tǒng)實驗教程M.北京：清華大學(xué)出版社，2006.附件：源程序清單磁盤調(diào)度算法源程序清單#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;/*將字符串轉(zhuǎn)換成數(shù)字*/int trans(char str,int a) /將字符串轉(zhuǎn)換成數(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; /*先來先服務(wù)調(diào)度算法*/void FCFS(int cidao,int m) /磁道號數(shù)組，個數(shù)為mint now=20;/當(dāng)前磁道號int sum=0; /總尋道長度int j,i;float ave; /平均尋道長度cout磁盤請求序列為：;for( i=0;im;i+) /按先來先服務(wù)的策略輸出磁盤請求序列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)先調(diào)度算法*/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); /調(diào)用冒泡排序算法排序if(cidaom-1=now) /若當(dāng)前磁道號大于請求序列中最大者，則直接由外向內(nèi)依次給予各請求服務(wù)cout=0;i-)coutc

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

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

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

24、內(nèi)掃描cout=0;j-)coutcidaoj ; /輸出向內(nèi)掃描的序列for(j=r;jm;j+) /磁頭移動到最小號，則改變方向向外掃描未掃描的磁道coutcidaoj ; /輸出向外掃描的序列sum=now-2*cidao0+cidaom-1;else /選擇移動臂方向向外，則先向外掃描cout磁盤掃描序列為：;for(j=r;jm;j+)coutcidaoj=0;j-) /磁頭移動到最大號，則改變方向向內(nèi)掃描未掃描的磁道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 * * 歡迎