多级页表如何节约内存
前言
在学习计算机组成原理时,书中谈到,"使用多级页表可以压缩页表占用的内存",在了解了多级页表的原理后,恐怕对这句话还是理解不了:把页表换成多级页表了就能节约内存了?不是还是得映射所有的虚拟地址空间么?
比如做个简单的数学计算,假如虚拟地址空间为32位(即4GB)、每个页面映射4KB以及每条页表项占4B,则进程需要1M个页表项(4GB / 4KB = 1M
),即页表(每个进程都有一个页表)占用4MB(1M * 4B = 4MB
)的内存空间。而假如我们使用二级页表,还是上述条件,但一级页表映射4MB、二级页表映射4KB,则需要1K个一级页表项(4GB / 4MB = 1K
)、每个一级页表项对应1K个二级页表项(4MB / 4KB = 1K
),这样页表占用4.004MB(1K * 4B + 1K * 1K * 4B = 4.004MB
)的内存空间。多级页表的内存空间占用反而变大了?
其实我们应该换个角度来看问题,还记得计算机组成原理里面无处不在的局部性原理么?
如何节约内存
我们分两方面来谈这个问题:第一,二级页表可以不存在;第二,二级页表可以不在主存。
二级页表可以不存在
我们反过来想,每个进程都有4GB的虚拟地址空间,而显然对于大多数程序来说,其使用到的空间远未达到4GB,何必去映射不可能用到的空间呢?
也就是说,一级页表覆盖了整个4GB虚拟地址空间,但如果某个一级页表的页表项没有被用到,也就不需要创建这个页表项对应的二级页表了,即可以在需要时才创建二级页表。做个简单的计算,假设只有20%的一级页表项被用到了,那么页表占用的内存空间就只有0.804MB(1K * 4B + 0.2 * 1K * 1K * 4B = 0.804MB
),对比单级页表的4M是不是一个巨大的节约?
那么为什么不分级的页表就做不到这样节约内存呢?我们从页表的性质来看,保存在主存中的页表承担的职责是将虚拟地址翻译成物理地址;假如虚拟地址在页表中找不到对应的页表项,计算机系统就不能工作了。所以页表一定要覆盖全部虚拟地址空间,不分级的页表就需要有1M个页表项来映射,而二级页表则最少只需要1K个页表项(此时一级页表覆盖到了全部虚拟地址空间,二级页表在需要时创建)。
二级页表可以不在主存
其实这就像是把页表当成了页面。回顾一下请求分页存储管理,当需要用到某个页面时,将此页面从磁盘调入到内存;当内存中页面满了时,将内存中的页面调出到磁盘,这是利用到了程序运行的局部性原理。我们可以很自然发现,虚拟内存地址存在着局部性,那么负责映射虚拟内存地址的页表项当然也存在着局部性了!这样我们再来看二级页表,根据局部性原理,1024个第二级页表中,只会有很少的一部分在某一时刻正在使用,我们岂不是可以把二级页表都放在磁盘中,在需要时才调入到内存?我们考虑极端情况,只有一级页表在内存中,二级页表仅有一个在内存中,其余全在磁盘中(虽然这样效率非常低),则此时页表占用了8KB(1K * 4B + 1 * 1K * 4B = 8KB
),对比上一步的0.804MB,占用空间又缩小了好多倍!
总结
我们把二级页表再推广到多级页表,就会发现页表占用的内存空间更少了,这一切都要归功于对局部性原理的充分应用。
回头想想,这么大幅度地解决内存空间,我们失去了什么呢?计算机的很多问题无外乎就是时间换空间和空间换时间了,而多级页表就是典型的时间换空间的例子了,动态创建二级页表、调入和调出二级页表都是需要花费额外时间的,远没有不分级的页表来的直接;而我们也仅仅是利用局部性原理让这个额外时间开销降得比较低了而已。
参考
- Bryant R, David Richard O H. 深入理解计算机系统[M]. 机械工业出版社, 2016.
正在看CSAPP,看完第九章虚拟内存一直对多级页表如何节省内存的机制没有弄清楚,这篇文章的两点可以说是完全说明白了,感谢!
前言中计算部分是不是没有考虑这个问题:索引使用的bit数量不同。如果都用每项固定 4B 算,多级页表会吃亏。
使用单级页表时,4G内存1M个4K页,每项只需要20个bit 用来索引(其它bit用来记录关于页的其它信息),总计 20 M bits
使用二级页表时(按照你例子里的划分方式),顶级页表需要 1K 10 = 10K bit,二级页表需要 1K 1K * 10 = 10 M bits,加上顶级页表总计 10.01 M bits。
文章的前言中,"但一级页表映射4MB、二级页表映射4KB"为什么是二级页表映射是4KB啊?
而且“每个一级页表项对应1K个二级页表项(4MB / 4KB = 1K)”是不是写反了?应该是【每个二级页表项对应1K个一级页表项】
厉害!
写的很不错,最近也在研究CSAPP,但一直没明白到底是怎么节省的内存,看了好多其他的介绍也没有您写的明白,真的一下就给我点明白了,多谢多谢。喜欢您的博客。
刚好在复习,并且不懂第一个点,讲得很清楚。
谢谢楼主,很感谢,有所收获
只有一级页表在内存中,二级页表仅有一个在内存中,其余全在磁盘中(虽然这样效率非常低),则此时页表占用了8KB(1K 4B + 1 1K * 4B = 8KB),对比上一步的0.804MB,占用空间又缩小了好多倍!
这句话开头说只有一级页表在内存中,那么我的理解就是含1m个一级页的页表都在内存中,不应该是1m 4b +11k*4b =4.004mb 吗? 怎么是8kb呢? 你这描述把我彻底看晕了。
在假设二级页表映射4KB的情况下,一级页表就只需要1K个页表项而不是1M个哟~
考研时看到,这两点总结很精辟~谢谢楼主
正好对这个问题有疑惑,感谢解答,这东西书上都不写的
在复习操作系统,正好对这个知识点有疑惑。您讲得十分清楚!