頁面置換算法

當發生缺頁中斷的時候, 系統會在內存中選擇一個頁面將其換出內存, 而當換出內存的時候如果該頁面的內容在內存中發生修改,則必須將該新數據重新寫回到磁盤, 然后再將需要換進的數據覆蓋掉原來的數據, 而當該數據在內存中沒有被修改的時候, 此時就直接用需要換進的內存的內容替換掉要淘汰的數據的內容.注意在換出的時候必須選擇一些使用頻率較低的頁面將其換出.
在大多數計算機中會把最近經常使用的存儲塊保存到一個高速緩存區中, 當這個高速緩存區裝滿的時候就需要選擇一些存儲塊將其丟棄

1. 最優頁面置換算法

每一個頁面用調用該頁面前所需要執行的指令數進行標記, 在進行頁面置換的時候選擇該數字最大的進行換出. 這種算法雖然性能等各方面都比較好, 但是由于操作系統無法獲知某個頁面要在什么時候被調用, 因此不能實現, 但是可以用來評估一個頁面置換算法的性能優劣

2. 先進先出頁面置換算法

在先進先出頁面置換算法中, 由操作系統維護當前內存中的頁面,并且通過鏈表的形式將其組織起來, 鏈表的前后順序按照調入內存的時間排序, 即最先調入內存的頁面處于鏈表的頭部, 當有一個新的頁面需要訪問內存的時候, 此時操作系統將處于鏈表頭部的頁面調出, 即在內存中待的最久的頁面將其調出, 然后將新的頁面插入到鏈表的尾部

3. 最近未使用頁面置換算法

????
為使得操作系統能夠獲得更多的有用信息, 系統為每一個頁面都設置了兩個狀態, 當頁面被訪問的時候設置 R 位, 當頁面被寫入的時候設置 M 位. 這些位都被放在了一個頁表項中(如上圖)每次訪問的時候更新這些位. 因此有硬件設置這些位是非常有必要的
在系統被啟動的時候, 所有的位都被清零. R 位被定期的清零, 為了區別頁面是否被訪問. 因此利用R位和M位可以將系統中的所有頁面劃分為以下三種
(0)沒有被訪問, 沒有被修改
(1)沒有被訪問, 已經被修改
(2)已經訪問, 沒有修改
(3)已經訪問, 已經修改
這樣的話, 每一個頁面都會有一個編號, 在進行頁面置換的時候, 系統往往從當前頁面中選擇一個編號最小的并且將其淘汰

4. 最近最少使用頁面置換算法

在內存中的頁面一般在很久的時間內沒有使用則該頁面在未來的很久時間內也可能被使用的幾率會特別小. 根據這個原理, 系統在進行頁面置換的時候每次從內存中選擇一個未使用時間最長的頁面將其換出.

頁面置換算法比較

局部分配策略和全局分配策略

局部分配策略就是每次在置換的時候選擇頁面在內存中生存時間最短的頁面將其換出, 而全局分配策略則是從內存中隨機的換出一個頁面. 全局分配策略比局部分配策略要好一點.

1. 頁面大小

選擇小頁面

選擇一個正文段, 數據段或者堆棧段很有可能不會恰好轉滿整個內存, 平均情況下都是最后一個頁面時空的. 多余的空間就被浪費, 這個被浪費的空間就叫做內部碎片. 總的來說,選擇小的頁面比選擇大的頁面浪費的內存會少一些, 但是選擇小的頁面也意味著內存中的頁表會變得更大, 頁面裝入頁面寄存器所花費的時間就會越長.

2. 未定義外部函數

在任何目標文件中被調用了但沒有被定義過的函數就叫做未定義函數. 如 printf 函數

3. 共享庫

如果一個程序被啟動了兩次, 大多數操作系統會自動地共享所有的代碼頁面. 依賴與不同的進程, 每一個進程都擁有一份私有的副本數據, 如果任何一個進程想要對這個副本數據進行修改, 操作系統變為這個進程將這個副本數據做一個拷貝, 這個拷貝的數據就是該進程私有的數據. 注意當一個共享庫被裝載或者使用的時候, 此時并不是將共享庫中所有的內容裝載進內存, 而是根據需要將需要的部分以也為單位將其裝入, 因此沒有被調用的函數是不會被裝載進內存的.
因此共享庫可以使得可執行文件更小, 并且節省內存.并且當我們在修改一個 bug 的時候, 如果共享庫中的一個函數被更新了, 此時不需要重新編譯這個函數程序. 就得二進制文件依然可以使用.

缺頁中斷處理

(1)硬件陷入內核, 在對應的堆棧中板寸程序計數器. 大多數機器將當前的指令各種信息保存在特殊的 CPU 寄存器中.
(2)啟動一個匯編代碼例程來保存寄存器和其他易失的信息. 這個例程往往將操作系統作為一個函數來調用.
(3)發生中斷的時候, 操作系統會嘗試發現需要哪個虛擬頁面.
(4)當知道了虛擬地址的時候, 此時操作系統便對這個地址進行檢查, 并且檢查存取和保護是否一致. 如果不一致, 則操作系統向對應的進程發送一個信號, 將該進程殺死. 如果沒有發生任何錯誤機制, 則操作系統拿著這個虛擬地址去檢查時候存在一個空閑的頁框, 如果沒有一個空閑的頁框, 那么操作系統便執行頁面置換算法尋找一個頁面將其換出.
(5)如果選擇換出的頁面被修改過, 那么系統將安排該數據寫回到磁盤, 掛起缺頁中斷的進程.
(6)如果該頁面shiganjingde,那么操作系統在磁盤中查找需要調入的頁面在磁盤中的位置, 然后將該頁面裝入到內存中. 并將發生缺頁中斷的進程掛起
(7)當磁盤訪問中斷的時候, 此時說明該頁面已經被調入到內存, 頁表已經對該頁進行相應的更新, 對應該頁表的頁框也發生了更新, 即標記為正常狀態.
(8)對缺頁中斷的指令以及程序計數器的內容做以修改.
(9)調度引起缺頁中斷的進程, 操作系統返回調用它的匯編例程
(10)恢復寄存器, 返回用戶態