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

操作系統(tǒng)課程設計任務書題 目： 磁盤調度算法 院 系： 專 業(yè)： 班 級： 姓 名： 學 號： 指導教師： 設計時間： 2018.1.1-2018.1.5 指導教師評語成績評定： 指導教師簽字：年月日 目 錄1、需求分析41.1課題描述41.2課題目的41.3理論依據(jù)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理論依據(jù) 設備的動態(tài)分配算法與進程調度相似，也是基于一定的分配策略的。常用的分配策略有先請求先分配、優(yōu)先級高者先分配等策略。在多道程序系統(tǒng)中，低效率通常是由于磁盤類旋轉設備使用不當造成的。操作系統(tǒng)中，對磁盤的訪問要求來自多方面，常常需要排隊。這時，對眾多的訪問要求按一定的次序響應，會直接影響磁盤的工作效率，進而影響系統(tǒng)的性能。訪問磁盤的時間因子由3部分構成，它們是查找（查找磁道）時間、等待（旋轉等待扇區(qū)）時間和數(shù)據(jù)傳輸時間，其中查找時間是決定因素。因此，磁盤調度算法先考慮優(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í)行的，而不管訪問者到來的先后次序。現(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)jm目前的位置變?yōu)楫斍暗奈恢胘+輸出磁盤調度序列arrayj磁頭移動總距離Sum+=abs(arrayj-arrayi)磁頭移動距離Sum=abs(now-array0)輸入當前磁道號now開始最短尋道時間優(yōu)先算法(SSTF)：開始 結束掃描SCAN算法：開始 結束3.2程序主要代碼先來先服務算法（FCFS）：void FCFS(vectorm_vec,int position) /先來先服務算法dis = 0;average_distance = 0;for(vector:iterator it=m_vec.begin();it!=m_vec.end();it+)dis += abs(position-*it);Sleep(500);cout*it;position = *it;compute_dis(m_vec,dis,average_distance); 最短尋道時間優(yōu)先算法(SSTF)： void SSTF(vectorm_vec,int position) /最短尋道時間算法 dis = 0; average_distance = 0; sort(m_vec.begin(),m_vec.end(); /從小到大排序 int i = 0; for(vector:iterator it=m_vec.begin();it!=m_vec.end();it+) if(position = *it) i+; int count = 0; int left = i-1; int right = i; while(count=0 & abs(m_vecright-position) abs(m_vecleft-position) | right=m_vec.size() dis += abs(m_vecleft-position); Sleep(500); coutm_vecleft; position = m_vecleft; left-; else dis += abs(m_vecright-position); Sleep(500); coutm_vecright; position = m_vecright; right+; count+; compute_dis(m_vec,dis,average_distance);掃描SCAN算法： void SCAN(vectorm_vec,int position) /電梯調度算法 dis = 0; average_distance = 0; sort(m_vec.begin(),m_vec.end(); /從小到大排序 int i = 0; for(vector:iterator it=m_vec.begin();it!=m_vec.end();it+) if(position = *it) i+; /找到position所在的磁道 int left = i - 1; /先從外到內掃描 int right = i; while(left = 0) dis += abs(position - m_vecleft); Sleep(500); coutm_vecleft; position = m_vecleft; left -; while(right m_vec.size() dis += abs(position - m_vecright); Sleep(500); coutm_vecright; position = m_vecright; right +; compute_dis(m_vec,dis,average_distance);4、運行結果及分析 4.1運行結果先來先服務算法（FCFS）：最短尋道時間優(yōu)先算法(SSTF)： 掃描SCAN算法： 4.2結果詳細分析 FCFS ：這是一種比較簡單的磁盤調度算法。它根據(jù)進程請求訪問磁盤的先后次序進行調度。此算法由于未對尋道進行優(yōu)化，在對磁盤的訪問請求比較多的情況下，此算法將降低設備服務的吞吐量，致使平均尋道時間可能較長，但各進程得到服務的響應時間的變化幅度較小。SSTF： 該算法選擇這樣的進程，其要求訪問的磁道與當前磁頭所在的磁道距離最近，以使每次的尋道時間最短，該算法可以得到比較好的吞吐量，但卻不能保證平均尋道時間最短。SCAN ：掃描算法不僅考慮到欲訪問的磁道與當前磁道的距離，更優(yōu)先考慮的是磁頭的當前移動方向。此算法基本上克服了最短尋道時間優(yōu)先算法的服務集中于中間磁道和響應時間變化比較大的缺點，而具有最短尋道時間優(yōu)先算法的優(yōu)點即吞吐量較大，平均響應時間較小，但由于是擺動式的掃描方法，兩側磁道被訪問的頻率仍低于中間磁道。5、總結和心得 通過這次的課程設計使我認識到要將操作系統(tǒng)這門計算機專業(yè)的課學好不僅僅是要把書上的基本知識學好而且還要不斷進行實踐，將所學的跟實踐操作結合起來才能更好地鞏固所學，才能提高自己實踐能力。通過這次的設計使我認識到只停留在表面理解問題是很難使問題得到很好的解決的，實踐能力與理論知識同樣重要?？梢哉f此課程設計的理論難度并不大，各種流圖設計特別是算法過程圖的設計很容易忽略操作性細節(jié)，在實際調試中帶來很大麻煩，需要特別注意，但是若要深入發(fā)掘其中的東西，并且實際去編程實現(xiàn)，就遇到了相當大的難度。因為與之涉及的很多方面并沒有學過，需要自己去自學和實踐檢驗。通過模擬磁盤調度及進程排隊算法來加深對操作系統(tǒng)中各個磁臂調度算法概念的理解模擬磁盤調度算法，實現(xiàn)各種不同調度算法的過程，并計算各算法的平均尋道長度，以便于我們判斷各種算法的優(yōu)劣以及各種算法使用的場合。6、參考文獻 1. 湯子瀛，哲鳳屏，湯小丹. 計算機操作系統(tǒng).西安電子科技大學出版社, 2005; 2. 譚浩強編著. C語言程序設計（第3版）.清華大學出版社，2005;3. 吳乃陵，況迎輝. C+程序設計（第二版）.高等教育出版社，2005。 7、附錄：程序源代碼FCFS：#include #include #include #include#include #include #include #include #include using namespace std;int position = 0; /當前磁道位置int dis = 0;double average_distance = 0;void request(vector&m_vec,ofstream &outfile) cout隨機生成磁盤序列：endl; int n = 0; srand(time(NULL); /添加隨機數(shù)種子 n = rand() % 20 + 1; int temp = 0; for(int i=0;in;i+) temp = rand() % 100; m_vec.push_back(temp); couttemp ; outfiletempendl; coutendl; position = rand() % 100; cout當前磁道：positionendl;void compute_dis(vectorm_vec,int &dis,double &average_distance) average_distance = (double)dis / (double)m_vec.size();void FCFS(vectorm_vec,int position) /先來先服務算法 dis = 0; average_distance = 0; for(vector:iterator it=m_vec.begin();it!=m_vec.end();it+) dis += abs(position-*it); Sleep(500); cout*it; position = *it; compute_dis(m_vec,dis,average_distance);void print() coutendlendl; cout經(jīng)計算，磁頭移動的總距離為:disendl; cout磁頭平均移動距離:average_distanceendl; coutendlendl;int main()ofstream outfile; outfile.open(data.txt); vectorm_vec; request(m_vec,outfile); /請求服務序列 cout磁盤請求的服務狀況：endl; FCFS(m_vec, position);print();outfile.close(); return 0;SSTF:#include #include #include #include #include #include#include #include #include using namespace std;int position = 0; /當前磁道位置int dis = 0;double average_distance = 0;void request(vector&m_vec,ofstream &outfile) cout隨機生成磁盤序列：endl; int n = 0; srand(time(NULL); /添加隨機數(shù)種子 n = rand() % 20 + 1; int temp = 0; for(int i=0;in;i+) temp = rand() % 100; m_vec.push_back(temp); couttemp ; outfiletempendl; coutendl; position = rand() % 100; cout當前磁道：positionendl;void compute_dis(vectorm_vec,int &dis,double &average_distance) average_distance = (double)dis / (double)m_vec.size();void SSTF(vectorm_vec,int position) /最短尋道時間算法 dis = 0; average_distance = 0; sort(m_vec.begin(),m_vec.end(); /從小到大排序 int i = 0; for(vector:iterator it=m_vec.begin();it!=m_vec.end();it+) if(position = *it) i+; int count = 0; int left = i-1; int right = i; while(count=0 & abs(m_vecright-position) abs(m_vecleft-position) | right=m_vec.size() dis += abs(m_vecleft-position); Sleep(500); coutm_vecleft; position = m_vecleft; left-; else dis += abs(m_vecright-position); Sleep(500); coutm_vecright; position = m_vecright; right+; count+; compute_dis(m_vec,dis,average_distance);void print() coutendlendl; cout經(jīng)計算，磁頭移動的總距離為:disendl; cout磁頭平均移動距離:average_distanceendl; coutendlendl;int main() ofstream outfile; outfile.open(data.txt); vectorm_vec; request(m_vec,outfile); /請求服務序列 cout磁盤請求的服務狀況：endl; SSTF(m_vec, position);print();outfile.close(); return 0;SCAN:#include #include #include #include #include #include#include #include #include using namespace std;int position = 0; /當前磁道位置int dis = 0;double average_distance = 0;void request(vector&m_vec,ofstream &outfile) cout隨機生成磁盤序列：endl; int n = 0; srand(time(NULL); /添加隨機數(shù)種子 n = rand() % 20 + 1; int temp = 0; for(int i=0;in;i+) temp = rand() % 100; m_vec.push_back(temp); couttemp ; outfiletempendl; coutendl; position = rand() % 100; cout當前磁道：positionendl;void compute_dis(vectorm_vec,int &dis,