LRU算法與CLOCK算法

1、實(shí)驗(yàn)報(bào)告課程名稱 操作系統(tǒng) 實(shí)驗(yàn)項(xiàng)目名 _LRU算法模擬 班級(jí)與班級(jí)代碼 實(shí)驗(yàn)室名稱（或課室） 專 業(yè) 任課教師 學(xué) 號(hào)： 姓 名： 實(shí)驗(yàn)日期： 2012 年 5 月 20 日 制 姓名 實(shí)驗(yàn)報(bào)告成績(jī) 評(píng)語(yǔ)：等級(jí)項(xiàng)目?jī)?yōu)一般差評(píng)分實(shí)驗(yàn)態(tài)度（10）正確性（20）熟練性（30）判斷能力（20）應(yīng)變能力（20） 指導(dǎo)教師（簽名） 年 月 日說(shuō)明：指導(dǎo)教師評(píng)分后，學(xué)年論文交院（系）辦公室保存。實(shí)驗(yàn)八 LRU算法模擬一、 實(shí)驗(yàn)?zāi)康?（1）模擬實(shí)現(xiàn)LRU算法。（2）模擬實(shí)現(xiàn)Clock算法。（3）比較分析LRU算法、Clock算法。二、 實(shí)驗(yàn)內(nèi)容（1）算法實(shí)現(xiàn)。（2）擬定測(cè)試數(shù)據(jù)對(duì)算法的正確性進(jìn)行測(cè)試。（3）

2、對(duì)比分析LRU算法和Clock算法各自的優(yōu)缺點(diǎn)。三、 實(shí)驗(yàn)環(huán)境硬件要求：P4 2.0G 1G內(nèi)存60G硬盤以上電腦軟件要求：C、C+編程環(huán)境，Java編程環(huán)境四、 實(shí)驗(yàn)步驟1. LRU算法（1） 預(yù)備知識(shí) 最近最久未使用(LRU)的頁(yè)面置換算法，是根據(jù)頁(yè)面調(diào)入內(nèi)存后的使用情況進(jìn)行決策的。由于無(wú)法預(yù)測(cè)各頁(yè)面將來(lái)的使用情況，只能利用“最近的過(guò)去”作為“最近的將來(lái)”的近似，因此，LRU置換算法是選擇最近最久未使用的頁(yè)面予以淘汰。該算法賦予每個(gè)頁(yè)面一個(gè)訪問(wèn)字段，用來(lái)記錄一個(gè)頁(yè)面自上次被訪問(wèn)以來(lái)所經(jīng)歷的時(shí)間t，當(dāng)須淘汰一個(gè)頁(yè)面時(shí)，選擇現(xiàn)有頁(yè)面中其t值最大的，即最近最久未使用的頁(yè)面予以淘汰。 （2）LRU

3、的實(shí)現(xiàn)（需要“堆?！敝С郑┛衫靡粋€(gè)特殊的棧來(lái)保存當(dāng)前使用的各個(gè)頁(yè)面的頁(yè)面號(hào)。每當(dāng)進(jìn)程訪問(wèn)某頁(yè)面時(shí)，便將該頁(yè)面的頁(yè)面號(hào)從棧中移出，將它壓入棧頂。因此，棧頂始終是最新被訪問(wèn)頁(yè)面的編號(hào)，而棧底則是最近最久未使用頁(yè)面的頁(yè)面號(hào)。假定現(xiàn)有一進(jìn)程所訪問(wèn)的頁(yè)面序列為：4，7，0，7，1，0，1，2，1，2，6隨著進(jìn)程的訪問(wèn)，棧中頁(yè)面號(hào)的變化情況如圖所示。在訪問(wèn)頁(yè)面6時(shí)發(fā)生了缺頁(yè)，此時(shí)頁(yè)面4是最近最久未被訪問(wèn)的頁(yè)，應(yīng)將它置換出去。（2）具體的操作代碼及其結(jié)果如下：#include#include#define num 20#define max 65535typedef struct PBint page;/

