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

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