第五章 虛擬存儲器.ppt

1、第五章 虛擬存儲器,5.1 虛擬存儲器概述 5.2 請求分頁存儲管理方式 5.3 頁面置換算法 5.4 “抖動”與工作集 5.5 請求分段存儲管理方式,5.1 虛擬存儲器,分頁內(nèi)存分配和分段內(nèi)存分配方法可以解決程序在內(nèi)存中離散存放的問題，但是，這兩種方式都要求程序整個裝入內(nèi)存。事實上，很多時候，程序本身比內(nèi)存要大得多，那么簡單的分頁和分段的內(nèi)存方式就無法解決這個問題了?？梢圆捎锰摂M存儲器的方法，使用請求分配和置換策略來實現(xiàn)存儲管理。,5.1 虛擬存儲器,為什么需要虛擬存儲器： 程序大于內(nèi)存 程序暫時不執(zhí)行或運行完是否還要占用內(nèi)存 程序的局部性原理,5.1 虛擬存儲器,5.1.1 引入 1.常規(guī)

2、存儲管理的特征： 一次性（指全部裝入）、 駐留性（指駐留在內(nèi)存不換出） 2、局部性原理 時間局部性：如循環(huán)執(zhí)行 空間局部性：如順序執(zhí)行。 3、虛擬存貯器 具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量進行擴充的一種存儲系統(tǒng)。 實質(zhì)：以時間換空間，但時間犧牲不大。 虛存大小由_決定。,虛擬存儲器技術需要解決的問題 ： 地址映射 分配策略 置換策略 裝載控制,5.1.2 虛擬存儲器的實現(xiàn)方式,需要動態(tài)重定位 1、請求分頁系統(tǒng) 以頁為單位轉(zhuǎn)換 需硬件： （1）請求分頁的頁表機制 （2）缺頁中斷 （3）地址變換機構(gòu) 需實現(xiàn)請求分頁機制的軟件（頁面請調(diào)、置換軟件等） 2、請求分段系統(tǒng) 以段為單位轉(zhuǎn)換:

3、 （1）請求分段的段表結(jié)構(gòu) （2）缺段中斷 （3）地址變換機構(gòu) 需實現(xiàn)請求分段機制的軟件（段請調(diào)、置換軟件等）,5.1.3 虛存特征,1多次性：局部裝入，多次裝入。 2對換性：換進、換出 3虛擬性：從邏輯上擴充內(nèi)存 離散分配：支持多次性和對換性，若連續(xù)則不可能提供虛存，無法支持大作業(yè)小內(nèi)存運行,請求分頁概念,在進程開始運行之前，不是裝入全部頁面，而是裝入幾個頁面，之后根據(jù)進程運行的需要，動態(tài)裝入其它頁面；當內(nèi)存空間已滿，而又需要裝入新的頁面時，則根據(jù)某種算法淘汰某個頁面，以便裝入新的頁面。,5.2.1 請求分頁中的數(shù)據(jù)結(jié)構(gòu)及硬件支持 1、頁表機制 頁表項： 2、缺頁中斷機構(gòu)：可在指令執(zhí)行期間產(chǎn)

4、生（如圖5-1） 轉(zhuǎn)入缺頁中斷處理程序。 3、地址變換機構(gòu) 比較簡單分頁機制，增加了中斷處理，（如圖5-2）,5.2 請求分頁存儲管理方式,圖5-1 涉及6次缺頁中斷的指令,圖5-2 請求分頁中的地址變換過程,MMU,例6,現(xiàn)有一請求調(diào)頁系統(tǒng)，頁表保存在寄存器中。若有一個被替換的頁未被修改過，則處理一個缺頁中斷需要8ms；若被替換的頁已被修改過，則處理一個缺頁中斷需要20ms；內(nèi)存存取時間為1s，訪問頁表的時間可忽略不計。假定70%被替換的頁被修改過，為保證有效存取時間不超過2s，可接受的最大缺頁率是多少？ 注：（缺頁率=缺頁次數(shù)/總的頁面訪問次數(shù)）,解：,如果用p表示缺頁率，則有效存取時間不

