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

1、 目 錄1.需求分析22. 數(shù)據(jù)結(jié)構(gòu)的設(shè)計22.1 函數(shù)介紹23.程序概要設(shè)計內(nèi)容23.1磁盤調(diào)度23.1.1先來先服務(wù)（fcfs）23.1.2最短時間優(yōu)先算法33.1.3掃描（scan）調(diào)度算法33.1.4循環(huán)掃描（cscan）算法34.程序詳細(xì)設(shè)計及流程圖44.1系統(tǒng)流程圖44.2先來先服務(wù)(fcfs)44.3最短尋道時間優(yōu)先(sstf)54.4掃描算法(scan)54.5循環(huán)掃描(cscan)算法75.功能模塊描述及使用說明85.1先來先服務(wù)調(diào)度(fcfs)85.2最短尋道時間優(yōu)先調(diào)度(sstf)85.3掃描調(diào)度算法(scan)95.4循環(huán)掃描算法(cscan)106.心得體會及結(jié)束語1

2、17.參考文獻(xiàn)11附源代碼121. 需求分析操作系統(tǒng)的任務(wù)之一就是有效的使用硬件。對于磁盤驅(qū)動器，滿足這一要求意味著要有較快的訪問速度和較寬的磁盤帶寬。訪問時間包括兩個主要部分：尋道時間，旋轉(zhuǎn)延遲。磁盤帶寬是所傳遞的總的字節(jié)數(shù)除以從服務(wù)請求開始到最后傳遞結(jié)束時的總時間。可以通過使用好的訪問順序來調(diào)度磁盤i/o請求，提高訪問速度和寬度。本程序模擬四種磁盤調(diào)度算法：先來先服務(wù)調(diào)度(fcfs)，最短尋道時間優(yōu)先調(diào)度(sstf)，掃描調(diào)度算法(scan)，循環(huán)掃描算法(cscan)。并通過比較，了解各種算法的優(yōu)缺點。2. 數(shù)據(jù)結(jié)構(gòu)的設(shè)計2.1 函數(shù)介紹hand:當(dāng)前磁道號;discline10:隨機生

3、成的磁道號;void setdi(int discl)生成隨機磁道號算法;void copyl(int sour,int dist ,int x) 數(shù)組sour復(fù)制到數(shù)組dist，復(fù)制到x個數(shù)（四）詳細(xì)設(shè)計;void delinq(int sour,int x,int y) 數(shù)組sour把x位置的數(shù)刪除,x后的數(shù)組元素向前挪一位.void paixu()尋道長度由低到高排序void fcfs(int han,int discl)先來先服務(wù)算法(fcfs)void sstf(int han,int discl)最短尋道時間優(yōu)先算法(sstf)int scan(int han,int discl,

4、int x,int y) 掃描算法(scan)void cscan(int han,int discl)循環(huán)掃描算法(cscan)3.程序概要設(shè)計內(nèi)容3.1磁盤調(diào)度在多道程序設(shè)計的計算機系統(tǒng)中，各個進程可能會不斷提出不同的對磁盤進行讀/寫操作的請求。由于有時候這些進程的發(fā)送請求的速度比磁盤響應(yīng)的還要快，因此我們有必要為每個磁盤設(shè)備建立一個等待隊列。3.1.1先來先服務(wù)（fcfs）即先來的請求先被響應(yīng)。fcfs策略看起來似乎是相當(dāng)公平的，但是當(dāng)請求的頻率過高的時候fcfs策略的響應(yīng)時間就會大大延長。fcfs策略為我們建立起一個隨機訪問機制的模型，但是假如用這個策略反復(fù)響應(yīng)從里到外的請求，那么將會

5、消耗大量的時間。為了盡量降低尋道時間，看來我們需要對等待著的請求進行適當(dāng)?shù)呐判?，而不是簡單的使用fcfs策略。這個過程就叫做磁盤調(diào)度管理。有時候fcfs也被看作是最簡單的磁盤調(diào)度算法。3.1.2最短時間優(yōu)先算法要求訪問的磁道，與當(dāng)前磁頭所在的磁道距離最近，以使每次的尋道時間最短。 3.1.3掃描（scan）調(diào)度算法該算法不僅考慮到欲訪問的磁道與當(dāng)前磁道間的距離，更優(yōu)先考慮的是磁頭當(dāng)前的移動方向。例如，當(dāng)磁頭正在自里向外移動時，scan算法所考慮的下一個訪問對象，應(yīng)是其欲訪問的磁道，既在當(dāng)前磁道之外，又是距離最近的。這樣自里向外的訪問，直至再無更外的磁道需要訪問時，才將磁道換向自外向里移動。這時

