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