第五章 虛擬存儲器

1、第五章第五章 虛擬存儲器虛擬存儲器5.1 5.1 虛擬存儲器概述虛擬存儲器概述 5.2 5.2 請求分頁存儲管理方式請求分頁存儲管理方式 5.3 5.3 頁面置換算法頁面置換算法 5.4 “5.4 “抖動抖動”與工作集與工作集5.5 5.5 請求分段存儲管理方式請求分段存儲管理方式 5.1 虛擬存儲器 分頁內(nèi)存分配和分段內(nèi)存分配方法可以解決程序在內(nèi)存中離散存放的問題，但是，這兩種方式都要求程序整個裝入內(nèi)存。事實上，很多時候，程序本身比內(nèi)存要大得多，那么簡單的分頁和分段的內(nèi)存方式就無法解決這個問題了?？梢圆捎锰摂M存儲器的方法，使用請求分配和置換策略請求分配和置換策略來實現(xiàn)存儲管理。5.1 虛擬存

2、儲器為什么需要虛擬存儲器： 程序大于內(nèi)存 程序暫時不執(zhí)行或運行完是否還要占用內(nèi)存 程序的局部性原理5.1 5.1 虛擬存儲器虛擬存儲器5.1.1 5.1.1 引入引入1.1.常規(guī)存儲管理的特征：常規(guī)存儲管理的特征： 一次性（指全部裝入）、一次性（指全部裝入）、 駐留性（指駐留在內(nèi)存不換出）駐留性（指駐留在內(nèi)存不換出）2 2、局部性原理、局部性原理 時間局部性：如循環(huán)執(zhí)行時間局部性：如循環(huán)執(zhí)行 空間局部性：如順序執(zhí)行?？臻g局部性：如順序執(zhí)行。3 3、虛擬存貯器、虛擬存貯器 具有請求調(diào)入功能和置換功能，能從邏輯上對具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量進行擴充的一種存儲系統(tǒng)。內(nèi)存容量進行

3、擴充的一種存儲系統(tǒng)。 實質(zhì)：以時間換空間，但時間犧牲不大。實質(zhì)：以時間換空間，但時間犧牲不大。 虛存大小由虛存大小由_決定。決定。 虛擬存儲器技術(shù)需要解決的問題 ：地址映射 分配策略 置換策略 裝載控制 5.1.2 5.1.2 虛擬存儲器的實現(xiàn)方式虛擬存儲器的實現(xiàn)方式需要需要動態(tài)重定位動態(tài)重定位1 1、請求分頁系統(tǒng)、請求分頁系統(tǒng) 以頁為單位轉(zhuǎn)換以頁為單位轉(zhuǎn)換 需硬件：需硬件：（1 1）請求分頁的頁表機制）請求分頁的頁表機制（2 2）缺頁中斷）缺頁中斷（3 3）地址變換機構(gòu)）地址變換機構(gòu) 需實現(xiàn)請求分頁機制的軟件（頁面請調(diào)、置換軟件等）需實現(xiàn)請求分頁機制的軟件（頁面請調(diào)、置換軟件等）2 2、請求

4、分段系統(tǒng)、請求分段系統(tǒng) 以段為單位轉(zhuǎn)換以段為單位轉(zhuǎn)換: :（1 1）請求分段的段表結(jié)構(gòu)）請求分段的段表結(jié)構(gòu)（2 2）缺段中斷）缺段中斷（3 3）地址變換機構(gòu)）地址變換機構(gòu) 需實現(xiàn)請求分段機制的軟件（段請調(diào)、置換軟件等）需實現(xiàn)請求分段機制的軟件（段請調(diào)、置換軟件等）5.1.3 5.1.3 虛存特征虛存特征1 1多次性多次性：局部裝入，多次裝入。：局部裝入，多次裝入。2 2對換性對換性：換進、換出：換進、換出3 3虛擬性虛擬性：從邏輯上擴充內(nèi)存：從邏輯上擴充內(nèi)存離散分配離散分配：支持多次性和對換性，若連續(xù)：支持多次性和對換性，若連續(xù)則不可能提供虛存，無法支持大作業(yè)小則不可能提供虛存，無法支持大作業(yè)

