操作系統(tǒng)課程設(shè)計磁盤調(diào)度算法

1、前 言摘要：本課程設(shè)計的目的是通過設(shè)計一個磁盤調(diào)度模擬系統(tǒng)，從而使磁盤調(diào)度算法更加形象化，使磁盤調(diào)度的特點(diǎn)更簡單明了，這里主要實(shí)現(xiàn)磁盤調(diào)度的四種算法，分別是：1、先來先服務(wù)算法（FCFS） 2、最短尋道時間優(yōu)先算法（SSTF） 3、掃描算法（SCAN） 4、循環(huán)掃描算法（CSCAN）。 啟動磁盤執(zhí)行輸入輸出操作時，要把移動臂移動到指定的柱面，再等待指定扇區(qū)的旋轉(zhuǎn)到磁頭位置下，然后讓指定的磁頭進(jìn)行讀寫，完成信息傳送；因此，執(zhí)行一次輸入輸出所花的時間有： 尋找時間磁頭在移動臂帶動下移動到指定柱面所花的時間。 延遲時間指定扇區(qū)旋轉(zhuǎn)到磁頭下所需的時間。 傳送時間由磁頭進(jìn)程讀寫完成信息傳送的時間，尋道時

2、間指計算機(jī)在發(fā)出一個尋址命令，到相應(yīng)目標(biāo)數(shù)據(jù)被找到所需時間；其中傳送信息所花的時間，是在硬件設(shè)計時固定的，而尋找時間和延遲時間是與信息在磁盤上的位置有關(guān)；然后設(shè)計出磁盤調(diào)度的設(shè)計方式，包括算法思路、步驟，以及要用到的主要數(shù)據(jù)結(jié)構(gòu)、函數(shù)模塊及其之間的調(diào)用關(guān)系等，并給出詳細(xì)的算法設(shè)計，對編碼進(jìn)行了測試與分析。 最后進(jìn)行個人總結(jié)與設(shè)計體會。關(guān)鍵詞：最短尋道時間優(yōu)先算法、掃描算法、總尋道長度.目 錄前 言22. 課程設(shè)計任務(wù)及要求42.1 設(shè)計任務(wù)42.2 設(shè)計要求43. 算法及數(shù)據(jù)結(jié)構(gòu)53.1算法的總體思想（流程）53.2 實(shí)現(xiàn)過程中用到的數(shù)據(jù)結(jié)構(gòu)63.3 實(shí)現(xiàn)過程中用到的系統(tǒng)調(diào)用114. 程序設(shè)計

3、與實(shí)現(xiàn)114.1 最短尋道時間優(yōu)先算法（SSTF）模塊114.1.1程序流程圖114.1.2 程序說明134.1.3 程序關(guān)鍵代碼134.2掃描算法（SCAN）模塊144.2.1 程序流程圖144.2.2 程序說明164.2.3 程序關(guān)鍵代碼164.3 實(shí)驗(yàn)結(jié)果175. 結(jié)論266. 參考文獻(xiàn)267. 收獲、體會和建議272. 課程設(shè)計任務(wù)及要求2.1 設(shè)計任務(wù) 1.熟悉并掌握磁盤調(diào)度算法管理系統(tǒng)的設(shè)計方法，加強(qiáng)對所學(xué)各種調(diào)度算法及相應(yīng)算法的特點(diǎn)了解。 2.掌握磁盤調(diào)度的基本概念，深刻體會各個算法的優(yōu)缺點(diǎn)，以及算法間的相似點(diǎn)。 2.2 設(shè)計要求 1)定義與算法相關(guān)的數(shù)據(jù)結(jié)構(gòu)，如PCB、隊(duì)列等；

