操作系統(tǒng)課程設計報告磁盤調度算法

1、 課 程 設 計課程設計名稱： 操作系統(tǒng)應用課程設計 專 業(yè) 班 級 ： 學 生 姓 名 ： xxxxx 學 號 ： 指 導 教 師 ： 課程設計時間： 2010.12.20-2010.12.26 計算機科學 專業(yè)課程設計任務書學生姓名專業(yè)班級學號題 目磁盤調度算法（sstf，nstepscan）課題性質其它課題來源自擬課題指導教師于俊偉同組姓名張曉鵬主要內容磁盤是可供多個進程共享的設備，當有多個進程都要求訪問磁盤時，應采用一種最佳調度算法，以使各進程對磁盤的平均訪問時間最小。由于在訪問磁盤的時間中，主要是尋道時間，因此，磁盤調度的目標是使磁盤的平均尋道時間最少。也正因為這樣，我們有必要對各算

2、法進行模擬，進而比較、分析、了解設計主界面以靈活選擇某算法，且以下算法都要實現(xiàn)：1、最短尋道時間優(yōu)先調度算法（sstf）2、nstepscan調度算法并求出每種算法的總尋到長度、平均尋道長度任務要求理解磁盤調度算法，并進一步加深對調度算法及其實現(xiàn)過程的理解。1、模擬一個磁盤調度算法；2、要求能夠模擬最短尋道時間優(yōu)先（sstf）、n步掃描算法（nstepscan）算法兩個磁盤調度算法3、輸入為一組作業(yè)的磁道請求，改組磁道好的獲得從文件中取出；4、輸出為按選擇的算法執(zhí)行時的磁頭移動軌跡。參考文獻1 任滿杰等.操作系統(tǒng)原理實用教程.電子工業(yè)出版社,20062 張堯學,史美林.計算機操作系統(tǒng)教程實驗指

3、導.清華大學出版社,2000 3 羅宇.操作系統(tǒng)課程設計.機械工業(yè)出版社,20054 湯子瀛，哲鳳屏，湯小丹編著.計算機操作系統(tǒng).西安電子科技大學出版社, 20055 周敏，楊武，楊承玉編著.計算機操作系統(tǒng)原理實驗指導基于linux（ver3.0）.重慶：重慶工學院,20066 譚浩強編著.c語言程序設計（第3版）.清華大學出版社，2005審查意見指導教師簽字：教研室主任簽字： 年 月 日 說明：本表由指導教師填寫，由教研室主任審核后下達給選題學生，裝訂在設計（論文）首頁一 .課程設計需求分析操作系統(tǒng)是計算機系統(tǒng)的一個重要系統(tǒng)軟件。我們在本課程的實驗過程中，了解實際操作系統(tǒng)的工作過程，在實踐中

4、加深對操作系統(tǒng)原理的理解。磁盤存儲器不僅容量大，存取速度快，而且可以實現(xiàn)隨機存取，是當前存放大量程序和數(shù)據的理想設備，故在現(xiàn)代計算機系統(tǒng)中，都配置了磁盤存儲器，并以它為主來存放文件。這樣，對文件的操作，都將涉及到對磁盤的訪問。磁盤i/o速度的高低和磁盤系統(tǒng)的可靠性都將直接影響到系統(tǒng)性能。因此，設法改善磁盤系統(tǒng)的性能，已成為現(xiàn)代操作系統(tǒng)的重要任務之一。磁盤性能有數(shù)據的組織、磁盤的類型和訪問時間等。磁盤調度的目標是使磁盤的平均尋道時間最少。也正因為這樣，我們有必要對各算法進行模擬，進而比較、分析、了解。本實驗設計的目的是通過設計一個磁盤調度模擬系統(tǒng)，以加深對最短尋道時間優(yōu)先（sstf）、n步掃描算

