1、燕山大學(xué)課程設(shè)計(jì)說明書課程設(shè)計(jì)名稱：操作系統(tǒng)OS 題目：頁(yè)式存儲(chǔ)管理中頁(yè)面置換（淘汰）的模擬程序 班級(jí)：計(jì)算機(jī)應(yīng)用二班開發(fā)小組名稱：CAMPUS課題負(fù)責(zé)人： 課題組成員：姓名 學(xué)號(hào) 班級(jí) 自評(píng)成績(jī) 課題開發(fā)日期：2011-1-10至2011-1-14一概述1目的通過分析、設(shè)計(jì)和實(shí)現(xiàn)頁(yè)式虛擬存儲(chǔ)管理缺頁(yè)中斷的模擬系統(tǒng)，熟悉和掌握請(qǐng)求分頁(yè)式存儲(chǔ)管理的實(shí)現(xiàn)過程，重點(diǎn)掌握當(dāng)請(qǐng)求頁(yè)面不在內(nèi)存而內(nèi)存塊已經(jīng)全部被占用時(shí)的替換算法，熟悉常見替換算法的原理和實(shí)現(xiàn)過程，并利用替換算法的評(píng)價(jià)指標(biāo)缺頁(yè)次數(shù)和缺頁(yè)率，來對(duì)各種替換算法進(jìn)行評(píng)價(jià)比較。2.主要完成的任務(wù)自行輸入實(shí)際頁(yè)數(shù)、內(nèi)存可用頁(yè)面數(shù)、存取內(nèi)存時(shí)間、存取快表

2、時(shí)間及缺頁(yè)中斷時(shí)間，然后由用戶隨機(jī)輸入各頁(yè)面號(hào)，模擬系統(tǒng)自動(dòng)運(yùn)行出FIFO、LRU、OPT、LFU四種算法的缺頁(yè)次數(shù)、缺頁(yè)率、命中率、總存取時(shí)間、存取平均時(shí)間等結(jié)果。 3 使用的開發(fā)工具（1）使用系統(tǒng)：Windows7（2）使用語(yǔ)言：C+（3）開發(fā)工具：Visual C+ 6.04 解決的主要問題設(shè)計(jì)的結(jié)果程序能實(shí)現(xiàn)FIFO、OPT、LRU、LFU算法模擬頁(yè)式存儲(chǔ)管理缺頁(yè)中斷，主要能夠處理以下的問題：(1) 用戶能夠輸入給作業(yè)分配的內(nèi)存塊數(shù)；(2) 用戶能夠輸入給定的頁(yè)面，并計(jì)算發(fā)生缺頁(yè)的次數(shù)以及缺頁(yè)率；(3) 程序可由用戶輸入頁(yè)面序列；(4) 系統(tǒng)自動(dòng)計(jì)算總存取時(shí)間及平均存取時(shí)間。二 使用的

3、基本概念和原理1.概念FIFO 即先進(jìn)先出頁(yè)面置換算法，該算法總是淘汰最先進(jìn)入內(nèi)存的頁(yè)面，即選擇在內(nèi)存中駐留時(shí)間最久的頁(yè)面予以淘汰。LRU 即最近最久未使用頁(yè)面置換算法，該算法選擇最近最久未使用的頁(yè)面予以淘汰。OPT 即最佳值換算法，其選擇淘汰的頁(yè)面是在最長(zhǎng)時(shí)間內(nèi)不再被訪問的頁(yè)面。LFU 即最近使用最少頁(yè)面置換算法，其淘汰的頁(yè)面是最近一段時(shí)間內(nèi)使用最少的頁(yè)面。缺頁(yè)中斷 存取頁(yè)面時(shí)頁(yè)面不在內(nèi)存中需從外存調(diào)入的現(xiàn)象。缺頁(yè)次數(shù) 即在存取頁(yè)面過程中發(fā)生缺頁(yè)中斷的次數(shù)。命中率 在存取過程中頁(yè)面在內(nèi)存中次數(shù)占頁(yè)面存取總次數(shù)的百分比。總存取時(shí)間 即存取所有頁(yè)面所消耗的總時(shí)間。存取平均時(shí)間 即存取一次頁(yè)面平均

