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

1、 操作系統(tǒng)課程設(shè)計(jì)任務(wù)書題 目： 磁盤調(diào)度算法 院 系： 專 業(yè)： 班 級： 姓 名： 學(xué) 號： 指導(dǎo)教師： 設(shè)計(jì)時(shí)間： 2018.1.1-2018.1.5 指導(dǎo)教師評語成績評定： 指導(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)度算法。具體包括三種算法分別是：先來

2、先服務(wù)算法（FCFS）、最短尋道時(shí)間優(yōu)先算法(SSTF)、掃描算法（電梯調(diào)度算法）(SCAN)。1.2課題目的 通過這次實(shí)驗(yàn)，加深對磁盤調(diào)度算法的理解，進(jìn)一步掌握先來先服務(wù)FCFS，最短尋道時(shí)間優(yōu)先SSTF，掃描SCAN算法的實(shí)現(xiàn)方法。1.3理論依據(jù) 設(shè)備的動態(tài)分配算法與進(jìn)程調(diào)度相似，也是基于一定的分配策略的。常用的分配策略有先請求先分配、優(yōu)先級高者先分配等策略。在多道程序系統(tǒng)中，低效率通常是由于磁盤類旋轉(zhuǎn)設(shè)備使用不當(dāng)造成的。操作系統(tǒng)中，對磁盤的訪問要求來自多方面，常常需要排隊(duì)。這時(shí)，對眾多的訪問要求按一定的次序響應(yīng)，會直接影響磁盤的工作效率，進(jìn)而影響系統(tǒng)的性能。訪問磁盤的時(shí)間因子由3部分構(gòu)成

3、，它們是查找（查找磁道）時(shí)間、等待（旋轉(zhuǎn)等待扇區(qū)）時(shí)間和數(shù)據(jù)傳輸時(shí)間，其中查找時(shí)間是決定因素。因此，磁盤調(diào)度算法先考慮優(yōu)化查找策略，需要時(shí)再優(yōu)化旋轉(zhuǎn)等待策略。 平均尋道長度（L）為所有磁道所需移動距離之和除以總的所需訪問的磁道數(shù)（N），即：L=（M1+M2+Mi+MN）/N 其中Mi為所需訪問的磁道號所需移動的磁道數(shù)。 啟動磁盤執(zhí)行輸入輸出操作時(shí)，要把移動臂移動到指定的柱面，再等待指定扇區(qū)的旋轉(zhuǎn)到磁頭位置下，然后讓指定的磁頭進(jìn)行讀寫，完成信息傳送。因此，執(zhí)行一次輸入輸出所花的時(shí)間有： 尋找時(shí)間磁頭在移動臂帶動下移動到指定柱面所花的時(shí)間。 延遲時(shí)間指定扇區(qū)旋轉(zhuǎn)到磁頭下所需的時(shí)間。 傳送時(shí)間由磁頭

4、進(jìn)程讀寫完成信息傳送的時(shí)間。 其中傳送信息所花的時(shí)間，是在硬件設(shè)計(jì)就固定的。而尋找時(shí)間和延遲時(shí)間是與信息在磁盤上的位置有關(guān)。為了減少移動臂進(jìn)行移動花費(fèi)的時(shí)間，每個(gè)文件的信息不是按盤面上的磁道順序存放滿一個(gè)盤面后，再放到下一個(gè)盤面上。而是按柱面存放，同一柱面上的各磁道被放滿信息后，再放到下一個(gè)柱面上。所以各磁盤的編號按柱面順序，每個(gè)柱面按磁道順序，每個(gè)磁道又按扇區(qū)順序進(jìn)行排序。 磁盤是可供多個(gè)進(jìn)程共享的設(shè)備，當(dāng)有多個(gè)進(jìn)程都要求訪問磁盤是，應(yīng)采用一種最佳調(diào)度算法，以使各種進(jìn)程對磁盤的平均訪問時(shí)間最小。由于在訪問磁盤的時(shí)間中，主要是尋道時(shí)間，因此，磁盤調(diào)度的目標(biāo)，是使磁盤的平均尋道時(shí)間最少。目前常用

