下载文档原格式
第三部分. 内存管理第九章：虚拟内存1.介绍虚拟内存的优点及相关术语2.介绍按需调页、3.页置换算法4.以及帧分配算法1. 背景逻辑内存磁盘虚拟内存物理内存Page 0Page 1Page 2Page 0Page 1Page 2swap in页表swap out1. 背景•虚拟内存是内存管理的一种技术，它允许执行进程不必完全载入内存。
为了运行程序，可以部分程序载入到内存•优点：1.逻辑地址空间可大于物理地址空间2.可以被多个进程共享地址空间3.可以提供更有效的进程创建虚拟内存大于物理内存的图进程的虚拟地址空间是进程如何在内存中存放的逻辑视图进程的虚拟地址空间这个孔是虚拟地址的一部分，只有在堆和栈生长时，才需要实际的物理地址使用虚拟内存的共享库虚拟内存也允许共享，实现进程之间内存共享2. 按需调页执行程序如何从磁盘载入内存（全部、部分）•为执行程序需要调入页、但暂时不需要的页不会调入到物理内存−可以减少I/O−可以减少内存使用−应答时间快•那么操作系统需要区分哪些页在物理内存，哪些页在虚拟内存−有效/无效位（valide/invalide）分页的内存到连续的磁盘空间之间的传送•交换程序•调页程序有效-无效位•有效（v）：页在物理内存中•无效（i）：页不在物理内存中，即在虚拟内存中-当访问无效页时，系统会出现页错误（Page Fault）-页错误触发载入（从虚拟内存到物理内存）vvvviii….Frame #valid-invalid bit page table当有些页不在内存中时的页表Virtual memory 页不在物理内存空间里页错误•想要访问的页不在内存空间（无效页），会发生页错误，并陷入操作系统•确定该访问是否合法，不合法就结束进程，合法就进行以下操作1.找到一个空闲帧2.将所需要的页调入找到的空闲帧3.修改页表（有效、无效位），以表示该页已在物理内存中4.重新开始因陷阱而中断的指令问：要是没有空闲帧，怎么办？处理页错误的步骤可能会出现的问题？3.创建进程时使用虚拟内存的长处写时复制(Copy-on-Write)•COW 技术允许父进程和子进程共享物理内存中的页•如果任何一个进程需要对页进行写操作，那么就会创建一个共享页的副本•优点1.可以快速创建进程2.最小化新创建进程的页数问：从哪里分配空闲页？答：空闲缓冲池举例：进程1修改页C之前创建进程时，可以通过共享页的方式，暂不进行复制操作举例：进程1修改页C之后当发生写得操作的时候发生复制操作没有空闲帧可分配，怎么办？可以采取以下几种方法−终止进程−交换出一个进程，页置换（page replacement）页置换找出当前没有使用的帧，并将其换出；需要使用的页，将其换入页置换算法的性能指标：如何最小化页错误的发生，同一个页有可能多次被释放、被载入页置换是按需调页的基础，它分开了逻辑内存和物理内存，给程序员提供的巨大的内存空间4. 页置换Need for pagereplacement页置换页面置换的基本操作A.查找所需页在磁盘上的位置B.查找一个空闲帧•如果有空闲帧就用•如果没有空闲帧，就通过某种置换算法选择一个“牺牲”帧C.将所需要的页读入空闲帧，修改页表和帧表D.重启进程页置换页置换发生两次页传输（换入、换出），导致页处理时间加倍，增加了内存访问时间有效方法+ 每个页关联一个修改位（modify bit）+ 通过修改为确认关联页是否被修改--如被修改过，在换出时必须写入磁盘--如没有被修改过，在换出时，不需要写入磁盘，从而避免了写入磁盘操作页置换5. 页置换算法1.FIFO 算法2.最优置换算法3.LRU（Least Recently Used）算法4.近似LRU 算法5.基于计数的算法6.页缓冲算法置换算法Goal：最小化页错误发生利用引用串(reference string)来评估一个置换算法•引用串：一系列页的序号•评估：检查发生的页错误次数页错误和帧数量关系图物理帧和页错误成反比（more frames less page fault）（1) FIFO 页置换FIFO 算法•引用串: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5•异常现象：more frame more page fault1234125343个帧12351245434个帧FIFO Illustrating Belady’s Anomaly异常现象(2) 最优置换•置换最长时间不会用的帧(将来)•4 个帧例子1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 512345-但问题是怎么知道引用串的未来信息？-最优算法主要用于比较研究最优置换1.最长时间不会用的是72.最长时间不会用的是13.依次类推4.。
虛擬記憶體管理Demand PagingCopy--on on--write, SwappingCopy頁替換演算法, 欄配置演算法Thrashing記憶體對映檔案虛擬記憶體(virtual memory) 使行程執行於虛擬位址空間的技術次級儲存體虛擬記憶體由四部分組成, 通常使用分頁與置換來實作 虛擬位址空間(Virtual address space)行程所看到的位址空間→邏輯位址空間記憶體對映→分頁表實體記憶體■次級儲存體(硬碟) 優點具有分頁的所有優點允許行程不必完全存在實體記憶體中而執行 可允許執行需求超過實體記憶體的行程Demand Paging行程執行時只有在需要讀寫或執行某一頁的時候才把該頁置換進來範例1111--1頁的無效位元標示頁是否存在實體記憶體中，否則須載入分頁錯誤(Page fault)參考到無效頁時中斷至作業系統由磁碟載入存取時間8mson--write)(Copy--on寫入時複製(Copyfork時並不複製資料分頁，直到寫入時才複製分頁替換(Swapping) 所有記憶空間都已被使用所有記憶空間都已被使用, , 就必須替換到硬碟就必須替換到硬碟分頁替換 如果沒有空白欄可用如果沒有空白欄可用, , 即替換未使用的欄即替換未使用的欄儲存未被需求頁儲存未被需求頁, , 載入需求頁載入需求頁, , 更改分頁表更改分頁表頁替換與欄配置Demand Paging 下行程不須分配所有的記憶體 硬碟I/O 需要時間: 讀取8ms, 傳輸50us減少分頁錯誤→改善演算法頁替換演算法--FIFO替換最早替換過的頁→Belady's anomaly頁替換演算法--最佳頁替換 把未來最長時間之內不會被用到的那一頁替換掉→必須預知哪種情況最佳頁替換演算法--LRU替換近來最少使用(Least (Least--Recently Recently--Used)的頁額外的堆疊表, 將最近參考的頁置於堆疊頂端→缺少硬體支援很難實現頁替換演算法--第二次機會替換法 Intel CPU 分頁功能支援Accessed (參考位元) 讀取該頁則設為1Dirty (修改位元) 修改該頁則設為1(0, 0) 最近未使用也未被修改→最佳替換頁(0, 1) 最近末使用但曾被修改→需要寫入磁碟, 才能替換(1, 0) 最近被使用但未修改→設A 為0, 第二次機會(1, 1) 最近被使用且被修改→最有可能再被使用, 非必要不替換頁替換演算法--頁緩衝法 頁緩衝區頁被修改且需要替換時, 由系統接管, 行程可以不必等待頁的寫入分頁裝置閒置時，就選出緩衝區的頁寫入磁碟中, 該頁Dirty 位元重置為0緩衝區中的頁被參考到緩衝區中的頁被參考到, , 即歸還給行程即歸還給行程欄配置演算法每個行程的最少量有效減少分頁錯誤的最低數目每個行程可配置的最大量實體記憶體扣除作業系統所剩都可配置行程間分配行程有需要就必須配置Realtime考量是否可替換其他行程的頁? ? Realtime平均分配, 或依分頁錯誤頻率, CPU 使用率,優先權等等分配分頁錯誤頻率太高→行程需要更多的欄→配置更多欄或避免替換太低→行程擁有太多欄→優先替換輾轉現象(Thrashing)CPU 使用率降低→執行新行程→替換原有行程的頁→更多的分頁錯誤→CPU使用率更降低→…預先載入分頁(Prepaging Prepaging)) 預先載入行程所預先載入行程所需求分頁附近的分需求分頁附近的分頁頁硬碟載入分頁時硬碟載入分頁時, , 傳輸時間傳輸時間<< << 搜尋時間搜尋時間行程的分頁需求通常有區域性 行程行程開始執行開始執行時常出現時常出現大量的分頁大量的分頁錯誤錯誤記憶體對映檔案(memory mapping file)允許部份的虛擬位址空間邏輯上連接到檔案。
Chapter 9: Virtual Memory沈卓炜zwshen@h@d九龙湖校区计算机楼347房间52090919Chapter 9: Virtual Memory C apte 9tua e o yBackgroundDemand PagingCopy-on-WritePage ReplacementAllocation of FramesThrashing gMemory-Mapped FilesAllocating Kernel MemoryAllocating Kernel Memory Other ConsiderationsOperating-System ExamplesBackgroundVi t l ti f l i lVirtual memory –separation of user logical memory from physical memory.Only part of the program needs to be in memory for execution.e ecut o Logical address space can therefore be much larger than physical address space larger than physical address space.More programs can be run at the same time L I/O b d d t l dLess I/O be needed to load or swap Virtual memory can be implemented via:y pDemand pagingDemand segmentationDemand segmentationVirtual Memory That is Larger Than PhysicalMemoryVirtual-address Space tua add ess SpaceChapter 9: Virtual Memory C apte 9tua e o yBackgroundDemand PagingCopy-on-WritePage ReplacementAllocation of FramesThrashing gMemory-Mapped FilesAllocating Kernel MemoryAllocating Kernel Memory Other ConsiderationsOperating-System ExamplesDemand PagingBring a page into memory only when it is neededneeded. Less I/O neededLess memory neededFaster responsep More usersPage is needed reference to it Page is needed ⇒reference to it invalid reference ⇒abortnot-in-memory ⇒bring to memoryPure demand paging –never bring a page Pure demand paging never bring a page into memory unless page will be neededValid-Invalid Bit a d a d tWith each page table entr a alid in alid bit With each page table entry a valid–invalid bit is associated(1 ⇒in-memory, 0⇒not-in-memory)Initially valid–invalid bit is set to 0on all Initially valid invalid bit is set to 0 on all entries.D i dd t l ti if lid i lid bit During address translation, if valid–invalid bit in page table entry is 0 ⇒page fault.Page Table When Some Pages Are Not in MainMemoryPage FaultIf th i f t fi tIf there is ever a reference to a page, first reference will trap to OS ⇒page fault OS looks at another table to decide: Invalid reference abortInvalid reference ⇒abort. Just not in memory.Get empty frame.Swap page into frameSwap page into frame. Reset tables, validation bit = 1. Restart instructionblock moveblock move auto increment/decrement locationSteps in Handling a Page Fault Steps a d g a age au tPerformance of Demand Paging e o a ce o e a d ag gPage Fault Rate 0 ≤p ≤1.0if 0f ltif p = 0 no page faults if p = 1, every reference is a fault Effective Access Time (EAT) Effective Access Time (EAT)EAT = (1 –p ) x memory access+ p (page fault overhead+[swap page out ]+ [swap page out ]+ swap page in+ restart overhead)Demand Paging Example e a d ag g a p eMemory access time = 1 microsecond y50%of the time the page that is being 50% of the time the page that is being replaced has been modified and therefore d t b d tneeds to be swapped out. Swap Page Time = 10 msec = 10,000 usecEAT =(1p)x 1+p (15000)EAT = (1 –p) x 1 + p (15000)1 + 15000P (in usec)()Chapter 9: Virtual Memory C apte 9tua e o yBackgroundDemand PagingCopy-on-WritePage ReplacementAllocation of FramesThrashing gMemory-Mapped FilesAllocating Kernel MemoryAllocating Kernel Memory Other ConsiderationsOperating-System ExamplesProcess Creation ocess C eat oVirt al memor allo s other benefits d ring Virtual memory allows other benefits during process creation:-Copy-on-Write Copy on WriteM M d Fil (L t )-Memory-Mapped Files (Later)Copy-on-Write Copy o teCopy-on-Write (COW) allows both parent and child processes to initially the and child processes to initially share the same pages in memory.If either process modifies a shared page, only then is the page copied.y p g p COW allows more efficient process creation as only modified pages are copied as only modified pages are copied. Free pages are allocated from a pool of zeroed-filled pages.Chapter 9: Virtual Memory C apte 9tua e o yBackgroundDemand PagingCopy-on-WritePage ReplacementAllocation of FramesThrashing gMemory-Mapped FilesAllocating Kernel MemoryAllocating Kernel Memory Other ConsiderationsOperating-System ExamplesWhat happens if there is no freef ?frame?Page replacement find some Page replacement –find some page in memory, but not really in it tuse, swap it out algorithm gperformance –want an algorithm which will result in minimum number which will result in minimum number of page faultsSame page may be brought into Same page may be brought into memory several timesPage ReplacementPrevent over-allocation of memory by modifying page-fault service routine to modifying page fault service routine to include page replacement.U dif di t )t d h d f Use modify (dirty ) bit to reduce overhead of page transfers –only modified pages are written to disk.Page replacement completes separation Page replacement completes separation between logical memory and physical l i t l b memory –large virtual memory can be provided on a smaller physical memory.Need For Page Replacement eed o age ep ace e tBasic Page Replacement1.Find the location of the desired page on disk disk.2.Find a free frame:-If there is a free frame, use it.-If there is no free frame, use a page,p g replacement algorithm to select a victim frameframe.3.Read the desired page into the (newly) free frame. Update the page and frame tables.Restart the instruction.4.Restart the instruction.Page Replacement age ep ace e tPage Replacement Algorithms age ep ace e t go t sWant lo est page fa lt rateWant lowest page-fault rate. Evaluate algorithm by running it on a g y gparticular string of memory references(reference string)and computing the number (reference string) and computing the number of page faults on that string.I ll l th f t i i In all our examples, the reference string is 1,2,3,4,1,2,5,1,2,3,4,5.1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.Graph of Page Faults Versus The Number ofFramesFirst-In-First-Out (FIFO) Algorithm st st Out (O)go t Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 53frames (3pages can be in memory at a 3 frames (3 pages can be in memory at a time per process)1145232312349 page faultsFirst-In-First-Out (FIFO) Algorithm st st Out (O)go t 4 frames1154232312510 page faults443 FIFO Replacement –Belady’s Anomaly more frames ⇒less page faultsFIFO Page Replacement O age ep ace e tFIFO Illustrating Belady’s Anamoly O ust at g e ady s a o yOptimal AlgorithmReplace page that will not be used for longest period of time.p4 frames example1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 514236 page faultsH d k thi ?45 How do you know this? Used for measuring how well your algorithm g y g performs.Optimal Page Replacement Opt a age ep ace e tLeast Recently Used (LRU)AlgorithmReference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 454, 512534435 Counter implementationE t h t tiEvery page entry has a counter; every time page is referenced through this entry, copy the l k i t th tclock into the counter. When a page needs to be changed, look at the counters to determine which are to change.LRU Page Replacement U age ep ace e tLRU Algorithm (Cont.)U go t (Co t )Stack implementation keep a stack of Stack implementation –keep a stack of page numbers in a double link form: Page referenced:9move it to the top p9requires 6 pointers to be changedNo search for replacementNo search for replacementUse Of A Stack to Record The Most Recent PageReferencesLRU Approximation AlgorithmsReference bitWith h i t bit i iti ll 0 With each page associate a bit, initially = 0 When page is referenced bit set to 1.Replace the one which is 0 (if one exists). We do not know the order, however.,Additional-Reference-Bits AlgorithmK 8bit b t f hKeep an 8-bit bytes for each page At regular intervals shifts the bits right 1 bit, shift the reference bit into the high-order bitInterpret these 8-bit bytes as unsigned intergers, p y g g the page with lowest number is the LRU pageLRU Approximation Algorithms (Cont.)Second chanceNeed reference bit.Clock replacement.p If page to be replaced (in clock order) has reference bit =1then:reference bit 1. then:9set reference bit 0.leave page in memory9leave page in memory.9replace next page (in clock order), subject to same rules.Second-Chance (clock) Page-ReplacementAlgorithmCounting Algorithms Cou t g go t sKeep a counter of the number of references that have been made to each page. LFU Algorithm: replaces page with smallest countcount. MFU Algorithm: based on the argument that the page with the smallest count wasthe page with the smallest count was probably just brought in and has yet to be used used.Chapter 9: Virtual Memory C apte 9tua e o yBackgroundDemand PagingCopy-on-WritePage Replacement Allocation of Frames Thrashing gMemory-Mapped Files Allocating Kernel Memory Allocating Kernel Memory Other Considerations Operating-System ExamplesAllocation of Frames ocat o o a esEach process needs minimum number of pages.Example:IBM 370–6pages to handle SS Example: IBM 370 6 pages to handle SS MOVE instruction:i t ti i 6b t i ht 2instruction is 6 bytes, might span 2 pages. 2 pages to handle from . 2 pages to handle to .Two major allocation schemes Two major allocation schemes. fixed allocationpriority allocationqEqual allocation –processes, give each 20 pages. ProportionalProportional allocation –the size of process.Priority Allocation o ty ocat oUse a proportional allocation scheme sing Use a proportional allocation scheme using priorities rather than size.If process generates a page fault If process P i generates a page fault, select for replacement one of its frames.l t f l t f fselect for replacement a frame from a process with lower priority number.Global vs. Local Allocation G oba s oca ocat oreplacement process selects a Global replacement –process selects a replacement frame from the set of allframes; one process can take a frame from another.Local replacement –each process selects from only its own set of allocated frames from only its own set of allocated frames.Chapter 9: Virtual Memory C apte 9tua e o yBackgroundDemand PagingCopy-on-WritePage ReplacementAllocation of FramesThrashing gMemory-Mapped FilesAllocating Kernel MemoryAllocating Kernel Memory Other ConsiderationsOperating-System ExamplesThrashing as gIf a process does not have “enough” pages, p g p g the page-fault rate is very high. This leads to:low CPU utilization.ti t thi k th t it d t operating system thinks that it needs to increase the degree of multiprogramming. another process added to the system. Thrashing ≡a process is busy swapping pages in and out pages in and out.ThrashingWhy does paging work?Locality model Locality modelProcess migrates from one locality to another.L li i lLocalities may overlap. Why does thrashing occur?y gΣsize of locality > total memory sizeLocality In A Memory-ReferenceP tt PatternWorking-Set Model o g Set odeΔ≡working-set window ≡a fixed number of page referencesExample: 10,000 instructionp , WSS i (working set of Process P i ) =total number of pages referenced in the total number of pages referenced in the most recent Δ(varies in time)if Δtoo small will not encompass entire locality.if Δtoo large will encompass several localities. g pif Δ= ∞⇒will encompass entire program.Working-Set Model (Cont.)o g Set ode (Co t )t t l d d f D = ΣWSS i ≡total demand frames if D > m ⇒Thrashing Policy if D > m, then suspend one of the y ,p processes.Working-set model o g set ode。
