【正文】 ? 缺頁中斷時(shí)，如果該頁不在緩沖區(qū)中，需要從空閑頁面鏈表的表頭取一個(gè)空閑物理塊分配給正在訪問的缺頁。那么每次內(nèi)存訪問都需要用軟件修改該時(shí)間字段（需要多大的開銷？）。 ? 新的頁面調(diào)入內(nèi)存后，需要更新頁表、快表。 ? 實(shí)現(xiàn)目標(biāo) ? 大用戶程序在小內(nèi)存空間的運(yùn)行 ? 多道程序度的提高 6 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 虛擬存儲(chǔ)器的定義 ? 所謂虛擬存儲(chǔ)器，是指僅把作業(yè)的一部分裝入內(nèi)存便可運(yùn)行作業(yè)的存儲(chǔ)器系統(tǒng)。頁面置換時(shí)，又需要選擇其中最早的頁面進(jìn)行置換。同時(shí)，將采用 FIFO算法將該進(jìn)程最早調(diào)入內(nèi)存的物理塊號(hào)（未修改）插入空閑頁表尾部或（該頁已修改）已修改頁面鏈表尾部。一個(gè)進(jìn)程創(chuàng)建時(shí)分配一定數(shù)量的物理塊。假設(shè)每個(gè)頁面對(duì)應(yīng)一個(gè) 2個(gè)字節(jié)的訪問時(shí)間字段（沒有硬件支持該字段的更新）。否則不必寫回，直接丟棄。具體地說，所謂虛擬存儲(chǔ)器是指具有請(qǐng)求調(diào)入功能和置換功能，能從邏輯上對(duì)內(nèi)存容量進(jìn)行擴(kuò)充的一種存儲(chǔ)器系統(tǒng)。 44 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 最近最久未使用置換算法硬件支持 —移位寄存器 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日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 最近最久未使用置換算法硬件支持 —棧 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 ? 某進(jìn)程分配獲得五個(gè)物理塊 頁面訪問序列 46 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 頁面置換算法 抖動(dòng)與缺頁率 最佳置換算法 先進(jìn)先出置換算法 最近最久未使用置換算法 Clock置換算法 最少使用置換算法 頁面緩沖算法 47 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 clock置換算法實(shí)現(xiàn) ? 利用頁表中的訪問字位、修改位 ? 不需要額外硬件 頁號(hào) 物理塊號(hào) 狀態(tài)位 訪問位 修改位 外存地址 48 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 簡(jiǎn)單 Clock置換算法 (NRU) 塊號(hào) 頁號(hào) 頁面 訪問位 指針 0 1 2 4 0 3 4 2 1 5 6 5 0 7 1 1 查尋指針 入口 返回 查尋指針 前移指向下一表目 選擇該頁淘汰 頁面訪問位 =0？ 置頁面 訪問位為 0 是 否 49 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 改進(jìn)型 Clock置換算法 ? 基本思想 ① 從查尋指針當(dāng)前位置起掃描內(nèi)存分頁循環(huán)隊(duì)列，選擇 A=0且 M=0的第一個(gè)頁面淘汰；若未找到，轉(zhuǎn)② ② 開始第二輪掃描，選擇 A=0且 M=1的第一個(gè)頁面淘汰，同時(shí)將經(jīng)過的所有頁面訪問位置 0；若不能找到，轉(zhuǎn)① ? 評(píng)價(jià) ? 與簡(jiǎn)單 Clock算法相比，可減少磁盤的 I/O操作次數(shù)，但淘汰頁的選擇可能經(jīng)歷多次掃描，故實(shí)現(xiàn)算法自身的開銷增大 50 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 頁面置換算法 抖動(dòng)與缺頁率 最佳置換算法 先進(jìn)先出置換算法 最近最久未使用置換算法 Clock置換算法 最少使用置換算法 頁面緩沖算法 51 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 最少使用置換算法 LFU ? 基本思想 ? 選擇在最近時(shí)期使用次數(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日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 最少使用置換算法 LFU ? 評(píng)價(jià) ? 鑒于僅用移位寄存器有限各位來記錄頁面使用會(huì)導(dǎo)致訪問一次與訪問多次的等效性（寄存器在 100ms右移一位，那么在這段時(shí)間內(nèi)，多次訪問與一次訪問的效果一樣）。 ? 缺頁中斷時(shí)，如果該頁還在緩沖區(qū)中，則將物理塊號(hào)從緩沖隊(duì)列中刪除，并插入進(jìn)程頁表中。 55 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 頁面緩沖算法 PBA ? 實(shí)現(xiàn)方法 ? 設(shè)立空閑頁面鏈表和已修改頁面鏈表 ? 初始化時(shí)，空閑頁面鏈表包括系統(tǒng)中所有空閑頁。不同的操作系統(tǒng)可以有非常不同的設(shè)計(jì)！ 23 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 請(qǐng)求分頁存儲(chǔ)管理方式 請(qǐng)求分頁中的硬件支持 內(nèi)存分配策略和分配算法 調(diào)頁策略 頁面置換算法 24 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 最小物理塊數(shù)的確定 ? 保證進(jìn)程正常運(yùn)行所需的最少物理塊數(shù) ? 若系統(tǒng)為某進(jìn)程分配的物理塊數(shù)少于此值，進(jìn)程將無法正常運(yùn)行 ? 不同于使進(jìn)程有效工作所需的物理塊數(shù) ? 與計(jì)算機(jī)的硬件結(jié)構(gòu)有關(guān)，并取決于指令的格式（操作數(shù)個(gè)數(shù)）、功能和尋址方式（直接 /間接） 25 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 物理塊分配算法 ? 平均分配算法 ? 將系統(tǒng)可供分配的物理塊平均分配 ? 按比例分配算法 ? BlockOfPk = max{minBlocks, Blocks ? PagesOfPk/?PagesOfPi} ? 考慮優(yōu)先權(quán)的分配算法 ? 照顧重要或緊迫的作業(yè)能盡快完成 26 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 物理塊分配與置換策略 ? 固定分配局部置換 ? 為每個(gè)進(jìn)程分配一固定頁數(shù)的內(nèi)存空間，在整個(gè)運(yùn)行期間都不再改變 ? 可變分配全局置換 ? 系統(tǒng)設(shè)立一個(gè)空閑物理塊隊(duì)列 ? 可變分配局部置換 ? 依據(jù)缺頁率酌情增加或減少物理塊 27 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 請(qǐng)求分頁存儲(chǔ)管理方式 請(qǐng)求分頁中的硬件支持 內(nèi)存分配策略和分配算法 調(diào)頁策略 頁面置換算法 28 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 何時(shí)調(diào)入頁面 ? 預(yù)調(diào)頁策略 ? 將那些預(yù)計(jì)在不久之后便會(huì)被訪問的程序或數(shù)據(jù)所在的頁面，預(yù)先調(diào)入內(nèi)存 ? 以預(yù)測(cè)為基礎(chǔ)，主要用于進(jìn)程首次調(diào)入 ? 請(qǐng)求調(diào)頁策略 ? 當(dāng)進(jìn)程在運(yùn)行中需要訪問某部分程序和數(shù)據(jù)時(shí)，若發(fā)現(xiàn)其所在的頁面不在內(nèi)存，應(yīng)立即提出請(qǐng)求，由系統(tǒng)將其所需頁面調(diào)入內(nèi)存；易于實(shí)現(xiàn)但系統(tǒng)開銷大 29 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 何處調(diào)入頁面 ? 對(duì)換區(qū)空間充分 ? 進(jìn)程運(yùn)行前，便須將與該進(jìn)程有關(guān)的文件，從文件區(qū)拷貝到對(duì)換區(qū) ? 對(duì)換區(qū)空間不足 ? 文件是否修改分別處理 ? UNIX方式 ? 凡未運(yùn)行過的頁面都應(yīng)從文件區(qū)調(diào)入，而對(duì)于曾運(yùn)行過又被換出到對(duì)換區(qū)的頁面則從對(duì)換區(qū)調(diào)入 30 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 頁面調(diào)入過程 ? 缺頁中斷發(fā)生 ? 程序所訪問的頁面不在內(nèi)存時(shí)產(chǎn)生缺頁中斷并轉(zhuǎn)入缺頁中斷處理程序 ? 根據(jù)頁表外存地址調(diào)入所缺頁面 ? 頁表項(xiàng)外存地址（物理盤塊號(hào)） ? 內(nèi)存不足置換 ? 頁面淘汰算法 ? 是否重寫磁盤 31 20