頁面置換算法 FIFO NUR LRU LFU

1、編號 09 學生實習報告20112012學年 第 一 學期實 習 類 別科研訓練學 生 姓 名 某某某專 業(yè)軟件開發(fā)與測試學 號XX指 導 教 師陳占芳學 院軟件學院2011年 12 月 起 止 周1718周 數(shù)2實習地點軟件學院專業(yè)實驗室實訓目的： 操作系統(tǒng)是計算機專業(yè)的核心專業(yè)課，“操作系統(tǒng)課程設(shè)計”是理解和鞏固操作系統(tǒng)基本理論、原理和方法的重要的實踐環(huán)節(jié)。主要任務(wù)是實現(xiàn)操作系統(tǒng)和相關(guān)系統(tǒng)軟件的設(shè)計，其中涉及進程創(chuàng)建，同步，進程間的通信，存儲管理，文件系統(tǒng)等操作系統(tǒng)概念。實訓要求：1）對需要上機完成的題目進行認真分析，列出實驗具體步驟，寫出符合題目要求的程序清單，準備出調(diào)試程序使用的數(shù)據(jù)。

2、2）以完整的作業(yè)包的形式提交原始代碼、設(shè)計文檔和可運行程序。課程設(shè)計報告字數(shù)不少于2000字。實訓進度安排及主要內(nèi)容：第一周：查閱資料、總體設(shè)計第二周：詳細設(shè)計、文檔編寫成績：指導教師/帶隊教師（簽字）年 月 日目錄第一章 概述- 2 -第二章 設(shè)計基本原理- 3 -第三章 總體設(shè)計- 5 -3.1分析算法結(jié)構(gòu)- 5 -3.2算法流程圖- 6 -3.2.1 FIFO頁面置換算法- 6 -3.2.2 LRU頁面置換算法- 7 -3.2.3 LFU頁面置換算法- 8 -第四章 詳細設(shè)計- 9 -4.1 main函數(shù)- 9 -4.2 FIFO函數(shù)- 9 -4.3 LRU函數(shù)- 10 -4.4 NUR

3、函數(shù)- 11 -4.5 LFU函數(shù)- 12 -4.6 initialize主函數(shù)- 13 -第五章 測試- 14 -第六章 總結(jié)- 16 -第七章 參考文獻- 16 -第一章 概述設(shè)計任務(wù)：請求頁式管理是一種常用的虛擬存儲管理技術(shù)。本設(shè)計通過請求頁式存儲管理中頁面置換算法模擬設(shè)計，了解虛擬存儲技術(shù)的特點，掌握請求頁式管理的頁面置換算法。通過隨機數(shù)產(chǎn)生一個指令序列，共320條指令。指令的地址按下述原則生成： 50% 的指令是順序執(zhí)行的； 25% 的指令是均勻分布在前地址部分； 25% 的指令是均勻分布在后地址部分。實施方法：在 0,319 的指令地址之間隨機選取一起點 m；順序執(zhí)行一條指令；在前

4、地址0,m+1中隨機選取一條指令并執(zhí)行，該指令的地址為 m； 順序執(zhí)行一條指令，其地址為 m+1；在后地址 m+2,319 中隨機選取一條指令并執(zhí)行 ；重復上述步驟 ， 直到執(zhí)行 320 次指令。將指令序列變換成為頁地址流設(shè)：頁面大小為 1K；用戶內(nèi)存容量為 4 頁到 32 頁 ；用戶虛存容量為 32K 。在用戶虛存中，按每 K 存放 10 條指令排列虛存地址，即 320 條指令在虛存中的放方式為：第 0 條 第 9 條指令為第 0 頁 ( 對應虛存地址為 0,9)；第 10 條 第 19 條指令為第 1 頁 ( 對應虛存地址為 10,19 ) ；第 310 條 第 319 條指令為第 31

5、頁 ( 對應虛存地址為 310,319) 。按以上方式，用戶指令可組成 32 頁。計算并輸出下述各種算法在不同內(nèi)存容量下的命中率。先進先出的算法 (FIFO)；最近最少使用算法 (LRu)；最少訪問頁面算法 (LFu)；最近最不經(jīng)常使用算法 (NUR)。第二章 設(shè)計基本原理(1)請求頁式存儲管理的實現(xiàn)原理請求頁式管理的基本原理是將邏輯地址空間分成大小相同的頁，將存儲地址空間分塊，頁和塊的大小相等，通過頁表進行管理。頁式系統(tǒng)的邏輯地址分為頁號和頁內(nèi)位移量。頁表包括頁號和塊號數(shù)據(jù)項，它們一一對應。根據(jù)邏輯空間的頁號，查找頁表對應項找到對應的塊號，塊號乘以塊長，加上位移量就行成存儲空間的物理地址。每

6、個作業(yè)的邏輯地址空間是連續(xù)的，重定位到內(nèi)存空間后就不一定連續(xù)了。(2)各種頁面置換算法的實現(xiàn)思想FIFO算法總是淘汰最先調(diào)入主存的頁面，即淘汰在主存中駐留時間最長的頁面，認為駐留時間最長的頁不再使用的可能性較大。LRU算法淘汰的頁面是最近一段時間內(nèi)最久未被訪問的那一頁，它是基于程序局部性原理來考慮的，認為那些剛被使用過的頁面可能還要立即被使用，而那些在較長時間內(nèi)未被使用的頁面可能不會立即使用。LFU即最不經(jīng)常使用頁置換算法，要求在頁置換時置換引用計數(shù)最小的頁，因為經(jīng)常使用的頁應該有一個較大的引用次數(shù)。但是有些頁在開始時使用次數(shù)很多，但以后就不再使用，這類頁將會長時間留在內(nèi)存中，因此可以將引用計