5、小內(nèi)存運行內(nèi)存運行請求分頁概念請求分頁概念 在進程開始運行之前，不是裝入全部頁面，而是裝入幾個頁面，之后根據(jù)進程運行的需要，動態(tài)裝入其它頁面；當內(nèi)存空間已滿，而又需要裝入新的頁面時，則根據(jù)某種算法淘汰某個頁面，以便裝入新的頁面。5.2.1 5.2.1 請求分頁中的數(shù)據(jù)結(jié)構(gòu)及硬件支持請求分頁中的數(shù)據(jù)結(jié)構(gòu)及硬件支持1 1、頁表機制、頁表機制 頁表項：頁表項：2 2、缺頁中斷機構(gòu)、缺頁中斷機構(gòu)：可在指令執(zhí)行期間產(chǎn)生（如圖：可在指令執(zhí)行期間產(chǎn)生（如圖5-15-1）轉(zhuǎn)入缺頁中斷處理程序。轉(zhuǎn)入缺頁中斷處理程序。3 3、地址變換機構(gòu)、地址變換機構(gòu)比較簡單分頁機制，增加了中斷處理，（比較簡單分頁機制，增加了中

6、斷處理，（如圖如圖5-25-2）5.2 5.2 請求分頁存儲管理方式請求分頁存儲管理方式頁號頁號物理塊號物理塊號狀態(tài)位狀態(tài)位P P 訪問字段訪問字段A A修改位修改位M M 外存地址外存地址 圖圖5-1 5-1 涉及涉及6 6次缺頁中斷的指令次缺頁中斷的指令圖圖5-2 請求分頁中的地址變換過程請求分頁中的地址變換過程 MMU例6 現(xiàn)有一請求調(diào)頁系統(tǒng)，頁表保存在寄存器中。若有一個被替換的頁未被修改過，則處理一個缺頁中斷需要8ms；若被替換的頁已被修改過，則處理一個缺頁中斷需要20ms；內(nèi)存存取時間為1s，訪問頁表的時間可忽略不計。假定70%被替換的頁被修改過，為保證有效存取時間不超過2s，可接受

7、的最大缺頁率是多少？注：（缺頁率=缺頁次數(shù)/總的頁面訪問次數(shù)） 解：解： 如果用p表示缺頁率，則有效存取時間不超過2s可表示為：(1-p)1s+p(0.720ms+0.38ms+1s) 2s因此可計算出：p 1/164000.000065.2.2 5.2.2 內(nèi)存分配策略和分配算法內(nèi)存分配策略和分配算法1 1、最小物理塊數(shù)：、最小物理塊數(shù)：與計算機的硬件結(jié)構(gòu)有關(guān)與計算機的硬件結(jié)構(gòu)有關(guān)不同的作業(yè)要求不同。不同的作業(yè)要求不同。如：允許間接尋址：則至如：允許間接尋址：則至少要求少要求3 3個物理塊。個物理塊。Mov A, B Mov A, B 物理塊是否越大越好？缺頁次數(shù)缺頁次數(shù) Versus 物理

8、頁框數(shù)物理頁框數(shù)臨界點臨界點5.2.2 5.2.2 內(nèi)存分配策略和分配算法內(nèi)存分配策略和分配算法2 2、頁面分配和置換策略。、頁面分配和置換策略。1 1）固定分配局部置換。）固定分配局部置換。 缺點：難以確定固定分配的頁數(shù)缺點：難以確定固定分配的頁數(shù).(.(少：少：置換率高置換率高 多：浪費多：浪費) )2 2）可變分配全局置換）可變分配全局置換3 3）可變分配局部置換）可變分配局部置換 根據(jù)進程的缺頁率進行頁面數(shù)調(diào)整，根據(jù)進程的缺頁率進行頁面數(shù)調(diào)整，進程之間相互不會影響。進程之間相互不會影響。3 3、分配算法、分配算法 1 1）平均分配算法）平均分配算法2 2）按進程大小比例分配算法：）按進

