操作系統(tǒng)磁盤調(diào)度算法實驗報告

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

2、AN.1、先來先效勞算法FCFS這是一種比擬簡單的磁盤調(diào)度算法.它根據(jù)進程請求訪問磁盤的先后 次序進行調(diào)度.此算法的優(yōu)點是公平、簡單,且每個進程的請求都能依次 得到處理,不會出現(xiàn)某一進程的請求長期得不到滿足的情況.此算法由于 未對尋道進行優(yōu)化,在對磁盤的訪問請求比擬多的情況下,此算法將降低 設備效勞的吞吐量,致使平均尋道時間可能較長,但各進程得到效勞的響 應時間的變化幅度較小.2、最短尋道時間優(yōu)先算法SSTF該算法選擇這樣的進程,其要求訪問的磁道與當前磁頭所在的磁道距 離最近,以使每次的尋道時間最短,該算法可以得到比擬好的吞吐量,但 卻不能保證平均尋道時間最短.其缺點是對用戶的效勞請求的響應時

3、機不 是均等的,因而導致響應時間的變化幅度很大.在效勞請求很多的情況下, 對內(nèi)外邊緣磁道的請求將會無限期的被延遲,有些請求的響應時間將不可 預期.3、掃描算法(SCAN)掃描算法不僅考慮到欲訪問的磁道與當前磁道的距離,更優(yōu)先考慮的 是磁頭的當前移動方向.例如,當磁頭正在自里向外移動時,掃描算法所 選擇的下一個訪問對象應是其欲訪問的磁道既在當前磁道之外,又是距離 最近的.這樣自里向外地訪問,直到再無更外的磁道需要訪問才將磁普換 向,白外向里移動.這時,同樣也是每次選擇這樣的進程來調(diào)度,即其要 訪問的磁道,在當前磁道之內(nèi),從而預防了饑餓現(xiàn)象的出現(xiàn).由于這種算 法中磁頭移動的規(guī)律頗似電梯的運行,故又

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

5、立即返回到最里的欲訪磁道,即將最小磁道號緊接著最大磁道號構(gòu)成 循環(huán),進行掃描.3. 模塊流程圖3.1模塊調(diào)用關系圖3. 2模塊程序流程圖FCFS算法先來先效勞流程圖:結(jié)束SSTF 最短尋道時間優(yōu)先算法 算法流程圖：結(jié)束CSCAN算法循環(huán)掃描算法流程圖:開始4.測試數(shù)據(jù)和結(jié)果輸入磁道序列號：25 160 78 65 100 62 16 53 45選擇算法1,平均尋道長度46.4444；選擇算法2,平均尋道長度為16.6667：.16 .1025 GGG71 麗 16016.系統(tǒng)菜單C八DOCDWENTS AND* 4-循環(huán)掃描* 5-退出JKMXXXKXXMXXXXXXXXXMXMMMXMXMX

6、XXXMXKXXXMXMXXXMMXMXXMCXC為號16G. 5列道3 1 r擊為. 5盤的列度 5著前序矢 *膏當描道 心籬入掃尋 菖序曹坷62 65 78 100* 1.先來先效勞*J2.最短尋晅時間優(yōu)先£:3.掃描調(diào)度二二E1兇2 的451G20動 544固 214 力膏166. 列番.1 .盤的移列度 畚當當描道 售入入掃尋 請連®:晶平53 G2 G5 78<1表示同夕卜62 65 78 100100 1G0. 0表示向內(nèi)：0JL60選擇算法3,磁臂移動方向為由外向內(nèi),平均尋道長度為16.4444c *C:DOCUIEITS AND SETTIHGSADI

