虚拟内存管理

虚拟内存管理

北京工业大学软件学院张丽1整理ppt主要内容虚拟内存技术的引入虚拟内存技术概念虚拟内存的实现分页技术实现的虚拟内存2整理ppt虚拟内存技术的引入内存空间大小的问题内存空间问题的解决方法软件解决方案的根底操作系统的解决方法3整理ppt内存空间大小的问题每个程序运行所需空间不能超过可用内存程序会因不能装入内存而无法运行程序的功能越来越复杂、代码越来越长采用覆盖技术限制太大程序员在写程序时要考虑内存大小、考虑覆盖4整理ppt内存空间问题的解决方法硬件：增加内存软件：改变程序的要求问题关键：如果程序可以不用全部放在内存中就能够执行5整理ppt软件解决方案的根底并不需要所有代码和数据都放到内存中一个CPU在某个时刻只能访问一条语句或者一个数据有成熟的地址重定向技术允许程序在内存中的位置不连续且可以变化6整理ppt操作系统的解决方法不再一次把一个进程的全部信息都装入到内存中只是装入一局部然后调度进程运行其他局部等到需要时再装入7整理ppt操作系统的解决方法多大的程序都可以在有限的内存中运行程序员写程序时再不用考虑内存的大小程序员可以编写使用任意大内存空间的程序1G的程序，编译程序编址地址空间从0到1G，程序可在只有256M内存的计算机上运行程序员感觉他有1G大的内存空间，而不是256M8整理ppt虚拟内存技术虚拟内存空间程序员写程序时使用的地址空间虚拟内存技术采用虚拟空间独立编址、操作系统负责把一个大的虚拟空间的内容分阶段装入实际内存中运行的技术程序员以为自己有一很大内存空间，且独享虚拟空间受限于地址宽度32位虚拟地址，虚拟空间上限4G9整理ppt虚拟内存技术的实现内存分配访问内存淘汰10整理ppt内存分配先把程序分成假设干局部选择把一局部装载到内存中记录信息哪些局部装载到内存中，哪些没有装载到内存中的局部放在什么位置可采用页式、段式、段页式11整理ppt内存分配页式虚拟空间仍然分成页在页表中增加一个标志，表示这个页是否在内存中如果在内存中，页表中记录相应页框号12整理ppt访问内存查找页表或者段表，判断内容是否在内存中已经被装入到内存中利用页表或者段表中的信息，把虚拟地址转换成对应的物理地址未装入到内存在内存中找一块空闲空间分配给进程把要访问的内容从外存读取到内存修改页表或者段表13整理ppt淘汰如果内存中没有空闲空间，或者空闲空间低于限定值选择内存中一些正被使用的单元把里面的内容写回到外存把这些空间释放出来分配给需要的进程14整理ppt淘汰抖动选择今后不会或者最近不会用到的内容换出局部性原理一般情况下一个进程在一段时间内要访问的指令和数据都集中在一起15整理ppt虚拟内存技术实现的根底局部性原理地址重定向技术使程序在一定程度上不再受物理内存大小的限制16整理ppt分页技术实现的虚拟内存内存分配虚拟空间的管理物理内存空间分成与页面大小相同页框空闲页框管理页表内存访问缺页中断页面淘汰17整理ppt虚拟空间的管理地址长度确定虚拟空间的大小如32位的Linux操作系统的虚拟空间大小4G分为系统空间和用户空间18整理ppt空闲页框管理链表位图19整理ppt页表创立新进程时，在内存中为进程创立一个页表为进程分配内存，填写页表相关内容20整理ppt页表表项结构页面访问位A{0

页面不在内存1页面在内存0

页面未被访问1页面已被访问0

页面未被修改1页面已被修改判断缺页中断影响页面置换策略是否重写外存

页面存在位P{

页面修改位M{页号页框号

存取控制页面存在P页面访问A页面修改M外存地址21整理ppt页表大小4GB虚拟空间分成512字节大小的页，共有4*230/29=4*221=8M个页每个页的页表项占4个字节进程页表大小为8M*4B=32MB22整理ppt解决方法把页表看作是在虚拟空间中整个页表也被分页页表不全部放在内存中每次系统只装载页表的一局部放在内存中的页表页也不再连续存放23整理ppt多级页表页目录表描述哪些页表页已经在内存中、哪些还不在在内存中的页表页放在什么地方24整理ppt多级页表25整理ppt两级页表结构的地址转换26整理ppt倒排页表按页框号排序每个页框占有一个表项每个表项存放在该页框中页面的虚拟页号拥有该页面的进程标识符27整理ppt倒排页表28整理ppt倒排页表节省空间虚拟空间很大，如64位页表大小〔页面大小为4KB，每个页表项8个字节〕8*264/212=255=235*220=235G查找费时按照虚拟页号查找整个页表解决方法散列页表快表TLB29整理ppt散列页表以页号作为参数形成散列值散列表中每一项有一个链表把有相同散列值的元素链接起来每个链表元素由三局部组成页号对应的内存块号指向链表中下一个元素的指针30整理ppt散列页表31整理ppt关联高速缓存TLB实现虚拟内存引入时间开销地址转换的时间开销读取进程的页表、页面目录一次访存变成两次、三次访存动作CPU内部设置专门用来存放页表的缓存放置最近经常用到的页表项32整理ppt高速关联缓存提高查找页表项的速度以其中某一存储项内容作为地址来存取的存储器也称TLB，TranslationLookasideBuffer〔转换检测缓冲区〕33整理ppt高速关联缓存34整理ppt单元访问访问虚拟地址单元的内容按照页面的大小计算页号查询页表检查该页表项中“存在〞标志位如果存在标志位被设置按页表项中的页框号计算物理地址；如果存在标志位未被设置缺页异常35整理ppt缺页异常异常与中断异常也称为同步中断在处理器执行到由于编程失误而导致的错误指令时，或者在执行期间出现特殊情况〔如缺页〕，必须靠内核处理时，处理器就会产生一个异常中断外部硬件产生的一个电信号，从CPU的中断引脚进入，打断当前CPU的运行把需要的内容装入到内存中并设置相应的页表项36整理ppt缺页中断37整理ppt多级页表的使用计算出页表项位于哪个页表页中根据页表页号查找页目录如果页表项在内存中得到页表项在内存中的位置，读取页表项、找到页框号、计算出物理地址、访问物理单元如果页表项未在内存中，缺页异常异常处理程序创立一个新的页表页38整理ppt页面的装入预装入访问速度很快浪费空间按需装入不浪费空间浪费时间39整理ppt页面的装入通常操作系统会综合利用这两种方式创立进程时，为每个进程预装入一定数量的页面当进程执行到一定阶段，需要新页面时，再按需要装入装入要访问的页时捎带把后面的页也预装入一些局部性原理40整理ppt页面的淘汰尽量减少缺页异常的发生选择以后再也不会用到的页面淘汰选择那些再次使用的时间距离现在最远的页面淘汰41整理ppt淘汰算法最优策略〔OPT〕先进先出法〔FIFO〕第二次时机置换法〔SCR〕最近最少访问的策略〔LRU〕简化形式的LRU工作集算法工作集时钟算法42整理ppt最优策略〔OPT〕选择以后再也不会用到的页面淘汰选择那些再次使用的时间距离现在最远的页面淘汰43整理ppt最优策略〔OPT〕44整理ppt最优策略〔OPT〕操作系统需要知道将来要使用的页面顺序作为一个最好的标准用在理想的实验环境下评测其他实用的淘汰策略45整理ppt先进先出〔FIFO〕法直接换出最早装入的页面容易理解方便程序设计46整理ppt先进先出〔FIFO〕法47整理ppt先进先出〔FIFO〕法性能并不很好缺点存在Belady异常现象，即缺页率随内存块增加而增加反常的现象：内存中可装入页面数增加了，缺页异常数反而也增加了淘汰的是常用页面48整理ppt第二次时机置换法〔SCR〕SecondChancePageReplacement,SCR对FIFO算法的改进防止把经常使用的页面置换出去按时间顺序检查设置页面访问位，检查队首页面的访问位0：淘汰该页；1：转移到队尾，给第二次时机49整理ppt时钟置换法〔Clock〕将页面保存在环形链表中防止SCR法在链表中移动页面50整理ppt最近最少访问的策略LRU，LeastRecentlyUsed猜测将来可能访问的页面序列如果一个页面很久没有被访问，根据局部性原理，将来被访问的可能性也比较小选择未被访问时间最长的那些页面换出51整理pptLRU策略52整理ppt最近最少访问的策略为每个在内存中的页面维持一个计时器页面被访问时，计时器清0，否那么随时间增长操作系统要淘汰页面时，比较页面计时器，选出时间最长的页面实验说明LRU的效果比FIFO要好53整理ppt简化形式的LRULRU策略的实现开销非常大为每个页设置一个标志位，表示这个页面最近是否被访问过，称为访问位通常设置在每个页的页表项中页面被访问时，访问位设置为1操作系统定期将所有页面的访问位清0当操作系统需要挑选页面换出时，选择访问位为0的页面使用最多的策略54整理ppt工作集替换算法工作集一个进程当前正在使用的页面的集合workingset假设整个工作集都被装入内存，进程在运行到下一运行阶段前，不会产生很多缺页中断找出一个不在工作集中的页面并淘汰它工作集w(k,t)在任一时刻t，包含所有最近k次内存访问所访问过的页面的一个集合55整理ppt工作集替换算法工作集模型设法跟踪进程的工作集，以确保在让进程运行以前，它的工作集就已在内存中了跟踪进程的工作集用长度为k的移位存放器，每次内存访问把存放器左移一位，在最右端插入刚访问的页面号缺页时，读出移位存放器内容并排序，删除重复的页面，即得到工作集维护移位存放器并在缺页中断时处理它所需的开销很大，从未被用过56整理ppt工作集替换算法页表设置“访问位〞、上次访问近似时间定期的时钟中断用软件方法去除访问位替换算法过程检查页面的访问位，假设访问位1：把当前实际时间写进页表项的“上次使用时间〞域，以表示缺页中断发生时该页面正在被使用该页面在当前时钟滴答中已经被访问过，在工作集中，不应该被删除假设所有页面都被访问过，那么随机选择57整理ppt工作集替换算法替换算法过程检查页面的访问位，假设访问位0：当前时钟滴答中，该页面还没有被访问过，可以作为候选者被置换需要计算生存时间〔即当前实际运行时间减去上次使用时间〕假设生存时间大于t，那么不在工作集，置换假设不大于t，那么在工作集，不能置换假设全在工作集中，选择生存时间最长的比较费时58整理ppt工作集时钟算法以页框为元素的循环表59整理ppt页面淘汰：其他考虑尽量选择那些没有被改动的页面操作系统需要把选定淘汰页面写回到外存如果页面没有被改写，和外存中原来的页面是一样的，没有必要再重写回外存换出没有被改动的页面，只要改动该页的页表项，并在系统中标记这个页没有被使用每个页的页表项中增加一个标志位，称为“修改位〞，表示页面是否被修改正