模擬磁盤調(diào)度算法操作系統(tǒng)課程設(shè)計(jì)

1、某某大學(xué)課程設(shè)計(jì)報(bào)告課程名稱： 操作系統(tǒng) 設(shè)計(jì)題目： 模擬磁盤調(diào)度算法 系 別： 計(jì)算機(jī)系 專 業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù) 組 別： 學(xué)生姓名: 學(xué) 號(hào): 起止日期: 指導(dǎo)教師: 目錄第一章 需求分析11.1課程設(shè)計(jì)的簡介11.2課程設(shè)計(jì)的目的11.3磁盤調(diào)度主要思想 11.4課程設(shè)計(jì)內(nèi)容2 第二章 概要設(shè)計(jì)32.1設(shè)計(jì)思想32.2 數(shù)據(jù)結(jié)構(gòu)32.3模塊調(diào)用關(guān)系圖32.4子模塊程序流程圖5第三章 詳細(xì)設(shè)計(jì)63.1模塊劃分6第四章 代碼測試94.1先來先服務(wù)94.1最短尋道時(shí)間優(yōu)先114.1掃描算法12第五章 心得體會(huì)13第六章 致謝13參考文獻(xiàn)1附源代碼2第一章 需求分析1.1課程設(shè)計(jì)的簡介這是一

2、個(gè)用VC+6.0為工具、C+為編程語言而實(shí)現(xiàn)模擬先來先服務(wù)算法（FCFS）、最短尋道時(shí)間優(yōu)先算法（SSTF）、掃描算法（SCAN）的一個(gè)磁盤調(diào)度程序。該程序設(shè)計(jì)系統(tǒng)主界面可以靈活選擇某種算法并算出磁頭移動(dòng)的總磁道數(shù)以及平均磁道數(shù)。1.2課程設(shè)計(jì)的目的本課程設(shè)計(jì)的目的是通過設(shè)計(jì)一個(gè)磁盤調(diào)度模擬系統(tǒng)，從而使磁盤調(diào)度算法更加形象化，容易使人理解，使磁盤調(diào)度的特點(diǎn)更簡單明了，能使使用者加深對(duì)先來先服務(wù)算法（FCFS）、最短尋道時(shí)間優(yōu)先算法（SSTF）、掃描算法（SCAN）等磁盤調(diào)度算法的理解。1.3磁盤調(diào)度主要思想設(shè)備的動(dòng)態(tài)分配算法與進(jìn)程調(diào)度相似，也是基于一定的分配策略的。常用的分配策略有先請(qǐng)求先分配

3、、優(yōu)先級(jí)高者先分配等策略。在多道程序系統(tǒng)中，低效率通常是由于磁盤類旋轉(zhuǎn)設(shè)備使用不當(dāng)造成的。操作系統(tǒng)中，對(duì)磁盤的訪問要求來自多方面，常常需要排隊(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)等待策略。 平均尋道長度（L）為所有磁道所需移動(dòng)距離之和除以總的所需訪問的磁道數(shù)（N），即： L=（M1+M2+Mi+MN）/N。其中Mi為所需訪問的磁道號(hào)所需移動(dòng)的磁道數(shù)。 啟動(dòng)磁盤執(zhí)行輸入

4、輸出操作時(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)按柱面順序（從0號(hào)柱

5、面開始），每個(gè)柱面按磁道順序，每個(gè)磁道又按扇區(qū)順序進(jìn)行排序。1.4課程設(shè)計(jì)內(nèi)容系統(tǒng)主界面可以靈活選擇某種算法，算法包括：先來先服務(wù)算法（FCFS）、最短尋道時(shí)間優(yōu)先算法（SSTF）、掃描算法（SCAN）。并計(jì)算及比較磁頭移動(dòng)總磁道數(shù)和平均磁道數(shù)。1.4.1、先來先服務(wù)算法（FCFS）這是一種比較簡單的磁盤調(diào)度算法。它根據(jù)進(jìn)程請(qǐng)求訪問磁盤的先后次序進(jìn)行調(diào)度。此算法的優(yōu)點(diǎn)是公平、簡單，且每個(gè)進(jìn)程的請(qǐng)求都能依次得到處理，不會(huì)出現(xiàn)某一進(jìn)程的請(qǐng)求長期得不到滿足的情況。此算法由于未對(duì)尋道進(jìn)行優(yōu)化，在對(duì)磁盤的訪問請(qǐng)求比較多的情況下，此算法將降低設(shè)備服務(wù)的吞吐量，致使平均尋道時(shí)間可能較長，但各進(jìn)程得到服務(wù)的響

