目錄

一、定義

二、分類

1、最佳置換算法 / 最遠置換算法（OPT，Optimal):

1.1、定義：

1.2、例子：

2、先進先出置換算法(FIFO）:

2.1、定義：

2.2、實現(xiàn)方法：

2.3、例子：

3、最近最久未使用置換算法（LRU，least recently used):

3.1、定義：

3.2、實現(xiàn)方法：

3.3、例子：

4、時鐘置換算法是一種性能和開銷較均衡的算法，又稱CLOCK算法，或最近未用算法（NRU，NotRecently Used)

4.1、簡單的CLOCK算法實現(xiàn)方法:

4.2、例子：

5、改進型的時鐘置換算法

5.1、實現(xiàn)方式

三、總結(jié)

---

一、定義

頁面置換算法是指在操作系統(tǒng)中，當需要調(diào)入一個頁面時，若所有的物理頁面已被占用，則需要選擇一個頁面進行置換。頁面置換算法是解決內(nèi)存不足的問題，從而實現(xiàn)更多程序同時運行的重要手段之一。

二、分類

1、最佳置換算法 / 最遠置換算法（OPT，Optimal):

1.1、定義：

每次選擇淘汰的頁面將是以后永不使用，或者在最長時間內(nèi)不再被訪問的頁面，這樣可以保證最低的缺頁率。

1.2、例子：

（1）在上例中，首先依次訪問頁面，并將頁面放入內(nèi)存塊中，直到內(nèi)存塊裝滿。

（2）裝滿后，接下來要訪問的是2號頁面；

（3）根據(jù)OPT算法規(guī)則，我們依次往后查看要訪問的頁面，發(fā)現(xiàn)在0，1，7三個頁面中，頁面7是最遠會被訪問的。

（4）所以，我們就會將內(nèi)存塊中的7頁面淘汰，替換為頁面2裝入。

（5）依此類推，整個過程缺頁中斷發(fā)生了9次，頁面置換發(fā)生了6次.（前3次沒有發(fā)生頁面置換）

缺頁率：缺頁次數(shù) / 總的訪問次數(shù)

注意：缺頁時未必發(fā)生頁面置換。若還有可用的空閑內(nèi)存塊，就不用進行頁面置換。

2、先進先出置換算法(FIFO）:

2.1、定義：

每次選擇淘汰的頁面是最早進入內(nèi)存的頁面

2.2、實現(xiàn)方法：

把調(diào)入內(nèi)存的頁面根據(jù)調(diào)入的先后順序排成一個隊列，需要換出頁面時選擇隊頭頁面即可。

隊列的最大長度取決于系統(tǒng)為進程分配了多少個內(nèi)存塊。

2.3、例子：

（1）在上例中，首先依次訪問頁面，并將頁面放入內(nèi)存塊中，直到內(nèi)存塊裝滿。

（2）下一個訪問的是頁面0，此時就要把最早進來的頁面3淘汰。

（3）替換為頁面0.

3、最近最久未使用置換算法（LRU，least recently used):

3.1、定義：

每次淘汰的頁面是最近最久未使用的頁面

3.2、實現(xiàn)方法：

賦予每個頁面對應(yīng)的頁表項中，用訪問字段記錄該頁面自上次被訪問以來所經(jīng)歷的時間t。

當需要淘汰一個頁面時，選擇現(xiàn)有頁面中t值最大的，即最近最久未使用的頁面。

3.3、例子：

（1）在上例中，首先依次訪問頁面，并將頁面放入內(nèi)存塊中，直到內(nèi)存塊裝滿。

（2）一直訪問，直到訪問到頁面3時。

（3）在此之前，我們依次訪問過了7，2，1，8，所以7是最久沒有被訪問的。

（4）所以將7替換為3.

4、時鐘置換算法是一種性能和開銷較均衡的算法，又稱CLOCK算法，或最近未用算法（NRU，NotRecently Used)

4.1、簡單的CLOCK算法實現(xiàn)方法:

1. 為每個頁面設(shè)置一個訪問位，再將內(nèi)存中的頁面都通過鏈接指針鏈接成一個循環(huán)隊列。
2. 當某頁被訪問時，其訪問位置為1。當需要淘汰一個頁面時，只需檢查頁的訪問位。
3. 如果是0，就選擇該頁換出;如果是1，則將它置為0，暫不換出，繼續(xù)檢查下一個頁面，若第一輪掃描中所有頁面都是1，則將這些頁面的訪問位依次置為O后，再進行第二輪掃描（第二輪掃描中一定會有訪問位為0的頁面，因此簡單的CLOCK算法選擇一個淘汰頁面最多會經(jīng)過兩輪掃描)

4.2、例子：

（1）若我們有如上例子，且有5個內(nèi)存塊，在依次訪問了1，3，4，2，5后，我們會得到如下視圖

????????

（2）此時這幾個內(nèi)存塊都被訪問過，所以它們的訪問位都為1.

（3）我們從1號頁面依次掃描，而且要將經(jīng)過的訪問位為1的頁面的訪問位改為0，并且找到訪問位為0的頁面。

（4）在上圖中，我們找了一圈也沒有找到訪問位為0的頁面，而且我們將它全部重置為0了。

（5）然后我們進行第二次掃描，發(fā)現(xiàn)1號頁為0，所以淘汰它，并且替換為6號頁

（6）接下來訪問3，4，7；

因為有3號頁了，所以指針不動，只是將3號頁的訪問位改為1；

4號頁同樣如此。

（7）然后訪問7，此時轉(zhuǎn)動指針，將3，4的訪問位改為0；而且找到了2號頁的訪問位為0；所以將7號頁存到下方。

5、改進型的時鐘置換算法

5.1、實現(xiàn)方式

（1）和簡單時鐘置換算法相似，其實就是將找0，改為了找（0，0）；

（2）只不過第一輪并不會相簡單的那樣將1改為0；

（3）而是，如果第一輪沒有找到（0，0），就會將（0，1）看作（0，0）進行淘汰。

（4）在第二輪的查找中，會將訪問位重置為0

（5）找到為（0，0）的頁淘汰

（6）若是如下例子

（7）第一輪掃描（0，0），發(fā)現(xiàn)都不是。

（8）第二輪掃描（0，1），且被掃描過的頁面的訪問位都會被置為0

（9）第三輪掃描（0，0），沒找到，不改變什么

（10）第四輪掃描，將（0，1）當作（0，0）淘汰

三、總結(jié)