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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上目錄 一、課程設(shè)計(jì)目的3二、課程設(shè)計(jì)要求3三、課程設(shè)計(jì)原理3四、程序代碼5五、流程圖設(shè)計(jì)11六、運(yùn)行結(jié)果14七、調(diào)試分析16八、心得體會(huì)16 一、課程設(shè)計(jì)目的操作系統(tǒng)是最重要的計(jì)算機(jī)系統(tǒng)軟件，同時(shí)也是最活躍的學(xué)科之一，發(fā)展極為迅速。我們?cè)诒菊n程的實(shí)驗(yàn)過(guò)程中，要了解實(shí)際操作系統(tǒng)的工作過(guò)程，加深對(duì)操作系統(tǒng)基礎(chǔ)理論和重要算法的理解，在實(shí)踐過(guò)程中加深對(duì)操作系統(tǒng)原理的理解。通過(guò)設(shè)計(jì)一個(gè)磁盤(pán)調(diào)度模擬系統(tǒng)，以加深對(duì)先來(lái)先服務(wù)、最短尋道時(shí)間、電梯算法以及循環(huán)掃描算法等磁盤(pán)調(diào)度算法的理解。讓我們更好地掌握操作系統(tǒng)中磁盤(pán)調(diào)度的原理及實(shí)現(xiàn)方法,增強(qiáng)動(dòng)手能力。本實(shí)驗(yàn)通過(guò)對(duì)磁盤(pán)調(diào)度算法的實(shí)現(xiàn)，

2、加深對(duì)算法的理解，同時(shí)通過(guò)用C+語(yǔ)言編寫(xiě)程序?qū)崿F(xiàn)這些算法，并在windows平臺(tái)上實(shí)現(xiàn)，也再一次提高了自己編程的能力，提高了綜合運(yùn)用專(zhuān)業(yè)課知識(shí)的能力。二、課程設(shè)計(jì)要求本設(shè)計(jì)的具體要求如下：1.模擬一個(gè)磁盤(pán)調(diào)度算法2.要求能夠模擬FCFS、最短尋道時(shí)間、電梯算法等磁盤(pán)調(diào)度算法3.輸入為一組作業(yè)的磁道請(qǐng)求4.輸出為按選擇的算法執(zhí)行時(shí)的磁頭移動(dòng)軌跡 三、課程設(shè)計(jì)原理1.各個(gè)算法分析（1）先來(lái)先服務(wù)算法（FCFS）這是一種最簡(jiǎn)單的磁盤(pán)調(diào)度算法。它根據(jù)請(qǐng)求訪(fǎng)問(wèn)磁盤(pán)的先后次序進(jìn)行調(diào)度。此算法的優(yōu)點(diǎn)是公平、簡(jiǎn)單，且每個(gè)進(jìn)程的請(qǐng)求都能依次地得到處理，不會(huì)出現(xiàn)某一進(jìn)程的請(qǐng)求長(zhǎng)期得不到滿(mǎn)足的情況。但是此算法由于未

3、對(duì)尋道進(jìn)行優(yōu)化，致使平均尋道時(shí)間可能較長(zhǎng)。當(dāng)有進(jìn)程先后提出磁盤(pán)I/O請(qǐng)求時(shí)，先按他們發(fā)出請(qǐng)求的先后次序排隊(duì)。然后依次給予服務(wù)。其平均尋道距離較大，故先來(lái)先服務(wù)算法僅適用于請(qǐng)求磁盤(pán)I/O進(jìn)程數(shù)目較少的場(chǎng)合。（2）最短尋道時(shí)間優(yōu)先算法（SSTF） 該算法選擇這樣的進(jìn)程：其要求訪(fǎng)問(wèn)的磁道與當(dāng)前磁頭所在的磁道距離最近，以使每次尋道時(shí)間最短。但這種算法不能保證平均尋道時(shí)間最短。有可能導(dǎo)致某個(gè)進(jìn)程出現(xiàn)“饑餓”現(xiàn)象，因?yàn)橹灰粩嘤行逻M(jìn)程請(qǐng)求到達(dá)，且其所要訪(fǎng)問(wèn)的磁道與磁頭當(dāng)前所在的磁道的距離較近，這種新進(jìn)程的I/O請(qǐng)求必然優(yōu)先滿(mǎn)足。（3）掃描算法（SCAN） 該算法不僅考慮到正欲訪(fǎng)問(wèn)的磁道與當(dāng)前磁道間的距離，

