Psyduck
Psyduck copied to clipboard
SmartKeyerror
Linux Virtual Memory 细节补充
在虚拟内存优化一节中，已经提到了多级页表的使用，但仍有一些细节可以补充。 并且强烈建议改变虚拟地址中 页号 和 数组下标 的说法和思路！
多级页表优点：查找高效
一如大家都提到的节省内存的优点，多级页表的设计同样大大提高了 CPU 对页面的查找效率
以32位 CPU的虚拟地址为例，一条4字节的虚拟地址其页表基址占20位: 如果采用一级页表的方式查找，其时间复杂程度为 O(2^20); 如果采用二级页表的方式查找，其时间复杂程度为 O(2*2^10)
多级页表如何分级
多级页表的分级方式由CPU 位数以及页面大小共同决定
在过去32位 CPU 中，页面通常设置为4KB
还是以32位 CPU的虚拟地址为例，一条4字节的虚拟地址由20位页表基址和12位偏移地址构成， 那么是否有疑问：我们为什么只凭地址的高20位就能找到对应的页面呢？
在二级页表下，每级页表基址占10位，这里的基址是作为索引去对应的目录表项和页表项遍历查找的。
而具体每个目录表项和页表项的结构实际上如下图所示：
所以并不存在页号这一不规范且容易误解的说法（在每一项里面并不存在“页号”这一事物） 而”索引“更不应该引喻为“数组下标”，会让人有一种“随机存取”的错觉： 无论分不分级，这些表项都是需要存储在内存中（多级页表节省内存的根本所在）， 而在内存中的查找是字节或者字为单位逐个遍历的。
我们会发现，每一个目录表项和页表项的大小为4B，共有1024个目录表项及每个目录表项对应的1024个页表项，恰好可以存放在一个个4KB的页面中而不会出现跨页面存放现象。 也正是因此，页面表和页面的起始地址总是在 4K 字节的边界上，这些地址的低12位永远为0.
反过来我们可以思考64位 CPU 的虚拟内存地址，采用4KB页面： 先预留低12位的偏移地址，再考虑页表设计； 将每一级目录（按级数划分）的大小限定在一个页面也就是4KB内，而一条地址占有8字节， 作除法可以得到每一级目录中有512个条目，每个条目还可以继续往下一级目录分512条， 所以最少的情况下我们采用一级目录需要9位的页面基址，当然我们可以用更多级目录，那么就要留 n*9 位作为目录基址。 当然我们不必用目录基址将64位全部填满，剩余位可用于其他用途。
以上就是我学习虚拟内存的一些想法和理解，如果有错误欢迎批评指正。
@Frank-Ye7104 感谢指正和对细节的补充！
The page number is used as an index into the page table, yielding the number of the page frame corresponding to that virtual page.
这里使用"页号"这一说法主要是为了便于理解，在具体实现中的确是不存在的。
因为 OS 的内容本身就不是特别好理解，因此在整理过程中会使用大量的比喻，”数组下标“这一说法更多的是想要表达索引这一功能，的确会存在歧义，后续会进行修改。
@SmartKeyerror “页号”的说法确实能帮助理解，但是您在 mind map 中的引用最后一张图却把“页号”作为虚拟地址的一部分，有失严谨。 不如采用来自 MIT 6.S081 教材上的一张图片：
（引用该图或涉及版权，您可以重新绘制并标明原型）