頁面置換實(shí)習(xí)報(bào)告

1、實(shí)習(xí)報(bào)告-頁面置換算法、設(shè)計(jì)目的：加深對(duì)請(qǐng)求頁式存儲(chǔ)管理實(shí)現(xiàn)原理的理解，掌握頁面置換算法。、設(shè)計(jì)內(nèi)容設(shè)計(jì)一個(gè)進(jìn)程，可以實(shí)現(xiàn)用戶可以為程序指定內(nèi)存塊數(shù)，自由設(shè)置程序的頁面訪 問順序，還可以在 OPT FIFO和LRU算法自由選擇一個(gè)，并能觀看到頁面置換過程。三、開發(fā)環(huán)境windows 環(huán)境，VC6.0 平臺(tái)。四、分析設(shè)計(jì)內(nèi)存空間的分配和回收均以頁調(diào)入內(nèi)存變可運(yùn)行； 還支持請(qǐng)求一實(shí)驗(yàn)原理為提高內(nèi)存利用率，提供了內(nèi)外存進(jìn)程對(duì)換機(jī)制; 為單位進(jìn)行：一個(gè)進(jìn)程只需將其中一部分（段或頁） 調(diào)頁的存儲(chǔ)管理方式。發(fā)現(xiàn)其所在的頁面不在內(nèi)存，就當(dāng)進(jìn)程在進(jìn)行中需要訪問某部分程序和數(shù)據(jù)時(shí)，立即提出請(qǐng)求（向 CPU發(fā)出中

2、斷），由系統(tǒng)將其所需頁面調(diào)入內(nèi)存。這種頁面調(diào)入 方式叫做請(qǐng)求調(diào)頁。當(dāng)CPU接收到缺頁中斷信號(hào)，中斷處理程序先保存現(xiàn)場， 分析中斷原因，轉(zhuǎn)入缺頁中斷處理程序。該程序通過查找頁表，得到該頁所在外存的物理塊號(hào)。如果此時(shí) 內(nèi)存未滿，能容納新頁，則啟動(dòng)磁盤I/O將所缺之頁調(diào)入內(nèi)存，然后修改頁表。如果內(nèi)存已滿，則需按照某種置換算法從內(nèi)存中選出一頁準(zhǔn)備換出，是否重新寫盤由 頁表的修改位決定，然后將缺頁調(diào)入，修改頁表。利用修改后的頁表，去形成所要 訪問數(shù)據(jù)的物理地址，再去訪問內(nèi)存數(shù)據(jù)。整個(gè)頁面的調(diào)入程序?qū)τ脩羰峭该鞯?。下面把我所用到的頁面置換算法：最佳置換算法（OPT）、先進(jìn)先出頁面置換算法（FIFO）、最近

3、最少使用頁面置換算法（LRU）,并對(duì)這些原理進(jìn)行描述：最佳置換算法（OPT）原理：選擇淘汰的頁面，將是以后永不使用的，或者是最長（未來）時(shí)間內(nèi)不再被訪問 的頁面。采用最佳置換算法，通常課保證最低缺頁率。先進(jìn)先出頁面置換算法（FIFO）原理:該算法總是先淘汰最先進(jìn)入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時(shí)間最久的頁面予 以淘汰。最近最少使用頁面置換算法(LRU)原理：由于無法預(yù)測(cè)各頁面將來的使用情況，只能利用“最近的過去”作為“最近的將 來”的近似。選擇最近最久未使用的頁面予以淘汰，該算法賦予每個(gè)頁面一個(gè)訪問 字段，用來記錄一個(gè)頁面自上次唄訪問以來所經(jīng)歷的時(shí)間t，當(dāng)必須淘汰一個(gè)頁面時(shí)，選擇現(xiàn)有頁面中其

