磁盤調(diào)度實(shí)驗(yàn)報(bào)告

1、操作系統(tǒng)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)六：磁盤調(diào)度算法一.實(shí)驗(yàn)?zāi)康膹?fù)習(xí)模擬實(shí)現(xiàn)一種磁盤調(diào)度算法，進(jìn)一步加深對(duì)磁盤調(diào)度效率的理解。二.實(shí)驗(yàn)屬性該實(shí)驗(yàn)為設(shè)計(jì)性實(shí)驗(yàn)。三.實(shí)驗(yàn)儀器設(shè)備及器材普通PC386以上微機(jī)四.實(shí)驗(yàn)要求本實(shí)驗(yàn)要求2學(xué)時(shí)完成。本實(shí)驗(yàn)要求完成如下任務(wù)：(1)建立相關(guān)的數(shù)據(jù)結(jié)構(gòu)，作業(yè)控制塊、已分配分區(qū)及未分配分區(qū)(2)實(shí)現(xiàn)一個(gè)分區(qū)分配算法，如最先適應(yīng)分配算法、最優(yōu)或最壞適應(yīng)分配算法(3)實(shí)現(xiàn)一個(gè)分區(qū)回收算法(4)給定一批作業(yè)/進(jìn)程，選擇一個(gè)分配或回收算法，實(shí)現(xiàn)分區(qū)存儲(chǔ)的模擬管理實(shí)驗(yàn)前應(yīng)復(fù)習(xí)實(shí)驗(yàn)中所涉及的理論知識(shí)和算法，針對(duì)實(shí)驗(yàn)要求完成基本代碼編寫并完成預(yù)習(xí)報(bào)告、實(shí)驗(yàn)中認(rèn)真調(diào)試所編代碼并進(jìn)行必要的測(cè)試、記

2、錄并分析實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)后認(rèn)真書寫符合規(guī)范格式的實(shí)驗(yàn)報(bào)告（參見附錄A）,并要求用正規(guī)的實(shí)驗(yàn)報(bào)告紙和封面裝訂整齊，按時(shí)上交。五.主要算法分析各個(gè)算法分析1 .先來先服務(wù)算法（FCFS）先來先服務(wù)（FCFS）調(diào)度：按先來后到次序服務(wù)，未作優(yōu)化。最簡(jiǎn)單的移臂調(diào)度算法是“先來先服務(wù)”調(diào)度算法，這個(gè)算法實(shí)際上不考慮訪問者要求訪問的物理位置，而只是考慮訪問者提出訪問請(qǐng)求的先后次序。例如，如果現(xiàn)在讀寫磁頭正在50號(hào)柱面上執(zhí)行輸出操作，而等待訪問者依次要訪問的柱面為130、199、32、159、15、148、61、99,那么，當(dāng)50號(hào)柱面上的操作結(jié)束后，移動(dòng)臂將按請(qǐng)求的先后次序先移到130號(hào)柱面，最后到達(dá)99號(hào)

3、柱面。采用先來先服務(wù)算法決定等待訪問者執(zhí)行輸入輸出操作的次序時(shí)，移動(dòng)臂來回地移動(dòng)。先來先服務(wù)算法花費(fèi)的尋找時(shí)間較長(zhǎng)，所以執(zhí)行輸入輸出操作的總時(shí)間也很長(zhǎng)。2 .最短尋道時(shí)間優(yōu)先算法（SSTF）最短尋找時(shí)間優(yōu)先調(diào)度算法總是從等待訪問者中挑選尋找時(shí)間最短的那個(gè)請(qǐng)求先執(zhí)行的，而不管訪問者到來的先后次序。現(xiàn)在仍利用同一個(gè)例子來討論，現(xiàn)在當(dāng)50號(hào)柱面的操作結(jié)束后，應(yīng)該先處理61號(hào)柱面的請(qǐng)求，然后到達(dá)32號(hào)柱面執(zhí)行操作，隨后處理15號(hào)柱面請(qǐng)求，后繼操作的次序應(yīng)該是99、130、148、159、199。采用最短尋找時(shí)間優(yōu)先算法決定等待訪問者執(zhí)行操作的次序時(shí)，讀寫磁頭總共移動(dòng)了200多個(gè)柱面的距離，與先來先服務(wù)

