一分鐘學會頁面置換算法【OPT、FIFO、LRU、NUR】

程序執行期間，若程序所要訪問的頁面未在內存時，便發出缺頁中斷，中斷處理程序首先保留CPU環境，轉入缺頁中斷處理程序。查找頁表，得到該頁在外存的物理塊后，如果內存未滿，則將缺頁調入內存并修改頁表。

如果內存已滿，則按照某種置換算法從內存中選出一頁換出；如果該頁未被修改過，可不必將該頁寫回磁盤；但如果此頁已被修改，則必須將它寫回磁盤，然后再把所缺的頁調入內存，并修改頁表中的相應表項，置其存在位為“1”，并將此頁表項寫入快表中。

最佳置換(OPT)算法選擇的被淘汰頁面，將是以后永不使用的，或許是在最長(未來)時間內不再被訪問的頁面；采用最佳置換算法可保證獲得最低的缺頁率。但是由于無法預知哪一個頁面是未來最長時間內不再被訪問的，因而該算法是無法實現的；

先進先出（FIFO）算法淘汰最先進入內存的頁面，即選擇在內存中駐留時間最久的頁面予以淘汰。

最近最久未使用（LRU）算法根據頁面調入內存后的使用情況進行決策，選擇最近最久未使用的頁面予以淘汰；該算法賦予每個頁面一個訪問字段，用來記錄一個頁面自上次被訪問一來所經歷的時間T，當需要淘汰一個頁面時，選擇現有頁面中T值最大的，即最近最久未使用的頁面予以淘汰。

CLCOK算法又稱為最近未使用算法（NUR） 每頁設置一個訪問位，再將內存中的所有頁面都通過鏈接指針鏈接成一個循環隊列；當某個頁面被訪問時，其訪問位置1。淘汰時，檢查其訪問位，如果是0，就換出；若為1，則重新將它置0；再按FIFO算法檢查下一個頁面，到隊列中的最后一個頁面時，若其訪問位仍為1，則再返回到隊首再去檢查第一個頁面。

1．假設系統為某進程分配了四個物理塊，頁面使用走向為：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1，分別采用OPT算法，FIFO算法，LRU算法，給出頁面的置換過程，以及各自發生了幾次頁面置換？

OPT:4次；FIFO:6次；LRU:4次

2．打開“Microsoft Visual C++ 6.0”，輸入相關代碼，根據代碼注釋把空缺的FIFO算法補充完畢，對程序行進編譯運行。給出你所填寫的FIFO算法代碼：

bc[p%blockCount]=pc[i]; p++;

3．根據提示輸入上述相關數據，分別記錄OPT算法、FIFO算法、LRU算法以及CLOCK算法運行結果：

（1）OPT算法：

（2）FIFO算法

（3）LRU算法

（4）CLOCK算法

——————————————————————————————————————————————————————————————————————————————————————

附上源代碼：

#include using namespace std; void Print(int bc[],int blockCount){ for(int i=0; i=k){ k=a[i]; j=i; } } return j; } void LRU(int pc[],int bc[], int pageCount, int blockCount) { cout<<"1:LRU 置換算法"<=max){ max=k; blockIndex=j; } } bc[blockIndex]=pc[i]; } noPage++; cout<<"物理塊情況:"; Print(bc, blockCount); } cout<>pageCount; int *pc=new int[pageCount]; cout<<"輸入頁面走向"<>pc[i]; } cout<<"輸入物理塊數"<>blockCount; cout<<"0:FIFO置換算法"<>n){ if(n==0){ int *bc=new int[blockCount]; FIFO(pc,bc,pageCount,blockCount); delete bc; } else if(n==1){ int *bc=new int[blockCount]; LRU(pc,bc,pageCount,blockCount); delete bc; } else if(n==2){ int *bc=new int[blockCount]; Optiomal(pc,bc,pageCount,blockCount); delete bc; } else if(n==3){ int *bc=new int[blockCount]; for(i=0; i

其實做人最重要的是自信，到哪兒都一樣。————《葉問4》

云數據庫 GaussDB(for Redis) 任務調度

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。