【正文】 22年 8月 21日星期日 北京交通大學(xué)計算機學(xué)院 請求分頁存儲管理方式 請求分頁中的硬件支持 內(nèi)存分配策略和分配算法 調(diào)頁策略 頁面置換算法 32 2022年 8月 21日星期日 北京交通大學(xué)計算機學(xué)院 頁面置換算法 抖動與缺頁率 最佳置換算法 先進(jìn)先出置換算法 最近最久未使用置換算法 Clock置換算法 最少使用置換算法 頁面緩沖算法 33 2022年 8月 21日星期日 北京交通大學(xué)計算機學(xué)院 抖動與缺頁率 ? 抖動的定義 ? 如果所用置換算法不當(dāng)，便可能導(dǎo)致這樣一種情形：剛被換出的頁面很快又被訪問，需重新調(diào)入，為此，又需再選一頁換出；而此剛被換出的頁面，不久也被訪問，故又需將它調(diào)入，如此頻繁地更換頁面，以致一個進(jìn)程在運行中把大部分的時間耗費在頁面置換的工作上，稱該進(jìn)程發(fā)生了抖動（或稱之為顛簸） ? 缺頁率 ? 缺頁率 = 缺頁中斷次數(shù) /頁面訪問次數(shù) 34 2022年 8月 21日星期日 北京交通大學(xué)計算機學(xué)院 頁面置換算法 抖動與缺頁率 最佳置換算法 先進(jìn)先出置換算法 最近最久未使用置換算法 Clock置換算法 最少使用置換算法 頁面緩沖算法 35 2022年 8月 21日星期日 北京交通大學(xué)計算機學(xué)院 最佳置換算法 ? 基本思想 ? 選擇永不使用或是在最長時間內(nèi)不再被訪問（即距現(xiàn)在最長時間才會被訪問）的頁面淘汰出內(nèi)存 ? 評價 ? 理想化算法，具有最好性能（對于固定分配頁面方式，本法可保證獲得最低的缺頁率），但實際上卻難于實現(xiàn)，故主要用于算法評價參照 36 2022年 8月 21日星期日 北京交通大學(xué)計算機學(xué)院 最佳置換算法舉例說明 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 2 2 2 2 2 2 2 2 2 2 7 7 7 0 0 0 0 0 0 4 4 4 0 0 0 0 0 0 0 0 0 0 1 1 1 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1 ? 某進(jìn)程分配獲得三個物理塊 ? 缺頁中斷次數(shù)為 6次，缺頁率 30% 頁面訪問序列 內(nèi)存頁面分布情況 頁面預(yù)先裝入 37 2022年 8月 21日星期日 北京交通大學(xué)計算機學(xué)院 頁面置換算法 抖動與缺頁率 最佳置換算法 先進(jìn)先出置換算法 最近最久未使用置換算法 Clock置換算法 最少使用置換算法 頁面緩沖算法 38 2022年 8月 21日星期日 北京交通大學(xué)計算機學(xué)院 先進(jìn)先出置換算法 ? 基本思想 ? 選擇最先進(jìn)入內(nèi)存即在內(nèi)存駐留時間最久的頁面換出到外存 ? 進(jìn)程已調(diào)入內(nèi)存的頁面按進(jìn)入先后次序鏈接成一個隊列，并設(shè)置替換指針以指向最老頁面 ? 評價 ? 簡單直觀，但不符合進(jìn)程實際運行規(guī)律，性能較差，故實際應(yīng)用極少 39 2022年 8月 21日星期日 北京交通大學(xué)計算機學(xué)院 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 0 0 0 0 7 7 7 0 0 0 0 3 3 3 2 2 2 2 2 1 1 1 1 1 0 0 1 1 1 1 0 0 0 3 3 3 3 3 2 2 2 2 2 1 ? 某進(jìn)程分配獲得三個物理塊 ? 缺頁中斷次數(shù)為 12次，缺頁率 60% 頁面訪問序列 內(nèi)存頁面分布情況 頁面預(yù)先裝入 先進(jìn)先出置換算法舉例說明 40 2022年 8月 21日星期日 北京交通大學(xué)計算機學(xué)院 頁面置換算法 抖動與缺頁率 最佳置換算法 先進(jìn)先出置換算法 最近最久未使用置換算法 Clock置換算法 最少使用置換算法 頁面緩沖算法 41 2022年 8月 21日星期日 北京交通大學(xué)計算機學(xué)院 最近最久未使用置換算法 LRU ? Least Recently Used ? 基本思想 ? 以“最近的過去”作為“最近的將來”的近似，選擇最近一段時間最長時間未被訪問的頁面淘汰出內(nèi)存 ? 評價 ? 適用于各種類型的程序，性能較好，但需要較多的硬件支持 42 2022年 8月 21日星期日 北京交通大學(xué)計算機學(xué)院 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 ? 某進(jìn)程分配獲得三個物理塊 ? 缺頁中斷次數(shù)為 9次，缺頁率 45% 頁面訪問序列 內(nèi)存頁面分布情況 頁面預(yù)先裝入 最近最久未使用置換算法舉例說明 43 2022年 8月 21日星期日 北京交通大學(xué)計算機學(xué)院 LUR置換算法實現(xiàn) ? 軟件實現(xiàn)的問題 ? 需要用操作系統(tǒng)軟件來更新頁面訪問時間。如果修改過，需要寫回磁盤保存。實際上，用戶看到的大容量只是一種感覺，是虛的，故而得名虛擬存儲器。本算法并不能真實全面地反映頁面使用情況 53 2022年 8月 21日星期日 北京交通大學(xué)計算機學(xué)院 頁面置換算法 抖動與缺頁率 最佳置換算法 先進(jìn)先出置換算法 最近最久未使用置換算法 Clock置換算法 最少使用置換算法 頁面緩沖算法 54 2022年 8月 21日星期日 北京交通大學(xué)計算機學(xué)院 頁面緩沖算法 PBA ? 完全正確的預(yù)測頁面將來的使用情況是困難的，錯誤在所難免。 56 2022年 8月 21日星期日 北京交通大學(xué)計算機學(xué)院 頁面緩沖算法 PBA ? 實現(xiàn)方法 ? 根據(jù)進(jìn)程缺頁率變化，修改一個進(jìn)程的可分配物理塊數(shù)。將準(zhǔn)備淘汰的頁面暫時存放在該緩沖區(qū)中，如果一段時間后沒有再次使用，則依次淘汰；否則，則回到已裝入頁面表中。 ?每位價格 ? =DRAM價格 +磁盤價格 /(DRAM容量 +磁盤容量 ) ? （同樣價格的內(nèi)存和磁盤，后者的容量大的多?。? ?Important measure: Average Access time = (Hit Rate x Hit Time) + (Miss Rate x Miss Time) 8 2022年 8月 21日星期日 北京交通大學(xué)計算機學(xué)院 局部性原理 ? 程序在執(zhí)行時將呈現(xiàn)局部性規(guī)律，即在一較短時間內(nèi)，程序的執(zhí)行僅限于某個部分；相應(yīng)地，它所訪問的內(nèi)存空間也僅局限于某個區(qū)域 ? 程序在大多數(shù)情況下的順序執(zhí)行特點 ? 過程調(diào)用深度及執(zhí)行軌跡 ? 程序循環(huán)結(jié)構(gòu)執(zhí)行及數(shù)據(jù)結(jié)構(gòu)操作特點 ? 局部性表現(xiàn)形式 ? 時間局部性（指令執(zhí)行與數(shù)據(jù)結(jié)構(gòu)訪問） ? 空間局部性（存儲單元臨近訪問） Review: Memory Hierarchy ? Take advantage of the principle of locality to: ? Present as much memory as in the cheapest technology ? Provide access at speed offered by the fastest technology Control Datapath Secondary Storage (Disk) Processor Second Level Cache (SRAM) Main Memory (DRAM) 1s 10,000,000s (10s ms) Speed (ns): 10s100s 100s 100s Ts Size (bytes): KsMs Gs Tertiary Storage (Tape) 10,000,000,000s (10s sec) Ts ? Compulsory (cold start): first reference to a block ?