9、程大小比例分配算法：3 3）考慮優(yōu)先權(quán)分配算法）考慮優(yōu)先權(quán)分配算法 mssbiiniiss15.2.3 5.2.3 頁面調(diào)入策略頁面調(diào)入策略 1.1.調(diào)入時機：調(diào)入時機： 預調(diào)：（根據(jù)空間局部性）預調(diào)：（根據(jù)空間局部性） 目前：成功率目前：成功率5050；適合于首次調(diào)入時；適合于首次調(diào)入時 請求調(diào)頁：每次調(diào)入一頁，較費系統(tǒng)開銷請求調(diào)頁：每次調(diào)入一頁，較費系統(tǒng)開銷 各有優(yōu)劣各有優(yōu)劣2 2從何處調(diào)頁：從何處調(diào)頁： 對換區(qū)：修改過的頁被換出時入對換區(qū)，對換區(qū)：修改過的頁被換出時入對換區(qū)， 快快 文件區(qū)：稍慢文件區(qū)：稍慢 UnixUnix方式方式 對共享頁，應判斷其是否在內(nèi)存區(qū)。對共享頁，應判斷其是否

10、在內(nèi)存區(qū)。3.3.頁面調(diào)入過程頁面調(diào)入過程目的：減少對換量，提高系統(tǒng)性能目的：減少對換量，提高系統(tǒng)性能 5.3.1 5.3.1 最佳置換算法和先進先出算法最佳置換算法和先進先出算法1 1、最佳（、最佳（OptimalOptimal）置換算法（理論上的）置換算法（理論上的）5.3 5.3 頁置換算法頁置換算法 圖圖 5-3 利用最佳頁面置換算法時的置換圖利用最佳頁面置換算法時的置換圖 5.3 5.3 頁面置換算法頁面置換算法 2 2、先進先出（、先進先出（FIFOFIFO）頁面置換算法）頁面置換算法 圖圖 5-4 利用利用FIFO置換算法時的置換圖置換算法時的置換圖 是否頁框數(shù)增加就一定會減少缺

11、頁數(shù)呢？是否頁框數(shù)增加就一定會減少缺頁數(shù)呢？2 2、先進先出（、先進先出（FIFOFIFO）頁面置換算法（續(xù)）頁面置換算法（續(xù)） Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 3 frames (3 pages can be in memory at a time per process)4 framesFIFO Replacement Beladys Anomaly more frames less page faults1231234125349 page faults10 page faults12312351245443FIF

12、O Illustrating Beladys Anomaly5.3.2 5.3.2 最近最久未用最近最久未用LRULRU置換置換1 1、算法描述、算法描述 將將“最近的過去最近的過去”，作為，作為“最近的將來最近的將來”。圖圖 5-5 LRU頁面置換算法頁面置換算法 2. LRU2. LRU置換算法的硬件支持置換算法的硬件支持 1) 1) 寄存器寄存器 為了記錄某進程在內(nèi)存中各頁的使用情況，須為每個在內(nèi)存中的頁面配置一個移位寄存器，可表示為: R=Rn-1Rn-2Rn-3 R2R1R0 2) 2) 棧棧 圖圖 5-7 用棧保存當前使用頁面時棧的變化情況用棧保存當前使用頁面時棧的變化情況 5.3

