- 最佳置換算法
- 先進(jìn)先出(FIFO)置換算法
- 最近最少未使用(LRU)算法
1.最佳置換算法（理想化算法）
淘汰最久不被訪問的頁(yè)面
例題：
系統(tǒng)為某進(jìn)程分配3個(gè)物理塊，進(jìn)程訪問頁(yè)面的順序是0撩幽，7秧秉，6淑蔚，5必尼，7屈尼，4，7艺挪，3不翩，5，4麻裳，7，4器钟，5津坑，6，5傲霸，7疆瑰，6，0昙啄，7穆役，6
| 訪問頁(yè)面 | 0 | 7 | 6 |
|---|---|---|---|
| 物理塊 | 0 | 0 | 0 |
| 7 | 7 | ||
| 6 |
接下來(lái)，最佳置換算法的語(yǔ)法就是淘汰最久不被訪問的梳凛，所以下一個(gè)進(jìn)入的數(shù)字是5
（為什么是5耿币，因?yàn)榭吹筋}目的進(jìn)程訪問頁(yè)面順序了嗎，就是按著0韧拒，7淹接，6十性，5，7....的順序來(lái)訪問的）塑悼，
那么物理塊就只有三個(gè)劲适，分別放著0，7厢蒜，6霞势；那么5要進(jìn)來(lái)，就只能淘汰掉0斑鸦，7愕贡，6中的其中一個(gè)，
（為什么鄙才？因?yàn)槲锢韷K只有三個(gè)颂鸿，只能放三個(gè)頁(yè)面啊Ｔ茆帧Ｗ旆摹！）
那么問題來(lái)了浓冒？我5要進(jìn)來(lái)栽渴，我是要淘汰誰(shuí)啊稳懒？
我們用的是最佳頁(yè)面置換算法闲擦，這個(gè)算法的
語(yǔ)法就是，淘汰掉最久不被訪問的那個(gè)场梆，
那么我們來(lái)看一下
0墅冷，7，6我要淘汰最久沒被訪問的頁(yè)面或油，那么我們看訪問頁(yè)面的順序寞忿，會(huì)發(fā)現(xiàn)
0在第18次再訪問，
7在第5 次再訪問顶岸，
6在第14次再訪問腔彰，
所以，我們要置換掉0辖佣，因?yàn)? 是最久未的訪問的
結(jié)果：
| 訪問頁(yè)面 | 0 | 7 | 6 | 5 |
|---|---|---|---|---|
| 物理塊 | 0 | 0 | 0 | 5 |
| 7 | 7 | 7 | ||
| 6 | 6 |
按照這樣的規(guī)律就可以最后得到以下的結(jié)果:
| 訪問頁(yè)面 | 0 | 7 | 6 | 5 | 7 | 4 | 7 | 3 | 5 | 4 | 7 | 4 | 5 | 6 | 5 | 7 | 6 | 0 | 7 | 6 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 物理塊 | 0 | 0 | 0 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 0 | 0 | 0 |
| 7 | 7 | 7 | 7 | 7 | 7 | 3 | 3 | 3 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | ||
| 6 | 6 | 6 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | |||
| 缺頁(yè)中斷 | × | × | × | × | × | × | × | × | × |
接下來(lái)霹抛，我們需要了解一個(gè)新的概念
缺頁(yè)中斷：在請(qǐng)求分頁(yè)系統(tǒng)中，可以通過(guò)查詢頁(yè)表中的狀態(tài)位來(lái)確定所要訪問的頁(yè)面是否存在于內(nèi)存中卷谈。每當(dāng)所要訪問的頁(yè)面不在內(nèi)存時(shí)杯拐，會(huì)產(chǎn)生一次缺頁(yè)中斷，此時(shí)操作系統(tǒng)會(huì)根據(jù)頁(yè)表中的外存地址在外存中找到所缺的一頁(yè)藕施，將其調(diào)入內(nèi)存。
舉個(gè)通俗的例子:上表有三個(gè)物理塊矛市，每次往物理塊添加數(shù)據(jù)就會(huì)產(chǎn)生一次缺頁(yè)中斷,ok，上表也寫上了
所以上表一共發(fā)生9次缺頁(yè)中斷
頁(yè)面置換：就是有頁(yè)面被置換诲祸，所以上表中頁(yè)面置換是6次
(一開始三個(gè)物理塊都是空的浊吏，添加進(jìn)076救氯，發(fā)生三次缺頁(yè)中斷，0次頁(yè)面置換着憨，后來(lái)的就會(huì)發(fā)生缺頁(yè)中斷的同時(shí)也會(huì)發(fā)生頁(yè)面置換墩衙，因?yàn)槿齻€(gè)物理塊沾滿了嗎，所以每添加進(jìn)新的頁(yè)面就只能是置換了)
2.先進(jìn)先出(FIFO)置換算法
聞其名知其意甲抖，這個(gè)算法就是先進(jìn)入的頁(yè)面先被淘汰
Belady想象：一般來(lái)說(shuō)分配的物理塊越多漆改，發(fā)生的缺頁(yè)越少准谚，但是FIFO就是這么奇葩，有時(shí)候分配的物理塊多了樊破，但缺頁(yè)反而增多唆铐，這就是所謂的Belady現(xiàn)象
3.最近最少未使用(LRU)算法
算法：LRU這個(gè)算法的名字很多，也有一種叫法叫做最近最久未使用置換算法艾岂，這個(gè)名字比較好，因?yàn)槁勂涿椭肋@個(gè)算法怎么搞
這個(gè)算法就是看在物理塊中的頁(yè)面澳盐，哪個(gè)是最久沒有被使用的令宿，就把它over掉
接下來(lái)來(lái)看看例題
| 訪問頁(yè)面 | 2 | 3 | 4 | 1 |
|---|---|---|---|---|
| 物理塊 | 2 | 3 | 4 | |
| 2 | 3 | |||
| 2 |
看上面的表粒没，接下來(lái)這個(gè)1要添加到哪里呢？
432要淘汰那個(gè)呢？
看這個(gè)算法怎么說(shuō)：淘汰最近最久未使用的入蛆，
首先我們先來(lái)看看我們最近使用的是432硕勿，那么在這個(gè)432里面最近最久沒使用的就是2，因?yàn)?第一個(gè)添加進(jìn)來(lái)源武，接下來(lái)34，都沒有使用到2话浇，所以2就是最近最久未使用的闹究，
所以就淘汰2
所以
| 訪問頁(yè)面 | 2 | 3 | 4 | 1 |
|---|---|---|---|---|
| 物理塊 | 2 | 3 | 4 | 1 |
| 2 | 3 | 4 | ||
| 2 | 3 |
ok，接下來(lái)赏寇，這個(gè)最近最久未使用的算法懂了把
