磁盤調(diào)度算法的實現(xiàn)

1、實驗五、磁盤調(diào)度算法的實現(xiàn)一、實驗?zāi)康膶嶒灣绦蚰M先來先服務(wù) FCFS最短尋道時間優(yōu)先SSTFSCA腳口循環(huán)SCAN 算法的工作過程。假設(shè)有n個磁道號所組成的磁道訪問序列，給定開始磁道號m 和磁頭移動的方向(正向或者反向)，分別利用不同的磁盤調(diào)度算法訪問磁道序 列，給出每一次訪問的磁頭移動距離， 計算每種算法的平均尋道長度，本程序采 用隨機數(shù)來產(chǎn)生磁道數(shù)。二、實驗要求算法所需的各種參數(shù)由輸入產(chǎn)生(手工輸入或者隨機數(shù)產(chǎn)生)。最后的結(jié)果 要求是在運行四種算法的程序后，能夠輸出調(diào)度過程、平均尋道長度的正確結(jié)果。三、實驗說明先來先服務(wù).(FCFS):這是一種簡單的磁盤調(diào)度算法。它根據(jù)進程請求訪問磁盤的

2、先后次序進行調(diào) 度。此算法的優(yōu)點是公平、簡單，且每個進程的請求都能依次得到處理，不會出 現(xiàn)某一進程的請求長期得不到滿足的情況。但此算法由于未對尋道進行優(yōu)化，致 使平均尋道時間可能較長。(2)最短尋道時間優(yōu)先(SSTF):該算法選擇這樣的進程，其要求訪問的磁道與當(dāng)前磁頭所在的磁道距離最 近，以使每次的尋道時間最短，但這種調(diào)度算法卻不能保證平均尋道時間最短。掃描算法(SCAN):SCANB法不僅考慮到欲訪問的磁道與當(dāng)前磁道的距離，更優(yōu)先考慮的是磁 頭的當(dāng)前移動方向。例如，當(dāng)磁頭正在自里向外移動時，SCANT法所選擇的下一個訪問對象應(yīng)是其欲訪問的磁道既在當(dāng)前磁道之外，又是距離最近的。這樣自里向外地訪

