課程設(shè)計(jì)-磁盤調(diào)度算法及代碼的實(shí)現(xiàn)講解

1、x EAST CHINA INSTITUTE OF TECHNOLOGY課程設(shè)計(jì)報(bào)告計(jì)算機(jī)操作系統(tǒng)課程設(shè)計(jì)題目：磁盤調(diào)度算法學(xué)生姓名：專 業(yè)：班 級(jí)：學(xué) 號(hào)：指導(dǎo)教師：2014年01月10日 TOC o 1-5 h z HYPERLINK l bookmark36 o Current Document 需求分析01 HYPERLINK l bookmark40 o Current Document 總體設(shè)計(jì)及分類簡(jiǎn)介 011）先來(lái)先服務(wù)（FCFS）算法012）最短尋道時(shí)間優(yōu)先（SSTF）算法013）掃描調(diào)度（SCAN）算法014）循環(huán)掃描（C-SCAN）算法01課程設(shè)計(jì)目的01 HYPERLI

2、NK l bookmark51 o Current Document 課程設(shè)計(jì)要求02詳細(xì)設(shè)計(jì)及算法流程圖021）總流程圖022）先來(lái)先服務(wù)（FCFS）算法流程圖033）最短尋道時(shí)間優(yōu)先（SSTF）算法流程圖044）掃描調(diào)度（SCAN）算法流程圖055）循環(huán)掃描（C-SCAN）算法流程圖06 HYPERLINK l bookmark61 o Current Document 課程設(shè)計(jì)具體步驟071）定義函數(shù)部分主要代碼072）先來(lái)先服務(wù)（FCFS）算法部分主要代碼073）最短尋道時(shí)間優(yōu)先（SSTF）算法部分主要代碼074）掃描調(diào)度（SCAN）算法部分主要代碼095）循環(huán)掃描（C-SCAN）算法

3、部分主要代碼09課程設(shè)計(jì)結(jié)果顯示101）先來(lái)先服務(wù)（FCFS）算法測(cè)試結(jié)果102）最短尋道時(shí)間優(yōu)先（SSTF）算法測(cè)試結(jié)果113）掃描調(diào)度（SCAN）算法測(cè)試結(jié)果124）循環(huán)掃描（C-SCAN）算法測(cè)試結(jié)果13 HYPERLINK l bookmark74 o Current Document 課程設(shè)計(jì)總結(jié)14 HYPERLINK l bookmark78 o Current Document 9心得體會(huì)15 HYPERLINK l bookmark81 o Current Document 10.參考資料15磁盤調(diào)度算法需求分析編譯程序運(yùn)用磁盤的四種調(diào)度算法實(shí)現(xiàn)對(duì)磁盤的調(diào)度，四種算法分別為先

4、來(lái) 先服務(wù)（FCFS）算法，最短尋道時(shí)間優(yōu)先（SSTF）算法，掃描調(diào)度（SCAN）算法， 循環(huán)掃描（C-SCAN）算法?？傮w設(shè)計(jì)及分類簡(jiǎn)介磁盤調(diào)度中常用的有四種算法，功能分別如下：先來(lái)先服務(wù)（FCFS）算法。即先來(lái)的請(qǐng)求先被響應(yīng)。FCFS策略看起來(lái)似乎 是相當(dāng)公平的，但是當(dāng)請(qǐng)求的頻率過(guò)高的時(shí)候FCFS策略的響應(yīng)時(shí)間就會(huì)大大 延長(zhǎng)。FCFS策略為我們建立起一個(gè)隨機(jī)訪問(wèn)機(jī)制的模型，但是假如用這個(gè)策略 反復(fù)響應(yīng)從里到外的請(qǐng)求，那么將會(huì)消耗大量的時(shí)間。為了盡量降低尋道時(shí)間， 看來(lái)我們需要對(duì)等待著的請(qǐng)求進(jìn)行適當(dāng)?shù)呐判?，而不是?jiǎn)單的使用FCFS策略。 這個(gè)過(guò)程就叫做磁盤調(diào)度管理。有時(shí)候FCFS也被看作是最

