磁盤調(diào)度-操作系統(tǒng)實驗報告(共21頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上實驗一 磁盤調(diào)度算法實現(xiàn)一、實驗?zāi)康谋菊n程設(shè)計的目的是通過磁盤調(diào)度算法設(shè)計一個磁盤調(diào)度模擬系統(tǒng)，從而使磁盤調(diào)度算法更加形象化，容易使人理解，使磁盤調(diào)度的特點更簡單明了，能使使用者加深對先來先服務(wù)算法、最短尋道時間優(yōu)先算法、掃描算法以及循環(huán)掃描算法等磁盤調(diào)度算法的理解。二、實驗內(nèi)容系統(tǒng)主界面可以靈活選擇某種算法，算法包括：先來先服務(wù)算法（FCFS）、最短尋道時間優(yōu)先算法（SSTF）、掃描算法（SCAN）、循環(huán)掃描算法（CSCAN）。2.1先來先服務(wù)算法（ FCFS ）這是一種比較簡單的磁盤調(diào)度算法。它根據(jù)進(jìn)程請求訪問磁盤的先后次序進(jìn)行調(diào)度。此算法的優(yōu)點是公平、簡單，且每

2、個進(jìn)程的請求都能依次得到處理，不會出現(xiàn)某一進(jìn)程的請求長期得不到滿足的情況。此算法由于未對尋道進(jìn)行優(yōu)化，在對磁盤的訪問請求比較多的情況下，此算法將降低設(shè)備服務(wù)的吞吐量，致使平均尋道時間可能較長，但各進(jìn)程得到服務(wù)的響應(yīng)時間的變化幅度較小。2.2 最短尋道時間優(yōu)先算法（ SSTF ）該算法選擇這樣的進(jìn)程，其要求訪問的磁道與當(dāng)前磁頭所在的磁道距離最近，以使每次的尋道時間最短，該算法可以得到比較好的吞吐量，但卻不能保證平均尋道時間最短。其缺點是對用戶的服務(wù)請求的響應(yīng)機(jī)會不是均等的，因而導(dǎo)致響應(yīng)時間的變化幅度很大。在服務(wù)請求很多的情況下，對內(nèi)外邊緣磁道的請求將會無限期的被延遲，有些請求的響應(yīng)時間將不可預(yù)期

3、。2.3 掃描算法（ SCAN ）掃描算法不僅考慮到欲訪問的磁道與當(dāng)前磁道的距離，更優(yōu)先考慮的是磁頭的當(dāng)前移動方向。例如，當(dāng)磁頭正在自里向外移動時，掃描算法所選擇的下一個訪問對象應(yīng)是其欲訪問的磁道既在當(dāng)前磁道之外，又是距離最近的。這樣自里向外地訪問，直到再無更外的磁道需要訪問才將磁臂換向，自外向里移動。這時，同樣也是每次選擇這樣的進(jìn)程來調(diào)度，即其要訪問的磁道，在當(dāng)前磁道之內(nèi)，從而避免了饑餓現(xiàn)象的出現(xiàn)。由于這種算法中磁頭移動的規(guī)律頗似電梯的運(yùn)行，故又稱為電梯調(diào)度算法。此算法基本上克服了最短尋道時間優(yōu)先算法的服務(wù)集中于中間磁道和響應(yīng)時間變化比較大的缺點，而具有最短尋道時間優(yōu)先算法的優(yōu)點即吞吐量較大

4、，平均響應(yīng)時間較小，但由于是擺動式的掃描方法，兩側(cè)磁道被訪問的頻率仍低于中間磁道。2.4 循環(huán)掃描算法（ CSCAN ）循環(huán)掃描算法是對掃描算法的改進(jìn)。如果對磁道的訪問請求是均勻分布的，當(dāng)磁頭到達(dá)磁盤的一端，并反向運(yùn)動時落在磁頭之后的訪問請求相對較少。這是由于這些磁道剛被處理，而磁盤另一端的請求密度相當(dāng)高，且這些訪問請求等待的時間較長，為了解決這種情況，循環(huán)掃描算法規(guī)定磁頭單向移動。例如，只自里向外移動，當(dāng)磁頭移到最外的被訪問磁道時，磁頭立即返回到最里的欲訪磁道，即將最小磁道號緊接著最大磁道號構(gòu)成循環(huán)，進(jìn)行掃描。三、實驗流程3.1 系統(tǒng)功能圖圖3-1 系統(tǒng)功能圖3.2 算法流程圖本次實驗為實現(xiàn)

