Linux Virtual Memory 细节补充 #11
Description
在虚拟内存优化一节中，已经提到了多级页表的使用，但仍有一些细节可以补充。
并且强烈建议改变虚拟地址中 页号 和 数组下标 的说法和思路！
多级页表优点：查找高效
一如大家都提到的节省内存的优点，多级页表的设计同样大大提高了 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位全部填满，剩余位可用于其他用途。
以上就是我学习虚拟内存的一些想法和理解，如果有错误欢迎批评指正。