虚拟内存管理

1、1北京工业大学软件学院 张丽操作系统2主要内容主要内容 虚拟内存技术的引入虚拟内存技术的引入 虚拟内存技术概念虚拟内存技术概念 虚拟内存的实现虚拟内存的实现 分页技术实现的虚拟内存分页技术实现的虚拟内存北京工业大学软件学院 张丽操作系统3虚拟内存技术的引入虚拟内存技术的引入 内存空间大小的问题内存空间大小的问题 内存空间问题的解决办法内存空间问题的解决办法 软件解决方案的基础软件解决方案的基础 操作系统的解决办法操作系统的解决办法北京工业大学软件学院 张丽操作系统4内存空间大小的问题内存空间大小的问题 每个程序运行所需空间不能超过可用内每个程序运行所需空间不能超过可用内存存 程序会因不能装入内

2、存而无法运行程序会因不能装入内存而无法运行 程序的功能越来越复杂、代码越来越长程序的功能越来越复杂、代码越来越长 采用覆盖技术采用覆盖技术 限制太大限制太大 程序员在写程序时要考虑内存大小、考虑程序员在写程序时要考虑内存大小、考虑覆盖覆盖北京工业大学软件学院 张丽操作系统5内存空间问题的解决办法内存空间问题的解决办法 硬件：增加内存硬件：增加内存 软件：改变程序的要求软件：改变程序的要求 问题关键：如果程序可以不用全部放在内问题关键：如果程序可以不用全部放在内存中就能够执行存中就能够执行北京工业大学软件学院 张丽操作系统6软件解决方案的基础软件解决方案的基础 并不需要所有代码和数据都放到内存中

3、并不需要所有代码和数据都放到内存中 一个一个CPU在某个时刻只能访问一条语句或在某个时刻只能访问一条语句或者一个数据者一个数据 有成熟的地址重定向技术有成熟的地址重定向技术 允许程序在内存中的位置不连续且可以变允许程序在内存中的位置不连续且可以变化化北京工业大学软件学院 张丽操作系统7操作系统的解决办法操作系统的解决办法 不再一次把一个进程的全部信息都装入到不再一次把一个进程的全部信息都装入到内存中内存中 只是装入一部分只是装入一部分 然后调度进程运行然后调度进程运行 其他部分等到需要时再装入其他部分等到需要时再装入北京工业大学软件学院 张丽操作系统8操作系统的解决办法操作系统的解决办法 多大

4、的程序都可以在有限的内存中运行多大的程序都可以在有限的内存中运行 程序员写程序时再不用考虑内存的大小程序员写程序时再不用考虑内存的大小 程序员可以编写使用任意大内存空间的程程序员可以编写使用任意大内存空间的程序序 1G的程序，编译程序编址地址空间从的程序，编译程序编址地址空间从0到到1G，程序可在只有程序可在只有256M内存的计算机上运行内存的计算机上运行 程序员感觉他有程序员感觉他有1G大的内存空间，而不是大的内存空间，而不是256M北京工业大学软件学院 张丽操作系统9虚拟内存技术虚拟内存技术 虚拟内存空间虚拟内存空间 程序员写程序时使用的地址空间程序员写程序时使用的地址空间 虚拟内存技术虚

5、拟内存技术 采用虚拟空间独立编址、操作系统负责把采用虚拟空间独立编址、操作系统负责把一个大的虚拟空间的内容分阶段装入实际一个大的虚拟空间的内容分阶段装入实际内存中运行的技术内存中运行的技术 程序员以为自己有一很大内存空间，且独享程序员以为自己有一很大内存空间，且独享 虚拟空间受限于地址宽度虚拟空间受限于地址宽度 32位虚拟地址，虚拟空间上限位虚拟地址，虚拟空间上限4G北京工业大学软件学院 张丽操作系统10虚拟内存技术的实现虚拟内存技术的实现 内存分配内存分配 访问内存访问内存 淘汰淘汰北京工业大学软件学院 张丽操作系统11内存分配内存分配 先把程序分成若干部分先把程序分成若干部分 选择把一部分

