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

1、目錄一、設(shè)計任務(wù)及主要技術(shù)3二、設(shè)計方案及論證結(jié)果4三、系統(tǒng)的原理框圖5四、設(shè)計程序12五、實驗結(jié)果20六、調(diào)試分析及故障處理24七、設(shè)計結(jié)論25八、心得體會261、 設(shè)計任務(wù)及主要技術(shù)1整體功能概述（設(shè)計任務(wù)）： 磁盤是外設(shè)中一個很常用的部分，所以，對磁盤數(shù)據(jù)的尋道時間的長短可以直接影響機器的整體運行速度的快慢。本設(shè)計為一個模擬磁盤調(diào)度算法的磁盤調(diào)度模擬系統(tǒng)，能夠模擬先來先服務(wù)（FCFS）算法、最短尋道時間（SSTF）算法、電梯（SCAN）算法、環(huán)形掃描（C_SCAN）算法及N_SCAN算法五個磁盤調(diào)度算法，輸入為一組作業(yè)的磁道請求，輸出為按選擇的算法執(zhí)行時的磁頭移動軌跡。其中，先來先服務(wù)（

2、FCFS）算法、最短尋道時間（SSTF）算法、電梯（SCAN）算法為基本算法，環(huán)形掃描（C_SCAN）算法及N_SCAN算法為擴展算法。2運行環(huán)境：（1）硬件環(huán)境 Intel core i5 CPU （2）軟件環(huán)境 Windows 7 Microsoft Visual C+ 6.03主要技術(shù)：（1）用C語言編寫程序；（2）對編程軟件Microsoft Visual C+ 6.0的了解和使用；（3）操作系統(tǒng)基礎(chǔ)知識（主要是對先來先服務(wù)（FCFS）算法、最短尋道時間（SSTF）算法、電梯（SCAN）算法的了解）；（4）操作系統(tǒng)擴展知識（通過網(wǎng)絡(luò)自學環(huán)形掃描（C_SCAN）算法及N_SCAN算法）。

3、二、設(shè)計方案及論證結(jié)果1設(shè)計方案：（1）先來先服務(wù)算法（First-Come，F(xiàn)irst-Served，F(xiàn)CFS）此算法為一種最簡單的磁盤調(diào)度算法。它直接根據(jù)作業(yè)請求磁盤的先后順序?qū)Υ疟P進行尋訪。此算法公平、簡單，每個作業(yè)的磁盤請求都可以得到處理，不會出現(xiàn)某個作業(yè)的請求長期得不到滿足的情況。但此算法未對尋道方案進行優(yōu)化，故平均周轉(zhuǎn)時間及帶權(quán)周轉(zhuǎn)時間都會較長。（2）最短尋道時間優(yōu)先算法（Shortest Seek Time First，SSTF）此算法優(yōu)先選擇距離當前磁頭位置最近的作業(yè)磁道請求。此算法可以使得每次尋道時所用的時間都最短，但不能保證平均周轉(zhuǎn)時間及帶權(quán)周轉(zhuǎn)時間最短。（3）電梯算法（S

4、CAN）此算法同時考慮下一個作業(yè)磁道請求與當前磁頭位置的距離和當前磁頭移動方向。本設(shè)計默認磁頭當前移動方向為自內(nèi)向外，故SCAN算法先選擇當前磁頭之外距離其最近的磁道進行訪問，直到再無更外的磁道請求，再將磁臂換向，訪問磁頭內(nèi)側(cè)距離當前磁頭位置最近的作業(yè)磁道請求。此算法避免了饑餓現(xiàn)象的出現(xiàn)，每個作業(yè)的磁盤請求都可以得到處理，且使每次尋道時間相對較短。（4）環(huán)形掃描算法（C_SCAN）此算法磁頭移動方向一直為自內(nèi)向外，同時考慮下一個作業(yè)磁道請求與當前磁頭位置的距離最短。先選擇當前磁頭之外距離其最近的磁道進行訪問，直到再無更外的磁道請求，再直接將磁頭移到最內(nèi)側(cè)磁道（此過程快速移動，并不訪問任何磁道）