5、的磁盤帝調(diào)度算法有：先來先服務(wù)、最短尋道時(shí)間優(yōu)先及掃描等算法。先來先服務(wù)（FCFS）調(diào)度:按先來后到次序服務(wù)，未作優(yōu)化。 最簡單的移臂調(diào)度算法是“先來先服務(wù)”調(diào)度算法，這個(gè)算法實(shí)際上不考慮訪問者要求訪問的物理位置，而只是考慮訪問者提出訪問請求的先后次序。例如，如果現(xiàn)在讀寫磁頭正在50號柱面上執(zhí)行輸出操作，而等待訪問者依次要訪問的柱面為130、199、32、159、15、148、61、99，那么，當(dāng)50號柱面上的操作結(jié)束后，移動臂將按請求的先后次序先移到130號柱面，最后到達(dá)99號柱面。 采用先來先服務(wù)算法決定等待訪問者執(zhí)行輸入輸出操作的次序時(shí)，移動臂來回地移動。先來先服務(wù)算法花費(fèi)的尋找時(shí)間較長

6、，所以執(zhí)行輸入輸出操作的總時(shí)間也很長。最短尋找時(shí)間優(yōu)先調(diào)度算法總是從等待訪問者中挑選尋找時(shí)間最短的那個(gè)請求先執(zhí)行的，而不管訪問者到來的先后次序?，F(xiàn)在仍利用同一個(gè)例子來討論，現(xiàn)在當(dāng)50號柱面的操作結(jié)束后，應(yīng)該先處理61號柱面的請求，然后到達(dá)32號柱面執(zhí)行操作，隨后處理15號柱面請求，后繼操作的次序應(yīng)該是99、130、148、159、199。 采用最短尋找時(shí)間優(yōu)先算法決定等待訪問者執(zhí)行操作的次序時(shí)，讀寫磁頭總共移動了200多個(gè)柱面的距離，與先來先服務(wù)、算法比較，大幅度地減少了尋找時(shí)間，因而縮短了為各訪問者請求服務(wù)的平均時(shí)間，也就提高了系統(tǒng)效率。 但最短查找時(shí)間優(yōu)先（SSTF）調(diào)度，F(xiàn)CFS會引起讀

7、寫頭在盤面上的大范圍移動，SSTF查找距離磁頭最短（也就是查找時(shí)間最短）的請求作為下一次服務(wù)的對象。SSTF查找模式有高度局部化的傾向，會推遲一些請求的服務(wù)，甚至引起無限拖延（又稱饑餓）。SCAN 算法又稱電梯調(diào)度算法。SCAN算法是磁頭前進(jìn)方向上的最短查找時(shí)間優(yōu)先算法，它排除了磁頭在盤面局部位置上的往復(fù)移動，SCAN算法在很大程度上消除了SSTF算法的不公平性，但仍有利于對中間磁道的請求。 “電梯調(diào)度”算法是從移動臂當(dāng)前位置開始沿著臂的移動方向去選擇離當(dāng)前移動臂最近的那個(gè)柱訪問者，如果沿臂的移動方向無請求訪問時(shí)，就改變臂的移動方向再選擇。這好比乘電梯，如果電梯已向上運(yùn)動到4層時(shí)，依次有3位乘

