作業系統--存儲管理4

-----頁面置換算法------

1.概念：當出現缺頁異常的時候，并且記憶體中的空閑頁面也用完，

此時必須把進行外存與記憶體的一個頁面置換。

頁面置換算法的功能：選擇合适的頁面進行置換。

2.置換算法追求的目标

* 盡可能減少頁面置換的次數

* 将未來不用/短時間内不使用的頁面換出。

注意：置換算法要考慮的是整個記憶體中所有程序執行的性能-并不隻是某個程序

3.頁面鎖定：記憶體中不能被置換的頁面

* 描述必須常駐記憶體的邏輯頁面

* 作業系統核心頁面

* 要求響應速度的代碼和資料

* 頁表中的鎖定标志位

4.置換算法的評價方法

記錄程序通路記憶體頁面的軌迹，模拟置換算法，記錄缺頁次數

5.頁面置換算法的分類

局部置換算法：每個程序配置設定的頁面個數确定，置換隻會發生在自己的所屬頁面

全局置換算法：置換頁面是所有可能被置換的頁面

6.局部置換算法--程序配置設定的頁面數固定

最優算法：預測未來最長時間不會使用的頁面--看的是後面的通路情況

OPT特點：缺頁最少，但是是理想情況，實際系統無法預測未來的通路序列

可以作為其他置換算法的評價标準

先進先出：按照時間順序置換，但是這個并不能保證是和程式的通路特性一緻

其實根據的是隊列的特性--時間。置換在記憶體中駐留時間最長的

FIFO實作：維護一個連結清單：鍊頭放時間最長，剛進來的頁面放在鍊尾

先進先出特點:實作簡單;性能較差;增加程序頁面個數,缺頁率不一定會減少

(Belady現象)很少會單獨使用該算法

最近最久未用算法：統計過去的通路特征，預測未來通路情況--算法過于複雜

OPT的近似。選擇最近最久未通路的頁面被置換

(LRU):依據最近最久沒通路的頁面在未來一段時間也不會通路

記錄每個頁面上次通路的時間，到現在的時間差

最大的一個頁面被置換出來。

LRU實作:1.系統維護一個按照最近一次通路時間順序的頁面連結清單；

鍊頭是剛剛通路的頁面，鍊尾巴是最近未通路的；

通路時候将剛通路的頁面置于鍊頭，缺頁置換鍊尾的頁面。

2.維護一個活動頁面棧

通路頁面時候壓棧頂并将相同的頁面删除

缺頁時候置換棧底的頁面

LRU實作過程：開銷比較大

時鐘算法Clock：對LRU近似+FIFO綜合;僅對頁面通路情況進行大緻的統計

僅僅記錄頁面是否被通路；沒通路的頁面按照進來的先後

順序進行置換出去。

Clock資料結構：在頁表項中增加通路位；把頁面組織成環形連結清單

指針指向最先調入的頁表

算法實作：頁面裝入的時候：通路位0；頁面通路的時候，通路位1；

缺頁時候指針從目前位置順序查找環形連結清單

通路位位0，就置換該頁面，新放入頁面為1

通路位為1；則通路位置0;并移動到下一個頁面直到找到

通路位為0可以被置換的頁面。

特點：是在LRU和FIFO中做折中

改進的Clock: 減小修改頁面的處理開銷：對于修改的頁面不進行替換

在頁表項目：定義一個修改位；修改過1；未修改就0

改進的Clock思路：在通路頁面的時候進行相應的修改

缺頁，修改頁面标志位，以跳過有修改的頁面

對于修改過的頁面寫回操作會被統一操作

最不常用算法IFU：對LRU近似;缺頁時候，置換的是最少次數通路的頁面

實作：為每個頁面設定計數，缺頁時候，置換出計數小的

特點：算法開銷大；開始頻繁使用的頁面，但是以後不使用就

難以被置換出去，通過定期對這些頁面的計數減小。、

7.局部置換算法的特征

1.belady現象：配置設定給程序頁面數增加，可能就出現缺頁次數增加

産生的原因：FIFO算法的置換特征與程序通路的動态特征沖突

被置換出去的頁面可能程序下次還會要通路

産生belady的算法：FIFO

2.LRU,FIFO,CLOCK比較

LRU算法性能好，但是系統開銷大(動态調整頁面的順序)

FIFO系統開銷小，但是會産生Belady現象(不進行動态調整)

CLOCK是它們的折中；在通路的過程中通過标準描述動态的關系

8.全局置換算法

局部置換算法并沒有考慮到程序的通路差異

思路：為程序配置設定可變數目的實體頁面

在不同階段為程序配置設定不同數目的實體頁面

算法：如何确定給程序配置設定多少頁面

程序個數與CPU使用率存在一個關系：前邊是正比，但是存在極限限制

引入工作集：一個程序目前正在使用的邏輯頁面的集合。w(t,V)

w(t,V):指的是目前時間之前的時間很短，通路頁面的集合；工作集大小可變

工作集變化規律：不同的階段工作集大小不同

常駐集：在目前時刻，程序實際駐留記憶體的頁面集合。

工作集與常駐集的關系：

工作集是程序運作過程的固有特性

常駐集是取決于系統配置設定給程序的實體頁面和頁面置換算法

常駐集包含于工作集：缺頁少

工作集發在劇烈變化，缺頁多

程序的常駐集大小達到一定數目；缺頁率不會明顯下降

工作集算法：可以了解為最優算法在全局置換的展現

思路：換出不在工作集中的頁面

實作：通路連結清單：維護視窗内的訪存頁面連結清單

訪存時候換出不在工作集中的；更新連結清單

缺頁時候，換入，更新連結清單

缺頁率置換算法：缺頁率定義：兩次缺頁時間間隔的倒數

影響缺頁率原因：頁面置換算法

配置設定給程序的頁面數目

頁面大小

程式的編寫方法

缺頁率置換算法： 訪存的時候設定标志

缺頁的時候計算時間間隔；>T置換未被引用<=T加入工作集

抖動和負載控制

抖動：程序擁有的實體頁面過少，不能包含工作集

造成大量缺頁，頻繁置換

程序運作速度變慢

産生抖動原因：記憶體中的程序數，每個程序擷取的頁面個數

作業系統需要在并發和缺頁率之間做折中

負載控制:通過控制并發程序數來進行系統的負載控制