5、簡(jiǎn)單的磁盤調(diào)度算法。最短尋道時(shí)間優(yōu)先（SSTF）算法。要求訪問(wèn)的磁道，與當(dāng)前磁頭所在的磁 道距離最近，以使每次的尋道時(shí)間最短。掃描調(diào)度（SCAN）算法。該算法不僅考慮到欲訪問(wèn)的磁道與當(dāng)前磁道間的距 離，更優(yōu)先考慮的是磁頭當(dāng)前的移動(dòng)方向。例如，當(dāng)磁頭正在自里向外移動(dòng)時(shí)， SCAN算法所考慮的下一個(gè)訪問(wèn)對(duì)象，應(yīng)是其欲訪問(wèn)的磁道，既在當(dāng)前磁道之外， 又是距離最近的。這樣自里向外的訪問(wèn)，直至再無(wú)更外的磁道需要訪問(wèn)時(shí)，才將 磁道換向自外向里移動(dòng)。這時(shí)，同樣也是每次選擇這樣的進(jìn)程來(lái)調(diào)度，也就是要 訪問(wèn)的當(dāng)前位置內(nèi)距離最近者，這樣，磁頭又逐步地從外向里移動(dòng)，直至再無(wú)更 里面的磁道要訪問(wèn)，從而避免了出現(xiàn)“饑餓

6、”現(xiàn)像。循環(huán)掃描（C-SCAN）算法。當(dāng)磁頭剛從里向外移動(dòng)而越過(guò)了某一磁道時(shí)，恰 好又有一進(jìn)程請(qǐng)求訪問(wèn)此磁道，這時(shí)，該里程就必須等待，為了減少這種延遲， CSCAN算法規(guī)定磁頭單向移動(dòng)，而本實(shí)驗(yàn)過(guò)程中我們所設(shè)計(jì)的是磁頭從里向外移 動(dòng)，而從外向里移動(dòng)時(shí)只須改方向而已，本實(shí)驗(yàn)未實(shí)現(xiàn)。但本實(shí)驗(yàn)已完全能演示 循環(huán)掃描的全過(guò)程。課程設(shè)計(jì)目的熟悉并掌握磁盤管理系統(tǒng)的設(shè)計(jì)方法，加深對(duì)所學(xué)各種磁盤調(diào)度算法及其算法的特點(diǎn)的了解。掌握磁盤調(diào)度的基本概念，比較各種磁盤調(diào)度算法的優(yōu)劣課程設(shè)計(jì)要求從課程設(shè)計(jì)的目的出發(fā)，通過(guò)設(shè)計(jì)工作的各個(gè)環(huán)節(jié)，達(dá)到以下設(shè)計(jì)要求:對(duì)系統(tǒng)進(jìn)行功能模塊分析、控制模塊分析正確；系統(tǒng)設(shè)計(jì)要實(shí)用；編

7、程簡(jiǎn)練，可用，功能全面,具有較好的健壯性；說(shuō)明書、流程圖要清楚。詳細(xì)設(shè)計(jì)及算法流程圖1.總流程圖2.先來(lái)先服務(wù)（FCFS）算法流程圖最短尋道時(shí)間優(yōu)先（SSTF）算法流程圖while(ak =0 )&(rn)while(ak =0 )&(rn)for(i=0;in;i+)coutai”;sum=an-1-n ow;移動(dòng)的 總道數(shù)*結(jié)束課程設(shè)計(jì)具體步驟定義函數(shù)部分主要代碼#include#includeusing namespace std;void FCFS(int a,int n);void SSTF(int a,int n);void SCAN(int a,int n);void CSCAN

