《計(jì)算機(jī)操作系統(tǒng)》實(shí)驗(yàn)學(xué)生

1、計(jì)算機(jī)操作系統(tǒng)實(shí)驗(yàn)要求為了順利完成操作系統(tǒng)課程實(shí)驗(yàn)，應(yīng)做到： （1） 實(shí)驗(yàn)前，認(rèn)真學(xué)習(xí)教材以及實(shí)驗(yàn)要求的相關(guān)內(nèi)容，提前做好實(shí)驗(yàn)準(zhǔn)備。（2） 實(shí)驗(yàn)結(jié)束后三天內(nèi)提交實(shí)驗(yàn)報(bào)告的電子版和打印版。實(shí)驗(yàn)報(bào)告內(nèi)容應(yīng)包括：實(shí)驗(yàn)?zāi)康?、?shí)驗(yàn)內(nèi)容、設(shè)計(jì)思路和流程框圖，主要程序代碼、測(cè)試結(jié)果以及實(shí)驗(yàn)總結(jié)。（實(shí)驗(yàn)報(bào)告模板見“OS實(shí)驗(yàn)?zāi)０濉保?） 遵守機(jī)房紀(jì)律，服從指揮，愛護(hù)實(shí)驗(yàn)設(shè)備。實(shí)驗(yàn)的驗(yàn)收將分為兩個(gè)部分。第一部分是上機(jī)操作，隨機(jī)抽查程序運(yùn)行和即時(shí)提問；第二部分是提交書面的實(shí)驗(yàn)報(bào)告。要杜絕抄襲現(xiàn)象，一經(jīng)發(fā)現(xiàn)雷同，雙方成績均以0分計(jì)算。實(shí)驗(yàn)內(nèi)容安排：實(shí)驗(yàn)內(nèi)容與要求實(shí)驗(yàn)一熟悉進(jìn)程調(diào)度相關(guān)內(nèi)容；根據(jù)進(jìn)程調(diào)度算法，選擇先來

2、先服務(wù)、短進(jìn)程優(yōu)先、時(shí)間片輪轉(zhuǎn)、高優(yōu)先權(quán)優(yōu)先調(diào)度等算法中的一個(gè)，編寫算法模擬程序。實(shí)驗(yàn)二熟悉頁面置換相關(guān)內(nèi)容；選擇最佳置換算法、先進(jìn)先出置換算法、LRU置換算法中的一個(gè)，編寫算法模擬程序。實(shí)驗(yàn)三熟悉銀行家算法，并編寫程序進(jìn)行模擬。實(shí)驗(yàn)一 進(jìn)程調(diào)度實(shí)驗(yàn)3實(shí)驗(yàn)二 頁面置換算法模擬10實(shí)驗(yàn)三 銀行家算法模擬15實(shí)驗(yàn)一 進(jìn)程調(diào)度實(shí)驗(yàn)【開發(fā)語言及實(shí)現(xiàn)平臺(tái)或?qū)嶒?yàn)環(huán)境】C+/C#/CfreeTurbo C / Microsoft Visual Studio 6.0 / Microsoft Visual Studio .NET 2010【實(shí)驗(yàn)?zāi)康摹浚?）加深對(duì)進(jìn)程的概念及進(jìn)程調(diào)度算法的理解；（2）在了解和掌握

3、進(jìn)程調(diào)度算法的基礎(chǔ)上，編制進(jìn)程調(diào)度算法通用程序，將調(diào)試結(jié)果顯示在計(jì)算機(jī)屏幕上，并檢測(cè)機(jī)算和筆算的一致性。【實(shí)驗(yàn)要求】（1）了解進(jìn)程調(diào)度；（2）理解利用進(jìn)程調(diào)度算法進(jìn)行調(diào)度的原理；（3）使用某種編程語言進(jìn)行算法模擬?！緦?shí)驗(yàn)原理】（注意：這個(gè)僅是個(gè)例子，可以參考本例，選擇其他算法進(jìn)行實(shí)驗(yàn)）一、 例題：設(shè)計(jì)一個(gè)有N個(gè)進(jìn)程的進(jìn)程調(diào)度算法。進(jìn)程調(diào)度算法：采用最高優(yōu)先數(shù)的調(diào)度算法（即把處理機(jī)分配給優(yōu)先數(shù)最高的進(jìn)程）。每個(gè)進(jìn)程有一個(gè)進(jìn)程控制塊（PCB）表示。進(jìn)程控制塊可以包含如下信息：進(jìn)程名、優(yōu)先數(shù)、到達(dá)時(shí)間、需要運(yùn)行時(shí)間、已用CPU時(shí)間、進(jìn)程狀態(tài)等等。進(jìn)程的優(yōu)先數(shù)及需要的運(yùn)行時(shí)間可以事先人為的指定（也可以