4、2） 實(shí)現(xiàn)2種不同的調(diào)度算法（可使用偽代碼或流程圖進(jìn)行分析）；3） 算法執(zhí)行結(jié)束時，應(yīng)給出總的尋道長度；4） 磁道訪問序列隨機(jī)生成，且要滿足一定的數(shù)量要求（不少于100個）；5）系統(tǒng)實(shí)現(xiàn)必須提供一定的交互性，所需測試數(shù)據(jù)應(yīng)當(dāng)以文件形式提供或者由用戶在測試過程中給出，不可將測試數(shù)據(jù)“寫死”在系統(tǒng)實(shí)現(xiàn)代碼中；6）必須給出足夠的注釋，注釋量不得少于代碼量的一半；7）對于系統(tǒng)中所使用到的系統(tǒng)調(diào)用（API函數(shù)），必須給出函數(shù)的定義原型、使用方法，參數(shù)較為復(fù)雜的，還應(yīng)該給出參數(shù)的具體描述；3. 算法及數(shù)據(jù)結(jié)構(gòu) 3.1算法的總體思想（流程） 開始輸入磁道的個數(shù)生成隨機(jī)的磁道號用戶輸入所選擇的算法進(jìn)行磁盤調(diào)度

5、輸入數(shù)字為1-2？輸出排序后的磁盤序列用戶輸入當(dāng)前磁道號顯示磁盤調(diào)度順序輸入為3？退出程序 結(jié)束總流程圖 Y N Y N 3.2 實(shí)現(xiàn)過程中用到的數(shù)據(jù)結(jié)構(gòu) 1.最短尋道時間優(yōu)先（SSTF）（從100號磁道開始）被訪問的下一個磁道號移動距離（磁道數(shù)）5545583391918219072160701501038112184146平均尋道長度：55.3 圖a SSTF調(diào)度算法示例圖ciidao=55,58,39,18,90,160,150,38,184（可隨機(jī)生成多個）用戶輸入當(dāng)前磁道號now，比較當(dāng)前磁道到每個磁道的移動距離，選擇最短距離的磁道進(jìn)行移動。now指向當(dāng)前磁道號，計算尋道長度sum。

6、用冒泡法對磁道數(shù)組進(jìn)行排序 返回內(nèi)側(cè)（外側(cè)）掃描 將當(dāng)前磁道號與剩余沒有訪問的磁道號進(jìn)行比較，重復(fù)上述操作。并計算平均尋道長度ave。 圖b SSTF算法流程示例圖原磁道號隨機(jī)組成的數(shù)組：cidao=55,58,39,18,90,160,150,38,184；排序后的數(shù)組=18,38,39,5,58,90,150,160,184；輸入當(dāng)前磁道號：now=100； 38 39 39 55 55 55 58 58 58 58 90 90 90 90 90now值:100 90 58 55 39 184 160 160 150 150 150 18 18 18 18 38 38 38 38 39 3

7、9 39 39 55 55 55 55 58 58 58 58 90 90 90 90 now值：18 150 160 184 圖c SSTF算法隊(duì)列示意圖(按磁道訪問順序)2.掃描（SCAN）算法（從100號磁道開始，向磁道號增加方向訪問）被訪問的下一個磁道號移動距離（磁道數(shù)）1505016010184249094583255339163811820平均尋道長度：27.8 圖d SCAN算法示例圖原磁道號隨機(jī)組成的數(shù)組：cidao=55,58,39,18,90,160,150,38,184；排序后的數(shù)組=18,38,39,5,58,90,150,160,184；輸入當(dāng)前磁道號：now=100

8、；選擇磁道移動方向；以磁道號增加的方向移動為例： 55 58 58 90 90 90 184 184 184 184 160 160 160 160 160 150 150 150 150 150 150now值：100 150 160 184 90 58 18 38 38 39 39 39 55 55 55 58 58 58 90 90 90 184 184 184 160 160 160 150 150 150 now值:55 39 38 圖e SCAN算法隊(duì)列示意圖（按磁道訪問順序） 3.3 實(shí)現(xiàn)過程中用到的系統(tǒng)調(diào)用系統(tǒng)模塊調(diào)用關(guān)系圖磁盤調(diào)度算法模擬系統(tǒng)最短尋道時間優(yōu)先掃描算法退出 4.

9、 程序設(shè)計與實(shí)現(xiàn) 4.1 最短尋道時間優(yōu)先算法（SSTF）模塊 4.1.1程序流程圖輸入磁道號串用冒泡法將磁道號從大到小排序判斷now的大小調(diào)用SSTF()函數(shù)輸入當(dāng)前磁道號now開始結(jié)束優(yōu)先服務(wù)離now最近的 磁道移動方向，再掉頭服務(wù)計算總尋道長度，并輸出移動的平均尋道長度直接從大到小給予磁道服務(wù)直接從小到大給予磁道服務(wù)找到離now尋道時間最短的磁道now=cidao0 cidao0now=cidaom-14.1.2 程序說明算法分析 優(yōu)點(diǎn)：相較于先來先服務(wù)算法（FCFS）有更好的尋道性能，使每次的尋道時間最短。 缺點(diǎn)：易造成某個進(jìn)程發(fā)生“饑餓”現(xiàn)象。 最短尋找時間優(yōu)先調(diào)度算法總是從等待訪問

