操作系統(tǒng)實(shí)驗(yàn)四 磁盤調(diào)度算法

1、操作系統(tǒng)實(shí)驗(yàn)四 磁盤調(diào)度算法實(shí)驗(yàn)四 磁盤調(diào)度一、實(shí)驗(yàn)?zāi)康模罕緦?shí)驗(yàn)要求學(xué)生模擬設(shè)計(jì)一個(gè)磁盤調(diào)度程序，觀察調(diào)度程序的動(dòng)態(tài)運(yùn)行過程。通過實(shí)驗(yàn)讓學(xué)生理解和掌握磁盤調(diào)度的職能。二、實(shí)驗(yàn)內(nèi)容：對磁盤進(jìn)行移臂操作，模擬磁盤調(diào)度算法并計(jì)算平均尋道時(shí)間三、實(shí)驗(yàn)準(zhǔn)備：1.相關(guān)理論知識：（1）假設(shè)磁盤只有一個(gè)盤面，并且磁盤是可移動(dòng)頭磁盤。（3）磁盤是高速、大容量、旋轉(zhuǎn)型、可直接存取的存儲(chǔ)設(shè)備。它作為計(jì)算機(jī)系統(tǒng)的輔助存儲(chǔ)器，擔(dān)負(fù)著繁重的輸入輸出工作，在現(xiàn)代計(jì)算機(jī)系統(tǒng)中往往同時(shí)會(huì)有若干個(gè)要求訪問磁盤的輸入輸出要求。系統(tǒng)可采用一種策略，盡可能按最佳次序執(zhí)行訪問磁盤的請求。由于磁盤訪問時(shí)間主要受尋道時(shí)間T的影響，為此需要采

2、用合適的尋道算法，以降低尋道時(shí)間。（2）磁盤是可供多個(gè)進(jìn)程共享的存儲(chǔ)設(shè)備，但一個(gè)磁盤每個(gè)時(shí)刻只能為一個(gè)進(jìn)程服務(wù)。當(dāng)有進(jìn)程在訪問某個(gè)磁盤時(shí)，其它想訪問該磁盤的進(jìn)程必須等待，直到磁盤一次工作結(jié)束。當(dāng)有多個(gè)進(jìn)程提出輸入輸出請求而處于等待狀態(tài)時(shí)，可用磁盤調(diào)度算法從若干個(gè)等待訪問者中選擇一個(gè)進(jìn)程，讓它訪問磁盤。2.測試數(shù)據(jù)：磁盤讀寫請求隊(duì)列：20，44，40，4，80，12，76當(dāng)前磁頭位置：50 試問采用FCFS、SSTF、SCAN磁盤調(diào)度算法時(shí)尋道順序及平均尋道時(shí)間分別為多少？ 四、實(shí)驗(yàn)過程：1.流程圖 SCAN算法（掃描算法）流程圖：求平均尋道長度選擇移動(dòng)臂移動(dòng)方向，開始掃描移動(dòng)到最?。ù螅┨?，改

3、向外（內(nèi)）移動(dòng)掃描未掃描的磁道輸出移動(dòng)的平均磁道數(shù)輸出排好序的磁道序列開始結(jié)束輸入磁道號使用冒泡法從小到大排序輸入當(dāng)前磁道號判斷當(dāng)前磁頭在序列中的位置2. 源代碼#include<stdio.h>#include<stdlib.h>#include<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'|s

4、tri>'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+(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+) i

5、f(cidaoi>cidaoj) temp=cidaoi; cidaoi=cidaoj; cidaoj=temp; cout<<"排序后的磁盤序列為：" for( i=0;i<m;i+) /輸出排序結(jié)果 cout<<cidaoi<<" " cout<<endl; return cidao; /*先來先服務(wù)調(diào)度算法*/void FCFS(int cidao,int m) /磁道號數(shù)組，個(gè)數(shù)為m int now;/當(dāng)前磁道號 int sum=0; /總尋道長度 int j,i;int a;char

6、str100; float ave; /平均尋道長度cout<<"磁盤請求序列為：" for( i=0;i<m;i+) /按先來先服務(wù)的策略輸出磁盤請求序列 cout<<cidaoi<<" " cout<<endl; cout<<"請輸入當(dāng)前的磁道號：" B: cin>>str; /對輸入數(shù)據(jù)進(jìn)行有效性判斷 a=decide(str); if(a=0) cout<<"輸入數(shù)據(jù)的類型錯(cuò)誤,請重新輸入！"<<endl;

7、 goto B; else now=trans(str,a); /輸入當(dāng)前磁道號 sum+=abs(cidao0-now);cout<<"磁盤掃描序列為：" for( i=0;i<m;i+) /輸出磁盤掃描序列 cout<<cidaoi<<" " for(i=0,j=1;j<m;i+,j+) /求平均尋道長度 sum+=abs(cidaoj-cidaoi); ave=(float)(sum)/(float)(m); cout<<endl; cout<<"平均尋道長度：&qu

