操作系統(tǒng)課程設(shè)計(jì)-磁盤調(diào)度模擬-C++

上海電力學(xué)院課程設(shè)計(jì)報(bào)告課程名稱：操作系統(tǒng)原理題目名稱：七、磁盤調(diào)度模擬姓名：XXX學(xué)號(hào)：2012XXXX班級(jí)：2012XXX同組姓名：XXX課程設(shè)計(jì)時(shí)間：2015.1.19～2015.1.23評(píng)語(yǔ)：成績(jī)：磁盤調(diào)度模擬一、設(shè)計(jì)內(nèi)容及要求〔1〕設(shè)計(jì)內(nèi)容：編寫程序模擬磁盤訪問時(shí)磁頭的移動(dòng)?！?〕具體要求：1.輸入：輸入當(dāng)前磁頭的位置，隨機(jī)產(chǎn)生磁盤請(qǐng)求訪問序列〔不低于8個(gè)請(qǐng)求〕；2.輸出：顯示滿足每個(gè)訪問請(qǐng)求時(shí)磁頭移動(dòng)情況，磁頭移動(dòng)距離，及最終的磁頭移動(dòng)總距離及平均尋道長(zhǎng)度；3.分別使用以下算法：①先來(lái)先效勞；②最短尋道時(shí)間優(yōu)先；③掃描算法；〔3〕小組分工：XXX、XXX：通過(guò)書上例題，一同整理思路，構(gòu)思程序總體框架；查找資料，完成隨機(jī)生成磁盤請(qǐng)求訪問序列的函數(shù)；在課上共同編寫程序，測(cè)試，修改，實(shí)現(xiàn)先來(lái)先效勞算法的磁盤調(diào)度序列功能；初步完成主函數(shù)菜單的編寫；XXX：編寫程序，實(shí)現(xiàn)掃描算法中的輸出磁盤調(diào)度序列功能；屢次測(cè)試數(shù)據(jù)，找出程序bug；給出修改建議。XXX：編寫程序，實(shí)現(xiàn)最短尋道時(shí)間優(yōu)先的各功能；整合三個(gè)算法功能并做調(diào)試修改；完成Print輸出函數(shù)的編寫，修改參數(shù)傳遞，完成其他三個(gè)算法對(duì)Print函數(shù)調(diào)用，最終實(shí)現(xiàn)輸出磁頭移動(dòng)情況、磁頭移動(dòng)距離、最終的磁頭移動(dòng)總距離、平均尋道長(zhǎng)度；改正調(diào)試中產(chǎn)生的error，測(cè)試運(yùn)行，修正測(cè)試數(shù)據(jù)中出現(xiàn)的bug，最終完善程序。二、詳細(xì)設(shè)計(jì)〔1〕原理概述磁盤調(diào)度中常用的三種調(diào)度算法的原理如下：1、先來(lái)先效勞算法〔FCFS〕。FCFS為一種最簡(jiǎn)單的磁盤調(diào)度算法，它直接根據(jù)作業(yè)請(qǐng)求磁盤的先后順序?qū)Υ疟P進(jìn)行尋訪，公平、簡(jiǎn)單，每個(gè)作業(yè)的磁盤請(qǐng)求都可以得到處理，不會(huì)出現(xiàn)某個(gè)作業(yè)的請(qǐng)求長(zhǎng)期得不到滿足的情況，但未對(duì)尋道方案進(jìn)行優(yōu)化即先來(lái)的請(qǐng)求先被響應(yīng)，當(dāng)請(qǐng)求的頻率過(guò)高時(shí)FCFS策略的響應(yīng)時(shí)間就會(huì)大大延長(zhǎng)，反復(fù)響應(yīng)從里到外的請(qǐng)求，那么將會(huì)消耗大量的時(shí)間。2、最短尋道時(shí)間優(yōu)先算法〔SSTF〕。SSTF優(yōu)先選擇距離當(dāng)前磁頭位置最近的作業(yè)磁道請(qǐng)求，可以使得每次尋道時(shí)所用的時(shí)間都最短，但不能保證平均周轉(zhuǎn)時(shí)間及帶權(quán)周轉(zhuǎn)時(shí)間最短要求訪問的磁道。3、掃描算法〔SCAN〕。SCAN不僅考慮到欲訪問的磁道與當(dāng)前磁道間的距離，更優(yōu)先考慮的是磁頭當(dāng)前的移動(dòng)方向。SCAN同時(shí)考慮下一個(gè)作業(yè)磁道請(qǐng)求與當(dāng)前磁頭位置的距離和當(dāng)前磁頭移動(dòng)方向先選擇當(dāng)前磁頭之外距離其最近的磁道進(jìn)行訪問，直到再無(wú)更外的磁道請(qǐng)求，再將磁臂換向，訪問磁頭內(nèi)側(cè)距離當(dāng)前磁頭位置最近的作業(yè)磁道請(qǐng)求，防止了“饑餓”現(xiàn)象的出現(xiàn)，每個(gè)作業(yè)的磁盤請(qǐng)求都可以得到處理，且使每次尋道時(shí)間相對(duì)較短?！?〕主要數(shù)據(jù)結(jié)構(gòu)1.重要的變量：存放磁道號(hào)的int類型數(shù)組，如：a[],aa[],aaa[],b[]存放數(shù)組下標(biāo)的int類型變量，如：i,j,l,r存放磁頭移動(dòng)總距離、平均尋道長(zhǎng)度的double類型變量，如：sum,avg存放磁道數(shù)、菜單項(xiàng)選擇擇的int類型變量，如：n，menu2.重要的函數(shù)調(diào)用：計(jì)算sum,avg時(shí)用到的求絕對(duì)值的abs函數(shù)，如：abs(b[i+1]-b[i])遞增排序用到的sort函數(shù)，如：sort(aa,aa+(n+1))隨機(jī)產(chǎn)生磁道號(hào)的srand函數(shù)，如：srand((unsigned)time(NULL))菜單項(xiàng)選擇擇的switch函數(shù)，如：switch(menu){case0:...case1:...case2:...case3:...}〔3〕算法〔流程圖〕①磁盤調(diào)度的功能模塊：②磁盤調(diào)度的流程圖：開始開始輸入磁道的個(gè)數(shù)輸入磁道的個(gè)數(shù)n隨機(jī)生成隨機(jī)生成n個(gè)磁道號(hào)，并輸出掃描算法掃描算法最短尋道時(shí)間優(yōu)先算法最短尋道時(shí)間優(yōu)先算法先來(lái)先效勞算法輸入當(dāng)前磁頭的位置，放入輸入當(dāng)前磁頭的位置，放入aaa[0]，并賦給first輸入當(dāng)前磁頭的位置，放入aa[0]，并賦給first輸入當(dāng)前磁頭的位置輸入當(dāng)前磁頭的位置，放入a[0]aaa[]從小到大排序(sort)aaa[]從小到大排序(sort)aa[]從小到大排序(sort)計(jì)算并計(jì)算并輸出：磁盤調(diào)度順序、磁頭依次移動(dòng)距離、最終的磁頭移動(dòng)總距離、平均尋道長(zhǎng)度當(dāng)前磁頭最大？a當(dāng)前磁頭最大？aaa[n]<=first?當(dāng)前磁頭最大？aa[n]<=first?NNNNYYYYaaa[]反向賦值給b[]aaa[]反向賦值給b[]aa[]反向賦值給b[]aa[]反向賦值給b[]當(dāng)前磁頭最小當(dāng)前磁頭最小？first<=aaa[0]?當(dāng)前磁頭最小？first<=aa[0]?NNNNYYYYYYaaa[]正向賦值給b[]aa[]正向賦值給b[]aaa[]正向賦值給b[]aa[]正向賦值給b[]磁頭賦值給b[0]磁頭賦值給b[0]磁頭賦值給b[0]磁頭賦值給b[0]輸入當(dāng)前磁頭移動(dòng)的方向當(dāng)前輸入當(dāng)前磁頭移動(dòng)的方向當(dāng)前磁頭first在aa[]中間的位置？NYNY磁頭向減小方向移動(dòng)？磁頭向減小方向移動(dòng)？first與左側(cè)aa[l]磁道最近first與左側(cè)aa[l]磁道最近？NNYNYN磁頭左側(cè)從大到小賦值給b[]磁頭右側(cè)從小到大賦值給b[]磁頭左側(cè)從大到小賦值給b[]磁頭右側(cè)從小到大賦值給b[]Yaa[l]賦值給b[]aa[l]賦值給b[]磁頭右側(cè)從小到大賦值給b[]磁頭右側(cè)從小到大賦值給b[]磁頭左側(cè)從大到小賦值給b[]aa[r]賦值給b[]aa[r]賦值給b[]計(jì)算并計(jì)算并輸出：磁盤調(diào)度順序、磁頭依次移動(dòng)距離、最終的磁頭移動(dòng)總距離、平均尋道長(zhǎng)度當(dāng)前磁頭在最左側(cè)當(dāng)前磁頭在最左側(cè)？l=-1?NNYY剩余的aa[r]從小到大賦值給b[]剩余的aa[r]從小到大賦值給b[]剩余的aa[l]從大到小賦值給b[]剩余的aa[l]從大到小賦值給b[]計(jì)算并計(jì)算并輸出：磁盤調(diào)度順序、磁頭依次移動(dòng)距離、最終的磁頭移動(dòng)總距離、平均尋道長(zhǎng)度〔4〕源程序文件名執(zhí)行文件名：XXXX.cpp三、實(shí)驗(yàn)結(jié)果與分析1、正確執(zhí)行的結(jié)果：①當(dāng)前磁道號(hào)的值在隨機(jī)產(chǎn)生的磁道號(hào)中間時(shí)：分析：1.先來(lái)先效勞算法：從當(dāng)前磁道號(hào)開始，按照隨機(jī)產(chǎn)生的磁道號(hào)順序，從前到后依次訪問。2.最短尋道時(shí)間優(yōu)先算法：先把當(dāng)前磁道號(hào)參加隨機(jī)產(chǎn)生的磁道號(hào)中，再?gòu)男〉酱笈判?；定位到?dāng)前磁道號(hào)，將其與左右兩個(gè)磁道號(hào)進(jìn)行比擬，輸出近的一個(gè)；以剛剛輸出的磁道號(hào)為根底，再重復(fù)比擬它左右兩個(gè)，假設(shè)一側(cè)全部輸出了，那么將另一側(cè)依次輸出，直到兩側(cè)全部輸出。3.掃描算法：先把當(dāng)前磁道號(hào)參加隨機(jī)產(chǎn)生的磁道號(hào)中，再?gòu)男〉酱笈判?；定位到?dāng)前磁道號(hào)，假設(shè)用戶定義磁頭向增加方向移動(dòng)，那么將當(dāng)前磁道號(hào)的右側(cè)依次輸出，再依次輸出左側(cè)磁道號(hào)；假設(shè)用戶定義磁頭向減少方向移動(dòng)，那么將當(dāng)前磁道號(hào)的左側(cè)依次輸出，再依次輸出右側(cè)磁道號(hào)。②當(dāng)前磁道號(hào)的值比任何一個(gè)隨機(jī)產(chǎn)生的磁道號(hào)都小時(shí)：分析：1.先來(lái)先效勞算法：從當(dāng)前磁道號(hào)開始，按照隨機(jī)產(chǎn)生的磁道號(hào)順序，從前到后依次訪問。2.最短尋道時(shí)間優(yōu)先算法：先把當(dāng)前磁道號(hào)參加隨機(jī)產(chǎn)生的磁道號(hào)中，再?gòu)男〉酱笈判颍话凑諒男〉酱箜樞蜉敵觥?.掃描算法：先把當(dāng)前磁道號(hào)參加隨機(jī)產(chǎn)生的磁道號(hào)中，再?gòu)男〉酱笈判颍灰驗(yàn)楫?dāng)前磁道號(hào)是最小值，所以不需要用戶定義磁頭移動(dòng)方向，按照從小到大順序輸出即可。③當(dāng)前磁道號(hào)的值比任何一個(gè)隨機(jī)產(chǎn)生的磁道號(hào)都大時(shí)：分析：1.先來(lái)先效勞算法：從當(dāng)前磁道號(hào)開始，按照隨機(jī)產(chǎn)生的磁道號(hào)順序，從前到后依次訪問。2.最短尋道時(shí)間優(yōu)先算法：先把當(dāng)前磁道號(hào)參加隨機(jī)產(chǎn)生的磁道號(hào)中，再?gòu)男〉酱笈判?；按照從大到小順序輸出?.掃描算法：先把當(dāng)前磁道號(hào)參加隨機(jī)產(chǎn)生的磁道號(hào)中，再?gòu)男〉酱笈判?；因?yàn)楫?dāng)前磁道號(hào)是最大值，所以不需要用戶定義磁頭移動(dòng)方向，按照從大到小順序輸出即可。