10、者中挑選尋找時間最短的那個請求先執(zhí)行的，而不管訪問者到來的先后次序。例如，如果現(xiàn)在讀寫磁頭正在100號柱面上執(zhí)行輸出操作，而等待訪問者依次要訪問的柱面為55,58,39,18,90,160,150,38,184，那么，當(dāng)100號柱面的操作結(jié)束后，應(yīng)該先處理90號柱面的請求，然后到達(dá)58號柱面執(zhí)行操作，隨后處理55號柱面請求，后繼操作的次序應(yīng)該是39,38,18,150,160,184.采用最短尋找時間優(yōu)先算法決定等待訪問者執(zhí)行操作的次序時，讀寫磁頭總共移動多個柱面的距離，與先來先服務(wù)、算法比較，大幅度地減少了尋找時間，具有更好的尋道性能，因而縮短了為各訪問者請求服務(wù)的平均時間，也就提高了系統(tǒng)效

11、率。但最短查找時間優(yōu)先（SSTF）調(diào)度，F(xiàn)CFS會引起讀寫頭在盤面上的大范圍移動，SSTF查找距離磁頭最短（也就是查找時間最短）的請求作為下一次服務(wù)的對象。SSTF查找模式有高度局部化的傾向，會推遲一些請求的服務(wù)，甚至引起無限拖延（又稱饑餓）。 算法流程：輸入磁頭初始磁道號，序列長度，磁道號序列。選擇磁盤調(diào)度算法（最短尋道時間優(yōu)先調(diào)度(SSTF)）或（掃描調(diào)度算法(SCAN)）中的任意一個，若選擇SSTF，則輸出各進(jìn)程被調(diào)度的順序，并計算總的尋道長度和平均尋道長度，選擇關(guān)閉則結(jié)束磁盤調(diào)度。4.1.3 程序關(guān)鍵代碼for(i=0;im;i+) /*使用冒泡法按從小到大順序排列*/for(j=i+

12、1;jarrayj) temp=arrayi; arrayi=arrayj; arrayj=temp; if(arraym-1=0;i-) coutarrayi=now) /*若當(dāng)前磁道號小于請求序列中最小者，則直接由內(nèi)向外依次給予各請求服務(wù)*/ while(l=0)&(rm) /*當(dāng)前磁道在請求序列范圍內(nèi)*/ if(now-arrayl)=(arrayr-now) /*選擇與當(dāng)前磁道最近的請求給予服務(wù)*/ coutarrayl=0;j-) coutarrayj ; /*輸出向內(nèi)掃描的序列*/ for(j=r;jm;j+) /*磁頭移動到最小號，則改變方向向外掃描未掃描的磁道*/ coutar

13、rayj ; /*輸出向外掃描的序列*/ sum=now-2*array0+arraym-1; else /*選擇移動臂方向向外，則先向外掃描*/ for(j=r;jm;j+) coutarrayj=0;j-) /*磁頭移動到最大號，則改變方向向內(nèi)掃描未掃描的磁道*/ coutarrayj ; sum=-now-array0+2*arraym-1; ave=(float)(sum)/(float)(m);4.3 實(shí)驗(yàn)結(jié)果 運(yùn)行界面截圖及相應(yīng)代碼1. 主界面void display() coutnnnn Operating Systems Curriculum Designn; coutn ;c

14、outn ;coutn 名稱: 磁盤調(diào)度 ; coutn ;coutn 工具: Visual Studio 2010 ; coutn ;coutn 班級:1205 ; coutn ;coutn 作者:施靜 ; coutn ;coutn 學(xué)號：211214020 ; coutn ;coutn n; system(pause);system(cls);2. 前言 提示用戶此程序?qū)崿F(xiàn)的算法cout【載入完成】endlendl;cout 前言endlendl;cout 歡迎使用磁盤調(diào)度算法系統(tǒng)，本程序?qū)崿F(xiàn)了常用的磁盤調(diào)度算法如下所示：nn;cout 最短尋道時間優(yōu)先（SSTF）：最短尋道時間優(yōu)先算法要