4、由隨機(jī)數(shù)產(chǎn)生）。進(jìn)程的到達(dá)時(shí)間為進(jìn)程的輸入的時(shí)間。進(jìn)程的運(yùn)行時(shí)間以時(shí)間片為單位進(jìn)行計(jì)算。每個(gè)進(jìn)程的狀態(tài)可以是就緒W（Wait）、運(yùn)行R（Run）、或完成F（Finish）三種狀態(tài)之一。就緒進(jìn)程獲得CPU后都只能運(yùn)行一個(gè)時(shí)間片。用已占用CPU時(shí)間加1表示。如果運(yùn)行一個(gè)時(shí)間片后，進(jìn)程的已占用CPU時(shí)間已達(dá)到所需要的運(yùn)行時(shí)間，則撤銷該進(jìn)程，如果運(yùn)行一個(gè)時(shí)間片后，進(jìn)程的已占用CPU時(shí)間還未達(dá)到所需要的運(yùn)行時(shí)間，也就是進(jìn)程還需要繼續(xù)運(yùn)行，此時(shí)應(yīng)該將進(jìn)程的優(yōu)先數(shù)減1（即降低一級(jí)），然后把它插入就緒隊(duì)列等待CPU。每進(jìn)行一次調(diào)度程序都打印一次運(yùn)行進(jìn)程、就緒隊(duì)列、以及各個(gè)進(jìn)程的PCB，以便進(jìn)行檢查。重復(fù)以上過

5、程，直到所要的進(jìn)程都完成為止。分析:使用固定隊(duì)列與靜動(dòng)態(tài)優(yōu)先級(jí)結(jié)合每個(gè)優(yōu)先級(jí)為00xFF,并且以小的數(shù)字為高優(yōu)先級(jí)，大的數(shù)字為低優(yōu)先級(jí)，每次皆使用循環(huán)得到最高優(yōu)先級(jí)的進(jìn)程并執(zhí)行，然后將其動(dòng)態(tài)優(yōu)先級(jí)設(shè)置為最低，并將其他進(jìn)程動(dòng)態(tài)優(yōu)先級(jí)提高，以使得每個(gè)進(jìn)程都有機(jī)會(huì)運(yùn)行。進(jìn)程的優(yōu)先級(jí)與運(yùn)行時(shí)間由隨機(jī)數(shù)產(chǎn)生。Y已達(dá)到未達(dá)到N開 始初始化PCB，輸入進(jìn)程信息各進(jìn)程按優(yōu)先數(shù)從高到低排列就緒隊(duì)列空？結(jié) 束就緒隊(duì)列首進(jìn)程投入運(yùn)行時(shí)間片到，運(yùn)行進(jìn)程已占用CPU時(shí)間1運(yùn)行進(jìn)程已占用CPU時(shí)間達(dá)到所需的運(yùn)行時(shí)間？進(jìn)程完成撤銷該進(jìn)程使運(yùn)行進(jìn)程的優(yōu)先數(shù)減1把運(yùn)行進(jìn)程插入到就緒隊(duì)列實(shí)驗(yàn)二 請(qǐng)求頁式存儲(chǔ)管理中常用頁面置換算法

6、模擬【開發(fā)語言及實(shí)現(xiàn)平臺(tái)或?qū)嶒?yàn)環(huán)境】C+/C#/CfreeTurbo C / Microsoft Visual Studio 6.0 / Microsoft Visual Studio .NET 2010【實(shí)驗(yàn)?zāi)康摹浚?）了解內(nèi)存分頁管理策略（2）掌握調(diào)頁策略（3）掌握一般常用的調(diào)度算法（4）學(xué)會(huì)各種存儲(chǔ)分配算法的實(shí)現(xiàn)方法。（5）了解頁面大小和內(nèi)存實(shí)際容量對(duì)命中率的影響?！緦?shí)驗(yàn)要求】（1）采用頁式分配存儲(chǔ)方案，通過分別計(jì)算不同算法的命中率來比較算法的優(yōu)劣，同時(shí)也考慮頁面大小及內(nèi)存實(shí)際容量對(duì)命中率的影響；（2）實(shí)現(xiàn)OPT 算法 (最優(yōu)置換算法)、LRU 算法 (Least Recently)、