6、，同樣也是每次選擇這樣的進程來調(diào)度，也就是要訪問的當(dāng)前位置內(nèi)距離最近者，這樣，磁頭又逐步地從外向里移動，直至再無更里面的磁道要訪問，從而避免了出現(xiàn)“饑餓”現(xiàn)像。3.1.4循環(huán)掃描（cscan）算法當(dāng)磁頭剛從里向外移動而越過了某一磁道時，恰好又有一進程請求訪問此磁道，這時，該里程就必須等待，為了減少這種延遲，cscan算法規(guī)定磁頭單向移動，而本實驗過程中我們所設(shè)計的是磁頭從里向外移動，而從外向里移動時只須改方向而已，本實驗未實現(xiàn)。但本實驗已完全能演示循環(huán)掃描的全過程。4.程序詳細(xì)設(shè)計及流程圖4.1系統(tǒng)流程圖： 4.2先來先服務(wù)(fcfs):這是一種簡單的磁盤調(diào)度算法。它根據(jù)進程請求訪問磁盤的先后

7、次序進行調(diào)度。此算法的優(yōu)點是公平、簡單，且每個進程的請求都能依次得到處理，不會出現(xiàn)某一進程的請求長期得不到滿足的情況。但此算法由于未對尋道進行優(yōu)化，致使平均尋道時間可能較長。先來先服務(wù)算法（fcfs）流程圖：4.3最短尋道時間優(yōu)先(sstf):該算法選擇這樣的進程，其要求訪問的磁道與當(dāng)前磁頭所在的磁道距離最近，以使每次的尋道時間最短，但這種調(diào)度算法卻不能保證平均尋道時間最短。最短尋道時間優(yōu)先流程圖：4.4掃描算法(scan):scan算法不僅考慮到欲訪問的磁道與當(dāng)前磁道的距離，更優(yōu)先考慮的是磁頭的當(dāng)前移動方向。例如，當(dāng)磁頭正在自里向外移動時，scan算法所選擇的下一個訪問對象應(yīng)是其欲訪問的磁道

8、既在當(dāng)前磁道之外，又是距離最近的。這樣自里向外地訪問，直到再無更外的磁道需要訪問才將磁臂換向，自外向里移動。這時，同樣也是每次選擇這樣的進程來調(diào)度，即其要訪問的磁道，在當(dāng)前磁道之內(nèi)，從而避免了饑餓現(xiàn)象的出現(xiàn)。由于這種算法中磁頭移動的規(guī)律頗似電梯的運行，故又稱為電梯調(diào)度算法。掃描算法（scan）流程圖4.5循環(huán)掃描(cscan)算法:處理該進程的請求，致使該進程的請求被嚴(yán)重地推遲。為了減少這種延遲，cscan算法規(guī)定磁頭單向移動。例如，只自里向外移動，當(dāng)磁頭移到最外的被訪問磁道時，磁頭立即返回到最里的欲訪磁道，即將最小磁道號緊接著最大磁道號構(gòu)成循環(huán)，進行掃描。循環(huán)掃描算法（cscan）流程圖：5

9、.功能模塊描述及使用說明5.1先來先服務(wù)調(diào)度(fcfs)輸入起始磁道（你可以輸入100），點確定，進入第二個界面，再輸入你要輸入的最大磁道（你可以輸入50），然后點確定。選擇磁盤調(diào)度算法1 2 3 4中的任意一個，若選擇1后確認(rèn)，則隨機輸出10個小于50的磁道數(shù)(41 17 34 0 19 24 28 8 12 14)，則先來先服務(wù)調(diào)度(fcfs)輸出：(41 17 34 0 19 24 28 8 12 14)，在選擇1或者0，選著1則繼續(xù)其它算法的磁盤調(diào)度，選著0則結(jié)束磁盤調(diào)度運行結(jié)果圖：5.2最短尋道時間優(yōu)先調(diào)度(sstf)輸入起始磁道（你可以輸入100），點確定，進入第二個界面，再輸入你