6、應(yīng)時(shí)間的變化幅度較小。1.4.2、最短尋道時(shí)間優(yōu)先算法（SSTF）該算法選擇這樣的進(jìn)程，其要求訪問的磁道與當(dāng)前磁頭所在的磁道距離最近，以使每次的尋道時(shí)間最短，該算法可以得到比較好的吞吐量，但卻不能保證平均尋道時(shí)間最短。其缺點(diǎn)是對(duì)用戶的服務(wù)請(qǐng)求的響應(yīng)機(jī)會(huì)不是均等的，因而導(dǎo)致響應(yīng)時(shí)間的變化幅度很大。在服務(wù)請(qǐng)求很多的情況下，對(duì)內(nèi)外邊緣磁道的請(qǐng)求將會(huì)無限期的被延遲，有些請(qǐng)求的響應(yīng)時(shí)間將不可預(yù)期。1.4.3、掃描算法（SCAN）掃描算法不僅考慮到欲訪問的磁道與當(dāng)前磁道的距離，更優(yōu)先考慮的是磁頭的當(dāng)前移動(dòng)方向。例如，當(dāng)磁頭正在自里向外移動(dòng)時(shí)，掃描算法所選擇的下一個(gè)訪問對(duì)象應(yīng)是其欲訪問的磁道既在當(dāng)前磁道之外

7、，又是距離最近的。這樣自里向外地訪問，直到再無更外的磁道需要訪問才將磁臂換向，自外向里移動(dòng)。這時(shí)，同樣也是每次選擇這樣的進(jìn)程來調(diào)度，即其要訪問的磁道，在當(dāng)前磁道之內(nèi)，從而避免了饑餓現(xiàn)象的出現(xiàn)。由于這種算法中磁頭移動(dòng)的規(guī)律頗似電梯的運(yùn)行，故又稱為電梯調(diào)度算法。此算法基本上克服了最短尋道時(shí)間優(yōu)先算法的服務(wù)集中于中間磁道和響應(yīng)時(shí)間變化比較大的缺點(diǎn)，而具有最短尋道時(shí)間優(yōu)先算法的優(yōu)點(diǎn)即吞吐量較大，平均響應(yīng)時(shí)間較小，但由于是擺動(dòng)式的掃描方法，兩側(cè)磁道被訪問的頻率仍低于中間磁道。第二章 概要設(shè)計(jì)2.1設(shè)計(jì)思想本次課程設(shè)計(jì)我們是以面向?qū)ο蟮乃枷霝橹?，利用Visual C為工具實(shí)現(xiàn)模擬磁盤調(diào)度。程序主要是利用冒

8、泡排序函數(shù)、FCFS函數(shù)、SSTF函數(shù)、SCAN函數(shù)、CSCAN函數(shù)實(shí)現(xiàn)函數(shù)的功能。利用菜單式的選擇界面，方便的用戶操作。最終對(duì)每一種模擬磁盤調(diào)度輸出磁頭平均移動(dòng)的磁道數(shù)以及總磁道數(shù)。2.2 數(shù)據(jù)結(jié)構(gòu)該程序主要是利用7個(gè)函數(shù)。Panduan（）函數(shù)：對(duì)輸入的字符進(jìn)行判斷是否合法，zhuanhua（）函數(shù)：對(duì)輸入合法的字符進(jìn)行轉(zhuǎn)化，bubble（）函數(shù)：對(duì)輸入的磁道進(jìn)行冒泡排序，F(xiàn)CFS（）函數(shù)，即先來先服務(wù)函數(shù)，SSTF（）函數(shù)：最短最短尋道時(shí)間函數(shù)，SCAN（）函數(shù)：掃描函數(shù)，CSCAN（）函數(shù)：循環(huán)掃描函數(shù)。各函數(shù)之間有點(diǎn)可以相互調(diào)用，共同實(shí)現(xiàn)要求。本程序主要用到的數(shù)據(jù)結(jié)構(gòu)為數(shù)組、字符串，

