• 使程序在一定程度上不再受物理内存大小 的限制
16
分页技术实现的虚拟内存
北 京 工 业 大 学 软 件 学 院 张 丽
操 作 系 统
• 内存分配
– – – – 虚拟空间的管理 物理内存空间分成与页面大小相同页框 空闲页框管理 页表
• 内存访问
– 缺页中断
• 页面淘汰
17
虚拟空间的管理
北 京 工 业 大 学 软 件 学 院 张 丽
虚拟内存管理
北京工业大学软件学院 张丽
1
主要内容
北 京 工 业 大 学 软 件 学 院 张 丽
操 作 系 统
• • • •
虚拟内存技术的引入 虚拟内存技术概念 虚拟内存的实现 分页技术实现的虚拟内存
2
虚拟内存技术的引入
北 京 工 业 大 学 软 件 学 院 张 丽
操 作 系 统
• • • •
内存空间大小的问题 内存空间问题的解决办法 软件解决方案的基础 操作系统的解决办法
– 页号 – 对应的内存块号 – 指向链表中下一个元素的指针
30
散列页表
北 京 工 业 大 学 软 件 学 院 张 丽
操 作 系 统
31
关联高速缓存TLB
北 京 工 业 大 学 软 件 学 院 张 丽
操 作 系 统
• 实现虚拟内存引入时间开销
– 地址转换的时间开销 – 读取进程的页表、页面目录 – 一次访存变成两次、三次访存动作
操 作 系 统
• 按页框号排序 • 每个页框占有一个表项 • 每个表项
– 存放在该页框中页面的虚拟页号 – 拥有该页面的进程标识符
27
倒排页表
北 京 工 业 大 学 软 件 学 院 张 丽
操 作 系 统
28
倒排页表
北 京 工 业 大 学 软 件 学 院 张 丽
操 作 系 统
• 节省空间
– 虚拟空间很大，如64位
– 描述哪些页表页已经在内存中、哪些还不在 – 在内存中的页表页放在什么地方
24
北 京 工 业 大 学 软 件 学 院 张 丽
多 级 页 表
操 作 系 统
25
两级页表结构的地址转换
北 京 工 业 大 学 软 件 学 院 张 丽
操 作 系 统
26
倒排页表
北 京 工 业 大 学 软 件 学 院 张 丽
操 作 系 统
• 虚拟内存空间
– 程序员写程序时使用的地址空间
• 虚拟内存技术
– 采用虚拟空间独立编址、操作系统负责把 一个大的虚拟空间的内容分阶段装入实际 内存中运行的技术
• 程序员以为自己有一很大内存空间，且独享
• 虚拟空间受限于地址宽度
– 32位虚拟地址，虚拟空间上限4G
9
虚拟内存技术的实现
北 京 工 业 大 学 软 件 学 院 张 丽
操 作 系 统
• 内存分配 • 访问内存 • 淘汰
10
内存分配
北 京 工 业 大 学 软 件 学 院 张 丽
操 作 系 统
• 先把程序分成若干部分 • 选择把一部分装载到内存中 • 记录信息
– 哪些部分装载到内存中，哪些没有 – 装载到内存中的部分放在什么位置
• 如果页表项未在内存中，缺页异常
– 异常处理程序创建一个新的页表页
38
页面的装入
北 京 工 业 大 学 软 件 学 院 张 丽
操 作 系 统
• 预装入
– 访问速度很快 – 浪费空间
• 按需装入
– 不浪费空间 – 浪费时间
39
页面的装入
北 京 工 业 大 学 软 件 学 院 张 丽
操 作 系 统
45
先进先出（FIFO）法
北 京 工 业 大 学 软 件 学 院 张 丽
操 作 系 统
• 直接换出最早装入的页面 • 容易理解 • 方便程序设计
46
北 京 工 业 大 学 软 件 学 院 张 丽
先进先出（FIFO）法
操 作 系 统
47
先进先出（FIFO）法
北 京 工 业 大 学 软 件 学 院 张 丽
14
淘汰
北 京 工 业 大 学 软 件 学 院 张 丽
操 作 系 统
• 抖动 • 选择今后不会或者最近不会用到的内容 换出 • 局部性原理
– 一般情况下一个进程在一段时间内要访问 的指令和数据都集中在一起
15
虚拟内存技术
北 京 工 业 大 学 软 件 学 院 张 丽
操 作 系 统
• 实现的基础
– 局部性原理 – 地址重定向技术
操 作 系 统
• 地址长度确定虚拟空间的大小
– 如32位的Linux操作系统的虚拟空间大小4G
• 分为系统空间和用户空间
18
空闲页框管理
北 京 工 业 大 学 软 件 学 院 张 丽
操 作 系 统
• 链表 • 位图
19
页表
北 京 工 业 大 学 软 件 学 院 张 丽
操 作 系 统
• 创建新进程时，在内存中为进程创建一 个页表 • 为进程分配内存，填写页表相关内容
33
北 京 工 业 大 学 软 件 学 院 张 丽
高速关联缓存
操 作 系 统
34
单元访问
北 京 工 业 大 学 软 件 学 院 张 丽
操 作 系 统
• 访问虚拟地址单元的内容
– 按照页面的大小计算页号查询页表 – 检查该页表项中 “存在”标志位 – 如果存在标志位被设置
• 按页表项中的页框号计算物理地址；
• 有成熟的地址重定向技术
– 允许程序在内存中的位置不连续且可以变 化
6
操作系统的解决办法
北 京 工 业 大 学 软 件 学 院 张 丽
操 作 系 统
• 不再一次把一个进程的全部信息都装入到 内存中 • 只是装入一部分 • 然后调度进程运行 • 其他部分等到需要时再装入
7
操作系统的解决办法
北 京 工 业 大 学 软 件 学 院 张 丽
41
淘汰算法
北 京 工 业 大 学 软 件 学 院 张 丽
操 作 系 统
• • • • • • •
最优策略（OPT） 先进先出法（FIFO） 第二次机会置换法（SCR） 最近最少访问的策略（LRU） 简化形式的LRU 工作集算法 工作集时钟算法
42
最优策略（OPT）
北 京 工 业 大 学 软 件 学 院 张 丽
• 把需要的内容装入到内存中并设置相应的 页表项
36
北 京 工 业 大 学 软 件 学 院 张 丽
缺 页 中 断
操 作 系 统
37
多级页表的使用
北 京 工 业 大 学 软 件 学 院 张 丽
操 作 系 统
• 计算出页表项位于哪个页表页中 • 根据页表页号查找页目录 • 如果页表项在内存中
– 得到页表项在内存中的位置，读取页表项、 找到页框号、计算出物理地址、访问物理 单元
– 如果存在标志位未被设置
• 缺页异常
35
缺页异常
北 京 工 业 大 学 软 件 学 院 张 丽
操 作 系 统
• 异常与中断
– 异常
• 也称为同步中断 • 在处理器执行到由于编程失误而导致的错误指令 时，或者在执行期间出现特殊情况（如缺页）， 必须靠内核处理时，处理器就会产生一个异常
– 中断
• 外部硬件产生的一个电信号，从CPU的中断引脚 进入，打断当前CPU的运行
22
解决办法
北 京 工 业 大 学 软 件 学 院 张 丽
操 作 系 统
• • • • •
把页表看作是在虚拟空间中 整个页表也被分页 页表不全部放在内存中 每次系统只装载页表的一部分 放在内存中的页表页也不再连续存放
23
多级页表
北 京 工 业 大 学 软 件 学 院 张 丽
操 作 系 统
• 页目录表
• 可采用页式、段式、段页式
11
内存分配
北 京 工 业 大 学 软 件 学 院 张 丽
操 作 系 统
• 页式
– 虚拟空间仍然分成页 – 在页表中增加一个标志，表示这个页是否 在内存中 – 如果在内存中，页表中记录相应页框号
12
访问内存
北 京 工 业 大 学 软 件 学 院 张 丽
操 作 系 统
• 查找页表或者段表，判断内容是否在内 存中 • 已经被装入到内存中
北 京 工 业 大 学 软 件 学 院 张 丽
操 作 系 统
• 硬件：增加内存 • 软件：改变程序的要求
– 问题关键：如果程序可以不用全部放在内 存中就能够执行
5
软件解决方案的基础
北 京 工 业 大 学 软 件 学 院 张 丽
操 作 系 统
• 并不需要所有代码和数据都放到内存中
– 一个CPU在某个时刻只能访问一条语句或 者一个数据
• 页表大小（页面大小为4KB，每个页表项8个字节）
– 8*264/212= 255= 235*220 = 235G
• 查找费时
– 按照虚拟页号查找整个页表 – 解决办法
• 散列页表 • 快表TLB
29
散列页表
北 京 工 业 大 学 软 件 学 院 张 丽
操 作 系 统
• • • •
以页号作为参数形成散列值 散列表中每一项有一个链表 把有相同散列值的元素链接起来 每个链表元素由三部分组成
• CPU内部设置专门用来存放页表的缓存
– 放置最近经常用到的页表项
32
高速关联缓存
北 京 工 业 大 学 软 件 学 院 张 丽
操 作 系 统
• 提高查找页表项的速度 • 以其中某一存储项内容作为地址来存取的 存储器 • 也称TLB，Translation Lookaside Buffer （转换检测缓冲区）