5、法（nstepscan）等磁盤調度算法的理解。讓我們更好地掌握操作系統(tǒng)的原理及實現(xiàn)方法,加深對操作系統(tǒng)基礎理論和重要算法的理解，加強動手能力。二.課程設計原理設備的動態(tài)分配算法與進程調度相似，也是基于一定的分配策略的。常用的分配策略有先請求先分配、優(yōu)先級高者先分配等策略。在多道程序系統(tǒng)中，低效率通常是由于磁盤類旋轉設備使用不當造成的。操作系統(tǒng)中，對磁盤的訪問要求來自多方面，常常需要排隊。這時，對眾多的訪問要求按一定的次序響應，會直接影響磁盤的工作效率，進而影響系統(tǒng)的性能。訪問磁盤的時間因子由3部分構成，它們是查找（查找磁道）時間、等待（旋轉等待扇區(qū)）時間和數(shù)據傳輸時間，其中查找時間是決定因素。

6、因此，磁盤調度算法先考慮優(yōu)化查找策略，需要時再優(yōu)化旋轉等待策略。平均尋道長度（l）為所有磁道所需移動距離之和除以總的所需訪問的磁道數(shù)（n），即：l=（m1+m2+mi+mn）/n。其中mi為所需訪問的磁道號所需移動的磁道數(shù)。啟動磁盤執(zhí)行輸入輸出操作時，要把移動臂移動到指定的柱面，再等待指定扇區(qū)的旋轉到磁頭位置下，然后讓指定的磁頭進行讀寫，完成信息傳送。因此，執(zhí)行一次輸入輸出所花的時間有：尋找時間磁頭在移動臂帶動下移動到指定柱面所花的時間；延遲時間指定扇區(qū)旋轉到磁頭下所需的時間；傳送時間由磁頭進程讀寫完成信息傳送的時間。其中傳送信息所花的時間，是在硬件設計就固定的。而尋找時間和延遲時間是與信息在

7、磁盤上的位置有關。為了減少移動臂進行移動花費的時間，每個文件的信息不是按盤面上的磁道順序存放滿一個盤面后，再放到下一個盤面上。而是按柱面存放，同一柱面上的各磁道被放滿信息后，再放到下一個柱面上。所以各磁盤的編號按柱面順序（從0號柱面開始），每個柱面按磁道順序，每個磁道又按扇區(qū)順序進行排序。磁盤是可供多個進程共享的設備，當有多個進程都要求訪問磁盤是，應采用一種最佳調度算法，以使各種進程對磁盤的平均訪問時間最小。由于在訪問磁盤的時間中，主要是尋道時間，因此，磁盤調度的目標，是使磁盤的平均尋道時間最少。三.算法分析及程序概要設計1.最短尋道時間優(yōu)先算法（sstf）1.1算法分析：最短尋找時間優(yōu)先調度

8、算法總是從等待訪問者中挑選尋找時間最短的那個請求先執(zhí)行的，而不管訪問者到來的先后次序。也就是說，該算法選擇這樣的進程：其要求訪問的磁道與當前磁頭所在的磁道距離最近，以使每次的尋道時間最短。但這種算法不能保證平均尋道時間最短。現(xiàn)在利用一個例子來討論，假設當前移動臂所在的磁道為100，進程請求訪問磁盤的先后次序為：55、58、39、18、90、160、150、38、184。那么該算法將這樣進行進程調度：現(xiàn)在當100號柱面的操作結束后，應該先處理90號柱面的請求，然后到達58號柱面執(zhí)行操作，隨后處理55號柱面請求，后繼操作的次序應該是39、38、18、150、160、184。采用最短尋找時間優(yōu)先算法

