虚拟地址

操作系统的职责之一是直接操作硬件并暴露更好用的接口给应用程序。操作系统直接操作的众多硬件中，就有内存。

内存需要通过地址来访问，直接访问内存的地址是物理地址。如果每个应用程序直接使用物理地址存放并读取自己的数据，会有很多问题（最典型的是程序A可以修改程序B的数据）。 所以操作系统对应用程序屏蔽了物理地址，应用程序只能使用虚拟地址来存放并读取自己的数据。操作系统拿到应用程序想要使用的虚拟地址，转化为物理地址做实际的存储，所以操作系统承担了一个中间人的身份。

假如我们需要操作一块512GB的内存，并且我们使用64bit的虚拟地址（也就是指针的大小是64bit）。512GB是2^39字节，也就是说有2^39个地址需要表示。如何用一个64bit的指针，去表示2^39个地址，是一门学问。有一种表示的方案叫做Sv39, Sv39只使用到了39个bit, 其他的bit用于拓展等用途。

操作系统在做虚拟地址到物理地址的转化，本质上操作系统需要在内存中维护一个哈希表，这个哈希表当然越小越好，接下来所述的各种方案和优化，目的都是为了让这张哈希表更小。 一个虚拟地址，经过这个哈希表，可以拿到一个物理地址。（当然实际的编程中，不是使用常见的哈希表，会有一些编程技巧）。

首先我们使用2^27个PTE，每个PTE用一个字节表示，那么2^27个PTE一共占用128MB，这么多PTE合在一起叫做Page Table。128MB确实大，后面会做优化。现在来看这种情况如何使用。 虚拟地址中的27位地址交给PTE后，可以拿到一个PPN，PPN+虚拟地址中的offset（大小是12位）可以拼接得到物理地址。虚拟地址中的offset实际上是一个页的大小，留offset实际上是部分保留了应用程序中的代码和数据的相对位置。如果不考虑Page Table的大小, offset为0的话, 代码位置自由度是最高的，实际上是操作系统去安排所有应用程序的每一个代码和数据的物理地址位置，也可以做到没有任何内存碎片， 但是代价太大了， 本质是内存只能用一半，另一半全放Page Table了。如果offset设置和物理地址一样大, 那操作系统控制不了应用程序代码直接的相对关系，只能同时服务一个应用。

如果512GB的内存中都要使用128MB来做虚拟地址到物理地址的转化，实在是太浪费了。可以使用三级缓存，也就是一级Page Table找到二级Page Table, 二级Page Table找到三级，三级找到物理地址。 这个实现思路很多人都能看懂，但是为什么这样可以节省内存？

首先，三级缓存的所有页表不可能同时都放到内存里，如果整个三级缓存的所有页表都出现，那需要2^9 + 2^9 * 2^44+2^9 * 2^44 * 2^44个PTE，也就是1.5845633e+29这么多的PTE。显然装不下。首先，确认的是如果要使用三级缓存寻址512GB的内存，1.5845633e+29这么多的PTE中的每个页表是都有可能出现的，但是我们也能确定，这么多页表不可能同时出现，甚至大部分时候就使用3到4张。这个结论的论据也比较简单，程序的局部性原理。运行过程中如果一些页表不需要使用了就可以下掉了。这相当于火车运行时，一直从火车后把铁路放到火车前面，这样总体的铁路长度就很短。

每个2^9的page table占0.5KB，如果一个进程占用的地址不超过2^21也就是2M（一张页表9bit, offset12bit），那只会分配1.5KB的page table，每大于2M会增加0.5KB的页,每多2^30既1GB（1+9+12），会多分1kb，这几乎很小很小了。