8、客陳生、伍生、張生在等候乘電梯。他們的要求是：陳生在2層等待去10層；伍生在5層等待去底層；張生在8層等待15層。由于電梯目前運(yùn)動方向是向上，所以電梯的形成是先把乘客張生從8層帶到15層，然后電梯換成下行方向，把乘客伍生從5層帶到底層，電梯最后再調(diào)換方向，把乘客陳生從2層送到10層。 但是，“電梯調(diào)度”算法在實(shí)現(xiàn)時(shí)，不僅要記住讀寫磁頭的當(dāng)前位置，還必須記住移動臂的當(dāng)前前進(jìn)方向。2、概要設(shè)計(jì)2.1設(shè)計(jì)方法 通過C語言的編程，設(shè)計(jì)程序模擬先來先服務(wù)FCFS，最短尋道時(shí)間優(yōu)先SSTF，和掃描SCAN算法的工作過程。假設(shè)有n個(gè)磁道號所組成的磁道訪問序列，給定開始磁道號m和磁頭移動的方向（正向或者反向）

9、，分別利用不同的磁盤調(diào)度算法訪問磁道序列，給出磁頭每一次移動的過程，算出磁頭移動的距離，繼而計(jì)算每種算法的平均尋道長度。2.2技術(shù) C語言、操作系統(tǒng)磁盤調(diào)度算法、C+。2.3運(yùn)行環(huán)境Window10、VC+6.0。3、詳細(xì)設(shè)計(jì) 3.1流程圖先來先服務(wù)算法（FCFS）： 結(jié)束Avg=sum/(m)j<m目前的位置變?yōu)楫?dāng)前的位置j+輸出磁盤調(diào)度序列arrayj磁頭移動總距離Sum+=abs(arrayj-arrayi)磁頭移動距離Sum=abs(now-array0)輸入當(dāng)前磁道號now開始最短尋道時(shí)間優(yōu)先算法(SSTF)：開始 結(jié)束掃描SCAN算法：開始 結(jié)束3.2程序主要代碼先來先服務(wù)算

10、法（FCFS）：void FCFS(vector<int>m_vec,int position) /先來先服務(wù)算法dis = 0;average_distance = 0;for(vector<int>: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); 最短尋道時(shí)間優(yōu)

