LRU算法與CLOCK算法

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

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

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

4、當前頁面號int seq_num;/對于頁面最近一次被訪問的序列號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);/頁塊中的頁面的最近最久未使用位置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;/檢測當前頁面在不在內存中，如果在內存中，返回所在頁塊號；如果不在，返回-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;/檢測有沒有空頁塊，如果有空頁塊，返回頁塊號；如果沒有，返回-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個頁塊號int Pn;int an=0;int seq100;int i;float ar;printf(請輸入頁塊數Pn：n);scanf(%d,&Pn);printf(請輸入%d位長的頁面訪問序列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(淘汰頁面號依次為：n);for(i=0;inum;i+)/做20次int a,b;a=test1

8、(seqi,Pn,pb);b=test2(pb,Pn);if(a=-1)/不在內存中if(b!=-1)/沒滿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缺頁次數為：%dn缺頁率為%fn,an,ar);void main()PCB();(2)運行調試，輸出結果： 程序完成后，進行調試編譯，在彈出的框中輸入頁塊數Pn，回車，然后輸入20位長的頁面訪問序列seq20,回車，實驗結果將顯示出該組數據的

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

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

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

12、eplacementint fifoM; /FIFOint cMN; /存儲每個階段狀態(tài)/訪問序列隨機生成e個，e是工作集中包含的頁數，m是工作集移動率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; /*保證在虛擬內存的頁號內*/j = i;r = rand() % 100;if (r t)q

13、 = rand() % N;elseq = (q + 1) % 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);/結果輸出void print(int e,int *a)int j, i;print_form

14、at(e);for(j = 0;j e;j+)printf( %2d ,aj); /讀入內存順序printf( n);printf(置換過程：);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; /改進的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+;/初始化內存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;/改進的Clock算法void Updating_Clock(int fold,int modiff, Page *b) int i, p = -1; /p是查詢指針 int val = -1; /找是否在內存中 for(i = 0;i = 0) bval.visit = 1; /被訪問 bval.modify = modiff; for(i = 0;i M;i+) if (i != val) bi.visit = 0; else nin+; /初始化內存 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; /找到后，其他設置為未訪問 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; /產生隨機訪問串及是否修改串 P = 1; int e, m, prop, t; printf(請輸入工作集中包含的頁數e和工作集移動率m:n); scanf(%d %d,&e,&m); t = 50; generate_list(a, e, m, t); printf(請輸入頁面被修改的概率(*100):n); scanf(%d,&prop); generate_mo

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