《華北電力大學(xué)操作系統(tǒng)實驗報告.doc》由會員分享，可在線閱讀，更多相關(guān)《華北電力大學(xué)操作系統(tǒng)實驗報告.doc（17頁珍藏版）》請在裝配圖網(wǎng)上搜索。

華北電力大學(xué)科技學(xué)院 實 驗 報 告 | | 實驗名稱 作業(yè)、進程調(diào)度、銀行家、頁面置換算法 課程名稱 計算機操作系統(tǒng)實驗 | | 專業(yè)班級： 學(xué)生姓名： 學(xué) 號： 成 績： 指導(dǎo)教師： 實驗日期： 實驗一 進程調(diào)度實驗 一、實驗?zāi)康? 通過通過實驗使學(xué)生更好地掌握操作系統(tǒng)的基本概念、基本原理、及基本功能。特別是進程的概念、進程控制塊的概念以及進程的三種基本狀態(tài)等概念。培養(yǎng)學(xué)生程序設(shè)計的方法和技巧，提高學(xué)生編制清晰、合理、可讀性好的系統(tǒng)程序的能力，加深對操作系統(tǒng)課程的理解，拓寬學(xué)生的知識領(lǐng)域，鍛煉學(xué)生的實踐技能。 二、實驗要求 本實驗?zāi)M單處理器系統(tǒng)的進程調(diào)度，加深對進程的概念及進程調(diào)度算法的理解。用某種語言編寫和調(diào)試一個進程調(diào)度的算法程序，有一些簡單的界面，能夠運行，仿真操作系統(tǒng)中進程調(diào)度的原理和過程。進程調(diào)度要求使用高響應(yīng)比優(yōu)先的動態(tài)優(yōu)先級調(diào)度算法。 三、實驗原理 動態(tài)優(yōu)先權(quán)是指，在創(chuàng)建進程時所賦予的優(yōu)先權(quán)，是可以隨進程的推進或隨其等待時間的增加而改變的，以便獲得更好的調(diào)度性能。例如，我們可以規(guī)定，在就緒隊列中的進程，隨其等待時間的增長，其優(yōu)先權(quán)以速率a提高。若所有的進程都具有相同的優(yōu)先權(quán)初值，則顯然是最先進入就緒隊列的進程，將因其動態(tài)優(yōu)先權(quán)變得最高而優(yōu)先獲得處理機，此即FCFS算法。若所有的就緒進程具有各不相同的優(yōu)先權(quán)初值，那么，對于優(yōu)先權(quán)初值低的進程，在等待了足夠的時間后，其優(yōu)先權(quán)便可能升為最高，從而可以獲得處理機。當(dāng)采用搶占式優(yōu)先權(quán)調(diào)度算法時，如果再規(guī)定當(dāng)前進程的優(yōu)先權(quán)以速率b下降，則可防止一個長作業(yè)長期地壟斷處理機。 高響應(yīng)比優(yōu)先調(diào)度算法是一種動態(tài)優(yōu)先權(quán)調(diào)度算法，其優(yōu)先權(quán)的變化規(guī)律可描述為： 由于等待時間與服務(wù)時間之和，就是系統(tǒng)對該作業(yè)的響應(yīng)時間，故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比RP。據(jù)此，又可表示為 四、實驗所需儀器、設(shè)備、材料 PC機 五、實驗思路 高響應(yīng)比優(yōu)先Rp值定義為：Rp=（已等待時間+要求運行時間）/要求運行時間=1+已等待時間/要求運行時間 高響應(yīng)比優(yōu)先算法實際是FCFS和SJF的一個折衷 分析： (1) 若干作業(yè)同時到達，短作業(yè)先調(diào)入執(zhí)行； (2) 若干作業(yè)要求執(zhí)行時間相同，先到作業(yè)先執(zhí)行 (3) 一般情況，按計算Rp值調(diào)度 六、實驗流程 同時到達 當(dāng)前作業(yè)取較早到達且相應(yīng)比較高的一個 當(dāng)前作業(yè)取較小到達的一個 當(dāng)前作業(yè)取相應(yīng)比較高的一個 返回這一次要執(zhí)行的作業(yè) 實驗二 作業(yè)調(diào)度實驗 一、實驗?zāi)康? 模擬作業(yè)調(diào)度算法，學(xué)習(xí)作業(yè)在操作系統(tǒng)中的調(diào)度過程，加深對作業(yè)管理的理解。特別是作業(yè)調(diào)度的概念、作業(yè)調(diào)度與進程調(diào)度的區(qū)別。培養(yǎng)學(xué)生程序設(shè)計的方法和技巧，提高學(xué)生編制清晰、合理、可讀性好的系統(tǒng)程序的能力，加深對操作系統(tǒng)課程的理解，拓寬學(xué)生的知識領(lǐng)域，鍛煉學(xué)生的實踐技能。 二、實驗要求 本實驗?zāi)M單處理器系統(tǒng)的作業(yè)調(diào)度，加深對作業(yè)調(diào)度算法的理解。用某種語言編寫和調(diào)試一個作業(yè)調(diào)度的算法程序，有一些簡單的界面，能夠運行，仿真操作系統(tǒng)中作業(yè)調(diào)度的原理和過程。 1、在后備作業(yè)隊列中輸入5道作業(yè)各自需要的時間及存儲空間。數(shù)據(jù)輸入格式如下： 作業(yè)編號 作業(yè)名稱 提交時間 運行時間 存儲空間 開始時間 完成時間 等待時間 1 JA 02：40 20 30 2 JB 02：50 30 15 3 JC 02：55 10 90 4 JD 03：00 24 10 5 JE 03：05 6 60 2、 按先來先服務(wù)（FCFS）的原則進行調(diào)度，輸出作業(yè)調(diào)度的順序及各自的等待時間。 3、 按最短作業(yè)優(yōu)先（SJF）的原則進行調(diào)度，輸出作業(yè)調(diào)度的順序及各自的等待時間。 4、 按最小作業(yè)（存儲空間）優(yōu)先的原則進行調(diào)度，輸出作業(yè)調(diào)度順序及各自的等待時間。 5．建立3個子函數(shù)對應(yīng)3種算法，在主函數(shù)中調(diào)用它們并按格式輸出相關(guān)信息； 6．按調(diào)度順序輸出作業(yè)，輸出格式為： 作業(yè)編號、作業(yè)名、提交時間、運行時間、存儲空間、等待時間 三、實驗原理 作業(yè)調(diào)度算法和進程調(diào)度算法。其中作業(yè)調(diào)度算法主要有先來先服務(wù)法FCFS、短作業(yè)優(yōu)先法SJF、最高響應(yīng)比優(yōu)先法HRN、定時輪轉(zhuǎn)法和優(yōu)先數(shù)法。在進程調(diào)度算法中主要介紹了先來先服務(wù)法FCFS、輪轉(zhuǎn)法RR、多級反饋輪轉(zhuǎn)法和優(yōu)先數(shù)法。 需要指出的是：（1）在作業(yè)調(diào)度和進程調(diào)度中同時出現(xiàn)的算法，如FCFS、RR、優(yōu)先數(shù)法，其使用原理是基本相同的；（2）作業(yè)調(diào)度算法和進程調(diào)度算法應(yīng)嚴(yán)格與存儲管理中的“請求淘汰換頁算法”相區(qū)別，注意不要混淆。 實驗提示 1、 根據(jù)作業(yè)輸入數(shù)據(jù)，定義JCB結(jié)構(gòu)； struct JCB{ char JobNum[2]; char JobName[8]; … }; 2、 定義數(shù)據(jù)結(jié)構(gòu)裝載后備作業(yè) JCB JobArray[MaxNumber]; 3、 三種調(diào)度算法的設(shè)計 4、 C++語言描述順序 建立文件：jcb.h；其中存放： 最大作業(yè)數(shù)； 定義數(shù)據(jù)結(jié)構(gòu)JCB； 三個作業(yè)調(diào)度函數(shù)； 建立主函數(shù)，其中包含： #include #include”jcb.h” void mian() { JCB jobArray[MaxNumber]; 數(shù)據(jù)輸入； 調(diào)用三種算法并輸出調(diào)度結(jié)果； } 四、實驗儀器 PC機 五、實驗思路 作業(yè)調(diào)度的實現(xiàn)主要考慮兩個方面：第一，如何將系統(tǒng)中的作業(yè)組織起來；另一個是如何進行作業(yè)調(diào)度。 1） 設(shè)計作業(yè)隊列的數(shù)據(jù)結(jié)構(gòu) 2） 作業(yè)調(diào)度 a) 先來先服務(wù)算法（FCFS） b) 短作業(yè)優(yōu)先算法（SJF） c) 最小作業(yè)優(yōu)先算法 六、實驗流程 實驗三 銀行家算法實驗 一、實驗?zāi)康? 熟悉銀行家算法，理解系統(tǒng)產(chǎn)生死鎖的原因及避免死鎖的方法,加深記意。 二、實驗要求 用高級語言編寫和調(diào)試一個描述銀行家算法的程序。 設(shè)計五個進程{P0，P1，P2，P3，P4}共享三類資源{A，B，C}的系統(tǒng)，{A，B，C}的資源數(shù)量分別為10，5，7。進程可動態(tài)地申請資源和釋放資源，系統(tǒng)按各進程的申請動態(tài)地分配資源。要求程序具有顯示和打印各進程的某一時刻的資源分配表和安全序列；顯示和打印各進程依次要求申請的資源號以及為某進程分配資源后的有關(guān)資源數(shù)據(jù)。 三、實驗原理 利用銀行家算法避免死鎖 1、銀行家算法中的數(shù)據(jù)結(jié)構(gòu) （1）可利用資源向量Available （2）最大需求規(guī)陣Max （3）分配矩陣Allocation （4）需求矩陣Need 2、銀行家算法 （1）如果Requesti＜或=Need,則轉(zhuǎn)向步驟2；否則，認(rèn)為出錯，因為它所需要的資源數(shù)已超過它所宣布的最大值。 （2）如果Request＜或=Available,則轉(zhuǎn)向步驟（3）；否則，表示系統(tǒng)中尚無足夠的資源，P1必須等待。 （3）系統(tǒng)試探把要求的資源分配給進程Pi,并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值： Available:=Available-Requesti; Allocation:=Allocationi+Request; Needi:=Needi-request; (4)系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。 3、安全性算法 系統(tǒng)所執(zhí)行的安全性算法可描述如下： （1）設(shè)置兩個向量 ①工作向量Work。它表示系統(tǒng)可提供進程繼續(xù)運行所需要的各類資源數(shù)目，它含有m個元素，執(zhí)行安全算法開始時，Work:=Allocation; ②Finish。它表示系統(tǒng)是否有足夠的資源分配給進程，使之運行完成，開始時先做Finish[i]:=false;當(dāng)有足夠資源分配給進程時，令Finish[i]:=true。 （2）從進程集合中找到一個能滿足下述條件的進程： ①Finish[i]:=false ②NeedAvailable(2,3,0)，讓P4等待。 （4） P0請求資源 P0發(fā)出請求向量Request0(0,2,0),系統(tǒng)按銀行家算法進行檢查： （1）Request0(o,2,0)<或=Need0(7,4,3)); （5）進行安全性檢查 可用資源Available{2,1,0}已不能滿足任何進程的需要，故系統(tǒng)進入不安全狀態(tài)，此時系統(tǒng)不分配資源。 如果在銀行家算法中，把P0發(fā)出的請求向量改為Request(0,1,0),系統(tǒng)是否能將資源分配給它，請讀者考慮 四、實驗所需儀器、設(shè)備、材料 PC機 五、實驗思路 銀行家算法的基本思想是分配資源之前, 判斷系統(tǒng)是否是安全的; 若是, 才分配。它是最具有代表性的避免死鎖的算法。 設(shè)進程cusneed 提出請求REQUEST [i] ，則銀行家算法按如下規(guī)則進行判斷。 (1) 如果REQUEST [cusneed] [i]<= NEED[cusneed][i] ，則轉(zhuǎn)(2) ；否則，出錯。 (2) 如果REQUEST [cusneed] [i]<= AVAILABLE[cusneed][i] ，則轉(zhuǎn)(3) ；否則，出錯。 (3) 系統(tǒng)試探分配資源，，進 (4) 系統(tǒng)執(zhí)行安全性檢查，如安全，則分配成立；否則試探險性分配作廢，系統(tǒng)恢復(fù) 原狀程等待 安全性檢查算法 (1) 設(shè)置兩個工作向量Work=AVAILABLE;FINISH (2) 從進程集合中找到一個滿足下述條件的進程， FINISH==false; NEED<=Work; 如找到，執(zhí)行(3) ；否則，執(zhí)行(4) (3) 設(shè)進程獲得資源，可順利執(zhí)行，直至完成，從而釋放資源。 Work+=ALLOCATION; Finish=true; (4) 如所有的進程Finish= true ，則表示安全；否則系統(tǒng)不安全 六、實驗流程 實驗四 存儲器管理實驗 一、實驗?zāi)康? 存儲器管理的主要功能是，合理地分配內(nèi)存空間，數(shù)據(jù)存儲和查詢。其中，請求頁式存儲管理是一種具有虛擬空間技術(shù)的存儲器管理系統(tǒng)。 本實驗的目的是，設(shè)計請求頁式存儲管理中的頁面置換算法，加深了解虛擬存儲技術(shù)的特點，掌握各種頁面置換的算法。 二、實驗要求 （１）通過隨機數(shù)產(chǎn)生一個指令序列，共３２０條指令。指令的地址按下述原則生成： ① ５０％的指令是順序執(zhí)行的。 ② ２５％的指令均勻分布在低地址部分。 ③ ２５％的指令均勻分布在高地址部分。 具體實施的方法是： ①　在［０，３１９］的指令地址之間隨機產(chǎn)生一個起點m； ②　順序執(zhí)行一條指令，即執(zhí)行m＋１處的執(zhí)行； ③　在地址［０，m＋１］中隨機選取一條指令執(zhí)行，該指令的地址為m１； ④　順序執(zhí)行一條指令，即執(zhí)行m1＋１處的執(zhí)行； ⑤　在地址［m1＋2,319］中隨機選取一條指令執(zhí)行； ⑥　重復(fù)上述步驟直到執(zhí)行了３２０條指令為止。 （２）將指令序列改變?yōu)轫摰刂妨?，并假設(shè)： ① 頁面尺寸為１Ｋ。 ② 用戶的內(nèi)存容量為４頁到３２頁。 ③ 用戶的虛存容量為３２Ｋ。 在用戶虛存中，按每Ｋ存放１０條指令來排列虛存地址，即３２０條指令在虛存放方式為： 第０條～第９條為０號頁（對應(yīng)的虛存地址為［０，９］）。 第１０條～第１９條為１號頁（對應(yīng)的虛存地址為［１０，１９］）。 …　　…　…　　… 第3１０條～第3１９條為3１號頁（對應(yīng)的虛存地址為［3１０，3１９］）。 按上述方式，用戶指令可組成32頁。 （3）計算并輸出下述各種算法在不同內(nèi)存容量下的命中率。 ① 先進先出算法（FIFO）。 ② 最近最少使用算法（LRU）。 ③ 最佳淘汰算法。 ④ 最少訪問頁面算法（LFR）。 其中，命中率為： 命中率=(1+缺頁次數(shù))/頁地址流長度 本實驗中，頁的地址流長度為320，頁面失效次數(shù)為每次訪問響應(yīng)指令時，該指令對應(yīng)的頁面不在內(nèi)存中的次數(shù)。 3．隨機數(shù)的產(chǎn)生方法 在VC中設(shè)計到隨機數(shù)有兩個函數(shù)srand() and rand()。srand() 的作用是是一個種子，提供每次獲得隨機數(shù)的基數(shù)而已，rand()根據(jù)種子而產(chǎn)生隨機數(shù)。 注意 1：srand() 里的值必須是動態(tài)變化的，否則得到的隨機數(shù)就是一個固定數(shù) 2：如果我們想得到一個 0-60的隨機數(shù)那么可以寫成 int i; srand(GetTickCount()); i=rand()%60; 三、實驗原理 1、分頁請求系統(tǒng) 為了能實現(xiàn)請求調(diào)頁和置換功能，系統(tǒng)必須提供必要的硬件支持，其中，最重要的是： （1）請求分頁的頁表機制。它是在分頁的頁表機制上增加若干個項而形成的，作為請求分頁的數(shù)據(jù)結(jié)構(gòu)； （2）缺頁中斷機構(gòu)。每當(dāng)用戶程序要訪問的頁面尚未調(diào)入內(nèi)存時，便產(chǎn)生一缺頁中斷，以請求OS將所缺的頁面調(diào)入內(nèi)存； （3）地址變換機構(gòu)。它同樣是在分頁的地址變換機構(gòu)的基礎(chǔ)上發(fā)展形成的。 為了實現(xiàn)請求調(diào)頁還須得到OS的支持，在實現(xiàn)請求調(diào)頁功能時，石油OS將所需的頁從外存調(diào)入內(nèi)存；在實現(xiàn)置換功能時，也是由OS將內(nèi)存的某些頁調(diào)至外存。 2、頁面置換算法 一、最佳（Optimal）置換算法 采用最佳置換算法可保證獲得最低的缺頁率。但由于人們目前還無法預(yù)知一個進程在內(nèi)存的若干個頁面中，哪一個頁面是未來最長時間內(nèi)不在被訪問的，因而該算法也是無法實現(xiàn)的，但是可利用該算法去評價其它算法。圖6-3示出了利用最佳置換算法時的置換圖。由圖可看出，采用最佳置換算法，只發(fā)生了6次頁面置換。 二、先進先出頁面置換算法 該算法總是淘汰最先進入內(nèi)存的頁面，即選擇在內(nèi)存中的駐留時間最久的頁面予以淘汰。該算法實現(xiàn)簡單，只需把一個進程已調(diào)入內(nèi)存的頁面，按先后次序鏈接成一個隊列，并設(shè)置一個指針，稱為替換指針，使它總是指向最老頁面。但該算法與進程實際運行的規(guī)律不相適應(yīng)，因為在進程中，有些頁面經(jīng)常被訪問，含有全局變量、常用函數(shù)、例程等的頁面，F(xiàn)IFO置換算法并不能保證這些頁面不被淘汰。 三、最近最久未使用LRU置換算法 1、LRU（Least Recently Used）算法的描述 FIFO置換算法之所以性能較差，是因為它所依據(jù)的條件是各個頁面調(diào)入內(nèi)存的時間，而頁面調(diào)入的先后并不能反映頁面的使用情況。而最近最久未使用（LRU）的頁面置換算法，，則是根據(jù)頁面調(diào)入內(nèi)存后的使用情況。由于無法預(yù)測各頁面將來的使用情況，只能利用“最近的過去”作為“最近的將來”的近似。因此，LRU置換算法是選擇最近最久未使用的頁面予以淘汰。 2、LRU算法的硬件支持 把LRU算法作為頁面置換算法是比較好的，它對于各種類型的程序都能適用，但實現(xiàn)起來有相當(dāng)大的難度，因為它要求系統(tǒng)具有較多的支持硬件。所要解決的問題有： 1.一個進程在內(nèi)存中的各個頁面各有多久時間未被進程訪問； 2.如何快速地知道哪一頁最近最久未使用的頁面。為此，須利用以下兩類支持硬件： （1）寄存器 用于記錄某進程在內(nèi)存中各頁的使用情況。 實頁/R 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 O 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 0 1 1 0 1 1 0 1 （2）棧 可利用一個特殊的棧來保存當(dāng)前使用的各個頁面的頁面號。每當(dāng)進程訪問某頁面時，便將該頁面的頁面號從棧中移出，將它壓入棧頂。 四、Clock 置換算法 1、簡單的Clock置換算法 利用Clock算法時，只須為每頁設(shè)置一位訪問位，在將內(nèi)存中的所有頁面都通過鏈接指針鏈成一個循環(huán)隊列。當(dāng)某頁被訪問時，其訪問位被置1。置換算法在選擇一頁淘汰時，只須檢查其訪問位。 2、改進型Clock置換算法 在將一個頁面換出時，如果該頁已被修改過，便須將它重新寫到磁盤上；但如果該頁未被修改過，則不必將它拷回磁盤。同時滿足兩條件的頁面作為手癬淘汰的頁。由訪問位A和修改位M可以組合成下面四種類型的頁面： 1 類（A=0，M=0）。表示該頁最近既未被訪問、又未被修改，是最佳淘汰頁。 2 類（A=0，M=1）。表示該頁最近未被訪問，但已被修改，并不是很好的淘汰頁。 3 類（A=1，M=0）。最近已被訪問，但未被修改，該頁有可能再被訪問。 4 類（A=1，M=1）。最近已被訪問且被修改，該頁有可能再被訪問。 在內(nèi)存中的每個頁必定是這四類頁面之一，在進行頁面置換時，可采用與簡單Clock算法相類似的算法，其差別在于須同時檢查訪問位和修改位，以確定該頁是四類頁面中的那一種。此算法稱為改進型Clock算法。其執(zhí)行過程可分成以下三步： （1）從指針?biāo)甘镜漠?dāng)前位置開始，掃描循環(huán)隊列，尋找A=0且M=0的第一類頁面，將所遇到的第一個頁面作為所選中的淘汰頁。在第一次掃描期間不改變訪問位A。 （2）如果第一步失敗，即查找一周后未遇到第一類頁面，則開始第二輪掃描，尋找A=0且M=1的第二類頁面，將所遇到的第一個這類頁面作為淘汰頁。在第二輪掃描期間，將所有經(jīng)過的頁面的訪問位置0。 （3）如果第二步也失敗，即未找到第二類頁面，則將指針返回到開始的位置，并將所有的訪問位復(fù)0。然后，重復(fù)第一步，如果仍失敗，必要時在重復(fù)第二步，此時就一定能夠找到被淘汰的頁。 五、其它置換算法 1、最少使用（Least Frequently Used）置換算法 在采用該算法時，應(yīng)為在內(nèi)存中的每個頁面設(shè)置一移位寄存器，用來記錄該頁面被訪問的頻率，該置換算法選擇在最近時期使用最少的頁面作為淘汰頁。 2、頁面緩沖算法（Page Buffering Algorithm） 雖然LRU和Clock置換算法都比FIFO算法好，但它們都需要一定的硬件支持，置換一個已修改的頁的開銷要大。而頁面緩沖算法則既改善分頁系統(tǒng)的性能，又可采用一種較簡單的置換策略。 六、請求分頁系統(tǒng)的性能分析 1、缺頁率對有效訪問的時間的影響 缺頁時須先調(diào)入該頁的情況時，有效訪問時間表示為：有效訪問時間=（1-p） ma+p 缺頁中斷時間。 2、缺頁中斷時間的組成 （1）缺頁中斷時間服務(wù)時間； （2）將缺頁中斷讀入的時間； （3）進程重新執(zhí)行時間。 由于CUP速度很快，所以其中地（1）和（3）兩部分可以不超過1ms;而將一磁盤塊讀入內(nèi)存的時間，則包括尋道時間、旋轉(zhuǎn)時間和數(shù)據(jù)傳送時間三部分，大體上是24ms。由此可得知缺頁中斷時間約為25ms。此處尚未考慮到進程可能因排隊等待所花費的時間。將上述數(shù)據(jù)代入到工集 有效訪問時間 四、實驗儀器 PC機 五、實驗思路 該試驗主要涉及到請求分頁的管理的頁面置換算法 設(shè)計最佳（Optimal）置換算法 先進先出頁面置換算法 最近最久未使用LRU置換算法 Clock 置換算法 對缺頁次數(shù)，缺頁率的計算 六、實驗流程 實驗心得：通過本次實驗了解并知道了了進程調(diào)度及銀行家算法的實現(xiàn)過程，實驗過程中遇到很多問題非常考驗自己編程能力，要使自己能進一步提高必須進一步學(xué)習(xí)經(jīng)典編程實例涉獵更加廣泛彌補自己不足之處。