5、，再由內(nèi)向外順次訪問距離當前磁頭位置最近的作業(yè)磁道請求。此算法每個作業(yè)的磁盤請求都可以得到處理，且使每次尋道時間相對較短。由于該方法一直保持磁頭移動尋訪方向不變，對兩端磁道請求比較有利。（5）N_SCAN算法此算法同時考慮下一個作業(yè)磁道請求與當前磁頭位置的距離和當前磁頭移動方向，但每次磁臂調(diào)轉(zhuǎn)方向時，將同時處理在磁頭向一側(cè)移動過程當中輸入的作業(yè)請求。本設(shè)計默認磁頭當前移動方向為自內(nèi)向外，先選擇當前磁頭之外距離其最近的磁道進行訪問，直到再無更外的磁道請求，接下來一并考慮在磁頭向外側(cè)移動過程當中輸入的作業(yè)請求與磁頭內(nèi)側(cè)未被處理的作業(yè)磁道請求。此算法對中間磁道請求比較有利。2論證結(jié)果： 本設(shè)計輸入當

6、前磁頭位置及一組作業(yè)磁道請求。選擇所需的算法，輸出相應(yīng)結(jié)果：（1）先來先服務(wù)算法（FCFS） 按輸入順序輸出訪問序列。（2）最短尋道時間優(yōu)先算法（SSTF）依次輸出距離當前磁頭位置最近的磁道請求。（3）電梯算法（SCAN）先按照從小到大的順序輸出所輸入的當前磁頭位置外側(cè)的磁道請求，再按照從大到小的順序輸出所輸入的當前磁頭位置內(nèi)側(cè)的磁道請求。（4）環(huán)形掃描算法（C_SCAN）先按照從小到大的順序輸出所輸入的當前磁頭位置外側(cè)的磁道請求，再按照從小到大的順序輸出所輸入的當前磁頭位置內(nèi)側(cè)的磁道請求。（5）N_SCAN算法先按照從小到大的順序輸出所輸入的當前磁頭位置外側(cè)的磁道請求，再按照從大到小的順序輸

7、出在磁頭向外側(cè)移動過程當中輸入的作業(yè)請求與所輸入的當前磁頭位置內(nèi)側(cè)的磁道請求。三、系統(tǒng)的原理框圖1總體框圖：本系統(tǒng)劃分為五個模塊：先來先服務(wù)算法模塊FCFS(int track)、最短尋道時間算法模塊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)。總體框圖：圖1 總體框圖2模塊框圖：（1）先來先服務(wù)算法模塊void FCFS(

8、int track)直接根據(jù)作業(yè)請求磁盤的先后順序?qū)Υ疟P進行尋訪。此算法公平、簡單，每個作業(yè)的磁盤請求都可以得到處理，不會出現(xiàn)某個作業(yè)的請求長期得不到滿足的情況。先來先服務(wù)算法流程圖：圖2 先來先服務(wù)算法模塊流程圖（2）最短尋道時間優(yōu)先算法模塊void SSTF(int correnttrack,int track)優(yōu)先選擇距離當前磁頭位置最近的作業(yè)磁道請求，可以使得每次尋道時所用的時間都最短。最短尋道時間優(yōu)先算法流程圖:圖3最短尋道時間優(yōu)先算法模塊流程圖（3）電梯算法模塊void SCAN(int correnttrack,int track)默認磁頭當前移動方向為自內(nèi)向外，先選擇當前磁頭之