4、所用的時(shí)間。2.原理頁(yè)式存儲(chǔ)管理把內(nèi)存分割成大小相等位置固定的若干區(qū)域，叫內(nèi)存頁(yè)面，內(nèi)存的分配以“頁(yè)”為單位，一個(gè)程序可以占用不連續(xù)的頁(yè)面，邏輯頁(yè)面的大小和內(nèi)存頁(yè)面的大小相同，內(nèi)外存的交換也以頁(yè)為單位進(jìn)行，頁(yè)面交換時(shí)，先查詢快表，若快表中找不到所需頁(yè)面再去查詢頁(yè)表，若頁(yè)表中仍未找到說明發(fā)生了缺頁(yè)中斷，需先將所需頁(yè)面調(diào)入內(nèi)存再進(jìn)行存取。三總體設(shè)計(jì)通過對(duì)所解決的問題的實(shí)質(zhì)的分析，即使用不同的算法對(duì)頁(yè)表進(jìn)行查詢，分查到和查不到兩種情況進(jìn)行處理，主要是采用面向過程的技術(shù)路線，把解決問題的方法進(jìn)行分步處理。軟件主要采用函數(shù)調(diào)用的總體結(jié)構(gòu)，把各種替換算法分別用函數(shù)實(shí)現(xiàn)，在主函數(shù)中進(jìn)行調(diào)用，各函數(shù)之間相互獨(dú)

5、立。整個(gè)程序的主要流程就是先輸入問題中需要用到的各種數(shù)據(jù)，如頁(yè)面序列，實(shí)際頁(yè)數(shù)，內(nèi)存中的頁(yè)數(shù)和存取時(shí)間等等。然后我們可以選擇相應(yīng)的替換算法進(jìn)行分析替換，得到相應(yīng)的存取時(shí)間和缺頁(yè)情況。具體的流程圖如下：圖1請(qǐng)求分頁(yè)流程圖四詳細(xì)設(shè)計(jì) 具體的設(shè)計(jì)使用的函數(shù)除了主函數(shù)中的輸入輸出函數(shù)外，大部分使用函數(shù)調(diào)用，所用的函數(shù)主要有四種替換算法函數(shù)FIFO,LRU,OPT,LFU以及所有替換算法中都要用到的查詢函數(shù)Search,LFU中的使用次數(shù)最少函數(shù) Min,OPT中計(jì)算使用距離的函數(shù) Compfu, LRU中的最久未使用時(shí)間函數(shù)Max，各算法使用函數(shù)具體如下： void main()int m=0,t=0

6、,N=0;coutm; Pro *p=new Prom;/p是用來放頁(yè)面的地方 cout可用內(nèi)存頁(yè)面數(shù)N; Pro *page=new ProN;/page是放物理塊的地方char c;int x,y,z;cout請(qǐng)輸入存取內(nèi)存時(shí)間(ns)x;cout請(qǐng)輸入訪問快表時(shí)間(ns)y; cout請(qǐng)輸入缺頁(yè)中斷時(shí)間(ns)z;float n=0;Input(m,N,p,page);/m是頁(yè)面的總長(zhǎng)，N是物理塊的長(zhǎng)度do coutf:FIFO頁(yè)面置換endl;coutl:LRU頁(yè)面置換endl;couto:OPT頁(yè)面置換endl;coutu:LFU頁(yè)面置換endl;cout按其它鍵結(jié)束c;if(c=f

7、)/FIFO頁(yè)面置換FIFO(p,page,m,N,x,y,z); if(c=l)/LRU頁(yè)面置換LRU(p,page,m,N,x,y,z);if(c=o)/OPT頁(yè)面置換OPT(p,page,m,N,x,y,z); if(c=u)/OPT頁(yè)面置換LFU(p,page,m,N,x,y,z); while(c=f|c=l|c=o|c=u); 以上為主函數(shù)的內(nèi)容。下面為所調(diào)用的函數(shù)int Search(int e, Pro *page ,int N) for(int i=0;iN;i+)if(e=pagei.num)return i;return -1;查詢函數(shù)Search的參數(shù)為所要查詢的頁(yè)號(hào)e