4、、算法比較，大幅度地減少了尋找時(shí)間，因而縮短了為各訪問者請(qǐng)求服務(wù)的平均時(shí)間，也就提高了系統(tǒng)效率。但最短查找時(shí)間優(yōu)先（SSTF）調(diào)度，F(xiàn)CFS會(huì)引起讀寫頭在盤面上的大范圍移動(dòng)，SSTF查找距離磁頭最短（也就是查找時(shí)間最短）的請(qǐng)求作為下一次服務(wù)的對(duì)象。SSTF查找模式有高度局部化的傾向，會(huì)推遲一些請(qǐng)求的服務(wù)，甚至引起無(wú)限拖延（又稱饑餓）3 .掃描算法（SCAN）SCAN算法又稱電梯調(diào)度算法。SCAN算法是磁頭前進(jìn)方向上的最短查找時(shí)間優(yōu)先算法，它排除了磁頭在盤面局部位置上的往復(fù)移動(dòng)，SCAN算法在很大程度上消除了SSTF算法的不公平性，但仍有利于對(duì)中間磁道的請(qǐng)求?！半娞菡{(diào)度”算法是從移動(dòng)臂當(dāng)前位置開

5、始沿著臂的移動(dòng)方向去選擇離當(dāng)前移動(dòng)臂最近的那個(gè)柱訪問者，如果沿臂的移動(dòng)方向無(wú)請(qǐng)求訪問時(shí)，就改變臂的移動(dòng)方向再選擇。這好比乘電梯，如果電梯已向上運(yùn)動(dòng)到4層時(shí)，依次有3位乘客陳生、伍生、張生在等候乘電梯。他們的要求是：陳生在2層等彳f去10層；伍生在5層等待去底層；張生在8層等待15層。由于電梯目前運(yùn)動(dòng)方向是向上，所以電梯的形成是先把乘客張生從8層帶到15層，然后電梯換成下行方向，把乘客伍生從5層帶到底層，電梯最后再調(diào)換方向，把乘客陳生從2層送到10層。但是，“電梯調(diào)度”算法在實(shí)現(xiàn)時(shí)，不僅要記住讀寫磁頭的當(dāng)前位置，還必須記住移動(dòng)臂的當(dāng)前前進(jìn)方向。六、程序代碼#include<iostream

6、.h>#include<stdio.h>#include<stdlib.h>voidFCFS(intarray,intm)/先來先服務(wù)算法intj,i,now;floatsum=0,avg;cout<<"輸入當(dāng)前的磁道號(hào)："/輸入當(dāng)前磁道號(hào)cin>>now;sum=abs(now-array0);cout<<"先來先服務(wù)算法（FCFS）調(diào)度后的序列為"<<array0<<""/輸出磁盤調(diào)度序列for(i=0,j=1;j<m;i+,j+)(s

7、um=sum+abs(arrayj-arrayi);cout<<arrayj<<""/輸出磁盤調(diào)度序列)avg=sum/(m);cout<<endl<<"平均尋道長(zhǎng)度："<<avg<<endl;/輸出平均尋道長(zhǎng)度/voidSSTF(intarray,intm)/最短尋道時(shí)間優(yōu)先算法inttemp;intk=1;intnow,l,r;inti,j;floatsum=0,avg=0;for(i=0;i<m;i+)for(j=i+1;j<m;j+)if(arrayi>ar

8、rayj)/將磁道號(hào)從小到大排序temp=arrayi;arrayi=arrayj;arrayj=temp;cout<<"請(qǐng)輸入當(dāng)前的磁道號(hào)：”;輸入當(dāng)前磁道號(hào)cin>>now;cout<<"最短尋道時(shí)間優(yōu)先算法(SSTF)調(diào)度后的序列為"/輸出磁盤調(diào)度序列if(arraym-1<=now)/若被訪問的下一最大的磁道號(hào)不大于當(dāng)前的磁道號(hào)(for(i=m-1;i>=0;i-)cout<<arrayi<<""/輸出磁盤調(diào)度序列sum=now-arrayi;now=arrayi;

9、elsef(array0>=now)/若被訪問的下一最小的磁道號(hào)不小于當(dāng)前的磁道號(hào)for(i=0;i<m;i+)cout<<arrayi<<""/輸出磁盤調(diào)度序列sum=arrayi-now;now=arrayi;else/當(dāng)前的磁道號(hào)的值在若所有被訪問的下的磁道號(hào)之間while(arrayk<now)/確定當(dāng)前磁道在已排的序列中的位置k+;l=k-1;r=k;if(now-arrayl)<=(arrayr-now)while(l>=0)先向磁道號(hào)減小方向訪問cout<<arrayl<<"

10、;"/輸出磁盤調(diào)度序列sum=sum+now-arrayl;l=l-1；now=array0;for(j=r;j<m;j+)再向磁道號(hào)增加方向訪問cout<<arrayj<<""/輸出磁盤調(diào)度序列sum+=arrayj-now;now=arrayelse/先向磁道號(hào)增加方向訪問while(r<m)cout<<arrayr<<""/輸出磁盤調(diào)度序列sum+=arrayr-now;now=arrayr;r=r+1;now=arraym-1;for(j=l;j>=0;j-)再向磁道號(hào)減