13、.3 Clock5.3.3 Clock置換算法置換算法（一種LRU近似算法：硬件消耗少）1 1、簡單的、簡單的ClockClock算法算法( (最近未用算法最近未用算法NRUNRU）：）： 設一訪問位：圖設一訪問位：圖5-85-8；循環(huán)掃描，每次掃描時將訪問；循環(huán)掃描，每次掃描時將訪問位復位。位復位。圖圖 5-8 簡單簡單Clock置換算法的流程和示例置換算法的流程和示例 頁面頁面12使用位使用位=1頁面頁面2使用位使用位=1頁面頁面36使用位使用位=0頁面頁面6使用位使用位=1頁面頁面23使用位使用位=1頁面頁面25使用位使用位=1頁面頁面11使用位使用位=0頁面頁面8使用位使用位=0頁面頁

14、面12使用位使用位=0頁面頁面2使用位使用位=1頁面頁面9使用位使用位=1頁面頁面6使用位使用位=0頁面頁面23使用位使用位=1頁面頁面25使用位使用位=1頁面頁面11使用位使用位=0頁面頁面8使用位使用位=0(a)頁面置換前狀態(tài)頁面置換前狀態(tài)(b)頁面置換后狀態(tài)頁面置換后狀態(tài)01234567時鐘算法時鐘算法2. 2. 改進型改進型ClockClock置換算法置換算法 由訪問位A和修改位M可以組合成下面四種類型的頁面： 1類(A=0, M=0): 2類(A=0, M=1)： 3類(A=1, M=0)： 4類(A=1, M=1): 其執(zhí)行過程可分成以下幾步：5.3.4 5.3.4 其它置換算法其

15、它置換算法1 1、最少使用算法、最少使用算法 LFULFU（訪問頻率）（訪問頻率） 與與LRULRU類似（記錄訪問次數(shù)），設置一個訪問計數(shù)類似（記錄訪問次數(shù)），設置一個訪問計數(shù)器。器。2 2、頁面緩沖算法：、頁面緩沖算法： 特點：淘汰的頁只是修改標志；若頁被修改過，則特點：淘汰的頁只是修改標志；若頁被修改過，則在欲復蓋它時回寫，否則成批回寫。在欲復蓋它時回寫，否則成批回寫。 在欲重訪問該頁時，若頁換出則只需修改標志。在欲重訪問該頁時，若頁換出則只需修改標志。5.4 “抖動抖動”與工作集與工作集5.5 5.5 請求分段存儲管理方式請求分段存儲管理方式5.5.1 5.5.1 請求分段中的硬件支持請

16、求分段中的硬件支持1 1、段表機制：、段表機制：2 2、缺段中斷機構(gòu)：、缺段中斷機構(gòu)： 段不定長，處理起來比缺頁中斷復雜。段不定長，處理起來比缺頁中斷復雜。圖圖5-125-123 3、地址變換機構(gòu)、地址變換機構(gòu) 圖圖5-135-13段名段名 段長段長 段的段的基址基址 存取存取方式方式 訪問訪問字段字段A 修改修改位位M 存在存在位位P 增補增補位位 外存外存始址始址 圖圖 5-12 5-12 請求分段系統(tǒng)中的中斷處理過程請求分段系統(tǒng)中的中斷處理過程圖圖 5-13 5-13 請求分段系統(tǒng)的地址變換過程請求分段系統(tǒng)的地址變換過程5.5.2 5.5.2 分段的共享與保護分段的共享與保護1 1、共享

17、段表：、共享段表：（整個系統(tǒng)一張）（整個系統(tǒng)一張）1 1）共享進程計數(shù)。）共享進程計數(shù)。2 2）存取控制字段。）存取控制字段。3 3）段號：不同的進程可以使用不同的段號去共享段。）段號：不同的進程可以使用不同的段號去共享段。圖圖 4-34 4-34 共享段表項共享段表項 5.5.2 5.5.2 分段的共享與保護分段的共享與保護2 2、共享段的分配與回收、共享段的分配與回收1 1）分配：）分配： 第一次訪問：分配內(nèi)存，（第一次訪問：分配內(nèi)存，（1 1）增加共享段表；）增加共享段表；（2 2）修改進程段表。）修改進程段表。 第二次訪問：（第二次訪問：（1 1）修改共享段表；（）修改共享段表；（2

18、2）修改）修改進程段表。進程段表。2 2）回收：）回收： （1 1）count=0 count=0 （2 2）count0count05.5.2 5.5.2 分段的共享與保護分段的共享與保護3 3、分段保護、分段保護1 1）越界檢查）越界檢查 段號越界檢查。段號越界檢查。 段內(nèi)偏移越界檢查。段內(nèi)偏移越界檢查。2 2）存取控制檢查。）存取控制檢查。 R R；R/WR/W；E E3 3）環(huán)保護機構(gòu)）環(huán)保護機構(gòu)（1 1）內(nèi)環(huán)可訪問相同環(huán)或外環(huán)數(shù)據(jù)；）內(nèi)環(huán)可訪問相同環(huán)或外環(huán)數(shù)據(jù)；（2 2）外環(huán)可請求相同環(huán)或內(nèi)環(huán)服務。）外環(huán)可請求相同環(huán)或內(nèi)環(huán)服務。段式存儲管理段式存儲管理頁式存儲管理頁式存儲管理段頁式存儲管理段頁式存儲管理虛擬存儲器虛擬存儲器虛擬存儲技術(shù)虛擬存儲技術(shù)程序局部性原理程序局部性原理虛擬頁式管理虛擬頁式管理虛擬段式管理虛擬段式管理頁面淘汰算法頁面淘汰算法抖動（顛簸）抖動（顛簸）工作集模型工作集模型用戶程序劃分用戶程序劃分邏輯地址邏輯地址內(nèi)存空間劃分內(nèi)存空間劃分內(nèi)存分配內(nèi)存分配管理考慮