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

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

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

3、應(yīng)時間將不可預(yù)期。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)時間變化比較大的缺點(diǎn)，而具有最短尋道時間優(yōu)先算法的優(yōu)點(diǎn)即吞

4、吐量較大，平均響應(yīng)時間較小，但由于是擺動式的掃描方法，兩側(cè)磁道被訪問的頻率仍低于中間磁道。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.模塊流程圖3.1模塊調(diào)用關(guān)系圖磁盤調(diào)度模擬系統(tǒng)退出先來先服務(wù)算法最短尋道時間優(yōu)

5、先掃描算法循環(huán)掃描算法3.2模塊程序流程圖FCFS算法（先來先服務(wù)）流程圖:輸入磁道號求平均尋道長度輸出移動的平均磁道數(shù)按輸入順序?qū)⒋诺佬蛄休敵鲩_始結(jié)束 SSTF（最短尋道時間優(yōu)先算法）算法流程圖：求平均尋道長度選擇與當(dāng)前磁道距離最近的磁道進(jìn)行掃描移動到最?。ù螅┨枺南蛲猓▋?nèi)）移動掃描未掃描的磁道輸出移動的平均磁道數(shù)輸出排好序的磁道序列判斷當(dāng)前磁頭在序列中的位置結(jié)束開始輸入磁道號使用冒泡法從小到大排序輸入當(dāng)前磁道號 SCAN算法（掃描算法）流程圖：求平均尋道長度選擇移動臂移動方向，開始掃描移動到最小（大）號，改向外（內(nèi)）移動掃描未掃描的磁道輸出移動的平均磁道數(shù)輸出排好序的磁道序列開始結(jié)束輸入

6、磁道號使用冒泡法從小到大排序輸入當(dāng)前磁道號判斷當(dāng)前磁頭在序列中的位置CSCAN算法（循環(huán)掃描算法）流程圖：求平均尋道長度掃描到最大號后，直接移動到最小號從內(nèi)向外掃描未掃描的磁道輸出移動的平均磁道數(shù)輸出排好序的磁道序列判斷當(dāng)前磁頭在序列中的位置規(guī)定移動臂單向反復(fù)的從內(nèi)向外掃描開始結(jié)束輸入磁道號使用冒泡法從小到大排序輸入當(dāng)前磁道號4 測試數(shù)據(jù)和結(jié)果輸入磁道序列號：25 160 78 65 100 62 16 53 45選擇算法1，平均尋道長度46.4444；選擇算法2，平均尋道長度為16.6667；選擇算法3，磁臂移動方向?yàn)橛赏庀騼?nèi)，平均尋道長度為16.4444選擇算法3，磁臂移動方向?yàn)橛蓛?nèi)向外，

7、平均尋道長度為31.5556；選擇算法4，平均尋道長度為31.44445 參考文獻(xiàn)計(jì)算機(jī)操作系統(tǒng)(修訂版) 湯子瀛 西安電子科技大學(xué)出版社 操作系統(tǒng)教程 方敏編 西安電子科技大學(xué)出版社 操作系統(tǒng)實(shí)用教程（第二版）任愛華 清華大學(xué)出版社 操作系統(tǒng)原理與實(shí)踐教程 周湘貞 清華出版社 程序設(shè)計(jì)基礎(chǔ)教程 陳家駿 機(jī)械工業(yè)出版社6 總結(jié)通過這次試驗(yàn)，我們清楚的了解到磁盤調(diào)度的詳細(xì)過程和四種調(diào)度算法（先來先服務(wù)算法；最短尋道時間優(yōu)先算法；掃描算法；循環(huán)掃描算法）以及四種調(diào)度算法之間的差異和共性，同時，也看到了經(jīng)過優(yōu)化的算法會帶來的好處！在實(shí)驗(yàn)過程中，也遇到了不少問題，在實(shí)現(xiàn)掃描算法時出現(xiàn)了問題！當(dāng)輸入的當(dāng)

