模擬磁盤調度算法操作系統(tǒng)課程設計

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

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

3、一定的分配策略的。常用的分配策略有先請求先分配、 優(yōu)先級高者先分配等策略。 在多道程序系統(tǒng)中， 低效 率通常是由于磁盤類旋轉設備使用不當造成的。 操作系統(tǒng)中，對磁盤的訪問要求 來自多方面，常常需要排隊。這時，對眾多的訪問要求按一定的次序響應，會直 接影響磁盤的工作效率， 進而影響系統(tǒng)的性能。 訪問磁盤的時間因子由 3 部分構 成，它們是查找（查找磁道） 時間、等待（旋轉等待扇區(qū)） 時間和數(shù)據傳輸時間， 其中查找時間是決定因素。 因此，磁盤調度算法先考慮優(yōu)化查找策略， 需要時再 優(yōu)化旋轉等待策略。平均尋道長度（L）為所有磁道所需移動距離之和除以總的所需訪問的磁道 數(shù)（N）,即： L=（M1+M2

4、十+Mi+MN /N。其中Mi為所需訪問的磁道號所需移動的磁道數(shù)。啟動磁盤執(zhí)行輸入輸出操作時, 要把移動臂移動到指定的柱面, 再等待指定 扇區(qū)的旋轉到磁頭位置下,然后讓指定的磁頭進行讀寫,完成信息傳送。因此, 執(zhí)行一次輸入輸出所花的時間有：尋找時間磁頭在移動臂帶動下移動到指定柱面所花的時間延遲時間指定扇區(qū)旋轉到磁頭下所需的時間。 傳送時間由磁頭進程讀寫完成信息傳送的時間。 其中傳送信息所花的時間， 是在硬件設計就固定的。 而尋找時間和延遲時間 是與信息在磁盤上的位置有關。為了減少移動臂進行移動花費的時間， 每個文件的信息不是按盤面上的磁道 順序存放滿一個盤面后， 再放到下一個盤面上。 而是按柱

5、面存放， 同一柱面上的 各磁道被放滿信息后， 再放到下一個柱面上。 所以各磁盤的編號按柱面順序 （從 0 號柱面開始），每個柱面按磁道順序，每個磁道又按扇區(qū)順序進行排序。1.4 課程設計內容 系統(tǒng)主界面可以靈活選擇某種算法，算法包括：先來先服務算法（FCFS）、最短尋道時間優(yōu)先算法（SSTF、掃描算法（SCA）并計算及比較磁頭移動總磁 道數(shù)和平均磁道數(shù)。1.4.1 、先來先服務算法（ FCFS、 這是一種比較簡單的磁盤調度算法。 它根據進程請求訪問磁盤的先后次序進行調度。此算法的優(yōu)點是公平、簡單，且每個進程的請求都能依次得到處理，不 會出現(xiàn)某一進程的請求長期得不到滿足的情況。此算法由于未對尋道

6、進行優(yōu)化， 在對磁盤的訪問請求比較多的情況下， 此算法將降低設備服務的吞吐量， 致使平 均尋道時間可能較長，但各進程得到服務的響應時間的變化幅度較小。1.4.2 、最短尋道時間優(yōu)先算法（ SSTF、 該算法選擇這樣的進程，其要求訪問的磁道與當前磁頭所在的磁道距離最近，以使每次的尋道時間最短， 該算法可以得到比較好的吞吐量， 但卻不能保證 平均尋道時間最短。 其缺點是對用戶的服務請求的響應機會不是均等的， 因而導 致響應時間的變化幅度很大。 在服務請求很多的情況下， 對內外邊緣磁道的請求 將會無限期的被延遲，有些請求的響應時間將不可預期。1.4.3 、掃描算法（ SCAN、 掃描算法不僅考慮到欲

7、訪問的磁道與當前磁道的距離， 更優(yōu)先考慮的是磁頭的當前移動方向。 例如，當磁頭正在自里向外移動時， 掃描算法所選擇的下一個 訪問對象應是其欲訪問的磁道既在當前磁道之外， 又是距離最近的。 這樣自里向 外地訪問，直到再無更外的磁道需要訪問才將磁臂換向，自外向里移動。這時， 同樣也是每次選擇這樣的進程來調度， 即其要訪問的磁道， 在當前磁道之內， 從 而避免了饑餓現(xiàn)象的出現(xiàn)。 由于這種算法中磁頭移動的規(guī)律頗似電梯的運行， 故 又稱為電梯調度算法。 此算法基本上克服了最短尋道時間優(yōu)先算法的服務集中于 中間磁道和響應時間變化比較大的缺點， 而具有最短尋道時間優(yōu)先算法的優(yōu)點即 吞吐量較大， 平均響應時間

