操作系統(tǒng)課程設計---磁盤調(diào)度報告

1、<p><b>　　題 目：磁盤調(diào)度</b></p><p><b>　　設計目的</b></p><p>　　本課程設計是學習完《計算機操作系統(tǒng)》課程后，進行的一次全面的綜合訓練，通過課程設計，我們更好地掌握操作系統(tǒng)的原理及實現(xiàn)方法,加深對操作系統(tǒng)基礎理論和重要算法的理解，加強了動手能力。</p><p>&l

2、t;b>　　課程設計內(nèi)容和要求</b></p><p>　　編程序?qū)崿F(xiàn)下述磁盤調(diào)度算法,并求出每種算法的平均尋道長度，要求設計主界面以靈活選擇某算法，且以下算法都要實現(xiàn)：</p><p>　　1、先來先服務算法（FCFS）</p><p>　　2、最短尋道時間優(yōu)先算法（SSTF）</p><p>　　3、掃描算法（SCAN）

3、</p><p>　　4、循環(huán)掃描算法（CSCAN）</p><p><b>　　三．算法及數(shù)據(jù)結(jié)構(gòu)</b></p><p>　　3.1算法的總體思想</p><p>　　設備的動態(tài)分配算法與進程調(diào)度相似，也是基于一定的分配策略的。常用的分配策略有先請求先分配、優(yōu)先級高者先分配等策略。在多道程序系統(tǒng)中，低效率通常是由于磁

4、盤類旋轉(zhuǎn)設備使用不當造成的。操作系統(tǒng)中，對磁盤的訪問要求來自多方面，常常需要排隊。這時，對眾多的訪問要求按一定的次序響應，會直接影響磁盤的工作效率，進而影響系統(tǒng)的性能。訪問磁盤的時間因子由3部分構(gòu)成，它們是查找（查找磁道）時間、等待（旋轉(zhuǎn)等待扇區(qū)）時間和數(shù)據(jù)傳輸時間，其中查找時間是決定因素。因此，磁盤調(diào)度算法先考慮優(yōu)化查找策略，需要時再優(yōu)化旋轉(zhuǎn)等待策略。</p><p>　　平均尋道長度（L）為所有磁道所需移動距

5、離之和除以總的所需訪問的磁道數(shù)（N），即：</p><p>　　L=（M1+M2+……+Mi+……+MN）/N</p><p>　　其中Mi為所需訪問的磁道號所需移動的磁道數(shù)。</p><p>　　啟動磁盤執(zhí)行輸入輸出操作時，要把移動臂移動到指定的柱面，再等待指定扇區(qū)的旋轉(zhuǎn)到磁頭位置下，然后讓指定的磁頭進行讀寫，完成信息傳送。因此，執(zhí)行一次輸入輸出所花的時間有：&l

6、t;/p><p>　　尋找時間——磁頭在移動臂帶動下移動到指定柱面所花的時間。</p><p>　　延遲時間——指定扇區(qū)旋轉(zhuǎn)到磁頭下所需的時間。</p><p>　　傳送時間——由磁頭進程讀寫完成信息傳送的時間。</p><p>　　其中傳送信息所花的時間，是在硬件設計就固定的。而尋找時間和延遲時間是與信息在磁盤上的位置有關。</p>

7、<p>　　為了減少移動臂進行移動花費的時間，每個文件的信息不是按盤面上的磁道順序存放滿一個盤面后，再放到下一個盤面上。而是按柱面存放，同一柱面上的各磁道被放滿信息后，再放到下一個柱面上。所以各磁盤的編號按柱面順序（從0號柱面開始），每個柱面按磁道順序，每個磁道又按扇區(qū)順序進行排序。</p><p><b>　　3.2算法實現(xiàn)</b></p><p>　

8、　1.先來先服務算法（FCFS）</p><p>　　先來先服務（FCFS）調(diào)度:按先來后到次序服務，未作優(yōu)化。</p><p>　　最簡單的移臂調(diào)度算法是“先來先服務”調(diào)度算法，這個算法實際上不考慮訪問者要求訪問的物理位置，而只是考慮訪問者提出訪問請求的先后次序。例如，如果現(xiàn)在讀寫磁頭正在100號柱面上執(zhí)行輸出操作，而等待訪問者依次要訪問的柱面為55,58,39,18,90,160,15