6、装载到内存中选择把一部分装载到内存中 记录信息记录信息 哪些部分装载到内存中，哪些没有哪些部分装载到内存中，哪些没有 装载到内存中的部分放在什么位置装载到内存中的部分放在什么位置 可采用页式、段式、段页式可采用页式、段式、段页式北京工业大学软件学院 张丽操作系统12内存分配内存分配 页式页式 虚拟空间仍然分成页虚拟空间仍然分成页 在页表中增加一个标志，表示这个页是否在页表中增加一个标志，表示这个页是否在内存中在内存中 如果在内存中，页表中记录相应页框号如果在内存中，页表中记录相应页框号北京工业大学软件学院 张丽操作系统13访问内存访问内存 查找页表或者段表，判断内容是否在内查找页表或者段表，判

7、断内容是否在内存中存中 已经被装入到内存中已经被装入到内存中 利用页表或者段表中的信息，把虚拟地址利用页表或者段表中的信息，把虚拟地址转换成对应的物理地址转换成对应的物理地址 未装入到内存未装入到内存 在内存中找一块空闲空间分配给进程在内存中找一块空闲空间分配给进程 把要访问的内容从外存读取到内存把要访问的内容从外存读取到内存 修改页表或者段表修改页表或者段表北京工业大学软件学院 张丽操作系统14淘汰淘汰 如果内存中没有空闲空间，或者空闲空如果内存中没有空闲空间，或者空闲空间低于限定值间低于限定值 选择内存中一些正被使用的单元选择内存中一些正被使用的单元 把里面的内容写回到外存把里面的内容写回

8、到外存 把这些空间释放出来把这些空间释放出来 分配给需要的进程分配给需要的进程北京工业大学软件学院 张丽操作系统15淘汰淘汰 抖动抖动 选择今后不会或者最近不会用到的内容选择今后不会或者最近不会用到的内容换出换出 局部性原理局部性原理 一般情况下一个进程在一段时间内要访问一般情况下一个进程在一段时间内要访问的指令和数据都集中在一起的指令和数据都集中在一起北京工业大学软件学院 张丽操作系统16虚拟内存技术虚拟内存技术 实现的基础实现的基础 局部性原理局部性原理 地址重定向技术地址重定向技术 使程序在一定程度上不再受物理内存大小使程序在一定程度上不再受物理内存大小的限制的限制北京工业大学软件学院

9、张丽操作系统17分页技术实现的虚拟内存分页技术实现的虚拟内存 内存分配内存分配 虚拟空间的管理虚拟空间的管理 物理内存空间分成与页面大小相同页框物理内存空间分成与页面大小相同页框 空闲页框管理空闲页框管理 页表页表 内存访问内存访问 缺页中断缺页中断 页面淘汰页面淘汰北京工业大学软件学院 张丽操作系统18虚拟空间的管理虚拟空间的管理 地址长度确定虚拟空间的大小地址长度确定虚拟空间的大小 如如32位的位的Linux操作系统的虚拟空间大小操作系统的虚拟空间大小4G 分为系统空间和用户空间分为系统空间和用户空间北京工业大学软件学院 张丽操作系统19空闲页框管理空闲页框管理 链表链表 位图位图北京工业

10、大学软件学院 张丽操作系统20页表页表 创建新进程时，在内存中为进程创建一创建新进程时，在内存中为进程创建一个页表个页表 为进程分配内存，填写页表相关内容为进程分配内存，填写页表相关内容北京工业大学软件学院 张丽操作系统21页表表项结构页表表项结构 页面访问位页面访问位 A A 0页面不在内存页面不在内存1 1页面在内存页面在内存0页面未被访问页面未被访问1 1页面已被访问页面已被访问0页面未被修改页面未被修改1 1页面已被修改页面已被修改判断缺页中断判断缺页中断影响页影响页面面置换策略置换策略是否重写外存是否重写外存 页面存在位页面存在位 P P 页面修改位页面修改位 M M 页号页号页框号

11、页框号 存取控制存取控制 北京工业大学软件学院 张丽操作系统22页表大小页表大小 4GB虚拟空间分成虚拟空间分成512字节大小的页，共字节大小的页，共有有 4*230/29 = 4*221 = 8M个页个页 每个页的页表项占每个页的页表项占4个字节个字节 进程页表大小为进程页表大小为 8M*4B= 32MB北京工业大学软件学院 张丽操作系统23解决办法解决办法 把页表看作是在虚拟空间中把页表看作是在虚拟空间中 整个页表也被分页整个页表也被分页 页表不全部放在内存中页表不全部放在内存中 每次系统只装载页表的一部分每次系统只装载页表的一部分 放在内存中的页表页也不再连续存放放在内存中的页表页也不再

