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

1、精選文檔某某高校課程設(shè)計(jì)報(bào)告課程名稱： 操作系統(tǒng) 設(shè)計(jì)題目： 模擬磁盤(pán)調(diào)度算法 系 別： 計(jì)算機(jī)系 專 業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù) 組 別： 同學(xué)姓名: 學(xué) 號(hào): 起止日期: 指導(dǎo)老師: 名目第一章 需求分析11.1課程設(shè)計(jì)的簡(jiǎn)介11.2課程設(shè)計(jì)的目的11.3磁盤(pán)調(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第三章 具體設(shè)計(jì)63.1模塊劃分6第四章 代碼測(cè)試94.1先來(lái)先服務(wù)94.1最短尋道時(shí)間優(yōu)先114.1掃描算法12第五章 心得體會(huì)13第六章 致謝13參考文獻(xiàn)1附源代碼2第一章 需求分析1.1課程設(shè)計(jì)的簡(jiǎn)

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

3、求先安排、優(yōu)先級(jí)高者先安排等策略。在多道程序系統(tǒng)中，低效率通常是由于磁盤(pán)類旋轉(zhuǎn)設(shè)備使用不當(dāng)造成的。操作系統(tǒng)中，對(duì)磁盤(pán)的訪問(wèn)要求來(lái)自多方面，經(jīng)常需要排隊(duì)。這時(shí)，對(duì)眾多的訪問(wèn)要求按肯定的次序響應(yīng)，會(huì)直接影響磁盤(pán)的工作效率，進(jìn)而影響系統(tǒng)的性能。訪問(wèn)磁盤(pán)的時(shí)間因子由3部分構(gòu)成，它們是查找（查找磁道）時(shí)間、等待（旋轉(zhuǎn)等待扇區(qū)）時(shí)間和數(shù)據(jù)傳輸時(shí)間，其中查找時(shí)間是打算因素。因此，磁盤(pán)調(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)磁盤(pán)

4、執(zhí)行輸入輸出操作時(shí)，要把移動(dòng)臂移動(dòng)到指定的柱面，再等待指定扇區(qū)的旋轉(zhuǎn)到磁頭位置下，然后讓指定的磁頭進(jìn)行讀寫(xiě)，完成信息傳送。因此，執(zhí)行一次輸入輸出所花的時(shí)間有： 查找時(shí)間磁頭在移動(dòng)臂帶動(dòng)下移動(dòng)到指定柱面所花的時(shí)間。 延遲時(shí)間指定扇區(qū)旋轉(zhuǎn)到磁頭下所需的時(shí)間。 傳送時(shí)間由磁頭進(jìn)程讀寫(xiě)完成信息傳送的時(shí)間。 其中傳送信息所花的時(shí)間，是在硬件設(shè)計(jì)就固定的。而查找時(shí)間和延遲時(shí)間是與信息在磁盤(pán)上的位置有關(guān)。 為了削減移動(dòng)臂進(jìn)行移動(dòng)花費(fèi)的時(shí)間，每個(gè)文件的信息不是按盤(pán)面上的磁道挨次存放滿一個(gè)盤(pán)面后，再放到下一個(gè)盤(pán)面上。而是按柱面存放，同一柱面上的各磁道被放滿信息后，再放到下一個(gè)柱面上。所以各磁盤(pán)的編號(hào)按柱面挨次（

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

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

7、磁道之外，又是距離最近的。這樣自里向外地訪問(wèn)，直到再無(wú)更外的磁道需要訪問(wèn)才將磁臂換向，自外向里移動(dòng)。這時(shí)，同樣也是每次選擇這樣的進(jìn)程來(lái)調(diào)度，即其要訪問(wèn)的磁道，在當(dāng)前磁道之內(nèi)，從而避開(kāi)了饑餓現(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í)間較小，但由于是搖擺式的掃描方法，兩側(cè)磁道被訪問(wèn)的頻率仍低于中間磁道。其次章 概要設(shè)計(jì)2.1設(shè)計(jì)思想本次課程設(shè)計(jì)我們是以面對(duì)對(duì)象的思想為主，利用Visual C為工具實(shí)現(xiàn)模擬磁盤(pán)調(diào)度。程序主要

8、是利用冒泡排序函數(shù)、FCFS函數(shù)、SSTF函數(shù)、SCAN函數(shù)、CSCAN函數(shù)實(shí)現(xiàn)函數(shù)的功能。利用菜單式的選擇界面，便利的用戶操作。最終對(duì)每一種模擬磁盤(pán)調(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ù)，即先來(lái)先服務(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)系圖磁盤(pán)調(diào)度模擬系統(tǒng)先來(lái)先服務(wù)最短尋道時(shí)間優(yōu)先掃描算法退出 圖2-1 磁盤(pán)調(diào)度模擬系統(tǒng)2.4子模塊程序流程圖2.4.1先來(lái)先服務(wù)算法（FCFS）流程圖：2.4.2最短尋道時(shí)間優(yōu)先算法（SSTF）流程圖2.4.3掃描算法（SCAN）流程圖第三章 具體設(shè)計(jì)3.1模塊劃分本系統(tǒng)劃分為四個(gè)模塊：先來(lái)先服務(wù)算法模塊int FCFS(int array,int m)、最短尋道時(shí)間優(yōu)先算法模塊int SSTF(int array,int m)、掃描算法模塊int SCAN(int array,int m) 3.1

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

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

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

13、8 34 23 87 100 18 26平均尋到長(zhǎng)度：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磁盤(pán)掃描序列為100 87 78 65 34 26 23 18平均尋到長(zhǎng)度：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

14、當(dāng)前磁道號(hào)：10磁盤(pán)掃描序列為：18 23 26 34 65 78 87 100平均掃描長(zhǎng)度：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磁盤(pán)掃描序列為：78 87 100 65 34 26 23 18平均掃描長(zhǎng)度：13.25磁道移動(dòng)總磁道數(shù)：1064.3 掃描算法（1）當(dāng)前磁道號(hào)大于磁道序列中的最大的磁道號(hào)時(shí)輸入磁道序列：65 78 34 23 87 100 18 26 排序后的磁道序列為：18 2

15、3 26 34 65 78 87 100當(dāng)前磁道號(hào)：200磁盤(pán)掃描序列為100 87 78 65 34 26 23 18平均尋到長(zhǎng)度：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磁盤(pán)掃描序列為：18 23 26 34 65 78 87 100平均掃描長(zhǎng)度：11.25磁道移動(dòng)總磁道數(shù)：90（3）當(dāng)前磁道號(hào)大于磁道序列中的最小的磁道號(hào)且小于最大磁道號(hào)（磁頭向外）時(shí)輸入磁道序列：65 78 34 23 87 100 18

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

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

18、者：孫鑫，余指導(dǎo)老師評(píng)語(yǔ)： 指導(dǎo)老師簽名： 年 月 日成果評(píng)定項(xiàng) 目權(quán)重成果1、設(shè)計(jì)過(guò)程中出勤、學(xué)習(xí)態(tài)度等方面0.12、設(shè)計(jì)技術(shù)水平0.43、平安程度及可操作程度0.24、設(shè)計(jì)報(bào)告書(shū)寫(xiě)及圖紙規(guī)范程度0.3總 成 績(jī) 教研室審核意見(jiàn)：教研室主任簽字： 年 月 日教學(xué)院（系）審核意見(jiàn)： 主任簽字： 年 月 日附源代碼#include#include#include#includeconst int maxsize=1000;int panduan(char str); int zhuanhua(char str,int a); int *bubble(int cidao,int m); int F

19、CFS(int cidao,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請(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+

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

21、ut|_|endl; cout|_|endl; bei7: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

22、(stri9)return 0;break;i+;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排序后的磁盤(pán)序列為：;

23、 for( i=0;im;i+) coutcidaoi ; coutendl; return cidao; /*先來(lái)先服務(wù)調(diào)度算法*/int FCFS(int cidao,int m) int now; int sum=0; int j,i;int a;char str100; float ave; cout磁盤(pán)懇求序列為：; 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);

24、sum+=abs(cidao0-now);cout磁盤(pán)掃描序列為：; 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平均尋道長(zhǎng)度：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; f

25、loat ave; cidao=bubble(cidao,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磁盤(pán)掃描序列為：; for(i=0;im;i+) coutcidaoicidao0&nowcidaom-1) cout磁盤(pán)掃描序列為：; while(cidaok=0)&(rm) if(now-cidaol)=(cidaor-now) coutcidaol ; sum+=now-cidaol; now=cidaol; l=l-1; else