10、要輸入的最大磁道（你可以輸入50），然后點確定。選擇磁盤調(diào)度算法1 2 3 4中的任意一個，若選擇2后確認(rèn)，則隨機輸出10個小于50的磁道數(shù)(5 45 31 27 11 41 45 42 27 36) ,則最短尋道時間優(yōu)先調(diào)度(sstf)：(45 45 42 41 36 31 27 27 11) 。在選擇1或者0，選著1則繼續(xù)其它算法的磁盤調(diào)度，選著0則結(jié)束磁盤調(diào)度.運行結(jié)果圖：5.3掃描調(diào)度算法(scan)輸入起始磁道（你可以輸入100），點確定，進入第二個界面，再輸入你要輸入的最大磁道（你可以輸入50），然后點確定。選擇磁盤調(diào)度算法1 2 3 4中的任意一個，若選擇3后確認(rèn)，則隨機輸出10

11、個小于50的磁道數(shù)：(41 4 2 3 42 32 21 16 18 45)，則掃描調(diào)度算法(scan)：(45 42 41 32 21 18 16 4 3 2) 。在選擇1或者0，選著1則繼續(xù)其它算法的磁盤調(diào)度，選著0則結(jié)束磁盤調(diào)度。運行結(jié)果圖：5.4循環(huán)掃描算法(cscan)輸入起始磁道（你可以輸入100），點確定，進入第二個界面，再輸入你要輸入的最大磁道（你可以輸入50），然后點確定。選擇磁盤調(diào)度算法1 2 3 4中的任意一個，若選擇4后確認(rèn)，則隨機輸出10個小于50的磁道數(shù)：（47 26 21 38 19 12 17 49 35 44），則循環(huán)掃描算法(cscan)：（12 17 19

12、 21 26 35 38 44 47 49）。運行結(jié)果圖：6.心得體會及結(jié)束語至此，計算機操作系統(tǒng)課程設(shè)計算法已經(jīng)完成。此次設(shè)計基本完成了所規(guī)定的功能，但由于這次設(shè)計的時間比較倉促，其中不免會有些紕漏，比如在程序的實現(xiàn)上還不夠嚴(yán)謹(jǐn)，出錯處理不夠完善等多方面問題，這些都有進一步改善。 由于平時上課不是很認(rèn)真許多概念沒有理解清楚，導(dǎo)致在做設(shè)計時有點無從下手的感覺，只好邊實驗邊看書直到弄懂概念后才開始做設(shè)計導(dǎo)致時間有點緊張，最終在同學(xué)和老師的指導(dǎo)下我完成了設(shè)計，此設(shè)計基本能夠?qū)崿F(xiàn)規(guī)定的要求但是還是不夠完善，很多東西做的不夠好，程序不夠完善和嚴(yán)謹(jǐn)。此次課程設(shè)計中我學(xué)到了很多東西，無論在理論上還是實踐中

13、，都得到不少的提高，這對于我以后的工作和學(xué)習(xí)都有一種巨大的幫助。7.參考文獻(xiàn)（1） 湯小丹 梁紅兵 哲鳳屏 湯子瀛 編著. 計算機操作系統(tǒng)（第三版）.西安電子科技大學(xué)出版社. 2007.（2） 譚浩強 編著.c程序設(shè)計（第三版）.清華大學(xué)出版社.2005附源代碼#include stdio.h#include stdlib.hvoid copyl(int sour,int dist ,int x); /數(shù)組sour復(fù)制到數(shù)組dist，復(fù)制到x個數(shù)void setdi(int discl); /隨機生成磁道數(shù) void print(int pri,int x); /打印輸出數(shù)組privoid d

14、elinq(int sour,int x,int y); /數(shù)組sour把x位置的數(shù)刪除，并把y前面的數(shù)向前移動，y后的數(shù)保持不變(即會出現(xiàn)2個y) void fcfs(int han,int discl); /先來先服務(wù)算法(fcfs)void sstf(int han,int discl); /最短尋道時間優(yōu)先算法(sstf)int scan(int han,int discl,int x,int y); /掃描算法(scan)void cscan(int han,int discl); /循環(huán)掃描算法(cscan)/void n_step_scan(int han1,int discl)

