磁盤調(diào)度算法設(shè)計(jì)報(bào)告

1、操作系統(tǒng)課程設(shè)計(jì)報(bào)告題目：磁盤調(diào)度算法院系：信息學(xué)院班級(jí)：信管11-2姓名：王裕辰學(xué)號(hào)：1101051024指導(dǎo)教師：趙華、概述本次設(shè)計(jì)的程序主要功能是模擬訪問磁盤的過程，實(shí)現(xiàn)先來(lái)先服務(wù)調(diào)度算法、最短 尋道時(shí)間調(diào)度算法、掃描算法、循環(huán)掃描算法四個(gè)磁盤調(diào)度算法，并根據(jù)輸入的數(shù)據(jù)和 所選擇的調(diào)度算法輸出每種調(diào)度算法的磁盤訪問順序，計(jì)算并輸出四個(gè)算法的平均尋道 長(zhǎng)度。本程序主要實(shí)現(xiàn)磁盤訪問的順序，輸出四種不同的磁盤調(diào)度算法的磁盤訪問結(jié)果， 并計(jì)算出各自的平均尋道長(zhǎng)度。以此來(lái)對(duì)四種調(diào)度算法的性能進(jìn)行評(píng)價(jià)。、設(shè)計(jì)的基本概念和原理1、基本概念（1）當(dāng)前磁道號(hào)：磁頭當(dāng)前時(shí)刻所在磁盤的磁道編號(hào)。（2）被訪問的

2、下一個(gè)磁道號(hào)：需要訪問的下一個(gè)磁盤的磁道編號(hào)。（3）移動(dòng)距離：磁頭從當(dāng)前磁道移動(dòng)到被訪問的下一個(gè)磁道號(hào)所需移動(dòng)的磁道數(shù)。2、基本原理（1）先來(lái)先服務(wù)（FCFS，F(xiàn)irst Come First Served）按照進(jìn)程請(qǐng)求訪問磁盤的先后次序進(jìn)行從小到大排序，每次訪問最先請(qǐng)求訪問的磁道。 這樣是每個(gè)進(jìn)程的請(qǐng)求都能夠依次地得到處理，不會(huì)出現(xiàn)某一進(jìn)程的請(qǐng)求長(zhǎng)期得不到滿 足的情況（2）最短尋道時(shí)間優(yōu)先（SSTF, Shortest Seek Time First）要求訪問的磁道與當(dāng)前磁頭所在的磁道距離最近，以使每次的尋道時(shí)間最短。磁頭每次 都移動(dòng)到距離當(dāng)前磁道距離最小的磁道上。（3）掃描算法（SCAN）

3、將請(qǐng)求訪問的磁道號(hào)進(jìn)行排序（升序或降序），磁頭按照磁道號(hào)從大到小或從小到達(dá)的 順序訪問磁盤。（4）循環(huán)掃描算法（CSCAN）磁頭從當(dāng)前磁道從里向外（或從外向里）訪問磁道，當(dāng)訪問到最外（或最里）的磁道并 訪問后，磁頭立即返回最里的（或最外）的欲訪問的磁道，即最?。ɑ蜃畲螅┑拇诺捞?hào) 緊接著最大（或最?。┐诺捞?hào)構(gòu)成循環(huán)，進(jìn)行循環(huán)掃描。三、總體設(shè)計(jì)本程序才用了結(jié)構(gòu)化程序設(shè)計(jì)方法，將程序進(jìn)行模塊化處理。首先將進(jìn)程訪問磁盤的請(qǐng) 求抽象為一個(gè)類，用用戶所輸入的數(shù)據(jù)來(lái)把每個(gè)對(duì)象來(lái)初始化。然后分塊地調(diào)用不同的 函數(shù)實(shí)現(xiàn)不同的調(diào)度算法。本程序包括以下三個(gè)模塊：（1）預(yù)定義及進(jìn)程類定義模塊定義程序所用到的頭文件和常