4、當(dāng)前頁(yè)面號(hào)int seq_num;/對(duì)于頁(yè)面最近一次被訪問(wèn)的序列號(hào)int fg;Pb;int k;int seek(int seq,int i,Pb a,int k);int test1(int seq_i,int Pn,Pb a);int test2(Pb a,int Pn);int LRU(int seq,int i,int Pn,Pb pb);/頁(yè)塊中的頁(yè)面的最近最久未使用位置int seek(int seq,int i,Pb a,int k)int flag=0;for(int j=i-1;j=0;j-)if(ak.page=seqj)flag=1;return j;break;if(

5、flag=0)return -1;/檢測(cè)當(dāng)前頁(yè)面在不在內(nèi)存中，如果在內(nèi)存中，返回所在頁(yè)塊號(hào)；如果不在，返回-1int test1(int seq_i,int Pn,Pb a)int flag=0;for(int j=0;jPn;j+)if(aj.page=seq_i)flag=1;return j;break;if(flag=0)return -1;/檢測(cè)有沒(méi)有空頁(yè)塊，如果有空頁(yè)塊，返回頁(yè)塊號(hào)；如果沒(méi)有，返回-1int test2(Pb a,int Pn)int flag=0;for(int j=0;jPn;j+)if(aj.page=-1)flag=1;return j;break;if(f

6、lag=0)return -1; int LRU(int seq,int i,int Pn,Pb pb)int temp20;int j;for(k=0;kPn;k+)tempk=seek(seq,i,pb,k);pbk.fg=seek(seq,i,pb,k); for(k=1;kPn;k+)int lastX=1;int tem;for(j=0;jtempj+1)tem=tempj;tempj=tempj+1;tempj+1=tem;lastX=0;if(lastX=1) break;for(k=0;kPn;k+)if(pbk.fg=temp0)printf(%d ,pbk.page);re

7、turn k;break;void PCB()Pb pb10;/最多只允許0-9共10個(gè)頁(yè)塊號(hào)int Pn;int an=0;int seq100;int i;float ar;printf(請(qǐng)輸入頁(yè)塊數(shù)Pn：n);scanf(%d,&Pn);printf(請(qǐng)輸入%d位長(zhǎng)的頁(yè)面訪問(wèn)序列seq%d：n,num,num);for(i=0;inum;i+)scanf(%d,&seqi);for(i=0;i10;i+)pbi.page=-1;pbi.seq_num=-1;pbi.fg=max;printf(淘汰頁(yè)面號(hào)依次為：n);for(i=0;inum;i+)/做20次int a,b;a=test1

8、(seqi,Pn,pb);b=test2(pb,Pn);if(a=-1)/不在內(nèi)存中if(b!=-1)/沒(méi)滿pbb.page=seqi;pbb.seq_num=i;an+;else/滿了k=LRU(seq,i,Pn,pb);pbk.page=seqi; pbk.seq_num=i; an+;ar=(float)an/(float)num;printf(n缺頁(yè)次數(shù)為：%dn缺頁(yè)率為%fn,an,ar);void main()PCB();(2)運(yùn)行調(diào)試，輸出結(jié)果： 程序完成后，進(jìn)行調(diào)試編譯，在彈出的框中輸入頁(yè)塊數(shù)Pn，回車，然后輸入20位長(zhǎng)的頁(yè)面訪問(wèn)序列seq20,回車，實(shí)驗(yàn)結(jié)果將顯示出該組數(shù)據(jù)的

9、淘汰頁(yè)面號(hào)、缺頁(yè)次數(shù)和缺頁(yè)率。 注：實(shí)驗(yàn)結(jié)果中，輸入的數(shù)據(jù)為：12560 36536 56042 70435。LRU算法編譯后的結(jié)果如下：（3）編譯時(shí)出現(xiàn)的錯(cuò)誤：調(diào)試時(shí)出錯(cuò)情況有三類：1） 低級(jí)錯(cuò)誤。編寫時(shí)字母寫錯(cuò)，或；丟失，等；2） 警告錯(cuò)誤。使用指針錯(cuò)誤，或定義的指針沒(méi)有使用等；3） 匹配錯(cuò)誤。在編譯子程序時(shí)出現(xiàn)類型不匹配，以及一些語(yǔ)法錯(cuò)誤等。2、CLOCK算法 （1）預(yù)備知識(shí) 當(dāng)采用簡(jiǎn)單Clock算法時(shí)，只需為每頁(yè)設(shè)置一位訪問(wèn)位，再將內(nèi)存中的所有頁(yè)面都通過(guò)鏈接指針鏈接成一個(gè)循環(huán)隊(duì)列。當(dāng)某頁(yè)被訪問(wèn)時(shí)，其訪問(wèn)位被置1。置換算法在選擇一頁(yè)淘汰時(shí)，只需檢查頁(yè)的訪問(wèn)位。如果是0，就選擇該頁(yè)換出；若