8、，快表中的頁(yè)號(hào)page、以及快表中頁(yè)數(shù)N，最后的返回值為所要查詢頁(yè)號(hào)在快表中的位置i或查不到的返回值-1.void FIFO(Pro p ,Pro page ,int m, int N, int x ,int y, int z) int a=0;float n=0; int i=0; int t=0; for(i=0;iN;i+)pagei.num=0;cout頁(yè)面置換情況: endl;for(i=0;i=0) a+=(x+y);continue;else t=t%N;n+;paget.num=pi.num; t+;a+=(3*x+z);cout缺頁(yè)次數(shù)：n 缺頁(yè)率：n/m 命中率：1-n/m

9、 總存取時(shí)間：ans 存取平均時(shí)間：a/mnsendl; FIFO替換算法中使用的參數(shù)有實(shí)際頁(yè)表 p ,快表 page ,實(shí)際頁(yè)數(shù) m, 內(nèi)存可用頁(yè)面數(shù)N,快表存取時(shí)間 x ,內(nèi)存存取時(shí)間y, 缺頁(yè)中斷時(shí)間 z，最后的返回值是缺頁(yè)次數(shù)n，缺頁(yè)率，命中率，總存取時(shí)間以及平均存取時(shí)間。void LRU(Pro p,Pro page,int m,int N,int x,int y,int z) int a=0; float n=0; int i=0; int t=0; for(i=0;iN;i+)pagei.num=0;pagei.time=N+2-i;cout頁(yè)面置換情況: endl; while

10、(i=0)a+=(x+y);paget.time=0; Else n+; t=Max(page,N); paget.num=pi.num; paget.time=0; a+=(3*x+z); for(int j=0;jN;j+)if(j=t)continue;paget.time+; i+; cout缺頁(yè)次數(shù)：n 缺頁(yè)率：n/m 命中率：1-n/m 總存取時(shí)間：ans 存取平均時(shí)間：a/mnsendl; LRU置換算法中的參數(shù)有實(shí)際頁(yè)號(hào) p,快表中的頁(yè)號(hào) page,實(shí)際頁(yè)數(shù) m, 內(nèi)存可用頁(yè)面數(shù) N, 快表存取時(shí)間x, 內(nèi)存存取時(shí)間 y, 缺頁(yè)中斷時(shí)間z。返回值為缺頁(yè)次數(shù)n，缺頁(yè)率，命中率，總

11、存取時(shí)間以及平均存取時(shí)間。int Max(Pro *page,int N) int e=page0.time,i=0;int k=0;while(iN) if(epagei.time) k=i;i+;return k; Max函數(shù)中的參數(shù)有快表中頁(yè)號(hào)page,內(nèi)存可用頁(yè)數(shù)N。返回值是最近最久未使用的頁(yè)面位置k。void OPT(Pro p,Pro page,int m,int N,int x,int y,int z) int a=0; float n=0; int i=0; int t=0; for(i=0;iN;i+) pagei.num=0; while(i=0)i+;else int t

