模擬磁盤調(diào)度算法系統(tǒng)的設(shè)計(jì)畢業(yè)設(shè)計(jì)

目錄 一、設(shè)計(jì)任務(wù)及主要技術(shù)3二、設(shè)計(jì)方案及論證結(jié)果4三、系統(tǒng)的原理框圖5四、設(shè)計(jì)程序12五、實(shí)驗(yàn)結(jié)果20六、調(diào)試分析及故障處理24七、設(shè)計(jì)結(jié)論25八、心得體會(huì)261、 設(shè)計(jì)任務(wù)及主要技術(shù)1整體功能概述（設(shè)計(jì)任務(wù)）： 磁盤是外設(shè)中一個(gè)很常用的部分，所以，對(duì)磁盤數(shù)據(jù)的尋道時(shí)間的長短可以直接影響機(jī)器的整體運(yùn)行速度的快慢。本設(shè)計(jì)為一個(gè)模擬磁盤調(diào)度算法的磁盤調(diào)度模擬系統(tǒng)，能夠模擬先來先服務(wù)（FCFS）算法、最短尋道時(shí)間（SSTF）算法、電梯（SCAN）算法、環(huán)形掃描（C_SCAN）算法及N_SCAN算法五個(gè)磁盤調(diào)度算法，輸入為一組作業(yè)的磁道請(qǐng)求，輸出為按選擇的算法執(zhí)行時(shí)的磁頭移動(dòng)軌跡。其中，先來先服務(wù)（FCFS）算法、最短尋道時(shí)間（SSTF）算法、電梯（SCAN）算法為基本算法，環(huán)形掃描（C_SCAN）算法及N_SCAN算法為擴(kuò)展算法。2運(yùn)行環(huán)境：（1）硬件環(huán)境 Intel core i5 CPU （2）軟件環(huán)境 Windows 7 Microsoft Visual C+ 6.03主要技術(shù)：（1）用C語言編寫程序；（2）對(duì)編程軟件Microsoft Visual C+ 6.0的了解和使用；（3）操作系統(tǒng)基礎(chǔ)知識(shí)（主要是對(duì)先來先服務(wù)（FCFS）算法、最短尋道時(shí)間（SSTF）算法、電梯（SCAN）算法的了解）；（4）操作系統(tǒng)擴(kuò)展知識(shí)（通過網(wǎng)絡(luò)自學(xué)環(huán)形掃描（C_SCAN）算法及N_SCAN算法）。 二、設(shè)計(jì)方案及論證結(jié)果1設(shè)計(jì)方案：（1）先來先服務(wù)算法（First-Come，F(xiàn)irst-Served，F(xiàn)CFS）此算法為一種最簡單的磁盤調(diào)度算法。它直接根據(jù)作業(yè)請(qǐng)求磁盤的先后順序?qū)Υ疟P進(jìn)行尋訪。此算法公平、簡單，每個(gè)作業(yè)的磁盤請(qǐng)求都可以得到處理，不會(huì)出現(xiàn)某個(gè)作業(yè)的請(qǐng)求長期得不到滿足的情況。但此算法未對(duì)尋道方案進(jìn)行優(yōu)化，故平均周轉(zhuǎn)時(shí)間及帶權(quán)周轉(zhuǎn)時(shí)間都會(huì)較長。（2）最短尋道時(shí)間優(yōu)先算法（Shortest Seek Time First，SSTF）此算法優(yōu)先選擇距離當(dāng)前磁頭位置最近的作業(yè)磁道請(qǐng)求。此算法可以使得每次尋道時(shí)所用的時(shí)間都最短，但不能保證平均周轉(zhuǎn)時(shí)間及帶權(quán)周轉(zhuǎn)時(shí)間最短。（3）電梯算法（SCAN）此算法同時(shí)考慮下一個(gè)作業(yè)磁道請(qǐng)求與當(dāng)前磁頭位置的距離和當(dāng)前磁頭移動(dòng)方向。本設(shè)計(jì)默認(rèn)磁頭當(dāng)前移動(dòng)方向?yàn)樽詢?nèi)向外，故SCAN算法先選擇當(dāng)前磁頭之外距離其最近的磁道進(jìn)行訪問，直到再無更外的磁道請(qǐng)求，再將磁臂換向，訪問磁頭內(nèi)側(cè)距離當(dāng)前磁頭位置最近的作業(yè)磁道請(qǐng)求。此算法避免了饑餓現(xiàn)象的出現(xiàn)，每個(gè)作業(yè)的磁盤請(qǐng)求都可以得到處理，且使每次尋道時(shí)間相對(duì)較短。（4）環(huán)形掃描算法（C_SCAN）此算法磁頭移動(dòng)方向一直為自內(nèi)向外，同時(shí)考慮下一個(gè)作業(yè)磁道請(qǐng)求與當(dāng)前磁頭位置的距離最短。先選擇當(dāng)前磁頭之外距離其最近的磁道進(jìn)行訪問，直到再無更外的磁道請(qǐng)求，再直接將磁頭移到最內(nèi)側(cè)磁道（此過程快速移動(dòng)，并不訪問任何磁道），再由內(nèi)向外順次訪問距離當(dāng)前磁頭位置最近的作業(yè)磁道請(qǐng)求。此算法每個(gè)作業(yè)的磁盤請(qǐng)求都可以得到處理，且使每次尋道時(shí)間相對(duì)較短。由于該方法一直保持磁頭移動(dòng)尋訪方向不變，對(duì)兩端磁道請(qǐng)求比較有利。（5）N_SCAN算法此算法同時(shí)考慮下一個(gè)作業(yè)磁道請(qǐng)求與當(dāng)前磁頭位置的距離和當(dāng)前磁頭移動(dòng)方向，但每次磁臂調(diào)轉(zhuǎn)方向時(shí)，將同時(shí)處理在磁頭向一側(cè)移動(dòng)過程當(dāng)中輸入的作業(yè)請(qǐng)求。本設(shè)計(jì)默認(rèn)磁頭當(dāng)前移動(dòng)方向?yàn)樽詢?nèi)向外，先選擇當(dāng)前磁頭之外距離其最近的磁道進(jìn)行訪問，直到再無更外的磁道請(qǐng)求，接下來一并考慮在磁頭向外側(cè)移動(dòng)過程當(dāng)中輸入的作業(yè)請(qǐng)求與磁頭內(nèi)側(cè)未被處理的作業(yè)磁道請(qǐng)求。此算法對(duì)中間磁道請(qǐng)求比較有利。2論證結(jié)果： 本設(shè)計(jì)輸入當(dāng)前磁頭位置及一組作業(yè)磁道請(qǐng)求。選擇所需的算法，輸出相應(yīng)結(jié)果：（1）先來先服務(wù)算法（FCFS） 按輸入順序輸出訪問序列。（2）最短尋道時(shí)間優(yōu)先算法（SSTF）依次輸出距離當(dāng)前磁頭位置最近的磁道請(qǐng)求。（3）電梯算法（SCAN）先按照從小到大的順序輸出所輸入的當(dāng)前磁頭位置外側(cè)的磁道請(qǐng)求，再按照從大到小的順序輸出所輸入的當(dāng)前磁頭位置內(nèi)側(cè)的磁道請(qǐng)求。（4）環(huán)形掃描算法（C_SCAN）先按照從小到大的順序輸出所輸入的當(dāng)前磁頭位置外側(cè)的磁道請(qǐng)求，再按照從小到大的順序輸出所輸入的當(dāng)前磁頭位置內(nèi)側(cè)的磁道請(qǐng)求。（5）N_SCAN算法先按照從小到大的順序輸出所輸入的當(dāng)前磁頭位置外側(cè)的磁道請(qǐng)求，再按照從大到小的順序輸出在磁頭向外側(cè)移動(dòng)過程當(dāng)中輸入的作業(yè)請(qǐng)求與所輸入的當(dāng)前磁頭位置內(nèi)側(cè)的磁道請(qǐng)求。三、系統(tǒng)的原理框圖1總體框圖：本系統(tǒng)劃分為五個(gè)模塊：先來先服務(wù)算法模塊FCFS(int track)、最短尋道時(shí)間算法模塊SSTF(int correnttrack,int track)、電梯算法模塊SCAN(int correnttrack,int track)、環(huán)形掃描算法模塊C_SCAN(int correnttrack,int track)及N_SCAN算法模塊N_SCAN(int correnttrack,int track)?？傮w框圖：圖1 總體框圖2模塊框圖： （1）先來先服務(wù)算法模塊void FCFS(int track)直接根據(jù)作業(yè)請(qǐng)求磁盤的先后順序?qū)Υ疟P進(jìn)行尋訪。此算法公平、簡單，每個(gè)作業(yè)的磁盤請(qǐng)求都可以得到處理，不會(huì)出現(xiàn)某個(gè)作業(yè)的請(qǐng)求長期得不到滿足的情況。先來先服務(wù)算法流程圖：圖2 先來先服務(wù)算法模塊流程圖（2）最短尋道時(shí)間優(yōu)先算法模塊void SSTF(int correnttrack,int track)優(yōu)先選擇距離當(dāng)前磁頭位置最近的作業(yè)磁道請(qǐng)求，可以使得每次尋道時(shí)所用的時(shí)間都最短。最短尋道時(shí)間優(yōu)先算法流程圖:圖3最短尋道時(shí)間優(yōu)先算法模塊流程圖（3）電梯算法模塊void SCAN(int correnttrack,int track)默認(rèn)磁頭當(dāng)前移動(dòng)方向?yàn)樽詢?nèi)向外，先選擇當(dāng)前磁頭之外距離其最近的磁道進(jìn)行訪問，直到再無更外的磁道請(qǐng)求，再將磁臂換向，訪問磁頭內(nèi)側(cè)距離當(dāng)前磁頭位置最近的作業(yè)磁道請(qǐng)求。電梯算法流程圖：圖4 電梯算法模塊流程圖（4）環(huán)形掃描算法模塊void C_SCAN(int correnttrack,int track)先選擇當(dāng)前磁頭之外距離其最近的磁道進(jìn)行訪問，直到再無更外的磁道請(qǐng)求，再直接將磁頭移到最內(nèi)側(cè)磁道（此過程快速移動(dòng)，并不訪問任何磁道），再由內(nèi)向外順次訪問距離當(dāng)前磁頭位置最近的作業(yè)磁道請(qǐng)求。一直保持磁頭移動(dòng)尋訪方向不變，對(duì)兩端磁道請(qǐng)求比較有利。環(huán)形掃描算法流程圖：圖5 環(huán)形掃描算法模塊流程圖（5）N_SCAN算法模塊void N_SCAN(int correnttrack,int track)本設(shè)計(jì)默認(rèn)磁頭當(dāng)前移動(dòng)方向?yàn)樽詢?nèi)向外，先選擇當(dāng)前磁頭之外距離其最近的磁道進(jìn)行訪問，直到再無更外的磁道請(qǐng)求，接下來一并考慮在磁頭向外側(cè)移動(dòng)過程當(dāng)中輸入的作業(yè)請(qǐng)求與磁頭內(nèi)側(cè)未被處理的作業(yè)磁道請(qǐng)求。此算法對(duì)中間磁道請(qǐng)求比較有利。N_SCAN算法流程圖：圖6 N_SCAN算法模塊流程圖（1）圖7 N_SCAN算法模塊流程圖（2）四、設(shè)計(jì)程序1主要模塊代碼：（1）先來先服務(wù)算法void FCFS(int track)直接根據(jù)作業(yè)請(qǐng)求磁盤的先后順序?qū)Υ疟P進(jìn)行尋訪。先來先服務(wù)算法代碼：void FCFS(int track)int k;for(k=0;k,trackk);printf(%d,track9);（2）最短尋道時(shí)間優(yōu)先算法void SSTF(int correnttrack,int track)優(yōu)先選擇距離當(dāng)前磁頭位置最近的作業(yè)磁道請(qǐng)求。最短尋道時(shí)間優(yōu)先算法代碼：void SSTF(int correnttrack,int track)int Line10;int i;int j;int d;int min_d;int k;int corrent; min_d=abs(correnttrack-track0); k=0;corrent=correnttrack;for(i=0;i10;i+)for(j=0;j10;j+)if(trackj!=-1)d=abs(corrent-trackj);if(d,correnttrack);Print(Line);（3）電梯算法void SCAN(int correnttrack,int track)默認(rèn)磁頭當(dāng)前移動(dòng)方向?yàn)樽詢?nèi)向外，先選擇當(dāng)前磁頭之外距離其最近的磁道進(jìn)行訪問，直到再無更外的磁道請(qǐng)求，再將磁臂換向，訪問磁頭內(nèi)側(cè)距離當(dāng)前磁頭位置最近的作業(yè)磁道請(qǐng)求。電梯算法代碼：void SCAN(int correnttrack,int track)int Line10;int dLine10;int i;int j;int k; int min; k=0; min=track0;for(i=0;i10;i+)for(j=0;j10;j+)if(trackj!=-1)if(trackjmin)min=trackj;k=j;dLinei=trackk;trackk=-1;min=65536;k=0;for(i=0;idLinei)k=k+1; j=k;for(i=0;i10-k;i+)Linei=dLinej;j=j+1;j=k-1;for(i=10-k;i10;i+)Linei=dLinej;j=j-1;Print(Line);（4）環(huán)形掃描算法void C_SCAN(int correnttrack,int track)先選擇當(dāng)前磁頭之外距離其最近的磁道進(jìn)行訪問，直到再無更外的磁道請(qǐng)求，再直接將磁頭移到最內(nèi)側(cè)磁道（此過程快速移動(dòng)，并不訪問任何磁道），再由內(nèi)向外順次訪問距離當(dāng)前磁頭位置最近的作業(yè)磁道請(qǐng)求。環(huán)形掃描算法代碼：void C_SCAN(int correnttrack,int track)int Line10;int dLine10;int i;int j;int k; int min; k=0; min=track0;for(i=0;i10;i+)for(j=0;j10;j+)if(trackj!=-1)if(trackjmin)min=trackj;k=j;dLinei=trackk;trackk=-1;min=65536;k=0;for(i=0;idLinei)k=k+1; j=k;for(i=0;i10-k;i+)Linei=dLinej;j=j+1;j=0;for(i=10-k;i10;i+)Linei=dLinej;j=j+1;Print(Line);（5）N_SCAN算法void N_SCAN(int correnttrack,int track)默認(rèn)磁頭當(dāng)前移動(dòng)方向?yàn)樽詢?nèi)向外，先選擇當(dāng)前磁頭之外距離其最近的磁道進(jìn)行訪問，直到再無更外的磁道請(qǐng)求，接下來一并考慮在磁頭向外側(cè)移動(dòng)過程當(dāng)中輸入的作業(yè)請(qǐng)求與磁頭內(nèi)側(cè)未被處理的作業(yè)磁道請(qǐng)求。N_SCAN算法void N_SCAN(int correnttrack,int track)int Line10;int dLine10;int lLine10;int i;int j;int k; int min,max;int choice;for(k=0;k10;k+)lLinek=-1; k=0;min=track0;for(i=0;i10;i+)for(j=0;j10;j+)if(trackj!=-1)if(trackjmin)min=trackj;k=j;dLinei=trackk;trackk=-1;min=65536;k=0;for(i=0;idLinei)k=k+1; j=k;for(i=0;i,Linei);Linei=-1;j=j+1; j=k-1;for(i=10-k;i10;i+)Linei=dLinej;j=j-1;printf(n是否還有作業(yè)請(qǐng)求（1-是；0-否）：n);scanf(%d,&choice); k=9-k;while(choice=1)printf(n請(qǐng)輸入作業(yè)的磁道請(qǐng)求：n);scanf(%d,&Linek);k=k-1; printf(n是否還有作業(yè)請(qǐng)求（1-是；0-否）：n); scanf(%d,&choice);printf(n磁頭繼續(xù)移動(dòng)軌跡為：n); k=9; max=Line9;for(i=0;i10;i+)for(j=0;jmax)max=Linej;k=j;lLinei=Linek;Linek=-1;max=0;for(i=0;i,lLinei);printf(%d,lLine9);2總模塊代碼：void main()int track10;int n;int correnttrack;int choice=1;printf(n*磁盤調(diào)度模擬系統(tǒng)*);while(choice=1)printf(n請(qǐng)輸入當(dāng)前磁道號(hào)：);scanf(%d,&correnttrack);printf(n請(qǐng)輸入一組作業(yè)的磁道請(qǐng)求：n);scanf(%d %d %d %d %d %d %d %d %d %d, &track0,&track1,&track2,&track3,&track4, &track5,&track6,&track7,&track8,&track9);printf(n請(qǐng)選擇算法：n); printf(t1.先來先服務(wù)算法(FCFS)n); printf(t2.最短尋道時(shí)間優(yōu)先算法(SSTF)n);printf(t3.電梯算法(SCAN)n);printf(t4.環(huán)形掃描算法(C_SCAN)n);printf(t5.(N_SCAN)n); scanf(%d,&n);printf(nn);switch(n)case 1: printf(*先來先服務(wù)算法(FCFS)*n磁頭移動(dòng)軌跡為：n);FCFS(track);break;case 2: printf(*最短尋道時(shí)間優(yōu)先算法(SSTF)*n磁頭移動(dòng)軌跡為：n);SSTF(correnttrack,track);break;case 3: printf(*電梯算法(SCAN)*n磁頭移動(dòng)軌跡為：n); SCAN(correnttrack,track);break;case 4: printf(*環(huán)形掃描算法(C_SCAN)*n磁頭移動(dòng)軌跡為：n); C_SCAN(correnttrack,track);break;case 5: printf(*N_SCAN*n磁頭移動(dòng)軌跡為：n); N_SCAN(correnttrack,track);break;printf(n請(qǐng)問是否繼續(xù)?（1-繼續(xù)；0-退出）n); scanf(%d,&choice);五、實(shí)驗(yàn)結(jié)果1總模塊實(shí)驗(yàn)結(jié)果：程序開始運(yùn)行，將出現(xiàn)輸入選擇界面;圖8 主界面2基礎(chǔ)模塊實(shí)驗(yàn)結(jié)果：（1）先來先服務(wù)算法（First-Come，F(xiàn)irst-Served，F(xiàn)CFS）按輸入順序輸出訪問序列。選擇該算法后，將輸出相應(yīng)磁頭移動(dòng)軌跡：圖9 先來先服務(wù)算法0 輸出結(jié)果為69- 23- 120- 45- 77- 31- 55- 99- 150- 2 滿足要求。（2）最短尋道時(shí)間優(yōu)先算法（Shortest Seek Time First，SSTF）依次輸出距離當(dāng)前磁頭位置最近的磁道請(qǐng)求。選擇該算法后，將輸出相應(yīng)磁頭移動(dòng)軌跡：圖10 最短尋道優(yōu)先算法 輸出結(jié)果為45- 55- 69- 77- 99- 120- 150- 31- 23- 2 滿足要求。（3）電梯算法（SCAN）先按照從小到大的順序輸出所輸入的當(dāng)前磁頭位置外側(cè)的磁道請(qǐng)求，再按照從大到小的順序輸出所輸入的當(dāng)前磁頭位置內(nèi)側(cè)的磁道請(qǐng)求。選擇該算法后，將輸出相應(yīng)磁頭移動(dòng)軌跡：圖11 電梯算法 輸出結(jié)果為55- 69- 77- 99- 120- 150- 45- 31- 23- 2 滿足要求。3擴(kuò)展模塊實(shí)驗(yàn)結(jié)果：（1）環(huán)形掃描算法（C_SCAN）先按照從小到大的順序輸出所輸入的當(dāng)前磁頭位置外側(cè)的磁道請(qǐng)求，再按照從小到大的順序輸出所輸入的當(dāng)前磁頭位置內(nèi)側(cè)的磁道請(qǐng)求。選擇該算法后，將輸出相應(yīng)磁頭移動(dòng)軌跡：圖12 環(huán)形掃描算法 輸出結(jié)果為55- 69- 77- 99- 120- 150- 2- 23- 31- 45 滿足要求。（2）N_SCAN算法先按照從小到大的順序輸出所輸入的當(dāng)前磁頭位置外側(cè)的磁道請(qǐng)求，再按照從大到小的順序輸出在磁頭向外側(cè)移動(dòng)過程當(dāng)中輸入的作業(yè)請(qǐng)求與所輸入的當(dāng)前磁頭位置內(nèi)側(cè)的磁道請(qǐng)求。選擇該算法后，將輸出相應(yīng)磁頭移動(dòng)軌跡：圖13 N_SCAN算法 輸出結(jié)果為55- 69- 77- 99- 120- 150- 88- 45- 31- 23- 8 - 2- 1 滿足要求。六、調(diào)試分析及故障處理1調(diào)試分析：（1）在代碼中錯(cuò)誤的使用了中文括號(hào)“）”，導(dǎo)致程序出錯(cuò)。圖14 錯(cuò)誤報(bào)告（2）在定義函數(shù)時(shí)誤在結(jié)尾處加分號(hào)“;”，導(dǎo)致調(diào)試過程中出錯(cuò)。圖15 錯(cuò)誤報(bào)告（3）由于未對(duì)變量初始化，導(dǎo)致錯(cuò)誤：圖16 錯(cuò)誤警告未對(duì)k初始化，如下圖：圖17 變量表2故障處理：重新檢查代碼，發(fā)現(xiàn)錯(cuò)誤，并及時(shí)修正。調(diào)試后無誤：圖18 無錯(cuò)誤及警告發(fā)生故障時(shí)，可采取單步調(diào)試的方法，逐條語句檢查，修正錯(cuò)誤。圖19 故障處理過程七、設(shè)計(jì)結(jié)論磁盤，是一種很重要也很常用的外設(shè)，其分配也有一定的分配策略。在操作系統(tǒng)中，作業(yè)對(duì)磁盤的請(qǐng)求常常要排隊(duì)，由此需要一些高效率的磁盤分配策略算法。本系統(tǒng)設(shè)計(jì)了五種尋道策略，其中先來先服務(wù)算法為一種最簡單的磁盤調(diào)度算法，它直接根據(jù)作業(yè)請(qǐng)求磁盤的先后順序?qū)Υ疟P進(jìn)行尋訪，公平、簡單，每個(gè)作業(yè)的磁盤請(qǐng)求都可以得到處理，不會(huì)出現(xiàn)某個(gè)作業(yè)的請(qǐng)求長期得不到滿足的情況，但未對(duì)尋道方案進(jìn)行優(yōu)化，故平均周轉(zhuǎn)時(shí)間及帶權(quán)周轉(zhuǎn)時(shí)間都會(huì)較長；最短尋道時(shí)間優(yōu)先算法優(yōu)先選擇距離當(dāng)前磁頭位置最近的作業(yè)磁道請(qǐng)求，可以使得每次尋道時(shí)所用的時(shí)間都最短，但不能保證平均周轉(zhuǎn)時(shí)間及帶權(quán)周轉(zhuǎn)時(shí)間最短；電梯算法同時(shí)考慮下一個(gè)作業(yè)磁道請(qǐng)求與當(dāng)前磁頭位置的距離和當(dāng)前磁頭移動(dòng)方向先選擇當(dāng)前磁頭之外距離其最近的磁道進(jìn)行訪問，直到再無更外的磁道請(qǐng)求，再將磁臂換向，訪問磁頭內(nèi)側(cè)距離當(dāng)前磁頭位置最近的作業(yè)磁道請(qǐng)求，避免了饑餓現(xiàn)象的出現(xiàn)，每個(gè)作業(yè)的磁盤請(qǐng)求都可以得到處理，且使每次尋道時(shí)間相對(duì)較短；環(huán)形掃描算法的