4、量。定義請(qǐng)求類的類成員，成員函數(shù)以及輸出請(qǐng)求類的類成員的輸出函數(shù)（2）主程序模塊包括以下五個(gè)步驟選擇進(jìn)程調(diào)度算法輸入請(qǐng)求調(diào)用所選的磁盤調(diào)度算法計(jì)算每個(gè)請(qǐng)求的移動(dòng)距離輸出磁盤訪問順序和每個(gè)請(qǐng)求的移動(dòng)距離，計(jì)算并輸出所選算法的平均尋道長(zhǎng)度（3）其它函數(shù)模塊定義了四種調(diào)度算法和程序中調(diào)用的其他函數(shù)。程序流程圖如下圖所示四、詳細(xì)設(shè)計(jì)每個(gè)模塊的代碼及分析如下：1、預(yù)定義及進(jìn)程類定義模塊#include stdafx.h#include #include #include using namespace std;#define Startnumber 100 /開始訪問的磁道號(hào)#define Max 10

5、0 進(jìn)程最大值class Requestprivate:intnumber,distance,difference;/ number-被訪問的下一個(gè)磁道號(hào)distance-移動(dòng)距離difference-被訪問的下一 個(gè)磁道與當(dāng)前磁道的距離public:intgetnumber()/返回被訪問的下一個(gè)磁道號(hào)return number;-intgetdistance()/返回移動(dòng)距離return distance;intgetdifference()/返回被訪問的下一個(gè)磁道與當(dāng)前磁道的距離return difference;void setnumber(int t)/設(shè)置被訪問的下一個(gè)磁道號(hào)num

6、ber=t;void setdistance(int t)/ 設(shè)置移動(dòng)距離distance=t;void setdifference(int t)/設(shè)置被訪問的下一個(gè)磁道與當(dāng)前磁道的距離differencevoid show() const 輸出被訪問的下個(gè)磁道號(hào)和移動(dòng)距離coutsetw(17)numbersetw(6)distanceendl;2、主程序模塊 int main(intargc, char* argv)inti,c,num,option,choice;double averdis;/平均尋道長(zhǎng)度Request requestMax; /請(qǐng)求數(shù)組存放請(qǐng)求while(1)cout

7、磁盤調(diào)度算法endlendl;cout1.先來(lái)先服務(wù)2.最短尋道時(shí)間優(yōu)先endl;cout3.掃描算法4.循環(huán)掃描算法endl;cout0.退出endl;coutendl;coutchoice; 輸入選擇的調(diào)度算法if(choice=0)return 0;elsecoutc;for(i=0;ic;i+) 輸入請(qǐng)求中的數(shù)據(jù)并初始化請(qǐng)求數(shù)組cout請(qǐng)輸入第i+1個(gè)請(qǐng)求endl;cout被訪問的下一個(gè)磁道號(hào)num;requesti.setnumber(num);if(choice=1)FCFS(request,c); 調(diào)用先來(lái)先服務(wù) if(choice=2) SSTF(request,c);/調(diào)用

8、SSTFFCFS(request,c);/調(diào)用先來(lái)先服務(wù)計(jì)算移動(dòng)距離 if(choice=3|choice=4)/若選擇SCAN或CSCAN則需要選擇訪問方向 cout選擇訪問方向：endl;cout”1.向磁道號(hào)增加方向2.向磁道號(hào)遞減方向endl;coutoption;/選擇訪問方向 if(choice=3)SCAN(request,c,option);/調(diào)用 SCAN if(choice=4)CSAN(request,c,option);/調(diào)用 CSCAN FCFS(request,c);/調(diào)用先來(lái)先服務(wù)計(jì)算移動(dòng)距離averdis=calcuaverage(request,c);/ 計(jì)算

