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

1、題目：磁盤調度一. 設計目的本課程設計是學習完計算機操作系統(tǒng)課程后，進行的一次全面的綜合訓練，通過課程設計，我們更好地掌握操作系統(tǒng)的原理及實現(xiàn)方法，加深對操作系統(tǒng)基礎理論和重要算法的理解，加強了動手能力 。二. 課程設計內容和要求編程序實現(xiàn)下述磁盤調度算法，并求出每種算法的平均尋道長度，要求設計 主界面以靈活選擇某算法，且以下算法都要實現(xiàn)：1、先來先服務算法（FCFS2、最短尋道時間優(yōu)先算法（SSTF3、掃描算法（SCAN4、循環(huán)掃描算法（CSCAN三. 算法及數(shù)據(jù)結構3.1算法的總體思想設備的動態(tài)分配算法與進程調度相似，也是基于一定的分配策略的。常用的 分配策略有先請求先分配、優(yōu)先級高者先分

2、配等策略。在多道程序系統(tǒng)中，低效 率通常是由于磁盤類旋轉設備使用不當造成的。 操作系統(tǒng)中，對磁盤的訪問要求 來自多方面，常常需要排隊。這時，對眾多的訪問要求按一定的次序響應，會直 接影響磁盤的工作效率，進而影響系統(tǒng)的性能。訪問磁盤的時間因子由3部分構 成，它們是查找（查找磁道）時間、等待（旋轉等待扇區(qū)）時間和數(shù)據(jù)傳輸時間， 其中查找時間是決定因素。因此，磁盤調度算法先考慮優(yōu)化查找策略，需要時再 優(yōu)化旋轉等待策略。平均尋道長度（L）為所有磁道所需移動距離之和除以總的所需訪問的磁道 數(shù)（N），即：L= （M1+M2十+Mi+MN /N其中Mi為所需訪問的磁道號所需移動的磁道數(shù)。啟動磁盤執(zhí)行輸入輸出

3、操作時，要把移動臂移動到指定的柱面，再等待指定 扇區(qū)的旋轉到磁頭位置下，然后讓指定的磁頭進行讀寫，完成信息傳送。因此， 執(zhí)行一次輸入輸出所花的時間有：尋找時間一一磁頭在移動臂帶動下移動到指定柱面所花的時間。延遲時間一一指定扇區(qū)旋轉到磁頭下所需的時間。傳送時間 由磁頭進程讀寫完成信息傳送的時間。其中傳送信息所花的時間，是在硬件設計就固定的。而尋找時間和延遲時間 是與信息在磁盤上的位置有關。為了減少移動臂進行移動花費的時間，每個文件的信息不是按盤面上的磁道 順序存放滿一個盤面后，再放到下一個盤面上。而是按柱面存放，同一柱面上的 各磁道被放滿信息后，再放到下一個柱面上。所以各磁盤的編號按柱面順序（從

4、 0號柱面開始），每個柱面按磁道順序，每個磁道又按扇區(qū)順序進行排序 。3.2算法實現(xiàn)1. 先來先服務算法（FCFS先來先服務（FCFS調度：按先來后到次序服務，未作優(yōu)化。最簡單的移臂調度算法是“先來先服務”調度算法，這個算法實際上不考慮訪問 者要求訪問的物理位置，而只是考慮訪問者提出訪問請求的先后次序。例如，如 果現(xiàn)在讀寫磁頭正在50號柱面上執(zhí)行輸出操作，而等待訪問者依次要訪問的柱 面為130、199、32、159、15、148、61、99,那么，當50號柱面上的操作結束 后，移動臂將按請求的先后次序先移到 130號柱面，最后到達99號柱面。采用先來先服務算法決定等待訪問者執(zhí)行輸入輸出操作的次

5、序時，移動臂來回地移動。先來先服務算法花費的尋找時間較長， 所以執(zhí)行輸入輸出操作的總時 間也很長。2. 短尋道時間優(yōu)先算法（SSTF最短尋找時間優(yōu)先調度算法總是從等待訪問者中挑選尋找時間最短的那個 請求先執(zhí)行的，而不管訪問者到來的先后次序?，F(xiàn)在仍利用同一個例子來討論， 現(xiàn)在當50號柱面的操作結束后，應該先處理 61號柱面的請求，然后到達32號 柱面執(zhí)行操作，隨后處理15號柱面請求，后繼操作的次序應該是99、130、148、 159、199。采用最短尋找時間優(yōu)先算法決定等待訪問者執(zhí)行操作的次序時，讀寫磁頭總共移動了 200多個柱面的距離，與先來先服務、算法比較，大幅度地減少了尋找 時間，因而縮短

