操作系統(tǒng)磁盤調(diào)度算法實(shí)驗(yàn)報(bào)告材料

1、目錄目錄 11課程設(shè)計(jì)目的 11.1 編寫目的 12課程設(shè)計(jì)容 12.1 設(shè)計(jì)容 13.1 模塊調(diào)用關(guān)系圖 34 測(cè)試數(shù)據(jù)和結(jié)果 75 參考文獻(xiàn) 106 總結(jié) 101 課程設(shè)計(jì)目的1.1編寫目的本課程設(shè)計(jì)的目的是通過磁盤調(diào)度算法設(shè)計(jì)一個(gè)磁盤調(diào)度模擬系統(tǒng)， 從而使磁盤調(diào)度算法更加形象化，容易使人理解，使磁盤調(diào)度的特點(diǎn)更簡(jiǎn) 單明了，能使使用者加深對(duì)先來(lái)先服務(wù)算法、最短尋道時(shí)間優(yōu)先算法、掃 描算法以及循環(huán)掃描算法等磁盤調(diào)度算法的理解。2.課程設(shè)計(jì)容2.1設(shè)計(jì)容系統(tǒng)主界面可以靈活選擇某種算法，算法包括：先來(lái)先服務(wù)算法（FCFS）、最短尋道時(shí)間優(yōu)先算法（SSTF）、掃描算法（SCAN ）、循環(huán)掃描算法（

2、CSCAN ）。1、先來(lái)先服務(wù)算法（FCFS這是一種比較簡(jiǎn)單的磁盤調(diào)度算法。它根據(jù)進(jìn)程請(qǐng)求訪問磁盤的先后 次序進(jìn)行調(diào)度。此算法的優(yōu)點(diǎn)是公平、簡(jiǎn)單，且每個(gè)進(jìn)程的請(qǐng)求都能依次 得到處理，不會(huì)出現(xiàn)某一進(jìn)程的請(qǐng)求長(zhǎng)期得不到滿足的情況。此算法由于 未對(duì)尋道進(jìn)行優(yōu)化，在對(duì)磁盤的訪問請(qǐng)求比較多的情況下，此算法將降低 設(shè)備服務(wù)的吞吐量，致使平均尋道時(shí)間可能較長(zhǎng)，但各進(jìn)程得到服務(wù)的響 應(yīng)時(shí)間的變化幅度較小。2、最短尋道時(shí)間優(yōu)先算法（SSTF）該算法選擇這樣的進(jìn)程，其要求訪問的磁道與當(dāng)前磁頭所在的磁道距 離最近，以使每次的尋道時(shí)間最短，該算法可以得到比較好的吞吐量，但 卻不能保證平均尋道時(shí)間最短。其缺點(diǎn)是對(duì)用戶的

3、服務(wù)請(qǐng)求的響應(yīng)機(jī)會(huì)不 是均等的，因而導(dǎo)致響應(yīng)時(shí)間的變化幅度很大。在服務(wù)請(qǐng)求很多的情況下，對(duì)外邊緣磁道的請(qǐng)求將會(huì)無(wú)限期的被延遲，有些請(qǐng)求的響應(yīng)時(shí)間將不可預(yù) 期。3、掃描算法（SCAN掃描算法不僅考慮到欲訪問的磁道與當(dāng)前磁道的距離，更優(yōu)先考慮的 是磁頭的當(dāng)前移動(dòng)方向。例如，當(dāng)磁頭正在自里向外移動(dòng)時(shí)，掃描算法所 選擇的下一個(gè)訪問對(duì)象應(yīng)是其欲訪問的磁道既在當(dāng)前磁道之外，又是距離 最近的。這樣自里向外地訪問，直到再無(wú)更外的磁道需要訪問才將磁臂換 向，自外向里移動(dòng)。這時(shí)，同樣也是每次選擇這樣的進(jìn)程來(lái)調(diào)度，即其要 訪問的磁道，在當(dāng)前磁道之，從而避免了饑餓現(xiàn)象的出現(xiàn)。由于這種算法 中磁頭移動(dòng)的規(guī)律頗似電梯的運(yùn)

