中科大操作系统原理与实现课件9_VirtualMemory1
- 格式:pdf
- 大小:405.83 KB
- 文档页数:32
第三部分. 内存管理第九章:虚拟内存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)允許部份的虛擬位址空間邏輯上連接到檔案。