頁面演算法操作系統

『壹』 操作系統原理與應用之 頁面調度演算法問題

FIFO：即先進先出演算法，就是先進去的頁在位置不夠時先淘汰。所以具體如下：
主存開始為空
訪問1，1不在主存中，產生缺頁中斷，添加，主存里現在是：1
訪問2，2不在主存中，產生缺頁中斷，添加，主存里現在是：1,2
以此類推，
1,2,3（缺頁中斷）
1,2,3,6（缺頁中斷）
訪問4，4不在主存中，缺頁中斷，主存滿了，最早的1淘汰，主存里現在是：2,3,6,4
然後3,6,4,7（缺頁中斷，2淘汰）
然後3，3在主存中，不產生中斷
然後6,4,7,2（缺頁中斷，3淘汰）
4,7,2,1（缺頁中斷，6淘汰）
4在主存中，不中斷
7在主存中，不中斷
7,2,1,5（缺頁中斷，4淘汰）
2,1,5,6（缺頁中斷，7淘汰）
5在主存中，不中斷
2在主存中，不中斷
1在主存中，不中斷
整個FIFO過程就是這樣。

LRU是最近最久未使用的先淘汰，具體如下：
1（缺頁中斷）
1,2（缺頁中斷）
1,2,3（缺頁中斷）
1,2,3,6（缺頁中斷）
2,3,6,4（缺頁中斷，1最久沒用過，淘汰）
3,6,4,7（缺頁中斷，2最久沒用過，淘汰）
3在主存中，不中斷，3最近使用過，主存中順序調整為6,4,7,3
4,7,3,2（缺頁中斷，6最久沒用過，淘汰）
7,3,2,1（缺頁中斷，4最久沒用過，淘汰）
3,2,1,4（缺頁中斷，7最久沒用過，淘汰）
2,1,4,7（缺頁中斷，3最久沒用過，淘汰）
1,4,7,5（缺頁中斷，2最久沒用過，淘汰）
4,7,5,6（缺頁中斷，1最久沒用過，淘汰）
5在主存中，調整順序為4,7,6,5
7,6,5,2（缺頁中斷，4最久沒用過，淘汰）
6,5,2,1（缺頁中斷，7最久沒用過，淘汰）
整個LRU過程就是這樣。

全手打求採納謝謝~！如有問題請追問~

『貳』 操作系統頁面置換演算法：第二次機會演算法是什麼

第二次機會演算法：

與FIFO、OPT、LRU、NRU等同為操作系統中請求分頁式管理方式的頁面置換演算法。

第二次機會演算法的基本思想是與FIFO相同的，但是有所改進，避免把經常使用的頁面置換出去。當選擇置換頁面時，依然和FIFO一樣，選擇最早置入內存的頁面。但是二次機會法還設置了一個訪問狀態位。所以還要檢查頁面的的訪問位。如果是0，就淘汰這頁；如果訪問位是1，就給它第二次機會，並選擇下一個FIFO頁面。當一個頁面得到第二次機會時，它的訪問位就清為0，它的到達時間就置為當前時間。如果該頁在此期間被訪問過，則訪問位置為1。這樣給了第二次機會的頁面將不被淘汰，直至所有其他頁面被淘汰過（或者也給了第二次機會）。因此，如果一個頁面經常使用，它的訪問位總保持為1，它就從來不會被淘汰出去。

第二次機會演算法可視為一個環形隊列。用一個指針指示哪一頁是下面要淘汰的。當需要一個存儲塊時，指針就前進，直至找到訪問位是0的頁。隨著指針的前進，把訪問位就清為0。在最壞的情況下，所有的訪問位都是1，指針要通過整個隊列一周，每個頁都給第二次機會。這時就退化成FIFO演算法了。