4、行，故又稱為電梯調(diào)度算法。此算法基本 上克服了最短尋道時(shí)間優(yōu)先算法的服務(wù)集中于中間磁道和響應(yīng)時(shí)間變化比 較大的缺點(diǎn)，而具有最短尋道時(shí)間優(yōu)先算法的優(yōu)點(diǎn)即吞吐量較大，平均響 應(yīng)時(shí)間較小，但由于是擺動(dòng)式的掃描方法，兩側(cè)磁道被訪問的頻率仍低于 中間磁道。4、循環(huán)掃描算法（CSCAN循環(huán)掃描算法是對(duì)掃描算法的改進(jìn)。如果對(duì)磁道的訪問請(qǐng)均勻分布的,當(dāng)磁頭到達(dá)磁盤的一端，并反向運(yùn)動(dòng)時(shí)落在磁頭之后的訪問請(qǐng)求相對(duì)較少。 這是由于這些磁道剛被處理，而磁盤另一端的請(qǐng)求密度相當(dāng)高，且這些訪 問請(qǐng)求等待的時(shí)間較長(zhǎng)，為了解決這種情況，循環(huán)掃描算法規(guī)定磁頭單向 移動(dòng)。例如，只自里向外移動(dòng)，當(dāng)磁頭移到最外的被訪問磁道時(shí)，磁頭立

5、 即返回到最里的欲訪磁道，即將最小磁道號(hào)緊接著最大磁道號(hào)構(gòu)成循環(huán)， 進(jìn)行掃描。3.模塊流程圖3.1模塊調(diào)用關(guān)系圖磁盤調(diào)度模擬系統(tǒng)最短尋道時(shí)間掃 描 算 法先 來(lái) 先 服 務(wù)3.2模塊程序流程圖FCFS算法（先來(lái)先服務(wù)）流程圖輸入磁道號(hào)按輸入順序?qū)⒋诺佬蛄休敵銮笃骄鶎さ篱L(zhǎng)度LJ輸出移動(dòng)的平均磁道數(shù)SSTF （最短尋道時(shí)間優(yōu)先算法） 算法流程圖：SCAN算法（掃描算法）流程圖:CSCAN算法（循環(huán)掃描算法）流程圖:開始輸入磁道號(hào)使用冒泡法從小到大排序輸出排好序的磁道序列輸入當(dāng)前磁道號(hào)規(guī)定移動(dòng)臂單向反 復(fù)的從內(nèi)向外掃描掃描到最大號(hào)后，直接 移動(dòng)到最小號(hào)從內(nèi)向外掃描未掃描的磁道求平均尋道長(zhǎng)度4 測(cè)試數(shù)

6、據(jù)和結(jié)果輸入磁道序列號(hào)：25 160 78 65 100 62 16 53 45選擇算法1,平均尋道長(zhǎng)度46.4444;嚀：遲出l-. C: tDOCEJMEBTS AID SETT rrGSDlIlTSTEATCEXlll saanfaVDifbaiLuif a. eze4HVJiK1K亜-V25.4 逍；也 1內(nèi)毬內(nèi) 吐J3業(yè)一.-rK 咼求當(dāng)描直 HH遲何竊殳 KM毒圭.r品節(jié)K-K M MMrX HGE 10SM X A-H H KM-M KMM K62 lb &3 4S6253 4SKMM MKNfqttWKMrtNMK NMHlt MMXWH SUCKkHNKMNMMMMM：r*系

7、斬聚甲*廠AJTO SETHH&5anil Bl STKATORV&Bj 3noa11f aDebiai suimf a- eie2 CLB5 I -舟阪77-.反 r,尋n.畀丘 蔚當(dāng)屆11 世甲.門尋選擇算法3,磁臂移動(dòng)方向?yàn)橛赏庀?，平均尋道長(zhǎng)度為16.4444選擇算法4,平均尋道長(zhǎng)度為 31.4444K -H MXM N MKK MX：M M MXK M MM K KMMLUUHM44EXKMMXM9MHKM73 me IbUM-HXW-H irN K-M-XWWM KM-MM MWME M-KX KKM*MH-KK-M-M-XliOI-M MM坯統(tǒng)菜單十*1.先禾先軀爵2.蛀短尋:直弓