15、; /n步掃描算法(nstepscan)void paixu(); /尋道長度由低到高排序void pri();int nall=0;int best52; /用作尋道長度由低到高排序時存放的數(shù)組 int limit=0; /輸入尋找的范圍磁道數(shù)iint jage;float aver=0;int main() int i; int discline10; /聲明準(zhǔn)備要生成的隨機磁道號的數(shù)組 int hand; /磁道數(shù) int con=1; int n; while(con=1) jage=0; printf(n 請輸入初始的磁道數(shù)(0n65536) printf(超出范圍!); elsep

16、rintf( *n);printf( * 磁盤調(diào)度算法 *n); printf( *n); printf(* 1.先來先服務(wù)算法(fcfs) *n); printf( * 2.最短尋道時間優(yōu)先算法(sstf) *n); printf( * 3.掃描算法(scan) *n); printf( * 4.循環(huán)掃描算法(cscan) *n); printf( *n); scanf(%d,&n); if(n=0) exit(0); printf(n); switch(n) case 1: setdi(discline); /隨機生成磁道數(shù) fcfs(hand,discline); /先來先服務(wù)算法(fc

17、fs) break; case 2: setdi(discline); /隨機生成磁道數(shù) sstf(hand,discline); /最短尋道時間優(yōu)先算法(sstf) break; case 3: setdi(discline); /隨機生成磁道數(shù) scan(hand,discline,0,9); /掃描算法(scan) break; case 4: setdi(discline); /隨機生成磁道數(shù) cscan(hand,discline); /循環(huán)掃描算法(cscan) break; case 5: setdi(discline); /隨機生成磁道數(shù) setdi(discline); /隨

18、機生成磁道數(shù) fcfs(hand,discline); /先來先服務(wù)算法(fcfs) sstf(hand,discline); /最短尋道時間優(yōu)先算法(sstf) scan(hand,discline,0,9); /掃描算法(scan) cscan(hand,discline); /循環(huán)掃描算法(cscan) paixu(); /尋道長度由低到高排序 printf(nn+ 尋道長度由低到高排序:); for(i=0;i5;i+) printf(%4d ,besti0); break; printf(nn+ 是否繼續(xù)(按0結(jié)束,按1繼續(xù))?); scanf(%5d,&con); /數(shù)組sour復(fù)

19、制到數(shù)組dist，復(fù)制到x個數(shù)void copyl(int sour,int dist ,int x) int i; for(i=0;i=x;i+) disti=souri; /打印輸出數(shù)組privoid print(int pri,int x) int i; for(i=0;i=x;i+) printf(%5d,prii); /隨機生成磁道數(shù)void setdi(int discl) int i; for(i=0;i=9;i+) discli=rand()%limit;/隨機生成10個磁道號 printf(+ 需要尋找的磁道號:); print(discl,9); /輸出隨機生成的磁道號 p

20、rintf(n);/數(shù)組sour把x位置的數(shù)刪除，并把y前面的數(shù)向前移動，y后的數(shù)保持不變(即會出現(xiàn)2個y) void delinq(int sour,int x,int y) int i; for(i=x;iy;i+) souri=souri+1; x+; /先來先服務(wù)算法(fcfs)void fcfs(int han,int discl) int rline10; /將隨機生成的磁道數(shù)數(shù)組discl復(fù)制給數(shù)組rline int i,k,all,temp; /temp是計算移動的磁道距離的臨時變量 all=0; /統(tǒng)計全部的磁道數(shù)變量 k=9; /限定10個的磁道數(shù) copyl(discl,

21、rline,9); /復(fù)制磁道號到臨時數(shù)組rline printf(n+ 按照fcfs算法磁道的訪問順序為:); all=han-rline0; for(i=0;i=9;i+) temp=rline0-rline1;/求出移動磁道數(shù),前一個磁道數(shù)減去后一個磁道數(shù)得出臨時的移動距離 if(temp0) temp=(-temp);/移動磁道數(shù)為負(fù)數(shù)時,算出相反數(shù)作為移動磁道數(shù) printf(%5d,rline0); all=temp+all;/求全部磁道數(shù)的總和 delinq(rline,0,k);/每個磁道數(shù)向前移動一位 k-; bestjage1=all;/best1存放移動磁道數(shù) bestj

22、age0=1; /best0存放算法的序號為:1 jage+;/排序的序號加1 aver=(float) all)/10;/求平均尋道次數(shù) printf(n+ 移動磁道數(shù): ,all); printf(n+ 平均尋道長度:*%0.2f* ,aver);/最短尋道時間優(yōu)先算法(sstf)void sstf(int han,int discl) int i,j,k,h,all; int temp; /temp是計算移動的磁道距離的臨時變量 int rline10; /將隨機生成的磁道數(shù)數(shù)組discl復(fù)制給數(shù)組rline int min; all=0; /統(tǒng)計全部的磁道數(shù)變量 k=9; /限定10個