4、更優(yōu)先考慮的是磁頭當(dāng)前的移動(dòng)方向。例如，當(dāng)磁頭正在自里向外移動(dòng)時(shí)，SCAN算法所考慮的下一個(gè)訪(fǎng)問(wèn)對(duì)象應(yīng)該是其欲訪(fǎng)問(wèn)的磁道之外，又是距離最近的。這樣自里向外地訪(fǎng)問(wèn)，直至再無(wú)更外的磁道需要訪(fǎng)問(wèn)時(shí)，才將磁臂換向?yàn)樽酝庀蚶镆苿?dòng)。這時(shí)，同樣也是每次選擇這樣的進(jìn)程來(lái)調(diào)度，既要訪(fǎng)問(wèn)的磁道在當(dāng)前位置內(nèi)距離最近者，這樣，磁頭又逐步地從外向里移動(dòng)，直至再無(wú)更里面的磁道要訪(fǎng)問(wèn)，從而避免了出現(xiàn)“饑餓”現(xiàn)象。由于在這種算法中磁頭移動(dòng)的規(guī)律頗似電梯的運(yùn)行，因而又常稱(chēng)之為電梯調(diào)度算法。（4）循環(huán)掃描算法（CSCAN） SCAN算法規(guī)定磁頭單向移動(dòng)，例如，只是自里向外移動(dòng)，當(dāng)磁頭移動(dòng)到最外的磁道并訪(fǎng)問(wèn)后，磁頭立即返回到最里的

5、欲訪(fǎng)問(wèn)的磁道，亦即將最小磁道號(hào)緊接著最大的磁道號(hào)構(gòu)成循環(huán)，進(jìn)行循環(huán)掃描。2.磁盤(pán)調(diào)度思想磁盤(pán)設(shè)備在工作時(shí)以恒定的速率旋轉(zhuǎn)。為了讀或?qū)?，磁頭必須能移動(dòng)到所要求的磁道上，并等待所要求的扇區(qū)開(kāi)始位置旋轉(zhuǎn)到磁頭下，然后或開(kāi)始讀或?qū)憯?shù)據(jù)。故可把磁盤(pán)訪(fǎng)問(wèn)時(shí)間分成以下三部分。（1）尋道時(shí)間Ts 這是把磁頭移動(dòng)到指定磁道上所經(jīng)歷的時(shí)間。該時(shí)間是啟動(dòng)磁臂的時(shí)間s與磁頭移動(dòng)n條磁道所花費(fèi)的時(shí)間之和，即 Ts=m*n+s其中，m是一常數(shù)，與磁盤(pán)驅(qū)動(dòng)器的速度有關(guān)。對(duì)于一般磁盤(pán)，m=0.2；對(duì)于高速磁盤(pán)，m<=0.1，磁臂的啟動(dòng)時(shí)間+約為2ms。這樣，對(duì)于一般的溫盤(pán)，對(duì)于一般的溫盤(pán)，其尋道時(shí)間將隨著尋道距離的增加

6、而增大，大體上是530ms。（2）旋轉(zhuǎn)延遲時(shí)間Tr這是指定扇區(qū)移動(dòng)到磁頭下面所經(jīng)歷的時(shí)間。不同的磁盤(pán)類(lèi)型中，旋轉(zhuǎn)速度至少相差一個(gè)數(shù)量級(jí)，如軟盤(pán)為300r/min，硬盤(pán)一般為720015000r/min，甚至更高。對(duì)于磁盤(pán)旋轉(zhuǎn)延遲時(shí)間而言，如硬盤(pán)，旋轉(zhuǎn)速度為15000r/min，每轉(zhuǎn)需時(shí)4ms，平均旋轉(zhuǎn)延遲時(shí)間Tr為2ms；而軟盤(pán)，其旋轉(zhuǎn)速度為300r/min或600r/min，這樣，平均Tr為50100ms。（3）傳輸時(shí)間Tt 這時(shí)指把數(shù)據(jù)從磁盤(pán)讀出或向磁盤(pán)寫(xiě)入數(shù)據(jù)所經(jīng)歷的時(shí)間。Tt的大小與每次所讀/寫(xiě)的字節(jié)數(shù)b和旋轉(zhuǎn)速度有關(guān)： Tt=b/(r*N)其中，r為磁盤(pán)每秒鐘的轉(zhuǎn)數(shù)；N為一條磁道上的

