1、頁(yè)面置換算法FIFO算法（1）、算法思路：最簡(jiǎn)單的頁(yè)面置換算法是先入先出（FIFO）法。這種算法的 實(shí)質(zhì)是，總是選擇在主存中停留時(shí)間最長(zhǎng)（即最老）的一頁(yè)置換，即先進(jìn)入內(nèi)存 的頁(yè)，先退出內(nèi)存。理由是：最早調(diào)入內(nèi)存的頁(yè)，其不再被使用的可能性比剛調(diào) 入內(nèi)存的可能性大。建立一個(gè)FIFO隊(duì)列，收容所有在內(nèi)存中的頁(yè)。被置換頁(yè)面 總是在隊(duì)列頭上進(jìn)行。當(dāng)一個(gè)頁(yè)面被放入內(nèi)存時(shí)，就把它插在隊(duì)尾上。這種算法只是在按線性順序訪問(wèn)地址空間時(shí)才是理想的，否則效率不高。因 為那些常被訪問(wèn)的頁(yè)，往往在主存中也停留得最久，結(jié)果它們因變“老”而不得 不被置換出去。FIFO的另一個(gè)缺點(diǎn)是，它有一種異?，F(xiàn)象，即在增加存儲(chǔ)塊的 情況下

2、，反而使缺頁(yè)中斷率增加了。當(dāng)然，導(dǎo)致這種異?，F(xiàn)象的頁(yè)面走向?qū)嶋H上 是很少見(jiàn)的。（2）、算法數(shù)據(jù)結(jié)構(gòu)：存儲(chǔ)頁(yè)面號(hào)序列page,存儲(chǔ)裝入物理塊中的頁(yè)面 memery,犧牲幀頁(yè)面的換出swap out,為頁(yè)面添加上位修改位modify bit,（3）、主要函數(shù)代碼：int Page320=0;虛擬存儲(chǔ)區(qū)，存儲(chǔ)320條指令,32個(gè)頁(yè)面int Page_flu320=0; 存儲(chǔ) 320 個(gè)頁(yè)地址流int count=0; 計(jì)算隨機(jī)產(chǎn)生的指令條數(shù)double lack_page=0;記錄缺頁(yè)數(shù)int count_page=max_page;計(jì)算隊(duì)列空頁(yè)面?zhèn)€數(shù)intcircle=l;在隊(duì)列中循環(huán)指向被調(diào)出的

3、進(jìn)程（4）、測(cè)試案例首先通過(guò)rand函數(shù)和srand函數(shù)產(chǎn)生320條指令，計(jì)算每條指令對(duì)應(yīng)的頁(yè) 面很簡(jiǎn)單，只需要將指令/10即可；得到頁(yè)地址流后（頁(yè)地址流存放在數(shù)組中）, 從頭到尾訪問(wèn)一遍頁(yè)地址流，每訪問(wèn)一個(gè)頁(yè)面就判斷其是否己經(jīng)在內(nèi)存中，在無(wú) 需操作，不在則將其（使用FIFO）調(diào)入內(nèi)存。FIFO：在頁(yè)面缺頁(yè)并且內(nèi)存塊不足時(shí)，只需要將內(nèi)存塊中原先的頁(yè)面依次 淘汰即可。假設(shè)頁(yè)地址流為：111126（內(nèi)存塊大小為3 ）塊大小為3 ）進(jìn)入內(nèi)存1被調(diào)出2被調(diào)出命中3被調(diào)出（形成一個(gè)循環(huán)）115被調(diào)出11124被調(diào)出11128被調(diào)出（形成一個(gè)循環(huán)）只要為內(nèi)存塊編號(hào)（不是為頁(yè)面編號(hào)），用一個(gè)變量（初值為1）作為指針，此 變量指向的內(nèi)存塊，就