9、包括對(duì)字符串的合法性判斷，利用數(shù)組算磁頭移動(dòng)的總磁道數(shù)，平均移動(dòng)磁道數(shù)。2.3模塊調(diào)用關(guān)系圖磁盤調(diào)度模擬系統(tǒng)先來先服務(wù)最短尋道時(shí)間優(yōu)先掃描算法退出 圖2-1 磁盤調(diào)度模擬系統(tǒng)2.4子模塊程序流程圖先來先服務(wù)算法（FCFS）流程圖：2.4.2最短尋道時(shí)間優(yōu)先算法（SSTF）流程圖掃描算法（SCAN）流程圖第三章 詳細(xì)設(shè)計(jì)3.1模塊劃分本系統(tǒng)劃分為四個(gè)模塊：先來先服務(wù)算法模塊int FCFS(int array,int m)、最短尋道時(shí)間優(yōu)先算法模塊int SSTF(int array,int m)、掃描算法模塊int SCAN(int array,int m) 先來先服務(wù)算法模塊：int FCF

10、S(int array,int m)輸入磁道號(hào)，按先來先服務(wù)的策略輸出磁盤請(qǐng)求序列，求平均尋道長度，輸出移動(dòng)平均磁道數(shù)。主要代碼：for(i=0,j=1;jm;i+,j+) sum+=abs(arrayj-arrayi); ave=(float)(sum)/(float)(m); 最短尋道時(shí)間優(yōu)先算法模塊：int SSTF(int array,int m)將磁道號(hào)用冒泡法從小到大排序，輸出排好序的磁道序列，輸入當(dāng)前磁道號(hào)，根據(jù)前磁道在已排的序列中的位置，選擇掃描的順序，求出平均尋道長度，輸出移動(dòng)的平均磁道數(shù)。主要代碼：for(i=0;im;i+) /*使用冒泡法按從小到大順序排列*/for(j

11、=i+1;jarrayj) temp=arrayi; arrayi=arrayj; arrayj=temp; if(arraym-1=0;i-) coutarrayi=now) /*若當(dāng)前磁道號(hào)小于請(qǐng)求序列中最小者，則直接由內(nèi)向外依次給予各請(qǐng)求服務(wù)*/ while(l=0)&(rm) /*當(dāng)前磁道在請(qǐng)求序列范圍內(nèi)*/ if(now-arrayl)=(arrayr-now) /*選擇與當(dāng)前磁道最近的請(qǐng)求給予服務(wù)*/ coutarrayl=0;j-) coutarrayj ; /*輸出向內(nèi)掃描的序列*/ for(j=r;jm;j+) /*磁頭移動(dòng)到最小號(hào)，則改變方向向外掃描未掃描的磁道*/ cou

12、tarrayj ; /*輸出向外掃描的序列*/ sum=now-2*array0+arraym-1; else /*選擇移動(dòng)臂方向向外，則先向外掃描*/ for(j=r;jm;j+) coutarrayj=0;j-) /*磁頭移動(dòng)到最大號(hào)，則改變方向向內(nèi)掃描未掃描的磁道*/ coutarrayj ; sum=-now-array0+2*arraym-1; ave=(float)(sum)/(float)(m);第四章 測試4.1 先來先服務(wù)算法輸入磁道序列：65 78 34 23 87 100 18 26當(dāng)前磁道號(hào)：80磁盤掃描序列為：65 78 34 23 87 100 18 26平均尋到長

13、度：31.25磁頭移動(dòng)總磁道數(shù)：2504.2 最短尋道時(shí)間優(yōu)先算法（1）當(dāng)前磁道號(hào)大于磁道序列中的最大的磁道號(hào)時(shí) 輸入磁道序列：65 78 34 23 87 100 18 26 排序后的磁道序列為：18 23 26 34 65 78 87 100當(dāng)前磁道號(hào)：200磁盤掃描序列為100 87 78 65 34 26 23 18平均尋到長度：22.75磁頭移動(dòng)總磁道數(shù)：182（2）當(dāng)前磁道號(hào)小于磁道序列中的最小的磁道號(hào)時(shí)輸入磁道序列：65 78 34 23 87 100 18 26排序后的磁道序列為：18 23 26 34 65 78 87 100當(dāng)前磁道號(hào)：10磁盤掃描序列為：18 23 26

