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

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

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

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

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

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

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

7、：當磁頭剛從里向外移動而越過了某一磁道時，恰好又有一進程請求訪問此磁道，這時，該里程就必須等待，為了減少這種延遲，cscan算法規(guī)定磁頭單向移動，而本實驗過程中我們所設(shè)計的是磁頭從里向外移動，而從外向里移動時只須改方向而已，本實驗未實現(xiàn)。但本實驗已完全能演示循環(huán)掃描的全過程。5 代碼及流程1.先來先服務(wù)（fcfs）圖 11 fcfs的流程圖2.最短尋道時間優(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);/累計總的移動距離avg=sum/(m-1);/計算平均尋道長度printf(n 移動的總道數(shù)： %d n,sum);printf( 平均尋道長度： %d n,av

9、g);/最短尋道時間優(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)/兩磁道號之間比較temp=arrayi;arrayi=arrayj;arrayj=temp;for( i=0;im;i+)/輸出排序后的磁道號數(shù)組printf(%d ,arrayi);printf(n 請輸入當前的磁道號：);scanf(%d,&now);printf(n sstf調(diào)度結(jié)果: );if(arraym-1=0;i-)/將數(shù)組磁道號從

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

11、=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 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;ja

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

13、yi);/將磁道號從小到大輸出sum=arraym-1-now;/計算移動距離elsewhile(arrayk=0;j-)printf(%d ,arrayj);for(j=r;jm;j+)printf(%d ,arrayj);sum=now-2*array0+arraym-1;/計算移動距離/磁道號減小方向elsefor(j=r;j=0;j-)printf(%d ,arrayj);sum=-now-array0+2*arraym-1;/計算移動距離/磁道號增加方向avg=sum/m;printf(n 移動的總道數(shù)： %d n,sum);printf( 平均尋道長度： %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)/對磁道號進行從小到大排列temp=arrayi;arrayi=arrayj;arrayj=temp;for( i=0;im;i+)printf(%d ,arrayi);/輸出排序后的磁道號數(shù)組printf(n 請輸入當前的磁道號：);scanf(%d,&now);if(arraym-1=now)/判斷整個數(shù)組里的數(shù)是否都小于當前磁道號 printf(n cscan

15、調(diào)度結(jié)果: );for(i=0;i=now)/判斷整個數(shù)組里的數(shù)是否都大于當前磁道號 printf(n cscan調(diào)度結(jié)果: );for(i=0;im;i+) printf(%d ,arrayi);/將磁道號從小到大輸出sum=arraym-1-now;/計算移動距離elsewhile(arrayk=0;j-)printf(%d ,arrayj);for(j=m-1;j=r;j-)printf(%d ,arrayj);sum=2*(arraym-1-array0)-arrayr+now;/計算移動距離/磁道號減小方向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;/計算移動距離/磁道號增加方向avg=sum/m;printf(n 移動的總道數(shù)： %d n,sum);printf( 平均尋道長度： %d n,avg);/ 操作界面int main()int c;file *fp;/定義指針文件int cidaomaxsize;/定義磁道號數(shù)組int i=0,count;fp=fopen(cidao.txt,r+);/讀取cidao.txt文件if(fp=null)/判斷文件是否存在printf(n 請 先 設(shè) 置 磁 道

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

18、dao,count);/先來先服務(wù)算法printf(n);break;case 2:sstf(cidao,count);/最短尋道時間優(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 運行結(jié)果 圖21 運行界面 圖22 運行fcfs的界面 圖23 運行sstf的界面 圖24 運行scan的界面 圖25 運行scan的界面 圖26 運行cscan的界面 圖27 運行cscan的界面運行結(jié)果： 四種磁盤調(diào)度運行結(jié)果正確，與預期的相符。7 設(shè)計心得此次操作系統(tǒng)的課程設(shè)計，從理論到實踐，在兩個星期的日子里，可以說是苦多于甜，但是可以學到很多很多的的東西，同時不僅可以鞏固了以前所學過的知識，而且學到