8、前的磁道號不在磁盤請求序列中時，程序可以正常執(zhí)行，當(dāng)輸入的當(dāng)前的磁道號在磁盤請求序列中時，程序執(zhí)行時出現(xiàn)處理序列順序錯誤的問題，通過和同學(xué)的討論，發(fā)現(xiàn)有兩個循環(huán)中的自變量初值設(shè)置有問題，經(jīng)過調(diào)整后，程序執(zhí)行無誤！以后，在實(shí)現(xiàn)代碼的過程中，一定會更加小心，防止出現(xiàn)低級錯誤導(dǎo)致程序出錯！附：#include#include#include#include#define maxsize 1000/*判斷輸入數(shù)據(jù)是否有效*/int decide(char str) /判斷輸入數(shù)據(jù)是否有效 int i=0;while(stri!=0) if(stri9)return 0;break;i+;return

9、i;/*將字符串轉(zhuǎn)換成數(shù)字*/int trans(char str,int a) /將字符串轉(zhuǎn)換成數(shù)字int i;int sum=0;for(i=0;ia;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;im;i+) /使用冒泡法按從小到大順序排列 for(j=i+1;jcidaoj) temp=cidaoi; cidaoi=cidaoj; cidaoj=temp; cout排序后的磁盤序列為：; for( i=0

10、;im;i+) /輸出排序結(jié)果 coutcidaoi ; coutendl; return cidao; /*先來先服務(wù)調(diào)度算法*/void FCFS(int cidao,int m) /磁道號數(shù)組，個數(shù)為m int now;/當(dāng)前磁道號 int sum=0; /總尋道長度 int j,i;int a;char str100; float ave; /平均尋道長度cout磁盤請求序列為：; for( i=0;im;i+) /按先來先服務(wù)的策略輸出磁盤請求序列 coutcidaoi ; coutendl; coutstr; /對輸入數(shù)據(jù)進(jìn)行有效性判斷 a=decide(str); if(a=0)

11、 cout輸入數(shù)據(jù)的類型錯誤,請重新輸入！endl; goto B; else now=trans(str,a); /輸入當(dāng)前磁道號 sum+=abs(cidao0-now);cout磁盤掃描序列為：; for( i=0;im;i+) /輸出磁盤掃描序列 coutcidaoi ; for(i=0,j=1;jm;i+,j+) /求平均尋道長度 sum+=abs(cidaoj-cidaoi); ave=(float)(sum)/(float)(m); coutendl; cout平均尋道長度：aveendl;/*最短尋道時間優(yōu)先調(diào)度算法*/void SSTF(int cidao,int m) in

12、t k=1; int now,l,r; int i,j,sum=0; int a; char str100; float ave; cidao=bubble(cidao,m); /調(diào)用冒泡排序算法排序 coutstr; /對輸入數(shù)據(jù)進(jìn)行有效性判斷 a=decide(str); if(a=0) cout輸入數(shù)據(jù)的類型錯誤,請重新輸入！endl; goto C; else now=trans(str,a); /輸入當(dāng)前磁道號 if(cidaom-1=now) /若當(dāng)前磁道號大于請求序列中最大者，則直接由外向內(nèi)依次給予各請求服務(wù) cout=0;i-) coutcidaoi=now) /若當(dāng)前磁道號小

13、于請求序列中最小者，則直接由內(nèi)向外依次給予各請求服務(wù) cout磁盤掃描序列為：; for(i=0;im;i+) coutcidaoicidao0&nowcidaom-1) /若當(dāng)前磁道號大于請求序列中最小者且小于最大者 cout磁盤掃描序列為：; while(cidaok=0)&(rm) /當(dāng)前磁道在請求序列范圍內(nèi) if(now-cidaol)=(cidaor-now) /選擇與當(dāng)前磁道最近的請求給予服務(wù) coutcidaol ; sum+=now-cidaol; now=cidaol; l=l-1; else coutcidaor ; sum+=cidaor-now; now=cidaor;

