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

1、目 錄1 課程設(shè)計(jì)目的及要求12 相關(guān)知識(shí)13 題目分析24 概要設(shè)計(jì)2 4.1 先來先服務(wù)（FCFS）的設(shè)計(jì)思想.2 4.2 最短尋道時(shí)間優(yōu)先調(diào)度（SSTF）的設(shè)計(jì)思想.2 4.3 掃描算法（SCAN）的設(shè)計(jì)思想2 4.4 循環(huán)掃描（CSCAN）的設(shè)計(jì)思想.25 代碼及流程3 5.1 流程圖.3 5.2 源代碼.86 運(yùn)行結(jié)果167 設(shè)計(jì)心得19參考文獻(xiàn)191 課程設(shè)計(jì)目的及要求設(shè)計(jì)目的：加深對(duì)操作系統(tǒng)原理的進(jìn)一步認(rèn)識(shí)，加強(qiáng)實(shí)踐動(dòng)手能力和程序開發(fā)能力的培養(yǎng)，提高分析問題解決問題的能力，培養(yǎng)合作精神，以鞏固和加深磁盤調(diào)度的概念。操作系統(tǒng)是一門工程性很強(qiáng)的課程，它不僅要求學(xué)生掌握操作系統(tǒng)的工作原

2、理和理論知識(shí)，也要求學(xué)生的實(shí)際動(dòng)手能力，以加深對(duì)所學(xué)習(xí)內(nèi)容的理解，使學(xué)生熟練地掌握計(jì)算機(jī)的操作方法，使用各種軟件工具，加強(qiáng)對(duì)課程內(nèi)容的理解。這次課程設(shè)計(jì)，就是通過模擬磁臂調(diào)度來加深對(duì)操作系統(tǒng)中磁臂調(diào)度概念的理解。使學(xué)生熟悉磁盤管理系統(tǒng)的設(shè)計(jì)方法；加深對(duì)所學(xué)各種磁盤調(diào)度算法的了解及其算法的特點(diǎn)。設(shè)計(jì)要求：編程序?qū)崿F(xiàn)下述磁盤調(diào)度算法,并求出每種算法的平均尋道長(zhǎng)度；要求設(shè)計(jì)主界面可以靈活選擇某算法，且以下算法都要實(shí)現(xiàn)1、先來先服務(wù)算法（FCFS）2、最短尋道時(shí)間優(yōu)先算法（SSTF）3、掃描算法（SCAN）4、循環(huán)掃描算法（CSCAN）2 相關(guān)知識(shí)數(shù)據(jù)結(jié)構(gòu)：數(shù)組now:當(dāng)前磁道號(hào);array:放置磁道

3、號(hào)的數(shù)組;void FCFS(int array,int m )先來先服務(wù)算法(FCFS)void SSTF(int array,int m)最短尋道時(shí)間優(yōu)先算法(SSTF)void SCAN(int array,int m) 掃描算法(SCAN)void CSCAN(int array,int m)循環(huán)掃描算法(CSCAN) 磁盤調(diào)度：當(dāng)有多個(gè)進(jìn)程都請(qǐng)求訪問磁盤時(shí)，采用一種適當(dāng)?shù)尿?qū)動(dòng)調(diào)度算法，使各進(jìn)程對(duì)磁盤的平均訪問（主要是尋道）時(shí)間最小。目前常用的磁盤調(diào)度算法有：1）閑來先服務(wù)2）最短尋道時(shí)間優(yōu)先3）掃描算法4）循環(huán)掃描算法等3 題目分析選擇一個(gè)自己熟悉的計(jì)算機(jī)系統(tǒng)和程序設(shè)計(jì)語言模擬操作系

4、統(tǒng)基本功能的設(shè)計(jì)方法及其實(shí)現(xiàn)過程 完成各分項(xiàng)功能。在算法的實(shí)現(xiàn)過程中，要求可決定變量應(yīng)是動(dòng)態(tài)可變的；同時(shí)模塊應(yīng)該有一個(gè)合理的輸出結(jié)果。具體可參照實(shí)驗(yàn)的程序模擬 .各功能程序要求自行編寫程序?qū)崿F(xiàn)，不得調(diào)用現(xiàn)有操作系統(tǒng)提供的模塊或功能函數(shù)。磁盤調(diào)度程序模擬。先來先服務(wù)調(diào)度算法. 最短尋道時(shí)間優(yōu)先調(diào)度，循環(huán)（SCAN）調(diào)度算法。程序設(shè)計(jì)語言自選，最終以軟件（含源代碼以及執(zhí)行程序）和設(shè)計(jì)報(bào)告的形式提交課程設(shè)計(jì)結(jié)果.。磁盤調(diào)度讓有限的資源發(fā)揮更大的作用。在多道程序設(shè)計(jì)的計(jì)算機(jī)系統(tǒng)中，各個(gè)進(jìn)程可能會(huì)不斷提出不同的對(duì)磁盤進(jìn)行讀/寫操作的請(qǐng)求。由于有時(shí)候這些進(jìn)程的發(fā)送請(qǐng)求的速度比磁盤響應(yīng)的還要快，因此我們有必