6、了為各訪問者請求服務的平均時間，也就提高了系統(tǒng)效率。 但最短查找時間優(yōu)先（SSTF調度，F(xiàn)CFS會引起讀寫頭在盤面上的大范圍移動， SSTF查找距離磁頭最短（也就是查找時間最短）的請求作為下一次服務的對象。 SSTF查找模式有高度局部化的傾向，會推遲一些請求的服務，甚至引起無限拖 延（又稱饑餓）。3. 掃描算法（SCANSCAN算法又稱電梯調度算法。SCAN算法是磁頭前進方向上的最短查找時間 優(yōu)先算法，它排除了磁頭在盤面局部位置上的往復移動，SCAN算法在很大程度上消除了 SSTF算法的不公平性，但仍有利于對中間磁道的請求?！半娞菡{度”算法是從移動臂當前位置開始沿著臂的移動方向去選擇離當前 移

7、動臂最近的那個柱訪問者，如果沿臂的移動方向無請求訪問時，就改變臂的移 動方向再選擇。這好比乘電梯，如果電梯已向上運動到4層時，依次有3位乘客 陳生、伍生、張生在等候乘電梯。他們的要求是：陳生在2層等待去10層；伍生在5層等待去底層；張生在8層等待15層。由于電梯目前運動方向是向上， 所以電梯的形成是先把乘客張生從 8層帶到15層，然后電梯換成下行方向，把 乘客伍生從5層帶到底層，電梯最后再調換方向，把乘客陳生從2層送到10層。我們仍用前述的同一例子來討論采用“電梯調度”算法的情況。由于磁盤移 動臂的初始方向有兩個，而該算法是與移動臂方向有關，所以分成兩種情況來討 論。<1> .移動

8、臂由里向外移動開始時，在50號柱面執(zhí)行操作的讀寫磁頭的移動臂方向是由里向外，趨向32號柱面的位置，因此，當訪問50號柱面的操作結束后，沿臂移動方向最近的 柱面是32號柱面。所以應先為32號柱面的訪問者服務，然后是為 15號柱面的 訪問者服務。之后，由于在向外移方向已無訪問等待者，故改變移動臂的方向， 由外向里依次為各訪問者服務。在這種情況下為等待訪問者服務的次序是61、99、130、14 8、159、199。2.移動臂由外向里移動開始時，正在50號柱面執(zhí)行操作的讀寫磁頭的移動臂是由外向里（即向柱 面號增大的內圈方向）趨向61號柱面的位置，因此，當訪問50號柱面的操作結 束后，沿臂移動方向最近的

9、柱面是 61號柱面。所以，應先為61號柱面服務，然 后按移動臂由外向里移動的方向，依次為 99、130、14 8、159、199柱面的訪問 者服務。當201號柱面的操作結束后，向里移動的方向已經(jīng)無訪問等待者， 所以 改變移動臂的前進方向，由里向外依次為 32、15柱面的訪問者服務?！半娞菡{度”與“最短尋找時間優(yōu)先”都是要盡量減少移動臂時所花的時間。 所不同的是：“最短尋找時間優(yōu)先”不考慮臂的移動方向，總是選擇離當前讀寫 磁頭最近的那個柱面，這種選擇可能導致移動臂來回改變移動方向；“電梯調度” 是沿著臂的移動方向去選擇離當前讀寫詞頭最近的哪個柱面的訪問者，僅當沿移動臂的前進移動方向無訪問等待者時

10、，才改變移動臂的前進方向。由于移動臂改 變方向是機械動作，速度相對較慢，所以，電梯調度算法是一種簡單、使用且高 效的調度算法。但是，“電梯調度”算法在實現(xiàn)時，不僅要記住讀寫磁頭的當前位置，還必 須記住移動臂的當前前進方向。4. 循環(huán)掃描算法（CSCAN單項掃描調度算法的基本思想是，不考慮訪問者等待的先后次序，總是從 0 號柱面開始向里道掃描，按照各自所要訪問的柱面位置的次序去選擇訪問者。在移動臂到達最后一個柱面后，立即快速返回到0號柱面，返回時不為任何的訪問 者等待服務。在返回到0號柱面后，再次進行掃描。由于該例中已假定讀寫的當前位置在 50號柱面，所以，指示了從50號柱面 繼續(xù)向里掃描，依次

11、為61、99、130、148、159、199各柱面的訪問者服務，此 時移動臂已經(jīng)是最內的柱面，于是立即返回到0號柱面，重新掃描，依次為15、32號柱面的訪問者服務。除了 “先來先服務”調度算法外，其余三種調度算法都是根據(jù)欲訪問的柱面 位置來繼續(xù)調度的。在調度過程中可能有新的請求訪問者加入。在這些新的請求 訪問者加入時，如果讀寫已經(jīng)超過了它們所要訪問的柱面位置，則只能在以后的調度中被選擇執(zhí)行。在多道程序設計系統(tǒng)中，在等待訪問磁盤的若干訪問者請求 中，可能要求訪問的柱面號相同，但在同一柱面上的不同磁道，或訪問同一柱面 中同一磁道上的不同扇區(qū)。所以，在進行移動調度時，在按照某種短法把移動臂 定位到某

12、個柱面后，應該在等待訪問這個柱面的各個訪問者的輸入輸出操作都完 成之后，再改變移動臂的位置。3.3.三個模塊之間的調用關系圖3.4實現(xiàn)代碼#i nclude<stdio.h>#in clude<math.h>void FCFS(i nt b,i nt n,i nt in it) /先來先服務int i,s,sum;int a20;for(i=0;i< n;i+)ai=bi;s=i nit;sum=0;for(i=0;i< n;i+)printf("第d次訪問的磁道:%dn",i+1,ai); sum+=abs(s-ai);s=ai;pri

13、ntf("平均尋道長度:%fn",sum*1.0/n);void SSTF(i nt b,i nt n,i nt k) /最短尋道法int i,j,s,sum=0,p;int a20;for(i=0;i< n;i+)ai=bi;for(i=n-1;i>=0;i-)s=a0;p=0;for(j=0;j<=i;j+)if(abs(aj-k)<abs(s-k)s=aj;p=j;ap=ai;printf("第£|次訪問的磁道:%dn",n-i,s); sum+=abs(s-k);k=s;printf("平均尋道長度:%

14、fn",sum*1.0/n);掃描算法void SCAN1(i nt b,i nt n,i nt k) /int i,j,s,sum=0,p,biaoji;int a20;for(i=0;i< n;i+)ai=bi;for(i=n-1;i>=0;i-)biaoji=0;for(j=0;j<=i;j+)if(aj-k<0)biaoji=1;P=j; break;if(biaoji=1)s=ap;for(j=0;j<=i;j+)if(aj<k&&k-aj<k-s)s=aj;P=j;ap=ai;printf("第d次訪問的

15、磁道：dn",n-i,s);sum+=k-s;k=s;elses=a0;for(j=0;j<=i;j+)if(aj-k<=s-k)s=aj;p=j;ap=ai;printf("第£|次訪問的磁道：dn",n-i,s); sum+=abs(k-s);k=s;printf(”平均尋道長度：fn",sum*1.0/n);void SCAN2(i nt b,i nt n,i nt k) /循環(huán)算法int i,j,s,sum=0,p,biaoji;int a20;for(i=0;i< n;i+)ai=bi;for(i=n-1;i>

16、=0;i-)biaoji=0;for(j=0;j<=i;j+)if(aj-k>0)biaoji=1;P=j; break;if(biaoji=1)s=ap;for(j=0;j<=i;j+)if(aj>k&&aj-k<s-k)s=aj;p=j;ap=ai;printf("第d次訪問的磁道：dn",n-i,s);sum+=s-k;k=s;elses=a0;for(j=0;j<=i;j+)if(k-aj<=k-s)s=aj;p=j;ap=ai;printf("第d次訪問的磁道：dn",n-i,s); s

17、um+=abs(k-s);k=s;printf("平均尋道長度：fn",sum*1.0/n);void C_SCAN(i nt b,i nt n,i nt k) /循環(huán)算法int i,j,s,sum=0,p,biaoji;int a20;for(i=0;i< n;i+)ai=bi;for(i=n-1;i>=0;i-)biaoji=0;for(j=0;j<=i;j+)if(aj-k>0)biaoji=1;p=j;break;if(biaoji=1)s=ap;for(j=0;j<=i;j+)if(aj>k&&aj-k<s

18、-k)s=aj;p=j;ap=ai;printf("第d次訪問的磁道:%dn",n-i,s);sum+=s-k;k=s;if(biaoji=0) break;s=a0;for(j=0;jv=i;j+)if(aj<=s)s=aj;P=j；ap=ai;printf("第d次訪問的磁道：dn",n-i,s); sum+=k-s;k=s;i-;for(;i>=0;i-)s=a0;for(j=0;j<=i;j+)if(aj-k<s-k)s=aj;P=j;ap=ai;printf("第£|次訪問的磁道:%dn",

19、n-i,s); sum+=s-k;k=s;printf("平均尋道長度：fn",sum*1.0/n); void mai n()int a20;int i,n ,k,k1,i nit;printf(”請輸入需要訪問的磁道總數(shù)：");sca nf("%d",&n);for(i=0;i< n;i+)printf("需要訪問的磁道%d:",i+1);scan f("%d",&ai);printf("請輸入指針所在磁道:");sca nf("%d",&

20、amp;init);k=1;while(k)printf("f*n");printf("$ 程倩磁盤調度 $n");printf("*1.先來先服務(FCFS) *n");printf("* 2.最短尋道時間優(yōu)先(SSTF) *n");printf("* 3.掃描算法(SCAN) *n");printf("* 4. 循環(huán)算法(C-SCAN) *n"); prin tf("* 0. 退出*n");printf("f*n");printf(

21、"&&&&&&&&&&&&謝謝使用 &&&&&&&&&&&&&&n"); printf(” 請在下面輸入您的選擇:");scan f("%d",&k);switch(k)case 1:FCFS(a, n,in it);break;case 2:SSTF(a ,n ,i nit);break;case 3:k1=1;while(k1)

22、printf("f*n");printf("# 程倩磁盤調度 #'n");prin tf("* 1.移動臂由里向外*n");prin tf("* 2.移動臂由外向里*n");prin tf("* 0.返回上一層*n");prin tf("請在下面輸入您的選擇："）；printf("f*n");printf("# 謝謝使用 #n");scan f("%d",&k1);switch(k1)case 1:S

23、CAN1(a, n,in it);break;case 2:SCAN2(a, n,in it);break; break;case 4:C_SCAN(a, n,in it);break;四. 運行結果及分析H :憬原螂，磁盤調度模擬算法.exe-! x|>0<耳耳>00<M：耳 NKNXNKN 耳1您您您您您洼4 5S4:5:在留的的的的磁 厲問訶問問問入耳耳 >OO< K>OO< K>OO< moot XXNKM：耳 NKM：耳 NKNXNKN 耳 NKN 耳 NKNXN<rr -I" ffi尋道4間優(yōu)先<SS

24、TF>*2 毘耒先|K#<fcfs>*3.ruwrhiwruwrhiwruwrijwruw*M-MMKK4 _j<C-SCAN> Y<SCAN>MMMW0.退岀rf'LiwjHJwruwjHJwruwjHJWj 同 |-tJ- ruvuvuwruvuvuwruvuvuwruw穆在下面輸入您的選擇:2.最短尋道時間優(yōu)先® h：；攝原貽1磁盤調度模擬算法，豈E二Ig. 2drwrvrviruwruvwuYvruvwvwwrvWfH#NJfME 44:M 腳 CC-SCfiN> Yi<SCftN>nf%rr&rrwMrTvrwrwww«Lr色 | | rvFvwwxjmmr<wuwnr 佬苕rrh l冋J 尋道時I可優(yōu)先佃£TF> *2.先.壬先服#<FCFS>*»3 J*«-從孔退tS津罟*3 0策弭弭弭KXKNJ（耳拭廉注魅図* 9 6 55泌1:雷道道* 彳幾- Lx* p Inp p 扌耳 愛次次次次寵12 3 4 5 -V 在 www 請您餐您您平3.先來先服務-|n| x|OOKrvfxrfu-fu-rvfxrru-fu-fvfxrfu-fu&#