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

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

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