9、外距離其最近的磁道進行訪問，直到再無更外的磁道請求，再將磁臂換向，訪問磁頭內(nèi)側(cè)距離當前磁頭位置最近的作業(yè)磁道請求。電梯算法流程圖：圖4 電梯算法模塊流程圖（4）環(huán)形掃描算法模塊void C_SCAN(int correnttrack,int track)先選擇當前磁頭之外距離其最近的磁道進行訪問，直到再無更外的磁道請求，再直接將磁頭移到最內(nèi)側(cè)磁道（此過程快速移動，并不訪問任何磁道），再由內(nèi)向外順次訪問距離當前磁頭位置最近的作業(yè)磁道請求。一直保持磁頭移動尋訪方向不變，對兩端磁道請求比較有利。環(huán)形掃描算法流程圖：圖5 環(huán)形掃描算法模塊流程圖（5）N_SCAN算法模塊void N_SCAN(int

10、correnttrack,int track)本設(shè)計默認磁頭當前移動方向為自內(nèi)向外，先選擇當前磁頭之外距離其最近的磁道進行訪問，直到再無更外的磁道請求，接下來一并考慮在磁頭向外側(cè)移動過程當中輸入的作業(yè)請求與磁頭內(nèi)側(cè)未被處理的作業(yè)磁道請求。此算法對中間磁道請求比較有利。N_SCAN算法流程圖：圖6 N_SCAN算法模塊流程圖（1）圖7 N_SCAN算法模塊流程圖（2）四、設(shè)計程序1主要模塊代碼：（1）先來先服務(wù)算法void FCFS(int track)直接根據(jù)作業(yè)請求磁盤的先后順序?qū)Υ疟P進行尋訪。先來先服務(wù)算法代碼：void FCFS(int track)int k;for(k=0;k<

11、9;k+)printf("%d->",trackk);printf("%d",track9);（2）最短尋道時間優(yōu)先算法void SSTF(int correnttrack,int track)優(yōu)先選擇距離當前磁頭位置最近的作業(yè)磁道請求。最短尋道時間優(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=corren

12、ttrack;for(i=0;i<10;i+)for(j=0;j<10;j+)if(trackj!=-1)d=abs(corrent-trackj);if(d<min_d)min_d=d;k=j;Linei=trackk;corrent=Linei;trackk=-1;min_d=65536;printf("%d->",correnttrack);Print(Line);（3）電梯算法void SCAN(int correnttrack,int track)默認磁頭當前移動方向為自內(nèi)向外，先選擇當前磁頭之外距離其最近的磁道進行訪問，直到再無更外的磁道

13、請求，再將磁臂換向，訪問磁頭內(nèi)側(cè)距離當前磁頭位置最近的作業(yè)磁道請求。電梯算法代碼：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;i<10;i+)for(j=0;j<10;j+)if(trackj!=-1)if(trackj<min)min=trackj;k=j;dLinei=trackk;trackk=-1;min=65536;k=0;for(i=0;i<10;i+)if(correnttrac

14、k>dLinei)k=k+1; j=k;for(i=0;i<10-k;i+)Linei=dLinej;j=j+1;j=k-1;for(i=10-k;i<10;i+)Linei=dLinej;j=j-1;Print(Line);（4）環(huán)形掃描算法void C_SCAN(int correnttrack,int track)先選擇當前磁頭之外距離其最近的磁道進行訪問，直到再無更外的磁道請求，再直接將磁頭移到最內(nèi)側(cè)磁道（此過程快速移動，并不訪問任何磁道），再由內(nèi)向外順次訪問距離當前磁頭位置最近的作業(yè)磁道請求。環(huán)形掃描算法代碼：void C_SCAN(int correnttrack

15、,int track)int Line10;int dLine10;int i;int j;int k; int min; k=0; min=track0;for(i=0;i<10;i+)for(j=0;j<10;j+)if(trackj!=-1)if(trackj<min)min=trackj;k=j;dLinei=trackk;trackk=-1;min=65536;k=0;for(i=0;i<10;i+)if(correnttrack>dLinei)k=k+1; j=k;for(i=0;i<10-k;i+)Linei=dLinej;j=j+1;j=0;

16、for(i=10-k;i<10;i+)Linei=dLinej;j=j+1;Print(Line);（5）N_SCAN算法void N_SCAN(int correnttrack,int track)默認磁頭當前移動方向為自內(nèi)向外，先選擇當前磁頭之外距離其最近的磁道進行訪問，直到再無更外的磁道請求，接下來一并考慮在磁頭向外側(cè)移動過程當中輸入的作業(yè)請求與磁頭內(nèi)側(cè)未被處理的作業(yè)磁道請求。N_SCAN算法void N_SCAN(int correnttrack,int track)int Line10;int dLine10;int lLine10;int i;int j;int k; int

