操作系統(tǒng) 虛擬內(nèi)存.ppt

1、內(nèi)容提要,虛存技術(shù)的引入和虛擬存儲器的定義、特征 虛擬存儲器的實(shí)現(xiàn) 請求分頁 請求分段,內(nèi)容提要,虛存技術(shù)的引入和虛擬存儲器的定義、特征 虛擬存儲器的實(shí)現(xiàn) 請求分頁 請求分段,需求,指令必須被裝載到內(nèi)存中運(yùn)行 上一講的解決方案 To place the entire logical address in physical memory Overlays（覆蓋） Dynamic loading Dynamic linking 然而 有的作業(yè)很大；作業(yè)個(gè)數(shù)很多 若從物理上擴(kuò)展內(nèi)存，代價(jià)太高 思路：從邏輯上擴(kuò)展內(nèi)存,虛存技術(shù)的引入,程序的局部性原理，1968，Denning 時(shí)間局部性、空間局部性

2、思路： 部分裝入、按需裝入、置換 虛擬存儲器： 是指具有請求調(diào)度功能和置換功能，能從邏輯上對內(nèi)存容量加以擴(kuò)充的一種存儲器系統(tǒng) 邏輯容量：從系統(tǒng)角度看：內(nèi)存容量外存容量從進(jìn)程角度看：地址總線寬度范圍內(nèi)；內(nèi)存容量外存容量 運(yùn)行速度：接近內(nèi)存 每位成本：接近外存,Virtual memory diagram,Some pages in memory, Some pages in disk,虛擬存儲器的特征,多次性：最重要的特征 一個(gè)作業(yè)被分成多次裝入內(nèi)存運(yùn)行 對換性 允許在進(jìn)程運(yùn)行的過程中，（部分）換入換出 虛擬性 邏輯上的擴(kuò)充 虛擬性是以多次性和對換性為基礎(chǔ)的。 多次性和對換性是建立在離散分配的基

3、礎(chǔ)上的,內(nèi)容提要,虛存技術(shù)的引入和虛擬存儲器的定義、特征 虛擬存儲器的實(shí)現(xiàn) 請求分頁 請求分段,虛擬存儲器的實(shí)現(xiàn),請求分頁 以分頁技術(shù)為基礎(chǔ)，加上 請求調(diào)頁（pager）功能和頁面置換功能 與對換相比，頁面置換中換入換出的基本單位是頁，而不是整個(gè)進(jìn)程 請求分段 以分段技術(shù)為基礎(chǔ),請求分頁,請求分頁的硬件支持 請求分頁的內(nèi)存分配策略和分配算法 調(diào)頁策略 頁面置換算法 請求分頁的性能分析和改進(jìn),請求分頁,請求分頁的硬件支持 請求分頁的內(nèi)存分配策略和分配算法 調(diào)頁策略 頁面置換算法 請求分頁的性能分析和改進(jìn),請求分頁的硬件支持,頁表機(jī)制 缺頁中斷機(jī)構(gòu) 地址變換機(jī)構(gòu) 對比“基本分頁存儲管理技術(shù)”,請求

4、分頁中的頁表機(jī)制,頁表是請求分頁系統(tǒng)中所需要的主要數(shù)據(jù)結(jié)構(gòu)，是前面所講頁表的擴(kuò)展，增加了： 存在位P：表示對應(yīng)的頁是否已經(jīng)裝入內(nèi)存 訪問字段A：記錄訪問情況，供換出時(shí)參考 修改位M：記錄修改情況，供換出時(shí)參考 外存地址：記錄在外存上的地址，供換入時(shí)參考,請求分頁中的缺頁中斷機(jī)構(gòu),當(dāng)一個(gè)進(jìn)程試圖訪問標(biāo)記為 “not present”的頁面時(shí)，會發(fā)生缺頁異常. Page fault trap（缺頁異常） Exact exception (trap)Restart the process in exactly the same place and state. Re-execute the inst