7、數(shù)寄存器定時右移一位，形成指數(shù)衰減的平均使用次數(shù)。算法提示：1. 命中率 = 1 - 頁面失效次數(shù)頁地址流長度在本實驗中，頁地址流長度為 320，頁面失效次數(shù)為每次訪問相應指令時，該指令所對應的頁不在內(nèi)存的次數(shù)。2. 隨機數(shù)產(chǎn)生辦法關(guān)于隨機數(shù)產(chǎn)生辦法，Windwos系統(tǒng)提供函數(shù)srand( ) 和 rand( )，進行初始化和產(chǎn)生隨機數(shù)。例如：#include srand( (unsigned)time( NULL ) );語句可初始化一個隨機數(shù) ; ao=10 * rand( ) / 32767 * 319 + 1;a1= 10 * rand( ) / 32767 * ao;語句可用來產(chǎn)生

8、a0 與 a1 中的隨機數(shù)。第三章 總體設(shè)計3.1分析算法結(jié)構(gòu)3.2算法流程圖3.2.1 FIFO頁面置換算法3.2.2 LRU頁面置換算法3.2.3 LFU頁面置換算法第四章 詳細設(shè)計4.1 main函數(shù)int main()int S,i;srand(int)time(NULL);S=(int)rand()%320;for(i=0;itotal_instruction;i+=1)ai=S; ai+1=ai+1;ai+2=(int)rand()%320; ai+3=ai+2+1; S=(int)rand()%320;for(i=0;itotal_instruction;i+) pagei=ai

9、/10; offseti=ai%10; 4.2 FIFO函數(shù)void FIFO(int total_pf) int i,j; pfc_type *p; initialize(total_pf); busypf_head=busypf_tail=NULL; for(i=0;inext; plbusypf_head-pn.pfn=INVALID; freepf_head=busypf_head; freepf_head-next=NULL; busypf_head=p; p=freepf_head-next; freepf_head-next=NULL; freepf_head-pn=pagei;

10、 plpagei.pfn=freepf_head-pfn; if(busypf_tail=NULL) busypf_head=busypf_tail=freepf_head; else busypf_tail-next=freepf_head; busypf_tail=freepf_head; freepf_head=p; printf( %6.4ft,1-(float)diseffect/320);4.3 LRU函數(shù)void LRU(int total_pf) int min,minj,i,j,present_time;initialize(total_pf);present_time=0;

11、for(i=0;itotal_instruction;i+) if(plpagei.pfn=INVALID) diseffect+;if(freepf_head=NUL) min=32767;for(j=0;jplj.time&plj.pfn!=INVALID)min=plj.time;minj=j;freepf_head=&pfcplminj.pfn;plminj.pfn=INVALID;plminj.time=-1;freepf_head-next=NUL;plpagei.pfn=freepf_head-pfn;plpagei.time=present_time;freepf_head=f

12、reepf_head-next;elseplpagei.time=present_time;present_time+;printf( %6.4ft,1-(float)diseffect/320);4.4 NUR函數(shù)void NUR(int total_pf) int i,j,dp,cont_flag,old_dp;pfc_type *t;initialize(total_pf);dp=0;for(i=0;itotal_instruction;i+)if(plpagei.pfn=INVALID) diseffect+;if(freepf_head=NUL)cont_flag=TRUE;old_

13、dp=dp;while(cont_flag)if(pldp.counter=0&pldp.pfn!=INVALID)cont_flag=FALSE;elsedp+;if(dp=total_vp) dp=0;if(dp=old_dp)for(j=0;jnext=NUL;plpagei.pfn=freepf_head-pfn;freepf_head=freepf_head-next;elseplpagei.counter=1;if(i%clear_period=0)for(j=0;jtotal_vp;j+)plj.counter=0;printf( %6.4ft,1-(float)diseffec

14、t/320);4.5 LFU函數(shù)void LFU (int total_pf) int i,j,min,minpage; pfc_type *t; initialize(total_pf); for(i=0;itotal_instruction;i+) if(plpagei.pfn=INVALID) diseffect+; if(freepf_head=NULL) min=32767; for(j=0;jplj.counter&plj.pfn!=INVALID) min=plj.counter; minpage=j; plj.counter=0; freepf_head=&pfcplminpa

15、ge.pfn; plminpage.pfn=INVALID; freepf_head-next=NULL; plpagei.pfn=freepf_head-pfn; plpagei.counter+; freepf_head=freepf_head-next; else plpagei.counter+;printf( %6.4fn,1-(float)diseffect/320);4.6 initialize主函數(shù)void initialize(int total_pf) int i;diseffect=0;for(i=0;itotal_vp;i+)pli.pn=i;pli.pfn=INVAL

16、ID; pli.counter=0;pli.time=-1; for(i=1;itotal_pf;i+)pfci-1.next=&pfci;pfci-1.pfn=i-1;pfctotal_pf-1.next=NUL;pfctotal_pf-1.pfn=total_pf-1;freepf_head=&pfc0;第五章 測試運行程序 ，如圖：第六章 總結(jié)兩周的課程設(shè)計結(jié)束了，在這次的課程設(shè)計中不僅檢驗了我所學習的知識，也培養(yǎng)了我如何去把握一件事情，如何去做一件事情，又如何完成一件事情。在這次設(shè)計過程中，體現(xiàn)出自己單獨設(shè)計模具的能力以及綜合運用知識的能力，體會了學以致用、突出自己勞動成果的喜悅心情，從中發(fā)現(xiàn)自己平時學習的不足和薄弱環(huán)節(jié)，從而加以彌補。在此感謝我們的陳占芳老師.，老師嚴謹細致、一絲不茍的作風一直是我