12、连续存放 北京工业大学软件学院 张丽操作系统24多级页表多级页表 页目录表页目录表 描述哪些页表页已经在内存中、哪些还不在描述哪些页表页已经在内存中、哪些还不在 在内存中的页表页放在什么地方在内存中的页表页放在什么地方北京工业大学软件学院 张丽操作系统25多多级级页页表表北京工业大学软件学院 张丽操作系统26两级页表结构的地址转换两级页表结构的地址转换北京工业大学软件学院 张丽操作系统27倒排页表倒排页表 按页框号排序按页框号排序 每个页框占有一个表项每个页框占有一个表项 每个表项每个表项 存放在该页框中页面的虚拟页号存放在该页框中页面的虚拟页号 拥有该页面的进程标识符拥有该页面的进程标识符北

13、京工业大学软件学院 张丽操作系统28倒排页表倒排页表北京工业大学软件学院 张丽操作系统29倒排页表倒排页表 节省空间节省空间 虚拟空间很大，如虚拟空间很大，如64位位 页表大小（页面大小为页表大小（页面大小为4KB，每个页表项，每个页表项8个字节）个字节） 8*264/212= 255= 235*220 = 235G 查找费时查找费时 按照虚拟页号查找整个页表按照虚拟页号查找整个页表 解决办法解决办法 散列页表散列页表 快表快表TLB北京工业大学软件学院 张丽操作系统30散列页表散列页表 以页号作为参数形成散列值以页号作为参数形成散列值 散列表中每一项有一个链表散列表中每一项有一个链表 把有相

14、同散列值的元素链接起来把有相同散列值的元素链接起来 每个链表元素由三部分组成每个链表元素由三部分组成 页号页号 对应的内存块号对应的内存块号 指向链表中下一个元素的指针指向链表中下一个元素的指针北京工业大学软件学院 张丽操作系统31散列页表散列页表北京工业大学软件学院 张丽操作系统32关联高速缓存关联高速缓存TLB 实现虚拟内存引入时间开销实现虚拟内存引入时间开销 地址转换的时间开销地址转换的时间开销 读取进程的页表、页面目录读取进程的页表、页面目录 一次访存变成两次、三次访存动作一次访存变成两次、三次访存动作 CPU内部设置专门用来存放页表的缓存内部设置专门用来存放页表的缓存 放置最近经常用

15、到的页表项放置最近经常用到的页表项北京工业大学软件学院 张丽操作系统33高速关联缓存高速关联缓存 提高查找页表项的速度提高查找页表项的速度 以其中某一存储项内容作为地址来存取的以其中某一存储项内容作为地址来存取的存储器存储器 也称也称TLB，Translation Lookaside Buffer（转换检测缓冲区）（转换检测缓冲区） 北京工业大学软件学院 张丽操作系统34高速关联缓存高速关联缓存北京工业大学软件学院 张丽操作系统35单元访问单元访问 访问虚拟地址单元的内容访问虚拟地址单元的内容 按照页面的大小计算页号查询页表按照页面的大小计算页号查询页表 检查该页表项中检查该页表项中 “存在存

16、在”标志位标志位 如果存在标志位被设置如果存在标志位被设置 按页表项中的页框号计算物理地址；按页表项中的页框号计算物理地址； 如果存在标志位未被设置如果存在标志位未被设置 缺页异常缺页异常北京工业大学软件学院 张丽操作系统36缺页异常缺页异常 异常与中断异常与中断 异常异常 也称为同步中断也称为同步中断 在处理器执行到由于编程失误而导致的错误指令在处理器执行到由于编程失误而导致的错误指令时，或者在执行期间出现特殊情况（如缺页），时，或者在执行期间出现特殊情况（如缺页），必须靠内核处理时，处理器就会产生一个异常必须靠内核处理时，处理器就会产生一个异常 中断中断 外部硬件产生的一个电信号，从外部硬