8、網(wǎng)代去3.掃描凋度4. ffpMtzP苗5.起出MKM-I-HEAJ3FV九令4bl&B 16 島5參考文獻(xiàn)計(jì)算機(jī)操作系統(tǒng) （ 修訂版 ） 湯子瀛電子科技大學(xué)操作系統(tǒng)教程方敏編電子科技大學(xué)操作系統(tǒng)實(shí)用教程（第二版）任愛華清華大學(xué)操作系統(tǒng)原理與實(shí)踐教程周湘貞清華程序設(shè)計(jì)基礎(chǔ)教程家駿機(jī)械工業(yè)6總結(jié)通過這次試驗(yàn)，我們清楚的了解到磁盤調(diào)度的詳細(xì)過程和四種調(diào)度算 法（先來(lái)先服務(wù)算法；最短尋道時(shí)間優(yōu)先算法；掃描算法；循環(huán)掃描算法） 以及四種調(diào)度算法之間的差異和共性，同時(shí)，也看到了經(jīng)過優(yōu)化的算法會(huì) 帶來(lái)的好處！在實(shí)驗(yàn)過程中，也遇到了不少問題，在實(shí)現(xiàn)掃描算法時(shí)出現(xiàn)了問題！ 當(dāng)輸入的當(dāng)前的磁道號(hào)不在磁盤請(qǐng)求序列

9、中時(shí)，程序可以正常執(zhí)行，當(dāng)輸 入的當(dāng)前的磁道號(hào)在磁盤請(qǐng)求序列中時(shí)，程序執(zhí)行時(shí)出現(xiàn)處理序列順序錯(cuò) 誤的問題，通過和同學(xué)的討論，發(fā)現(xiàn)有兩個(gè)循環(huán)中的自變量初值設(shè)置有問 題，經(jīng)過調(diào)整后，程序執(zhí)行無(wú)誤！以后，在實(shí)現(xiàn)代碼的過程中，一定會(huì)更加小心，防止出現(xiàn)低級(jí)錯(cuò)誤導(dǎo) 致程序出錯(cuò)！附：#include#include #include #include#define maxsize 1000/*判斷輸入數(shù)據(jù)是否有效*/ int decide(char str) /判斷輸入數(shù)據(jù)是否有效 int i=0;while(stri!=0)if(stri9) return 0; break; i+; return i;/

10、*將字符串轉(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 *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;

11、i+)/ 輸出排序結(jié)果coutcidaoi ; coutendl;return cidao;/*先來(lái)先服務(wù)調(diào)度算法 */void FCFS(int cidao,int m)/ 磁道號(hào)數(shù)組，個(gè)數(shù)為 mint now;/ 當(dāng)前磁道號(hào)int sum=0; / 總尋道長(zhǎng)度int j,i; int a;char str100;float ave; /平均尋道長(zhǎng)度cout 磁盤請(qǐng)求序列為： ;for( i=0;im;i+) / 按先來(lái)先服務(wù)的策略輸出磁盤請(qǐng)求序列 coutcidaoi ;coutendl;coutstr; /對(duì)輸入數(shù)據(jù)進(jìn)行有效性判斷a=decide(str);if(a=0)cout 輸入數(shù)

12、據(jù)的類型錯(cuò)誤 ,請(qǐng)重新輸入！ endl;goto B; elsenow=trans(str,a); / 輸入當(dāng)前磁道號(hào) sum+=abs(cidao0-now); cout 磁盤掃描序列為： ;for( i=0;im;i+) / 輸出磁盤掃描序列coutcidaoi ;for(i=0,j=1;jm;i+,j+) /求平均尋道長(zhǎng)度 sum+=abs(cidaoj-cidaoi); ave=(float)(sum)/(float)(m);coutendl; cout 平均尋道長(zhǎng)度： aveendl;/* 最 短 尋 道 時(shí) 間 優(yōu) 先 調(diào) 度 算 法 */ void SSTF(int cidao,

13、int m)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; / 對(duì)輸入數(shù)據(jù)進(jìn)行有效性判斷a=decide(str);if(a=0)cout 輸入數(shù)據(jù)的類型錯(cuò)誤 ,請(qǐng)重新輸入！ endl; goto C;elsenow=trans(str,a); /輸入當(dāng)前磁道號(hào)if(cidaom-1=now)/若當(dāng)前磁道號(hào)大于請(qǐng)求序列中最大者，則直接由外向依次給予各請(qǐng)求服務(wù)cout=0;i-) coutcidaoi=now)/ 若當(dāng)前磁道號(hào)小于請(qǐng)求序列

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

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