8、較小， 但由于是擺動式的掃描方法， 兩側磁道被訪問 的頻率仍低于中間磁道。第二章 概要設計2.1 設計思想本次課程設計我們是以面向對象的思想為主，利用 Visual C 為工具實 現(xiàn)模擬磁盤調度。程序主要是利用冒泡排序函數(shù)、FCFS函數(shù)、SSTF函數(shù)、SCAN函數(shù)、CSCA函數(shù)實現(xiàn)函數(shù)的功能。禾U用菜單式的選擇界面，方便的用戶操作。 最終對每一種模擬磁盤調度輸出磁頭平均移動的磁道數(shù)以及總磁道數(shù)。2.2 數(shù)據結構該程序主要是利用7個函數(shù)。Panduan ()函數(shù)：對輸入的字符進行判斷是否合法，zhuanhua ()函數(shù)：對輸入合法的字符進行轉化，bubble ()函數(shù)：對 輸入的磁道進行冒泡排序

9、，F(xiàn)CFS()函數(shù)，即先來先服務函數(shù)，SSTF()函數(shù)： 最短最短尋道時間函數(shù)，SCAN()函數(shù)：掃描函數(shù)，CSCAN )函數(shù)：循環(huán)掃描 函數(shù)。各函數(shù)之間有點可以相互調用，共同實現(xiàn)要求。本程序主要用到的數(shù)據結構為數(shù)組、字符串，包括對字符串的合法性判斷， 利用數(shù)組算磁頭移動的總磁道數(shù)，平均移動磁道數(shù)。2.3 模塊調用關系圖圖2-1磁盤調度模擬系統(tǒng)2.4子模塊程序流程圖先來先服務算法（FCFS流程圖：FCFS算法流程圖-開始輸入磁道號按輸入順序將 序列輸岀與磁道求平均尋道長度"動平輸岀移動旳平 道數(shù)L均磁1結束最短尋道時間優(yōu)先算法（SSTF）流程圖243掃描算法(SCAN流程圖開始輸入磁