9、0,38,184那么，當100號柱面上的操作結(jié)束后，移動臂將按請求的先后次序先移到55號柱面，最后到達184號柱面。</p><p>　　采用先來先服務算法決定等待訪問者執(zhí)行輸入輸出操作的次序時，移動臂來回地移動。先來先服務算法花費的尋找時間較長，所以執(zhí)行輸入輸出操作的總時間也很長。</p><p>　　void FCFS(int a[],int begin,int len)</p&

10、gt;<p><b>　　{</b></p><p>　　int b[100],i;</p><p>　　for(i=0;i<len;i++) b[i]=a[i];</p><p>　　double sum=0,avg;</p><p>　　for(i=0;i<len;i++)</p>

11、;<p><b>　　{</b></p><p>　　sum+=abs(begin-b[i]);</p><p>　　cout<<"第"<<i+1<<"次訪問的磁道是："<<b[i]<<endl;</p><p>　　begin=b

12、[i];</p><p><b>　　}</b></p><p>　　cout<<"平均尋道長度："<<sum*1.0/len<<endl;</p><p><b>　　}</b></p><p>　　2.短尋道時間優(yōu)先算法（SSTF）<

13、/p><p>　　最短尋找時間優(yōu)先調(diào)度算法總是從等待訪問者中挑選尋找時間最短的那個請求先執(zhí)行的，而不管訪問者到來的先后次序。現(xiàn)在仍利用同一個例子來討論，現(xiàn)在當100號柱面的操作結(jié)束后，應該先處理90號柱面的請求，然后到達58號柱面執(zhí)行操作，隨后處理55號柱面請求，后繼操作的次序應該是39,38,18,150,160,184.采用最短尋找時間優(yōu)先算法決定等待訪問者執(zhí)行操作的次序時，讀寫磁頭總共移動多個柱面的距離，與先來

14、先服務、算法比較，大幅度地減少了尋找時間，因而縮短了為各訪問者請求服務的平均時間，也就提高了系統(tǒng)效率。</p><p>　　但最短查找時間優(yōu)先（SSTF）調(diào)度，F(xiàn)CFS會引起讀寫頭在盤面上的大范圍移動，SSTF查找距離磁頭最短（也就是查找時間最短）的請求作為下一次服務的對象。SSTF查找模式有高度局部化的傾向，會推遲一些請求的服務，甚至引起無限拖延（又稱饑餓）。</p><p>　　voi