16、ble(cidao,m);coutstr; / 對(duì)輸入數(shù)據(jù)進(jìn)行有效性判斷 a=decide(str);if(a=0)cout 輸入數(shù)據(jù)的類型錯(cuò)誤 ,請(qǐng)重新輸入！ endl; goto D;else now=trans(str,a); /輸入當(dāng)前磁道號(hào)if(cidaom-1=now)/若當(dāng)前磁道號(hào)大于請(qǐng)求序列中最大者， 則直接由外向依次給予各請(qǐng)求服務(wù) ,此情況同最短尋道優(yōu)先cout=0;i-) coutcidaoi=now)/若當(dāng)前磁道號(hào)小于請(qǐng)求序列中最小者，則直接由向外依次給予各請(qǐng)求服務(wù) ,此情況同最短尋道優(yōu)先cout 磁盤掃描序列為： ; for(i=0;im;i+) coutcidaoic

17、idao0&nowcidaom-1)/若當(dāng)前磁道號(hào)大于請(qǐng)求序列中最小者且小于最大者 while(cidaoknow)k+;l=k-1;r=k;coutd;if(d=0)/選擇移動(dòng)臂方向向，則先向掃描cout=0;j-)coutcidaoj ;/輸出向掃描的序列for(j=r;jm;j+)/磁頭移動(dòng)到最小號(hào)，則改變方向向外掃描未掃描的磁道coutcidaoj ;/輸出向外掃描的序列 sum=now-2*cidao0+cidaom-1;else/選擇移動(dòng)臂方向向外，則先向外掃描cout 磁盤掃描序列為： ;for(j=r;jm;j+)coutcidaoj=0;j-)/磁頭移動(dòng)到最大號(hào)， 則改變方向

18、向掃描未掃描的磁道coutcidaoj sum=-now-cidao0+2*cidaom-1; ave=(float)(sum)/(float)(m);coutendl;cout 平均尋道長(zhǎng)度：/*/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);aveendl;循環(huán)掃描調(diào)度算/調(diào)用冒泡排序算法排序coutstr; / 對(duì)輸入數(shù)據(jù)進(jìn)行有效性判斷 a=decide(str);if(a=0)cout 輸入數(shù)據(jù)的類型錯(cuò)誤 ,請(qǐng)重

19、新輸入！ endl; goto E;else now=trans(str,a); /輸入當(dāng)前磁道號(hào)if(cidaom-1=now)/若當(dāng)前磁道號(hào)大于請(qǐng)求序列中最大者，則直接將移動(dòng)臂移動(dòng)到最小號(hào)磁道依次向外給予各請(qǐng)求服務(wù)cout 磁盤掃描序列為： ; for(i=0;im;i+) coutcidaoi=now) / 若當(dāng)前磁道號(hào)小于請(qǐng)求序列中最小者，則直接由向 外依次給予各請(qǐng)求服務(wù) ,此情況同最短尋道優(yōu)先cout 磁盤掃描序列為： ;for(i=0;im;i+)coutcidaoicidao0&nowcidaom-1)/若當(dāng)前磁道號(hào)大于請(qǐng)求序列中最小者且小于最大者cout 磁盤掃描序列為： ;w

20、hile(cidaoknow)/單向反復(fù)地從向外掃描k+;l=k-1;r=k;for(j=r;jm;j+)coutcidaoj ;/輸出從當(dāng)前磁道向外掃描的序列for(j=0;jr;j+)/當(dāng)掃描完最大號(hào)磁道，磁頭直接移動(dòng)到最小號(hào)磁道，再向外掃描未掃描的磁道coutcidaoj ;sum=2*cidaom-1+cidaol-now-2*cidao0;ave=(float)(sum)/(float)(m);coutendl;cout 平均尋道長(zhǎng)度： aveendl;void main()int a;int c; /菜單項(xiàng)int cidaomaxsize;int i=0,count; char str100;cout 請(qǐng)輸入磁道序列( 0 結(jié)束)： str; / 對(duì)輸入數(shù)據(jù)進(jìn)行有效性判斷 a=decide(str);if(a=0) endl;endl;coutstr; /對(duì)輸入