10、道號調用冒泡排序函數(shù)SCAN 算法流程圖輸出排好序的磁道一 序列 輸入當前磁道號判斷當前磁頭在序 列中的位置選擇與當前磁道距離最近 的磁道進行掃描移動到最小(人丿號，改向外"(內)移動掃描未掃描的磁道1求平均尋道長度求總尋道長度結束第三章詳細設計3.1模塊劃分本系統(tǒng)劃分為四個模塊：先來先服務算法模塊int FCFS(i nt array,i ntm)、最短尋道時間優(yōu)先算法模塊int SSTF(int array,int m)、掃描算法模塊int SCAN(int array,int m)3.1.1 先來先服務算法模塊：int FCFS(i nt array,i nt m)輸入磁道號，

11、按先來先服務的策略輸出磁盤請求序列，求平均尋道長度，輸出移動平均磁道數(shù)。主要代碼：for(i=0,j=1;j<m;i+,j+)sum+=abs(arrayj-arrayi);ave=(float)(sum)/(float)(m);3.1.2 最短尋道時間優(yōu)先算法模塊：int SSTF(i nt array,i nt m)將磁道號用冒泡法從小到大排序， 輸出排好序的磁道序列， 輸入當前磁道號，根據前磁道在已排的序列中的位置， 動的平均磁道數(shù)。主要代碼： for(i=0;i<m;i+) /*for(j=i+1;j<m;j+)if(arrayi>arrayj)temp=arr

12、ayi;arrayi=arrayj;arrayj=temp;if(arraym-1<=now) /*大者，則直接由外向內依次給予各請求服務 for(i=m-1;i>=0;i-)cout<<arrayi<<" "sum=now-array0;elseif(array0>=now) /*小者，則直接由內向外依次給予各請求服務while(l>=0)&&(r<m) /*選擇掃描的順序， 求出平均尋道長度， 輸出移使用冒泡法按從小到大順序排列 */若當前磁道號大于請求序列中最*/if(now-arrayl)<

13、=(arrayr-now) /*若當前磁道號小于請求序列中最*/當前磁道在請求序列范圍內 */選擇與當前磁道最近的請求給予服務 */cout<<arrayl<<" "sum+=now-arrayl;now=arrayl;l=l-1;3.1.3 掃描算法模塊： int SCAN(int array,int m) 將磁道號用冒泡法從小到大排序， 輸出排好序的序列， 輸入當前磁道號， 選 擇移動臂的移動方向，根據當前磁道在已排的序列中的位置，選擇掃描的順序， 求出平均尋道長度，輸出移動的平均磁道數(shù)。主要代碼： if(d=0) /* 選擇移動臂方向向內，則先

14、向內掃描 */for(j=l;j>=0;j-)cout<<arrayj<<" " /* 輸出向內掃描的序列 */for(j=r;j<m;j+) /*磁頭移動到最小號， 則改變方向向外掃描未掃描的磁道*/cout<<arrayj<<" " /* 輸出向外掃描的序列 */sum=now-2*array0+arraym-1;else /* 選擇移動臂方向向外，則先向外掃描 */for(j=r;j<m;j+)cout<<arrayj<<" " /* 輸出

15、向外掃描的序列 * 、/* 磁頭移動到最大號， 則改變方向向內for(j=l;j>=0;j-)掃描未掃描的磁道*/coutvvarrayjvv""sum=-no w-array0+2*arraym-1;ave=(float)(sum)/(float)(m);第四章測試4.1先來先服務算法輸入磁道序列：65 78 34 23 87 100 18 26當前磁道號：80磁盤掃描序列為：65 78 34 23 87 100 18 26平均尋到長度：31.25磁頭移動總磁道數(shù)：2504.2最短尋道時間優(yōu)先算法(1)當前磁道號大于磁道序列中的最大的磁道號時3243d 07 55

16、232430?88砧口礎-2. :道.31數(shù) 為磁為列的列蠱 序前序舌心 求當描道動 盤聾均頭輸入磁道序列：65 78 34 23 87 100 18 26排序后的磁道序列為：18 23 26 34 65 78 87 100當前磁道號：200磁盤掃描序列為100 87 78 65 34 26 23 18平均尋到長度：22.75磁頭移動總磁道數(shù)：182001?887564362328132624356000 0 712 8為號10 列道* 農為：道 盤的列脣 磁前序養(yǎng) 的當描道動 后入掃書(2)當刖磁道號小于磁道序列中的最小的磁道號時輸入磁道序列：65 78 34 23 87 100 18 26

17、排序后的磁道序列為：18 23 26 34 65 78 87 100當前磁道號：10磁盤掃描序列為：18 23 26 34 65 78 87 100平均掃描長度：11.25磁道移動總磁道數(shù)：90436232 5 02 9 為號1B1-: 列道：丄教 蠱為希 盤的列富 磁前序 的當描道動 后入掃一62328 01 134 65 78 8765 78 87 100100(3)當前磁道號大于磁道序列中的最小的磁道號且小于最大磁道號時輸入磁道序列：65 78 34 23 87 100 18 26排序后的磁道序列為：18 23 26 34 65 78 87 100當前磁道號：80磁盤掃描序列為：78 8

18、7 100 65 34 26 23 18平均掃描長度：13.25磁道移動總磁道數(shù)：106I!二盤的列匱 磁前序舌心 的當描道動 后入掃書均頭為號78洌道.:18 23 ；8087 1002510634 6587 10034 26 23 1S4.3掃描算法(1)當前磁道號大于磁道序列中的最大的磁道號時輸入磁道序列：65 78 34 23 87 100 18 26排序后的磁道序列為：18 23 26 34 65 78 87 100當前磁道號：200磁盤掃描序列為100 87 78 65 34 26 23 18平均尋到長度：22.75磁頭移動總磁道數(shù)：182(2)當前磁道號小于磁道序列中的最小的磁道

19、號時輸入磁道序列：65 78 34 23 87 100 18 26排序后的磁道序列為：18 23 26 34 65 78 87 100當前磁道號：10磁盤掃描序列為：18 23 26 34 65 78 87 100平均掃描長度：11.25磁道移動總磁道數(shù)：90序后的磁盤序列為 18 23 26 34 65 78 87 100 輸入當前苗磁道號0盤掃描序列為】18 23 26 34 65 78 87 100(3)當前磁道號大于磁道序列中的最小的磁道號且小于最大磁道號(磁頭向外)時輸入磁道序列：65 78 34 23 87 100 18 26排序后的磁道序列為：18 23 26 34 65 78

20、87 100當前磁道號：80請輸入當前移動臂的移動的方向(1表示向外，0表示向內)：1磁盤掃描序列為：87 100 78 65 34 26 23 18平均尋到長度：12.75磁道移動總磁道數(shù)：1023向65方?80力08 0 2 移丄7516 為口咼872. 列道臂：丄數(shù) 霍動為，道 一盤的移列蠱 礒煎刖序舌心 的當當描道動 、/FI入入掃睦 一 頭62328i34 65 78 87 100<1表示向外，®表示向內：134 26 23 18O為聶 盤阿列專 前序首 的當描道動 后入掃一 葫為號87列道-t 18 :801002S231826 34 佔?8 87 10023 26

21、 34 65 78請選擇算法，5Press any key to cont inuej. i*n *第五章 心的體會通過這次的課程設計使我認識到要將操作系統(tǒng)這門計算機專業(yè)的課學好不 僅僅是要把書上的基本知識學好而且還要不斷進行實踐， 將所學的跟實踐操作結 合起來才能更好地鞏固所學，才能提高自己實踐能力 . 通過這次的設計使我認識 到只停留在表面理解問題是很難使問題得到很好的解決的， 實踐能力與理論知識 同樣重要。可以說此課程設計的理論難度并不大， 但是若要深入發(fā)掘其中的東西， 并且實際去編程實現(xiàn)， 就遇到了相當大的難度。 因為與之涉及的很多方面并沒有 學過，需要自己去自學和實踐檢驗。通過本次課

22、程設計，通過模擬磁盤調度及進程排隊算法來加深對操作系統(tǒng)中 各個磁臂調度算法概念的理解。模擬磁盤調度算法（FCFS,SSTF,SCAN,CSCAN實 現(xiàn)各種不同調度算法的過程， 并計算各算法的平均尋道長度， 以便于我們判斷各 種算法的優(yōu)劣以及各種算法使用的場合。對 VC+6.0的應用也更加得心應手。第六章 致謝感謝陜粉麗老師和本組成員在這次系統(tǒng)開發(fā)過程中對我的幫助參考文獻1 計算機操作系統(tǒng) 高等教育出版社，作者：孫鐘秀，費翔林，駱斌 等編著2 VC+深入詳解 電子工業(yè)出版社作者：孫鑫，余指導教師評語：指導教師簽名：年月日成績 評 疋項目權重成績1、設計過程中出勤、學習態(tài)度等方面0.12、設計技術

23、水平0.43、安全程度及可操作程度0.24、設計報告書寫及圖紙規(guī)范程度0.3總成績教研室審核意見：教研室主任簽字：年月日教學院（系）審核意見：主任簽字：年月日附源代碼#include<stdio.h>#include<stdlib.h>#include<iostream.h>#include<math.h> const int maxsize=1000;int panduan(char str);int zhuanhua(char str,int a);int *bubble(int cidao,int m);int FCFS(int cidao

24、,int m);void 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<<" 請輸入磁道序列( 0 結束)： "<<endl; bei1:cin>>str;a=panduan(str);if(a=0)"<<endl;"<<endl;cout<<" 輸入數(shù)據的類型錯誤 ,請重新輸入！ g