5、要為每個(gè)磁盤設(shè)備建立一個(gè)等待隊(duì)列。4 概要設(shè)計(jì)1.先來先服務(wù)（FCFS）的設(shè)計(jì)思想即先來的請(qǐng)求先被響應(yīng)。FCFS策略看起來似乎是相當(dāng)公平的，但是當(dāng)請(qǐng)求的頻率過高的時(shí)候FCFS策略的響應(yīng)時(shí)間就會(huì)大大延長(zhǎng)。FCFS策略為我們建立起一個(gè)隨機(jī)訪問機(jī)制的模型，但是假如用這個(gè)策略反復(fù)響應(yīng)從里到外的請(qǐng)求，那么將會(huì)消耗大量的時(shí)間。為了盡量降低尋道時(shí)間，看來我們需要對(duì)等待著的請(qǐng)求進(jìn)行適當(dāng)?shù)呐判?，而不是?jiǎn)單的使用FCFS策略。這個(gè)過程就叫做磁盤調(diào)度管理。有時(shí)候fcfs也被看作是最簡(jiǎn)單的磁盤調(diào)度算法。2.最短尋道時(shí)間優(yōu)先調(diào)度（SSTF）的設(shè)計(jì)思想最短時(shí)間優(yōu)先算法選擇這樣的進(jìn)程。要求訪問的磁道，與當(dāng)前磁頭所在的磁道距

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

7、：當(dāng)磁頭剛從里向外移動(dòng)而越過了某一磁道時(shí)，恰好又有一進(jìn)程請(qǐng)求訪問此磁道，這時(shí)，該里程就必須等待，為了減少這種延遲，CSCAN算法規(guī)定磁頭單向移動(dòng)，而本實(shí)驗(yàn)過程中我們所設(shè)計(jì)的是磁頭從里向外移動(dòng)，而從外向里移動(dòng)時(shí)只須改方向而已，本實(shí)驗(yàn)未實(shí)現(xiàn)。但本實(shí)驗(yàn)已完全能演示循環(huán)掃描的全過程。5 代碼及流程1.先來先服務(wù)（FCFS）圖 11 FCFS的流程圖2.最短尋道時(shí)間優(yōu)先調(diào)度（SSTF） 圖12 SSTF的流程圖3.掃描算法（SCAN） 圖13 SCAN的流程圖 4.循環(huán)掃描（CSCAN）圖14 CSCAN的流程圖 圖15 主函數(shù)的流程圖源代碼：#includestdio.h#includestdlib.

8、h/#includeiostream.h#define maxsize 100 /定義最大數(shù)組域/先來先服務(wù)調(diào)度算法void FCFS(int array,int m)int sum=0,j,i;int avg;printf(n FCFS調(diào)度結(jié)果: );for(i=0;im;i+)/輸出FCFS磁盤調(diào)度結(jié)果printf(%d ,arrayi);for(i=0,j=1;jm;i+,j+)sum+=abs(arrayj-arrayi);/累計(jì)總的移動(dòng)距離avg=sum/(m-1);/計(jì)算平均尋道長(zhǎng)度printf(n 移動(dòng)的總道數(shù)： %d n,sum);printf( 平均尋道長(zhǎng)度： %d n,av

9、g);/最短尋道時(shí)間優(yōu)先調(diào)度算法void SSTF(int array,int m)int temp;int k=1;int now,l,r;int 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ù)組printf(%d ,arrayi);printf(n 請(qǐng)輸入當(dāng)前的磁道號(hào)：);scanf(%d,&now);printf(n SSTF調(diào)度結(jié)果: );if(arraym-1=0;i-)/將數(shù)組磁道號(hào)從

10、大到小輸出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-now)/判斷最短距離 printf(%d ,arrayl);sum+=now-arrayl;/計(jì)算移動(dòng)距離now=arrayl;l=l-1;else printf(%d ,arrayr);sum+

11、=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( 平均尋道長(zhǎng)度： %d n,avg);/掃描算法void SCAN(int array,int m)/先要給出當(dāng)前磁道號(hào)和移動(dòng)臂的移動(dòng)方向int temp;int k=1;int now,l,r,d;int i,j,sum=0;int avg;for(i=0;im;i+)for(j=i+1;ja

12、rrayj)/對(duì)磁道號(hào)進(jìn)行從小到大排列temp=arrayi;arrayi=arrayj;arrayj=temp;for( i=0;im;i+)printf(%d ,arrayi);/輸出排序后的磁道號(hào)數(shù)組printf(n 請(qǐng)輸入當(dāng)前的磁道號(hào)：);scanf(%d,&now);if(arraym-1=0;i-)printf(%d ,arrayi);/將數(shù)組磁道號(hào)從大到小輸出sum=now-array0;/計(jì)算移動(dòng)距離else if(array0=now)/判斷整個(gè)數(shù)組里的數(shù)是否都大于當(dāng)前磁道號(hào) printf(n SCAN調(diào)度結(jié)果: );for(i=0;im;i+)printf(%d ,arra

13、yi);/將磁道號(hào)從小到大輸出sum=arraym-1-now;/計(jì)算移動(dòng)距離elsewhile(arrayk=0;j-)printf(%d ,arrayj);for(j=r;jm;j+)printf(%d ,arrayj);sum=now-2*array0+arraym-1;/計(jì)算移動(dòng)距離/磁道號(hào)減小方向elsefor(j=r;j=0;j-)printf(%d ,arrayj);sum=-now-array0+2*arraym-1;/計(jì)算移動(dòng)距離/磁道號(hào)增加方向avg=sum/m;printf(n 移動(dòng)的總道數(shù)： %d n,sum);printf( 平均尋道長(zhǎng)度： %d n,avg);/循環(huán)