10、為1，則重新將它置0，暫不換出，而給該頁(yè)第二次駐留內(nèi)存的機(jī)會(huì)，再按照FIFO算法檢查下一個(gè)頁(yè)面。當(dāng)檢查到隊(duì)列中的最后一個(gè)頁(yè)面時(shí)，若其訪問(wèn)位仍為1，則再返回到隊(duì)首去檢查第一個(gè)頁(yè)面。下圖展示了該算法的流程和示例。由于該算法是循環(huán)地檢查各頁(yè)面的使用情況，故稱為Clock算法。但因該算法只有一位訪問(wèn)位，只能用它表示該頁(yè)是否已經(jīng)使用過(guò)，而置換時(shí)是將未使用過(guò)的頁(yè)面換出去，故又把該算法稱為最近未用算法NRU(Not Recently Used)。 (2)具體的操作代碼如下：#includeStdAfx.h#include#include #include #define M 3 /內(nèi)存物理塊數(shù)#define

11、 N 20 /虛擬內(nèi)存尺寸int P; /工作集的起始位置int nin; /記錄缺頁(yè)次數(shù)/用于CLOCK算法的頁(yè)面定義typedef struct page_clock int num; int visit; Page_clock; /用于改進(jìn)的CLOCK算法的頁(yè)面定義typedef struct page int num; /頁(yè)面號(hào) int visit; /是否訪問(wèn) int modify; /是否修改Page; Page_clock b_clockM; /內(nèi)存單元數(shù) ClockPage bM; /updating_clockint optM; /optint ranM; /random r

12、eplacementint fifoM; /FIFOint cMN; /存儲(chǔ)每個(gè)階段狀態(tài)/訪問(wèn)序列隨機(jī)生成e個(gè)，e是工作集中包含的頁(yè)數(shù)，m是工作集移動(dòng)率void generate_list(int *list, int e, int m, int t)int i, j = 0, q =P, r;srand(unsigned)time(NULL);while (j e)for (i = j;i j + m;i+)if (i = e)break;listi = (q + rand() % e) % N; /*保證在虛擬內(nèi)存的頁(yè)號(hào)內(nèi)*/j = i;r = rand() % 100;if (r t)q

13、 = rand() % N;elseq = (q + 1) % N;/隨機(jī)生產(chǎn)是否被修改的情況，prop(0.100)，prop/100的概率未被修改void generate_modify(int *mo, int e, int prop)int i, t;for (i = 0;i prop)moi = 0;elsemoi = 1;/格式輸出void print_format(int e)int i;printf( );for (i = 1;i e;i+)printf( );printf( n);/結(jié)果輸出void print(int e,int *a)int j, i;print_form

14、at(e);for(j = 0;j e;j+)printf( %2d ,aj); /讀入內(nèi)存順序printf( n);printf(置換過(guò)程：);print_format(e);for(i = 0;i M;i+) for(j = 0;j e;j+)if(cij = -1)printf( %c , );elseprintf( %2d ,cij);printf( n);print_format(e);/Clock算法初始化void Init_Clock(Page_clock *b_clock)nin = 0;int i, j;for(i = 0;i M;i+) b_clocki.num = -1;