4、t最大的，即最近最少使用頁面予以淘汰。二程序結(jié)構(gòu)我的程序分為三部分：第一部分：鍵盤輸入數(shù)據(jù)作為測(cè)試用例用for循環(huán)進(jìn)行數(shù)據(jù)的連續(xù)輸入第二部分：算法的實(shí)現(xiàn)算法的實(shí)現(xiàn)也分為三部分：1. 算法1-最佳置換算法(OPT)(1) .數(shù)據(jù)剛?cè)霔?，物理塊數(shù)都為缺頁數(shù)(2) .超過分配的物理塊數(shù)，如果有與棧內(nèi)的數(shù)據(jù)一致的稱為命中數(shù)據(jù)，并把棧內(nèi)數(shù)據(jù)打印出來：Print(Num)，并用一個(gè)m=1標(biāo)記有命中數(shù)據(jù)(3) 超過分配的物理塊數(shù)，如果沒有與棧內(nèi)的數(shù)據(jù)一致的數(shù)據(jù)，則調(diào)用fin ds pace ()函數(shù)，讓棧內(nèi)的數(shù)與后面的數(shù)進(jìn)行比較，如果有相同的數(shù)就用Pos1j記下他們的標(biāo)號(hào)i(j從0開始)，如果有一個(gè)沒有命中

5、，則把此數(shù)換出去，而如果物理塊都有命中，則比較Pos1j中那個(gè)數(shù)最大，+。把最大的數(shù)換出去，因?yàn)榇藭r(shí)這個(gè)數(shù)是最長(未來)時(shí)間內(nèi)不再被訪問 的頁面，并且缺頁次數(shù)(4) 計(jì)算缺頁率并打印出來2. 算法2-先進(jìn)先出頁面置換算法(FIFO):(1) .數(shù)據(jù)剛?cè)霔?，物理塊數(shù)都為缺頁數(shù)(2) .超過分配的物理塊數(shù)，如果有與棧內(nèi)的數(shù)據(jù)一致的稱為命中數(shù)據(jù)，并把棧內(nèi)數(shù)據(jù)打印出來：Print(Num)，并用一個(gè)m=1標(biāo)記有命中數(shù)據(jù)(3) 超過分配的物理塊數(shù)，如果沒有與棧內(nèi)的數(shù)據(jù)一致的數(shù)據(jù)，則把先進(jìn)棧的+。數(shù)換出去，讓棧內(nèi)的數(shù)從第二數(shù)開始往前移，然后把剛?cè)霔５臄?shù)據(jù)放入 棧尾，打印出來，并且缺頁次數(shù)(4) 計(jì)算缺頁率

6、并打印出來-1 -3. 算法 3-(1).(2).最近最少使用頁面置換算法 (LRU) : 數(shù)據(jù)剛?cè)霔＃锢韷K數(shù)都為缺頁數(shù) 超過分配的物理塊數(shù)，如果有與棧內(nèi)的數(shù)據(jù)一致的稱為命中數(shù)據(jù)，并把棧內(nèi)數(shù)據(jù)打印出來：Print(Num)，并用一個(gè)m=1標(biāo)記有命中數(shù)據(jù)(3) 超過分配的物理塊數(shù)， 如果沒有與棧內(nèi)的數(shù)據(jù)一致的數(shù)據(jù)， 則把先進(jìn)棧的數(shù)換出去，讓棧內(nèi)的數(shù)從第二數(shù)開始往前移，然后把剛?cè)霔５臄?shù)據(jù)放入 棧尾，打印出來，并且缺頁次數(shù)(4) 計(jì)算缺頁率并打印出來+。第三部分 : 程序的運(yùn)行(1) . 輸入進(jìn)程物理塊數(shù)(2) . 輸入進(jìn)程頁面地址數(shù)(3) 輸入進(jìn)程頁面地址流，即測(cè)試的數(shù)據(jù)(4) 把置換的結(jié)果、缺

7、頁次數(shù)和缺頁率打印到屏幕上V三一些全局?jǐn)?shù)據(jù)的設(shè)置：先為物理塊分配空間，然后在根據(jù)用戶需求進(jìn)行輸入物理塊的大小:#define pNum 100/ 全局變量而每種算法都要對(duì)缺頁次數(shù)和缺頁次數(shù)進(jìn)行統(tǒng)計(jì)，為了方便用戶使用和理解，也設(shè) 置一個(gè)全局變量：intqycs=0;/ 缺頁次數(shù)float qyl;/ 缺頁率 進(jìn)程塊賦初值，賦予一個(gè)空間，方便我們輸入空間大小和查看頁面置換的命中率與 缺頁率char pblockpNum;四程序流程圖:- 3 -五.運(yùn)行示例及結(jié)果分析-9 -橫著看棧，用-1標(biāo)記數(shù)據(jù)沒有入棧，此時(shí)表明有四個(gè)物理塊(棧)t | -作者：去胡藝亨;5： 30*0717231悽S輔Ar比-