11、小方向訪問cout<<arrayj<<""/輸出磁盤調(diào)度序列sum+=now-arrayj;now=arrayj;avg=sum/(m);cout<<endl<<"平均尋道長(zhǎng)度："<<avg<<endl;輸出平均尋道長(zhǎng)度/voidSCAN(intarray,intm)/掃描算法inttemp;intk=1;intnow,d,l,r;inti,j;floatsum=0,avg=0;for(i=0;i<m;i+)for(j=i+1;j<m;j+)if(arrayi>ar

12、rayj)/將磁道號(hào)從小到大排序temp=arrayi;arrayi=arrayj;arrayj=temp;cout<<"請(qǐng)輸入當(dāng)前的磁道號(hào)："/輸入當(dāng)前磁道號(hào)cin>>now;cout<<"請(qǐng)輸入當(dāng)前移動(dòng)臂的移動(dòng)的方向(1表示向磁道號(hào)增加方向,0表示向磁道號(hào)減小方向):"cin>>d;/先要給出當(dāng)前磁道號(hào)和移動(dòng)臂的移動(dòng)方向cout<<"掃描算法(SCAN)調(diào)度后的序列為"if(arraym-1<=now)/若被訪問的下一最大的磁道號(hào)不大于當(dāng)前的磁道號(hào)for(i=m-1

13、;i>=0;i-)cout<<arrayi<<""/輸出磁盤調(diào)度序列sum=now-arrayi;now=arrayi;elseif(array0>=now)/若被訪問的下一最小的磁道號(hào)不小于當(dāng)前的磁道號(hào)for(i=0;i<m;i+)cout<<arrayi<<""/輸出磁盤調(diào)度序列sum=arrayi-now;now=arrayi;else/當(dāng)前的磁道號(hào)的值在若所有被訪問的下的磁道號(hào)之間while(arrayk<now)/確定當(dāng)前磁道在已排的序列中的位置k+;l=k-1;r=k;s

14、witch(d)case0:/先向磁道號(hào)減小方向訪問while(l>=0)cout<<arrayl<<""/輸出磁盤調(diào)度序列sum=sum+now-arrayl;l=l-1;)now=array0;for(j=r;j<m;j+)cout<<arrayj<<""/輸出磁盤調(diào)度序列sum+=arrayj-now;now=arrayj;break;)case1:/先向磁道號(hào)增加方向訪問while(r<m)cout<<arrayr<<""/輸出磁盤調(diào)度序

15、列sum+=arrayr-now;now=arrayr;r=r+1;now=arraym-1;for(j=l;j>=0;j-)cout<<arrayj<<""/輸出磁盤調(diào)度序列now=arrayj;break;)default:cout<<"輸入有誤"<<endl;avg=sum/(m);cout<<endl<<"平均尋道長(zhǎng)度："<<avg<<endl;輸出平均尋道長(zhǎng)度/voidmain()inti,m,n,flag=1,array1

16、00;cout<<"輸入磁盤調(diào)度序列的個(gè)數(shù)："；cin>>m;cout<<"分別輸入磁盤調(diào)度序列："；for(i=0;i<m;i+)cin>>arrayi;do終止"<<endl;先來先服務(wù)算法(FCFS)"<<endl;最短尋道時(shí)間優(yōu)先算法(SSTF)"<<endl;最短尋道時(shí)間優(yōu)先算法(SCAN)"<<endl;選擇以上的算法："cout<<"0cout<<"

17、;1cout<<"2cout<<"3cout<<"cin>>n;switch(n)(case0:flag=0;break;/case1:FCFS(array,m);break;/case2:SSTF(array,m);break;/case3:SCAN(array,m);break;/default:cout<<"輸入有誤，終止程序先來先服務(wù)算法(FCFS)最短尋道時(shí)間優(yōu)先算法(SSTF)最短尋道時(shí)間優(yōu)先算法(SCAN)請(qǐng)重新輸入:"<<endl;while(flag!=0

18、);七、各算法的流程圖.先來先服務(wù)算法流程圖3,掃描算法流程圖八.課程設(shè)計(jì)運(yùn)行結(jié)果一.運(yùn)行后的開始界面如下：件的個(gè)數(shù):7周度序列二居1429171G:DebuVCppl.ezeFZTftsCsSs>-&sWJnyJ.先.wso?服道道的度盤調(diào)酒要先尋尋上磁短以71別終先日E蕈擇W分BlZ工選、運(yùn)行各個(gè)算法結(jié)果如下八G二yDcbucXCpp1.eie口I*1.運(yùn)行先來先服務(wù)（FCFS）算法調(diào)度后程序結(jié)果如下:44:>去去s¥nvCF曼CFS小先先1度輸止采短期以當(dāng)先京來短短以別終先曰警取擇A膏終先日警軍擇53<F先先法;照道道的先尋尋上盤磁A道法：服道道的的務(wù)長(zhǎng)先尋尋上一揣道;號(hào)皿53為分電123邁輔,Mi23選71I58924的后度2.運(yùn)行最短尋道時(shí)間優(yōu)先（SSTF）算法調(diào)度程序結(jié)果如下:度盤r蔓=LI4B11VIN5lbNSY1<7FT0s0£入利紇先r最均終先最最擇1715&?241605屠：篦<F先先2號(hào)算,2一.道先33-間度服酒道的一部長(zhǎng)在尋尋上當(dāng)?shù)朗揽?lt;F先先一stt,.服道酒的先m上的表布間建道號(hào)減小方向、表小回讀運(yùn)