作業系統（五）頁面置換算法與配置設定政策
一、頁面置換算法
1、最佳置換算法（OPT）
- 每次選擇淘汰的頁面将是以後永不使用，或者在最長時間内不再被通路的頁面，這樣可以保證最低的缺頁率
實際上就是
從目前記憶體塊的頁面中淘汰一個最後出現的頁面
。
- 最佳置換算法是缺頁率最低的算法
- 由于程序運作中無法擷取程序要通路的全部頁面，是以最佳置換算法是無法實作的
2、先進先出置換算法（FIFO）
- 把調入記憶體的頁面形成一個隊列，每次發生置換時選擇隊頭頁面即可
- 實作簡單
- 算法性能差
- 會産生Belady異常（當為程序配置設定的實體塊增大時，缺頁次數不減反增）
3、最近最久未使用算法（LRU）
- 每次淘汰最近最久沒有使用的頁面
- 性能好
- 實作困難，需要專門的硬體支援，開銷大
4、時鐘置換算法（CLOCK）
- 又稱最久未用算法（NRU）
為每個頁面設定一個通路位，首先在頁面中選擇通路位為0的頁面，并将通路位為1的頁面置為0
- 性能與開銷比較均衡
- 未考慮頁面是否被修改
5、改進型時鐘置換算法
- 如果一個頁面在通路過程中被修改了，那麼它需要執行I/O操作寫回外存，是以在其他條件相同時，應該優先淘汰未修改的頁面
為每個頁面增加一個修改位
1.尋找标志位為（0,0）即最近未通路未修改的頁面
2.尋找标志位為（0,1）即最近未通路但修改過的頁面，并将掃描過的頁面的通路位設為0
3.尋找标志位為（0,0）即最近通路過但未修改過的頁面
4.尋找标志位為（0,1）即最近通路過且修改過的頁面
個人覺得這樣設計的依據是根據局部性原理，最近通路過的頁面接下來也可能被通路，是以會優先淘汰未通路的
6、小結
- OPT算法是無法實作的
- 隻有FIFO算法會導緻Belady異常
二、頁面配置設定政策
1、駐留集
指請求分頁存儲管理中給程序配置設定的實體塊的集合
- 駐留集太小，會導緻缺頁頻繁，系統會花費大量的時間去處理缺頁
- 駐留集太大，會導緻多道程式并發度下降，資源使用率低
2、頁面配置設定、置換政策
固定配置設定：作業系統給程序配置設定的實體塊數目在程序運作期間固定不變，即駐留集大小不變
可變配置設定：駐留集大小可變
局部置換：發生缺頁時隻能選擇程序自己的實體塊進行替換
全局替換：可以将作業系統保留的空閑實體塊配置設定給缺頁程序，也可以将别的程序持有的實體塊置換到外存，再配置設定給缺頁程序
3、調入頁面的時機
4、從何處調頁
5、抖動（颠簸）現象
剛剛換出的頁面馬上又要換入記憶體，剛剛換入的頁面又要馬上換出外存，這種頻繁的頁面排程行為稱為抖動或颠簸
6、工作集
基于工作集的可變配置設定方式的最大視窗尺寸一般是視窗尺寸+1
工作集指在某段時間間隔裡，程序實際通路頁面的集合。
7、小結
- 系統為某程序配置設定了n個實體塊等價于系統為該程序配置設定的駐留集大小為n
- 不存在固定配置設定全局置換，因為固定配置設定程序的駐留集大小是不會改變的，是以一定不會發生全局置換