可視化磁盤調(diào)度算法

目錄TOC\o"1-5"\h\z第一章課程設(shè)計的目的與要求 1\o"CurrentDocument"1.1課程設(shè)計的目的 1\o"CurrentDocument"1.2課程設(shè)計的要求 1\o"CurrentDocument"第二章課程設(shè)計的任務(wù)內(nèi)容 2\o"CurrentDocument"2.1課程設(shè)計的任務(wù) 2\o"CurrentDocument"2.2課程設(shè)計的內(nèi)容 2\o"CurrentDocument"2.3課程設(shè)計的原理 2\o"CurrentDocument"第三章詳細設(shè)計說明 3\o"CurrentDocument"3.1模塊描述 3\o"CurrentDocument"3.2性能 3\o"CurrentDocument"3.3輸入項 4\o"CurrentDocument"3.4輸出項 4\o"CurrentDocument"3.5算法 5\o"CurrentDocument"3.6流程邏輯 6\o"CurrentDocument"3.7接口 9\o"CurrentDocument"3.8限制條件 9\o"CurrentDocument"第四章軟件使用說明 10\o"CurrentDocument"第五章課程設(shè)計心得與體會 13\o"CurrentDocument"附錄1：參考文獻 14\o"CurrentDocument"附錄2：程序清單 15可視化仿真磁盤調(diào)度程序第一章課程設(shè)計的目的與要求1.1課程設(shè)計的目的課程設(shè)計是課程中重要的實踐教學環(huán)節(jié)。其主要目的一方面使學生更透徹地理解操作系統(tǒng)的基本概念和原理，使之由抽象到具體；另一方面通過課程設(shè)計加強學生的實驗手段與實踐技能，培養(yǎng)學生獨立分析問題、解決問題、應(yīng)用知識的能力和創(chuàng)新精神。與實驗教學相比，課程設(shè)計獨立設(shè)課，具有更多的學時，給學生更多自行設(shè)計、自主實驗的機會，充分放于讓學生真正培養(yǎng)學生的實踐動手能力，全面提高學生的綜合素質(zhì)。1.2課程設(shè)計的要求課程設(shè)計的要求是在深入理解操作系統(tǒng)基本原理的基礎(chǔ)上，先確定設(shè)計方案，設(shè)計系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)和程序結(jié)構(gòu)，設(shè)計每個模塊的處理流程。要求設(shè)計合理，編程序?qū)崿F(xiàn)系統(tǒng)，要求實現(xiàn)可視化的運行界面，界面應(yīng)清楚地反映出系統(tǒng)的運行結(jié)果，確定測試方案，選擇測試用例，對系統(tǒng)進程測試，運行系統(tǒng)并要通過驗收，講解運行結(jié)果，說明系統(tǒng)的特色和創(chuàng)新之處，并提交課程設(shè)計報告。第二章課程設(shè)計的任務(wù)內(nèi)容2.1課程設(shè)計的任務(wù)磁盤調(diào)度課程設(shè)計的任務(wù)是理解磁盤調(diào)度相關(guān)理論和掌握多種磁盤調(diào)度算法。比如先來先服務(wù)算法、最短尋道時間優(yōu)先算法、掃描算法和循環(huán)掃描算法等算法，了解各種算法對磁盤掃描的優(yōu)化等級，并且比較各種算法的優(yōu)缺點，從而掃描不同的磁盤序列時采用相應(yīng)的算法，使得磁道掃描時間盡量最短。2.2課程設(shè)計的內(nèi)容為了完成課程設(shè)計的任務(wù)，所以在課程設(shè)計的內(nèi)容上要根據(jù)任務(wù)來設(shè)置，因此在課程設(shè)計的內(nèi)容上對于磁盤調(diào)用的相應(yīng)算法的優(yōu)劣點，可以設(shè)置幾組相同的數(shù)據(jù)對各種算法進行比較，得出各種算法的平均尋道時間，然后對數(shù)據(jù)進行比較從中得出各種算法的優(yōu)劣點。2.3課程設(shè)計的原理磁盤可供多個進程共享，當有多個進程要求訪問磁盤時，應(yīng)采用一種調(diào)度算法，以使進程對磁盤的平均訪問時間最小，由于在訪問磁盤的時間中，主要是尋道時間，因此磁盤調(diào)度的目標就是使磁盤的平均尋道時間最短。設(shè)備的動態(tài)分配算法與進程調(diào)度相似，也是基于一定的分配策略的。常用的分配策略有先請求先分配、優(yōu)先級高者先分配等策略。在多道程序系統(tǒng)中，低效率通常是由于磁盤類旋轉(zhuǎn)設(shè)備使用不當造成的。操作系統(tǒng)中，對磁盤的訪問要求來自多方面，常常需要排隊。這時，對眾多的訪問要求按一定的次序響應(yīng)，會直接影響磁盤的工作效率，進而影響系統(tǒng)的性能。訪問磁盤的時間因子由3部分構(gòu)成，它們是查找（查找磁道）時間、等待（旋轉(zhuǎn)等待扇區(qū)）時間和數(shù)據(jù)傳輸時間，其中查找時間是決定因素。因此，磁盤調(diào)度算法先考慮優(yōu)化查找策略，需要時再優(yōu)化旋轉(zhuǎn)等待策略。第三章詳細設(shè)計說明3.1模塊描述模塊描述要求給出對該模塊的簡要描述，說明該模塊應(yīng)具有的功能，并且要求說明本模塊的特點，比如模塊是否有返回值等。圖3-1所示為功能模塊圖：圖3-1功能模塊圖系統(tǒng)主要模塊分為四大模塊，分別是先來先服務(wù)算法模塊、最短尋道時間優(yōu)先算法模塊、掃描算法模塊和循環(huán)掃描算法模塊。當進入系統(tǒng)時，可以按系統(tǒng)提示輸入相關(guān)數(shù)據(jù)，然后可以停止操作直接退出或者是選擇相應(yīng)的算法進行運算，最后輸出運算結(jié)果。本組實驗是做的先來先服務(wù)算法和最短尋到時間優(yōu)先算法。3.2性能一個可靠安全的系統(tǒng)不僅要在理論上可以運行起來，同時在系統(tǒng)出錯處理、系統(tǒng)漏洞、系統(tǒng)安全、系統(tǒng)精確度、靈活度及時間特性等系能上要有一定的要求，這樣才可以保障用戶數(shù)據(jù)的可靠性和安全性等基本需求。對于磁盤調(diào)度系統(tǒng)的性能來講，系統(tǒng)的精確度為萬分之一，輸出數(shù)據(jù)精確到小數(shù)點后四位。