3、問，直到再無更外的磁道需要訪問才將磁臂換向，自外向里移動。這時，同樣也是每次選擇這樣的進程來調(diào)度，即其要訪問的磁道，在當(dāng)前磁道之內(nèi)， 從而避免了饑餓現(xiàn)象的出現(xiàn)。由于這種算法中磁頭移動的規(guī)律頗似電梯的運行， 故又稱為電梯調(diào)度算法。(4)循環(huán)掃描算法(CSCANCSCANJT法是對掃描算法的改進。如果對磁道的訪問請求是均勻分布的， 當(dāng) 磁頭到達磁盤的一端，并反向運動時落在磁頭之后的訪問請求相對較少。這是由 于這些磁道剛被處理，而磁盤另一端的請求密度相當(dāng)高， 且這些訪問請求等待的 時間較長，為了解決這種情況，循環(huán)掃描算法規(guī)定磁頭單向移動。例如，只自里向外移動，當(dāng)磁頭移到最外的被訪問磁道時，磁頭立即返

4、回到最里的欲訪磁道， 即將最小磁道號緊接著最大磁道號構(gòu)成循環(huán)，進行掃描本系統(tǒng)劃分為四個模塊：先來先服務(wù)算法模塊void FCFS(int array,int m)最短尋道時間優(yōu)先算法模塊 void SSTF(int array,int m)掃描算法模塊void SCAN(int array,int m)、循環(huán)掃描模塊 void CSCAN (int Han,int DiscL)系統(tǒng)模塊圖1先來先服務(wù)算法模塊：void FCFS(int array,int m)輸入磁道號，按先來先服務(wù)的策略輸出磁盤請求序列，求平均尋道長度，輸出移動平均磁道數(shù)。2最短尋道時間優(yōu)先算法模塊：void SSTF(in

5、t array,int m)將磁道號用冒泡法從小到大排序， 輸出排好序的磁道序列，輸入當(dāng)前磁道號，根 據(jù)前磁道在已排的序列中的位置， 選擇掃描的順序，求出平均尋道長度，輸出移 動的平均磁道數(shù)。3 掃描算法模塊：void SCAN(int array,int m)將磁道號用冒泡法從小到大排序， 輸出排好序的序列，輸入當(dāng)前磁道號，選擇移 動臂的移動方向，根據(jù)當(dāng)前磁道在已排的序列中的位置， 選擇掃描的順序，求出 平均尋道長度，輸出移動的平均磁道數(shù)。4 循環(huán)掃描算法模塊：void CSCAN(int array,int m)將磁道號用冒泡法從小到大排序， 輸出排好序的序列，輸入當(dāng)前磁道號，規(guī)定移 動臂

6、單向反復(fù)的從內(nèi)向外移動，根據(jù)當(dāng)前磁道在已排的序列中的位置， 選擇掃描 的順序，求出平均尋道長度，輸出移動的平均磁道數(shù)。1、先來先服務(wù)(FCFS)這是一種簡單的磁盤調(diào)度算法。它根據(jù)進程請求訪問磁盤的先后次序進行調(diào)度。此算法的優(yōu)點是公平、簡單，且每個進程的請求都能依次得到處理， 不會出現(xiàn)某 一進程的請求長期得不到滿足的情況。但此算法由于未對尋道進行優(yōu)化，致使平 均尋道時間可能較長。實現(xiàn)函數(shù)：void FCFS(int Han,int DiscL)先來先服務(wù)算法(FCFS流程圖：2、最短尋道時間優(yōu)先(SSTF)該算法選擇這樣的進程，其要求訪問的磁道與當(dāng)前磁頭所在的磁道距離最近，以使每次的尋道時間最短

7、，但這種調(diào)度算法卻不能保證平均尋道時間最短。實現(xiàn)函數(shù)：void SSTF(int Han,int DiscL)最短尋道時間優(yōu)先流程圖:輸入磁使用冒泡法從小到輸出排好序的磁選擇與當(dāng)前磁道 距離最近的磁道移動到最小（大） 號，改向外（內(nèi)） 移幼掃描未掃描 k>求生物尋道輸出移動的平均3、掃描算法（SCAN）SCANB法不僅考慮到欲訪問的磁道與當(dāng)前磁道的距離,更優(yōu)先考慮的是磁頭的當(dāng)前移動方向。例如，當(dāng)磁頭正在自里向外移動時，SCAN算法所選擇的下一個訪問對象應(yīng)是其欲訪問的磁道既在當(dāng)前磁道之外，又是距離最近的。這樣自里向外地訪問，直到再無更外的磁道需要訪問才將磁臂換向，自外向里移動。這時， 同樣

8、也是每次選擇這樣的進程來調(diào)度， 即其要訪問的磁道，在當(dāng)前磁道之內(nèi)，從而避免了饑餓現(xiàn)象的出現(xiàn)。由于這種算法中磁頭移動的規(guī)律頗似電梯的運行，故又稱為電梯調(diào)度算法。實現(xiàn)函數(shù):int SCAN(int Han,int DiscL,int x,int y)(4)循環(huán)掃描算法(CSCANcscaNT法在scanB法的基礎(chǔ)上規(guī)定了刺頭單向移動，減少了進程的請求延遲。 例如：只是自理向外移動，當(dāng)磁頭移到最外的磁道并訪問后， 磁頭立即返回到最 里的欲訪問磁道，亦即將最小的磁道號緊接著最大的磁道號構(gòu)成循環(huán)， 進行循環(huán) 掃描。實現(xiàn)函數(shù)：void CSCAN(int Han,int DiscL)源代碼：©/

9、 123123123.cpp :定義控制臺應(yīng)用程序的入口點#include "stdafx.h"#include "stdio.h"#include "stdlib.h"void CopyL( int Sour, int Dist , int x); / 數(shù)組 Sour 復(fù)制到數(shù)組 Dist , 復(fù)制到 x 個數(shù) void SetDI( int DiscL); / 隨機生成磁道數(shù) void Print( int Pri, int x);/ 打印輸出數(shù)組 Pri void DelInq( int Sour, int x, int y);

10、/數(shù)組Sour把x位置的數(shù)刪除，并把y前面的數(shù)向前移動，y后的數(shù)保持不變(即 會出現(xiàn)2個y) void FCFS(int Han, int DiscL); /先來先服務(wù)算法 (FCFS)void SSTF(int Han,int DiscL); / 最短尋道時間優(yōu)先算法(SSTF)int SCAN(nt Han,int DiscL, int x, int y);/ 掃描算法(SCAN)zoid CSCANi(itHan,int DiscL); /循環(huán)掃描算法(CSCANvoid N_Step_SCAN(nt Han1, int DiscL); /N步掃描算法(NStepScan) void P

11、aiXu(); /尋道長度由低到高 排序void Pri(); int NAll= 0; int Best 5 2; /用作尋道長度由低到高排序 時存放的數(shù)組int Limit= 0; /輸入尋找的范圍磁道數(shù)i int Jage; float Aver=0;int main() (int i;int DiscLine 10;/聲明準(zhǔn)備要生成的隨機磁道號的數(shù)組int Hand; / 磁道數(shù) int Con=1;int n;while (Con=1)(Jage= 0;printf("請輸入初始的磁道數(shù)(0<n<65536):");scanf("%d”,&a

12、mp;Hand);printf(" +輸入尋找的范圍:");scanf("%d",&Limit);if (Limit<= 0|Limit> 65536)printf("超出范圍!");)else printf("(>n");printf( "I操作系統(tǒng)課程實驗In");printf( " (1磁盤調(diào)度算法I、n");printf( " IIIn");printf("<)n");printf("

13、I1. 先來先服務(wù)算法(FCFS)n");printf("n");printf("11 n");printf("1n");printf("1n");printf("1n");printf("1n");printf("1n");printf("1n");printf(n");printf("'11)n" );printf("n");scanf("%d"

14、,&n);if (n=0) exit( 0);printf(" " );2.3.4.最短尋道時間優(yōu)先算法(SSTF)掃描算法(SCAN)循環(huán)掃描算法(CSCAN)請輸入你的選擇的算法(輸入0離開)switch (n) (case 1:SetDI(DiscLine);FCFS(Hand,DiscLine); break;case 2:SetDI(DiscLine);SSTF(Hand,DiscLine); break ;case 3:SetDI(DiscLine);SCAN(Hand,DiscLine, break ;case 4: SetDI(DiscLine);

15、CSCAN(Hand,DiscLine);break ; printf( scanf(/隨機生成磁道數(shù)/先來先服務(wù)算法(FCFS)/隨機生成磁道數(shù)/最短尋道時間優(yōu)先算法(SSTF)/隨機生成磁道數(shù)0, 9);/ 掃描算法(SCAN)/隨機生成磁道數(shù)/循環(huán)掃描算法(CSCAN)"+是否繼續(xù)(按0結(jié)束，按1繼續(xù))?"); "%5d”,&Con);)/數(shù)組Sour復(fù)制到數(shù)組Dist ,復(fù)制到x個數(shù)void CopyL( int Sour, intDist , int x)(int i;for (i= 0;i<=x;i+)(Disti=Souri;)/ 打印

16、輸出數(shù)組 Pri void Print( int Pri, int x)(int i;for (i= 0;i<=x;i+)(printf( "%5d",Prii);/ 隨機生成磁道數(shù) void SetDI( int DiscL)(int i;for (i= 0;i<= 9;i+)(DiscLi=rand()%Limit;隨機生成 10 個磁道號printf("+需要尋找的磁道號:");Print(DiscL, 9);/輸出隨機生成的磁道號printf(" n" );/數(shù)組Sour把x位置的數(shù)刪除，并把y前面的數(shù)向前移動，y

17、后的數(shù)保持不變(即會出現(xiàn) 2 個 y) void DelInq( int Sour, int x, int y)(int i;for (i=x;i<y;i+)(Souri=Souri+ 1;x+;"/先來先服務(wù)算法(FCFS)void FCFS(int Han, int DiscL)(int RLine 10;/將隨機生成的磁道數(shù)數(shù)組 Discl口復(fù)制給數(shù)組RLine口int i,k,All,Temp; /Temp是計算移動的磁道距離的臨時變量All= 0; /統(tǒng)計全部的磁道數(shù)變量k= 9; 限定10個的磁道數(shù)CopyL(DiscL,RLine, 9);/復(fù)制磁道號到臨時數(shù)組R

18、Lineprintf( " +按照FCFSU法磁道的訪問順序為:");All=Han-RLine 0;for (i= 0;i<= 9;i+)Temp=RLine 0-RLine 1; /求出移動磁道數(shù)，前一個磁道數(shù)減去后一 個磁道數(shù)得出臨時的移動距離if (Temp<0)Temp=(-Temp); /移動磁道數(shù)為負數(shù)時，算出相反數(shù)作為移動磁道 數(shù)printf( "%5d",RLine 0);All=Temp+All;/求全部磁道數(shù)的總和DelInq(RLine,0,k); /每個磁道數(shù)向前移動一位k-;BestJage1=All; /Best

19、1 存放移動磁道數(shù)BestJage0=1; /Best0存放算法的序號為:1Jage+; /排序的序號加1Aver=( float ) All)/ 10;/ 求平均尋道次數(shù)printf("n");printf(" + 移動磁道數(shù):<%5d> " ,All);printf( "n");printf( " + 平均尋道長度：*%0.2f* n" ,Aver);printf( "n");/ 冒泡排序 int * Bubble( int pArr, int nFirst, int nEnd)

20、 int nTemp=0;for (int i=nFirst;i<nEnd;+i)for (int j=i;j<nEnd;+j)if (pArri>pArrj)nTemp=pArri;pArri=pArrj;pArrj=nTemp;return pArr;/ 最短尋道時間優(yōu)先算法(SSTF)void SSTF(int Han, int DiscL) int temp;int k= 1 ,n= 10;int l,r;int i,j,all= 0;/將磁道號按遞增排序DiscL=Bubble(DiscL, 0, 10);printf( "n+按照SSTF算法磁道的訪問順

21、序為：")；/判斷標(biāo)志位Han左、右兩邊的偏移量大小if (DiscLn- 1<=Han)/當(dāng)前磁頭位置大于最外圍欲訪問磁道for (i=n- 1;i>= 0;i-)printf( "%d " ,DiscLi);all=Han-DiscL 0;elseif (DiscL 0>=Han)/當(dāng)前磁頭位置小于最里欲訪問磁道for (i= 0;i<n;i+)printf("%d " ,DiscLi);all=DiscLn- 1-Han;elsewhile (DiscLk<Han) /確定當(dāng)前磁道在已排的序列中的位置k+;l

22、=k-1; /在磁頭位置的前一個欲訪問磁道r=k;/磁頭欲訪問磁道while (l>= 0)&&(r<n)if (Han-DiscLl)<=(DiscLr-Han) / 選擇離磁頭近的磁道 printf("%d " ,DiscLl);all+=Han-DiscLl;Han=DiscLl;l=l-1;elseprintf("%d " ,DiscLr);all+=DiscLr-Han;Han=DiscLr;r=r+ 1;)if (l=- 1)磁頭位置里側(cè)的磁道已訪問完(for (j=r;j<n;j+)/訪問磁頭位置外側(cè)

23、的磁道printf("%d " ,DiscLj);) all+=DiscLn-1-DiscL 0;)if (r=n) /磁頭位置外側(cè)的磁道已訪問完 for (j=k- 1;j>- 1 ;j-)/訪問磁頭位置里側(cè)的磁道printf( "%d " ,DiscLj);)all+=DiscLn- 1-DiscL 0;)printf( "n + 移動磁道數(shù):<%5d> n" ,all);printf( " + 平均尋道長度：*%0.2f* n",all/ 10.0);)/ 掃描算法(SCAN)nt SCAN

24、nt Han, int DiscL, int x, int y)int temp;int k= 1 ,n= 10;int l,r;int i,j,all= 0;DiscL=Bubble(DiscL,x,y);/printf("按遞增順序排好的磁道為：")；/for( i=0;i<n;i+)/ printf("%d ",DiscLi);/)/以下算法確定磁道訪問順序if (DiscLn- 1<=Han) /磁頭位置大于最外圍欲訪問磁道for (i=n- 1;i>= 0;i-)printf("%d " ,DiscLi);

25、all=Han-DiscL 0;)elseif (DiscL 0>=Han) /磁頭位置小于最里欲訪問磁道for (i= 0;i<n;i+)printf( all=DiscLn-"%d " ,DiscLi);1-Han;)else/磁頭位置在最里側(cè)磁道與最外側(cè)磁道之間int d;while (DiscLk<Han)/確定當(dāng)前磁道在已排的序列中的位置k+;)l=k-1; /在磁頭位置的前一個欲訪問磁道r=k;/磁頭欲訪問磁道printf("n請輸入當(dāng)前磁頭移動的方向(0表示向內(nèi)，1表示向外)："); scanf("%d"

26、;,&d);/確定磁頭訪問的方向printf("按照SCANT法訪問順序為：");if (d=0|d= 1) if (d=0)磁頭向內(nèi)for (j=l;j>= 0;j-) printf("%d " ,DiscLj);) for (j=r;j<n;j+) printf("%d " ,DiscLj);) all=Han-2*DiscL 0+DiscLn- 1;) if (d=1)/磁頭向外for (j=r;j<n;j+)printf("%d " ,DiscLj);) for (j=l;j>

27、;= 0;j-) printf("%d " ,DiscLj);) all=2*DiscLn- 1-Han-DiscL 0;) ) elseprintf("請輸入 0 或 1!");)printf( "n +移動磁道數(shù):<%5d> n" ,all);printf( " + 平均尋道長度：*%0.2f* n" ,all/ 10.0);return 0;"/循環(huán)掃描算法(CSCANVoid CSCAN(nt Han, int DiscL口) int temp;int l,r;int i,j,all= 0;int k= 1 ,n= 10;/對訪問磁道按由小到大順序排列輸出DiscL=Bubble(DiscL, 0, 10);/printf("按遞增順序排好的磁道為：")；/for( i=0;i<n;i+) / printf("%d ",DiscLi);/)if (DiscLn- 1<=Han)/磁頭位置