7、FIFO 算法 (First IN First Out)的模擬；（3）使用某種編程語言模擬頁面置換算法?！緦?shí)驗(yàn)原理】分頁存儲(chǔ)管理將一個(gè)進(jìn)程的邏輯地址空間分成若干大小相等的片，稱為頁面或頁。在進(jìn)程運(yùn)行過程中，若其所要訪問的頁面不在內(nèi)存而需把它們調(diào)入內(nèi)存，但內(nèi)存已無空閑空間時(shí)，為了保證該進(jìn)程能正常運(yùn)行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)，送磁盤的對(duì)換區(qū)中。但應(yīng)將哪個(gè)頁面調(diào)出，須根據(jù)算法來確定。通常，把選擇換出頁面的算法稱為頁面置換算法。 一個(gè)好的頁面置換算法，應(yīng)具有較低的頁面更換頻率。從理論上講，應(yīng)將那些以后不再會(huì)訪問的頁面換出，或?qū)⒛切┰谳^長時(shí)間內(nèi)不會(huì)再訪問的頁面調(diào)出。一、最佳置換算法OPT(O

8、ptimal)它是由Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰頁面，將是以后永不使用的或許是在最長(未來)時(shí)間內(nèi)不再被訪問的頁面。采用最佳置換算法，通?？杀ＷC獲得最低的缺頁率。但由于人目前還無法預(yù)知一個(gè)進(jìn)程在內(nèi)存的若干個(gè)頁面中，哪一個(gè)頁面是未來最長時(shí)間內(nèi)不再被訪問的，因而該算法是無法實(shí)現(xiàn)的，但是可以利用此算法來評(píng)價(jià)其它算法。如果編寫程序模擬該算法，可以提前設(shè)定頁面訪問次序，獲知某個(gè)頁面是否在未來不再被訪問。 二、先進(jìn)先出(FIFO)頁面置換算法 這是最早出現(xiàn)的置換算法。該算法總是淘汰最先進(jìn)入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時(shí)間最久的頁面予以淘汰。該算法實(shí)現(xiàn)簡(jiǎn)單只需把一個(gè)進(jìn)程

9、已調(diào)入內(nèi)存的頁面，按先后次序鏈接成一個(gè)隊(duì)列，并設(shè)置一個(gè)指針，稱為替換指針，使它總是指向最老的頁面。三、最近最久未使用置換算法 1、LRU(Least Recently Used)置換算法的描述FIFO置換算法性能之所以較差，是因?yàn)樗罁?jù)的條件是各個(gè)頁面調(diào)入內(nèi)存的時(shí)間，而頁面調(diào)入的先后并不能反映頁面的使用情況。最近最久未使用（LRU）置換算法，是根據(jù)頁面調(diào)入內(nèi)存后的使用情況進(jìn)行決策的。由于無法預(yù)測(cè)各頁面將來的使用情況，只能利用“最近的過去”作為“最近的將來”的近似，因此，LRU置換算法是選擇最近最久未使用的頁面予以淘汰。該算法賦予每個(gè)頁面一個(gè)訪問字段，用來記錄一個(gè)頁面自上次被訪問以來所經(jīng)歷的時(shí)

10、間t,，當(dāng)須淘汰一個(gè)頁面時(shí)，選擇現(xiàn)有頁面中其t值最大的，即最近最久未使用的頁面予以淘汰。 2、LRU置換算法的硬件支持 LRU置換算法雖然是一種比較好的算法，但要求系統(tǒng)有較多的支持硬件。為了了解一個(gè)進(jìn)程在內(nèi)存中的各個(gè)頁面各有多少時(shí)間未被進(jìn)程訪問，以及如何快速地知道哪一頁是最近最久未使用的頁面，須有以下兩類硬件之一的支持： 1）寄存器 為了記錄某個(gè)進(jìn)程在內(nèi)存中各頁的使用情況，須為每個(gè)在內(nèi)存中的頁面配置一個(gè)移位寄存器，可表示為 R=Rn-1Rn-2Rn-3R2R1R0 當(dāng)進(jìn)程訪問某物理塊時(shí)，要將相應(yīng)寄存器的Rn-1位置成1。此時(shí)，定時(shí)信號(hào)將每隔一定時(shí)間(例如100ms)將寄存器右移一位。如果我們把