3.3輸入項輸入項要求是給出對每一個輸入項的特性包括名稱、標識、數(shù)據(jù)的類型格式、數(shù)據(jù)值的有效范圍、輸入的方式、數(shù)量和頻度、輸入媒體比如鍵盤或文件、輸入數(shù)據(jù)的來源和安全保密條件等。輸入項要求如表3.2所示：表3.2輸入項特征輸入項名稱輸入磁道的個數(shù)輸入項標識數(shù)字型數(shù)據(jù)類型格式數(shù)據(jù)型數(shù)據(jù)有效范圍1-1000數(shù)據(jù)輸出方式字符型輸入媒體鍵盤數(shù)據(jù)來源輸入值數(shù)據(jù)安全保密條件無3.4輸出項對于輸出項要求給出對每一個輸出項的特性、包括名稱、標識、數(shù)據(jù)的類型和格式、數(shù)據(jù)值的有效范圍、輸出的形式、數(shù)量和頻度、輸出比如顯示器或文件、對輸出圖形及符號的說明、安全保密條件等。輸入項要求如表3.3所示：表3.3輸出項特征輸出項名稱平均尋道長度輸出項標識數(shù)字型數(shù)據(jù)類型格式最多保留四位小數(shù)數(shù)據(jù)有效范圍大于1數(shù)據(jù)輸出方式字符型輸入媒體曰壬顯示器數(shù)據(jù)安全保密條件無3.5算法先來先服務(wù)（FCFS）調(diào)度:按先來后到次序服務(wù)，未作優(yōu)化。最簡單的移臂調(diào)度算法是“先來先服務(wù)”調(diào)度算法，這個算法實際上不考慮訪問者要求訪問的物理位置，而只是考慮訪問者提出訪問請求的先后次序。例如，如果現(xiàn)在讀寫磁頭正在50號柱面上執(zhí)行輸出操作，而等待訪問者依次要訪問的柱面為130、199、32、159、15、148、61、99，那么，當50號柱面上的操作結(jié)束后，移動臂將按請求的先后次序先移到130號柱面，最后到達99號柱面。采用先來先服務(wù)算法決定等待訪問者執(zhí)行輸入輸出操作的次序時，移動臂來回地移動。先來先服務(wù)算法花費的尋找時間較長，所以執(zhí)行輸入輸出操作的總時間也很長。最短尋找時間優(yōu)先調(diào)度算法總是從等待訪問者中挑選尋找時間最短的那個請求先執(zhí)行的，而不管訪問者到來的先后次序?，F(xiàn)在仍利用同一個例子來討論，現(xiàn)在當50號柱面的操作結(jié)束后，應(yīng)該先處理61號柱面的請求，然后到達32號柱面執(zhí)行操作，隨后處理15號柱面請求，后繼操作的次序應(yīng)該是99、130、148、159、199。采用最短尋找時間優(yōu)先算法決定等待訪問者執(zhí)行操作的次序時，讀寫磁頭總共移動了200多個柱面的距離，與先來先服務(wù)算法比較，大幅度地減少了尋找時間，因而縮短了為各訪問者請求服務(wù)的平均時間，也就提高了系統(tǒng)效率。但最短查找時間優(yōu)先（SSTF）調(diào)度，F(xiàn)CFS會引起讀寫頭在盤面上的大范圍移動，SSTF查找距離磁頭最短（也就是查找時間最短）的請求作為下一次服務(wù)的對象。SSTF查找模式有高度局部化的傾向，會推遲一些請求的服務(wù)，甚至引起無限拖延。SCAN算法又稱電梯調(diào)度算法°SCAN算法是磁頭前進方向上的最短查找時間優(yōu)先算法，它排除了磁頭在盤面局部位置上的往復(fù)移動，SCAN算法在很大程度上消除了SSTF算法的不公平性，但仍有利于對中間磁道的請求?！半娞菡{(diào)度”算法是從移動臂當前位置開始沿著臂的移動方向去選擇離當前移動臂最近的那個柱訪問者，如果沿臂的移動方向無請求訪問時，就改變臂的移動方向再選擇。這好比乘電梯，如果電梯已向上運動到4層時，依次有3位乘客A、B、C在等候乘電梯。他們的要求是：A在2層等待去10層；B在5層等待去底層；C在8層等待15層。由于電梯目前運動方向是向上，所以電梯的形成是先把乘客C從8層帶到15層，然后電梯換成下行方向，把乘客B從5層帶到底層，電梯最后再調(diào)換方向，把乘客A從2層送到10層。但是，“電梯調(diào)度”算法在實現(xiàn)時，不僅要記住讀寫磁頭的當前位置，還必須記住移動臂的當前前進方向。為了減少SCAN算法造成的某些進程的請求被嚴重推遲，CSCAN算法規(guī)定磁頭單向移動。例如，只自里向外移動，當磁頭移到最外的被訪問磁道時，磁頭立即返回到最里的欲訪磁道，即將最小磁道號緊接著最大磁道號構(gòu)成循環(huán)，進行掃描。算法要求是詳細說明本模塊所選用的算法，具體的計算公式和計算步驟。訪問磁盤的總時間由三部分構(gòu)成，它們是查找（查找磁道）時間、等待（旋轉(zhuǎn)等待扇區(qū)）時間和數(shù)據(jù)傳輸時間，所以總的時間為T總時間=丁查找時間+T等待時間+T數(shù)據(jù)傳輸數(shù)據(jù)。對于求平均尋道長度（L）為所有磁道所需移動距離之和除以總的所需訪問的磁道數(shù)（N）即公式為：L=（M1+M2+……+Mi+……+MN）/N其中Mi為所需訪問的磁道號所需移動的磁道數(shù)。啟動磁盤執(zhí)行輸入輸出操作時，要把移動臂移動到指定的柱面，再等待指定扇區(qū)的旋轉(zhuǎn)到磁頭位置下，然后讓指定的磁頭進行讀寫，完成信息傳送。因此，執(zhí)行一次輸入輸出所花的時間有：尋找時間——磁頭在移動臂帶動下移動到指定柱面所花的時間。延遲時間——指定扇區(qū)旋轉(zhuǎn)到磁頭下所需的時間。傳送時間——由磁頭進程讀寫完成信息傳送的時間。3.6流程邏輯要求用圖表比如流程圖并輔以必要的說明來表示本模塊的邏輯流程。如圖3-7所示為先來先服務(wù)算法流程圖：對于先來先服務(wù)算法，系統(tǒng)開始后，先進行系統(tǒng)的初始化，然后根據(jù)系統(tǒng)提示輸入需要訪問的磁盤的序列，判斷序列是否為空的話，序列空的話退出系統(tǒng)，不是的話則輸入當前磁道號，求出平均尋道時間，完成運算后，可以選擇退出系統(tǒng)或是再次進行運算。圖3-7先來先服務(wù)流程圖如圖3-8所示為最短尋道時間優(yōu)先算法流程圖:圖3-8最短尋道時間優(yōu)先算法流程圖3.7接口在系統(tǒng)的最短尋道時間優(yōu)先算法模塊中，有一個子模塊為冒泡算法模塊。其中冒泡算法模塊的參數(shù)賦值如下：模塊全局變量為：intdecide(charstr[])//判斷輸入數(shù)據(jù)是否有效{inti=0;while(str[i]!='\0')其中初始值為i=03.8限制條件說明本程序運行中所受到的限制條件。由于計算機是有限精度有限容量的，所以對于磁道數(shù)的最大值，系統(tǒng)設(shè)置為1000。對于輸出的數(shù)據(jù)精確度，系統(tǒng)精確到小數(shù)點后四位。第四章軟件使用說明打開軟件，如圖4-1所示為系統(tǒng)界面圖。請輸.A,i必亙序列［&結(jié)束）1圖4-1系統(tǒng)界面圖根據(jù)提示輸入磁道序列10、22、20、2、40、6、38。系統(tǒng)顯示界面如圖4-2所示:你輸入的磁道序列為：值2220240638>000<>0000<>0000<>00<>0000<>0000<>0000<>00<>0000<>0000<於XXXNNX系亳充 NJOOCXNMMMMMM先來先服務(wù)**最短尋道時間優(yōu)先?*3.退出HMMMMMJOCJOCJCJOCJOCJCJOCNNJOCKNJOCJOCNJOCJOCJCJOCNNJOCKNJOCNKNJOCJOCM：請詵禪翕夫: 圖4-2輸入磁道數(shù)后系統(tǒng)界面根據(jù)選項可以選擇先來先服務(wù)算法或者是最短尋道時間優(yōu)先算法，輸入“1”選擇的是先來先服務(wù)算法，選擇“2”選擇的是最短尋道時間優(yōu)先算法。如圖4-3所示的為選擇先來先服務(wù)算法，輸入當前磁道數(shù)為“20”。系統(tǒng)顯示結(jié)果如下：讀選建鬢法f磁盤請求序列為：102220240638讀碗:、當煎的覦苴號/2臨磁盤掃描序列為:F2220240638平均尋道畏度『20.8571KXIOOCJC系 MMMMMMuuuuu*u**1-先來先服務(wù)**二r最短尋道時間優(yōu)先“**3.退出**R-TR-T R-TR-TR-TXNXXNXXXXXXNXXNJCXNXXXXXXNXXNJCXNXXXXXXNXXNJCXXXXXNXXNXXXXXXNXXNJCXNXXXXXXNXXNJCXNXXXXXXNXXNJCXXXX請選擇算法: 圖4-3先來先服務(wù)界面根據(jù)結(jié)果可以知道磁盤掃描的順序為10、22、20、2、40、6、38。平均尋道時間為20.8571。當選擇最短尋道時間有限算法，并且輸入當前磁道數(shù)為20時，結(jié)果顯示如圖4-4所示：岸膏冒宙凝序列為：261928223840喻入當前的感道號：20盤掃描序列為：20221B62384日怦均尋道親度：S.57143:MJCNX知JC親亳無MMMMMMKMMMMMMKMMMMMMKMMKMMMMMMKMMMMMMKMMMMMMKMHMMMMK**1.先來先服務(wù)****2-最短尋■道時間優(yōu)先****3-退出**MMMMMM請選擇算法：圖4-4最短尋道時間優(yōu)先算法界面

從結(jié)果我們可以知道磁盤掃描的順序為20、22、10、6、2、38、40。平均尋道時間為8.57143。和算法1相比較，算法2所用的時間要少。若是選擇“3”，則是退出系統(tǒng)。圖4-5退出算法界面第五章課程設(shè)計心得與體會首先課程設(shè)計是培養(yǎng)我們學生綜合運用所學知識，發(fā)現(xiàn)，提出，分析和解決實際問題，鍛煉實踐能力的重要環(huán)節(jié)，是對實際工作能力的具體訓練和考察過程.隨著科學技術(shù)發(fā)展的日新日異，計算機已經(jīng)成為當今生活必不可少的事務(wù)，在生活中可以說得是無處不在。計算機的編程語言雖然很多，然而自己掌握一種編程語言不僅對于以后的工作有了幫助而且讓我們學會了許多新的東西，因此對于二十一世紀的大學生來說掌握計算機編程技術(shù)是十分重要的?；仡櫰鸫舜未疟P調(diào)度的課程設(shè)計，我感慨頗多，從選擇題目到查找資料，使我進一步了解磁盤的各種算法，雖然做的時間不是很長，但是可以學到許多東西，不僅可以鞏固了以前所學過的知識，也知道曾經(jīng)學習的不足，并加以改正。而且我也學到了很多在書本上所沒有學到過的知識。通過這次課程設(shè)計我懂得了理論與實際相結(jié)合的重要性.在學習理論中，自己并沒有學好書本上的知識，而平時也不注意，但當在實驗中要用到時就感覺學的很少或者是不精通，不知道學了后又什么用，一些操作往往只知道大概而不懂得具體怎么做。通過完成實驗讓自己可以把以前的漏洞加以學習，對于學過的東西加以靈活運用。只有理論中得出結(jié)論，才能真正為社會服務(wù)，從而提高自己的實際動手能力和獨立思考的能力。在設(shè)計的過程中遇到各種各樣的問題，不僅是磁盤算法的問題，也有在編程中出現(xiàn)的故障，經(jīng)過不斷的修改讓自己掌握了許多東西。通過這次課程設(shè)計，把以前所學過的知識重新溫故。附錄1:參考文獻[1].[美]AndrewS.TanenbaumAlbertS.Woodhull著.陳渝，諶衛(wèi)軍譯，向勇審校.操作系統(tǒng)設(shè)計與實現(xiàn).電子工業(yè)出版社.2006.⑵.張紅光，李福才著.操作系統(tǒng)教程.高等教育出版社.2010.[3]陳龍等著.21天學通C++.人民郵電出版社.2009.附錄2：程序清單#include<stdio.h>#include<stdlib.h>#include<iostream.h>#include<math.h>#definemaxsize1000/*********************判斷輸入數(shù)據(jù)是否有效**************************/intdecide(charstr[])//判斷輸入數(shù)據(jù)是否有效inti=0;while(str[i]!='\0')if(str[i]<'0'||str[i]>'9')return0;break;i++;returni;/******************將字符串轉(zhuǎn)換成數(shù)字***********************/inttrans(charstr[],inta)//將字符串轉(zhuǎn)換成數(shù)字inti;intsum=0;for(i=0;i<a;i++)sum=sum+(int)((str[i]-'0')*pow(10,a-i-1));}returnsum;/*********************冒泡排序算法**************************/int*bubble(intcidao[],intm){inti,j;inttemp;for(i=0;i<m;i++)//使用冒泡法按從小到大順序排列for(j=i+1;j<m;j++){if(cidao[i]>cidao[j]){temp=cidao[i];cidao[i]=cidao[j];cidao[j]=temp;}}cout<<"排序后的磁盤序列為："；for(i=0;i<m;i++)//輸出排序結(jié)果{cout<<cidao[i]<<"";cout<<endl;returncidao;/*********************先來先服務(wù)調(diào)度算法**************************/voidFCFS(intcidao[],intm)//磁道號數(shù)組，個數(shù)為mintnow;//當前磁道號intsum=0;//總尋道長度intj,i;inta;charstr[100];floatave;//平均尋道長度cout<<"磁盤請求序列為："；for(i=0;i<m;i++)//按先來先服務(wù)的策略輸出磁盤請求序列{cout<<cidao[i]<<"";}cout<<endl;cout<<"請輸入當前的磁道號："；B:cin>>str;//對輸入數(shù)據(jù)進行有效性判斷a=decide(str);if(a==0){cout<<"輸入數(shù)據(jù)的類型錯誤，請重新輸入！"<<endl;gotoB;}elsenow=trans(str,a);//輸入當前磁道號sum+=abs(cidao[0]-now);coutvv"磁盤掃描序列為："；for(i=0;i<m;i++)〃輸出磁盤掃描序列{coutvvcidao[i]vv"";}for(i=0,j=1;jvm;i++,j++)//求平均尋道長度{sum+=abs(cidao[j]-cidao[i]);ave=(float)(sum)/(float)(m);}cout<<endl;cout<<”平均尋道長度："<<ave<<endl;/**********************最短尋道時間優(yōu)先調(diào)度算法********************/voidSSTF(intcidao[],intm){intk=1;intnow,l,r;inti,j,sum=0;inta;charstr[100];floatave;cidao=bubble(cidao,m);〃調(diào)用冒泡排序算法排序cout<<"請輸入當前的磁道號："；C:cin>>str;//對輸入數(shù)據(jù)進行有效性判斷a=decide(str);if(a==0){cout<<"輸入數(shù)據(jù)的類型錯誤，請重新輸入！"<<endl;gotoC;}elsenow=trans(str,a);//輸入當前磁道號if(cidao[m-1]<=now)//若當前磁道號大于請求序列中最大者，則直接由外向內(nèi)依次給予各請求服務(wù)cout<<"磁盤掃描序列為：”；for(i=m-1;i>=0;i--)cout<<cidao[i]<<”";sum=now-cidao[0];}if(cidao[0]>=now)//若當前磁道號小于請求序列中最小者，則直接由內(nèi)向外依次給予各請求服務(wù){(diào)cout<<"磁盤掃描序列為：”；for(i=0;i<m;i++)cout<<cidao[i]<<"";sum=cidao[m-1]-now;}if(now>cidao[0]&&now<cidao[m-1])//若當前磁道號大于請求序列中最小者且小于最大者{cout<<"磁盤掃描序列為：”；while(cidao[k]<now)〃確定當前磁道在已排的序列中的位置，后面的算法都用到了，可以直接復(fù)制后少量修改，節(jié)省時間。{k++;}l=k-1;r=k;while((l>=0)&&(r<m))//當前磁道在請求序列范圍內(nèi){if((now-cidao[l])<=(cidao[r]-now))〃選擇與當前磁道最近的請求給予服務(wù){(diào)cout<<cidao[l]<<"";sum+=now-cidao[l];now=cidao[l];l=l-1；}else{cout<<cidao[r]<<"";sum+=cidao[r]-now;now=cidao[r];r=r+1;}}if(l==-1)//磁頭移動到序列的最小號，返回外側(cè)掃描仍未掃描的磁道{for(j=r;j<m;j++){cout<<cidao[j]<<"";}sum+=cidao[m-1]-cidao[0];}else//磁頭移動到序列的最大號，返回內(nèi)側(cè)掃描仍未掃描的磁道{for(j=l;j>=0;j--){cout<<cidao[j]<<"";}sum+=cidao[m-1]-cidao[0];}}ave=(float)(sum)/(float)(m);cout<<endl;cout<<"平均尋道長度："<<ave<<endl;}voidmain(){inta;intc;//菜單項intcidao[maxsize];inti=0,count;charstr[100];cout<<"請輸入磁道序列(0結(jié)束)："<<endl;A:cin>>str;〃對輸入數(shù)據(jù)進行有效性判斷a=decide(str);if(a==0)