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

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