17、件产生的一个电信号，从CPU的中断引脚的中断引脚进入，打断当前进入，打断当前CPU的运行的运行 把需要的内容装入到内存中并设置相应的把需要的内容装入到内存中并设置相应的页表项页表项北京工业大学软件学院 张丽操作系统37缺缺页页中中断断北京工业大学软件学院 张丽操作系统38多级页表的使用多级页表的使用 计算出页表项位于哪个页表页中计算出页表项位于哪个页表页中 根据页表页号查找页目录根据页表页号查找页目录 如果页表项在内存中如果页表项在内存中 得到页表项在内存中的位置，读取页表项、得到页表项在内存中的位置，读取页表项、找到页框号、计算出物理地址、访问物理找到页框号、计算出物理地址、访问物理单元单元

18、 如果页表项未在内存中，缺页异常如果页表项未在内存中，缺页异常 异常处理程序创建一个新的页表页异常处理程序创建一个新的页表页北京工业大学软件学院 张丽操作系统39页面的装入页面的装入 预装入预装入 访问速度很快访问速度很快 浪费空间浪费空间 按需装入按需装入 不浪费空间不浪费空间 浪费时间浪费时间北京工业大学软件学院 张丽操作系统40页面的装入页面的装入 通常操作系统会综合利用这两种方式通常操作系统会综合利用这两种方式 创建进程时，为每个进程预装入一定数量创建进程时，为每个进程预装入一定数量的页面的页面 当进程执行到一定阶段，需要新页面时，当进程执行到一定阶段，需要新页面时，再按需要装入再按需

19、要装入 装入要访问的页时捎带把后面的页也预装装入要访问的页时捎带把后面的页也预装入一些入一些 局部性原理局部性原理北京工业大学软件学院 张丽操作系统41页面的淘汰页面的淘汰 尽量减少缺页异常的发生尽量减少缺页异常的发生 选择以后再也不会用到的页面淘汰选择以后再也不会用到的页面淘汰 选择那些再次使用的时间距离现在最远的选择那些再次使用的时间距离现在最远的页面淘汰页面淘汰北京工业大学软件学院 张丽操作系统42淘汰算法淘汰算法 最优策略（最优策略（OPT） 先进先出法（先进先出法（FIFO） 第二次机会置换法（第二次机会置换法（SCR） 最近最少访问的策略（最近最少访问的策略（LRU） 简化形式的简

20、化形式的LRU 工作集算法工作集算法 工作集时钟算法工作集时钟算法北京工业大学软件学院 张丽操作系统43最优策略（最优策略（OPT） 选择以后再也不会用到的页面淘汰选择以后再也不会用到的页面淘汰 选择那些再次使用的时间距离现在最远的选择那些再次使用的时间距离现在最远的页面淘汰页面淘汰北京工业大学软件学院 张丽操作系统44最优策略（最优策略（OPT）北京工业大学软件学院 张丽操作系统45最优策略（最优策略（OPT） 操作系统需要知道将来要使用的页面顺序操作系统需要知道将来要使用的页面顺序 作为一个最好的标准用在理想的实验环境作为一个最好的标准用在理想的实验环境下评测其他实用的淘汰策略下评测其他实

21、用的淘汰策略北京工业大学软件学院 张丽操作系统46先进先出（先进先出（FIFO）法）法 直接换出最早装入的页面直接换出最早装入的页面 容易理解容易理解 方便程序设计方便程序设计北京工业大学软件学院 张丽操作系统47先进先出（先进先出（FIFO）法）法北京工业大学软件学院 张丽操作系统48先进先出（先进先出（FIFO）法）法 性能并不很好性能并不很好 缺点缺点 存在存在Belady异常现象，即缺页率随内存块增异常现象，即缺页率随内存块增加而增加加而增加 反常的现象：内存中可装入页面数增加了，缺页反常的现象：内存中可装入页面数增加了，缺页异常数反而也增加了异常数反而也增加了 淘汰的是常用页面淘汰的

22、是常用页面北京工业大学软件学院 张丽操作系统49第二次机会置换法（第二次机会置换法（SCR） Second Chance Page Replacement, SCR 对对FIFO算法的改进算法的改进 避免把经常使用的页面置换出去避免把经常使用的页面置换出去 按时间顺序检查按时间顺序检查 设置页面访问位，检查队首页面的访问位设置页面访问位，检查队首页面的访问位 0： 淘汰该页；淘汰该页；1：转移到队尾，给第二次机会：转移到队尾，给第二次机会北京工业大学软件学院 张丽操作系统时钟置换法（时钟置换法（Clock） 将页面保存在环形链表中将页面保存在环形链表中 避免避免SCR法法在链表中移动页面在链表