12、emp=0,cn; for(t=0;tN;t+) if(tempCompfu(page,i,t,p,m) temp=Compfu(page,i,t,p,m);cn=t;pagecn=pi;n=n+1;i+;a+=(3*x+z);cout缺頁(yè)次數(shù)：n 缺頁(yè)率：n/m 命中率：1-n/m 總存取時(shí)間：ans 存取平均時(shí)間：a/mnsendl; OPT置換算法中的參數(shù)有實(shí)際頁(yè)號(hào) p,快表中的頁(yè)號(hào) page,實(shí)際頁(yè)數(shù) m, 內(nèi)存可用頁(yè)面數(shù) N, 快表存取時(shí)間x, 內(nèi)存存取時(shí)間 y, 缺頁(yè)中斷時(shí)間z。返回值為缺頁(yè)次數(shù)n，缺頁(yè)率，命中率，總存取時(shí)間以及平均存取時(shí)間。int Compfu(Pro *page

13、,int i,int t,Pro p,int m) int count=0; for(int j=i;jm;j+)if(paget.num=pj.num )break; else count+;return count; Compfu函數(shù)中參數(shù)為快表中頁(yè)號(hào)page,頁(yè)面位置 i,頁(yè)面在快表中位置 t,實(shí)際頁(yè)表 p,實(shí)際頁(yè)數(shù)m，返回值為下次使用的步數(shù)count。void LFU(Pro p,Pro page,int m,int N,int x,int y,int z) int a=0;float n=0;int i=0;int t=0;for(i=0;iN;i+) pagei.num=0;for

14、(i=0;iN;i+)pagei.time=0;cout頁(yè)面置換情況: endl;for(i=0;i=0)a+=(x+y);pagei.time+;continue;/else t=Min(page,N); tpaget.num=pi.num;paget.time=0; n+;a+=(3*x+z);cout缺頁(yè)次數(shù)：n 缺頁(yè)率：n/m 命中率：1-n/m 總存取時(shí)間：ans 存取平均時(shí)間：a/mnsendl; LFU置換算法中的參數(shù)有實(shí)際頁(yè)號(hào) p,快表中的頁(yè)號(hào) page,實(shí)際頁(yè)數(shù) m, 內(nèi)存可用頁(yè)面數(shù) N, 快表存取時(shí)間x, 內(nèi)存存取時(shí)間 y, 缺頁(yè)中斷時(shí)間z。返回值為缺頁(yè)次數(shù)n，缺頁(yè)率，命中

15、率，總存取時(shí)間以及平均存取時(shí)間。int Min(Pro page,int N) int k=0;int min=page0.time;for(int i=0;ipagei.time)k=i;return k; Min函數(shù)使用的參數(shù)為實(shí)際頁(yè)號(hào)page,內(nèi)存可用頁(yè)數(shù)N，返回值為置換位置k。五編碼設(shè)計(jì)1. 開發(fā)環(huán)境的設(shè)置和建立本程序所使用的開發(fā)環(huán)境為Visual C+ 6.0，在Windows7系統(tǒng)中建立一個(gè)Win32 Console Application的工程，然后在工程里建立一個(gè)C+ source file的文件。2. 程序設(shè)計(jì)時(shí)需要注意的問題程序設(shè)計(jì)時(shí)需要注意調(diào)用函數(shù)的嵌套，各種替換算法中替

16、換的位置確認(rèn)，函數(shù)調(diào)用的實(shí)現(xiàn)3. 主要程序的代碼設(shè)計(jì)及注釋；#include #include #include struct Pro int num,time;/num存放具體的內(nèi)容，time在不同算法里面有不同的意義; /它們是物理塊和頁(yè)面的數(shù)據(jù)結(jié)構(gòu)int Input(int m,int N,Pro *p,Pro *page)/完成p數(shù)組和page的初始化工作/p數(shù)組是存放頁(yè)面的空間，m是頁(yè)面的長(zhǎng)度，page是可以使用的物理塊，N是物理塊的大小 coutendl請(qǐng)輸入各頁(yè)面號(hào)endl; int *p1=new intm;for(int j=0;jp1j; for(int i=0;im;i+

17、)pi.num=p1i;pi.time=0;return m;int Search(int e,Pro *page,int N)/算法里面都要用到它，它是找e頁(yè)是否在page物理塊中，N是物理塊的大小for(int i=0;iN;i+)if(e=pagei.num)return i;/如果找到，就返回在物理塊中的位置給Searchreturn -1;/找不到，就返回-1int Max(Pro *page,int N)/LRU算法用到的/找出在page塊中，time最大的值和位置，同時(shí)位置返回，time最大，就代表了最久沒被使用的int e=page0.time,i=0;int k=0;whil

18、e(iN)/找出離現(xiàn)在時(shí)間最長(zhǎng)的頁(yè)面if(epagei.time) k=i;i+;return k; int Compfu(Pro *page,int i,int t,Pro p,int m)/OPT算法用到的，找出如果paget要等于p，并且在pipm這個(gè)區(qū)間內(nèi)，走的次數(shù)，最大的數(shù)int count=0;/count是保存走的步數(shù)for(int j=i;jm;j+)if(paget.num=pj.num )break;/如果相等，跳出循環(huán)else count+;/不等就步數(shù)加1return count; int Min(Pro page,int N)/LFU算法用到的，page是可以使用的物

