内存需要被分成固定大小的页(Page),通过虚拟地址到物理地址的转换、才能找到实际物理地址、程序看到的地址都是虚拟地址
简单页表
1
2
3
4
5
6
7
8
9
| 虚拟内存和物理内存映射、最直观的方法就是建立一张映射表、实现虚拟内存到物理内存的一一映射
其实就是页表(Page)
这种转换会把一个内存地址分成页号Directory和偏移量Offset两个部分
前边的高位、就是内存地址的页号; 后边的地位就是内存地址里的偏移量.
地址转换的页表、只保留页号之间的映射关系即可.
同一个页面的内存、在物理层面是连续的、eg. 一个页大小为4K
需要20位的高位和12位的地位
|
内存地址转换:
- 将虚拟内存地址、切分成页号和偏移量的组合
- 从页表里边、查询出虚拟页号对应的物理页号
- 拿物理页号 + 偏移量 -> 物理内存地址
思考: 这样一个页表需要多大空间 ？
1
2
3
4
| 32位的内存地址空间、需要记录2^20大小的数组、一个页号是完整的32位的4字节、这样一个页表就需要4M的空间
并且: 每个进程都有属于自己的虚拟地址空间、也就是、每个进程都需要这样一个页表.
不管进程本身是只有几KB大小的程序、还是需要几GB这样的内存空间、都需要这样一个页表
现在的内存大多超过了4G、若使用上边的数据结构来保存页面、内存占用会更大、如何处理呢 ？
|
多级页表
1
2
3
4
5
6
7
8
9
10
| 大部分进程占用的内存是有限的、需要的页自然也是有限的、只保存 `用到的页`
之间的映射关系即可
那、是不是可以选择hash表呢 ？其实采用的是多级页表. 为什么呢 ？
在整个进程的内存地址空间、通常是 `两头实、中间空`. 在程序运行的时候、内存地址从顶部往下、
不断分配占用的桟的空间. 而堆的空间、则是从底部往上、不断分配占用的
所以、在一个世纪的程序进程里、虚拟内存占用的地址空间、通常是两段连续的空间、而不是完全散落的随机的内存地址.
而多级页表、就很适合这样的内存地址分布
|
以一个4级的多级页表为例: 同一个虚拟内存地址、偏移量的部分和简单页表一样不变、但原有的页号部分、拆成4段、从低到高、分成4级到1级这样4个页表索引
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| 对应的、一个进程会有一个4级页表、先通过4级页表索引、找到4级页表里对应的条目Entry. 存放的是一张3级页表所在的位置
4级页表的每一个条目、都对应这一张3级页表、所以可能有多张3级页表
找到对应的3级页表之后、用3级页表找对应3级索引的条目.
3级页表的索引会指向一个2级页表、同样、二级页表使用索引指向1级页表
1级页表的条目对应的数据内容是物理页号.
拿到物理页号之后、使用 `页号 + 偏移量 ` 得到最终的物理内存地址
可能有很多张1级页表、2级页表甚至3级页表、但: 因为实际的虚拟内存地址通常是连续的、可能只需要很少的2级页表、甚至只需要一张3级页表就可以了
事实上、多级页表就像一个多叉树、常称为页表树(Page Table Tree)
因为虚拟地址分布的连续性、树的第一层节点的指针、很多是空的、无需对应子树、找最终物理页号
就类似通过一个特定的访问路径、走到树最底层的叶子节点.
这样分成4级的多级页表来看、若每一级都用5个bit表示、每一张某一级的页表、只需要2^5=32个条目
若每个条目还是4个字节、共需要128字节、而一个一级索引表、对应32个4KB的、即共128KB的大小
一个填满的2级索引、对应32个1级索引、即4MB的大小
若一个进程占用8MB的内存空间、分成2个4MB的连续空间、则它需要2个独立的、填满的2级索引表、
64个1级索引表、2个独立的3级索引表、1个4级索引表、共需要64+2+2+1=69个索引表、每个128字节(9KB)
差不多只有简单页表的1/500、不过也带来了时间上的开销
原本只需要一次内存访问就可以找到物理页号、算出物理内存地址、使用4级页表的话、就需要4次内存访问、才能找到物理页号
|
思考:
内存访问比Cache的性能要差很多、原本只是要做一个简单地址转换、反而要访问好几次内存、时间性能的损耗如何优化呢 ？
— 下文分析