7、IHISTRATOR桌面suanf aDebugsuanf a. eze*系統(tǒng)菜單XX1.先來先效勞ZMM“2.最耙尋道時間優(yōu)先-二3.掃捕調(diào)度Z*4.循環(huán)掃:苗*XMMK*5.退.出*選擇算法3,磁臂移動方向為由內(nèi)向外,平均尋道長度為3L 5556：x選擇算法4,平均尋道長度為31.4444x西安電子科技大學出版社 西安電子科技大學出版社 清華大學出版社 清華出版社 機械工業(yè)出版社5.參考文獻?計算機操作系統(tǒng)修訂版?湯子瀛?操作系統(tǒng)教程?方敏編?操作系統(tǒng)實用教程第二版?任愛華?操作系統(tǒng)原理與實踐教程? 周湘貞?程序設計根底教程?陳家駿6 .總結(jié)通過這次試驗,我們清楚的了解到磁盤調(diào)度的詳細過程

8、和四種調(diào)度算 法先來先效勞算法；最短尋道時間優(yōu)先算法；掃描算法：循環(huán)掃描算法 以及四種調(diào)度算法之間的差異和共性,同時,也看到了經(jīng)過優(yōu)化的算法會 帶來的好處！在實驗過程中,也遇到了不少問題,在實現(xiàn)掃描算法時出現(xiàn)了問題！ 當輸入的當前的磁道號不在磁盤請求序列中時,程序可以正常執(zhí)行,當輸 入的當前的磁道號在磁盤請求序列中時,程序執(zhí)行時出現(xiàn)處理序列順序錯 誤的問題,通過和同學的討論,發(fā)現(xiàn)有兩個循環(huán)中的變量初值設置有問 題,經(jīng)過調(diào)整后,程序執(zhí)行無誤！以后,在實現(xiàn)代碼的過程中,一定會更加小心,預防出現(xiàn)低級錯誤導 致程序出錯！附：#include<stdio. h>#include<std

9、lib. h>ttinclude<iostream. h>ttinclude<math. h>define maxsize 1000/ * 判 斷 輸 入 數(shù) 據(jù) 是 否 有 效/int decide (char str ) /判斷輸入數(shù)據(jù)是否有效int i=O;while(stri !=' O')if (stri<O' | |stri>'9')return 0;break;)i+十；return i;)/* 將字符 串轉(zhuǎn)換成數(shù)字 */ int trans (char str, int a)/將宇符串轉(zhuǎn)換成數(shù)宇i

10、nt i;int sum=0;for(i=0;i<a;i+)sum=sum+(int) (stri-' O' )*pow(10, a-iT);)return sum;)/* 冒泡排序算法 */ int *bubble(int cidao, int m)int i, j;int temp;for(i=0;i<m;i)使用冒泡法按從小到大順序排列for(j=i+l; j<m; j+)if(cidaoi>cidaoj)temp=cidaoi;cidaoLi=cidaoLj;cidaoj=temp;)cout«/z排序后的磁盤序列為："；fo

11、r( i=0;i<m; i+)/輸出排序結(jié)果cout«cidaoi«* *:cout«endl;return cidao;)/ *先 來 先 服 務 調(diào) 度 算 法.rY* xY% .void FCFS(int cidao, int m)/磁道號數(shù)組,個數(shù)為 m(int now,/當前磁道號int sum=0; 總尋道長度int j, i；int a;char strtlOO;float ave;/平均尋道長度cout«磁盤請求序列為："；for( i=0;im;i+)按先來先效勞的策略輸出磁盤請求序列(cout«cidaoi&

12、#171;*)cout«endl;cout«*請輸入當前的磁道號："；B： cin»str; /對輸入數(shù)據(jù)進行有效性判斷a=decide(str); if(a=0)cout«,z輸入數(shù)據(jù)的類型錯誤,請重新輸入！ ?endl;goto B;)elsenow=trans (str, a);輸入當前磁道號sum+=abs(cidao0j-now);cout«"磁盤掃描序列為：；for( i=0;i<m;i+)/輸出磁盤掃描序列cout«cidaoi«* *;for(i=0, j=l;j<m;i+,

13、j+)/求平均尋道長度(sum+=abs (cidaoj-cidaoi);ave=(float)(sum)/(float)(m);)cout«endl;cout<<*平均尋道長度：*«ave«endl;)/* 最短尋道時間優(yōu)先調(diào)度算法*/void SSTF(int cidao,int m)int k=l;int now, 1, r;int i, j, sum=0;int a;char str 100;float ave;cidao=bubble (cidao, m);/調(diào)用冒泡排序算法排序cout«z,請輸入當前的磁道號："；C:

14、cin»str; /對輸入數(shù)據(jù)進行有效性判斷a=decide(str);if(a=0)cout«*輸入數(shù)據(jù)的類型錯誤,請重新輸入！ ?endl; goto C;elsenow=trans(str, a);輸入當前磁道號if (cidao m-l<=now)假設當前磁道號大于請求序列中最大者,那么直接由外向內(nèi)依次給予各請求效勞(COUt«,Z磁盤掃描序列為："；for(i=m-l;i>=0;i)cout«cidaoi«*sum=now-c i dao0;)if(cidao0>=now)假設當前磁道號小于請求序列中最小者

15、,那么直接由內(nèi)向外依次給予各請求效勞(cout«"磁盤掃描序列為："；for(i=0;i<m;i+)cout«cidaoi«* *;sum=c i dao mT -now;i f (now>c i dao 0 &&now< c i dao nrl )/假設當前磁道號大于請求序列中最小者且小丁最大者(cout«"磁盤掃描序列為："；wh i 1 e (c i dao k <now)/確定當前磁道在己排的序列中的位置,后面的算法都用到了,可以直接復制后少量修改,節(jié)省時間.k+;)

16、l=k-l;r=k;whi le (l>=0) && (r<m) 當前磁道在請求序列范圍內(nèi)(if (now-cidao 1 ) <= (cidaor-now)/選擇與當前磁道最近的請求給予效勞cout«cidao1 «*sum+=now-c i dao1 ;now=cidaoEl;1=1-1;)else(cout«cidaor «/*sum+=cidaor-now;now=cidaor;r=r+l;if(l=-l)/磁頭移動到序列的最小號,返回外側(cè)掃描仍未掃描的磁道for(j=r;j<m;j+)cout«

17、cidaoj«*)sum+=c i daom1-c i dao0;else /磁頭移動到序列的最大號,返回內(nèi)側(cè)掃描仍未掃描的磁 道for(j=l;j>=0;j)(cout«cidaoj«*)sum+=c idao Lml -cidao 0;)ave=(float)(sum)/(float)(m);cout«endl;cout«,z平均尋道長度：/<<ave«endl;intintintint/*掃描 調(diào)度 算法 */ void SCAN(int cidao, int m) /先要給出當前磁道號和移動臂的移 動方向k=

18、l；now, 1, r, d;i, j, sum=0;a；char str100;float ave;cidao=bubble (cidao, m) ;/調(diào)用冒泡排序算法排序cout«"請輸入當前的磁道號："；D: cin»str; /對輸入數(shù)據(jù)進行有效性判斷 a=decide(str);if(a=0)cout«*輸入數(shù)據(jù)的類型錯誤,請重新輸入！ ,z«endl; goto D;elsenow=trans(str, a);/輸入當前磁道號if (cidaom-1 <=now)假設當前磁道號大丁請求序列中最大者,那么直接由外向內(nèi)依

19、次給予各請求效勞,此情況同最短尋道優(yōu)先(COUt«,Z磁盤掃描序列為：；for(i=m-l;i>=0;i)cout«cidaoi«*sum=now-c i dao0 ;if (cidao 0 >=now)/假設當前磁道號小于請求序列中最小者,那么直接由內(nèi)向外依次給予各請求效勞,此情況同最短尋道優(yōu)先(cout«"磁盤掃描序列為："；for(i=0;i<m;i+)cout«cidaoi«z,sum=c i dao nr 1 -now;)i f (now>c i dao OJ &&

20、now< c i dao Lm-1)/假設當前磁道號大于請求序列中最小者且小于最大者(while(cidaoLk<now)k+;)l=k-l;r=k;cout«"請輸入當前移動臂的移動的方向(1表示向外,0表示向 內(nèi)):"；cin»d;i f (d=0)/選擇移動W方向向內(nèi),那么先向內(nèi)掃描cout«*磁盤掃描序列為：for(j=l;j>=0;j)cout«cidaoj«*/輸出向內(nèi)掃描的序列for(j=r; j<m; j+)/磁頭移動到最小號,那么改變方向向外掃描未掃描的磁道cout«cid

21、aoj«*/輸出向外掃描的序列)sum=now-2*c i dao0+c i dao1;)else/選擇移動臂方向向外,那么先向外掃描cout«"磁盤掃描序列為：；for(j=r;j<m;j+)cout«cidaoj«*輸出向外掃描的序列for(j=l; j>=0; j-)/磁頭移動到最大號,那么改變方向向內(nèi)掃描未掃描的磁道cout«cidaoj«*)sum=-now-c i dao0+2*c i dao Em-1;)ave=(float)(sum)/(float)(m);cout«endl;cout&

22、#171;,z 平均尋道長度：z,<<ave«endl;)/* 循 環(huán) 掃 描 調(diào) 度 算 法*/ void CSCAN(int cidao, int m)int k=l;int now, 1, r;int i, j, sum=0;int a;char str100;float ave;cidao=bubble (cidao, m);/調(diào)用冒泡排序算法排序cout«"請輸入當前的磁道號：；E: cin»str, 對輸入數(shù)據(jù)進行有效性判斷 a=decide(str);if(a=0)(cout«*輸入數(shù)據(jù)的類型錯誤,請重新輸入！,z&#

23、171;endl;goto E;)elsenow=trans(str, a); 輸入當前磁道號i f (c i dao1 <=now) /假設當前磁道號大于請求序列中最大者,那么直接將移動臂移動到最小號磁道依次向外給予各請求效勞cout«"磁盤掃描即列為： for(i=0;i<m;i+)cout«cidaoi«*sum=now-2*cidao 0 +cidao Lm-1;)if (cidao0>=now) /假設當前磁道號小于請求序列中最小者,那么直接由 內(nèi)向外依次給予各請求效勞,此情況同最短尋道優(yōu)先(COUt«,磁盤掃描序列

24、為：；for(i=0;i<m;i+)cout«cidaoi«*sum=c i dao nr 1 -now;if (now>cidao 0&&now<c idao m-1) /假設當前磁道號大于請求序列 中最小者且小于最大者(COUt«,Z磁盤掃描序列為："； while (cidao k Gow)單向反復地從內(nèi)向外掃描( k+;l=k-l;r=k;for(j=r;j<m;j+)(cout«cidaoj«* ",輸出從當前磁道向外掃描的序列for(j=0;j<r;j+)當掃描完最大

25、號磁道,磁頭直接移動到最小號磁道,再向外掃描未掃描的磁道(cout«cidaoLj<<*)sum=2*c i dao m-1 +c i dao 1 -now2*c i dao 0;)ave=(float)(sum)/(float)(m);cout«endl;cout«,< 平均尋道長度：z,<<ave«endl;void main()int a;int c;/菜單項int cidaomaxsize;int i=0,count;char strF100;cout«"請輸入磁道序列(0結(jié)束)："&#

26、171;endl;A:cin»str; /對輸入數(shù)據(jù)進行有效性判斷 a=decide(str);if(a=0)(C0Ut«/z輸入數(shù)據(jù)的類型錯誤,請重新輸入！ "?endl;goto A;/輸入錯誤,跳轉(zhuǎn)到A,重新輸入elsecidaoi=trans(str,a);i+;while(cidaoiT !=0)(cin»str; 對輸入數(shù)據(jù)進行有效性判斷 a=decide(str);if(a=0)cout«輸入數(shù)據(jù)的類型錯誤,清重新輸入！else(cidaoi=trans(str, a); i+；)count=i-l; 要訪問的磁道數(shù)cout«,z你輸入的磁道序列為："；for(i=0;i<count;i+)(cout«cidaoi«*/輸出磁道序列cout«endl;while(l)cout«endl;cout«"*«endl;