25、oto bei1;elsecidaoi=zhuanhua(str,a);i+;while(cidaoi-1!=0)cin>>str;a=panduan(str);if(a=0)cout<<" 輸入數(shù)據的類型錯誤 ,請重新輸入！ else cidaoi=zhuanhua(str,a); i+; count=i-1; cout<<" 你輸入的磁道序列為： " for(i=0;i<count;i+)cout<<cidaoi<<" " cout<<endl; while(1)

26、 cout<<endl;cout<<"|"<<endl;cout<<"|(*A_A*)系統(tǒng)菜單(*A_A*)|"<<endl;cout<<"|"<<endl;cout<<"|"<<endl;cout<<"|1. 先來先服務|"<<endl;cout<<"|"<<endl;cout<<"|2. 最短尋道

27、時間優(yōu)先|"<<endl;cout<<"|"<<endl;cout<<"|3. 掃描調度|"<<endl;cout<<"|"<<endl;cout<<"|4. 退出|"<<endl;cout<<"|"<<endl;cout<<"|"<<endl;cout<<"|"<<e

28、ndl;bei7:cout<<" 請選擇算法：bei6:cin>>str;a=panduan(str);if(a=0)cout<<" 輸入數(shù)據的類型錯誤 ,請重新輸入！ "<<endl; goto bei6;elsec=zhuanhua(str,a);if(c=5)break;if(c>5)cout<<" 數(shù)據輸入錯誤！請重新輸入 "<<endl; goto bei7;switch(c)case 1:FCFS(cidao,count); break;case 2:SS