11、先算法(SSTF)： void SSTF(vector<int>m_vec,int position) /最短尋道時(shí)間算法 dis = 0; average_distance = 0; sort(m_vec.begin(),m_vec.end(); /從小到大排序 int i = 0; for(vector<int>: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(co

12、unt<m_vec.size() if(left >=0 && abs(m_vecright-position) > abs(m_vecleft-position) | right>=m_vec.size() dis += abs(m_vecleft-position); Sleep(500); cout<<"->"<<m_vecleft; position = m_vecleft; left-; else dis += abs(m_vecright-position); Sleep(500); cout

13、<<"->"<<m_vecright; position = m_vecright; right+; count+; compute_dis(m_vec,dis,average_distance);掃描SCAN算法： void SCAN(vector<int>m_vec,int position) /電梯調(diào)度算法 dis = 0; average_distance = 0; sort(m_vec.begin(),m_vec.end(); /從小到大排序 int i = 0; for(vector<int>:iterato

14、r it=m_vec.begin();it!=m_vec.end();it+) if(position >= *it) i+; /找到position所在的磁道 int left = i - 1; /先從外到內(nèi)掃描 int right = i; while(left >= 0) dis += abs(position - m_vecleft); Sleep(500); cout<<"->"<<m_vecleft; position = m_vecleft; left -; while(right < m_vec.size()

15、dis += abs(position - m_vecright); Sleep(500); cout<<"->"<<m_vecright; position = m_vecright; right +; compute_dis(m_vec,dis,average_distance);4、運(yùn)行結(jié)果及分析 4.1運(yùn)行結(jié)果先來先服務(wù)算法（FCFS）：最短尋道時(shí)間優(yōu)先算法(SSTF)： 掃描SCAN算法： 4.2結(jié)果詳細(xì)分析 FCFS ：這是一種比較簡單的磁盤調(diào)度算法。它根據(jù)進(jìn)程請求訪問磁盤的先后次序進(jìn)行調(diào)度。此算法由于未對尋道進(jìn)行優(yōu)化，在對磁盤的訪

16、問請求比較多的情況下，此算法將降低設(shè)備服務(wù)的吞吐量，致使平均尋道時(shí)間可能較長，但各進(jìn)程得到服務(wù)的響應(yīng)時(shí)間的變化幅度較小。SSTF： 該算法選擇這樣的進(jìn)程，其要求訪問的磁道與當(dāng)前磁頭所在的磁道距離最近，以使每次的尋道時(shí)間最短，該算法可以得到比較好的吞吐量，但卻不能保證平均尋道時(shí)間最短。SCAN ：掃描算法不僅考慮到欲訪問的磁道與當(dāng)前磁道的距離，更優(yōu)先考慮的是磁頭的當(dāng)前移動方向。此算法基本上克服了最短尋道時(shí)間優(yōu)先算法的服務(wù)集中于中間磁道和響應(yīng)時(shí)間變化比較大的缺點(diǎn)，而具有最短尋道時(shí)間優(yōu)先算法的優(yōu)點(diǎn)即吞吐量較大，平均響應(yīng)時(shí)間較小，但由于是擺動式的掃描方法，兩側(cè)磁道被訪問的頻率仍低于中間磁道。5、總結(jié)和

17、心得 通過這次的課程設(shè)計(jì)使我認(rèn)識到要將操作系統(tǒng)這門計(jì)算機(jī)專業(yè)的課學(xué)好不僅僅是要把書上的基本知識學(xué)好而且還要不斷進(jìn)行實(shí)踐，將所學(xué)的跟實(shí)踐操作結(jié)合起來才能更好地鞏固所學(xué)，才能提高自己實(shí)踐能力。通過這次的設(shè)計(jì)使我認(rèn)識到只停留在表面理解問題是很難使問題得到很好的解決的，實(shí)踐能力與理論知識同樣重要?？梢哉f此課程設(shè)計(jì)的理論難度并不大，各種流圖設(shè)計(jì)特別是算法過程圖的設(shè)計(jì)很容易忽略操作性細(xì)節(jié)，在實(shí)際調(diào)試中帶來很大麻煩，需要特別注意，但是若要深入發(fā)掘其中的東西，并且實(shí)際去編程實(shí)現(xiàn)，就遇到了相當(dāng)大的難度。因?yàn)榕c之涉及的很多方面并沒有學(xué)過，需要自己去自學(xué)和實(shí)踐檢驗(yàn)。通過模擬磁盤調(diào)度及進(jìn)程排隊(duì)算法來加深對操作系統(tǒng)中各

18、個(gè)磁臂調(diào)度算法概念的理解模擬磁盤調(diào)度算法，實(shí)現(xiàn)各種不同調(diào)度算法的過程，并計(jì)算各算法的平均尋道長度，以便于我們判斷各種算法的優(yōu)劣以及各種算法使用的場合。6、參考文獻(xiàn) 1. 湯子瀛，哲鳳屏，湯小丹. 計(jì)算機(jī)操作系統(tǒng).西安電子科技大學(xué)出版社, 2005; 2. 譚浩強(qiáng)編著. C語言程序設(shè)計(jì)（第3版）.清華大學(xué)出版社，2005;3. 吳乃陵，況迎輝. C+程序設(shè)計(jì)（第二版）.高等教育出版社，2005。 7、附錄：程序源代碼FCFS：#include <iostream>#include <time.h>#include <vector>#include<alg

19、orithm>#include <math.h>#include <stdlib.h>#include <cstring>#include <windows.h>#include <fstream>using namespace std;int position = 0; /當(dāng)前磁道位置int dis = 0;double average_distance = 0;void request(vector<int>&m_vec,ofstream &outfile) cout<<"隨

20、機(jī)生成磁盤序列："<<endl; int n = 0; srand(time(NULL); /添加隨機(jī)數(shù)種子 n = rand() % 20 + 1; int temp = 0; for(int i=0;i<n;i+) temp = rand() % 100; m_vec.push_back(temp); cout<<temp<<" " outfile<<temp<<endl; cout<<endl; position = rand() % 100; cout<<"

21、當(dāng)前磁道："<<position<<endl;void compute_dis(vector<int>m_vec,int &dis,double &average_distance) average_distance = (double)dis / (double)m_vec.size();void FCFS(vector<int>m_vec,int position) /先來先服務(wù)算法 dis = 0; average_distance = 0; for(vector<int>:iterator it=m_

22、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() cout<<endl<<endl; cout<<"經(jīng)計(jì)算，磁頭移動的總距離為:"<<dis<<endl; cout<<"磁頭平均移動距

23、離:"<<average_distance<<endl; cout<<endl<<endl;int main()ofstream outfile; outfile.open("data.txt"); vector<int>m_vec; request(m_vec,outfile); /請求服務(wù)序列 cout<<"磁盤請求的服務(wù)狀況："<<endl; FCFS(m_vec, position);print();outfile.close(); return 0;S

24、STF:#include <iostream>#include <time.h>#include <vector>#include <math.h>#include <stdlib.h>#include<algorithm>#include <cstring>#include <windows.h>#include <fstream>using namespace std;int position = 0; /當(dāng)前磁道位置int dis = 0;double average_distan

25、ce = 0;void request(vector<int>&m_vec,ofstream &outfile) cout<<"隨機(jī)生成磁盤序列："<<endl; int n = 0; srand(time(NULL); /添加隨機(jī)數(shù)種子 n = rand() % 20 + 1; int temp = 0; for(int i=0;i<n;i+) temp = rand() % 100; m_vec.push_back(temp); cout<<temp<<" " outf

26、ile<<temp<<endl; cout<<endl; position = rand() % 100; cout<<"當(dāng)前磁道："<<position<<endl;void compute_dis(vector<int>m_vec,int &dis,double &average_distance) average_distance = (double)dis / (double)m_vec.size();void SSTF(vector<int>m_vec,

27、int position) /最短尋道時(shí)間算法 dis = 0; average_distance = 0; sort(m_vec.begin(),m_vec.end(); /從小到大排序 int i = 0; for(vector<int>: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<m_vec.size() if(left >=0 &&

28、; abs(m_vecright-position) > abs(m_vecleft-position) | right>=m_vec.size() dis += abs(m_vecleft-position); Sleep(500); cout<<"->"<<m_vecleft; position = m_vecleft; left-; else dis += abs(m_vecright-position); Sleep(500); cout<<"->"<<m_vecright;

29、 position = m_vecright; right+; count+; compute_dis(m_vec,dis,average_distance);void print() cout<<endl<<endl; cout<<"經(jīng)計(jì)算，磁頭移動的總距離為:"<<dis<<endl; cout<<"磁頭平均移動距離:"<<average_distance<<endl; cout<<endl<<endl;int main() ofs

30、tream outfile; outfile.open("data.txt"); vector<int>m_vec; request(m_vec,outfile); /請求服務(wù)序列 cout<<"磁盤請求的服務(wù)狀況："<<endl; SSTF(m_vec, position);print();outfile.close(); return 0;SCAN:#include <iostream>#include <time.h>#include <vector>#include <

31、math.h>#include <stdlib.h>#include<algorithm>#include <cstring>#include <windows.h>#include <fstream>using namespace std;int position = 0; /當(dāng)前磁道位置int dis = 0;double average_distance = 0;void request(vector<int>&m_vec,ofstream &outfile) cout<<"

32、;隨機(jī)生成磁盤序列："<<endl; int n = 0; srand(time(NULL); /添加隨機(jī)數(shù)種子 n = rand() % 20 + 1; int temp = 0; for(int i=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;void compute_dis(vector<int>m_vec,int &dis,double &average_distance) average_distance = (double)dis / (do