15、求訪問的磁盤與當(dāng)前磁頭所在的n;cout 磁盤距離最近，以使每次的尋道時間最短。nn;cout 掃描算法(SCAN)電梯調(diào)度：掃描算法不僅考慮到欲訪問的磁道與當(dāng)前磁道的距離n;cout 更優(yōu)先考慮的是磁頭的當(dāng)前移動方向。nn; system(pause);system(cls);/清屏3. 用戶選擇所使用的算法（先隨機(jī)生成101個磁道號）void showMenu(int cidao,int n) int choice; while(true) cout請您選擇喜歡的算法來實(shí)現(xiàn)調(diào)度(輸入1-3):; coutn ; coutn ; coutn 1.最短尋道時間優(yōu)先(SSTF) |; coutn

16、 ; coutn 2.掃描算法(SCAN) ; coutn ; coutn 3.退出(EXIT) ; coutn ; coutn n; coutendl; while(true) coutchoice; switch(choice) /*case 1: FCFS(a,n); break;*/ case 1: SSTF(cidao,n); break; case 2: SCAN(cidao,n); break; case 3: coutn要退出系統(tǒng)了歡迎使用本系統(tǒng)n; exit(0); 4. 最短尋道時間優(yōu)先算法/*最短尋道時間優(yōu)先調(diào)度算法*/void SSTF(int cidao,int m)

17、 system(cls); int k=1; int now,l,r; int i,j,sum=0; int a; char str100; float ave; cidao=bubble(cidao,m); /調(diào)用冒泡排序算法排序 coutstr; /對輸入數(shù)據(jù)進(jìn)行有效性判斷 a=decide(str); if(a=0) cout輸入數(shù)據(jù)的類型錯誤,請重新輸入！endl; goto C; else now=trans(str,a); /輸入當(dāng)前磁道號 if(cidaom-1=now) /若當(dāng)前磁道號大于請求序列中最大者，則直接由外向內(nèi)依次給予各請求服務(wù) cout=0;i-) coutcida

18、oi=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; else coutcidaor ; sum+=cidaor-

19、now; now=cidaor; 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; cout請按任意鍵返回系統(tǒng)菜單endl; getch(); showMenu(cidao,m); /回到主界面最短尋道時間優(yōu)先（SSTF）算法實(shí)現(xiàn)界面 （2） 掃描（S

20、CAN）算法/*掃描調(diào)度算法*/void SCAN(int cidao,int n)/先要給出當(dāng)前磁道號和移動臂的移動方向int temp;int i,j;int now;int sum;for(i=0;in;i+) /給磁道號排序 for(j=i+1;jcidaoj) temp=cidaoi; cidaoi=cidaoj; cidaoj=temp; coutn按非遞減順序排列好的磁道: n;for(i=0;in;i+) /輸出排好序的磁道號 coutcidaoi ;coutendl;coutnow; /用戶自定義當(dāng)前磁道號if(cidaon-1=0;i-) coutcidaoinow if(

21、cidao0=now) for(i=0;in;i+) coutcidaoi ; sum=cidaon-1-now; else /cidao0now int pointer; int location=1; int left,right; while(cidaolocationnow) location+; left=location-1; right=location; coutpointer; cout=0;j-) coutcidaoj ; for(j=right;jn;j+) coutcidaoj ; sum=now+cidaon-1-2*cidao0; coutendl; if(pointer=1)/磁頭向右移動到最大號，再改變方向向內(nèi)掃描未掃描的磁道 for(j=right;jn;j+) coutcidaoj=0;j-) coutcidaoj ; sum=2*cidaon-1-now-cidao0;/求總尋道長度 coutendl; else coutn輸入不合法!請輸入0或1:n; goto loop; coutnn需要移動的總磁道數(shù)為: sumendl; cout請按任意鍵返回系統(tǒng)菜單endl; getch(); showMenu(cidao,n); /回到主界面5. 結(jié)論 （1）用戶界面友好，采用了選擇菜單模式