虚拟内存管理.pptx

1主要内容虚拟内存技术的引入虚拟内存技术概念虚拟内存的实现分页技术实现的虚拟内存第1页/共62页2虚拟内存技术的引入内存空间大小的问题内存空间问题的解决办法软件解决方案的基础操作系统的解决办法第2页/共62页3内存空间大小的问题 每个程序运行所需空间不能超过可用内存程序会因不能装入内存而无法运行程序的功能越来越复杂、代码越来越长采用覆盖技术限制太大程序员在写程序时要考虑内存大小、考虑覆盖第3页/共62页4内存空间问题的解决办法硬件：增加内存软件：改变程序的要求问题关键：如果程序可以不用全部放在内存中就能够执行第4页/共62页5软件解决方案的基础 并不需要所有代码和数据都放到内存中一个CPU在某个时刻只能访问一条语句或者一个数据有成熟的地址重定向技术允许程序在内存中的位置不连续且可以变化第5页/共62页6操作系统的解决办法不再一次把一个进程的全部信息都装入到内存中只是装入一部分然后调度进程运行其他部分等到需要时再装入第6页/共62页7操作系统的解决办法多大的程序都可以在有限的内存中运行程序员写程序时再不用考虑内存的大小程序员可以编写使用任意大内存空间的程序1G的程序，编译程序编址地址空间从0到1G，程序可在只有256M内存的计算机上运行程序员感觉他有1G大的内存空间，而不是256M第7页/共62页8虚拟内存技术虚拟内存空间程序员写程序时使用的地址空间虚拟内存技术采用虚拟空间独立编址、操作系统负责把一个大的虚拟空间的内容分阶段装入实际内存中运行的技术程序员以为自己有一很大内存空间，且独享虚拟空间受限于地址宽度32位虚拟地址，虚拟空间上限4G第8页/共62页9虚拟内存技术的实现 内存分配 访问内存淘汰第9页/共62页10内存分配先把程序分成若干部分选择把一部分装载到内存中记录信息哪些部分装载到内存中，哪些没有装载到内存中的部分放在什么位置可采用页式、段式、段页式第10页/共62页11内存分配页式虚拟空间仍然分成页在页表中增加一个标志，表示这个页是否在内存中如果在内存中，页表中记录相应页框号第11页/共62页12访问内存查找页表或者段表，判断内容是否在内存中已经被装入到内存中利用页表或者段表中的信息，把虚拟地址转换成对应的物理地址未装入到内存在内存中找一块空闲空间分配给进程把要访问的内容从外存读取到内存修改页表或者段表第12页/共62页13淘汰如果内存中没有空闲空间，或者空闲空间低于限定值选择内存中一些正被使用的单元把里面的内容写回到外存把这些空间释放出来分配给需要的进程第13页/共62页14淘汰抖动选择今后不会或者最近不会用到的内容换出局部性原理一般情况下一个进程在一段时间内要访问的指令和数据都集中在一起第14页/共62页15虚拟内存技术实现的基础局部性原理地址重定向技术使程序在一定程度上不再受物理内存大小的限制第15页/共62页16分页技术实现的虚拟内存 内存分配虚拟空间的管理物理内存空间分成与页面大小相同页框空闲页框管理页表内存访问缺页中断页面淘汰第16页/共62页17虚拟空间的管理地址长度确定虚拟空间的大小如32位的Linux操作系统的虚拟空间大小4G分为系统空间和用户空间第17页/共62页18空闲页框管理链表位图第18页/共62页19页表创建新进程时，在内存中为进程创建一个页表为进程分配内存，填写页表相关内容第19页/共62页20页表表项结构页面访问位页面访问位 A A 0页面不在内存页面不在内存1 1页面在内存页面在内存0页面未被访问页面未被访问1 1页面已被访问页面已被访问0页面未被修改页面未被修改1 1页面已被修改页面已被修改判断缺页中断判断缺页中断影响页影响页面面置换策略置换策略是否重写外存是否重写外存 页面存在位页面存在位 P P 页面修改位页面修改位 M M 页号页号页框号页框号 存取控制 页面存在页面存在 P P 页面访问页面访问 A A 页面修改页面修改 M M 外存地址外存地址第20页/共62页21页表大小 4GB虚拟空间分成512字节大小的页，共有4*230/29=4*221=8M个页每个页的页表项占4个字节进程页表大小为 8M*4B=32MB第21页/共62页22解决办法 把页表看作是在虚拟空间中整个页表也被分页页表不全部放在内存中每次系统只装载页表的一部分放在内存中的页表页也不再连续存放 第22页/共62页23多级页表页目录表描述哪些页表页已经在内存中、哪些还不在在内存中的页表页放在什么地方第23页/共62页24多级页表第24页/共62页25两级页表结构的地址转换第25页/共62页26倒排页表按页框号排序每个页框占有一个表项每个表项存放在该页框中页面的虚拟页号拥有该页面的进程标识符第26页/共62页27倒排页表第27页/共62页28倒排页表节省空间虚拟空间很大，如64位页表大小（页面大小为4KB，每个页表项8个字节）8*264/212=255=235*220=235G查找费时按照虚拟页号查找整个页表解决办法散列页表快表TLB第28页/共62页29散列页表以页号作为参数形成散列值散列表中每一项有一个链表把有相同散列值的元素链接起来每个链表元素由三部分组成页号对应的内存块号指向链表中下一个元素的指针第29页/共62页30散列页表第30页/共62页31关联高速缓存TLB实现虚拟内存引入时间开销地址转换的时间开销读取进程的页表、页面目录一次访存变成两次、三次访存动作CPU内部设置专门用来存放页表的缓存放置最近经常用到的页表项第31页/共62页32高速关联缓存提高查找页表项的速度以其中某一存储项内容作为地址来存取的存储器也称TLB，Translation Lookaside Buffer（转换检测缓冲区）第32页/共62页33高速关联缓存第33页/共62页34单元访问访问虚拟地址单元的内容按照页面的大小计算页号查询页表检查该页表项中“存在”标志位如果存在标志位被设置按页表项中的页框号计算物理地址；如果存在标志位未被设置缺页异常第34页/共62页35缺页异常 异常与中断异常也称为同步中断在处理器执行到由于编程失误而导致的错误指令时，或者在执行期间出现特殊情况（如缺页），必须靠内核处理时，处理器就会产生一个异常中断外部硬件产生的一个电信号，从CPU的中断引脚进入，打断当前CPU的运行把需要的内容装入到内存中并设置相应的页表项第35页/共62页36缺页中断第36页/共62页37多级页表的使用计算出页表项位于哪个页表页中根据页表页号查找页目录如果页表项在内存中得到页表项在内存中的位置，读取页表项、找到页框号、计算出物理地址、访问物理单元如果页表项未在内存中，缺页异常异常处理程序创建一个新的页表页第37页/共62页38页面的装入预装入访问速度很快浪费空间按需装入不浪费空间浪费时间第38页/共62页39页面的装入通常操作系统会综合利用这两种方式创建进程时，为每个进程预装入一定数量的页面当进程执行到一定阶段，需要新页面时，再按需要装入装入要访问的页时捎带把后面的页也预装入一些局部性原理第39页/共62页40页面的淘汰尽量减少缺页异常的发生选择以后再也不会用到的页面淘汰选择那些再次使用的时间距离现在最远的页面淘汰第40页/共62页41淘汰算法最优策略（OPT）先进先出法（FIFO）第二次机会置换法（SCR）最近最少访问的策略（LRU）简化形式的LRU工作集算法工作集时钟算法第41页/共62页42最优策略（OPT）选择以后再也不会用到的页面淘汰选择那些再次使用的时间距离现在最远的页面淘汰第42页/共62页43最优策略（OPT）第43页/共62页44最优策略（OPT）操作系统需要知道将来要使用的页面顺序作为一个最好的标准用在理想的实验环境下评测其他实用的淘汰策略第44页/共62页45先进先出（FIFO）法直接换出最早装入的页面容易理解方便程序设计第45页/共62页46先进先出（FIFO）法第46页/共62页47先进先出（FIFO）法性能并不很好缺点存在Belady异常现象，即缺页率随内存块增加而增加反常的现象：内存中可装入页面数增加了，缺页异常数反而也增加了淘汰的是常用页面第47页/共62页48第二次机会置换法（SCR）Second Chance Page Replacement,SCR对FIFO算法的改进避免把经常使用的页面置换出去按时间顺序检查设置页面访问位，检查队首页面的访问位0：淘汰该页；1：转移到队尾，给第二次机会第48页/共62页时钟置换法（Clock）将页面保存在环形链表中避免SCR法在链表中移动页面49第49页/共62页50最近最少访问的策略LRU，Least Recently Used猜测将来可能访问的页面序列如果一个页面很久没有被访问，根据局部性原理，将来被访问的可能性也比较小选择未被访问时间最长的那些页面换出第50页/共62页51LRU策略第51页/共62页52最近最少访问的策略为每个在内存中的页面维持一个计时器页面被访问时，计时器清0，否则随时间增长操作系统要淘汰页面时，比较页面计时器，选出时间最长的页面实验表明LRU的效果比FIFO要好第52页/共62页53简化形式的LRULRU策略的实现开销非常大为每个页设置一个标志位，表示这个页面最近是否被访问过，称为访问位通常设置在每个页的页表项中页面被访问时，访问位设置为1操作系统定期将所有页面的访问位清0当操作系统需要挑选页面换出时，选择访问位为0的页面使用最多的策略第53页/共62页工作集替换算法工作集一个进程当前正在使用的页面的集合working set若整个工作集都被装入内存，进程在运行到下一运行阶段前，不会产生很多缺页中断找出一个不在工作集中的页面并淘汰它工作集w(k,t)在任一时刻t，包含所有最近k次内存访问所访问过的页面的一个集合54第54页/共62页工作集替换算法工作集模型设法跟踪进程的工作集，以确保在让进程运行以前，它的工作集就已在内存中了跟踪进程的工作集用长度为k的移位寄存器，每次内存访问把寄存器左移一位，在最右端插入刚访问的页面号缺页时，读出移位寄存器内容并排序，删除重复的页面，即得到工作集维护移位寄存器并在缺页中断时处理它所需的开销很大，从未被用过55第55页/共62页工作集替换算法页表设置“访问位”、上次访问近似时间定期的时钟中断用软件方法清除访问位替换算法过程检查页面的访问位，若访问位1：把当前实际时间写进页表项的“上次使用时间”域，以表示缺页中断发生时该页面正在被使用该页面在当前时钟滴答中已经被访问过，在工作集中，不应该被删除若所有页面都被访问过，则随机选择56第56页/共62页工作集替换算法替换算法过程检查页面的访问位，若访问位0：当前时钟滴答中，该页面还没有被访问过，可以作为候选者被置换需要计算生存时间（即当前实际运行时间减去上次使用时间）若生存时间大于t，则不在工作集，置换若不大于t，则在工作集，不能置换若全在工作集中，选择生存时间最长的比较费时 57第57页/共62页工作集时钟算法以页框为元素的循环表58第58页/共62页59页面淘汰：其他考虑 尽量选择那些没有被改动的页面操作系统需要把选定淘汰页面写回到外存如果页面没有被改写，和外存中原来的页面是一样的，没有必要再重写回外存换出没有被改动的页面，只要改动该页的页表项，并在系统中标记这个页没有被使用每个页的页表项中增加一个标志位，称为“修改位”，表示页面是否被修改过第59页/共62页60页表表项结构页面访问位页面访问位 A A 0页面不在内存页面不在内存1 1页面在内存页面在内存0页面未被访问页面未被访问1 1页面已被访问页面已被访问0页面未被修改页面未被修改1 1页面已被修改页面已被修改判断缺页中断判断缺页中断影响页影响页面面置换策略置换策略是否重写外存是否重写外存 页面存在位页面存在位 P P 页面修改位页面修改位 M M 页号页号页框号页框号 存取控制 页面存在页面存在 P P 页面访问页面访问 A A 页面修改页面修改 M M 外存地址外存地址第60页/共62页练习FIFO算法替换哪个页面LRU算法替换哪个页面SCR算法替换哪个页面61第61页/共62页62感谢您的观看！第62页/共62页