14、掃描算法void CSCAN(int array,int m)int temp;int k=1;int now,l,r,d;int i,j,sum=0;int avg;for(i=0;im;i+)for(j=i+1;jarrayj)/對(duì)磁道號(hào)進(jìn)行從小到大排列temp=arrayi;arrayi=arrayj;arrayj=temp;for( i=0;im;i+)printf(%d ,arrayi);/輸出排序后的磁道號(hào)數(shù)組printf(n 請(qǐng)輸入當(dāng)前的磁道號(hào)：);scanf(%d,&now);if(arraym-1=now)/判斷整個(gè)數(shù)組里的數(shù)是否都小于當(dāng)前磁道號(hào) printf(n CSCAN

15、調(diào)度結(jié)果: );for(i=0;i=now)/判斷整個(gè)數(shù)組里的數(shù)是否都大于當(dāng)前磁道號(hào) printf(n CSCAN調(diào)度結(jié)果: );for(i=0;im;i+) printf(%d ,arrayi);/將磁道號(hào)從小到大輸出sum=arraym-1-now;/計(jì)算移動(dòng)距離elsewhile(arrayk=0;j-)printf(%d ,arrayj);for(j=m-1;j=r;j-)printf(%d ,arrayj);sum=2*(arraym-1-array0)-arrayr+now;/計(jì)算移動(dòng)距離/磁道號(hào)減小方向elsefor(j=r;jm;j+)printf(%d ,arrayj);fo

16、r(j=0;jr;j+)printf(%d ,arrayj);sum=2*(arraym-1-array0)+arrayr-1-now;/計(jì)算移動(dòng)距離/磁道號(hào)增加方向avg=sum/m;printf(n 移動(dòng)的總道數(shù)： %d n,sum);printf( 平均尋道長(zhǎng)度： %d n,avg);/ 操作界面int main()int c;FILE *fp;/定義指針文件int cidaomaxsize;/定義磁道號(hào)數(shù)組int i=0,count;fp=fopen(cidao.txt,r+);/讀取cidao.txt文件if(fp=NULL)/判斷文件是否存在printf(n 請(qǐng) 先 設(shè) 置 磁 道

17、! n);exit(0);while(!feof(fp)/如果磁道文件存在fscanf(fp,%d,&cidaoi);/調(diào)入磁道號(hào)i+;count=i-1;printf(n -n);printf( 10-11年度OS課程設(shè)計(jì)-磁盤調(diào)度算法系統(tǒng)n);printf( 計(jì)算機(jī)科學(xué)與技術(shù)二班n);printf( 姓名：宋思揚(yáng)n);printf( 學(xué)號(hào)：n);printf( 電話：*n);printf( 2010年12月29日n);printf(n -n);printf(n 磁道讀取結(jié)果：n);for(i=0;i5)break;switch(c)/算法選擇case 1:FCFS(cidao,count)

18、;/先來先服務(wù)算法printf(n);break;case 2:SSTF(cidao,count);/最短尋道時(shí)間優(yōu)先算法printf(n);break;case 3:SCAN(cidao,count);/掃描算法printf(n);break;case 4:CSCAN(cidao,count);/循環(huán)掃描算法printf(n);break;case 5:exit(0);return 0;6 運(yùn)行結(jié)果 圖21 運(yùn)行界面 圖22 運(yùn)行FCFS的界面 圖23 運(yùn)行SSTF的界面 圖24 運(yùn)行SCAN的界面 圖25 運(yùn)行SCAN的界面 圖26 運(yùn)行CSCAN的界面 圖27 運(yùn)行CSCAN的界面運(yùn)行結(jié)果： 四種磁盤調(diào)度運(yùn)行結(jié)果正確，與預(yù)期的相符。7 設(shè)計(jì)心得此次操作系統(tǒng)的課程設(shè)計(jì)，從理論到實(shí)踐，在兩個(gè)星期的日子里，可以說是苦多于甜，但是可以學(xué)到很多很多的的東西，同時(shí)不僅可以鞏固了以前所學(xué)過的知識(shí)，而且學(xué)到了