1、頁面置換算法是幹嘛的
虛拟頁式存儲管理的基本工作原理：在程序運作之前，不是裝入全部頁面，而是裝入全部頁面，而是裝入一個或零個頁面，之後根據程序運作的需要，動态裝入其他頁面；當記憶體空間已滿，而又需要裝入新的頁面時，則根據某種算法淘汰某個頁面，以便裝入新的頁面。
在使用虛拟頁式存儲管理時需要在頁表中增加一些内容，得到頁表的内容如下：
頁号、駐留位、記憶體塊号、外存位址、通路位、修改位
其中駐留位，又稱中斷位，表示該頁實在記憶體中還是外存中；通路位表示該頁在記憶體期間是否被通路過，稱為R位；修改位表示改業在記憶體中是否被修改過，稱為M位。
通路位和修改位可以用來決定置換哪個頁面，比如說第二次機會頁面置換算法。
缺頁中斷：在位址映射過程中，若在頁表中發現所要通路的頁面不在記憶體，則産生缺頁中斷。
當發生缺頁中斷時，作業系統必須在記憶體中選擇一個頁面将其移除頁面，以便即将調入的頁面讓出空間。
2、頁面置換算法
(1)理想頁面(OPT：optimal)
這是一種理想情況下的頁面置換算法，但實際上是不可能實作的。
該算法的基本思想：發生缺頁時，有些頁面在記憶體中，其中有一頁将很快被通路(包含緊接着 的下一條指令的那頁)，而其他頁則可能到10、100或1000條指令後才會被通路，每個頁都可以用在該頁面首次被通路前所要執行的指令數進行标記。标記樹最大的頁應該被置換。
舉例：如果某頁在八百萬條指令内不會被使用，另外一頁在六百萬條指令不會被使用，則置換前一個頁面。
這個算法無法實作，因當缺頁中斷時，系統無法知道各個頁面下一次在什麼時候被通路。
(2)先進先出(FIFO：First-In First-Out)
先進先出頁面置換算法總是選擇最先裝入記憶體的一頁調出，或者說是把駐留在記憶體中時間最長的一頁調出。
FIFO算法簡單，容易實作。以把裝入記憶體的那些頁面的頁号按進入的先後次序排好隊列，每次總是調出隊首的頁。當系統維護一個所有目前在記憶體中的頁面的連結清單，最老的頁面在頭上，最新的頁面在表尾。當發生缺頁時，淘汰表頭的頁面并把新調入的頁面加到表尾。
(3)最近最少使用(LRU：Least Recently Used)
最近最少使用頁面置換算法總是選擇距離現在最長時間内沒有被通路過的頁面先調出。
(4)第二次機會頁面置換算法
FIFO算法可能會吧經常使用的頁面置換出去，為了避免這一問題，對該算法進行簡單的修改：檢查最老頁面的R位，如果R位是0，那麼這個頁面又老有沒用，可以立即置換出去，如果是1，就清零R位，并将該頁放到連結清單的尾端，修改它的裝入時間使它就像裝入的一樣，然後繼續搜尋。如果所有的頁面都被通路過，那麼該算法就被降為純粹的FIFO算法。
(5)時鐘頁面置換算法
由于第二次機會頁面置換算法要經常在連結清單中移動頁面，降低了效率。一個更好的辦法，将所有的頁面存在一個類似鐘表面的環形連結清單中。
(6)最近未使用(NRU：Not Recently Used)
用R位和M位構造一個簡單的頁面置換算法：當啟動一個程序時，它的所有頁的兩個位都由作業系統設定成0，R位被定期的清零，以差別最近沒有被通路的頁和被通路了的頁。
根據R位和M位，分為4類頁面
第0類：沒有被通路，沒有被修改
第1類，沒有被通路，被修改
第2類，被通路，沒有被修改
第3類，被通路，被修改。
NRU算法随機地從編号最小的非空類中挑選一個頁淘汰之。這個算法隐含的意思是，淘汰一個在最近一個時鐘周期内沒有被通路過的已修改頁要比淘汰一個被頻繁通路的幹淨的頁好。
Belady異常現象
從直覺上看，在記憶體中的實體頁面數越多，程式的缺頁次數應該越少，但是實際情況并不是這樣。
Belady在1969年發現一個反例，使用FIFO算法時，四個頁框時缺頁次數比三個頁框時多。這種奇怪的情況稱為Belady異常現象。
計算缺頁次數
題目：某程式在記憶體中配置設定3頁，初始為空，頁面走向為4、3、2、1、4、3、5、4、3、2、1、5。計算缺頁次數。
理想置換算法的缺頁次數
替換上一次出現的頁面，
FIFO缺頁次數
先進來的頁，先出去。
最近最少使用
看最上邊的頁面走向，相比目前頁數遠的置換出去。
題目2
.在一個請求頁式存儲管理中，一個程式的頁面走向為3，4，2，1，4，5，4，3，5，1，2，并采用LRU算法。社配置設定給該程式的存儲塊數 S 分别為 3 和 4，在該通路中發生的缺頁次數 F ？
S = 3,F = 8;
S = 4,F = 7。