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

操作系統(tǒng)課程設(shè)計(jì)任務(wù)書題 目： 磁盤調(diào)度算法 院 系： 專 業(yè)： 班 級(jí)： 姓 名： 學(xué) 號(hào)： 指導(dǎo)教師： 設(shè)計(jì)時(shí)間： 2018.1.1-2018.1.5 指導(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)先服務(wù)算法（FCFS）、最短尋道時(shí)間優(yōu)先算法(SSTF)、掃描算法（電梯調(diào)度算法）(SCAN)。1.2課題目的 通過(guò)這次實(shí)驗(yàn)，加深對(duì)磁盤調(diào)度算法的理解，進(jìn)一步掌握先來(lái)先服務(wù)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ì)磁盤的訪問(wèn)要求來(lái)自多方面，常常需要排隊(duì)。這時(shí)，對(duì)眾多的訪問(wèn)要求按一定的次序響應(yīng)，會(huì)直接影響磁盤的工作效率，進(jìn)而影響系統(tǒng)的性能。訪問(wèn)磁盤的時(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)距離之和除以總的所需訪問(wèn)的磁道數(shù)（N），即：L=（M1+M2+Mi+MN）/N 其中Mi為所需訪問(wèn)的磁道號(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)程都要求訪問(wèn)磁盤是，應(yīng)采用一種最佳調(diào)度算法，以使各種進(jìn)程對(duì)磁盤的平均訪問(wèn)時(shí)間最小。由于在訪問(wèn)磁盤的時(shí)間中，主要是尋道時(shí)間，因此，磁盤調(diào)度的目標(biāo)，是使磁盤的平均尋道時(shí)間最少。目前常用的磁盤帝調(diào)度算法有：先來(lái)先服務(wù)、最短尋道時(shí)間優(yōu)先及掃描等算法。先來(lái)先服務(wù)（FCFS）調(diào)度:按先來(lái)后到次序服務(wù)，未作優(yōu)化。 最簡(jiǎn)單的移臂調(diào)度算法是“先來(lái)先服務(wù)”調(diào)度算法，這個(gè)算法實(shí)際上不考慮訪問(wèn)者要求訪問(wèn)的物理位置，而只是考慮訪問(wèn)者提出訪問(wèn)請(qǐng)求的先后次序。例如，如果現(xiàn)在讀寫磁頭正在50號(hào)柱面上執(zhí)行輸出操作，而等待訪問(wèn)者依次要訪問(wèn)的柱面為130、199、32、159、15、148、61、99，那么，當(dāng)50號(hào)柱面上的操作結(jié)束后，移動(dòng)臂將按請(qǐng)求的先后次序先移到130號(hào)柱面，最后到達(dá)99號(hào)柱面。 采用先來(lái)先服務(wù)算法決定等待訪問(wèn)者執(zhí)行輸入輸出操作的次序時(shí)，移動(dòng)臂來(lái)回地移動(dòng)。先來(lái)先服務(wù)算法花費(fèi)的尋找時(shí)間較長(zhǎng)，所以執(zhí)行輸入輸出操作的總時(shí)間也很長(zhǎng)。最短尋找時(shí)間優(yōu)先調(diào)度算法總是從等待訪問(wèn)者中挑選尋找時(shí)間最短的那個(gè)請(qǐng)求先執(zhí)行的，而不管訪問(wèn)者到來(lái)的先后次序?，F(xiàn)在仍利用同一個(gè)例子來(lái)討論，現(xiàn)在當(dāng)50號(hào)柱面的操作結(jié)束后，應(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)先算法決定等待訪問(wèn)者執(zhí)行操作的次序時(shí)，讀寫磁頭總共移動(dòng)了200多個(gè)柱面的距離，與先來(lái)先服務(wù)、算法比較，大幅度地減少了尋找時(shí)間，因而縮短了為各訪問(wèn)者請(qǐng)求服務(wù)的平均時(shí)間，也就提高了系統(tǒng)效率。 但最短查找時(shí)間優(yōu)先（SSTF）調(diào)度，F(xiàn)CFS會(huì)引起讀寫頭在盤面上的大范圍移動(dòng)，SSTF查找距離磁頭最短（也就是查找時(shí)間最短）的請(qǐng)求作為下一次服務(wù)的對(duì)象。SSTF查找模式有高度局部化的傾向，會(huì)推遲一些請(qǐng)求的服務(wù)，甚至引起無(wú)限拖延（又稱饑餓）。SCAN 算法又稱電梯調(diào)度算法。SCAN算法是磁頭前進(jìn)方向上的最短查找時(shí)間優(yōu)先算法，它排除了磁頭在盤面局部位置上的往復(fù)移動(dòng)，SCAN算法在很大程度上消除了SSTF算法的不公平性，但仍有利于對(duì)中間磁道的請(qǐng)求。 “電梯調(diào)度”算法是從移動(dòng)臂當(dāng)前位置開始沿著臂的移動(dòng)方向去選擇離當(dāng)前移動(dòng)臂最近的那個(gè)柱訪問(wèn)者，如果沿臂的移動(dòng)方向無(wú)請(qǐng)求訪問(wèn)時(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)先服務(wù)FCFS，最短尋道時(shí)間優(yōu)先SSTF，和掃描SCAN算法的工作過(guò)程。假設(shè)有n個(gè)磁道號(hào)所組成的磁道訪問(wèn)序列，給定開始磁道號(hào)m和磁頭移動(dòng)的方向（正向或者反向），分別利用不同的磁盤調(diào)度算法訪問(wèn)磁道序列，給出磁頭每一次移動(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)先服務(wù)算法（FCFS）： 結(jié)束Avg=sum/(m)jm目前的位置變?yōu)楫?dāng)前的位置j+輸出磁盤調(diào)度序列arrayj磁頭移動(dòng)總距離Sum+=abs(arrayj-arrayi)磁頭移動(dòng)距離Sum=abs(now-array0)輸入當(dāng)前磁道號(hào)now開始最短尋道時(shí)間優(yōu)先算法(SSTF)：開始 結(jié)束掃描SCAN算法：開始 結(jié)束3.2程序主要代碼先來(lái)先服務(wù)算法（FCFS）：void FCFS(vectorm_vec,int position) /先來(lái)先服務(wù)算法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); 最短尋道時(shí)間優(yōu)先算法(SSTF)： void SSTF(vectorm_vec,int position) /最短尋道時(shí)間算法 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) /電梯調(diào)度算法 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; /先從外到內(nèi)掃描 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、運(yùn)行結(jié)果及分析 4.1運(yùn)行結(jié)果先來(lái)先服務(wù)算法（FCFS）：最短尋道時(shí)間優(yōu)先算法(SSTF)： 掃描SCAN算法： 4.2結(jié)果詳細(xì)分析 FCFS ：這是一種比較簡(jiǎn)單的磁盤調(diào)度算法。它根據(jù)進(jìn)程請(qǐng)求訪問(wèn)磁盤的先后次序進(jìn)行調(diào)度。此算法由于未對(duì)尋道進(jìn)行優(yōu)化，在對(duì)磁盤的訪問(wèn)請(qǐng)求比較多的情況下，此算法將降低設(shè)備服務(wù)的吞吐量，致使平均尋道時(shí)間可能較長(zhǎng)，但各進(jìn)程得到服務(wù)的響應(yīng)時(shí)間的變化幅度較小。SSTF： 該算法選擇這樣的進(jìn)程，其要求訪問(wèn)的磁道與當(dāng)前磁頭所在的磁道距離最近，以使每次的尋道時(shí)間最短，該算法可以得到比較好的吞吐量，但卻不能保證平均尋道時(shí)間最短。SCAN ：掃描算法不僅考慮到欲訪問(wèn)的磁道與當(dāng)前磁道的距離，更優(yōu)先考慮的是磁頭的當(dāng)前移動(dòng)方向。此算法基本上克服了最短尋道時(shí)間優(yōu)先算法的服務(wù)集中于中間磁道和響應(yīng)時(shí)間變化比較大的缺點(diǎn)，而具有最短尋道時(shí)間優(yōu)先算法的優(yōu)點(diǎn)即吞吐量較大，平均響應(yīng)時(shí)間較小，但由于是擺動(dòng)式的掃描方法，兩側(cè)磁道被訪問(wèn)的頻率仍低于中間磁道。5、總結(jié)和心得 通過(guò)這次的課程設(shè)計(jì)使我認(rèn)識(shí)到要將操作系統(tǒng)這門計(jì)算機(jī)專業(yè)的課學(xué)好不僅僅是要把書上的基本知識(shí)學(xué)好而且還要不斷進(jìn)行實(shí)踐，將所學(xué)的跟實(shí)踐操作結(jié)合起來(lái)才能更好地鞏固所學(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)很大麻煩，需要特別注意，但是若要深入發(fā)掘其中的東西，并且實(shí)際去編程實(shí)現(xiàn)，就遇到了相當(dāng)大的難度。因?yàn)榕c之涉及的很多方面并沒有學(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 #include #include #include#include #include #include #include #include using namespace std;int position = 0; /當(dāng)前磁道位置int dis = 0;double average_distance = 0;void request(vector&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;in;i+) temp = rand() % 100; m_vec.push_back(temp); couttemp ; outfiletempendl; coutendl; position = rand() % 100; cout當(dāng)前磁道：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) /先來(lái)先服務(wù)算法 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)計(jì)算，磁頭移動(dòng)的總距離為:disendl; cout磁頭平均移動(dòng)距離:average_distanceendl; coutendlendl;int main()ofstream outfile; outfile.open(data.txt); vectorm_vec; request(m_vec,outfile); /請(qǐng)求服務(wù)序列 cout磁盤請(qǐng)求的服務(wù)狀況：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; /當(dāng)前磁道位置int dis = 0;double average_distance = 0;void request(vector&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;in;i+) temp = rand() % 100; m_vec.push_back(temp); couttemp ; outfiletempendl; coutendl; position = rand() % 100; cout當(dāng)前磁道：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) /最短尋道時(shí)間算法 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)計(jì)算，磁頭移動(dòng)的總距離為:disendl; cout磁頭平均移動(dòng)距離:average_distanceendl; coutendlendl;int main() ofstream outfile; outfile.open(data.txt); vectorm_vec; request(m_vec,outfile); /請(qǐng)求服務(wù)序列 cout磁盤請(qǐng)求的服務(wù)狀況：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; /當(dāng)前磁道位置int dis = 0;double average_distance = 0;void request(vector&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;in;i+) temp = rand() % 100; m_vec.push_back(temp); couttemp ; outfiletempendl; coutendl; position = rand() % 100; cout當(dāng)前磁道：positionendl;void compute_dis(vectorm_vec,int &dis,