23、的磁道數(shù) copyl(discl,rline,9); /復(fù)制磁道號到臨時數(shù)組rline printf(n+ 按照sstf算法磁道的訪問順序為:); for(i=0;i=9;i+) min=64000; for(j=0;jhan) /如果第一個隨機生成的磁道號大于當(dāng)前的磁道號，執(zhí)行下一句 temp=rlinej-han; /求出臨時的移動距離 else temp=han-rlinej; /求出臨時的移動距離 if(tempmin) /如果每求出一次的移動距離小于min，執(zhí)行下一句 min=temp; /temp臨時值賦予min h=j; /把最近當(dāng)前磁道號的數(shù)組下標(biāo)賦予h all=all+min

24、; /統(tǒng)計一共移動的距離 printf(%5d,rlineh); han=rlineh; delinq(rline,h,k); /每個磁道數(shù)向前移動一位 k-; bestjage1=all;/best1存放移動磁道數(shù) bestjage0=2;/best0存放算法的序號為:2 jage+;/排序序號加1 aver=(float)all)/10;/求平均尋道次數(shù) printf(n+ 移動磁道數(shù): ,all); printf(n+ 平均尋道長度:*%0.2f* ,aver);/掃描算法(scan)int scan(int han,int discl,int x,int y) int j,n,k,h,

25、m,all; int t=0; int temp; int min; int rline10; /將隨機生成的磁道數(shù)數(shù)組discl復(fù)制給數(shù)組rline int order; order=1; k=y; m=2; /控制while語句的執(zhí)行，即是一定要使當(dāng)前磁道向內(nèi)向外都要掃描到 all=0; /統(tǒng)計全部的磁道數(shù)變量 copyl(discl,rline,9); /復(fù)制磁道號到臨時數(shù)組rline printf(n+ 按照scan算法磁道的訪問順序為:); min=64000; for(j=x;jhan) /如果第一個隨機生成的磁道號大于當(dāng)前的磁道號，執(zhí)行下一句 temp=rlinej-han; /

26、求出臨時的移動距離 else temp=han-rlinej; /求出臨時的移動距離 if(temp=han) /判斷磁道的移動方向，即是由里向外還是由外向里 order=0; t=1; han=rlineh; delinq(rline,h,k); /每個磁道數(shù)向前移動一位 k-; while(m0) if(order=1) /order是判斷磁盤掃描的方向標(biāo)簽，order是1的話，磁道向內(nèi)移動 for(j=x;j=y;j+) h=-1; min=64000; for(n=x;n=k;n+) /判斷離當(dāng)前磁道最近的磁道號 if(rlinen=han) temp=han-rlinen; if(t

27、empmin) min=temp; /temp臨時值賦予min h=n; /把最近當(dāng)前磁道號的數(shù)組下標(biāo)賦予h if(h!=-1) all=all+min; /疊加移動距離 printf(%5d,rlineh); han=rlineh; /最近的磁道號作為當(dāng)前磁道 delinq(rline,h,k); k-; order=0; /當(dāng)完成向內(nèi)的移動，order賦予0，執(zhí)行else語句，使磁道向外移動 m-; /向內(nèi)完成一次，m減一次，保證while循環(huán)執(zhí)行兩次 else /order是0的話，磁道向外移動 for(j=x;j=y;j+) h=-1; min=64000; for(n=x;n=han) temp=rlinen-han; if(temp5) bestjage1=all;/best1存放移動磁道數(shù) bestjage0=3;/best0存放算法的序號為:3 jage+;/排序序號加1 aver=(float)all)/10;/求平均尋道次數(shù) printf(n+ 移動磁道數(shù): ,all); printf(n+ 平均尋道長度:*%0.2f* ,aver); if(t=1) print