14、34 65 78 87 100平均掃描長度：11.25磁道移動(dòng)總磁道數(shù)：90（3）當(dāng)前磁道號(hào)大于磁道序列中的最小的磁道號(hào)且小于最大磁道號(hào)時(shí)輸入磁道序列：65 78 34 23 87 100 18 26排序后的磁道序列為：18 23 26 34 65 78 87 100當(dāng)前磁道號(hào)：80磁盤掃描序列為：78 87 100 65 34 26 23 18平均掃描長度：13.25磁道移動(dòng)總磁道數(shù)：1064.3 掃描算法（1）當(dāng)前磁道號(hào)大于磁道序列中的最大的磁道號(hào)時(shí)輸入磁道序列：65 78 34 23 87 100 18 26 排序后的磁道序列為：18 23 26 34 65 78 87 100當(dāng)前磁道號(hào)

15、：200磁盤掃描序列為100 87 78 65 34 26 23 18平均尋到長度：22.75磁頭移動(dòng)總磁道數(shù)：182（2）當(dāng)前磁道號(hào)小于磁道序列中的最小的磁道號(hào)時(shí)輸入磁道序列：65 78 34 23 87 100 18 26排序后的磁道序列為：18 23 26 34 65 78 87 100當(dāng)前磁道號(hào)：10磁盤掃描序列為：18 23 26 34 65 78 87 100平均掃描長度：11.25磁道移動(dòng)總磁道數(shù)：90（3）當(dāng)前磁道號(hào)大于磁道序列中的最小的磁道號(hào)且小于最大磁道號(hào)（磁頭向外）時(shí)輸入磁道序列：65 78 34 23 87 100 18 26排序后的磁道序列為：18 23 26 34

16、65 78 87 100當(dāng)前磁道號(hào)：80請(qǐng)輸入當(dāng)前移動(dòng)臂的移動(dòng)的方向（1表示向外，0表示向內(nèi)）：1磁盤掃描序列為：87 100 78 65 34 26 23 18平均尋到長度：12.75磁道移動(dòng)總磁道數(shù)：102第五章 心的體會(huì)通過這次的課程設(shè)計(jì)使我認(rèn)識(shí)到要將操作系統(tǒng)這門計(jì)算機(jī)專業(yè)的課學(xué)好不僅僅是要把書上的基本知識(shí)學(xué)好而且還要不斷進(jìn)行實(shí)踐，將所學(xué)的跟實(shí)踐操作結(jié)合起來才能更好地鞏固所學(xué)，才能提高自己實(shí)踐能力.通過這次的設(shè)計(jì)使我認(rèn)識(shí)到只停留在表面理解問題是很難使問題得到很好的解決的，實(shí)踐能力與理論知識(shí)同樣重要。可以說此課程設(shè)計(jì)的理論難度并不大，但是若要深入發(fā)掘其中的東西，并且實(shí)際去編程實(shí)現(xiàn)，就遇到了

17、相當(dāng)大的難度。因?yàn)榕c之涉及的很多方面并沒有學(xué)過，需要自己去自學(xué)和實(shí)踐檢驗(yàn)。通過本次課程設(shè)計(jì)，通過模擬磁盤調(diào)度及進(jìn)程排隊(duì)算法來加深對(duì)操作系統(tǒng)中各個(gè)磁臂調(diào)度算法概念的理解。模擬磁盤調(diào)度算法(FCFS,SSTF,SCAN,CSCAN)，實(shí)現(xiàn)各種不同調(diào)度算法的過程，并計(jì)算各算法的平均尋道長度，以便于我們判斷各種算法的優(yōu)劣以及各種算法使用的場合。對(duì)VC+6.0的應(yīng)用也更加得心應(yīng)手。第六章 致謝感謝陜粉麗老師和本組成員在這次系統(tǒng)開發(fā)過程中對(duì)我的幫助參考文獻(xiàn)1 計(jì)算機(jī)操作系統(tǒng) 高等教育出版社，作者：孫鐘秀，費(fèi)翔林，駱斌等編著2VC+深入詳解 電子工業(yè)出版社作者：孫鑫，余指導(dǎo)教師評(píng)語： 指導(dǎo)教師簽名： 年 月

18、 日成績?cè)u(píng)定項(xiàng) 目權(quán)重成績1、設(shè)計(jì)過程中出勤、學(xué)習(xí)態(tài)度等方面0.12、設(shè)計(jì)技術(shù)水平0.43、安全程度及可操作程度0.24、設(shè)計(jì)報(bào)告書寫及圖紙規(guī)范程度0.3總 成 績 教研室審核意見：教研室主任簽字： 年 月 日教學(xué)院（系）審核意見： 主任簽字： 年 月 日附源代碼#include#include#include#includeconst int maxsize=1000;int panduan(char str); int zhuanhua(char str,int a); int *bubble(int cidao,int m); int FCFS(int cidao,int m); voi

