【文章內(nèi)容簡介】 況 頁面預先裝入 先進先出置換算法舉例說明 40 2022年 8月 21日星期日 北京交通大學計算機學院 頁面置換算法 抖動與缺頁率 最佳置換算法 先進先出置換算法 最近最久未使用置換算法 Clock置換算法 最少使用置換算法 頁面緩沖算法 41 2022年 8月 21日星期日 北京交通大學計算機學院 最近最久未使用置換算法 LRU ? Least Recently Used ? 基本思想 ? 以“最近的過去”作為“最近的將來”的近似，選擇最近一段時間最長時間未被訪問的頁面淘汰出內(nèi)存 ? 評價 ? 適用于各種類型的程序，性能較好，但需要較多的硬件支持 42 2022年 8月 21日星期日 北京交通大學計算機學院 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 7 7 2 2 2 2 4 4 4 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 3 3 3 3 3 3 0 0 0 0 0 1 1 1 3 3 3 2 2 2 2 2 2 2 2 2 7 7 7 ? 某進程分配獲得三個物理塊 ? 缺頁中斷次數(shù)為 9次，缺頁率 45% 頁面訪問序列 內(nèi)存頁面分布情況 頁面預先裝入 最近最久未使用置換算法舉例說明 43 2022年 8月 21日星期日 北京交通大學計算機學院 LUR置換算法實現(xiàn) ? 軟件實現(xiàn)的問題 ? 需要用操作系統(tǒng)軟件來更新頁面訪問時間。假設每個頁面對應一個 2個字節(jié)的訪問時間字段（沒有硬件支持該字段的更新）。那么每次內(nèi)存訪問都需要用軟件修改該時間字段（需要多大的開銷？）。頁面置換時，又需要選擇其中最早的頁面進行置換。 44 2022年 8月 21日星期日 北京交通大學計算機學院 最近最久未使用置換算法硬件支持 —移位寄存器 B R R7 R6 R5 R4 R3 R2 R1 R0 1 0 1 0 1 0 0 1 0 2 1 0 1 0 1 1 0 0 3 0 0 0 0 1 1 0 0 4 0 1 1 0 1 0 1 1 5 1 1 0 1 0 1 1 0 6 0 0 1 0 1 0 1 1 7 0 0 0 0 0 1 1 1 8 0 1 1 0 1 1 0 1 45 2022年 8月 21日星期日 北京交通大學計算機學院 最近最久未使用置換算法硬件支持 —棧 4 4 7 4 7 0 7 4 0 7 0 4 7 1 7 0 4 1 0 1 7 4 0 1 0 7 4 1 2 1 0 7 4 2 1 2 0 7 4 1 2 1 0 7 4 2 6 2 1 0 7 6 ? 某進程分配獲得五個物理塊 頁面訪問序列 46 2022年 8月 21日星期日 北京交通大學計算機學院 頁面置換算法 抖動與缺頁率 最佳置換算法 先進先出置換算法 最近最久未使用置換算法 Clock置換算法 最少使用置換算法 頁面緩沖算法 47 2022年 8月 21日星期日 北京交通大學計算機學院 clock置換算法實現(xiàn) ? 利用頁表中的訪問字位、修改位 ? 不需要額外硬件 頁號 物理塊號 狀態(tài)位 訪問位 修改位 外存地址 48 2022年 8月 21日星期日 北京交通大學計算機學院 簡單 Clock置換算法 (NRU) 塊號 頁號 頁面 訪問位 指針 0 1 2 4 0 3 4 2 1 5 6 5 0 7 1 1 查尋指針 入口 返回 查尋指針 前移指向下一表目 選擇該頁淘汰 頁面訪問位 =0？ 置頁面 訪問位為 0 是 否 49 2022年 8月 21日星期日 北京交通大學計算機學院 改進型 Clock置換算法 ? 基本思想 ① 從查尋指針當前位置起掃描內(nèi)存分頁循環(huán)隊列，選擇 A=0且 M=0的第一個頁面淘汰；若未找到，轉② ② 開始第二輪掃描，選擇 A=0且 M=1的第一個頁面淘汰，同時將經(jīng)過的所有頁面訪問位置 0；若不能找到，轉① ? 評價 ? 與簡單 Clock算法相比，可減少磁盤的 I/O操作次數(shù)，但淘汰頁的選擇可能經(jīng)歷多次掃描，故實現(xiàn)算法自身的開銷增大 50 2022年 8月 21日星期日 北京交通大學計算機學院 頁面置換算法 抖動與缺頁率 最佳置換算法 先進先出置換算法 最近最久未使用置換算法 Clock置換算法 最少使用置換算法 頁面緩沖算法 51 2022年 8月 21日星期日 北京交通大學計算機學院 最少使用置換算法 LFU ? 基本思想 ? 選擇在最近時期使用次數(shù)最少的頁面淘汰 B R R7 R6 R5 R4 R3 R2 R1 R0 1 0 1 0 1 0 0 1 0 2 1 0 1 0 1 1 0 0 3 0 0 0 0 1 1 0 0 4 0 1 1 0 1 0 1 1 5 1 1 0 1 0 1 1 0 6 0 0 1 0 1 0 1 1 7 0 0 0 0 0 1 1 1 8 0 1 1 0 1 1 0 1 52 2022年 8月 21日星期日 北京交通大學計算機學院 最少使用置換算法 LFU ? 評價 ? 鑒于僅用移位寄存器有限各位來記錄頁面使用會導致訪問一次與訪問多次的等效性（寄存器在 100ms右移一位，那么在這段時間內(nèi)，多次訪問與一次訪問的效果一樣）。本算法并不能真實全面地反映頁面使用情況 53 2022年 8月 21日星期日 北京交通大學計算機學院 頁面置換算法 抖動與缺頁率 最佳置換算法 先進先出置換算法 最近最久未使用置換算法 Clock置換算法 最少使用置換算法 頁面緩沖算法 54 2022年 8月 21日星期日 北京交通大學計算機學院 頁面緩沖算法 PBA ? 完全正確的預測頁面將來的使用情況是困難的，錯誤在所難免。 ? 基本思想 ? 設立淘汰頁面的緩沖區(qū)。將準備淘汰的頁面暫時存放在該緩沖區(qū)中，如果一段時間后沒有再次使用，則依次淘汰；否則，則回到已裝入頁面表中。 55 2022年 8月 21日星期日 北京交通大學計算機學院 頁面緩沖算法 PBA ? 實現(xiàn)方法 ? 設立空閑頁面鏈表和已修改頁面鏈表 ? 初始化時，空閑頁面鏈表包括系統(tǒng)中所有空閑頁。一個進程創(chuàng)建時分配一定數(shù)量的物理塊。 ? 缺頁中斷時，如果該頁不在緩沖區(qū)中，需要從空閑頁面鏈表的表頭取一個空閑物理塊分配給正在訪問的缺頁。同時，將采用 FIFO算法將該進程最早調(diào)入內(nèi)存的物理塊號（未修改）插入空閑頁表尾部或（該頁已修改）已修改頁面鏈表尾部。 ? 缺頁中斷時，如果該頁還在緩沖區(qū)中，則將物理塊號從緩沖隊列中刪除，并插入進程頁表中。 56 2022年 8月 21日星期日 北京交通大學計算機學院 頁面緩沖算法 PBA ? 實現(xiàn)方法 ? 根據(jù)進程缺頁率變化，修改一個進程的可分配物理塊數(shù)。即采用可變分配和基于先進先出的局部置換策略 ? 當已修改頁面鏈表達到一定長度如 64個頁面時，一起將所有已修改頁面寫回磁盤，故可顯著減少磁盤 I/O操作次數(shù) 57 2022年 8月 21日星期日 北京交通大學計算機學院 頁面置換算法 抖動與缺頁率 最佳置換算法 先進先出置換算法 最近最久未使用置換算法 Clock置換算法 最少使用置換算法 頁面緩沖算法 Thrashing ? If a process does not have “enough” pages, the pagefault rate is very high. This leads to: ? low CPU utilization ? operating system spends most of its time swapping to disk