第五章 虛擬存儲(chǔ)器.ppt

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

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

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

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

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

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

7、FIFO）頁(yè)面置換算法,圖 5-4 利用FIFO置換算法時(shí)的置換圖,是否頁(yè)框數(shù)增加就一定會(huì)減少缺頁(yè)數(shù)呢？,2、先進(jìn)先出（FIFO）頁(yè)面置換算法（續(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頁(yè)面置換算法,2. LRU置換算法的硬件支持,1) 寄存器 為了記錄某進(jìn)程在內(nèi)存中各頁(yè)的使用情況，須為每個(gè)在內(nèi)存中的頁(yè)面配置一個(gè)移位寄存器，可表示為:,R=Rn-1Rn-2Rn-3 R2R1R0,2) 棧,圖 5-7 用棧保存當(dāng)前使用頁(yè)面時(shí)棧的變化情況,5.3.3 Clock置換算法（一種LRU近似算法：硬件消耗少）,1、簡(jiǎn)單的Clock算法(最近未用算法NRU）： 設(shè)一訪問位：圖5-8；循環(huán)掃描，每次掃描時(shí)將訪問位復(fù)位。,圖 5-8 簡(jiǎn)單Cloc

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