15、d SSTF(int a[],int begin,int len)</p><p><b>　　{</b></p><p>　　int i,j,p,min,q,b[100];</p><p>　　for(i=0;i<len;i++) b[i]=a[i];</p><p>　　sort(b,b+len);</p

16、><p>　　double sum=0,avg;</p><p>　　for(i=0;i<len;i++){ flag[i]=1;}</p><p><b>　　p=begin;</b></p><p>　　for(i=0;i<len;i++)</p><p><b>　　{&l

17、t;/b></p><p><b>　　min=1000;</b></p><p>　　for(j=0;j<len;j++)</p><p><b>　　{</b></p><p>　　if(flag[j])</p><p><b>　　{</b&

18、gt;</p><p>　　if(abs(b[j]-p)<min)</p><p>　　{q=j;min=abs(b[j]-p);}</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　flag[q]=0;</p&g

19、t;<p><b>　　sum+=min;</b></p><p><b>　　p=b[q];</b></p><p>　　cout<<"第"<<i+1<<"次訪問的磁道是："<<p<<endl; </p><p&

20、gt;<b>　　}</b></p><p>　　cout<<"平均尋道長度："<<sum*1.0/len<<endl;</p><p><b>　　}</b></p><p>　　3.掃描算法（SCAN）</p><p>　　SCAN 算法又

21、稱電梯調(diào)度算法。SCAN算法是磁頭前進方向上的最短查找時間優(yōu)先算法，它排除了磁頭在盤面局部位置上的往復移動，SCAN算法在很大程度上消除了SSTF算法的不公平性，但仍有利于對中間磁道的請求。</p><p>　　“電梯調(diào)度”算法是從移動臂當前位置開始沿著臂的移動方向去選擇離當前移動臂最近的那個柱訪問者，如果沿臂的移動方向無請求訪問時，就改變臂的移動方向再選擇。這好比乘電梯，如果電梯已向上運動到4層時，依次有3位乘

22、客陳生、伍生、張生在等候乘電梯。他們的要求是：陳生在2層等待去10層；伍生在5層等待去底層；張生在8層等待15層。由于電梯目前運動方向是向上，所以電梯的形成是先把乘客張生從8層帶到15層，然后電梯換成下行方向，把乘客伍生從5層帶到底層，電梯最后再調(diào)換方向，把乘客陳生從2層送到10層。</p><p>　　我們?nèi)杂们笆龅耐焕觼碛懻摬捎谩半娞菡{(diào)度”算法的情況。由于磁盤移動臂的初始方向有兩個，而該算法是與移動臂方向

23、有關，所以分成兩種情況來討論。</p><p>　　〈1〉.移動臂由里向外移動</p><p>　　開始時，，在100號柱面執(zhí)行操作的讀寫磁頭的移動臂方向是由里向外，趨向32號柱面的位置，因此，當訪問100號柱面的操作結(jié)束后，沿臂移動方向最近的柱面是150號柱面。所以應先為150號柱面的訪問者服務，然后是為160號柱面的訪問者服務。之后，由于在向外移方向已無訪問等待者，故改變移動臂的方向，

24、由外向里依次為各訪問者服務。在這種情況下為等待訪問者服務的次序是184,90,58,55,39,38,18。</p><p>　　〈2〉.移動臂由外向里移動</p><p>　　開始時，正在100號柱面執(zhí)行操作的讀寫磁頭的移動臂是由外向里（即向柱面號增大的內(nèi)圈方向）趨向90號柱面的位置，因此，當訪問90號柱面的操作結(jié)束后，沿臂移動方向最近的柱面是58號柱面。所以，應先為58號柱面服務，然后

25、按移動臂由外向里移動的方向，依次為55,39,38,18柱面的訪問者服務。當18號柱面的操作結(jié)束后，向里移動的方向已經(jīng)無訪問等待者，所以改變移動臂的前進方向，由里向外依次為150,160,184柱面的訪問者服務。</p><p>　　“電梯調(diào)度”與“最短尋找時間優(yōu)先”都是要盡量減少移動臂時所花的時間。所不同的是：“最短尋找時間優(yōu)先”不考慮臂的移動方向，總是選擇離當前讀寫磁頭最近的那個柱面，這種選擇可能導致移動臂來

26、回改變移動方向；“電梯調(diào)度”是沿著臂的移動方向去選擇離當前讀寫詞頭最近的哪個柱面的訪問者，僅當沿移動臂的前進移動方向無訪問等待者時，才改變移動臂的前進方向。由于移動臂改變方向是機械動作，速度相對較慢，所以，電梯調(diào)度算法是一種簡單、使用且高效的調(diào)度算法。</p><p>　　但是，“電梯調(diào)度”算法在實現(xiàn)時，不僅要記住讀寫磁頭的當前位置，還必須記住移動臂的當前前進方向。</p><p>　　v

27、oid SCAN(int a[],int begin,int len,int dir)</p><p><b>　　{</b></p><p>　　int i,j,k,t,b[100];</p><p>　　for(i=0;i<len;i++) b[i]=a[i];</p><p>　　sort(b,b+len);

28、</p><p>　　double sum=0;</p><p>　　if(dir==1){</p><p>　　for(i=0;i<len;i++)</p><p>　　if(b[i]>begin)</p><p>　　{k=i; break;}</p><p><b>

29、　　t=1;</b></p><p>　　for(i=k;i<len;i++)</p><p><b>　　{</b></p><p>　　sum+=abs(b[i]-begin);</p><p>　　begin=b[i];</p><p>　　cout<<&quo

30、t;第"<<t++<<"次訪問的磁道: "<<b[i]<<endl;</p><p><b>　　}</b></p><p>　　for(i=k-1;i>=0;i--)</p><p><b>　　{</b></p><

31、p>　　sum+=abs(b[i]-begin);</p><p>　　begin=b[i];</p><p>　　cout<<"第"<<t++<<"次訪問的磁道: "<<b[i]<<endl;</p><p><b>　　}</b><

32、;/p><p>　　cout<<"平均尋道時間："<<sum*1.0/len<<endl;</p><p><b>　　}</b></p><p>　　else if(dir==2){</p><p><b>　　t=1;</b></p>

33、;<p>　　for(i=len-1;i>=0;i--)</p><p>　　if(b[i]<begin){k=i;break;}</p><p>　　for(i=k;i>=0;i--)</p><p>　　{sum+=abs(b[i]-begin);begin=b[i];</p><p>　　cout<

34、<"第"<<t++<<"次訪問的磁道: "<<b[i]<<endl;</p><p><b>　　}</b></p><p>　　for(i=k+1;i<len;i++)</p><p>　　{ sum+=b[i];begin=b[i];<

35、/p><p>　　cout<<"第"<<t++<<"次訪問的磁道: "<<b[i]<<endl;</p><p><b>　　}</b></p><p>　　cout<<"平均尋道時間："<<sum*1.0

36、/len<<endl;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　4.循環(huán)掃描算法（CSCAN）</p><p>　　單項掃描調(diào)度算法的基本思想是，不考慮訪問者等待的先后次序，總是從0號柱面開始向里道掃描，按照各自所要訪問的柱面位

37、置的次序去選擇訪問者。在移動臂到達最后一個柱面后，立即快速返回到0號柱面，返回時不為任何的訪問者等待服務。在返回到0號柱面后，再次進行掃描。</p><p>　　由于該例中已假定讀寫的當前位置在100號柱面，所以，指示了從100號柱面繼續(xù)向里掃描，依次為150,160,184各柱面的訪問者服務，此時移動臂已經(jīng)是最內(nèi)的柱面，于是立即返回到18號柱面，重新掃描，依次為38,39,55,58,90號柱面的訪問者服務。&

38、lt;/p><p>　　除了“先來先服務”調(diào)度算法外，其余三種調(diào)度算法都是根據(jù)欲訪問的柱面位置來繼續(xù)調(diào)度的。在調(diào)度過程中可能有新的請求訪問者加入。在這些新的請求訪問者加入時，如果讀寫已經(jīng)超過了它們所要訪問的柱面位置，則只能在以后的調(diào)度中被選擇執(zhí)行。在多道程序設計系統(tǒng)中，在等待訪問磁盤的若干訪問者請求中，可能要求訪問的柱面號相同，但在同一柱面上的不同磁道，或訪問同一柱面中同一磁道上的不同扇區(qū)。所以，在進行移動調(diào)度時，在

39、按照某種短法把移動臂定位到某個柱面后，應該在等待訪問這個柱面的各個訪問者的輸入輸出操作都完成之后，再改變移動臂的位置。</p><p>　　void CSCAN(int a[],int begin,int len,int dir)</p><p><b>　　{</b></p><p>　　int i,k,t=1,b[100];</p&g

40、t;<p>　　for(i=0;i<len;i++) b[i]=a[i];</p><p>　　sort(b,b+len);</p><p>　　double sum=0;</p><p>　　if(dir==1)</p><p><b>　　{</b></p><p>　　f

41、or(i=0;i<len;i++)</p><p>　　{if(b[i]>begin){k=i;break;}}</p><p>　　for(i=k;i<len;i++)</p><p>　　{sum+=abs(b[i]-begin);begin=b[i];</p><p>　　cout<<"第&quo

42、t;<<t++<<"次訪問的磁道: "<<b[i]<<endl;</p><p><b>　　}</b></p><p>　　for(i=0;i<k;i++)</p><p>　　{sum+=abs(b[i]-begin);begin=b[i];</p>&

43、lt;p>　　cout<<"第"<<t++<<"次訪問的磁道: "<<b[i]<<endl;</p><p><b>　　}</b></p><p>　　cout<<"平均尋道時間："<<sum*1.0/len<&

44、lt;endl;</p><p><b>　　}</b></p><p>　　else if(dir==2)</p><p><b>　　{</b></p><p>　　for(i=len-1;i>=0;i--)</p><p>　　{if(b[i]<begin)

45、k=i;break;}</p><p>　　for(i=k;i>=0;i--)</p><p>　　{sum+=abs(b[i]-begin);begin=b[i];</p><p>　　cout<<"第"<<t++<<"次訪問的磁道: "<<b[i]<<end

46、l;</p><p><b>　　}</b></p><p>　　for(i=k+1;i<len;i++)</p><p>　　{sum+=abs(b[i]-begin);begin=b[i];</p><p>　　cout<<"第"<<t++<<"

47、次訪問的磁道: "<<b[i]<<endl;</p><p><b>　　}</b></p><p>　　cout<<"平均尋道時間："<<sum*1.0/len<<endl; </p><p><b>　　}</b></p&

48、gt;<p><b>　　}</b></p><p><b>　　運行結(jié)果及分析</b></p><p>　　2.最短尋道時間優(yōu)先</p><p><b>　　3.先來先服務</b></p><p><b>　　4.掃描算法</b></

49、p><p><b>　　1．從內(nèi)向外掃描</b></p><p><b>　　2.從外向內(nèi)掃描</b></p><p><b>　　5．循環(huán)算法</b></p><p>　?。?）磁頭由里向外移動</p><p>　　（2）磁頭由外向里移動</p>