出錯(cuò)處理的結(jié)果：①菜單功能選擇錯(cuò)誤的處理：分析：假設(shè)用戶在菜單功能選擇時(shí)不小心輸入錯(cuò)誤，不在給定的0~3范圍內(nèi)時(shí)，用while語(yǔ)句提示用戶重新輸入，直到輸入正確繼續(xù)執(zhí)行。②掃描算法中磁頭移動(dòng)方向的錯(cuò)誤處理：分析：假設(shè)用戶在磁頭移動(dòng)方向選擇時(shí)不小心輸入錯(cuò)誤，不在給定的0、1范圍內(nèi)時(shí)，用while語(yǔ)句提示用戶重新輸入，直到輸入正確繼續(xù)執(zhí)行。四、設(shè)計(jì)總結(jié)通過(guò)本次課程設(shè)計(jì)，我更加清楚地理解了磁盤調(diào)度算法的原理，在和同組同學(xué)的配合、努力下最終完成了使用C++語(yǔ)言編寫程序。我們?cè)O(shè)計(jì)的程序可以按照用戶給出的磁道個(gè)數(shù)隨機(jī)生成磁道號(hào)，模擬磁盤訪問時(shí)磁頭的移動(dòng)，顯示不同算法的磁盤調(diào)度順序、磁頭依次移動(dòng)距離、磁頭移動(dòng)總距離、平均尋道長(zhǎng)度等。設(shè)計(jì)過(guò)程中也遇到了一些問題，局部問題與解決方法如下：首先碰到的是輸出顯示問題，一開始我們編寫的先來(lái)先效勞和掃描算法都是使用邊計(jì)算邊輸出的，先來(lái)先效勞的輸出沒有任何問題，但是到掃描算法的時(shí)候，發(fā)現(xiàn)磁頭依次移動(dòng)距離的輸出很麻煩，后來(lái)經(jīng)過(guò)我們的討論，決定將輸出函數(shù)單獨(dú)編寫，這樣即減少了代碼的長(zhǎng)度，也使程序更精簡(jiǎn)、更便于閱讀。具體實(shí)現(xiàn)是將正確的磁盤調(diào)度順序存入數(shù)組，然后使用參數(shù)傳遞的方式調(diào)用輸出函數(shù)，統(tǒng)一計(jì)算并輸出顯示。在編寫最短尋道時(shí)間優(yōu)先算法的過(guò)程中，一開始是想將磁頭指向的磁道號(hào)和剩余磁道號(hào)依次比擬找出尋道時(shí)間最短的磁道號(hào)，后來(lái)在網(wǎng)上查閱資料的時(shí)候發(fā)現(xiàn)，如果將隨機(jī)生成的磁道號(hào)先從小到大排序，會(huì)大大減少比擬的次數(shù)，每次只要和左右兩個(gè)磁道號(hào)比擬就可以了，碰到磁頭在一側(cè)的情況，直接依次訪問另一側(cè)的磁道號(hào)即可。在測(cè)試過(guò)程中，發(fā)現(xiàn)如果先選擇最短尋道時(shí)間優(yōu)先算法或者掃描算法，再選擇先來(lái)先效勞算法時(shí)，磁道號(hào)顯示的是上一次執(zhí)行的磁道號(hào)。最后決定將三個(gè)算法使用的隨機(jī)磁道號(hào)用不同的數(shù)組獨(dú)立存放，先來(lái)先效勞用a[]、最短尋道時(shí)間優(yōu)先用aa[]、掃描算法用aaa[]存放，防止互相影響。計(jì)算平均尋道長(zhǎng)度時(shí)，一開始得到的數(shù)值不夠精確，后來(lái)決定使用double類型代替int類型，僅僅將avg改成double類型不行，測(cè)試時(shí)發(fā)現(xiàn)要將sum也改成double類型的才可以，因?yàn)槭鞘褂胊vg=sum/(n+1)計(jì)算的平均尋道長(zhǎng)度。關(guān)于數(shù)組下標(biāo)確實(shí)定和下標(biāo)值的判斷條件是我們?cè)O(shè)計(jì)時(shí)的最大問題。碰到無(wú)法確定哪一步出錯(cuò)的時(shí)候，可以在程序中適當(dāng)添加輸出語(yǔ)句的標(biāo)記，按照輸出語(yǔ)句和運(yùn)行顯示結(jié)果，進(jìn)一步確定出錯(cuò)位置，并進(jìn)行相應(yīng)調(diào)整；碰到多一個(gè)或少一個(gè)磁道號(hào)的情況，一般就是判斷條件或者循環(huán)條件的問題了，是否取等號(hào)、加一減一都可以通過(guò)舉具體的例子來(lái)分析獲得；修改一處后要用不同的數(shù)值來(lái)測(cè)試，保證程序的的正確性，不能改了多處后再進(jìn)行測(cè)試，容易越改越錯(cuò)?？偟膩?lái)說(shuō)本次課程設(shè)計(jì)還是很成功的，雖然過(guò)程中遇到了很多大大小小的問題，但都被我們一一解決了，可能我們?cè)O(shè)計(jì)的程序還不能算完美，還存在一些需要改良的地方，但我們都盡自己最大的努力去發(fā)現(xiàn)并解決了，也正是因?yàn)檫@些問題的存在，讓我們?nèi)ニ伎?、去調(diào)試，在完善和修改中學(xué)習(xí)。這短短的五天時(shí)間，我感覺自己收獲頗多。五、附源程序#include<iostream>#include<algorithm>//遞增排序用到的sort函數(shù)#include<ctime>//隨機(jī)時(shí)用到的time函數(shù)usingnamespacestd;voidFCFS(inta[],intn);//先來(lái)先效勞算法voidSSTF(intaa[],intb[],intn);//最短尋道時(shí)間優(yōu)先算法voidSCAN(intaaa[],intb[],intn);//掃描算法voidPrint(intb[],intn);//顯示函數(shù)//輸出顯示函數(shù)〔Print〕voidPrint(intb[],intn){ inti; doublesum=0,avg=0; cout<<"磁盤調(diào)度順序?yàn)椋?; for(i=0;i<n+1;i++)//按訪問順序輸出磁道號(hào) cout<<b[i]<<""; cout<<endl; cout<<"磁頭依次移動(dòng)距離："; for(i=0;i<n;i++) { sum+=abs(b[i+1]-b[i]);//abs絕對(duì)值函數(shù) cout<<abs(b[i+1]-b[i])<<""; } avg=sum/(n+1); cout<<endl; cout<<"磁頭移動(dòng)總距離為："<<sum<<endl; cout<<"平均尋道長(zhǎng)度為："<<avg<<endl;}//先來(lái)先效勞〔FCFS〕voidFCFS(inta[],intn){ doublesum=0,avg=0; cout<<"請(qǐng)輸入當(dāng)前磁道號(hào)："; cin>>a[0];//確定當(dāng)前磁頭所在位置 Print(a,n);}//最短尋道時(shí)間優(yōu)先〔SSTF〕voidSSTF(intaa[],intb[],intn){ intk=0,first,i,j;//k用于確定磁頭位置 cout<<"請(qǐng)輸入當(dāng)前的磁道號(hào)："; cin>>aa[0]; first=aa[0];//當(dāng)前磁頭位置賦給first sort(aa,aa+(n+1));//從小到大排序 if(aa[n]<=first)//當(dāng)前磁頭最大時(shí) { for(i=n,j=0;i>=0;i--,j++) b[j]=aa[i]; } else if(first<=aa[0])//當(dāng)前磁頭最小時(shí) { for(i=0;i<n+1;i++) b[i]=aa[i]; } else { while(aa[k]<first)//磁頭在數(shù)組中間時(shí) k++;//找到磁頭在數(shù)組a中的下標(biāo)k intl=k-1;//左側(cè)數(shù)組下標(biāo)l intr=k+1;//右側(cè)數(shù)組下標(biāo)r intj=0;//新數(shù)組下標(biāo)j b[j++]=first;//磁頭的值給新數(shù)組b[0],j+1 while((l>=0)&&(r<n+1)) { if((first-aa[l])<=(aa[r]-first))//離左邊近 { b[j]=aa[l]; first=aa[l]; l--; j++; } else { b[j]=aa[r]; first=aa[r]; r++; j++; } } if(l==-1)//磁頭移到最小位置〔最左側(cè)〕 { for(;r<n+1;r++,j++)//依次訪問右側(cè)磁道 b[j]=aa[r]; } else { if(r==n+1)//磁頭移到最大位置〔最右側(cè)〕 { for(;l>-1;l--,j++)//依次訪問左側(cè)磁道 b[j]=aa[l]; } } } Print(b,n);}//掃描算法〔SCAN〕voidSCAN(intaaa[],intb[],intn){ intk=0,first,i,j;//k用于確定磁頭位置 cout<<"請(qǐng)輸入當(dāng)前的磁道號(hào)："; cin>>aaa[0]; first=aaa[0];//當(dāng)前磁頭位置賦給first sort(aaa,aaa+(n+1));//從小到大排序 if(aaa[n]<=first)//當(dāng)前磁頭最大時(shí) { for(i=n,j=0;i>=0;i--,j++) b[j]=aaa[i]; } else if(first<=aaa[0])//當(dāng)前磁頭最小時(shí) { for(i=0;i<n+1;i++) b[i]=aaa[i]; } else { while(aaa[k]<first)//磁頭在數(shù)組中間時(shí) k++;//找到磁頭在數(shù)組a中的下標(biāo)k intl=k-1;//左側(cè)數(shù)組下標(biāo)l intr=k+1;//右側(cè)數(shù)組下標(biāo)r intj=0;//新數(shù)組下標(biāo)j intdir;//磁頭移動(dòng)方向 b[j++]=first;//磁頭的值給新數(shù)組b[0],j+1 cout<<"請(qǐng)輸入當(dāng)前磁頭移動(dòng)的方向(增加1，減少0):"; cin>>dir; while(dir!=0&&dir!=1) { cout<<"輸入錯(cuò)誤，請(qǐng)輸入1或0："; cin>>dir; } if(dir==0)//磁頭向減小方向移動(dòng) { for(;l>=0;l--,j++) b[j]=aaa[l]; for(;r<n+1;r++,j++) b[j]=aaa[r]; } if(dir==1)//磁頭向增加方向移動(dòng) { while(r<n+1) b[j++]=aaa[r++]; while(l>=0) b[j++]=aaa[l--]; } } Print(b,n); }intmain(){ cout<<endl; cout<<"—————?dú)g送使用磁盤調(diào)度算法—————"<<endl; cout<<"——1.先來(lái)先效勞算法〔FCFS〕——"<<endl; cout<<"——2.最短尋道時(shí)間優(yōu)先算法〔SSTF〕——"<<endl; cout<<"