PAGEPAGE1實(shí)驗(yàn)七磁盤(pán)調(diào)度算法實(shí)驗(yàn)?zāi)康谋菊n程設(shè)計(jì)是學(xué)習(xí)完《計(jì)算機(jī)操作系統(tǒng)》課程后，進(jìn)行的一次全面的綜合訓(xùn)練，通過(guò)課程設(shè)計(jì)，我們更好地掌握操作系統(tǒng)的原理及實(shí)現(xiàn)方法,加深對(duì)操作系統(tǒng)基礎(chǔ)理論和重要算法的理解，加強(qiáng)了動(dòng)手能力。實(shí)驗(yàn)內(nèi)容和要求編程序?qū)崿F(xiàn)下述磁盤(pán)調(diào)度算法,并求出每種算法的平均尋道長(zhǎng)度，要求設(shè)計(jì)主界面以靈活選擇某算法，且以下算法都要實(shí)現(xiàn)：1、先來(lái)先服務(wù)算法（FCFS）2、最短尋道時(shí)間優(yōu)先算法（SSTF）3、掃描算法（SCAN）//4、循環(huán)掃描算法（CSCAN）下面給出的程序中已經(jīng)給出了1、2兩個(gè)算法，請(qǐng)根據(jù)這兩個(gè)算法完成3、4算法。三．實(shí)現(xiàn)原理設(shè)備的動(dòng)態(tài)分配算法與進(jìn)程調(diào)度相似，也是基于一定的分配策略的。常用的分配策略有先請(qǐng)求先分配、優(yōu)先級(jí)高者先分配等策略。在多道程序系統(tǒng)中，低效率通常是由于磁盤(pán)類(lèi)旋轉(zhuǎn)設(shè)備使用不當(dāng)造成的。操作系統(tǒng)中，對(duì)磁盤(pán)的訪(fǎng)問(wèn)要求來(lái)自多方面，常常需要排隊(duì)。這時(shí)，對(duì)眾多的訪(fǎng)問(wèn)要求按一定的次序響應(yīng)，會(huì)直接影響磁盤(pán)的工作效率，進(jìn)而影響系統(tǒng)的性能。訪(fǎng)問(wèn)磁盤(pán)的時(shí)間因子由3部分構(gòu)成，它們是查找（查找磁道）時(shí)間、等待（旋轉(zhuǎn)等待扇區(qū)）時(shí)間和數(shù)據(jù)傳輸時(shí)間，其中查找時(shí)間是決定因素。因此，磁盤(pán)調(diào)度算法先考慮優(yōu)化查找策略，需要時(shí)再優(yōu)化旋轉(zhuǎn)等待策略。平均尋道長(zhǎng)度（L）為所有磁道所需移動(dòng)距離之和除以總的所需訪(fǎng)問(wèn)的磁道數(shù)（N），即：L=（M1+M2+……+Mi+……+MN）/N其中Mi為所需訪(fǎng)問(wèn)的磁道號(hào)所需移動(dòng)的磁道數(shù)。啟動(dòng)磁盤(pán)執(zhí)行輸入輸出操作時(shí)，要把移動(dòng)臂移動(dòng)到指定的柱面，再等待指定扇區(qū)的旋轉(zhuǎn)到磁頭位置下，然后讓指定的磁頭進(jìn)行讀寫(xiě)，完成信息傳送。因此，執(zhí)行一次輸入輸出所花的時(shí)間有：尋找時(shí)間——磁頭在移動(dòng)臂帶動(dòng)下移動(dòng)到指定柱面所花的時(shí)間。延遲時(shí)間——指定扇區(qū)旋轉(zhuǎn)到磁頭下所需的時(shí)間。傳送時(shí)間——由磁頭進(jìn)程讀寫(xiě)完成信息傳送的時(shí)間。其中傳送信息所花的時(shí)間，是在硬件設(shè)計(jì)就固定的。而尋找時(shí)間和延遲時(shí)間是與信息在磁盤(pán)上的位置有關(guān)。為了減少移動(dòng)臂進(jìn)行移動(dòng)花費(fèi)的時(shí)間，每個(gè)文件的信息不是按盤(pán)面上的磁道順序存放滿(mǎn)一個(gè)盤(pán)面后，再放到下一個(gè)盤(pán)面上。而是按柱面存放，同一柱面上的各磁道被放滿(mǎn)信息后，再放到下一個(gè)柱面上。所以各磁盤(pán)的編號(hào)按柱面順序（從0號(hào)柱面開(kāi)始），每個(gè)柱面按磁道順序，每個(gè)磁道又按扇區(qū)順序進(jìn)行排序。算法實(shí)現(xiàn)1.先來(lái)先服務(wù)算法（FCFS）先來(lái)先服務(wù)（FCFS）調(diào)度:按先來(lái)后到次序服務(wù)，未作優(yōu)化。最簡(jiǎn)單的移臂調(diào)度算法是“先來(lái)先服務(wù)”調(diào)度算法，這個(gè)算法實(shí)際上不考慮訪(fǎng)問(wèn)者要求訪(fǎng)問(wèn)的物理位置，而只是考慮訪(fǎng)問(wèn)者提出訪(fǎng)問(wèn)請(qǐng)求的先后次序。例如，如果現(xiàn)在讀寫(xiě)磁頭正在50號(hào)柱面上執(zhí)行輸出操作，而等待訪(fǎng)問(wèn)者依次要訪(fǎng)問(wèn)的柱面為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)柱面。采用先來(lái)先服務(wù)算法決定等待訪(fǎng)問(wèn)者執(zhí)行輸入輸出操作的次序時(shí)，移動(dòng)臂來(lái)回地移動(dòng)。先來(lái)先服務(wù)算法花費(fèi)的尋找時(shí)間較長(zhǎng)，所以執(zhí)行輸入輸出操作的總時(shí)間也很長(zhǎng)。2.短尋道時(shí)間優(yōu)先算法（SSTF）最短尋找時(shí)間優(yōu)先調(diào)度算法總是從等待訪(fǎng)問(wèn)者中挑選尋找時(shí)間最短的那個(gè)請(qǐng)求先執(zhí)行的，而不管訪(fǎng)問(wèn)者到來(lái)的先后次序?，F(xiàn)在仍利用同一個(gè)例子來(lái)討論，現(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)先算法決定等待訪(fǎng)問(wèn)者執(zhí)行操作的次序時(shí)，讀寫(xiě)磁頭總共移動(dòng)了200多個(gè)柱面的距離，與先來(lái)先服務(wù)、算法比較，大幅度地減少了尋找時(shí)間，因而縮短了為各訪(fǎng)問(wèn)者請(qǐng)求服務(wù)的平均時(shí)間，也就提高了系統(tǒng)效率。但最短查找時(shí)間優(yōu)先（SSTF）調(diào)度，F(xiàn)CFS會(huì)引起讀寫(xiě)頭在盤(pán)面上的大范圍移動(dòng)，SSTF查找距離磁頭最短（也就是查找時(shí)間最短）的請(qǐng)求作為下一次服務(wù)的對(duì)象。SSTF查找模式有高度局部化的傾向，會(huì)推遲一些請(qǐng)求的服務(wù)，甚至引起無(wú)限拖延（又稱(chēng)饑餓）。3.掃描算法（SCAN）SCAN算法又稱(chēng)電梯調(diào)度算法。SCAN算法是磁頭前進(jìn)方向上的最短查找時(shí)間優(yōu)先算法，它排除了磁頭在盤(pán)面局部位置上的往復(fù)移動(dòng)，SCAN算法在很大程度上消除了SSTF算法的不公平性，但仍有利于對(duì)中間磁道的請(qǐng)求?！半娞菡{(diào)度”算法是從移動(dòng)臂當(dāng)前位置開(kāi)始沿著臂的移動(dòng)方向去選擇離當(dāng)前移動(dòng)臂最近的那個(gè)柱訪(fǎng)問(wèn)者，如果沿臂的移動(dòng)方向無(wú)請(qǐng)求訪(fǎng)問(wèn)時(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)杂们笆龅耐焕觼?lái)討論采用“電梯調(diào)度”算法的情況。由于磁盤(pán)移動(dòng)臂的初始方向有兩個(gè)，而該算法是與移動(dòng)臂方向有關(guān)，所以分成兩種情況來(lái)討論。〈1〉.移動(dòng)臂由里向外移動(dòng)開(kāi)始時(shí)，，在50號(hào)柱面執(zhí)行操作的讀寫(xiě)磁頭的移動(dòng)臂方向是由里向外，趨向32號(hào)柱面的位置，因此，當(dāng)訪(fǎng)問(wèn)50號(hào)柱面的操作結(jié)束后，沿臂移動(dòng)方向最近的柱面是32號(hào)柱面。所以應(yīng)先為32號(hào)柱面的訪(fǎng)問(wèn)者服務(wù)，然后是為15號(hào)柱面的訪(fǎng)問(wèn)者服務(wù)。之后，由于在向外移方向已無(wú)訪(fǎng)問(wèn)等待者，故改變移動(dòng)臂的方向，由外向里依次為各訪(fǎng)問(wèn)者服務(wù)。在這種情況下為等待訪(fǎng)問(wèn)者服務(wù)的次序是61、99、130、148、159、199?！?〉.移動(dòng)臂由外向里移動(dòng)開(kāi)始時(shí)，正在50號(hào)柱面執(zhí)行操作的讀寫(xiě)磁頭的移動(dòng)臂是由外向里（即向柱面號(hào)增大的內(nèi)圈方向）趨向61號(hào)柱面的位置，因此，當(dāng)訪(fǎng)問(wèn)50號(hào)柱面的操作結(jié)束后，沿臂移動(dòng)方向最近的柱面是61號(hào)柱面。所以，應(yīng)先為61號(hào)柱面服務(wù)，然后按移動(dòng)臂由外向里移動(dòng)的方向，依次為99、130、148、159、199柱面的訪(fǎng)問(wèn)者服務(wù)。當(dāng)201號(hào)柱面的操作結(jié)束后，向里移動(dòng)的方向已經(jīng)無(wú)訪(fǎng)問(wèn)等待者，所以改變移動(dòng)臂的前進(jìn)方向，由里向外依次為32、15柱面的訪(fǎng)問(wèn)者服務(wù)。“電梯調(diào)度”與“最短尋找時(shí)間優(yōu)先”都是要盡量減少移動(dòng)臂時(shí)所花的時(shí)間。所不同的是：“最短尋找時(shí)間優(yōu)先”不考慮臂的移動(dòng)方向，總是選擇離當(dāng)前讀寫(xiě)磁頭最近的那個(gè)柱面，這種選擇可能導(dǎo)致移動(dòng)臂來(lái)回改變移動(dòng)方向；“電梯調(diào)度”是沿著臂的移動(dòng)方向去選擇離當(dāng)前讀寫(xiě)詞頭最近的哪個(gè)柱面的訪(fǎng)問(wèn)者，僅當(dāng)沿移動(dòng)臂的前進(jìn)移動(dòng)方向無(wú)訪(fǎng)問(wèn)等待者時(shí)，才改變移動(dòng)臂的前進(jìn)方向。由于移動(dòng)臂改變方向是機(jī)械動(dòng)作，速度相對(duì)較慢，所以，電梯調(diào)度算法是一種簡(jiǎn)單、使用且高效的調(diào)度算法。但是，“電梯調(diào)度”算法在實(shí)現(xiàn)時(shí)，不僅要記住讀寫(xiě)磁頭的當(dāng)前位置，還必須記住移動(dòng)臂的當(dāng)前前進(jìn)方向。4.循環(huán)掃描算法（CSCAN）單項(xiàng)掃描調(diào)度算法的基本思想是，不考慮訪(fǎng)問(wèn)者等待的先后次序，總是從0號(hào)柱面開(kāi)始向里道掃描，按照各自所要訪(fǎng)問(wèn)的柱面位置的次序去選擇訪(fǎng)問(wèn)者。在移動(dòng)臂到達(dá)最后一個(gè)柱面后，立即快速返回到0號(hào)柱面，返回時(shí)不為任何的訪(fǎng)問(wèn)者等待服務(wù)。在返回到0號(hào)柱面后，再次進(jìn)行掃描。由于該例中已假定讀寫(xiě)的當(dāng)前位置在50號(hào)柱面，所以，指示了從50號(hào)柱面繼續(xù)向里掃描，依次為61、99、130、148、159、199各柱面的訪(fǎng)問(wèn)者服務(wù)，此時(shí)移動(dòng)臂已經(jīng)是最內(nèi)的柱面，于是立即返回到0號(hào)柱面，重新掃描，依次為15、32號(hào)柱面的訪(fǎng)問(wèn)者服務(wù)。除了“先來(lái)先服務(wù)”調(diào)度算法外，其余三種調(diào)度算法都是根據(jù)欲訪(fǎng)問(wèn)的柱面位置來(lái)繼續(xù)調(diào)度的。在調(diào)度過(guò)程中可能有新的請(qǐng)求訪(fǎng)問(wèn)者加入。在這些新的請(qǐng)求訪(fǎng)問(wèn)者加入時(shí)，如果讀寫(xiě)已經(jīng)超過(guò)了它們所要訪(fǎng)問(wèn)的柱面位置，則只能在以后的調(diào)度中被選擇執(zhí)行。在多道程序設(shè)計(jì)系統(tǒng)中，在等待訪(fǎng)問(wèn)磁盤(pán)的若干訪(fǎng)問(wèn)者請(qǐng)求中，可能要求訪(fǎng)問(wèn)的柱面號(hào)相同，但在同一柱面上的不同磁道，或訪(fǎng)問(wèn)同一柱面中同一磁道上的不同扇區(qū)。所以，在進(jìn)行移動(dòng)調(diào)度時(shí)，在按照某種短法把移動(dòng)臂定位到某個(gè)柱面后，應(yīng)該在等待訪(fǎng)問(wèn)這個(gè)柱面的各個(gè)訪(fǎng)問(wèn)者的輸入輸出操作都完成之后，再改變移動(dòng)臂的位置。五．三個(gè)模塊之間的調(diào)用關(guān)系圖登錄模塊登錄模塊參數(shù)輸入模塊算法實(shí)現(xiàn)模塊六．實(shí)現(xiàn)代碼#include<stdio.h>#include<math.h>voidFCFS(intb[],intn,intinit)//先來(lái)先服務(wù){(diào) inti,s,sum; inta[20]; for(i=0;i<n;i++) a[i]=b[i]; s=init; sum=0; for(i=0;i<n;i++) { printf("第%d次訪(fǎng)問(wèn)的磁道:%d\n",i+1,a[i]); sum+=abs(s-a[i]); s=a[i]; } printf("平均尋道長(zhǎng)度:%f\n",sum*1.0/n);}voidSSTF(intb[],intn,intk)//最短尋道法{ inti,j,s,sum=0,p; inta[20]; for(i=0;i<n;i++) a[i]=b[i]; for(i=n-1;i>=0;i--) { s=a[0]; p=0; for(j=0;j<=i;j++) if(abs(a[j]-k)<abs(s-k)) { s=a[j]; p=j; } a[p]=a[i]; printf("第%d次訪(fǎng)問(wèn)的磁道:%d\n",n-i,s); sum+=abs(s-k); k=s; } printf("平均尋道長(zhǎng)度:%f\n",sum*1.0/n);}//電梯調(diào)度算法//循環(huán)掃描算法voidmain(){ inta[20]; inti,n,k,k1,init; printf("請(qǐng)輸入需要訪(fǎng)問(wèn)的磁道總數(shù)："); scanf("%d",&n); for(i=0;i<n;i++) { printf("需要訪(fǎng)問(wèn)的磁道%d:",i+1); scanf("%d",&a[i]); } printf("請(qǐng)輸入指針?biāo)诖诺?"); scanf("%d",&init); k=1; while(k) { printf("**********************************\n"); printf("$$$$$$$$$$$程倩--磁盤(pán)調(diào)度$$$$$$$$$\n"); printf("**1.先來(lái)先服務(wù)(FCFS)**\n"); printf("**2.最短尋道時(shí)間優(yōu)先(SSTF)**\n"); printf("**3.掃描算法(SCAN)**\n"); printf("**4.循環(huán)算法(C-SCAN)**\n"); printf("**0.退出**\n"); printf("**********************************\n"); printf("&&&&&&&&&&&&謝謝使用&&&&&&&&&&&&&&\n"); printf("請(qǐng)?jiān)谙旅孑斎肽倪x擇:"); scanf("%d",&k); switch(k) { case1:FCFS(a,n,init);break; case2:SSTF(a,n,init);break; case3:k1=1; while(k1) { printf("*********************************\n"); printf("########程倩--磁盤(pán)調(diào)度###########\n"); printf("****1.移動(dòng)臂由里向外**\n"); printf("****2.移動(dòng)臂由外向里**\n"); printf("****0.返回上一層**\n"); printf("*********************************\n"); printf("#############謝謝使用############\n"); printf("請(qǐng)?jiān)谙旅孑斎肽倪x擇:"); scanf