7、字節(jié)數(shù)，當(dāng)一次讀/寫(xiě)的字節(jié)數(shù)相當(dāng)于半條磁道上的字節(jié)數(shù)時(shí)，T3與T2相同。因此，可將訪(fǎng)問(wèn)時(shí)間Ta表示為 Ta=Ts+1/(2*r)+b/(r*N)由上式可以看出，在訪(fǎng)問(wèn)時(shí)間中，尋道時(shí)間和旋轉(zhuǎn)延遲時(shí)間基本上都與所讀/寫(xiě)數(shù)據(jù)的多少無(wú)關(guān)，而且它通常占據(jù)了訪(fǎng)問(wèn)時(shí)間中的大頭。磁盤(pán)是可供多個(gè)進(jìn)程共享的設(shè)備，當(dāng)有多個(gè)進(jìn)程都要求訪(fǎng)問(wèn)磁盤(pán)時(shí)，應(yīng)采用一種最佳調(diào)度算法，以使各進(jìn)程對(duì)磁盤(pán)的平均訪(fǎng)問(wèn)時(shí)間最小。由于在訪(fǎng)問(wèn)磁盤(pán)的時(shí)間中，主要是尋道時(shí)間，因此，磁盤(pán)調(diào)度的目標(biāo)是使磁盤(pán)的平均尋道時(shí)間最少?，F(xiàn)在我們考慮平均尋道長(zhǎng)度：所有磁道所需移動(dòng)距離之和除以總的所需訪(fǎng)問(wèn)的磁道數(shù)，所以尋道長(zhǎng)度決定了尋道時(shí)間，我們需要從上面的算法中選

8、擇最優(yōu)者。四、程序代碼下面給出部分重要的程序/*先來(lái)先服務(wù)調(diào)度算法*/void FCFS(int cidao,int m) /磁道號(hào)數(shù)組，磁道數(shù)為m int now;/當(dāng)前所在磁道號(hào) int sum=0; /總尋道長(zhǎng)度 int i; int j; int a; char strmax; float ave; /平均尋道長(zhǎng)度 cout<<"磁盤(pán)請(qǐng)求序列為：" for( i=0;i<m;i+) /按先來(lái)先服務(wù)策略輸出磁盤(pán)請(qǐng)求序列 cout<<cidaoi<<" " cout<<endl; cout<

9、<"請(qǐng)輸入當(dāng)前的磁道號(hào)：" BB: cin>>str; /判斷輸入的數(shù)據(jù)是不是正確 a=panduan(str); if(a=0) cout<<"數(shù)據(jù)類(lèi)型錯(cuò)誤,請(qǐng)重新輸入！"<<endl; goto BB; else now=zhuanhuan(str,a); /當(dāng)前磁道號(hào) sum+=abs(cidao0-now); cout<<"磁盤(pán)掃描序列為：" for( i=0;i<m;i+) /輸出磁盤(pán)掃描序列 cout<<cidaoi<<" &qu

10、ot; for(i=0,j=1;j<m;i+,j+) /求總尋道長(zhǎng)度和平均尋道長(zhǎng)度 sum+=abs(cidaoj-cidaoi); ave=(float)(sum)/(float)(m); cout<<endl; cout<<"平均尋道長(zhǎng)度："<<ave<<endl;/*最短尋道時(shí)間優(yōu)先調(diào)度算法*/void SSTF(int cidao,int m) int k=1; int now,l,r; int i,j,sum=0; int a; char strmax; float ave; cidao=paixu(cidao

11、,m); /調(diào)用排序算法排序 cout<<"請(qǐng)輸入當(dāng)前的磁道號(hào)：" CC: cin>>str; /判斷輸入的數(shù)據(jù)是不是正確 a=panduan(str); if(a=0) cout<<"數(shù)據(jù)類(lèi)型錯(cuò)誤,請(qǐng)重新輸入！"<<endl; goto CC; else now=zhuanhuan(str,a); /輸入當(dāng)前磁道號(hào) if(cidaom-1<=now) /若當(dāng)前磁道號(hào)大于請(qǐng)求序列中最大者，則直接由外向內(nèi)依次給予各請(qǐng)求服務(wù) cout<<"磁盤(pán)掃描序列為：" for(i=m

12、-1;i>=0;i-) cout<<cidaoi<<" " sum=now-cidao0; if(cidao0>=now) /若當(dāng)前磁道號(hào)小于請(qǐng)求序列中最小者，則直接由內(nèi)向外依次給予各請(qǐng)求服務(wù) cout<<"磁盤(pán)掃描序列為：" for(i=0;i<m;i+) cout<<cidaoi<<" " sum=cidaom-1-now; if(now>cidao0&&now<cidaom-1) /若當(dāng)前磁道號(hào)大于請(qǐng)求序列中最小者且小于最大

