操作系統(tǒng)磁盤調度算法

-.z.操作系統(tǒng)課程設計任務書題目：磁盤調度算法院系：專業(yè)：班級：姓名：學號：指導教師：設計時間：指導教師評語成績評定：指導教師簽字：年月日目錄1、需求分析41.1課題描述41.2課題目的41.3理論依據72、概要設計82.1設計方法82.2技術82.3運行環(huán)境83、詳細設計93.1流程圖113.2程序主要代碼134、運行結果及分析144.1運行結果154.2結果詳細分析165、總結和心得166、參考文獻177、附錄：程序源代碼231、需求分析1.1課題描述這次課程設計我研究的題目是：磁盤調度算法。具體包括三種算法分別是：先來先效勞算法〔FCFS〕、最短尋道時間優(yōu)先算法(SSTF)、掃描算法〔電梯調度算法〕(SCAN)。1.2課題目的通過這次實驗，加深對磁盤調度算法的理解，進一步掌握先來先效勞FCFS，最短尋道時間優(yōu)先SSTF，掃描SCAN算法的實現(xiàn)方法。1.3理論依據設備的動態(tài)分配算法與進程調度相似，也是基于一定的分配策略的。常用的分配策略有先請求先分配、優(yōu)先級高者先分配等策略。在多道程序系統(tǒng)中，低效率通常是由于磁盤類旋轉設備使用不當造成的。操作系統(tǒng)中，對磁盤的要求來自多方面，常常需要排隊。這時，對眾多的要求按一定的次序響應，會直接影響磁盤的工作效率，進而影響系統(tǒng)的性能。磁盤的時間因子由3局部構成，它們是查找〔查找磁道〕時間、等待〔旋轉等待扇區(qū)〕時間和數(shù)據傳輸時間，其中查找時間是決定因素。因此，磁盤調度算法先考慮優(yōu)化查找策略，需要時再優(yōu)化旋轉等待策略。平均尋道長度〔L〕為所有磁道所需移動距離之和除以總的所需的磁道數(shù)〔N〕，即：L=〔M1+M2+??+Mi+??+MN〕/N其中Mi為所需的磁道號所需移動的磁道數(shù)。啟動磁盤執(zhí)行輸入輸出操作時，要把移動臂移動到指定的柱面，再等待指定扇區(qū)的旋轉到磁頭位置下，然后讓指定的磁頭進展讀寫，完成信息傳送。因此，執(zhí)行一次輸入輸出所花的時間有：尋找時間——磁頭在移動臂帶動下移動到指定柱面所花的時間。延遲時間——指定扇區(qū)旋轉到磁頭下所需的時間。傳送時間——由磁頭進程讀寫完成信息傳送的時間。其中傳送信息所花的時間，是在硬件設計就固定的。而尋找時間和延遲時間是與信息在磁盤上的位置有關。為了減少移動臂進展移動花費的時間，每個文件的信息不是按盤面上的磁道順序存放滿一個盤面后，再放到下一個盤面上。而是按柱面存放，同一柱面上的各磁道被放滿信息后，再放到下一個柱面上。所以各磁盤的編號按柱面順序，每個柱面按磁道順序，每個磁道又按扇區(qū)順序進展排序。磁盤是可供多個進程共享的設備，當有多個進程都要求磁盤是，應采用一種最正確調度算法，以使各種進程對磁盤的平均時間最小。由于在磁盤的時間中，主要是尋道時間，因此，磁盤調度的目標，是使磁盤的平均尋道時間最少。目前常用的磁盤帝調度算法有：先來先效勞、最短尋道時間優(yōu)先及掃描等算法。先來先效勞〔FCFS〕調度:按先來后到次序效勞，未作優(yōu)化。最簡單的移臂調度算法是"先來先效勞〞調度算法，這個算法實際上不考慮者要求的物理位置，而只是考慮者提出請求的先后次序。例如，如果現(xiàn)在讀寫磁頭正在50號柱面上執(zhí)行輸出操作，而等待者依次要的柱面為130、199、32、159、15、148、61、99，則，當50號柱面上的操作完畢后，移動臂將按請求的先后次序先移到130號柱面，最后到達99號柱面。采用先來先效勞算法決定等待者執(zhí)行輸入輸出操作的次序時，移動臂來回地移動。先來先效勞算法花費的尋找時間較長，所以執(zhí)行輸入輸出操作的總時間也很長。最短尋找時間優(yōu)先調度算法總是從等待者中挑選尋找時間最短的那個請求先執(zhí)行的，而不管者到來的先后次序?，F(xiàn)在仍利用同一個例子來討論，現(xiàn)在當50號柱面的操作完畢后，應該先處理61號柱面的請求，然后到達32號柱面執(zhí)行操作，隨后處理15號柱面請求，后繼操作的次序應該是99、130、148、159、199。采用最短尋找時間優(yōu)先算法決定等待者執(zhí)行操作的次序時，讀寫磁頭總共移動了200多個柱面的距離，與先來先效勞、算法比擬，大幅度地減少了尋找時間，因而縮短了為各者請求效勞的平均時間，也就提高了系統(tǒng)效率。但最短查找時間優(yōu)先〔SSTF〕調度，F(xiàn)CFS會引起讀寫頭在盤面上的大范圍移動，SSTF查找距離磁頭最短〔也就是查找時間最短〕的請求作為下一次效勞的對象。SSTF查找模式有高度局部化的傾向，會推遲一些請求的效勞，甚至引起無限拖延〔又稱饑餓〕。SCAN算法又稱電梯調度算法。SCAN算法是磁頭前進方向上的最短查找時間優(yōu)先算法，它排除了磁頭在盤面局部位置上的往復移動，SCAN算法在很大程度上消除了SSTF算法的不公平性，但仍有利于對中間磁道的請求。"電梯調度〞算法是從移動臂當前位置開場沿著臂的移動方向去選擇離當前移動臂最近的那個柱者，如果沿臂的移動方向無請求時，就改變臂的移動方向再選擇。這好比乘電梯，如果電梯已向上運動到4層時，依次有3位乘客陳生、伍生、張生在等候乘電梯。他們的要求是：陳生在2層等待去10層；伍生在5層等待去底層；張生在8層等待15層。由于電梯目前運動方向是向上，所以電梯的形成是先把乘客張生從8層帶到15層，然后電梯換成下行方向，把乘客伍生從5層帶到底層，電梯最后再調換方向，把乘客陳生從2層送到10層。但是，"電梯調度〞算法在實現(xiàn)時，不僅要記住讀寫磁頭的當前位置，還必須記住移動臂的當前前進方向。2、概要設計2.1設計方法通過C語言的編程，設計程序模擬先來先效勞FCFS，最短尋道時間優(yōu)先SSTF，和掃描SCAN算法的工作過程。假設有n個磁道號所組成的磁道序列，給定開場磁道號m和磁頭移動的方向〔正向或者反向〕，分別利用不同的磁盤調度算法磁道序列，給出磁頭每一次移動的過程，算出磁頭移動的距離，繼而計算每種算法的平均尋道長度。2.2技術C語言、操作系統(tǒng)磁盤調度算法、C++。2.3運行環(huán)境Window10、VC++6.0。3、詳細設計3.1流程圖先來先效勞算法〔FCFS〕：完畢Avg=sum/(m)j<m目前的位置變?yōu)楫斍暗奈恢胘++輸出磁盤調度序列array[j]磁頭移動總距離Sum+=abs(array[j]-array[i])磁頭移動距離Sum=abs(now-array[0])輸入當前磁道號now開場完畢Avg=sum/(m)j<m目前的位置變?yōu)楫斍暗奈恢胘++輸出磁盤調度序列array[j]磁頭移動總距離Sum+=abs(array[j]-array[i])磁頭移動距離Sum=abs(now-array[0])輸入當前磁道號now開場最短尋道時間優(yōu)先算法(SSTF)：開場開場完畢完畢掃描SCAN算法：開場開場完畢完畢3.2程序主要代碼先來先效勞算法〔FCFS〕：voidFCFS(vector<int>m_vec,intposition){//先來先效勞算法dis=0;average_distance=0;for(vector<int>::iteratorit=m_vec.begin();it!=m_vec.end();it++){dis+=abs(position-*it);Sleep(500);cout<<"->"<<*it;position=*it;}pute_dis(m_vec,dis,average_distance);}最短尋道時間優(yōu)先算法(SSTF)：voidSSTF(vector<int>m_vec,intposition){//最短尋道時間算法dis=0;average_distance=0;sort(m_vec.begin(),m_vec.end());//從小到大排序inti=0;for(vector<int>::iteratorit=m_vec.begin();it!=m_vec.end();it++){if(position>=*it)i++;}intcount=0;intleft=i-1;intright=i;while(count<m_vec.size()){if((left>=0&&abs(m_vec[right]-position)>abs(m_vec[left]-position))||right>=m_vec.size()){dis+=abs(m_vec[left]-position);Sleep(500);cout<<"->"<<m_vec[left];position=m_vec[left];left--;}else{dis+=abs(m_vec[right]-position);Sleep(500);cout<<"->"<<m_vec[right];position=m_vec[right];right++;}count++;}pute_dis(m_vec,dis,average_distance);}掃描SCAN算法：voidSCAN(vector<int>m_vec,intposition){//電梯調度算法dis=0;average_distance=0;sort(m_vec.begin(),m_vec.end());//從小到大排序inti=0;for(vector<int>::iteratorit=m_vec.begin();it!=m_vec.end();it++){if(position>=*it)i++;//找到position所在的磁道}intleft=i-1;//先從外到內掃描intright=i;while(left>=0){dis+=abs(position-m_vec[left]);Sleep(500);cout<<"->"<<m_vec[left];position=m_vec[left];left--;}while(right<m_vec.size()){dis+=abs(position-m_vec[right]);Sleep(500);cout<<"->"<<m_vec[right];position=m_vec[right];right++;}pute_dis(m_vec,dis,average_distance);}4、運行結果及分析4.1運行結果先來先效勞算法〔FCFS〕：最短尋道時間優(yōu)先算法(SSTF)：掃描SCAN算法：4.2結果詳細分析FCFS：這是一種比擬簡單的磁盤調度算法。它根據進程請求磁盤的先后次序進展調度。此算法由于未對尋道進展優(yōu)化，在對磁盤的請求比擬多的情況下，此算法將降低設備效勞的吞吐量，致使平均尋道時間可能較長，但各進程得到效勞的響應時間的變化幅度較小。SSTF：該算法選擇這樣的進程，其要求的磁道與當前磁頭所在的磁道距離最近，以使每次的尋道時間最短，該算法可以得到比擬好的吞吐量，但卻不能保證平均尋道時間最短。SCAN：掃描算法不僅考慮到欲的磁道與當前磁道的距離，更優(yōu)先考慮的是磁頭的當前移動方向。此算法根本上克制了最短尋道時間優(yōu)先算法的效勞集中于中間磁道和響應時間變化比擬大的缺點，而具有最短尋道時間優(yōu)先算法的優(yōu)點即吞吐量較大，平均響應時間較小，但由于是擺動式的掃描方法，兩側磁道被的頻率仍低于中間磁道。5、總結和心得通過這次的課程設計使我認識到要將操作系統(tǒng)這門計算機專業(yè)的課學好不僅僅是要把書上的根本知識學好而且還要不斷進展實踐，將所學的跟實踐操作結合起來才能更好地穩(wěn)固所學，才能提高自己實踐能力。通過這次的設計使我認識到只停留在外表理解問題是很難使問題得到很好的解決的，實踐能力與理論知識同樣重要?？梢哉f此課程設計的理論難度并不大，各種流圖設計特別是算法過程圖的設計很容易忽略操作性細節(jié)，在實際調試中帶來很大麻煩，需要特別注意，但是假設要深入開掘其中的東西，并且實際去編程實現(xiàn)，就遇到了相當大的難度。因為與之涉及的很多方面并沒有學過，需要自己去自學和實踐檢驗。通過模擬磁盤調度及進程排隊算法來加深對操作系統(tǒng)中各個磁臂調度算法概念的理解模擬磁盤調度算法，實現(xiàn)各種不同調度算法的過程，并計算各算法的平均尋道長度，以便于我們判斷各種算法的優(yōu)劣以及各種算法使用的場合。6、參考文獻[1].湯子瀛，哲鳳屏，湯小丹."計算機操作系統(tǒng)".**電子科技大學,2005;[2].譚浩強編著."C語言程序設計〔第3版〕".清華大學，2005;[3].吳乃陵，況迎輝."C++程序設計〔第二版〕".高等教育，2005。7、附錄：程序源代碼FCFS：#include<iostream>#include<time.h>#include<vector>#include<algorithm>#include<math.h>#include<stdlib.h>#include<cstring>#include<windows.h>#include<fstream>usingnamespacestd;intposition=0;//當前磁道位置intdis=0;doubleaverage_distance=0;voidrequest(vector<int>&m_vec,ofstream&outfile){cout<<"隨機生成磁盤序列："<<endl;intn=0;srand(time(NULL));//添加隨機數(shù)種子n=rand()%20+1;inttemp=0;for(inti=0;i<n;i++){temp=rand()%100;m_vec.push_back(temp);cout<<temp<<"";outfile<<temp<<endl;}cout<<endl;position=rand()%100;cout<<"當前磁道："<<position<<endl;}voidpute_dis(vector<int>m_vec,int&dis,double&average_distance){average_distance=(double)dis/(double)m_vec.size();}voidFCFS(vector<int>m_vec,intposition){//先來先效勞算法dis=0;average_distance=0;for(vector<int>::iteratorit=m_vec.begin();it!=m_vec.end();it++){dis+=abs(position-*it);Sleep(500);cout<<"->"<<*it;position=*it;}pute_dis(m_vec,dis,average_distance);}voidprint(){cout<<endl<<endl;cout<<"經計算，磁頭移動的總距離為:"<<dis<<endl;cout<<"磁頭平均移動距離:"<<average_distance<<endl;cout<<endl<<endl;}intmain(){ ofstreamoutfile;outfile.open("data.t*t");vector<int>m_vec;request(m_vec,outfile);//請求效勞序列cout<<"磁盤請求的效勞狀況："<<endl;FCFS(m_vec,position); print(); outfile.close();return0;}SSTF:#include<iostream>#include<time.h>#include<vector>#include<math.h>#include<stdlib.h>#include<algorithm>#include<cstring>#include<windows.h>#include<fstream>usingnamespacestd;intposition=0;//當前磁道位置intdis=0;doubleaverage_distance=0;voidrequest(vector<int>&m_vec,ofstream&outfile){cout<<"隨機生成磁盤序列："<<endl;intn=0;srand(time(NULL));//添加隨機數(shù)種子n=rand()%20+1;inttemp=0;for(inti=0;i<n;i++){temp=rand()%100;m_vec.push_back(temp);cout<<temp<<"";outfile<<temp<<endl;}cout<<endl;position=rand()%100;cout<<"當前磁道："<<position<<endl;}voidpute_dis(vector<int>m_vec,int&dis,double&average_distance){average_distance=(double)dis/(double)m_vec.size();}voidSSTF(vector<int>m_vec,intposition){//最短尋道時間算法dis=0;average_distance=0;sort(m_vec.begin(),m_vec.end());//從小到大排序inti=0;for(vector<int>::iteratorit=m_vec.begin();it!=m_vec.end();it++){if(position>=*it)i++;}intcount=0;intleft=i-1;intright=i;while(count<m_vec.size()){if((left>=0&&abs(m_vec[right]-position)>abs(m_vec[left]-position))||right>=m_vec.size()){dis+=abs(m_vec[left]-position);Sleep(500);cout<<"->"<<m_vec[left];position=m_vec[left];left--;}else{dis+=abs(m_vec[right]-position);Sleep(500);cout<<"->"<<m_vec[right];position=m_vec[right];right++;}count++;}pute_dis(m_vec,dis,average_distance);}voidprint(){cout<<endl<<endl;cout<<"經計算，磁頭移動的總距離為:"<<dis<<endl;cout<<"磁頭平均移動距離:"<<average_distance<<endl;cout<<endl<<endl;}intmain(){ofstreamoutfile;outfile.open("data.t*t");vector<int>m_vec;request(m_vec,outfile);//請求效勞序列cout<<"磁盤請求的效勞狀況："<<endl;SSTF(m_vec,position); print(); outfile.close();return0;}SCAN:#include<iostream>#include<time.h>#include<vector>#include<math.h>#include<stdlib.h>#include<algorithm>#include<cstring>#include<windows.h>#include<fstream>usingnamespacestd;intposition=0;//當前磁道位置intdis=0;doubleaverage_distance=0;voidrequest(vector<int>&m_vec,ofstream&outfile){cout<<"隨機生成磁盤序列："<<endl;intn=0;srand(time(NULL));//添加隨機數(shù)種子n=rand()%20+1;inttemp=0;for(inti=0;i<n;i++){temp=rand()%100;m_vec.push_back(temp);cout<<temp<<"";outfile<<temp<<endl;}cout<<endl;position=rand()%100;cout<<"當前磁道："<<position<<endl;}voidpute_dis(vector<int>m_vec,int&dis,double&average_distance){average_distance=(double)dis/(double)m_vec.size();}void