9、平均尋道長(zhǎng)度coutsetw(20)下一個(gè)磁道號(hào)setw(6)移動(dòng)距離(磁道數(shù))endl;for(i=0;ic;i+)/輸出調(diào)度結(jié)果和訪問順序。requesti.show();cout平均尋道長(zhǎng)度為：;coutaverdisendl;/輸出平均尋道長(zhǎng)度return 0;3、其它函數(shù)模塊void FCFS(Request *req,int count)/先來(lái)先服務(wù)inti,currentnumber;for(i=0;icount;i+)if(i=0)/第一個(gè)請(qǐng)求的移動(dòng)距離為它的磁道號(hào)與Startnumber的差reqi.setdistance(abs(reqi.getnumber()-Start

10、number);currentnumber=reqi.getnumber();else 其他請(qǐng)求的移動(dòng)距離為其磁道號(hào)與上一個(gè)請(qǐng)求磁道號(hào)的差reqi.setdistance(abs(reqi.getnumber()-currentnumber);currentnumber=reqi.getnumber();double calcuaverage(Request *req,int count)/求平 均尋道長(zhǎng)度inti;double aver;aver=0;for(i=0;icount;i+)aver+=reqi.getdistance();aver=aver/count;return aver;

11、void asc(Request *req,int count)/ 按磁道號(hào)遞增排序inti,j;Request temp;for(i=0;icount;i+)for(j=i;jcount;j+)if(reqj.getnumber()reqi.getnumber()temp=reqj;reqj=reqi;reqi=temp;void dec(Request *req,int count)/ 按磁道號(hào)遞減排序inti,j;Request temp;for(i=0;icount;i+)for(j=i;jreqi.getnumber()temp=reqj;reqj=reqi;reqi=temp;vo

12、id SSTF(Request *req,int count)/最短尋道時(shí)間優(yōu)先inti,currentnumber,j,k,min,flagminMax,flag;Request mediareqMax;for(i=0;icount;i+)flagmini=0;currentnumber=Startnumber;k=0;for(i=0;icount;i+)求所有磁道號(hào)與當(dāng)前磁道的差for(j=0;jcount;j+)reqj.setdifference(abs(reqj.getnumber()-currentnumber);找磁道差的最小值，并把此請(qǐng)求放入中間數(shù)組中，其磁道作為當(dāng)前磁道for

13、(j=0;jcount;j+) 每次將沒有訪問的磁道的磁道差作為最小值if(flagminj=0)min=reqj.getdifference();flag=j;break;for(j=0;jcount;j+)/找磁道差的最小值if(reqj.getdifference()min&flagminj=0)/將磁道差小于 min 且沒有訪問 的磁道差作為最小值min=reqj.getdifference();flag=j;/ flag記錄磁道差最小的請(qǐng)求號(hào)flagminflag=1;mediareqk+=reqflag;/找到的請(qǐng)求放入中間數(shù)組中currentnumber=reqflag.getn

14、umber();/ 磁道號(hào)作為當(dāng)前磁道for(i=0;icount;i+)reqi=mediareqi;void SCAN(Request *req,intcount,int p)/掃描算法inti,j,k,l;Request mediamaxMax,mediaminMax;j=0;k=0;for(i=0;iStartnumber)mediamaxj+=reqi;if(reqi.getnumber()Startnumber)mediamink+=reqi;asc(mediamax,j);dec(mediamin,k);if(p=1)/向磁道號(hào)增加的方向訪問，先訪問大于開始磁道號(hào)的磁道，再訪問小

15、于Startnumber 的for(i=0;ij;i+)reqi=mediamaxi;for(i=j,l=0;icount,lk;i+,l+)reqi=mediaminl;else向磁道號(hào)減少的方向訪問，先訪問小于Startnumber的磁道，再訪問大于Startnumber 的for(i=0;ik;i+)reqi=mediamini;for(i=k,l=0;ivcount,lvj;i+,l+)reqi=mediamaxl;void CSAN(Request *req,intcount,int p)inti,j,k,l;Request mediamaxMax,mediaminMax;j=0;k

16、=0;for(i=0;iStartnumber)mediamaxj+=reqi;if(reqi.getnumber()Startnumber)mediamink+=reqi;if(p=1)/向磁道號(hào)增加的方向訪問asc(mediamin,k);/將小于Startnumber的磁道的請(qǐng)求按磁道號(hào)升序排序asc(mediamax,j);/將大于Startnumber的磁道的請(qǐng)求按磁道號(hào)升序排序for(i=0;ij;i+)reqi=mediamaxi;for(i=j,l=0;ivcount,lvk;i+,l+)reqi=mediaminl;elsedec(mediamin,k);/將小于于Start

17、number的磁道的請(qǐng)求按磁道號(hào)降序排序dec(mediamax,j);/將大于Startnumber的磁道的請(qǐng)求按磁道號(hào)降序排序for(i=0;ik;i+)/將 請(qǐng)求重新排序reqi=mediamini;for(i=k,l=0;ivcount,lvj;i+,l+)reqi=mediamaxl;五、測(cè)試與數(shù)據(jù)分析選擇FCFS算法，輸入以下請(qǐng)求信息：被訪問的下一個(gè)磁道號(hào)移動(dòng)距離（磁道數(shù)）5545583391918219072160701501038112184146可以得到先來(lái)先服務(wù)調(diào)度算法的平均尋道時(shí)間（應(yīng)為55.3）。選擇最短尋道時(shí)間調(diào)度算法，再次輸入上述請(qǐng)求信息。可以得到SSTF的平均尋道

18、 時(shí)間（應(yīng)為27.5）。選擇掃描算法，再次輸入以上請(qǐng)求信息，選擇向磁道號(hào)增加的方向訪問，則得到掃 描算法的平均尋道長(zhǎng)度（應(yīng)為27.8）。選擇循環(huán)掃描算法，再次輸入上述請(qǐng)求信息，選擇向磁道號(hào)增加的方向訪問，得到 循環(huán)掃描算法的平均尋道時(shí)間（應(yīng)為35.8）將上述四個(gè)調(diào)度算法得到的平均尋道時(shí)間進(jìn)行比較，可以對(duì)這四種算法的性能進(jìn)行 分析和比較，對(duì)這四個(gè)磁盤調(diào)度算法有了更深入的理解。六、完成的情況、簡(jiǎn)要的使用說明本程序經(jīng)過了調(diào)試，能夠正常運(yùn)行，并能夠得到正確的結(jié)果。但使用時(shí)應(yīng)注意以下 幾個(gè)問題：1、選擇調(diào)度算法的時(shí)候只能輸入0、1、2、3、4這五個(gè)數(shù)字，若輸入其它字符 將造成程序進(jìn)入死循環(huán)。2、進(jìn)行掃描

19、算法和循環(huán)掃描算法時(shí)，選擇訪問方向只能為1或2,若輸入其它 字符將造成程序進(jìn)入死循環(huán)。3、在輸入請(qǐng)求信息之前，應(yīng)確定請(qǐng)求的數(shù)目，并輸入。4、本程序需要逐個(gè)輸入請(qǐng)求的信息，對(duì)于請(qǐng)求數(shù)目比較多的時(shí)候會(huì)花費(fèi)較長(zhǎng)的 時(shí)間。故本程序最好用于請(qǐng)求數(shù)目較少的情況。5、程序中的開始磁道號(hào)（Startnumber）為常量，用戶無(wú)法輸入但可以在程序代 碼中進(jìn)行修改。七、結(jié)果分析運(yùn)行程序界面如如下圖所示C:Use rsWCD es ktop0 深程設(shè)計(jì)、磋坦調(diào)度DI SKDi patchDeb u gDIS KDi patch.ex e藏盤調(diào)度算法2遢丑尋道時(shí)間優(yōu)先4 ,循環(huán)掃描具法請(qǐng)輸羌你選擇的調(diào)度算法:選擇1，

20、輸入五測(cè)試與數(shù)據(jù)分析中的數(shù)據(jù)，得到如下所示C:Use rsWCD es ktop0 深呈設(shè)計(jì) L 磋坦調(diào)度DI SKDi pate hDeb u gDIS KD i patch .ex e清輸zfef爾選擇的調(diào)度算法:3ir2遢丑尋道時(shí)間優(yōu)先4 ,循環(huán)掃描具法下一個(gè)磁道號(hào)移動(dòng)距離其磁道數(shù)）5545583391918219072160701501S38184112146平均尋道長(zhǎng)度為：55.3333磁盤調(diào)度算法選擇2,再次輸入上述數(shù)據(jù)，得到如下所示C:Use rsWVCDes top0 深程設(shè)計(jì)、磋坦調(diào)度D1 SKDi patchDeb u gDIS KDi patch.exe清輸:A你選擇的調(diào)度算法:2遢短尋道時(shí)間優(yōu)先 4：循環(huán)掃箱算法下頃磁道號(hào)移動(dòng)距離笑磁道數(shù)）9S58325533916381182S15S1321S18424平均尋道長(zhǎng)度為W 27-55S6磁盤調(diào)度算法選擇3,再輸入上述數(shù)據(jù)，選擇向磁道號(hào)增加的方向訪問，得到如下所示C:Use rsV/YCD es ktop0 深程設(shè)計(jì) k 磋坦調(diào)度D1 SKDi patchDeb u gDISKOipatch.exe管愕口方向2