13、者 cout<<"磁盤(pán)掃描序列為：" while(cidaok<now) /確定當(dāng)前磁道在排序后的磁道序列中的位置 k+; l=k-1; r=k; while(l>=0)&&(r<m) if(now-cidaol)<=(cidaor-now) /選擇與當(dāng)前磁道最近的請(qǐng)求給予服務(wù) cout<<cidaol<<" " sum+=now-cidaol; now=cidaol; l=l-1; else cout<<cidaor<<" " sum

14、+=cidaor-now; now=cidaor; r=r+1; if(l=-1) /說(shuō)明磁頭已移動(dòng)到序列的最小號(hào)，現(xiàn)返回外側(cè)掃描仍未掃描的磁道 for(j=r;j<m;j+) cout<<cidaoj<<" " sum+=cidaom-1-cidao0; else /說(shuō)明磁頭已移動(dòng)到序列的最大號(hào)，現(xiàn)返回內(nèi)側(cè)掃描仍未掃描的磁道 for(j=l;j>=0;j-) cout<<cidaoj<<" " sum+=cidaom-1-cidao0; ave=(float)(sum)/(float)(m);

15、 cout<<endl; cout<<"平均尋道長(zhǎng)度："<<ave<<endl;/*電梯算法*/void SCAN(int cidao,int m) /先要給出當(dāng)前磁道號(hào)和移動(dòng)臂的移動(dòng)方向 int k=1; int now,l,r,d; int i,j,sum=0; int a; char strmax; float ave; cidao=paixu(cidao,m); /調(diào)用排序算法排序 cout<<"請(qǐng)輸入當(dāng)前的磁道號(hào)：" DD: cin>>str; /判斷輸入的數(shù)據(jù)是否正確 a

16、=panduan(str); if(a=0) cout<<"數(shù)據(jù)類(lèi)型錯(cuò)誤,請(qǐng)重新輸入！"<<endl; goto DD; else now=zhuanhuan(str,a); /輸入當(dāng)前磁道號(hào) if(cidaom-1<=now) /若當(dāng)前磁道號(hào)大于請(qǐng)求序列中最大者，則直接由外向內(nèi)依次給予各請(qǐng)求服務(wù) cout<<"磁盤(pán)掃描序列為：" for(i=m-1;i>=0;i-) cout<<cidaoi<<" " sum=now-cidao0; if(cidao0>=

17、now) /若當(dāng)前磁道號(hào)小于請(qǐng)求序列中最小者，則直接由內(nèi)向外依次給予各請(qǐng)求服務(wù) cout<<"磁盤(pán)掃描序列為：" for(i=0;i<m;i+) cout<<cidaoi<<" " sum=cidaom-1-now; if(now>cidao0&&now<cidaom-1) /若當(dāng)前磁道號(hào)大于請(qǐng)求序列中最小者且小于最大者 while(cidaok<now) k+; l=k-1; r=k; cout<<"請(qǐng)輸入當(dāng)前移動(dòng)臂的移動(dòng)的方向 (0表示由外向內(nèi) ，1 表

18、示由內(nèi)向外) : " cin>>d; if(d=0) /選擇移動(dòng)臂方向向內(nèi)，則先向內(nèi)掃描 cout<<"磁盤(pán)掃描序列為：" for(j=l;j>=0;j-) cout<<cidaoj<<" " /輸出向內(nèi)掃描的序列 for(j=r;j<m;j+) /磁頭移動(dòng)到最小號(hào)，則改變方向向外掃描未掃描的磁道 cout<<cidaoj<<" " /輸出向外掃描的序列 sum=now-2*cidao0+cidaom-1; else /選擇移動(dòng)臂方向向外，則

19、先向外掃描 cout<<"磁盤(pán)掃描序列為：" for(j=r;j<m;j+) cout<<cidaoj<<" " /輸出向外掃描的序列 for(j=l;j>=0;j-) /磁頭移動(dòng)到最大號(hào)，則改變方向向內(nèi)掃描未掃描的磁道 cout<<cidaoj<<" " sum=-now-cidao0+2*cidaom-1; ave=(float)(sum)/(float)(m); cout<<endl; cout<<"平均尋道長(zhǎng)度："