5、磁盤調(diào)度算法，分別實現(xiàn)四個算法并調(diào)試。四個算法算法包括：先來先服務(wù)算法（FCFS）、最短尋道時間優(yōu)先算法（SSTF）、掃描算法（SCAN）、循環(huán)掃描算法（CSCAN）。四個算法的流程圖分析如下。1） 先來先服務(wù)算法（FCFS）的流程圖圖3-2 先來先服務(wù)算法的流程圖2） 最短尋道時間優(yōu)先算法（SSTF）的流程圖圖3-3 最短尋道時間優(yōu)先算法的流程圖3） 掃描算法（SCAN）的流程圖圖3-4掃描算法的流程圖4） 循環(huán)掃描算法（CSCAN）的流程圖圖3-5 循環(huán)掃描算法的流程圖4、 源程序#include<stdio.h>#include<stdlib.h>#include

6、<iostream.h>#include<math.h>#define maxsize 1000/*判斷輸入數(shù)據(jù)是否有效*/int decide(char str) /判斷輸入數(shù)據(jù)是否有效int i=0;while(stri!='0')if(stri<'0'|stri>'9') return 0;break;i+;return i;/*將字符串轉(zhuǎn)換成數(shù)字*/int trans(char str,int a) /將字符串轉(zhuǎn)換成數(shù)字int i;int sum=0;for(i=0;i<a;i+)sum=sum+

7、(int)(stri-'0')*pow(10,a-i-1);return sum;/*冒泡排序算法*/int *bubble(int cidao,int m) int i,j;int temp;for(i=0;i<m;i+) /使用冒泡法按從小到大順序排列for(j=i+1;j<m;j+)if(cidaoi>cidaoj) temp=cidaoi;cidaoi=cidaoj;cidaoj=temp;cout<<" 排序后的磁盤序列為："for( i=0;i<m;i+) /輸出排序結(jié)果cout<<cidaoi&l

8、t;<" "cout<<endl;return cidao; /*先來先服務(wù)調(diào)度算法*/void FCFS(int cidao,int m) /磁道號數(shù)組，個數(shù)為mint now;/當(dāng)前磁道號int sum=0; /總尋道長度int j,i;int a;char str100;float ave; /平均尋道長度cout<<" 磁盤請求序列為："for( i=0;i<m;i+) /按先來先服務(wù)的策略輸出磁盤請求序列cout<<cidaoi<<" "cout<<en

9、dl;cout<<" 請輸入當(dāng)前的磁道號：" B: cin>>str; /對輸入數(shù)據(jù)進(jìn)行有效性判斷a=decide(str);if(a=0)cout<<"輸入數(shù)據(jù)的類型錯誤,請重新輸入！"<<endl;goto B;elsenow=trans(str,a); /輸入當(dāng)前磁道號sum+=abs(cidao0-now);cout<<" 磁盤掃描序列為："for( i=0;i<m;i+) /輸出磁盤掃描序列cout<<cidaoi<<" &q

10、uot;for(i=0,j=1;j<m;i+,j+) /求平均尋道長度sum+=abs(cidaoj-cidaoi);ave=(float)(sum)/(float)(m);cout<<endl;cout<<" 平均尋道長度："<<ave<<endl;/*最短尋道時間優(yōu)先調(diào)度算法*/void SSTF(int cidao,int m)int k=1;int now,l,r;int i,j,sum=0;int a;char str100;float ave;cidao=bubble(cidao,m); /調(diào)用冒泡排序算法排

11、序cout<<" 請輸入當(dāng)前的磁道號：" C: cin>>str; /對輸入數(shù)據(jù)進(jìn)行有效性判斷a=decide(str);if(a=0)cout<<" 輸入數(shù)據(jù)的類型錯誤,請重新輸入！"<<endl;goto C;elsenow=trans(str,a); /輸入當(dāng)前磁道號if(cidaom-1<=now) /若當(dāng)前磁道號大于請求序列中最大者，則直接由外向內(nèi)依次給予各請求服務(wù) cout<<" 磁盤掃描序列為："for(i=m-1;i>=0;i-)cout<&