5、ruction which triggered the trap. 一條指令在執(zhí)行期間可能產(chǎn)生多次缺頁異常,One instruction use 100 ns) Effective Access Time (EAT) EAT = (1 p)ma + ppage fault time,Page fault time,Page fault overhead Service the page-fault interrupt (1100us) (May be) swap some pages out Read in the page (24ms,尋道，旋轉(zhuǎn)，傳輸) Restart overhead

6、(1100us) Restart the process Page fault time may be 25ms,性能舉例,Page fault time = 25ms ma = 100ns Then EAT = 100(1-p)+25106p = 100 + 24,999,900p If p=1/1000, then EAT =25,099.9 ns If needs EAT 110ns, then 100+24,999,900p110that is p 10/24,999,90010/25,000,000 =1/2,500,000 =410-7 Page fault rage p must

7、 be smaller than 410-7,請求分頁,請求分頁的硬件支持 請求分頁的內(nèi)存分配策略和分配算法 調(diào)頁策略 頁面置換算法 請求分頁的性能分析和改進(jìn),內(nèi)存分配策略,為進(jìn)程分配內(nèi)存時(shí)，涉及3個(gè)主要問題 最小物理塊數(shù)的確定 物理塊的分配策略 物理塊的分配算法,最小物理塊數(shù)的確定,Determined by ISA(Instruction-Set Architecture ) We must have enough frames to hold all the different pages that any single instruction can reference Example

8、: IBM 370 6 pages to handle MVC instruction: instruction is 6 bytes, might span 2 pages. 2 pages to handle from; 2 pages to handle to. How about maximum number?,物理塊的分配策略,分配策略： Fixed allocation The No. of frames allocated to a process is fixed Variable allocation The No. of frames allocated to a proc

9、ess is variable as the process running 置換策略： 全局 vs. 局部 兩者結(jié)合： 固定分配局部置換 可變分配全局置換 可變分配局部置換,物理塊的分配算法,1、平均分配算法： The simplest way to split m frames among n processes is to give each one an equal share: m/n frames each 2、按比例分配算法（舉例）： Allocate frames to each process according to the size of each process. 3、

10、考慮優(yōu)先級的分配算法 在按比例分配算法中，考慮將size（部分）換成優(yōu)先級,Example:,請求分頁,請求分頁的硬件支持 請求分頁的內(nèi)存分配策略和分配算法 調(diào)頁策略 頁面置換算法 請求分頁的性能分析和改進(jìn),請求分頁,請求分頁的硬件支持 請求分頁的內(nèi)存分配策略和分配算法 調(diào)頁策略 頁面置換算法 請求分頁的性能分析和改進(jìn),頁面置換算法,Free page frame is managed by OS using free-frame-list What happens if there is no free frame? Page replacement,Page-Replacement Alg

11、orithms,目標(biāo)：盡可能降低缺頁率 Different algorithms are evaluated by calculating the number of page faults they cause on a reference string. A reference string is a sequence of addresses referenced by a program.,Example,An address reference string: 0100 0432 0101 0612 0102 0103 0104 01010611 0103 0104 0101 061

12、0 0102 0103 01040101 0609 0102 0105 Assuming page size = 100 B, then its corresponding page reference string is: 1 4 1 6 1 6 1 6 1 6 1,11 pages,Example (contd),缺頁多少次? 取決于可用物理頁框的個(gè)數(shù) 若物理頁框數(shù)3，則 1 4 1 6 1 6 1 6 1 6 1 1, 4, 6 3 次缺頁 若只有1個(gè)物理頁框，那么每次訪問一個(gè)新的頁都會導(dǎo)致發(fā)生缺頁: 11 次缺頁,Page faults vs. the number of frames

13、,隨著物理頁框個(gè)數(shù)的增加，缺頁次數(shù)下降,Number of frames,Number of page faults,頁面置換算法,假定， 訪問序列為： 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 有3個(gè)物理頁框 介紹如下算法 FIFO page replacement Optimal page replacement LRU page replacement LRU approximation page replacement counting-based page replacement page buffering algorithm,First-In

