操作系統(tǒng)試驗匯報學(xué)生學(xué)院計算機(jī)學(xué)院專業(yè)班級計算機(jī)科學(xué)與技術(shù)3班學(xué)號學(xué)生姓名林虹指導(dǎo)教師丁國芳年12月15曰目錄1試驗一進(jìn)程調(diào)度…………………… 12試驗二銀行家算法………………… 163試驗三動態(tài)分辨別配方式的模擬……………… 204試驗四仿真多種磁盤調(diào)度算法…………………..26試驗一進(jìn)程調(diào)度1.試驗?zāi)康木帉懖⒄{(diào)試一種模擬的進(jìn)程調(diào)度程序，分別采用“短進(jìn)程優(yōu)先”、“時間片輪轉(zhuǎn)”、“高響應(yīng)比優(yōu)先”調(diào)度算法對隨機(jī)產(chǎn)生的五個進(jìn)程進(jìn)行調(diào)度，并比較算法的平均周轉(zhuǎn)時間。以加深對進(jìn)程的概念及進(jìn)程調(diào)度算法的理解。2.試驗規(guī)定每個進(jìn)程由一種進(jìn)程控制塊（PCB）表達(dá)，進(jìn)程控制塊可以包括如下信息：進(jìn)程名、優(yōu)先數(shù)（響應(yīng)比）、抵達(dá)時間、需要運(yùn)行時間（進(jìn)程的長度）、已運(yùn)行時間、進(jìn)程狀態(tài)等等（可以根據(jù)需要自已設(shè)定）。由程序自動生成進(jìn)程（包括需要的數(shù)據(jù)，要注意數(shù)據(jù)的合理范圍），第一種進(jìn)程抵達(dá)時間從0開始，其他進(jìn)程抵達(dá)時間隨機(jī)產(chǎn)生。采用時間片輪轉(zhuǎn)調(diào)度算法時，進(jìn)程的運(yùn)行時間以時間片為單位進(jìn)行計算。每個進(jìn)程的狀態(tài)可以是就緒W（Wait）、運(yùn)行R（Run）、或完畢F（Finish）三種狀態(tài)之一。每進(jìn)行一次調(diào)度，程序都要輸出一次運(yùn)行成果：正在運(yùn)行的進(jìn)程、就緒隊列中的進(jìn)程、完畢的進(jìn)程以及各個進(jìn)程的PCB，以便進(jìn)行檢查。最終計算各調(diào)度算法的平均周轉(zhuǎn)時間，并進(jìn)行比較、分析。3.試驗內(nèi)容 a.算法原理（1）短進(jìn)程優(yōu)先調(diào)度算法“短進(jìn)程優(yōu)先”調(diào)度算法的基本思想是把CPU分派給就緒隊列中需要時間最短的進(jìn)程。（2）時間片輪轉(zhuǎn)算法將系統(tǒng)中所有的就緒進(jìn)程按照FCFS原則，排成一種隊列。每次調(diào)度時將CPU分派給隊首進(jìn)程，讓其執(zhí)行一種時間片。時間片的長度從幾種ms到幾百ms。在一種時間片結(jié)束時，發(fā)生時鐘中斷。調(diào)度程序據(jù)此暫停目前進(jìn)程的執(zhí)行，將其送到就緒隊列的末尾，并通過上下文切換執(zhí)行目前的隊首進(jìn)程。進(jìn)程可以未使用完一種時間片，就出讓CPU。（3）高響應(yīng)比優(yōu)先算法HRRN調(diào)度方略同步考慮每個作業(yè)的等待時間長短和估計需要的執(zhí)行時間長短，從中選出響應(yīng)比最高的作業(yè)投入執(zhí)行。每個作業(yè)完畢後要打印該作業(yè)的開始運(yùn)行時刻、完畢時刻、周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間，這一組作業(yè)完畢後要計算并打印這組作業(yè)的平均周轉(zhuǎn)時間、帶權(quán)平均周轉(zhuǎn)時間。b.程序流程圖c.重要數(shù)據(jù)構(gòu)造 d.各程序闡明及關(guān)系 1.voidinput()輸入進(jìn)程函數(shù) 2.voidprint()打印進(jìn)程函數(shù)3.intmain()主函數(shù)調(diào)用4.各函數(shù)代碼voidSJF()短進(jìn)程優(yōu)先函數(shù) e運(yùn)行成果截圖voidRR()短進(jìn)程優(yōu)先函數(shù)運(yùn)行成果截圖voidHRRN()高響應(yīng)比優(yōu)先函數(shù)程序運(yùn)行成果4.成果分析與試驗小結(jié)作業(yè)調(diào)度本質(zhì)與進(jìn)程調(diào)度類似，不過多道的話，就要多考慮空間的容量了。單道的狀況就不作分析了，對于多道調(diào)度，要考慮清晰，什么時候可以接納新的作業(yè)進(jìn)來；對于給定的空間來說，一次能讓作業(yè)同步執(zhí)行的數(shù)量應(yīng)當(dāng)是多少；根據(jù)算法，應(yīng)當(dāng)按照怎么樣的先後次序選擇等待的作業(yè)……逐漸分析後，對于非搶占的CPU，一旦作業(yè)進(jìn)入了執(zhí)行狀態(tài)，它的結(jié)束時間也就定了下來，一旦有作業(yè)結(jié)束，就會釋放空間，釋放之後就能立即選擇新的作業(yè)進(jìn)來。根據(jù)不一樣算法，對等待隊列也有不一樣的排序成果，無論怎樣，都按先後次序放入隊列中，因此每次選擇的時候，都要遍歷一遍所有等待中的進(jìn)程，假如這個作業(yè)滿足空間需求，則放入CPU中執(zhí)行，同步更新結(jié)束時間，否則則跳過這個作業(yè)，判斷下一種作業(yè)，直到問詢完所有等待的作業(yè)為止。不停反復(fù)上面的環(huán)節(jié)，直到所有的作業(yè)都執(zhí)行完因此模擬的時候，分別開了一種運(yùn)行隊列和一種等待隊列，運(yùn)行隊列作為判斷有哪個作業(yè)已經(jīng)執(zhí)行結(jié)束。通過這個試驗，對操作系統(tǒng)的作業(yè)調(diào)度已經(jīng)有了更深一層的理解了，望後來能再接再厲。試驗二銀行家算法1.試驗?zāi)康挠勉y行家算法防止死鎖，實現(xiàn)系統(tǒng)合理分派資源，加深對進(jìn)程同步及死鎖理解。2.試驗規(guī)定假定系統(tǒng)有3類資源A（10個）、B（15個）、C（12個），系有5個進(jìn)程并發(fā)執(zhí)行，進(jìn)程調(diào)度采用時間片輪轉(zhuǎn)調(diào)度算法。每個進(jìn)程由一種進(jìn)程控制塊（PCB）表達(dá)，進(jìn)程控制塊可以包括如下信息：進(jìn)程名、需要的資源總數(shù)、已分派的資源數(shù)、進(jìn)程狀態(tài)。由程序自動生成進(jìn)程（包括需要的數(shù)據(jù)，要注意數(shù)據(jù)的合理范圍）。進(jìn)程在運(yùn)行過程中會隨機(jī)申請資源（隨機(jī)生成祈求的資源數(shù)），假如到達(dá)最大需求，表達(dá)該進(jìn)程可以完畢；假如沒有到達(dá)最大需求，則運(yùn)行一種時間片後，調(diào)度其他進(jìn)程運(yùn)行。資源分派采用銀行家算法來防止死鎖。每個進(jìn)程的狀態(tài)可以是就緒W（Wait）、運(yùn)行R（Run）、阻塞B（Block）或完畢F（Finish）狀態(tài)之一。每進(jìn)行一次調(diào)度，程序都要輸出一次運(yùn)行成果：正在運(yùn)行的進(jìn)程、就緒隊列中的進(jìn)程、阻塞隊列中的進(jìn)程、完畢的進(jìn)程以及各個進(jìn)程的PCB，以便進(jìn)行檢查。3.試驗內(nèi)容a.算法原理操作系統(tǒng)按照銀行家制定的規(guī)則為進(jìn)程分派資源，當(dāng)進(jìn)程初次申請資源時，要測試該進(jìn)程對資源的最大需求量，假如系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按目前的申請量分派資源，否則就推遲分派。當(dāng)進(jìn)程在執(zhí)行中繼續(xù)申請資源時，先測試該進(jìn)程本次申請的資源數(shù)與否超過了該資源所剩余的總量。若超過則拒絕分派資源，若能滿足則按目前的申請量分派資源，否則也要推遲分派b.程序流程圖c.重要數(shù)據(jù)構(gòu)造d.各函數(shù)實現(xiàn) 1.voidinput()隨機(jī)生成進(jìn)程函數(shù)2.voidprint()pcb打印函數(shù)3.voidSafe()安全性檢查算法4.voidBankalgorithm()5.intmain()主函數(shù)e.運(yùn)行成果截圖4.成果分析與小結(jié)多種進(jìn)程同步運(yùn)行時，系統(tǒng)根據(jù)各類系統(tǒng)資源的最大需求和各類系統(tǒng)的剩余資源為進(jìn)程安排安全序列，使得系統(tǒng)能迅速且安全地運(yùn)行進(jìn)程，不至發(fā)生死鎖。銀行家算法是防止死鎖的重要措施，其思緒在諸多方面都非常值得我們來學(xué)習(xí)借鑒。試驗三動態(tài)分辨別配方式的模擬1.試驗?zāi)康睦斫鈩討B(tài)分辨別配方式中的數(shù)據(jù)構(gòu)造和分派算法，并深入加深對動態(tài)分區(qū)存儲管理方式及其實現(xiàn)過程的理解2.試驗規(guī)定用C語言分別實現(xiàn)采用初次適應(yīng)算法和最佳適應(yīng)算法的動態(tài)分辨別配過程和回收過程。其中，空閑分區(qū)通過空閑分區(qū)鏈（表）來管理；在進(jìn)行內(nèi)存分派時，系統(tǒng)優(yōu)先使用空閑區(qū)低端的空間。假設(shè)初始狀態(tài)下，可用的內(nèi)存空間為640KB，并有下列的祈求序列：祈求次序操作祈求內(nèi)存大?。↘B）作業(yè)1申請130作業(yè)2申請60作業(yè)3申請100作業(yè)2釋放60作業(yè)4申請200作業(yè)3釋放100作業(yè)1釋放130作業(yè)5申請140作業(yè)6申請60作業(yè)7申請50作業(yè)8申請60規(guī)定每次分派和回收後顯示出作業(yè)分派狀況及空閑內(nèi)存分區(qū)鏈的狀況。3.試驗內(nèi)容a.算法原理（1）初次適應(yīng)算法:最先適應(yīng)算法的基本思想是空閑區(qū)表中的空閑區(qū)按地址大小遞增次序排列。當(dāng)規(guī)定分派一種容量S的區(qū)域時，在空閑區(qū)表中從頭開始比較。直到找到X>=S為止。假如滿足，則從X中分派S，剩余部分保留在空閑區(qū)表中本來位置，否則分派失敗。（2）最佳適應(yīng)算法:最佳適應(yīng)算法的基本思想是空閑區(qū)表中空閑區(qū)按其容量以遞增次序排列，即X1<=X2<=X3<=.......<=Xn。當(dāng)規(guī)定一種空閑區(qū)時，由小到大進(jìn)行查找。假如規(guī)定分派一種容量為S的分區(qū)，則從X1開始比較，直至S<=X1；然後從Xi分派S,若有剩余，則作為一種空余區(qū)插入合適位置，否則分派失敗。b.程序流圖分派回收c.重要數(shù)據(jù)構(gòu)造闡明d.各程序闡明及其關(guān)系1.space*New_space(intnum,intSize,intadr):動態(tài)申請空間函數(shù)動態(tài)申請措施如下：2.voidFF()：初次適應(yīng)算法函數(shù)遍歷一次所有的空閑分區(qū)，一旦找到則跳出遍歷，分派空間，分派後，也許會有Size==0的分區(qū)出現(xiàn)，這時候應(yīng)當(dāng)調(diào)用remove_zero函數(shù)，將該分區(qū)移出鏈表：3.voidBF()：最佳適應(yīng)算法函數(shù)每次分派前都要找一次最小值，假如找不到，則闡明分派失敗，已經(jīng)沒有可以滿足空間規(guī)定的分區(qū)了，關(guān)鍵代碼如下：voidrecycle()：回收空間函數(shù)對于回收的過程，則要分狀況處理了，關(guān)鍵代碼及其詳細(xì)闡明如下：e.程序設(shè)計成果為6個進(jìn)程依次自動分派空間，分派所有後，再依次釋放空間：1.初次適應(yīng)算法2.最佳適應(yīng)算法4.成果分析與小結(jié)可變分區(qū)的分派與回收，關(guān)鍵在于細(xì)心。對于分派來說，根據(jù)三個算法來分派，基本用鏈表來模擬的話，應(yīng)當(dāng)沒什么問題。而對于回收來說，要判斷的條件就會比較多了，首先要考慮是不是第一種分區(qū)，再考慮是不是最終一種，兩者都不是的話，就要考慮與否相鄰的狀況，對于第一種和最終一種，也同樣需要考慮與否相鄰的狀況，因此用鏈表模擬的話，一定要細(xì)心，否則很輕易會出現(xiàn)指針越界導(dǎo)致程序瓦解。試驗四仿真多種磁盤調(diào)度算法1.試驗?zāi)康?.試驗規(guī)定先來先服務(wù)算法、最短尋道時間優(yōu)先算法、掃描算法和循環(huán)掃描算法時磁頭移動次序并計算磁頭的平均移動磁道數(shù)。（假設(shè)磁頭剛從80磁道移到100磁道）3.試驗內(nèi)容a.算法原理（1）先來先服務(wù)算法即先來的祈求先被響應(yīng)。FCFS方略看起來似乎是相稱"公平"的，不過當(dāng)祈求的頻率過高的時候FCFS方略的響應(yīng)時間就會大大延長。FCFS方略為我們建立起一種隨機(jī)訪問機(jī)制的模型，不過假如用這個方略反復(fù)響應(yīng)從裏到外的祈求，那么將會消耗大量的時間。為了盡量減少尋道時間，看來我們需要對等待著的祈求進(jìn)行合適的排序，而不是簡樸的使用FCFS方略。這個過程就叫做磁盤調(diào)度管理。有時候FCFS也被看作是最簡單的磁盤調(diào)度算法（2）最短尋道時間優(yōu)先算法規(guī)定訪問的磁道，與目前磁頭所在的磁道距離近來，以使每次的尋道時間最短。（3）掃描算法該算法不僅考慮到欲訪問的磁道與目前磁道間的距離，更優(yōu)先考慮的是磁頭目前的移動方向。例如，當(dāng)磁頭正在自裏向外移動時，SCAN算法所考慮的下一種訪問對象，應(yīng)是其欲訪問的磁道，既在目前磁道之外，又是距離近來的。這樣自裏向外的訪問，直至再無更外的磁道需要訪問時，才將磁道換向自外向裏移動。這時，同樣也是每次選擇這樣的進(jìn)程來調(diào)度，也就是要訪問的目前位置內(nèi)距離近來者，這樣，磁頭又逐漸地從外向裏移動，直至再無更裏面的磁道要訪問，從而防止了出現(xiàn)“饑餓”現(xiàn)像（4）循環(huán)算法當(dāng)磁頭剛從裏向外移動而越過了某一磁道時，恰好又有一進(jìn)程祈求訪問此磁道，這時，該裏程就必須等待，為了減少這種延遲，CSCAN算法規(guī)定磁頭單向移動，而本實驗過程中我們所設(shè)計的是磁頭從裏向外移動，而從外向裏移動時只須改方向而已，本實驗未實現(xiàn)。但本試驗已完全能演示循環(huán)掃描的全過程。b.總程序流圖c.重要數(shù)據(jù)構(gòu)造d.各算法代碼1.doubleFCFS()先來先服務(wù)算法2.doubleSSTF()最短尋道時間優(yōu)先算法3.doubleSCAN()掃描算法4.doubleCSCAN()循環(huán)算法5.intmain()主函數(shù)e.運(yùn)行成果4.成果分析與小結(jié)計算機(jī)磁盤是一種很重要也很常用的外部設(shè)備，其分派也有一定的分派方略。在操作系統(tǒng)中，作業(yè)對磁盤的祈求常常要排隊，由此需要某些高效率的磁盤分派方略算法。（1）先來先服務(wù)算法為一種最簡樸的磁盤調(diào)度算法，它直接根據(jù)作業(yè)祈求磁盤的先後次序?qū)Υ疟P進(jìn)行尋訪，公平、簡樸，每個作業(yè)的磁盤祈求都可以得到處理，不會出現(xiàn)某個作業(yè)的祈求長期得不到滿足的狀況，但未對尋道方案進(jìn)行優(yōu)化；（2）最短尋道時間優(yōu)先算法優(yōu)先選擇距離目前磁頭位置近來的作業(yè)磁道祈求，可以使得每次尋道時所用的時間都最短，但不能保證平均周轉(zhuǎn)時間及帶權(quán)周轉(zhuǎn)時間最短；（3）電梯算法同步考慮下一種作業(yè)磁道祈求與目前磁頭位置的距離和目前磁頭移動方向先選擇目前磁頭之外距離其近來的磁道進(jìn)行訪問，直到再無更外的磁道祈求，再將磁臂換向，訪問磁頭內(nèi)側(cè)距離目前磁頭位置近來的作業(yè)磁道祈求，防