9、決定等待訪問者執(zhí)行操作的次序時，讀寫磁頭總共移動了200多個柱面的距離，與先來先服務、算法比較，大幅度地減少了尋找時間，因而縮短了為各訪問者請求服務的平均時間，也就提高了系統(tǒng)效率。sstf算法雖然能獲得較好的尋道性能，但卻可能導致某個進程發(fā)生“饑餓”（starvation）現(xiàn)象。因為只要不斷有新進程的請求到達，且其所要訪問的磁道與磁頭當前所在磁道的距離較近，這種新進程的i/o請求必然優(yōu)先滿足。也就是說，sstf查找模式有高度局部化的傾向，會推遲一些請求的服務，甚至引起無限拖延（饑餓）。1.2概要設計（流程圖）：6將磁道號從小到大排序輸入當前磁道號nowarraym-1=0輸出磁盤調度序列arr

10、ayj(array0=now磁頭移動總距離sum=now-arrayi目前的位置變?yōu)楫斍暗奈恢胣ow=arrayinow=arrayiim確定當前磁道在已排的序列中的位置now-arrayl)=(arrayr-now先向磁道號減小方向訪問，再向磁道號增加方向訪問輸出磁盤調度序列先向磁道號增加方向訪問，再向磁道號減小方向訪問輸出磁盤調度序列輸出平均尋道長度avg=sum/(m)2、nstepscan算法2.1算法分析n步掃描算法是基于掃描算法發(fā)展而成的，故要想很好的了解它，首先得對掃描算法加以理解分析，只有這樣才能很好地理解n步掃描算法。掃描算法（scan） 又稱電梯調度算法。該算法不僅考慮到與

11、訪問的磁道與當前磁道間的距離，更優(yōu)先考慮的是磁頭當前的移動方向。scan算法是磁頭前進方向上的最短查找時間優(yōu)先算法，它排除了磁頭在盤面局部位置上的往復移動，scan算法這種逐步自里向外又自外向里（或先自外向里又自外向里）的磁頭移動規(guī)率，很好地避免了出現(xiàn)“饑餓”現(xiàn)象，并在很大程度上消除了sstf算法的不公平性，但仍有利于對中間磁道的請求?！半娞菡{度”算法是從移動臂當前位置開始沿著臂的移動方向去選擇離當前移動臂最近的那個柱訪問者，如果沿臂的移動方向無請求訪問時，就改變臂的移動方向再選擇。這好比乘電梯，如果電梯已向上運動到4層時，依次有3位乘客陳生、伍生、張生在等候乘電梯。他們的要求是：陳生在2層等

12、待去10層；伍生在5層等待去底層；張生在8層等待15層。由于電梯目前運動方向是向上，所以電梯的形成是先把乘客張生從8層帶到15層，然后電梯換成下行方向，把乘客伍生從5層帶到底層，電梯最后再調換方向，把乘客陳生從2層送到10層。但是，“電梯調度”算法在實現(xiàn)時，不僅要記住讀寫磁頭的當前位置，還必須記住移動臂的當前前進方向。n步掃描算法是將磁盤請求隊列分成若干個長度為n的子隊列，磁盤調度將按fcfs算法依次處理這些子隊列。而沒處理一個隊列時又是按scan算法，對一個隊列處理完后，在處理其他隊列。當正在處理某子隊列時，如果又出現(xiàn)新的i/o請求，便將新請求進程放入其他隊列，這樣就可以避免出現(xiàn)粘著現(xiàn)象，統(tǒng)

13、稱“磁盤粘著”（armstickiness）(有一個或幾個進程對某一磁道有較高的訪問頻率，即這些進程反復請求對某一磁道的i/o操作，從而壟斷了整個磁盤設備的現(xiàn)象）。而在sstf、scan及cscan幾種調度算法中，都有可能出現(xiàn)磁臂留在某處不動的情況，即出現(xiàn)磁盤粘著現(xiàn)象。當n取值很大時，會使n步掃描的性能接近于scan算法的性能；當n=1時，n步掃描算法退化為fcfs算法。此外，需要了解的是n步scan算法的簡化算法是fscan算法，即將磁盤請求隊列分成兩個子隊列的算法。2.2概要設計（流程圖）從文件中獲取進程請求磁道號放入cidaoi統(tǒng)計總個數(shù)count輸入當前磁道號now,子隊列個數(shù) n,移

14、動臂的移動方向d從cidaoi中取出前count/n組成一個子隊列，存入bi,最后一列將該子隊列為剩余磁道號，存入bin！=0? y n將磁道號從小到大排序arraym-1=0(array0=now輸出磁盤調度序列arrayjim磁頭移動總距離sum=arrayi-now確定當前磁道在已排的序列中的位置switch(d)case 0:移動臂向磁道號減小方向訪問case 1:移動臂向磁道號增加方向訪問訪問輸出磁盤調度序列輸出磁盤調度序列輸出子隊列尋道總道數(shù)sum輸出子隊列平均尋道長度avg=sum/(m)輸出該算法下總的尋道數(shù)s輸出該算法下平均尋道數(shù)四、詳細設計#includestdio.h#i

15、ncludestdlib.h/#includeiostream.h#define maxsize 100 /定義最大數(shù)組域int now,s;/最短尋道時間優(yōu)先調度算法void sstf(int array,int m)int temp;int k=1;int now,l,r; /當前磁道號now；找出的當前磁道左側的磁道l，右側的磁道rint i,j,sum=0;int avg;for(i=0;im;i+)for(j=i+1;jarrayj)/兩磁道號之間比較temp=arrayi;arrayi=arrayj;arrayj=temp;for( i=0;im;i+)/輸出排序后的磁道號數(shù)組pr

16、intf(%d ,arrayi);printf(n 請輸入當前的磁道號：);scanf(%d,&now);printf(n sstf調度結果: );if(arraym-1=0;i-)/將數(shù)組磁道號從大到小輸出printf(%d ,arrayi);sum=now-array0;/計算移動距離else if(array0=now)/判斷整個數(shù)組里的數(shù)是否都大于當前磁道號 for(i=0;im;i+)/將磁道號從小到大輸出printf(%d ,arrayi);sum=arraym-1-now;/計算移動距離elsewhile(arrayk=0)&(rm)if(now-arrayl)=(arrayr-

17、now)/判斷最短距離 printf(%d ,arrayl);sum+=now-arrayl;/計算移動距離now=arrayl;l=l-1;else printf(%d ,arrayr);sum+=arrayr-now;/計算移動距離now=arrayr;r=r+1;if(l=-1) for(j=r;j=0;j-) printf(%d ,arrayj);sum+=arraym-1-array0;/計算移動距離avg=sum/m;printf(n 移動的總道數(shù)： %d n,sum);printf( 平均尋道長度： %d n,avg);/掃描調度方法void scan(int array,int

18、 m,int d)/先要給出當前磁道號和移動臂的移動方向int k=1;int l,r;int i,j,sum=0;int avg;int temp; /用于排序的臨時參數(shù)int q; for(i=0;im;i+)for(j=i+1;jarrayj)/對磁道號進行從小到大排列temp=arrayi;arrayi=arrayj;arrayj=temp;if(arraym-1=0;i-)printf(%d ,arrayi);/將數(shù)組磁道號從大到小輸出 q=arrayi;sum=now-q;/計算移動距離s=s+sum;now=q;else if(array0=now)/判斷整個數(shù)組里的數(shù)是否都大于

19、當前磁道號 printf(n scan調度結果: );for(i=0;im;i+)printf(%d ,arrayi);/將磁道號從小到大輸出 q=arrayi;sum=arraym-1-now;/計算移動距離 s=s+sum;now=q;elsewhile(arrayk=0;j-)printf(%d ,arrayj); q=arrayj;for(j=r;jm;j+)printf(%d ,arrayj); q=arrayj;sum=now-2*array0+arraym-1;/計算移動距離 s=s+sum;now=q;/磁道號減小方向elsefor(j=r;j=0;j-)printf(%d ,

20、arrayj); q=arrayj;sum=-now-array0+2*arraym-1;/計算移動距離 s=s+sum;now=q;/磁道號增加方向avg=sum/m;printf(n 該子隊列移動的總道數(shù)： %d n,sum);printf( 該子隊列平均尋道長度： %d n,avg);void nstepscan(int array,int m) int sn,n,d; /sn標記每一子隊列的長度，n記錄子隊列個數(shù)，now標記當前磁道號int b100,c100; /b100儲存前幾個子隊列，c100儲存最后一個子隊列int i=0,j=0,k=0,n=1;int ave; printf

21、(請輸入當前磁道號：n);scanf(%d,&now);printf(請輸入子隊列的個數(shù)：n);scanf(%d,&n);while(nm)printf(超出范圍，文件中的磁道數(shù)不夠分組，請重新輸入：n); scanf(%d,&n); printf(請輸入當前移動臂的移動的方向 (1 磁道號增加方向，0磁道號減小方向) : ); scanf(%d,&d);sn=m/n;while(n!=1) /當不是最后一個子隊列時，循環(huán)進行scan調度j=0;for(i=k;isn*n;i=k,j+)bj=arrayi;k=k+1; printf(n第%d個隊列的排序結果為：n,n); scan(b,sn,

22、d);n=n-1;n=n+1;if(n=1) /最后一個子隊列時進行scan調度for(i=k,j=0;im;i+,j+)cj=arrayi; printf(n最后一個隊列的調度結果為：n); scan(c,m-k,d);ave=s/m;printf(n該調度總的結果為：n);printf(n 移動的總道數(shù)： %d n,s);printf( 平均尋道長度： %d n,ave); / 操作界面int main()int c;int c=1;file *fp;/定義指針文件int cidaomaxsize;/定義磁道號數(shù)組int i=0,count;fp=fopen(cidao.txt,r+);/

23、讀取cidao.txt文件if(fp=null)/判斷文件是否存在printf(n 請 先 設 置 磁 道! n);exit(0);while(!feof(fp)/如果磁道文件存在fscanf(fp,%d,&cidaoi);/調入磁道號i+;count=i;printf(n -n);printf( 10-11年度os課程設計-磁盤調度算法模擬);printf(n -n); printf(n 磁道讀取結果：n);for(i=0;icount;i+)printf(%5d,cidaoi);/輸出讀取的磁道的磁道號printf(n );while(c=1) printf( n);printf( 操作系

24、統(tǒng)課程設計 n); printf( 磁盤調度算法 n ); printf( n); printf( n); printf( n); printf( 1.最短尋道時間優(yōu)先算法(sstf) n); printf( n); printf( n); printf( 2.n步掃描算法(nstepscan) n); printf( n); printf( n); printf( n); printf( n); printf( 請輸入你的選擇的算法(輸入0離開) n); printf( n); scanf(%d,&c); if(c=0) exit(0); printf( );while(c!=1&c!=2)

25、printf(輸入數(shù)據超出范圍，請重新輸入您想進行的調度算法：n); scanf(%d,&c);switch(c) case 1: sstf(cidao,count);/最短尋道時間優(yōu)先算法 printf(n); break; case 2:i=0; fp=fopen(cidao.txt,r+);/讀取cidao.txt文件 if(fp=null)/判斷文件是否存在printf(n 請 先 設 置 磁 道! n); exit(0); while(!feof(fp)/如果磁道文件存在 fscanf(fp,%d,&cidaoi);/調入磁道號 i+; count=i; printf(n 磁道讀取結果：n); for(i=0;icount;i+) printf(%5d,cidaoi);/輸出讀取的磁道的磁道號 printf(n );nstepscan(cidao,count);/n步掃描算法 printf(n); break;printf( 是否繼續(xù)(按0結束,按1繼續(xù))?);scanf(%5d,&c);return(0);五、調試運行結果1. 調試運行后的開始界面如下：2、調試運行各個算法結果如下:21運行最短尋道時間優(yōu)先（sstf）算法調度程序結果如下：22調試運行nstepscan調度程序結果如下：2.2.1移動臂的移動