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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19、當(dāng)前磁道號(hào) printf(n scan調(diào)度結(jié)果: );for(i=0;im;i+)printf(%d ,arrayi);/將磁道號(hào)從小到大輸出 q=arrayi;sum=arraym-1-now;/計(jì)算移動(dòng)距離 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;/計(jì)算移動(dòng)距離 s=s+sum;now=q;/磁道號(hào)減小方向elsefor(j=r;j=0;j-)printf(%d ,

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

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

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

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

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