29、TF(cidao,count); break;case 3:SCAN(cidao,count); break; return 0;/*判斷輸入數(shù)據是否有效 */ int panduan(char str) int i=0;while(stri!='0')if(stri<'0'|stri>'9') return 0; break;i+; return i;/*將字符串轉換成數(shù)字 */int zhuanhua(char str,int a)int i;int sum=0; for(i=0;i<a;i+) sum=sum+(int)(

30、stri-'0')*pow(10,a-i-1);return sum;*冒泡排序算法 *int *bubble(int cidao,int m)int i,j;int temp;for(i=0;i<m;i+)for(j=i+1;j<m;j+)if(cidaoi>cidaoj)temp=cidaoi;cidaoi=cidaoj; cidaoj=temp;cout<<" 排序后的磁盤序列為：for( i=0;i<m;i+)cout<<cidaoi<<" "cout<<endl;re

31、turn cidao;/*先來先服務調度算法 */int FCFS(int cidao,int m) int now;int sum=0;int j,i;int a;char str100;float ave;cout<<" 磁盤請求序列為： "for( i=0;i<m;i+) cout<<cidaoi<<" "cout<<endl;cout<<" 請輸入當前的磁道號： "bei2: cin>>str;a=panduan(str);if(a=0)cout&l

32、t;<" 輸入數(shù)據的類型錯誤 ,請重新輸入！ "<<endl; goto bei2;elsenow=zhuanhua(str,a);sum+=abs(cidao0-now);cout<<" 磁盤掃描序列為： "for( i=0;i<m;i+)cout<<cidaoi<<" "for(i=0,j=1;j<m;i+,j+)sum+=abs(cidaoj-cidaoi); ave=(float)(sum)/(float)(m);cout<<endl;cout<

33、;<" 平均尋道長度： "<<ave<<endl;cout<<" 磁頭移動總磁道數(shù)： "<<sum<<endl; return 0;*最短尋道時間優(yōu)先調度算法 */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(cidao,m);cout<<" 請輸入當前的磁道號： " bei3: cin>&g

34、t;str;a=panduan(str);if(a=0)cout<<" 輸入數(shù)據的類型錯誤 ,請重新輸入！ "<<endl; goto bei3;elsenow=zhuanhua(str,a);if(cidaom-1<=now)cout<<" 磁盤掃描序列為：for(i=m-1;i>=0;i-)cout<<cidaoi<<" "sum=now-cidao0; if(cidao0>=now)cout<<" 磁盤掃描序列為： " for(i

35、=0;i<m;i+) cout<<cidaoi<<" " sum=cidaom-1-now; if(now>cidao0&&now<cidaom-1)cout<<" 磁盤掃描序列為： " while(cidaok<now)k+; l=k-1; r=k;while(l>=0)&&(r<m) if(now-cidaol)<=(cidaor-now) cout<<cidaol<<" " sum+=now-ci

36、daol; now=cidaol;l=l-1;else cout<<cidaor<<" " sum+=cidaor-now; now=cidaor; r=r+1; if(l=-1) for(j=r;j<m;j+) cout<<cidaoj<<" " sum+=cidaom-1-cidao0;elsefor(j=l;j>=0;j-)cout<<cidaoj<<" " sum+=cidaom-1-cidao0;ave=(float)(sum)/(float)(m);cout<<endl;cout<<" 平均尋道長度： "<<ave<<endl; cout<<" 磁頭移動總磁道數(shù)： "<<sum<<endl;*掃