繼續(xù)重溫操作系統(tǒng)系列知識，頁面置換的三種常見算法為：LRU（最近最久未使用）、FIFO（先進(jìn)先出）、最佳置換。

部分公司的面試會考到LRU的知識。

LRU置換算法

所謂LRU置換算法，單看字面意思較為麻煩，實際上在進(jìn)行頁面置換的過程中，被替換的頁面塊只需要按照“很久之前使用了，但最近沒有使用”的規(guī)則進(jìn)行選取就可以了。不需要考慮后續(xù)頁面走向是否又需要讀入符合上述規(guī)則的頁面，因為這正是LRU的缺點。

最佳置換算法

這種算法選取被替換頁面的時候，遵循以下兩點

1.某個頁面后續(xù)走向永遠(yuǎn)不會訪問到，所以它可以直接被置換。

2.某個頁面需要過很久才會訪問到，優(yōu)先替換它。

這種算法的優(yōu)點是理論上缺頁率比較低。

先進(jìn)先出算法

替換規(guī)則為替換當(dāng)前走向所有的物理塊中那個最早進(jìn)入的頁面。

例題

假設(shè)存在一個走向，4，1，2，5，3，4，6，3，1，2。當(dāng)分配的物理塊M=4時，分別求FIFO、LRU、最佳置換算法的頁面走向（假設(shè)初始時為空塊）。

例題LRU解法

LRU表

走向	4	1	2	5	3	4	6	3	1	2
塊1	4	4	4	4	3	3	3	3	3	3
塊2		1	1	1	1	4	4	4	4	2
塊3			2	2	2	2	6	6	6	6
塊4				5	5	5	5	5	1	1
缺頁	√	√	√	√	√	√	√		√	√
置換					√	√	√		√	√

（1）.對于LRU，首先按照順序填好走向，并填滿前面的物理塊，與其他算法一樣。

很顯然在一開始每次都需要調(diào)入所需頁面。因此，前面幾次都是缺頁，但沒有產(chǎn)生置換。

（2）.開始進(jìn)入置換過程。

對于接下來的走向頁面3而言，塊中無3說明缺頁，塊中已滿調(diào)入3則說明需要置換。

通過觀察我們可以得知最近的頁面，無論是4、1、2、5，都只是調(diào)用了一次，因此我們需要替換最久未使用的4。

但有的時候并不會這么簡單，那如果走向不再是4125，而是是4、1、4、5呢？有2個4，還要不要替換4？

那么答案是：則應(yīng)該替換1，因為雖然4是最早入塊的，但是最近4使用過，所以不再是最久未使用的。排除4后1最久未使用，5剛剛使用過。

本題走向為4、1、2、5，因此走向3的塊序列為3、1、2、5.

對于接下來的走向頁面4而言，因為上一次的序列為3、1、2、5很顯然沒有4，但又滿物理塊，所以既置換又缺頁。

按照剛剛的示例，在前面的走向4、1、2、5、3中，很顯然最久未使用的是1，所以需要替換1.

因此走向4的塊序列為3、4、2、5.

對于接下來的走向6而言，最近最久未使用的是2（其實可以觀察2和5的長度，在3、4、2、5中，又無重復(fù)項目，而2是最久未使用的）。所以替換2.

結(jié)果是3、4、6、5，很顯然缺頁6又置換2。

對于接下來的走向3而言，存在3，所以不需要置換、也不缺頁。

對于1而言，最近的序列為（3、4、6、5），觀察發(fā)現(xiàn)5和3的序列橫向一樣長，然而3剛剛調(diào)用過，所以需要替換5.

結(jié)果為3、4、6、1

對于接下來的走向2而言，我們發(fā)現(xiàn)最近的序列為（3、4、6、1），通過觀察可以發(fā)現(xiàn)4-3-6-1走向中4最久未使用，所以替換4.

結(jié)果為3、2、6、1.

最終我們填寫了整個LRU的置換表。

例題FIFO算法

走向	4	1	2	5	3	4	6	3	1	2
塊1	4	4	4	4	3	3	3	3	3	2
塊2		1	1	1	1	4	4	4	4	4
塊3			2	2	2	2	6	6	6	6
塊4				5	5	5	5	5	1	1
缺頁	√	√	√	√	√	√	√		√	√
置換					√	√	√		√	√

按照先進(jìn)的先被替換，雷打不動，就可以做出了，這道題答案基本上和LRU一樣，就是最后一個走向有些區(qū)別。

解題時候遇到重復(fù)性的走向容易出錯，規(guī)避即可。

例題最佳置換算法

頁面	4	1	2	5	3	4	6	3	1	2
塊1	4	4	4	4	4	4	6
塊2		1	1	1	1	1	1
塊3			2	2	2	2	2
塊4				5	3	3	3
缺頁否	√	√	√	√	√		√
置換否					√		√

對于走向3而言，我們可以看到后面的走向46312，3、1、2是最久會再次調(diào)用的，可以替換2，因為2是最后要訪問的。

那么對于走向3來說，4、1、2、5：3應(yīng)該被用于替換誰？

由于塊4的已經(jīng)入塊的5在后面是永遠(yuǎn)不會被再次調(diào)用的（46312是沒有5的），所以不替換2，要替換5.

結(jié)果為4、1、2、3.

下一個走向含有4，因此不缺頁也不置換。

接下來的走向6，很顯然走向4的頁面已經(jīng)不再需要了（后續(xù)走向無4），所以替換走向4，最終結(jié)果很巧妙，完全不缺頁也不置換。

以上就是三種常見的解法

總結(jié)

以上是生活随笔為你收集整理的操作系统：页面置换算法（LRU、FIFO、OPT）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。