11、n位寄存器的數(shù)看作是一個(gè)整數(shù)，那么具有最小數(shù)值的寄存器所對(duì)應(yīng)的頁面，就是最近最久未使用的頁面。下圖顯示了某進(jìn)程在內(nèi)存中具有8個(gè)頁面，為每個(gè)內(nèi)存頁面配置一個(gè)8位寄存器時(shí)的LRU訪問情況。這里，把8個(gè)內(nèi)存頁面的序號(hào)分別定為1-8。由圖可以看出，第7個(gè)內(nèi)存頁面的R值最小，當(dāng)發(fā)生缺頁時(shí)首先將它置換出去。 R7 R6 R5 R4 R3 R2 R1 R0 1 0 1 0 1 0 0 1 0 2 1 0 1 0 1 1 0 0 3 0 0 0 0 0 1 0 0 4 0 1 1 0 1 0 1 1 5 1 1 0 1 0 1 1 0 6 0 0 1 0 1 0 1 1 7 0 0 0 0 0 1 1 1 8

12、 0 1 1 0 1 1 0 1 2)棧 可利用一個(gè)特殊的棧來保存當(dāng)前使用的各個(gè)頁面的頁面號(hào)。每當(dāng)進(jìn)程訪問某頁面時(shí)，便將頁面的頁面號(hào)從棧中移出，將它壓入棧頂。因此，棧頂始終是最新被訪問頁面的編號(hào)，而棧底則是最近最久未使用的頁面的頁面號(hào)。實(shí)驗(yàn)三 銀行家算法模擬【開發(fā)語言及實(shí)現(xiàn)平臺(tái)或?qū)嶒?yàn)環(huán)境】C+/C#/cfreeTurbo C / Microsoft Visual Studio 6.0 / Microsoft Visual Studio .NET 2010【實(shí)驗(yàn)?zāi)康摹浚?）理解利用銀行家算法避免死鎖的問題；（2）在了解和掌握銀行家算法的基礎(chǔ)上，編制銀行家算法通用程序，將調(diào)試結(jié)果顯示在計(jì)算機(jī)屏幕上

13、，并檢測(cè)機(jī)算和筆算的一致性。（3）理解和掌握安全序列、安全性算法【實(shí)驗(yàn)要求】（1）了解和理解死鎖；（2）理解利用銀行家算法避免死鎖的原理；（3）使用某種編程語言模擬該算法?！緦?shí)驗(yàn)原理】一、安全狀態(tài)指系統(tǒng)能按照某種順序如(稱為序列為安全序列)，為每個(gè)進(jìn)程分配所需的資源，直至最大需求，使得每個(gè)進(jìn)程都能順利完成。 二、銀行家算法假設(shè)在進(jìn)程并發(fā)執(zhí)行時(shí)，進(jìn)程i提出請(qǐng)求j類資源k個(gè)后，表示為Requestij=k。系統(tǒng)按下述步驟進(jìn)行安全檢查：（1）如果RequestiNeedi則繼續(xù)以下檢查，否則顯示需求申請(qǐng)超出最大需求值的錯(cuò)誤。（2）如果RequestiAvailable則繼續(xù)以下檢查，否則顯示系統(tǒng)無足

14、夠資源，Pi阻塞等待。（3）系統(tǒng)試探著把資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值： Availablej=Availablej-Requestij; Allocationi,j=Allocationi,j+Requestij; Needi,j=Needi,j-Requestij;（4）系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程Pi，以完成本次分配；否則， 將本次的試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進(jìn)程Pi等待。三、安全性算法（1）設(shè)置兩個(gè)向量： 工作向量Work: 它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，它含有m個(gè)元素，在

15、執(zhí)行安全算法開始時(shí)，Work=Available; Finish: 它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開始時(shí)先做Finishi=false; 當(dāng)有足夠資源分配給進(jìn)程時(shí)， 再令Finishi=true。（2）從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程： Finishi=false; Needi,jWorkj； 若找到， 執(zhí)行步驟(3)， 否則，執(zhí)行步驟(4)。（3）當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行： Workj=Worki+Allocationi,j; Finishi=true; go to step 2; （4）如果所有進(jìn)程的Finishi=true都滿足， 則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)?！緦?shí)驗(yàn)步驟】參考實(shí)驗(yàn)步驟如下：（1）參考下圖流程編寫安全性算法。Y所有finish都為true？輸出安全序列NYN存在Fini