8、ot;<<ave<<endl;/*最短尋道時(shí)間優(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)用冒泡排序算法排序 cout<<"請輸入當(dāng)前的磁道號：" C: cin>>str; /對輸入數(shù)據(jù)進(jìn)行有效性判斷 a=decide(str); if(a=0) cout<<"輸入數(shù)據(jù)的類型錯(cuò)誤,請重新輸入！&q

9、uot;<<endl; goto C; else now=trans(str,a); /輸入當(dāng)前磁道號 if(cidaom-1<=now) /若當(dāng)前磁道號大于請求序列中最大者，則直接由外向內(nèi)依次給予各請求服務(wù) cout<<"磁盤掃描序列為：" for(i=m-1;i>=0;i-) cout<<cidaoi<<" " sum=now-cidao0; if(cidao0>=now) /若當(dāng)前磁道號小于請求序列中最小者，則直接由內(nèi)向外依次給予各請求服務(wù) cout<<"磁盤掃

10、描序列為：" for(i=0;i<m;i+) cout<<cidaoi<<" " sum=cidaom-1-now; if(now>cidao0&&now<cidaom-1) /若當(dāng)前磁道號大于請求序列中最小者且小于最大者 cout<<"磁盤掃描序列為：" while(cidaok<now) /確定當(dāng)前磁道在已排的序列中的位置，后面的算法都用到了，可以直接復(fù)制后少量修改，節(jié)省時(shí)間。 k+; l=k-1; r=k; while(l>=0)&&(r&l

11、t;m) /當(dāng)前磁道在請求序列范圍內(nèi) if(now-cidaol)<=(cidaor-now) /選擇與當(dāng)前磁道最近的請求給予服務(wù) cout<<cidaol<<" " sum+=now-cidaol; now=cidaol; l=l-1; else cout<<cidaor<<" " sum+=cidaor-now; now=cidaor; r=r+1; if(l=-1) /磁頭移動(dòng)到序列的最小號，返回外側(cè)掃描仍未掃描的磁道 for(j=r;j<m;j+) cout<<cidaoj&

12、lt;<" " sum+=cidaom-1-cidao0; else /磁頭移動(dòng)到序列的最大號，返回內(nèi)側(cè)掃描仍未掃描的磁道 for(j=l;j>=0;j-) cout<<cidaoj<<" " sum+=cidaom-1-cidao0; ave=(float)(sum)/(float)(m); cout<<endl; cout<<"平均尋道長度： "<<ave<<endl;/*掃描調(diào)度算法*/void SCAN(int cidao,int m) /先要

13、給出當(dāng)前磁道號和移動(dòng)臂的移動(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) cout<<"輸入數(shù)據(jù)的類型錯(cuò)誤,請重新輸入！"<<endl; goto D; else now=trans(str,a); /輸入

14、當(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)前磁道號小于請求序列中最小者，則直接由內(nèi)向外依次給予各請求服務(wù),此情況同最短尋道優(yōu)先 cout<<"磁盤掃描序列為：" for(i=0;i<m;i+)

15、 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)前移動(dòng)臂的移動(dòng)的方向 (1 表示向外 ，0表示向內(nèi)) : " cin>>d; if(d=0) /選擇移動(dòng)臂方向向內(nèi)，則先向內(nèi)掃描 cout<<"磁盤掃描序列為：" for(j=

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

17、t; /輸出向外掃描的序列 for(j=l;j>=0;j-) /磁頭移動(dòng)到最大號，則改變方向向內(nèi)掃描未掃描的磁道 cout<<cidaoj<<" " sum=-now-cidao0+2*cidaom-1; ave=(float)(sum)/(float)(m); cout<<endl; cout<<"平均尋道長度： "<<ave<<endl;/*循環(huán)掃描調(diào)度算法*/void CSCAN(int cidao,int m) int k=1; int now,l,r; int i,j

18、,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<<"輸入數(shù)據(jù)的類型錯(cuò)誤,請重新輸入！"<<endl; goto E; else now=trans(str,a); /輸入當(dāng)前磁道號 if(cidaom-1<=now) /若當(dāng)前磁道號大于請求序列中最大者，則直

19、接將移動(dòng)臂移動(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)向外依次給予各請求服務(wù),此情況同最短尋道優(yōu)先 cout<<"磁盤掃描序列為：" for(i=0;i<m;i+) cout<<cidaoi<<" "

20、 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<<cidaoj<<" " /輸出從當(dāng)前磁道向外掃描的序列 for(j=0;j<r;j+) /當(dāng)掃描完最大號磁道，磁頭直接移動(dòng)到最小號磁道，再向外掃描未掃描的磁道 c

21、out<<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; /菜單項(xiàng) int cidaomaxsize; int i=0,count; char str100; cout<<"請輸入磁道序列（0結(jié)束）："<<

22、endl; A:cin>>str; /對輸入數(shù)據(jù)進(jìn)行有效性判斷 a=decide(str); if(a=0) cout<<"輸入數(shù)據(jù)的類型錯(cuò)誤,請重新輸入！"<<endl; goto A;/輸入錯(cuò)誤，跳轉(zhuǎn)到A，重新輸入 else cidaoi=trans(str,a); i+; while(cidaoi-1!=0) cin>>str; /對輸入數(shù)據(jù)進(jìn)行有效性判斷 a=decide(str); if(a=0) cout<<"輸入數(shù)據(jù)的類型錯(cuò)誤,請重新輸入！"<<endl; else c

23、idaoi=trans(str,a); i+; count=i-1; /要訪問的磁道數(shù) cout<<"你輸入的磁道序列為：" for(i=0;i<count;i+) cout<<cidaoi<<" " /輸出磁道序列 cout<<endl; while(1) cout<<endl; cout<<"*"<<endl; cout<<" 系統(tǒng)菜單 "<<endl;cout<<"* *&q

24、uot;<<endl;cout<<"* 1. 先來先服務(wù) *"<<endl;cout<<"* *"<<endl;cout<<"* 2. 最短尋道時(shí)間優(yōu)先 *"<<endl;cout<<"* *"<<endl;cout<<"* 3. 掃描調(diào)度 *"<<endl;cout<<"* *"<<endl;cout<<"* 4. 循環(huán)掃描 *&q