操作系統(tǒng)課程設(shè)計(jì)磁盤調(diào)度報(bào)告

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

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

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

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

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

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

7、臂最近的那個(gè)柱訪問者，如果沿臂的移動(dòng)方向無請求訪問時(shí)，就改變臂的移 動(dòng)方向再選擇。這好比乘電梯，如果電梯已向上運(yùn)動(dòng)到4層時(shí)，依次有3位乘客 陳生、伍生、張生在等候乘電梯。他們的要求是：陳生在2層等待去10層；伍生在5層等待去底層；張生在8層等待15層。由于電梯目前運(yùn)動(dòng)方向是向上， 所以電梯的形成是先把乘客張生從 8層帶到15層，然后電梯換成下行方向，把 乘客伍生從5層帶到底層，電梯最后再調(diào)換方向，把乘客陳生從2層送到10層。我們?nèi)杂们笆龅耐焕觼碛懻摬捎谩半娞菡{(diào)度”算法的情況。由于磁盤移 動(dòng)臂的初始方向有兩個(gè)，而該算法是與移動(dòng)臂方向有關(guān)，所以分成兩種情況來討 論。1.移動(dòng)臂由里向外移動(dòng)開始時(shí)

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

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

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

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

12、待訪問這個(gè)柱面的各個(gè)訪問者的輸入輸出操作都完 成之后，再改變移動(dòng)臂的位置。3.3 .三個(gè)模塊之間的調(diào)用關(guān)系圖3.4 實(shí)現(xiàn)代碼#include#includevoid FCFS(int b口,int n,int init) /先來先服務(wù)int i,s,sum;int a20;for(i=0;in;i+)ai=bi；s=init;sum=0;for(i=0;in;i+) printf(第做訪問的磁道:%dn,i+1,ai);sum+=abs(s-ai); s=ai；printf(平均尋道長度:%fn,sum*1.0/n);void SSTF(int b口,int n,int k) /最短尋道法in

13、t i,j,s,sum=0,p;int a20;for(i=0;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(平均尋道長度:%fn,sum*1.0/n);void SCAN1(int b,int n,int k) /掃描算法int i,j,s,sum=0,p,biaoji;int a20;for(i=0;i=0;i-)biaoji=0;for(j=0;j=i;j+)if(aj-k0)biaoji=1;

14、P=j； break;if(biaoji=1)s=ap；for(j=0;j=i;j+) if(ajk&k-ajk-s)s=aj；P=j；ap=ai；printf(第做訪問的磁道：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(int b口,int n,int k) /循環(huán)算法int i,j,s,sum=0,p,biaoji;int

15、 a20;for(i=0;i=0;i-)biaoji=0;for(j=0;j0)biaoji=1;P=j； break;if(biaoji=1)s=ap；for(j=0;jk&aj-ks-k)s=aj；P=j；ap=ai；printf(第做訪問的磁道：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(第做訪問的磁道：dn,n-i,s);sum+=abs(k-s);k=s;printf(平均尋道長度：fn,sum*1.0/n);void C_SCAN(int b口,int n,in

16、t k) /循環(huán)算法int i,j,s,sum=0,p,biaoji;int a20;for(i=0;i=0;i-)biaoji=0;for(j=0;j0)biaoji=1;p=j；break;if(biaoji=1)s=ap；for(j=0;jk&aj-ks-k)s=aj；p=j；ap=ai；printf(第做訪問的磁道：dn,n-i,s);sum+=s-k;k=s;if(biaoji=0) break;s=a0;for(j=0;j=i;j+)if(aj=0;i-)s=a0;for(j=0;j=i;j+) if(aj-ks-k)s=aj； P=j；ap=ai；printf(第做訪問的磁道：d

17、n,n-i,s); sum+=s-k;k=s;printf(平均尋道長度：fn,sum*1.0/n); void main()int a20;int i,n,k,k1,init;printf(”請輸入需要訪問的磁道總數(shù)：);scanf(%d,&n);for(i=0;in;i+)printf( 需要訪問的磁道d:,i+1); scanf(%d”,&ai);printf(請輸入指針?biāo)诖诺溃骸?； scanf(%d”,&init);k=1;while(k)printf(*n);printf($ 程倩磁盤調(diào)度 $n”);printf(* 1.先來先服務(wù)(FCFS) *n);printf(* 2. 最

18、短尋道時(shí)間優(yōu)先(SSTF) *n);printf(* 3.掃描算法(SCAN)*n);printf(* 4.循環(huán)算法(C-SCAN)*n);printf(* 0. 退出*n);printf(I*n);printf(&謝謝使用 &n); printf( 請?jiān)谙旅孑斎肽倪x擇:);scanf(%d,&k);switch(k)case 1:FCFS(a,n,init);break;case 2:SSTF(a,n,init);break; case 3:k1=1;while(k1)printf(*n);printf(#程倩磁盤調(diào)度 #n);printf(* 1.移動(dòng)臂由里向外*n);printf(*

19、2.移動(dòng)臂由外向里*n);printf(* 0. 返回上一層 *n);printf(I*n);printf(# 謝謝使用 #n);printf(請?jiān)谙旅孑斎肽倪x擇:);scanf(%d,&k1);switch(k1)case 1:SCAN1(a,n,init);break;case 2:SCAN2(a,n,init);break;break;case 4:C_SCAN(a,n,init);break;四.運(yùn)行結(jié)果及分析H :最原始磁盤調(diào)度模擬苴法,exe,1! x|1您您您您您迂顯的的的的磁rrfhJfsrrhrrfhJfsrrhr*M-*3 *4.彳三孑田.退由法CYCAH YiMMMXXMM磁盤調(diào)度晴在下面輸入您的選擇J2.最短尋道時(shí)間優(yōu)先國H：最原始：.磁盤調(diào)度模擬算法.E吒-! x|Md+H* 制*=H第涸=H= *型#、#IrkTfMirwrarruMrrw fwfwwi工蕾軍冒娛田*2 .先乘先服