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

操作系統(tǒng)課程設(shè)計(jì)報(bào)告題目： 磁盤調(diào)度算法 院 系： 信息學(xué)院 班 級(jí)： 信管11-2 姓 名： 王裕辰 學(xué) 號(hào)： 1101051024 指導(dǎo)教師： 趙華 一、概述本次設(shè)計(jì)的程序主要功能是模擬訪問(wèn)磁盤的過(guò)程，實(shí)現(xiàn)先來(lái)先服務(wù)調(diào)度算法、最短尋道時(shí)間調(diào)度算法、掃描算法、循環(huán)掃描算法四個(gè)磁盤調(diào)度算法，并根據(jù)輸入的數(shù)據(jù)和所選擇的調(diào)度算法輸出每種調(diào)度算法的磁盤訪問(wèn)順序，計(jì)算并輸出四個(gè)算法的平均尋道長(zhǎng)度。本程序主要實(shí)現(xiàn)磁盤訪問(wèn)的順序，輸出四種不同的磁盤調(diào)度算法的磁盤訪問(wèn)結(jié)果，并計(jì)算出各自的平均尋道長(zhǎng)度。以此來(lái)對(duì)四種調(diào)度算法的性能進(jìn)行評(píng)價(jià)。二、設(shè)計(jì)的基本概念和原理1、基本概念當(dāng)前磁道號(hào)：磁頭當(dāng)前時(shí)刻所在磁盤的磁道編號(hào)。被訪問(wèn)的下一個(gè)磁道號(hào)：需要訪問(wèn)的下一個(gè)磁盤的磁道編號(hào)。移動(dòng)距離：磁頭從當(dāng)前磁道移動(dòng)到被訪問(wèn)的下一個(gè)磁道號(hào)所需移動(dòng)的磁道數(shù)。2、基本原理先來(lái)先服務(wù)（FCFS，F(xiàn)irstComeFirstServed）按照進(jìn)程請(qǐng)求訪問(wèn)磁盤的先后次序進(jìn)行從小到大排序，每次訪問(wèn)最先請(qǐng)求訪問(wèn)的磁道。這樣是每個(gè)進(jìn)程的請(qǐng)求都能夠依次地得到處理，不會(huì)出現(xiàn)某一進(jìn)程的請(qǐng)求長(zhǎng)期得不到滿足的情況最短尋道時(shí)間優(yōu)先(SSTF,ShortestSeekTimeFirst)要求訪問(wèn)的磁道與當(dāng)前磁頭所在的磁道距離最近，以使每次的尋道時(shí)間最短。磁頭每次都移動(dòng)到距離當(dāng)前磁道距離最小的磁道上。掃描算法（SCAN）將請(qǐng)求訪問(wèn)的磁道號(hào)進(jìn)行排序（升序或降序），磁頭按照磁道號(hào)從大到小或從小到達(dá)的順序訪問(wèn)磁盤。循環(huán)掃描算法（CSCAN）磁頭從當(dāng)前磁道從里向外（或從外向里）訪問(wèn)磁道，當(dāng)訪問(wèn)到最外（或最里）的磁道并訪問(wèn)后，磁頭立即返回最里的（或最外）的欲訪問(wèn)的磁道，即最?。ɑ蜃畲螅┑拇诺捞?hào)緊接著最大（或最?。┐诺捞?hào)構(gòu)成循環(huán)，進(jìn)行循環(huán)掃描。三、總體設(shè)計(jì)本程序才用了結(jié)構(gòu)化程序設(shè)計(jì)方法，將程序進(jìn)行模塊化處理。首先將進(jìn)程訪問(wèn)磁盤的請(qǐng)求抽象為一個(gè)類，用用戶所輸入的數(shù)據(jù)來(lái)把每個(gè)對(duì)象來(lái)初始化。然后分塊地調(diào)用不同的函數(shù)實(shí)現(xiàn)不同的調(diào)度算法。本程序包括以下三個(gè)模塊：預(yù)定義及進(jìn)程類定義模塊定義程序所用到的頭文件和常量。定義請(qǐng)求類的類成員，成員函數(shù)以及輸出請(qǐng)求類的類成員的輸出函數(shù)主程序模塊包括以下五個(gè)步驟=1\*GB3①選擇進(jìn)程調(diào)度算法=2\*GB3②輸入請(qǐng)求=3\*GB3③調(diào)用所選的磁盤調(diào)度算法=4\*GB3④計(jì)算每個(gè)請(qǐng)求的移動(dòng)距離=5\*GB3⑤輸出磁盤訪問(wèn)順序和每個(gè)請(qǐng)求的移動(dòng)距離，計(jì)算并輸出所選算法的平均尋道長(zhǎng)度其它函數(shù)模塊定義了四種調(diào)度算法和程序中調(diào)用的其他函數(shù)。程序流程圖如下圖所示四、詳細(xì)設(shè)計(jì)每個(gè)模塊的代碼及分析如下：預(yù)定義及進(jìn)程類定義模塊#include"stdafx.h"#include<iostream>#include<cmath>#include<iomanip>usingnamespacestd;#defineStartnumber100//開始訪問(wèn)的磁道號(hào)#defineMax100//進(jìn)程最大值classRequest{ private: intnumber,distance,difference; //number-被訪問(wèn)的下一個(gè)磁道號(hào)distance-移動(dòng)距離difference--被訪問(wèn)的下一個(gè)磁道與當(dāng)前磁道的距離 public: intgetnumber()//返回被訪問(wèn)的下一個(gè)磁道號(hào) { returnnumber; } intgetdistance()//返回移動(dòng)距離 { returndistance; } intgetdifference()//返回被訪問(wèn)的下一個(gè)磁道與當(dāng)前磁道的距離 { returndifference; } voidsetnumber(intt)//設(shè)置被訪問(wèn)的下一個(gè)磁道號(hào) { number=t; } voidsetdistance(intt)//設(shè)置移動(dòng)距離 { distance=t; } voidsetdifference(intt)//設(shè)置被訪問(wèn)的下一個(gè)磁道與當(dāng)前磁道的距離 { difference=t; } voidshow()const//輸出被訪問(wèn)的下個(gè)磁道號(hào)和移動(dòng)距離 { cout<<setw(17)<<number<<setw(6)<<distance<<endl; }};主程序模塊intmain(intargc,char*argv[]){ inti,c,num,option,choice; doubleaverdis;//平均尋道長(zhǎng)度 Requestrequest[Max];//請(qǐng)求數(shù)組存放請(qǐng)求 while(1){ cout<<"磁盤調(diào)度算法"<<endl<<endl; cout<<"1.先來(lái)先服務(wù)2.最短尋道時(shí)間優(yōu)先"<<endl; cout<<"3.掃描算法4.循環(huán)掃描算法"<<endl; cout<<"0.退出"<<endl; cout<<endl; cout<<"請(qǐng)輸入你選擇的調(diào)度算法："; cin>>choice;//輸入選擇的調(diào)度算法 if(choice==0) return0; else { cout<<"請(qǐng)輸入請(qǐng)求數(shù)量："; cin>>c;for(i=0;i<c;i++)//輸入請(qǐng)求中的數(shù)據(jù)并初始化請(qǐng)求數(shù)組 { cout<<"請(qǐng)輸入第"<<i+1<<"個(gè)請(qǐng)求"<<endl; cout<<"被訪問(wèn)的下一個(gè)磁道號(hào)"<<endl; cin>>num; request[i].setnumber(num); } if(choice==1) FCFS(request,c);//調(diào)用先來(lái)先服務(wù) if(choice==2) { SSTF(request,c);//調(diào)用SSTF FCFS(request,c);//調(diào)用先來(lái)先服務(wù)計(jì)算移動(dòng)距離 } if(choice==3||choice==4)//若選擇SCAN或CSCAN則需要選擇訪問(wèn)方向 { cout<<"選擇訪問(wèn)方向："<<endl; cout<<"1.向磁道號(hào)增加方向2.向磁道號(hào)遞減方向"<<endl; cout<<"你的選擇是："; cin>>option;//選擇訪問(wèn)方向 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ì)算平均尋道長(zhǎng)度 cout<<setw(20)<<"下一個(gè)磁道號(hào)"<<setw(6)<<"移動(dòng)距離（磁道數(shù)）"<<endl; for(i=0;i<c;i++)//輸出調(diào)度結(jié)果和訪問(wèn)順序。 request[i].show(); cout<<"平均尋道長(zhǎng)度為："; cout<<averdis<<endl;//輸出平均尋道長(zhǎng)度 }} return0;}其它函數(shù)模塊voidFCFS(Request*req,intcount){//先來(lái)先服務(wù) inti,currentnumber; for(i=0;i<count;i++) { if(i==0)//第一個(gè)請(qǐng)求的移動(dòng)距離為它的磁道號(hào)與Startnumber的差 { req[i].setdistance(abs(req[i].getnumber()-Startnumber)); currentnumber=req[i].getnumber(); } else//其他請(qǐng)求的移動(dòng)距離為其磁道號(hào)與上一個(gè)請(qǐng)求磁道號(hào)的差 {req[i].setdistance(abs(req[i].getnumber()-currentnumber)); currentnumber=req[i].getnumber(); } }}doublecalcuaverage(Request*req,intcount)//求平均尋道長(zhǎng)度{ inti; doubleaver; aver=0; for(i=0;i<count;i++) {aver+=req[i].getdistance(); } aver=aver/count; returnaver;}voidasc(Request*req,intcount)//按磁道號(hào)遞增排序{ inti,j; Requesttemp;for(i=0;i<count;i++) { for(j=i;j<count;j++) { if(req[j].getnumber()<req[i].getnumber()) { temp=req[j]; req[j]=req[i]; req[i]=temp; } } }}voiddec(Request*req,intcount)//按磁道號(hào)遞減排序{ inti,j; Requesttemp;for(i=0;i<count;i++) { for(j=i;j<count;j++) { if(req[j].getnumber()>req[i].getnumber()) { temp=req[j]; req[j]=req[i]; req[i]=temp; } } }}voidSSTF(Request*req,intcount){//最短尋道時(shí)間優(yōu)先 inti,currentnumber,j,k,min,flagmin[Max],flag; Requestmediareq[Max]; for(i=0;i<count;i++) flagmin[i]=0;currentnumber=Startnumber; k=0;for(i=0;i<count;i++) { //求所有磁道號(hào)與當(dāng)前磁道的差 for(j=0;j<count;j++) req[j].setdifference(abs(req[j].getnumber()-currentnumber)); //找磁道差的最小值，并把此請(qǐng)求放入中間數(shù)組中，其磁道作為當(dāng)前磁道for(j=0;j<count;j++)//每次將沒(méi)有訪問(wèn)的磁道的磁道差作為最小值 { if(flagmin[j]==0) { min=req[j].getdifference(); flag=j; break; } } for(j=0;j<count;j++)//找磁道差的最小值 { if(req[j].getdifference()<min&&flagmin[j]==0)//將磁道差小于min且沒(méi)有訪問(wèn)的磁道差作為最小值 { min=req[j].getdifference(); flag=j;//flag記錄磁道差最小的請(qǐng)求號(hào) } } flagmin[flag]=1; mediareq[k++]=req[flag];//找到的請(qǐng)求放入中間數(shù)組中 currentnumber=req[flag].getnumber();//磁道號(hào)作為當(dāng)前磁道 } for(i=0;i<count;i++) req[i]=mediareq[i];}voidSCAN(Request*req,intcount,intp){//掃描算法 inti,j,k,l; Requestmediamax[Max],mediamin[Max]; j=0; k=0; for(i=0;i<count;i++)//大于Startnumber的請(qǐng)求放入mediamax，小于的放入mediamin中 { if(req[i].getnumber()>Startnumber) mediamax[j++]=req[i]; if(req[i].getnumber()<Startnumber) mediamin[k++]=req[i]; }asc(mediamax,j); dec(mediamin,k); if(p==1) {//向磁道號(hào)增加的方向訪問(wèn)，先訪問(wèn)大于開始磁道號(hào)的磁道，再訪問(wèn)小于Startnumber的for(i=0;i<j;i++) req[i]=mediamax[i];for(i=j,l=0;i<count,l<k;i++,l++) req[i]=mediamin[l]; } else {//向磁道號(hào)減少的方向訪問(wèn),先訪問(wèn)小于Startnumber的磁道，再訪問(wèn)大于Startnumber的 for(i=0;i<k;i++) req[i]=mediamin[i]; for(i=k,l=0;i<count,l<j;i++,l++) req[i]=mediamax[l]; }}voidCSAN(Request*req,intcount,intp){ inti,j,k,l; Requestmediamax[Max],mediamin[Max]; j=0; k=0; for(i=0;i<count;i++)//大于Startnumber的請(qǐng)求放入mediamax，小于的放入mediamin中 { if(req[i].getnumber()>Startnumber) mediamax[j++]=req[i]; if(req[i].getnumber()<Startnumber) mediamin[k++]=req[i]; }if(p==1)//向磁道號(hào)增加的方向訪問(wèn) { asc(mediamin,k);//將小于Startnumber的磁道的請(qǐng)求按磁道號(hào)升序排序 asc(mediamax,j);//將大于Startnumber的磁道的請(qǐng)求按磁道號(hào)升序排序for(i=0;i<j;i++) req[i]=mediamax[i];for(i=j,l=0;i<count,l<k;i++,l++) req[i]=mediamin[l]; } else { dec(mediamin,k);//將小于于Startnumber的磁道的請(qǐng)求按磁道號(hào)降序排序 dec(mediamax,j);//將大于Startnumber的磁道的請(qǐng)求按磁道號(hào)降序排序 for(i=0;i<k;i++)//將請(qǐng)求重新排序 req[i]=mediamin[i]; for(i=k,l=0;i<count,l<j;i++,l++) req[i]=mediamax[l]; }}五、測(cè)試與數(shù)據(jù)分析選擇FCFS算法，輸入以下請(qǐng)求信息：被訪問(wèn)的下一個(gè)磁道號(hào)移動(dòng)距離（磁道數(shù)）5545583391918219072160701501038112184146可以得到先來(lái)先服務(wù)調(diào)度算法的平均尋道時(shí)間（應(yīng)為55.3）。選擇最短尋道時(shí)間調(diào)度算法，再次輸入上述請(qǐng)求信息?？梢缘玫絊STF的平均尋道時(shí)間（應(yīng)為27.5）。選擇掃描算法，再次輸入以上請(qǐng)求信息，選擇向磁道號(hào)增加的方向訪問(wèn)，則得到掃描算法的平均尋道長(zhǎng)度（應(yīng)為27.8）。選擇循環(huán)掃描算法，再次輸入上述請(qǐng)求信息，選擇向磁道號(hào)增加的方向訪問(wèn)，得到循環(huán)掃描算法的平均尋道時(shí)間（應(yīng)為35.8）將上述四個(gè)調(diào)度算法得到的平均尋道時(shí)間進(jìn)行比較，可以對(duì)這四種算法的性能進(jìn)行分析和比較，對(duì)這四個(gè)磁盤調(diào)度算法有了更深入的理解。六、完成的情況、簡(jiǎn)要的使用說(shuō)明本程序經(jīng)過(guò)了調(diào)試，能夠正常運(yùn)行，并能夠得到正確的結(jié)果。但使用時(shí)應(yīng)注意以下幾個(gè)問(wèn)題：選擇調(diào)度算法的時(shí)候只能輸入0、1、2、3、4這五個(gè)數(shù)字，若輸入其它字符將造成程序進(jìn)入死循環(huán)。進(jìn)行掃描算法和循環(huán)掃描算法時(shí)，選擇訪問(wèn)方向只能為1或2，若輸入其它字符將造成程序進(jìn)入死循環(huán)。在輸入請(qǐng)求信息之前，應(yīng)確定請(qǐng)求