頁面置換算法 FIFO NUR LRU LFU_第1頁
頁面置換算法 FIFO NUR LRU LFU_第2頁
頁面置換算法 FIFO NUR LRU LFU_第3頁
頁面置換算法 FIFO NUR LRU LFU_第4頁
頁面置換算法 FIFO NUR LRU LFU_第5頁
已閱讀5頁,還剩13頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

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é),從而加以彌補。在此感謝我們的陳占芳老師.,老師嚴謹細致、一絲不茍的作風一直是我

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論