8、(int a,int n);先來(lái)先服務(wù)(FCFS)算法部分主要代碼void FCFS(int a,int n)(int sum=0,j,i,first=0,now;coutnow;/確定當(dāng)前磁頭所在位置cout磁盤調(diào)度順序?yàn)椋篹ndl;for( i=0;in;i+)(coutai;for(i=0,j=1;jn;i+,j+)(first+=abs(aj-ai);sum+=first+abs(now-a0);coutendl;cout移動(dòng)的總磁道數(shù)為：sumendl;最短尋道時(shí)間優(yōu)先(SSTF)算法部分主要代碼for(i=0;in;i+)for(j=i+1;jaj)(temp=ai;ai=aj;a

9、j=temp;if(an-1=0;i-)coutai;sum二now-a0;if(l=-1)/磁頭位置里側(cè)的磁道已訪問(wèn)完(for(j=r;jn;j+)/訪問(wèn)磁頭位置外側(cè)的磁道(coutaj-1;j-) 訪問(wèn)磁頭位置里側(cè)的磁道(sum+=an-1-a0;coutendl;cout移動(dòng)的總道數(shù)為:sumendl;掃描調(diào)度(SCAN)算法部分主要代碼void SCAN(int a,int n)(int temp;int k=1;int now,l,r;int i,j,sum=0;for(i=0;in;i+)if(an-1=0;i-)coutai;sum二now-a0;循環(huán)掃描(C-SCAN)算法部分

10、主要代碼void CSCAN(int a,int n)(int temp;int now,l,r;int i,j,sum=0;int k=1;for(i=0;in;i+)if(an-1=now)/磁頭位置大于最外圍欲訪問(wèn)磁道(for(i=0;in;i+)coutai;sum二now-2*a0+an-1;課程設(shè)計(jì)結(jié)果顯示1.先來(lái)先服務(wù)(FCFS)算法測(cè)試結(jié)果2.最短尋道時(shí)間優(yōu)先（SSTF）算法測(cè)試結(jié)果3.掃描調(diào)度（SCAN）算法測(cè)試結(jié)果4.循環(huán)掃描（C-SCAN）算法測(cè)試結(jié)果課程設(shè)計(jì)總結(jié)計(jì)算機(jī)磁盤是一種很重要也很常用的外部設(shè)備，其分配也有一定的分配策 略。在操作系統(tǒng)中，作業(yè)對(duì)磁盤的請(qǐng)求常常要排隊(duì)

11、，由此需要一些高效率的磁盤 分配策略算法。（1）先來(lái)先服務(wù)算法為一種最簡(jiǎn)單的磁盤調(diào)度算法，它直接根據(jù) 作業(yè)請(qǐng)求磁盤的先后順序?qū)Υ疟P進(jìn)行尋訪，公平、簡(jiǎn)單，每個(gè)作業(yè)的磁盤請(qǐng)求都 可以得到處理，不會(huì)出現(xiàn)某個(gè)作業(yè)的請(qǐng)求長(zhǎng)期得不到滿足的情況，但未對(duì)尋道方 案進(jìn)行優(yōu)化；（2）最短尋道時(shí)間優(yōu)先算法優(yōu)先選擇距離當(dāng)前磁頭位置最近的作業(yè) 磁道請(qǐng)求，可以使得每次尋道時(shí)所用的時(shí)間都最短，但不能保證平均周轉(zhuǎn)時(shí)間及 帶權(quán)周轉(zhuǎn)時(shí)間最短；（3）電梯算法同時(shí)考慮下一個(gè)作業(yè)磁道請(qǐng)求與當(dāng)前磁頭位置 的距離和當(dāng)前磁頭移動(dòng)方向先選擇當(dāng)前磁頭之外距離其最近的磁道進(jìn)行訪問(wèn)，直 到再無(wú)更外的磁道請(qǐng)求，再將磁臂換向，訪問(wèn)磁頭內(nèi)側(cè)距離當(dāng)前磁頭位

12、置最近的 作業(yè)磁道請(qǐng)求，避免了饑餓現(xiàn)象的出現(xiàn)，每個(gè)作業(yè)的磁盤請(qǐng)求都可以得到處理， 且使每次尋道時(shí)間相對(duì)較短；（4）N_SCAN算法同時(shí)考慮下一個(gè)作業(yè)磁道請(qǐng)求與 當(dāng)前磁頭位置的距離和當(dāng)前磁頭移動(dòng)方向，但每次磁臂調(diào)轉(zhuǎn)方向時(shí)，將同時(shí)處理 在磁頭向一側(cè)移動(dòng)過(guò)程當(dāng)中輸入的作業(yè)請(qǐng)求，先選擇當(dāng)前磁頭之外距離其最近的 磁道進(jìn)行訪問(wèn)，直到再無(wú)更外的磁道請(qǐng)求，接下來(lái)一并考慮在磁頭向外側(cè)移動(dòng)過(guò) 程當(dāng)中輸入的作業(yè)請(qǐng)求與磁頭內(nèi)側(cè)未被處理的作業(yè)磁道請(qǐng)求，此算法對(duì)中間磁道 請(qǐng)求比較有利。總之，各種算法都有其長(zhǎng)處，也各有不足，需要在實(shí)際應(yīng)用中權(quán) 衡利弊，擇優(yōu)使用才能達(dá)到最好的效果。九心得體會(huì)在這幾天的課程設(shè)計(jì)中，由于之前做過(guò)

13、相似的實(shí)驗(yàn)，所以在一開(kāi)的實(shí)驗(yàn)設(shè)計(jì) 流程圖時(shí)還是很快就完成了，不過(guò)在接下來(lái)的編寫代碼的階段里，出現(xiàn)很大的問(wèn) 題，花費(fèi)了很多的時(shí)間。好在有老師的耐心細(xì)心的指導(dǎo)，一步一步的驗(yàn)證，一點(diǎn) 一點(diǎn)的改正。每一次的運(yùn)行看到錯(cuò)誤都在慢慢的減少，正確的設(shè)計(jì)結(jié)果也在不斷 的靠近，最終取得了成功。由于自己的知識(shí)和能力還不到位，在課程設(shè)計(jì)時(shí)間里 經(jīng)歷了很多困難和挑戰(zhàn)，但我認(rèn)為，在這過(guò)程中的每一次的錯(cuò)誤和故障，都使我 收獲頗豐，使我成長(zhǎng)了很多。當(dāng)然，這個(gè)磁盤調(diào)度系統(tǒng)的設(shè)計(jì)遠(yuǎn)非完美，還有很多地方可以改進(jìn)，例如界 面可以更加友好，資源可以更加節(jié)約，算法也還有優(yōu)化的余地，但是時(shí)間有限， 經(jīng)歷也有限，在課程設(shè)計(jì)時(shí)間允許的范圍內(nèi)只

14、能做到這樣，我會(huì)在課余時(shí)間自行 完善該磁盤調(diào)度算法程序。每一次的課程設(shè)計(jì)都是自己對(duì)所學(xué)知識(shí)的強(qiáng)化，是一次難得的動(dòng)手機(jī)會(huì)。在 課程設(shè)計(jì)的每一個(gè)步驟的執(zhí)行中，都要認(rèn)真的反復(fù)的去做，因?yàn)橐粋€(gè)小小的錯(cuò)誤 都會(huì)導(dǎo)致課程設(shè)計(jì)結(jié)果發(fā)生巨大的偏差。完成一個(gè)成功的設(shè)計(jì)，會(huì)讓自己學(xué)會(huì)很 多很多的東西，并且能夠很清楚的看到自己的不足，查補(bǔ)缺漏，繼續(xù)學(xué)習(xí)。通過(guò) 自己的動(dòng)手動(dòng)腦，既增加了知識(shí)，又給了我專業(yè)知識(shí)以及專業(yè)技能上的提升，對(duì) 提高自己的思維能力和操作能力有很大的幫助。同時(shí)我也會(huì)更加努力，認(rèn)真學(xué)習(xí)， 爭(zhēng)取在以后的課程中做得更好！十.參考資料計(jì)算機(jī)操作系統(tǒng)清華大學(xué)出版社計(jì)算機(jī)操作系統(tǒng)實(shí)驗(yàn)指導(dǎo)清華大學(xué)出版社附錄:#i

15、nclude#include using namespace std;void FCFS(int a,int n);void SSTF(int a,int n);void SCAN(int a,int n);void CSCAN(int a,int n);int main()磁道的個(gè)數(shù)功能號(hào)磁道的個(gè)數(shù)功能號(hào)int s;cout請(qǐng)輸入當(dāng)前磁道的個(gè)數(shù)，按Enter鍵顯示生成的隨機(jī)磁道號(hào)：n;int *a=new intn;cout生成的隨機(jī)磁道號(hào)為:srand(unsigned)time(NULL);for(int i=0;in;i+) ai=(rand()%100)+1;coutai;coute

16、ndl;while(1) coutendl; TOC o 1-5 h z cout|endl;磁盤調(diào)度算法功能列表|11磁盤調(diào)度算法功能列表|11、 先來(lái)先服務(wù)算法(FCFS)| vvendl;12、 最短尋道時(shí)間算法(SSTF)| endl;13、 掃描算法(SCAN)| endl;14、循環(huán)掃描算法(CSCAN)|endl;cout|endl;cout|cout|endl;cout|cout|endl;cout|cout|endl;cout|endl;coutI endl;0、退出cout 0、退出cout1endl;coutendl;couts;if(s4)cout數(shù)據(jù)輸入有誤！請(qǐng)重新輸

17、入：endl;elseswitch(s) case 0: exit(0);break ;case 1:FCFS(a,n); break;case 2:SSTF(a, n);break;case 3:SCAN(a, n);break;case 4:CSCAN(a,n);break;return 0;/先來(lái)先服務(wù)調(diào)度算法(FCFS)void FCFS(int a,int n)int sum=0,j,i,first=0,now;coutnow;/確定當(dāng)前磁頭所在位置cout磁盤調(diào)度順序?yàn)椋篹ndl;for( i=0;in;i+)/按訪問(wèn)順序輸出磁道號(hào)coutai;計(jì)算sumfor(i=0,j=1;j

18、n;i+,j+)first+=abs(aj-ai);/外卜圍磁道與最里面磁道的距離sum+=first+abs(now-a0);coutendl;cout”移動(dòng)的總磁道數(shù)為：sumendl;最短尋道時(shí)間算法(SSTF)void SSTF(int a,int n) int temp;int k=1;int now,l,r;int i,j,sum=0;/將磁道號(hào)按遞增排序for(i=0;in;i+)for(j=i+1;jaj)temp=ai;ai=aj;aj=temp;cout按遞增順序排好的磁道顯示為：endl;for( i=0;in;i+)coutai ”;/輸出排好的磁道順序coutendl

19、;coutnow;/確定當(dāng)前磁頭所在位置cout磁盤調(diào)度順序?yàn)椋篹ndl;if(an-1=0;i-)coutai=now)/當(dāng)前磁頭位置小于最里欲訪問(wèn)磁道for(i=0;in;i+)coutai;sum=an-1-now;elsewhile(ak=0)&(rn)if(now-al)=(ar-now)/選擇離磁頭近的磁道coutal;sum+=now-al;now=al;l=l-1;elsecoutar;sum+=ar-now;now=ar;r=r+1;if(l=-1)/磁頭位置里側(cè)的磁道已訪問(wèn)完for(j=r;jn;j+)/訪問(wèn)磁頭位置外側(cè)的磁道coutaj-1;j-) 訪問(wèn)磁頭位置里側(cè)的磁道

20、coutaj;sum+=an-1-a0;coutendl;cout”移動(dòng)的總道數(shù)為:sumendl;掃描算法(SCAN)void SCAN(int a,int n)int temp;int k=1;int now,l,r;int i,j,sum=0;for(i=0;in;i+)/對(duì)訪問(wèn)磁道按由小到大順序排列輸出for(j=i+1;jaj)temp=ai;ai=aj;aj=temp;cout”按遞增順序排好的磁道為：endl;for( i=0;in;i+)coutai;coutendl;coutnow;以下算法確定磁道訪問(wèn)順序if(an-1=0;i-)coutai=now) /磁頭位置小于最里欲訪問(wèn)磁道for(i=0;in;i+)coutai;sum=an-1-now;else磁頭位置在最里側(cè)磁道與最外側(cè)磁道之間 int d;while(aknow)確定當(dāng)前磁道在已排的序列中的位置k+;l=k-1;/在磁頭位置的前一個(gè)欲訪問(wèn)磁道r=k;/磁頭欲訪問(wèn)磁道coutd;確定磁頭訪問(wèn)的方向cout=0;j-)coutaj;for(j=r;jn;j+)coutaj;sum=now-2*a0+an-1;if(d=1)/磁頭向外for(j=r;jn;j+)coutaj=0;j-)