14、 r=r+1; if(l=-1) /磁頭移動到序列的最小號，返回外側(cè)掃描仍未掃描的磁道 for(j=r;jm;j+) coutcidaoj=0;j-) coutcidaoj ; sum+=cidaom-1-cidao0; ave=(float)(sum)/(float)(m); coutendl; cout平均尋道長度： aveendl;/*掃描調(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; cid

15、ao=bubble(cidao,m); /調(diào)用冒泡排序算法排序 coutstr; /對輸入數(shù)據(jù)進(jìn)行有效性判斷 a=decide(str); if(a=0) 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=0;i-) coutcidaoi=now) /若當(dāng)前磁道號小于請求序列中最小者，則直接由內(nèi)向外依次給予各請求服務(wù),此情況同最短尋道優(yōu)先 cout磁盤掃描序列為：; for(i=

16、0;im;i+) coutcidaoicidao0&nowcidaom-1) /若當(dāng)前磁道號大于請求序列中最小者且小于最大者 while(cidaoknow) k+; l=k-1; r=k; coutd; if(d=0) /選擇移動臂方向向內(nèi)，則先向內(nèi)掃描 cout=0;j-) coutcidaoj ; /輸出向內(nèi)掃描的序列 for(j=r;jm;j+) /磁頭移動到最小號，則改變方向向外掃描未掃描的磁道 coutcidaoj ; /輸出向外掃描的序列 sum=now-2*cidao0+cidaom-1; else /選擇移動臂方向向外，則先向外掃描 cout磁盤掃描序列為：; for(j=r

17、;jm;j+) coutcidaoj=0;j-) /磁頭移動到最大號，則改變方向向內(nèi)掃描未掃描的磁道 coutcidaoj ; sum=-now-cidao0+2*cidaom-1; ave=(float)(sum)/(float)(m); coutendl; cout平均尋道長度： aveendl;/*循環(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)用冒泡排序算法排序 coutst

18、r; /對輸入數(shù)據(jù)進(jìn)行有效性判斷 a=decide(str); if(a=0) cout輸入數(shù)據(jù)的類型錯誤,請重新輸入！endl; goto E; else now=trans(str,a); /輸入當(dāng)前磁道號 if(cidaom-1=now) /若當(dāng)前磁道號大于請求序列中最大者，則直接將移動臂移動到最小號磁道依次向外給予各請求服務(wù) cout磁盤掃描序列為：; for(i=0;im;i+) coutcidaoi=now) /若當(dāng)前磁道號小于請求序列中最小者，則直接由內(nèi)向外依次給予各請求服務(wù),此情況同最短尋道優(yōu)先 cout磁盤掃描序列為：; for(i=0;im;i+) coutcidaoici

19、dao0&nowcidaom-1) /若當(dāng)前磁道號大于請求序列中最小者且小于最大者 cout磁盤掃描序列為：; while(cidaoknow) /單向反復(fù)地從內(nèi)向外掃描 k+; l=k-1; r=k; for(j=r;jm;j+) coutcidaoj ; /輸出從當(dāng)前磁道向外掃描的序列 for(j=0;jr;j+) /當(dāng)掃描完最大號磁道，磁頭直接移動到最小號磁道，再向外掃描未掃描的磁道 coutcidaoj ; sum=2*cidaom-1+cidaol-now-2*cidao0; ave=(float)(sum)/(float)(m); coutendl; cout平均尋道長度： aveendl;void main() int a; int c; /菜單項(xiàng) int cidaomaxsize; int i=0,count; char str100; cout請輸入磁道序列（0結(jié)束）：str; /對輸入數(shù)據(jù)進(jìn)行有效性判斷 a=decide(str); if(a=0) cout輸入數(shù)據(jù)的類型錯誤,請重新輸入！str; /對輸入數(shù)據(jù)進(jìn)行有效性判斷 a=decide(str); if(a=0) cout輸入數(shù)據(jù)的類型錯誤,請重新輸入！endl; el