5、超過2s可表示為： (1-p)1s+p(0.720ms+0.38ms+1s) 2s 因此可計算出： p 1/164000.00006,5.2.2 內(nèi)存分配策略和分配算法,1、最小物理塊數(shù)： 與計算機的硬件結(jié)構(gòu)有關 不同的作業(yè)要求不同。 如：允許間接尋址：則至少要求3個物理塊。 Mov A, B,物理塊是否越大越好？,缺頁次數(shù) Versus 物理頁框數(shù),臨界點,5.2.2 內(nèi)存分配策略和分配算法,2、頁面分配和置換策略。 1）固定分配局部置換。 缺點：難以確定固定分配的頁數(shù).(少：置換率高 多：浪費) 2）可變分配全局置換 3）可變分配局部置換 根據(jù)進程的缺頁率進行頁面數(shù)調(diào)整，進程之間相互不會影

6、響。,3、分配算法,1）平均分配算法 2）按進程大小比例分配算法： 3）考慮優(yōu)先權分配算法,5.2.3 頁面調(diào)入策略,1.調(diào)入時機： 預調(diào)：（根據(jù)空間局部性） 目前：成功率50；適合于首次調(diào)入時 請求調(diào)頁：每次調(diào)入一頁，較費系統(tǒng)開銷 各有優(yōu)劣 2從何處調(diào)頁： 對換區(qū)：修改過的頁被換出時入對換區(qū)，快 文件區(qū)：稍慢 Unix方式 對共享頁，應判斷其是否在內(nèi)存區(qū)。 3.頁面調(diào)入過程,目的：減少對換量，提高系統(tǒng)性能 5.3.1 最佳置換算法和先進先出算法 1、最佳（Optimal）置換算法（理論上的）,5.3 頁置換算法,圖 5-3 利用最佳頁面置換算法時的置換圖,5.3 頁面置換算法,2、先進先出（

7、FIFO）頁面置換算法,圖 5-4 利用FIFO置換算法時的置換圖,是否頁框數(shù)增加就一定會減少缺頁數(shù)呢？,2、先進先出（FIFO）頁面置換算法（續(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 frames FIFO Replacement Beladys Anomaly more frames less page faults,9 page faults,10 page faults,FIFO Illustrat

8、ing Beladys Anomaly,5.3.2 最近最久未用LRU置換,1、算法描述 將“最近的過去”，作為“最近的將來”。,圖 5-5 LRU頁面置換算法,2. LRU置換算法的硬件支持,1) 寄存器 為了記錄某進程在內(nèi)存中各頁的使用情況，須為每個在內(nèi)存中的頁面配置一個移位寄存器，可表示為:,R=Rn-1Rn-2Rn-3 R2R1R0,2) 棧,圖 5-7 用棧保存當前使用頁面時棧的變化情況,5.3.3 Clock置換算法（一種LRU近似算法：硬件消耗少）,1、簡單的Clock算法(最近未用算法NRU）： 設一訪問位：圖5-8；循環(huán)掃描，每次掃描時將訪問位復位。,圖 5-8 簡單Cloc

9、k置換算法的流程和示例,時鐘算法,2. 改進型Clock置換算法,由訪問位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 其它置換算法,1、最少使用算法 LFU（訪問頻率） 與LRU類似（記錄訪問次數(shù)），設置一個訪問計數(shù)器。 2、頁面緩沖算法： 特點：淘汰的頁只是修改標志；若頁被修改過，則在欲復蓋它時回寫，否則成批回寫。 在欲重訪問該頁時，若頁換出則只需修改標志。,5.4 “抖動”與工作集,5.5 請求分段存儲管理方式,5.5.1 請求分段中的硬件支持 1、段表機制： 2、缺段中斷機構(gòu)： 段不定長，處理起來比缺頁中斷復雜。圖5-12 3、地址變換機構(gòu) 圖5-13,圖 5-12 請求分段系統(tǒng)中的中斷處理過程,圖 5-13 請求分段系統(tǒng)的地址變換過程,5.5.2 分段的共享與保護,1、共享段表：（整個系統(tǒng)一張） 1）共享進程計數(shù)。 2）存取控制字段。 3）段號：不同的進程可以使用不同的段號去共享段。,圖 4-34 共享段表項,5.5.2 分段的共享與保護,2、共享段的分配與回收 1）分配： 第一次訪問：分配內(nèi)存，（1）增加共享段表；（2）修改進程段表。 第二次訪問：（1