计算机基础

发布日期: 2022-11-06

文章字数: 2.2k

阅读时长: 8 分

阅读次数:

问题：page table过大

前面说到，每个程序（或者进程）都有一个page table，以此来区分它和其他的进程，彼此之间互不干扰。而且，每个page table都保存在内存中。但是随着程序或者多进程程序的增多，内存的容量入不敷出。

举例：page table占据的空间

举例说明，对于32位的virtual address，4KiB的page size（12bits），page table中共有 $2^{20}$ 个entry，如果每个entry共4个bytes，则一个page table需要占据 $2^{22}$ 个bytes，共4MiB。

因此，一个process对应4MiB的page table，成百上千的process需要的内存空间非常大。更不用说，现在的地址均为64位的，则需要的内存空间更大。

一些解决办法

那么如何减少page table占据的内存空间呢？一般来说，有5种方法。

dynamic page table with a single direction

前面的page table的问题：容量的大小在初始阶段已经确定，但是一个process可能用不了那么大的page table。

解决思路：最简单的方式是让page table的大小随着process使用的内存增多而逐渐增多。

解决方式：这种方法可以通过设置一个limit register来解决，给每个process一个固定的初始page table容量，当超过该容量时，就随着process占据的virtual address space的增多而增加。

方法的不足：这种方法，要求address space只能向一个方向扩展。

dynamic page table with both directions

上述方法的问题：address space只能向一个方向扩展，受到一些编程语言的限制，比如C++：

stack的内存地址向下增长；
heap的内存地址向上增长；

解决思路：将address space划分，同时支持向两个方向扩展。

解决方法：与上述方法相同。此时，需要两个单独的page tables和对应的limit registers。对于virtual address也要进行划分，用来指定去哪个page table完成映射，如下所示，通过提供一个bit进行标识。

使用一个bit划分两个page table

其中，通过hight-order bit决定去哪个page table完成映射；
每个分开的page table的大小最多是原来的一半；最小是limit register指定的数量；
这种划分，对于上层的应用来说完全感知不到，可以像往常一样操作；
此时，每个page table的大小取决于程序中使用的stack空间多还是heap 空间多。

这种方法的主要缺点是当address space以稀疏sparse的方式使用，而不是以连续的virtual address的方式使用时，工作地并不好。

这里效果不好的原因（包括上一个方法），我的理解是这样的，因为page table的初始大小受到limit register的限制，当地址扩展时，page table的容量也会扩展，但是地址的扩展有两种方式：

一是稳定地扩展，这样page table的容量也会稳定的增长，方法在这种场景下表现很好；

二是不稳定扩展，例如，第一次访问内存的virtual page number是page table的第一个，而第二次访问的virtual page number是最后一个，则会导致，page table的容量一下子从初始大小扩展到最大的容量，这种稀疏的内存地址扩展方式，使得这种方法效果不好。

inverted page table

通过对virtual address 使用hashing function，可以减少page table的size。因为，此时page table中的entry的数量是physical pages的数量，不是virtual pages的数量（两者之间，相差2个bit，则相差4倍）。这样的结构称为inverted page table。

但是这种结构中，对于page table的查找很复杂，因为不能通过virtual page number索引整个page table。

关于inverted page table的内容，可以继续参考如下材料：

multilevel page table

通过多级page table可以减少page table占据的空间。这种方式可以忽略一些不需要内存page的地址，也就不需要进行地址转换，即，核心在于，我们只需要存储那些需要访问的内存地址的映射关系即可。

上述的方法中，不管内存地址是否会被使用，只要后续的地址被访问，其前面的内存映射关系就会占据page table存储空间，举例说明：当process访问地址0x00020000对应的内存时，那么在page table中一定会为0x00010000保存了映射关系需要的存储空间。

多级页表可以有效解决这个问题，首先先看一下多级页表的结构，本质上是一个多叉树，如下：

多级页表的结构

对于一个virtual address分成两个部分：

对应multilevel page table的索引；
page offset

一个对应multilevel page table的索引又分为了4个部分，分别对应不同level的page table的索引，每个索引占据5个bits。

对于第4级索引，对应一个page table，该索引能找到该table中的一个entry，整个表共有 $2^5 = 32$个entries，每个entry中存储的并不是physical page number，而是下一级page table的地址，因此一个4th page table可以对应32个3rd page tables。对于一个32位的地址来说，每个entry需要占据4KiB的空间，因此4th page table需要占据 32*4 = 128KiB的空间。
当通过4th entry中的地址找到对应的3rd page table时，就可以通过3rd level的索引在该page table中找到2nd page table的地址。同样的，每个3rd page table也有32个entries，占据了128KiB的空间。
找到2nd page table后，可以通过2nd level的索引找到1rt page table，之后在该page table中找到对应的physical page number，其与page offset结合，共同组成真实的physical address。

这就是整个virtual address被划分为多级索引，从而在多级page table中映射physical address的过程。前面我们说了multilevel page table能够减少存储空间，下面分析一下上述的结构共占据多少空间。

多级页表占据的存储空间

整个结构为一个多叉树：

level	page table数量	每个page table的entry数量	每个entry的大小	占据的总空间
4	1	32	4KiB	128KiB
3	32	32	4KiB	4096KiB
2	32 * 32=1024	32	4KiB	131072KiB
1	32 * 32 * 32=32768	32	4KiB	4194304KiB

将所有的占据空间加和得到：

$$
128 + 4096 + 131072 + 4194304 = 4329600 \text{KiB} = 4.129\text{GB}
$$

WTF？用了多级页表后，怎么page table占据的空间更大了？注意，这只是理论上的，实际当中，基本不会需要这么大的存储空间。这是因为局部性原理，程序运行时，stack是从上向下增长的，heap是从下向上增长的，也就是说内存地址的空间趋向于连续，这是空间局部性原理产生的效果。

这会造成什么影响？在多级页表中进行查询时，只会沿着特定的路径完成地址映射，如上图中的红色框图，也就是说，对于一个process而言，其使用的4th pt和3rd pt，甚至是2nd pt可能一直是同一个，这种情况下，只需要一级page table保持32个（占满，实际也有可能不会满），则占据的存储空间为：

$$
4 + 4 + 4 + 128 = 140 \text{KiB}
$$

相比于之前的4MB存储空间，大大减少了。

除了减少了存储空间，这种方法还有一个好处，尤其是相比上述的dynamic page table，即支持address space以稀疏sparse的方式使用，即便再稀疏，只会保存使用的page的地址映射关系，对于不需要的，则不会保存，这种支持特别有利于以非连续的方式分配address space的软件程序。

但是这种方法也有缺点：前面说过page table是驻留在内存中的，在之前的方法中，一个virtual page number对应一个physical page number，只需要访问一次内存就可以完成地址转换。现在分成了4个level的page tables，需要访问4次内存，理论上需要的地址转换时间是之前的4倍，不仅更复杂了，而且还需要更多的时间。这是典型的以时间换空间的策略。

Make page tables paged

这种方法有时也称为virtualized page tables，核心思想在于将page table视为普通的内存。因此，也可以将page table放到virtual address space，但是这种方法会有严重的问题——never-ending series of page faults，详细内容可以参考以下资料：