虚拟内存管理PPT课件

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