17、 min,max;int choice;for(k=0;k<10;k+)lLinek=-1; k=0;min=track0;for(i=0;i<10;i+)for(j=0;j<10;j+)if(trackj!=-1)if(trackj<min)min=trackj;k=j;dLinei=trackk;trackk=-1;min=65536;k=0;for(i=0;i<10;i+)if(correnttrack>dLinei)k=k+1; j=k;for(i=0;i<10-k;i+)Linei=dLinej;printf("%d->&qu

18、ot;,Linei);Linei=-1;j=j+1; j=k-1;for(i=10-k;i<10;i+)Linei=dLinej;j=j-1;printf("n是否還有作業(yè)請求（1-是；0-否）：n");scanf("%d",&choice); k=9-k;while(choice=1)printf("n請輸入作業(yè)的磁道請求：n");scanf("%d",&Linek);k=k-1; printf("n是否還有作業(yè)請求（1-是；0-否）：n"); scanf("%

19、d",&choice);printf("n磁頭繼續(xù)移動軌跡為：n"); k=9; max=Line9;for(i=0;i<10;i+)for(j=0;j<10;j+)if(Linej>max)max=Linej;k=j;lLinei=Linek;Linek=-1;max=0;for(i=0;i<9;i+)if(lLinei!=-1)printf("%d->",lLinei);printf("%d",lLine9);2總模塊代碼：void main()int track10;int n;i

20、nt correnttrack;int choice=1;printf("n*磁盤調(diào)度模擬系統(tǒng)*");while(choice=1)printf("n請輸入當前磁道號：");scanf("%d",&correnttrack);printf("n請輸入一組作業(yè)的磁道請求<以回車分隔>：n");scanf("%d %d %d %d %d %d %d %d %d %d", &track0,&track1,&track2,&track3,&tr

21、ack4, &track5,&track6,&track7,&track8,&track9);printf("n請選擇算法：n"); printf("t1.先來先服務(wù)算法(FCFS)n"); printf("t2.最短尋道時間優(yōu)先算法(SSTF)n");printf("t3.電梯算法(SCAN)n");printf("t4.環(huán)形掃描算法(C_SCAN)n");printf("t5.(N_SCAN)n"); scanf("%d&

22、quot;,&n);printf("nn");switch(n)case 1: printf("*先來先服務(wù)算法(FCFS)*n磁頭移動軌跡為：n");FCFS(track);break;case 2: printf("*最短尋道時間優(yōu)先算法(SSTF)*n磁頭移動軌跡為：n");SSTF(correnttrack,track);break;case 3: printf("*電梯算法(SCAN)*n磁頭移動軌跡為：n"); SCAN(correnttrack,track);break;case 4: pri

23、ntf("*環(huán)形掃描算法(C_SCAN)*n磁頭移動軌跡為：n"); C_SCAN(correnttrack,track);break;case 5: printf("*N_SCAN*n磁頭移動軌跡為：n"); N_SCAN(correnttrack,track);break;printf("n請問是否繼續(xù)?（1-繼續(xù)；0-退出）n"); scanf("%d",&choice);五、實驗結(jié)果1總模塊實驗結(jié)果：程序開始運行，將出現(xiàn)輸入選擇界面;圖8 主界面2基礎(chǔ)模塊實驗結(jié)果：（1）先來先服務(wù)算法（First-

24、Come，F(xiàn)irst-Served，F(xiàn)CFS）按輸入順序輸出訪問序列。選擇該算法后，將輸出相應(yīng)磁頭移動軌跡：圖9 先來先服務(wù)算法0 輸出結(jié)果為69-> 23-> 120-> 45-> 77-> 31-> 55-> 99-> 150-> 2 滿足要求。（2）最短尋道時間優(yōu)先算法（Shortest Seek Time First，SSTF）依次輸出距離當前磁頭位置最近的磁道請求。選擇該算法后，將輸出相應(yīng)磁頭移動軌跡：圖10 最短尋道優(yōu)先算法 輸出結(jié)果為45-> 55-> 69-> 77-> 99-> 120->

25、; 150-> 31-> 23-> 2 滿足要求。（3）電梯算法（SCAN）先按照從小到大的順序輸出所輸入的當前磁頭位置外側(cè)的磁道請求，再按照從大到小的順序輸出所輸入的當前磁頭位置內(nèi)側(cè)的磁道請求。選擇該算法后，將輸出相應(yīng)磁頭移動軌跡：圖11 電梯算法 輸出結(jié)果為55-> 69-> 77-> 99-> 120-> 150-> 45-> 31-> 23-> 2 滿足要求。3擴展模塊實驗結(jié)果：（1）環(huán)形掃描算法（C_SCAN）先按照從小到大的順序輸出所輸入的當前磁頭位置外側(cè)的磁道請求，再按照從小到大的順序輸出所輸入的當前磁頭位置

26、內(nèi)側(cè)的磁道請求。選擇該算法后，將輸出相應(yīng)磁頭移動軌跡：圖12 環(huán)形掃描算法 輸出結(jié)果為55-> 69-> 77-> 99-> 120-> 150-> 2-> 23-> 31-> 45 滿足要求。（2）N_SCAN算法先按照從小到大的順序輸出所輸入的當前磁頭位置外側(cè)的磁道請求，再按照從大到小的順序輸出在磁頭向外側(cè)移動過程當中輸入的作業(yè)請求與所輸入的當前磁頭位置內(nèi)側(cè)的磁道請求。選擇該算法后，將輸出相應(yīng)磁頭移動軌跡：圖13 N_SCAN算法 輸出結(jié)果為55-> 69-> 77-> 99-> 120-> 150->

27、; 88-> 45-> 31-> 23-> 8 -> 2-> 1 滿足要求。六、調(diào)試分析及故障處理1調(diào)試分析：（1）在代碼中錯誤的使用了中文括號“）”，導致程序出錯。圖14 錯誤報告（2）在定義函數(shù)時誤在結(jié)尾處加分號“;”，導致調(diào)試過程中出錯。圖15 錯誤報告（3）由于未對變量初始化，導致錯誤：圖16 錯誤警告未對k初始化，如下圖：圖17 變量表2故障處理：重新檢查代碼，發(fā)現(xiàn)錯誤，并及時修正。調(diào)試后無誤：圖18 無錯誤及警告發(fā)生故障時，可采取單步調(diào)試的方法，逐條語句檢查，修正錯誤。圖19 故障處理過程七、設(shè)計結(jié)論磁盤，是一種很重要也很常用的外設(shè)，其分配也有一

28、定的分配策略。在操作系統(tǒng)中，作業(yè)對磁盤的請求常常要排隊，由此需要一些高效率的磁盤分配策略算法。本系統(tǒng)設(shè)計了五種尋道策略，其中先來先服務(wù)算法為一種最簡單的磁盤調(diào)度算法，它直接根據(jù)作業(yè)請求磁盤的先后順序?qū)Υ疟P進行尋訪，公平、簡單，每個作業(yè)的磁盤請求都可以得到處理，不會出現(xiàn)某個作業(yè)的請求長期得不到滿足的情況，但未對尋道方案進行優(yōu)化，故平均周轉(zhuǎn)時間及帶權(quán)周轉(zhuǎn)時間都會較長；最短尋道時間優(yōu)先算法優(yōu)先選擇距離當前磁頭位置最近的作業(yè)磁道請求，可以使得每次尋道時所用的時間都最短，但不能保證平均周轉(zhuǎn)時間及帶權(quán)周轉(zhuǎn)時間最短；電梯算法同時考慮下一個作業(yè)磁道請求與當前磁頭位置的距離和當前磁頭移動方向先選擇當前磁頭之外距