19、理塊，N是物理塊的大小，找到出現(xiàn)次數(shù)最小的的數(shù)，并把位置返回 int k=0;int min=page0.time;for(int i=0;ipagei.time)k=i;return k;void FIFO(Pro p,Pro page,int m,int N,int x,int y,int z)/p數(shù)組是存放頁(yè)面的空間，m是頁(yè)面的長(zhǎng)度，page是可以使用的物理塊，N是物理塊的大小 int a=0;float n=0;/n用來保存缺頁(yè)的次數(shù)int i=0;/i是循環(huán)變量，它是表示走到頁(yè)面的位置。int t=0;/t是用來表示物理塊走到的位置for(i=0;iN;i+)/初試化頁(yè)面基本情況pa

20、gei.num=0;cout頁(yè)面置換情況: endl;for(i=0;i=0) a+=(x+y);continue;/找到相同的頁(yè)面，就跳到下一次循環(huán)，不做處理。else /在找不到的時(shí)候，通過t=t%N,求出這次來替換物理塊的位置 t=t%N;n+;/缺頁(yè)數(shù)加1paget.num=pi.num; t+;/位置加1a+=(3*x+z);cout缺頁(yè)次數(shù)：n 缺頁(yè)率：n/m 命中率：1-n/m 總存取時(shí)間：ans 存取平均時(shí)間：a/mnsendl; void LFU(Pro p,Pro page,int m,int N,int x,int y,int z)/p數(shù)組是存放頁(yè)面的空間，m是頁(yè)面的長(zhǎng)度

21、，page是可以使用的物理塊，N是物理塊的大小， int a=0;float n=0;int i=0;int t=0;for(i=0;iN;i+)/初始化頁(yè)面基本情況pagei.num=0;for(i=0;iN;i+)pagei.time=0;cout頁(yè)面置換情況: endl;for(i=0;i=0)a+=(x+y);pagei.time+;/找到相同的頁(yè)面，time加1continue;/else /找出使用最少的頁(yè)面進(jìn)行調(diào)換t=Min(page,N);/找到出現(xiàn)次數(shù)最小的的數(shù)，并把位置返回tpaget.num=pi.num;paget.time=0;/該頁(yè)time清零n+;/缺頁(yè)數(shù)加1a+

22、=(3*x+z);cout缺頁(yè)次數(shù)：n 缺頁(yè)率：n/m 命中率：1-n/m 總存取時(shí)間：ans 存取平均時(shí)間：a/mnsendl;void OPT(Pro p,Pro page,int m,int N,int x,int y,int z)/p數(shù)組是存放頁(yè)面的空間，m是頁(yè)面的長(zhǎng)度 int a=0; /page是可以使用的物理塊，N是物理塊的大小 float n=0;/n用來保存缺頁(yè)的次數(shù) int i=0;/i是循環(huán)變量，它是表示走到頁(yè)面的位置。 int t=0; /t是用來表示物理塊走到的位置 for(i=0;iN;i+)/初始化頁(yè)面基本情況pagei.num=0; while(i=0)i+;/

