Linux Virtual Memory 细节补充

[Frank-Ye7104]

在虚拟内存优化一节中，已经提到了多级页表的使用，但仍有一些细节可以补充。
并且强烈建议改变虚拟地址中 页号 和 数组下标 的说法和思路！

多级页表优点：查找高效

一如大家都提到的节省内存的优点，多级页表的设计同样大大提高了 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位全部填满，剩余位可用于其他用途。

以上就是我学习虚拟内存的一些想法和理解，如果有错误欢迎批评指正。

[SmartKeyerror]

@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 的内容本身就不是特别好理解，因此在整理过程中会使用大量的比喻，”数组下标“这一说法更多的是想要表达索引这一功能，的确会存在歧义，后续会进行修改。

[Frank-Ye7104]

@SmartKeyerror
“页号”的说法确实能帮助理解，但是您在 mind map 中的引用最后一张图却把“页号”作为虚拟地址的一部分，有失严谨。
不如采用来自 MIT 6.S081 教材上的一张图片：

（引用该图或涉及版权，您可以重新绘制并标明原型）

[SmartKeyerror]

@Frank-Ye7104 这里我的确没注意到，感谢大佬指正