23、中移动页面50北京工业大学软件学院 张丽操作系统51最近最少访问的策略最近最少访问的策略 LRU，Least Recently Used 猜测将来可能访问的页面序列猜测将来可能访问的页面序列 如果一个页面很久没有被访问，根据局部如果一个页面很久没有被访问，根据局部性原理，将来被访问的可能性也比较小性原理，将来被访问的可能性也比较小 选择未被访问时间最长的那些页面换出选择未被访问时间最长的那些页面换出北京工业大学软件学院 张丽操作系统52LRU策略策略北京工业大学软件学院 张丽操作系统53最近最少访问的策略最近最少访问的策略 为每个在内存中的页面维持一个计时器为每个在内存中的页面维持一个计时器

24、页面被访问时，计时器清页面被访问时，计时器清0，否则随时间增长，否则随时间增长 操作系统要淘汰页面时，比较页面计时器，操作系统要淘汰页面时，比较页面计时器，选出时间最长的页面选出时间最长的页面 实验表明实验表明LRU的效果比的效果比FIFO要好要好北京工业大学软件学院 张丽操作系统54简化形式的简化形式的LRU LRU策略的实现开销非常大策略的实现开销非常大 为每个页设置一个标志位，表示这个页为每个页设置一个标志位，表示这个页面最近是否被访问过，称为访问位面最近是否被访问过，称为访问位 通常设置在每个页的页表项中通常设置在每个页的页表项中 页面被访问时，访问位设置为页面被访问时，访问位设置为1

25、 操作系统定期将所有页面的访问位清操作系统定期将所有页面的访问位清0 当操作系统需要挑选页面换出时，选择当操作系统需要挑选页面换出时，选择访问位为访问位为0的页面的页面 使用最多的策略使用最多的策略北京工业大学软件学院 张丽操作系统工作集替换算法工作集替换算法 工作集工作集 一个进程当前正在使用的页面的集合一个进程当前正在使用的页面的集合 working set 若整个工作集都被装入内存，若整个工作集都被装入内存， 进程在运进程在运行到下一运行阶段前，不会产生很多缺页行到下一运行阶段前，不会产生很多缺页中断中断 找出一个不在工作集中的页面并淘汰它找出一个不在工作集中的页面并淘汰它 工作集工作集

26、w(k, t) 在任一时刻在任一时刻t，包含所有最近，包含所有最近k次内存访问所次内存访问所访问过的页面的一个集合访问过的页面的一个集合55北京工业大学软件学院 张丽操作系统工作集替换算法工作集替换算法 工作集模型工作集模型 设法跟踪进程的工作集，以确保在让进程运设法跟踪进程的工作集，以确保在让进程运行以前，它的工作集就已在内存中了行以前，它的工作集就已在内存中了 跟踪进程的工作集跟踪进程的工作集 用长度为用长度为k的移位寄存器，每次内存访问把寄的移位寄存器，每次内存访问把寄存器左移一位，在最右端插入刚访问的页面存器左移一位，在最右端插入刚访问的页面号号 缺页时，读出移位寄存器内容并排序，删除

27、缺页时，读出移位寄存器内容并排序，删除重复的页面，即得到工作集重复的页面，即得到工作集 维护移位寄存器并在缺页中断时处理它所需维护移位寄存器并在缺页中断时处理它所需的开销很大，从未被用过的开销很大，从未被用过56北京工业大学软件学院 张丽操作系统工作集替换算法工作集替换算法 页表设置页表设置“访问位访问位”、上次访问近似时间、上次访问近似时间 定期的时钟中断用软件方法清除访问位定期的时钟中断用软件方法清除访问位 替换算法过程替换算法过程 检查页面的访问位，若访问位检查页面的访问位，若访问位 1：把当前实际时间写进页表项的：把当前实际时间写进页表项的“上次使用时间上次使用时间”域，以表示缺页中断发生时该页面正在被使用域，以表示缺页中断发生时该页面正在被使用 该页面在当前时钟滴答中已经被访问过，在工作集中，该页面在当前时钟滴答中已经被访问过，在工作集中，不应该被删除不应该被删除 若所有页面都被访问过，则随机选择若所有页面都被访问过，则随机选择57北京工业大学软件学院 张丽操作系统工作集替换算法工作集替换算法 替换算法过程替换算法过程 检查页面的访问位，若访问位检查页面的访问