23、如果找到了，就不做處理。else/如果找不到int temp=0,cn;/cn用來保存離后面最遠(yuǎn)的數(shù)for(t=0;tN;t+)/對(duì)物理塊里面的每個(gè)數(shù)進(jìn)行遍歷if(tempCompfu(page,i,t,p,m)/temp用來保存/paget= pipm這個(gè)區(qū)間內(nèi)，走的次數(shù)，最大的數(shù)temp=Compfu(page,i,t,p,m);cn=t;pagecn=pi;/把當(dāng)前的值放要發(fā)生要走最遠(yuǎn)的數(shù)，也就最不可能最近出現(xiàn)的數(shù)n=n+1;/缺頁(yè)數(shù)加1i+;/跳到下一次循環(huán)a+=(3*x+z);cout缺頁(yè)次數(shù)：n 缺頁(yè)率：n/m 命中率：1-n/m 總存取時(shí)間：ans 存取平均時(shí)間：a/mnsend

24、l; void LRU(Pro p,Pro page,int m,int N,int x,int y,int z)/p數(shù)組是存放頁(yè)面的空間，m是頁(yè)面的長(zhǎng)度 int a=0;/page是可以使用的物理塊，N是物理塊的大小 float n=0;/n用來保存缺頁(yè)的次數(shù)int i=0;/i是循環(huán)變量，它是表示走到頁(yè)面的位置。int t=0; /t是用來表示物理塊走到的位置for(i=0;iN;i+)/初始化頁(yè)面基本情況pagei.num=0;pagei.time=N+2-i;cout頁(yè)面置換情況: endl; while(i=0)a+=(x+y);paget.time=0;/如果找到，就要把當(dāng)前的pa

25、get.time次數(shù)清零 else/找不到的時(shí)候，發(fā)生缺頁(yè) n+; /缺頁(yè)數(shù)加1t=Max(page,N);/找出page物理塊里面，最久沒被時(shí)候的數(shù)，同時(shí)把最久沒被時(shí)候的數(shù)在物理塊里的位置傳給t paget.num=pi.num;/最久沒被使用的是被現(xiàn)在的數(shù)代替paget.time=0;/同時(shí)清零a+=(3*x+z); for(int j=0;jN;j+)/把缺頁(yè)以外的數(shù)，把它沒被使用的次數(shù)加1if(j=t)continue;paget.time+; i+;/跳到下一次循環(huán) cout缺頁(yè)次數(shù)：n 缺頁(yè)率：n/m 命中率：1-n/m 總存取時(shí)間：ans 存取平均時(shí)間：a/mnsendl; vo

26、id main()int m=0,t=0,N=0;coutm; Pro *p=new Prom;/p是用來放頁(yè)面的地方 cout可用內(nèi)存頁(yè)面數(shù)N; Pro *page=new ProN;/page是放物理塊的地方char c;int x,y,z;cout請(qǐng)輸入存取內(nèi)存時(shí)間(ns)x;cout請(qǐng)輸入訪問快表時(shí)間(ns)y; cout請(qǐng)輸入缺頁(yè)中斷時(shí)間(ns)z;float n=0;Input(m,N,p,page);/m是頁(yè)面的總長(zhǎng)，N是物理塊的長(zhǎng)度do coutf:FIFO頁(yè)面置換endl;coutl:LRU頁(yè)面置換endl;couto:OPT頁(yè)面置換endl;coutu:LFU頁(yè)面置換end

27、l;cout按其它鍵結(jié)束c;if(c=f)/FIFO頁(yè)面置換FIFO(p,page,m,N,x,y,z); if(c=l)/LRU頁(yè)面置換LRU(p,page,m,N,x,y,z);if(c=o)/OPT頁(yè)面置換OPT(p,page,m,N,x,y,z); if(c=u)/OPT頁(yè)面置換LFU(p,page,m,N,x,y,z); while(c=f|c=l|c=o|c=u); 4. 解決的技術(shù)難點(diǎn)、經(jīng)常犯的錯(cuò)誤。主要技術(shù)難點(diǎn)四種置換算法實(shí)現(xiàn)，經(jīng)常犯的錯(cuò)誤就是算法實(shí)現(xiàn)出現(xiàn)錯(cuò)誤，計(jì)算結(jié)果和實(shí)際結(jié)果不一致，以及函數(shù)調(diào)用出現(xiàn)問題。六 測(cè)試時(shí)出現(xiàn)過的問題及其解決方法主要問題是頁(yè)面置換時(shí)出現(xiàn)問題，程序計(jì)算出來的結(jié)果和實(shí)際結(jié)果不一致，缺頁(yè)次數(shù)計(jì)算出現(xiàn)錯(cuò)誤，后來經(jīng)過堅(jiān)持不懈的調(diào)試修改和分析，成功的解決了這個(gè)計(jì)算錯(cuò)誤的問題。七程序測(cè)試結(jié)果八軟件使用說明基本功能：在頁(yè)式存儲(chǔ)管理方式中實(shí)現(xiàn)四種算法的頁(yè)面置換以及存取時(shí)間，缺頁(yè)次數(shù)，命中率等的輸出。需要運(yùn)行的環(huán)境：Visual C+ 6.0安裝：在Windows7系統(tǒng)中建立一個(gè)Win32 Console Application的工程，然后在工程里建立一個(gè)C+ source f