12、lt;cidaoi<<" "sum=now-cidao0;if(cidao0>=now) /若當(dāng)前磁道號小于請求序列中最小者，則直接由內(nèi)向外依次給予各請求服務(wù)cout<<" 磁盤掃描序列為："for(i=0;i<m;i+)cout<<cidaoi<<" "sum=cidaom-1-now;if(now>cidao0&&now<cidaom-1) /若當(dāng)前磁道號大于請求序列中最小者且小于最大者 cout<<" 磁盤掃描序列為：&

13、quot;while(cidaok<now) /確定當(dāng)前磁道在已排的序列中的位置，后面的算法都用到了，可以直接復(fù)制后少量修改，節(jié)省時間。k+; l=k-1;r=k;while(l>=0)&&(r<m) /當(dāng)前磁道在請求序列范圍內(nèi)if(now-cidaol)<=(cidaor-now) /選擇與當(dāng)前磁道最近的請求給予服務(wù) cout<<cidaol<<" "sum+=now-cidaol;now=cidaol;l=l-1; elsecout<<cidaor<<" "sum

14、+=cidaor-now;now=cidaor;r=r+1; if(l=-1) /磁頭移動到序列的最小號，返回外側(cè)掃描仍未掃描的磁道for(j=r;j<m;j+)cout<<cidaoj<<" " sum+=cidaom-1-cidao0;else /磁頭移動到序列的最大號，返回內(nèi)側(cè)掃描仍未掃描的磁道for(j=l;j>=0;j-) cout<<cidaoj<<" "sum+=cidaom-1-cidao0; ave=(float)(sum)/(float)(m);cout<<end

15、l;cout<<" 平均尋道長度： "<<ave<<endl;/*掃描調(diào)度算法*/void SCAN(int cidao,int m) /先要給出當(dāng)前磁道號和移動臂的移動方向int k=1;int now,l,r,d;int i,j,sum=0;int a;char str100;float ave;cidao=bubble(cidao,m); /調(diào)用冒泡排序算法排序cout<<" 請輸入當(dāng)前的磁道號："D: cin>>str; /對輸入數(shù)據(jù)進(jìn)行有效性判斷a=decide(str);if(a=0

16、) cout<<" 輸入數(shù)據(jù)的類型錯誤,請重新輸入！"<<endl;goto D;else now=trans(str,a); /輸入當(dāng)前磁道號if(cidaom-1<=now) /若當(dāng)前磁道號大于請求序列中最大者，則直接由外向內(nèi)依次給予各請求服務(wù),此情況同最短尋道優(yōu)先 cout<<" 磁盤掃描序列為："for(i=m-1;i>=0;i-)cout<<cidaoi<<" "sum=now-cidao0;if(cidao0>=now) /若當(dāng)前磁道號小于請求序

17、列中最小者，則直接由內(nèi)向外依次給予各請求服務(wù),此情況同最短尋道優(yōu)先 cout<<" 磁盤掃描序列為：" for(i=0;i<m;i+)cout<<cidaoi<<" "sum=cidaom-1-now;if(now>cidao0&&now<cidaom-1) /若當(dāng)前磁道號大于請求序列中最小者且小于最大者 while(cidaok<now) k+;l=k-1;r=k; cout<<" 請輸入當(dāng)前移動臂的移動的方向:n"<<endl;co

18、ut<<" 0:表示向內(nèi)1 :表示向外: "<<endl;cin>>d;if(d=0) /選擇移動臂方向向內(nèi)，則先向內(nèi)掃描 cout<<" 磁盤掃描序列為："for(j=l;j>=0;j-)cout<<cidaoj<<" " /輸出向內(nèi)掃描的序列 for(j=r;j<m;j+) /磁頭移動到最小號，則改變方向向外掃描未掃描的磁道cout<<cidaoj<<" " /輸出向外掃描的序列 sum=now-2*ci

19、dao0+cidaom-1;else /選擇移動臂方向向外，則先向外掃描 cout<<" 磁盤掃描序列為："for(j=r;j<m;j+)cout<<cidaoj<<" " /輸出向外掃描的序列 for(j=l;j>=0;j-) /磁頭移動到最大號，則改變方向向內(nèi)掃描未掃描的磁道cout<<cidaoj<<" " sum=-now-cidao0+2*cidaom-1; ave=(float)(sum)/(float)(m);cout<<endl;cou