15、b_clocki.visit = 0; for(i = 0;i M;i+) for(j = 0;j N;j+)cij = -1; /改進(jìn)的Clock算法初始化void Init_updatingClock(Page *b)nin = 0;int i, j;for(i = 0;i M;i+) bi.num = -1;bi.visit = 0; bi.modify = 0;for(i = 0;i M;i+)for(j = 0;j N;j+)cij = -1; /Clock算法void Clock(int fold,Page_clock *b_clock)int i, val = -1, p = 0

16、; /p為查詢指針for (i = 0;i = 0)b_clockval.visit = 1;for(i = 0;i M;i+)if (i != val)b_clocki.visit = 0;elsenin+;/初始化內(nèi)存for (i = 0;i M;i+)if (b_clocki.num = -1)val = i;break;while (val 0)if (b_clockp.visit = 0)val = p;elseb_clockp.visit = 0;p = (p + 1) % M;b_clockval.num = fold;b_clockval.visit = 1;for(i = 0

17、;i M;i+)if (i != val)b_clocki.visit = 0;/改進(jìn)的Clock算法void Updating_Clock(int fold,int modiff, Page *b) int i, p = -1; /p是查詢指針 int val = -1; /找是否在內(nèi)存中 for(i = 0;i = 0) bval.visit = 1; /被訪問(wèn) bval.modify = modiff; for(i = 0;i M;i+) if (i != val) bi.visit = 0; else nin+; /初始化內(nèi)存 for (i = 0;i M;i+) if (bi.num

18、 = -1) val = i; break; while (val 0) /第一步掃描 for (i = 0;i M;i+) p = (p + 1) % M; if (bp.modify = 0) & (bp.visit = 0) val = p; break; /第二步掃描 if (val 0) for (i = 0;i M;i+) p = (p + 1) % M; if (bp.modify = 1) & (bp.visit = 0) val = p; break; else bp.visit = 0; /找到后，其他設(shè)置為未訪問(wèn) bval.num = fold; bval.modify

19、= modiff; bval.visit = 1; for(i = 0;i M;i+) if (i != val) bi.visit = 0; /主程序void main() int aN; int moN; int i,j; /產(chǎn)生隨機(jī)訪問(wèn)串及是否修改串 P = 1; int e, m, prop, t; printf(請(qǐng)輸入工作集中包含的頁(yè)數(shù)e和工作集移動(dòng)率m:n); scanf(%d %d,&e,&m); t = 50; generate_list(a, e, m, t); printf(請(qǐng)輸入頁(yè)面被修改的概率(*100):n); scanf(%d,&prop); generate_mo

20、dify(mo, e, prop); /Clock算法實(shí)現(xiàn) Init_Clock(b_clock); for(i = 0;i e;i+) Clock(ai,b_clock); for(j = 0;j M;j+) cji = b_clockj.num; printf(Clock算法的內(nèi)存狀態(tài)為：n); print(e, a); nin = nin - M; printf(缺頁(yè)次數(shù)為：%dn缺頁(yè)率：%.2fn,nin,nin * 1.0 / e); printf(n); /改進(jìn)的Clock算法實(shí)現(xiàn) Init_updatingClock(b); for(i = 0;i e;i+) Updating_

21、Clock(ai, moi, b); for(j = 0;j M;j+) cji = bj.num; printf(改進(jìn)的Clock算法的內(nèi)存狀態(tài)為：n); print(e, a); for(j = 0;j e;j+) printf( %2d ,moj); /是否修改序列串 printf( n); print_format(e); nin = nin - M; printf(缺頁(yè)次數(shù)為：%dn缺頁(yè)率：%.2fn,nin,nin * 1.0 / e); printf(n);Clock算法實(shí)驗(yàn)運(yùn)行結(jié)果: 五、 實(shí)驗(yàn)分析（1）頁(yè)塊數(shù)可變，LRU算法結(jié)果正確。成功實(shí)現(xiàn)了LRU算法，并將頁(yè)塊數(shù)作為輸入項(xiàng)，交由用戶控制，實(shí)現(xiàn)了較為完善的LRU算法。（2）clock算法中，輸入工作集中的頁(yè)數(shù)和工作及移動(dòng)率可變，且在改變的clock算法中運(yùn)行結(jié)果與之前的數(shù)據(jù)一致，所以，clock算法及其改進(jìn)算法