8、(B運(yùn)出晴送擇尸旦頁配疋可序痛翳或選澤逾岀Hi楸貯:擇那科算注韓請(qǐng)?jiān)枌廸 說1F!岀:一 l-t作者.狂卻主(1(afl、 (H3ee71?E38久I垂弔早往2222113 3 3吐n那:起為？675000： ! ： ：上好備點(diǎn)y蘭-退岀揃入講sa配他物理決數(shù)：4WWftLfeTJLSfeso： 7#選逢產(chǎn)生貝直走問呼貝的方貳(違円惑渤網(wǎng)退出、詢 要迪坯嗎TXjMnJnTruii 41 也 hty tu C4ittiiiu(二色也彎翦輸萍屮窗“ i 1fi斗Pl乩.妲選搔那種異辛卻 =- - -Hl作苦I張薊芒;iH-JB.B. Q銀隹1旅g法-接進(jìn)久未覆用畀怯-la 31選：2F I F 0

9、真法2&右利盟世娥喝 a/t -嗟咋顯屜EE iR曲4務(wù)I 叢向 物址走 旳地面r 配10貢M 號(hào)主E 蘑-7 1 人入吟 輸洞苗10 y gcii隆丄我選薛迪出汕呼送S選擇恥種舁法Y請(qǐng)世萍IP.選0逼出=(1-作者“的壬:CiI 1 C3 :袪算用，星未 1r岀久 5W晟 隹進(jìn)歯 罠鷲也訂HL n U?r 祛W-iz說匹歡數(shù)加 缺;瓦率為O顯75 ft湘互醴無1|亍Jhn1 !fl學(xué)號(hào)：3070717230入嚴(yán)缶 720l 8選扌羊1或選佯0退出你想選擇那種葬袪? ；!1!1i柞寺，張莉蕓 退出學(xué)號(hào)，209 0717238 iiiiiL.= ! ! I i ! I 作若t張莉蕓 學(xué)號(hào)I 30

10、9 0717238!搜盤輛入產(chǎn)生一_=_=_=_=退_出! 3瓦面走冋序碉的方式血擇1或選F剌極出M就A聲分配的抑理塊數(shù)： t入進(jìn)程M面地1數(shù)烝溜過緲匸 錯(cuò)選堡產(chǎn)生匸二二二m 二Eess any key to continue六、心得與體會(huì)在這兩周的計(jì)算機(jī)操作系統(tǒng)實(shí)習(xí)中，我學(xué)到了很多東西。不僅對(duì)LINUX的終端操作的了解加深了很多，不光是懂得指令的操作，而且明白了以前很多模糊的地方，比如對(duì)權(quán)限的訪問那一部分，以前只知道用chmodg+w文件名；chmod o-r文件名這兩條指令修改權(quán)限，卻不知道-rw-rw-rw-是什么意思，通過這次實(shí)習(xí)，我明白了這是多級(jí)訪問權(quán)限的意思，還有一些類似的指令也是

11、一樣。這次老師還要我們看了fork.cp p 的代碼，一開始，LINUX里面的代碼太多了，找不到，后來用搜索的功能才把fork.cpP找到，發(fā)現(xiàn)它在，后來從老師給的資料才知道，fork的功能是復(fù)制進(jìn)程里面的東西，對(duì)LINUX進(jìn)程的創(chuàng)建、內(nèi)容的復(fù)制有了更深層次的了解，包括如何調(diào)用線程，父進(jìn)程和子進(jìn)程等等。但是讓我感觸最深的還是對(duì)頁面置換算法程序編寫的過程。 一開始大家都只是懂 得原理，不是很懂得怎么實(shí)現(xiàn)，后來我們幾個(gè)做頁面置換的同學(xué)就在一起討論怎么 實(shí)現(xiàn)題目要求的功能，最后我決定選擇堆棧的方法進(jìn)行頁面置換。在進(jìn)行 FIFO 和 LRU這兩種置換方法的時(shí)候，思想很類似，就是發(fā)現(xiàn)物理塊內(nèi)的數(shù)沒有命中

12、的時(shí)候， 把需要置換的數(shù)據(jù)移出棧外，讓后面的數(shù)往前移，并把最新入棧的數(shù)據(jù)放到棧的最 后面，并以此類推。而OPT算法則不是這樣的，剛?cè)霔５臅r(shí)候與前面兩種算法一樣， 但是到后面的時(shí)候，在發(fā)現(xiàn)棧后第一個(gè)數(shù)據(jù)沒有與棧內(nèi)的數(shù)據(jù)一致即沒有命中數(shù)據(jù) 的時(shí)候，則調(diào)用 findspace（） 函數(shù)，先用棧內(nèi)的第一數(shù)分別與棧外面的數(shù)依次進(jìn)行 比較，如果發(fā)現(xiàn)第一個(gè)一致的，則用數(shù) POS1j （j 從 0 開始）記下那個(gè)數(shù)的位置， 并把標(biāo)記數(shù)K2+,如果沒有一致的，則把Pos1=0，再用相同的方法把第二個(gè)數(shù)分 別與后面的數(shù)進(jìn)行比較。等棧內(nèi)的數(shù)據(jù)比較完了以后，看是否有pos1j=0 的，如果有，則把此頁換出，把棧外第一

13、個(gè)數(shù)換進(jìn)來，如果有兩個(gè)，則把離棧頂最近的數(shù) 換出，如果沒有則比較所有 Pos1j 中數(shù)，把最大的數(shù)的那一頁換出，因?yàn)榇藭r(shí) 表明命中的數(shù)離棧最遠(yuǎn)，符合以后永不使用的，或者是最長（未來）時(shí)間內(nèi)不再被 訪問的頁面的原理。而在此之后如棧的數(shù)還是用同樣地方法進(jìn)行比較，老師說這樣 的話空間花費(fèi)大，代碼需要優(yōu)化，這也是我要改進(jìn)的地方。我發(fā)現(xiàn)我還有一個(gè)地方 不足的是我不是很會(huì)用界面來做實(shí)習(xí)，這也是我將來要努力的方向。這就是我這次實(shí)習(xí)的心得和體會(huì)。參考文獻(xiàn)：1、湯子嬴 編：計(jì)算機(jī)操作系統(tǒng)，西安電子科技大學(xué)出版社2、陳智勇 編：計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)，西安電子科技大學(xué)出版社附錄、源程序清單/*頁面置換算法性能測(cè)試要求：1

14、用戶可以為程序指定內(nèi)存塊數(shù) 2用戶可以自由設(shè)置程序的頁面訪問順序 3.用戶可在 OPT、FIFO 和 LRU 算法選擇一個(gè) ,并能觀看到頁面置換過程。*/#include#include#include#include#include#include#define pNum 100/ 系統(tǒng)為進(jìn)程分配物理空間intqycs=0;/ 缺頁次數(shù)char pblockpNum;/ 進(jìn)程塊賦初值，方便我們看頁面置換的命中率與缺頁率float qyl;/ 缺頁率void jpsr(intymNum,char p)/ 由鍵盤輸入 n 個(gè)整數(shù)放到 p 數(shù)組里面int i;for(i=0;iymNum;i+)s

15、canf(%d,&pi);void Print(intNum)/ 打印進(jìn)程塊的內(nèi)容int i;for(i=0;iNum;i+)printf(%3d ,pblocki);printf(n);intfindsPace(intm,charym,intNum,intymNum)/ 為最佳置換算法 (OPtimal) 尋找該置換的物理塊號(hào)inti,j,k=0,k2=0,pos1100,pos2,pos=0;for(j=0;jNum;j+)/地址序列第 M 位后與 Num 塊物理塊中的每一塊最近匹配的序列位置i存入pos1數(shù)組中j=物理塊號(hào)/k2 是個(gè)計(jì)數(shù)器如果 Num 塊物理塊中的某一塊地址序列第 M位

16、后的元素不會(huì)發(fā)生命中Pos1該物理塊號(hào)的值為零發(fā)生命中Pos1該物理塊號(hào)=該數(shù)在序列里的位置for(i=m;iymNum;i+)if(ymi=pblockj)pos1j=i;k2+;break;else pos1j=0;- 11 -if(k2=Num)/取 pos1 數(shù)組的最大值舍去pos2=pos10;for(k=1;kNum;k+)if(pos2pos1k)pos=k;else pos2=pos1k;return pos;else /當(dāng)分配的物理塊中有在后續(xù)中不使用的， 可以直接舍去語句 pos1j=0; 的作用在for(pos=0;posNum;pos+)if(pos1pos=0) re

17、turn pos;void Optimal(char ym,intNum,intymNum)/ 最佳置換算法inti,j,m=0,p;for(j=0;jNum;j+)/ 數(shù)據(jù)剛?cè)霔?，都為缺頁?shù)pblockj=ymj;Print(Num);qycs+;for(j=Num;jymNum;j+)/ 超過分配的物理塊數(shù)m=0;for(i=0;iNum;i+)if(ymj=pblocki)/ 如果有與棧內(nèi)的數(shù)據(jù)一致的稱為命中數(shù)據(jù)m=1;Print(Num);break;if(m=0)/ 沒有與棧內(nèi)的數(shù)據(jù)一致，缺頁次數(shù)加 1p=findspace(j,ym,Num,ymNum);pblockp=ymj;P