20、t<<" 平均尋道長度： "<<ave<<endl;/*循環(huán)掃描調(diào)度算法*/void CSCAN(int cidao,int m)int k=1;int now,l,r;int i,j,sum=0;int a;char str100;float ave;cidao=bubble(cidao,m); /調(diào)用冒泡排序算法排序cout<<" 請輸入當(dāng)前的磁道號：" E: cin>>str; /對輸入數(shù)據(jù)進(jìn)行有效性判斷a=decide(str);if(a=0) cout<<" 輸入

21、數(shù)據(jù)的類型錯誤,請重新輸入！"<<endl;goto E;elsenow=trans(str,a); /輸入當(dāng)前磁道號if(cidaom-1<=now) /若當(dāng)前磁道號大于請求序列中最大者，則直接將移動臂移動到最小號磁道依次向外給予各請求服務(wù) cout<<" 磁盤掃描序列為："for(i=0;i<m;i+)cout<<cidaoi<<" "sum=now-2*cidao0+cidaom-1;if(cidao0>=now) /若當(dāng)前磁道號小于請求序列中最小者，則直接由內(nèi)向外依次給予

22、各請求服務(wù),此情況同最短尋道優(yōu)先 cout<<" 磁盤掃描序列為："for(i=0;i<m;i+)cout<<cidaoi<<" "sum=cidaom-1-now; if(now>cidao0&&now<cidaom-1) /若當(dāng)前磁道號大于請求序列中最小者且小于最大者 cout<<" 磁盤掃描序列為："while(cidaok<now) /單向反復(fù)地從內(nèi)向外掃描k+; l=k-1;r=k;for(j=r;j<m;j+)cout<&l

23、t;cidaoj<<" " /輸出從當(dāng)前磁道向外掃描的序列for(j=0;j<r;j+) /當(dāng)掃描完最大號磁道，磁頭直接移動到最小號磁道，再向外掃描未掃描的磁道cout<<cidaoj<<" "sum=2*cidaom-1+cidaol-now-2*cidao0;ave=(float)(sum)/(float)(m);cout<<endl;cout<<" 平均尋道長度： "<<ave<<endl;void main()int a;int c; /

24、菜單項int cidaomaxsize;int i=0,count;char str100;cout<<" 請輸入磁道序列(輸入0結(jié)束): "<<endl;A:cin>>str; /對輸入數(shù)據(jù)進(jìn)行有效性判斷a=decide(str);if(a=0)cout<<" 輸入數(shù)據(jù)的類型錯誤,請重新輸入！"<<endl;goto A;/輸入錯誤，跳轉(zhuǎn)到A，重新輸入elsecidaoi=trans(str,a);i+;while(cidaoi-1!=0)cin>>str; /對輸入數(shù)據(jù)進(jìn)行有效性

25、判斷a=decide(str);if(a=0)cout<<" 輸入數(shù)據(jù)的類型錯誤,請重新輸入！"<<endl;else cidaoi=trans(str,a);i+;count=i-1; /要訪問的磁道數(shù)cout<<" 輸入的磁道序列為："for(i=0;i<count;i+)cout<<cidaoi<<" " /輸出磁道序列cout<<endl;while(1)cout<<endl;cout<<" -"<&

26、lt;endl;cout<<"n 1.先來先服務(wù) 2.最短尋道時間優(yōu)先 3.掃描調(diào)度 4.循環(huán)掃描 5.退出 n"<<endl;cout<<" -"<<endl;G:cout<<" 請選擇算法: "F:cin>>str; /對輸入數(shù)據(jù)進(jìn)行有效性判斷a=decide(str);if(a=0)cout<<" 輸入數(shù)據(jù)的類型錯誤,請重新輸入！"<<endl;goto F;/輸入錯誤，跳轉(zhuǎn)到F，重新輸入 elsec=trans(str,a);if(c=5)break;if(c>5) cout<<" 輸入的數(shù)據(jù)錯誤！請重新輸入"<<endl;goto G;switch(c)case 1: /使用FCFS算法FCFS(cidao,count);break;case 2: /使用SSTF算法SSTF(cidao,count);break;case 3: /使用SCAN算法SCAN(cidao,count);break;