14、-First-Out (FIFO) Algorithm,置換時(shí)，選擇“the oldest one” 最簡單，但性能不是很好,缺頁15次，置換12次,Beladys Anomaly,“增加物理頁框，能降低缺頁次數(shù)”不是真理！ 考慮訪問序列: 1 2 3 4 1 2 5 1 2 3 4 5 物理頁框數(shù)為4時(shí) 1 1 1 1 1 1 5 5 5 5 4 4 2 2 2 2 2 2 1 1 1 1 5 3 3 3 3 3 3 2 2 2 2 4 4 4 4 4 4 3 3 3 物理頁框數(shù)為3時(shí) 1 1 1 4 4 4 5 5 5 5 5 5 2 2 2 1 1 1 1 1 3 3 4 3 3 3 2

15、 2 2 2 2 4 4,Page fault: 10 Page replacement: 6,Page fault: 9 Page replacement: 6,Graph,Number of frames,Number of page faults,Optimal Algorithm 最優(yōu)算法,置換在未來最長時(shí)間內(nèi)不會被使用的頁面（如果是未來永遠(yuǎn)不會使用的，最好） 保證最少缺頁率 缺點(diǎn)：必須預(yù)先知道進(jìn)程在未來的行為 very difficult to implement 因此，常用于進(jìn)行置換算法比較時(shí),缺頁9次，置換6次,LRU algorithm,LRU = Least Recently

16、 Used 最近最久未使用 Replace the page that has not been used for the longest period of time.,缺頁12次，置換9次,LRU implementation,Hard to implement efficiently: Use an extra counter (time-of-use) field in a page replace the oldest page Store a stack of page numbers replace the bottom page,使用計(jì)數(shù)器的LRU,為每個(gè)頁配備一個(gè)計(jì)數(shù)器cou

17、nter; CPU必須具備一個(gè)邏輯時(shí)鐘或者計(jì)數(shù)器 當(dāng)某個(gè)頁被訪問時(shí), 將當(dāng)前時(shí)鐘值填寫到counter中 存在更新的系統(tǒng)開銷 當(dāng)需要置換時(shí)，必須搜索所有的counter來確定置換哪個(gè)頁面 存在搜索的系統(tǒng)開銷,使用棧的LRU,利用一個(gè)特殊的棧來保存當(dāng)前使用的各個(gè)頁面的頁面號 棧的大小就是物理頁框的個(gè)數(shù) 每當(dāng)頁面被訪問時(shí) 若頁面號不在棧中，將頁面號壓入棧頂 處于最下方的頁面號，被壓出棧 若頁面號已經(jīng)在棧中，則將其從棧中移出，然后壓入棧頂 不必搜索,LRU with stack (graph),Also need hardware assistance,LRU the problems,Few ma

18、chines have sufficient hardware to support LRU so approximate it with the available hardware Many systems have a reference bit in each page With each page associate a bit, initially = 0 When page is referenced bit set to 1.(read/write) It is easy to replace the one which is 0 (if one exists). But we

19、 do not know the order,思考,考慮4個(gè)頁框和8個(gè)頁面的情況，頁框初始為空，訪問序列為0172327103時(shí)，會產(chǎn)生多少次缺頁？LRU呢？,LRU近似算法,Three variants Additional-reference-bits algorithm Second-chance algorithm Enhanced Second-chance algorithm,Second chance algorithm,每個(gè)頁設(shè)置一個(gè)訪問位（reference bit） Inspect the pages in a FIFO manner Start from current

20、oldest (FIFO) page; If the page has reference bit = 0, replace it, exit; Set its reference bit to 0; give the page a second chance Loop back to step 1. 這個(gè)算法可以用在頁表上，將頁表看成一個(gè)循環(huán)隊(duì)列，此時(shí)算法被稱為Clock算法,Second chance algorithm (contd),0,1,1,0,1,1,ref. bits,pages,Next victim,later,0,0,0,0,1,1,pages,Next victim,r

21、ef. bits,The clock page replacement algorithm.,The Clock Page Replacement Algorithm,Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639,改進(jìn)型Second-Chance Algorithm,+ modify bit Four page classes （訪問位，修改位） (0, 0) best page to replace (0, 1) not quite as good (1, 0) probably be used again soon (1, 1) probably be used again soon, and be dirty Replace the first