18、rint(Num);qycs+;qyl=(float)qycs/ymNum;/ 計(jì)算缺頁率|n);printf(|- 12 - 14 -printf(缺頁率為 %fn,qyl);|n);printf(| void FIFO(char ym,intNum,intymNum)/ 先進(jìn)先出算法inti,j,m=0;qycs=0;/ 防止多次選擇時(shí) qycs 會(huì)累加for(j=0;jNum;j+)/ 數(shù)據(jù)剛?cè)霔?，都為缺頁?shù)pblockj=ymj;Print(Num);qycs+;for(j=Num;jymNum;j+)/ 如果有與棧內(nèi)的數(shù)據(jù)一致的稱為命中數(shù)據(jù)m=0;for(i=0;iNum;i+)if

19、(ymj=pblocki)m=1;Print(Num);break;if(m=0)/ 沒有與棧內(nèi)的數(shù)據(jù)一致，缺頁次數(shù)加 1for(i=0;iNum-1;i+) pblocki=pblocki+1;pblockNum-1=ymj;Print(Num);qycs+;qyl=(float)qycs/ymNum;|n);printf(|printf(缺頁次數(shù)為 %dn,qycs);printf(缺頁率為 %fn,qyl);|n);printf(| void LRU(char ym,intNum,intymNum)/ 最近最久未使用算法int c=0,i,j,m=0;qycs=0;for(j=0;jNu

20、m;j+)/ 數(shù)據(jù)剛?cè)霔＃紴槿表摂?shù)pblockj=ymj; Print(Num);qycs+;for(j=Num;jymNum;j+)m=0;for(i=0;iNum;i+) if(ymj=pblocki)c=ymj;for(i+;iNum;i+)pblocki-1=pblocki;pblockNum-1=c;Print(Num);m=1;printf(n);if(m=0)for(i=0;iNum-1;i+)pblocki=pblocki+1;pblockNum-1=ymj;Print(Num);qycs+;qyl=(float)qycs/ymNum;printf(|printf(print

21、f(printf(|void display1()printf(|n);缺頁次數(shù)為 %dn,qycs);缺頁率為 %fn,qyl);|n);|n);作者：張莉蕓學(xué)號(hào)： 3090717238 (1)最佳置換算法printf(| (2)先進(jìn)先出算法printf(| (3)最近最久未使用算法printf(| (0)退出- 13 -printf(|n);|n);|n);|n);|n);|n);printf( void run() void display2(intselect,charym,intNum,intymNum);int select,s2,i,Num,ymNum;char ch;char ym20;for(Num=0;NumpNum;Num+)pblockNum=-1;/ 進(jìn)程塊賦初值，方便我們看頁面置換的命中率與缺頁率printf(nnnn);printf(- 14 -printf(作者：張莉蕓學(xué)號(hào)： 3090717238|n);printf(1) 鍵盤輸