- 通过多级页表，既保证了连续（页目录号是连续的），又可以让页表占用内存小（对空的页表项，就舍弃不要）。
L22 多级页表与快表
内存分页存在的问题
内存分页也是存在问题的，为了提高内存的空间利用率，应该让一页的内存尽可能小，但页小了页表就大了，页表一大，页表的放置就会成为问题。
如下图所示，一页的大小通常为 4K，而地址是 32 位的，也就意味着，对应于 2^32 = 4G 的空间，需要 4G / 4K = 1M 的页表项，而对于每个页表项，其大小为 4 个字节，所以对于一个进程，就需要 4M 的空间用于存储其页表，如果系统中并发了 10 个进程，就需要 40M 的内存，并发了 100 个进程，就需要 400M 的内存，是很占空间的。
实际上，一个进程并不会填满整个页表，即一个进程中的逻辑地址不会占满整个 4G 的空间，如下图，0-4K，4K-8K 的逻辑地址用到了，但 8K-12K 的逻辑地址并没有用到（也就是说在该进程中，并没有 8K-12K 的逻辑地址），所以页号为 2 的这一项为空；既然页号为 2 的这一项为空，那就可以不要这个页表项，以减小页表的大小。
所以上述想法就是只有用到的逻辑页才有页表项，但由于页表中页号不连续，就需要比较、查找来找到所需的页表项。考虑一个极端的情况，如果一个进程，4G 大小的逻辑地址全部用到，所以页表中就有 4G / 4K = 1M 的页表项，即使采用折半查找，平均也需要查找 20 次，这意味着，为了访问一次逻辑地址所对应的物理内存地址，需要额外再访问内存 20 次，那操作系统的速度就会变得极慢，所以这种方法不可取。
而如果对每个进程都不管其页表项是否用得到，都用 1M 个页表项，那虽然查页表项的位置的速度快了，但太占内存，就是前面所提出的问题。
是否存在一种方法，既能让页表项连续，又能让页表占用内存小？这就要用到多级页表。
★★★多级页表
我们可以用书的章目录和节目录来类比于多级页表：
对于一本书，前面所述的一级页表相当于把书的内容分为了连续的一小节一小节（页号），然后根据每一小节（页号）来找到该小节的内容在书中的具体页数（页框号）；
而多级页表相当于先把书划分为连续的一章一章（页目录号），对每一章，又划分为一小节一小节（页号），所以如果要找到某一小节的内容，就先找该小节在哪一章（页目录号）中，继而找到该小节（页号），最终找到该小节的内容在书中的具体页数（页框号）。通过多级页表，既保证了连续（页目录号是连续的），又可以让页表占用内存小（对空的页表项，就舍弃不要）。
如下图所示，一个程序段中具体某条指令用到的 32 位逻辑地址，10 位用于页目录号、10 位用于页号，12 位（4K）用于偏移。
首先用页目录号来找到页目录；然后用页号来找到对应页目录中的某一页表项；最后根据该页表项找到实际内存中的物理页号（页框号），再加上偏移就找到了对应于逻辑地址的物理地址。
★★★注意：除了对空的页表项可以舍弃不要，对空的页目录也可以舍弃不要，如图中空白处所示（是不占内存，但是位置仍然占有着，仍然占有着位置的代价就是：例如对页目录表，就需要 4*2^10 = 4K 字节的内存空间，而不仅仅是 3*4 = 12字节的内存空间）。图中只有三个页目录，所以该程序段的页表只占有了 3*2^10*4 = 12K 字节的内存空间（该程序段占有了 3*2^10*4KB = 12M 字节的内存空间），再加上页目录表本身 4*2^10 = 4K 字节的内存空间，该程序段在页表上总共占有了 16K 字节的内存空间，相比于前面一个程序段的页表占用了 4M 字节的内存空间来说，要小得多（16K << 4M）。（注意：重点在于比较采取了多级页表前后页表所占内存空间的大小，采用多级页表前为 4M 字节，采用多级页表后为 16K 字节（例子中），而不管有没有采用多级页表，程序段占有的内存空间都是 12M 字节（由于页表项也可以为空，所以可能要小于 12M 字节））。
★快表
虽然多级页表提高了空间效率，但由于增加了进程访问内存的次数（要多访问页目录表），所以时间效率并没有提高。为了提高时间效率，又引入了快表的概念。
快表（TLB）是一组相联快速存储，是寄存器。快表中记录了最近经常使用的页号，当再次使用时，直接通过快表来得到页号对应的页框号即可，时间效率大大提高（前提是快表中有该页号，否则还是要先通过多级页表来查找该页号，然后可以选择将该页号存储在快表中，那下次再查找该页号时，就可以直接通过快表来查找了）。
快表加上多级页表，就可以保证既提高了空间效率（多级页表），也提高了时间效率（快表）。