20、;<<ave<<endl;/*循環(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 strmax; float ave; cidao=paixu(cidao,m); /調(diào)用排序算法排序 cout<<"請(qǐng)輸入當(dāng)前的磁道號(hào)：" EE: cin>>str; /判斷輸入的數(shù)據(jù)是否正確 a=panduan(str); if(a=0) cout<<"數(shù)據(jù)類(lèi)型錯(cuò)誤,請(qǐng)重新輸入！"<&l

21、t;endl; goto EE; else now=zhuanhuan(str,a); /輸入當(dāng)前磁道號(hào) if(cidaom-1<=now) /若當(dāng)前磁道號(hào)大于請(qǐng)求序列中最大者，則直接將移動(dòng)臂移動(dòng)到最小號(hào)磁道依次向外給予各請(qǐng)求服務(wù) cout<<"磁盤(pán)掃描序列為：" for(i=0;i<m;i+) cout<<cidaoi<<" " sum=now-2*cidao0+cidaom-1; if(cidao0>=now) /若當(dāng)前磁道號(hào)小于請(qǐng)求序列中最小者，則直接由內(nèi)向外依次給予各請(qǐng)求服務(wù) cout<

22、<"磁盤(pán)掃描序列為：" for(i=0;i<m;i+) cout<<cidaoi<<" " sum=cidaom-1-now; if(now>cidao0&&now<cidaom-1) /若當(dāng)前磁道號(hào)大于請(qǐng)求序列中最小者且小于最大者 cout<<"磁盤(pán)掃描序列為：" while(cidaok<now) /反復(fù)地從內(nèi)向外掃描 k+; l=k-1; r=k; for(j=r;j<m;j+) cout<<cidaoj<<"

23、; " /輸出從當(dāng)前磁道向外掃描的序列 for(j=0;j<r;j+) /當(dāng)掃描完最大號(hào)磁道，磁頭直接移動(dòng)到最小號(hào)磁道，再向外掃描未掃描的磁道 cout<<cidaoj<<" " sum=2*cidaom-1+cidaol-now-2*cidao0; ave=(float)(sum)/(float)(m); cout<<endl; cout<<"平均尋道長(zhǎng)度："<<ave<<endl;五、流程圖設(shè)計(jì)1.先來(lái)先服務(wù)算法流程圖輸入當(dāng)前磁道號(hào)now磁頭移動(dòng)距離sum=abs

24、(now-cidao0)磁頭移動(dòng)總距離sum+=abs(cidaoj-cidaoi)輸出磁盤(pán)調(diào)度序列cidao j目前的位置變?yōu)楫?dāng)前的位置j+j<m輸出平均尋道長(zhǎng)度ave=sum/(m)2. 最短尋道時(shí)間優(yōu)先算法流程圖將磁道號(hào)從小到大排序輸入當(dāng)前磁道號(hào)nowcidaom-1<=now輸出磁盤(pán)調(diào)度序列cidaoj目前的位置變?yōu)楫?dāng)前的位置now=cidaoi磁頭移動(dòng)總距離sum=now-cidaoii>=0輸出磁盤(pán)調(diào)度序列cidaoj(cidao0>=now磁頭移動(dòng)總距離sum=now-cidaoi目前的位置變?yōu)楫?dāng)前的位置now=cidaoinow=arrayii<m

25、確定當(dāng)前磁道在已排的序列中的位置now-cidaol)<=(cidaor-now先向磁道號(hào)減小方向訪(fǎng)問(wèn)，再向磁道號(hào)增加方向訪(fǎng)問(wèn)輸出磁盤(pán)調(diào)度序列先向磁道號(hào)增加方向訪(fǎng)問(wèn)，再向磁道號(hào)減小方向訪(fǎng)問(wèn)輸出磁盤(pán)調(diào)度序列輸出平均尋道長(zhǎng)度ave=sum/(m)3. 掃描算法流程圖將磁道號(hào)從小到大排序輸入當(dāng)前磁道號(hào)now, 移動(dòng)臂的移動(dòng)的方向cidaom-1<=now磁頭移動(dòng)總距離sum=now-cidaoi輸出磁盤(pán)調(diào)度序列cidaoji>=0(cidao0>=now輸出磁盤(pán)調(diào)度序列cidaoji<m磁頭移動(dòng)總距離sum=cidao i-now確定當(dāng)前磁道在已排的序列中的位置switch(d)case 0:移動(dòng)臂向磁道號(hào)減小方向訪(fǎng)問(wèn)case 1:移動(dòng)臂向磁道號(hào)增加方向訪(fǎng)問(wèn)訪(fǎng)問(wèn)輸出磁盤(pán)調(diào)度序列輸出磁盤(pán)調(diào)度序列輸出平均尋道長(zhǎng)度ave=sum/(m)