19、d SSTF(int cidao,int m);void SCAN(int cidao,int m); int main() int a; int c; int cidaomaxsize; int i=0,count; char str100; cout請(qǐng)輸入磁道序列（0結(jié)束）：str; a=panduan(str); if(a=0) cout輸入數(shù)據(jù)的類型錯(cuò)誤,請(qǐng)重新輸入！str; a=panduan(str); if(a=0) cout輸入數(shù)據(jù)的類型錯(cuò)誤,請(qǐng)重新輸入！endl; else cidaoi=zhuanhua(str,a); i+; count=i-1; cout你輸入的磁道序列

20、為：; for(i=0;icount;i+) coutcidaoi ; coutendl; while(1) coutendl; cout|_|endl; cout| (*_*) 系統(tǒng)菜單 (*_*) |endl; cout|_|endl; cout| |endl; cout| 1. 先來先服務(wù) |endl; cout| |endl; cout| 2. 最短尋道時(shí)間優(yōu)先 |endl; cout| |endl; cout| 3. 掃描調(diào)度 |endl; cout| |endl; cout| 4. 退出 |endl; cout| |endl; cout|_|endl; cout|_|endl; b

21、ei7:coutstr; a=panduan(str); if(a=0) cout輸入數(shù)據(jù)的類型錯(cuò)誤,請(qǐng)重新輸入！5) cout數(shù)據(jù)輸入錯(cuò)誤！請(qǐng)重新輸入endl; goto bei7; switch(c) case 1: FCFS(cidao,count); break; case 2: SSTF(cidao,count); break; case 3: SCAN(cidao,count); break; return 0;/*判斷輸入數(shù)據(jù)是否有效*/int panduan(char str) int i=0;while(stri!=0) if(stri9)return 0;break;i+;

22、return i;/*將字符串轉(zhuǎn)換成數(shù)字*/int zhuanhua(char str,int a) int i;int sum=0;for(i=0;ia;i+)sum=sum+(int)(stri-0)*pow(10,a-i-1);return sum;/*冒泡排序算法*/int *bubble(int cidao,int m) int i,j;int temp; for(i=0;im;i+) for(j=i+1;jcidaoj) temp=cidaoi; cidaoi=cidaoj; cidaoj=temp; cout排序后的磁盤序列為：; for( i=0;im;i+) coutcida

23、oi ; coutendl; return cidao; /*先來先服務(wù)調(diào)度算法*/int FCFS(int cidao,int m) int now; int sum=0; int j,i;int a;char str100; float ave; cout磁盤請(qǐng)求序列為：; for( i=0;im;i+) coutcidaoi ; coutendl; coutstr; a=panduan(str); if(a=0) cout輸入數(shù)據(jù)的類型錯(cuò)誤,請(qǐng)重新輸入！endl; goto bei2; else now=zhuanhua(str,a); sum+=abs(cidao0-now);cout

24、磁盤掃描序列為：; for( i=0;im;i+) coutcidaoi ; for(i=0,j=1;jm;i+,j+) sum+=abs(cidaoj-cidaoi); ave=(float)(sum)/(float)(m); coutendl; cout平均尋道長度：aveendl;cout磁頭移動(dòng)總磁道數(shù)：sumendl;return 0;/*最短尋道時(shí)間優(yōu)先調(diào)度算法*/void SSTF(int cidao,int m) int k=1; int now,l,r; int i,j,sum=0; int a; char str100; float ave; cidao=bubble(ci

25、dao,m); coutstr; a=panduan(str); if(a=0) cout輸入數(shù)據(jù)的類型錯(cuò)誤,請(qǐng)重新輸入！endl; goto bei3; else now=zhuanhua(str,a); if(cidaom-1=now) cout=0;i-) coutcidaoi=now) cout磁盤掃描序列為：; for(i=0;im;i+) coutcidaoicidao0&nowcidaom-1) cout磁盤掃描序列為：; while(cidaok=0)&(rm) if(now-cidaol)=(cidaor-now) coutcidaol ; sum+=now-cidaol; now=cidaol; l=l-1; else c