内存管理 ： 03多级页表和快表
一、课程核心内容介绍
这一讲主要讲解多级页表和快表。在上一讲中提到的分页机制，是操作系统将物理内存打散成固定大小的页来分配内存，其优点是空间利用率高且无内存碎片。然而，单独的分页机制在实际系统中存在问题，需要通过多级页表和快表来解决，它们与分页机制结合，形成一套在实际中可高效工作的完整机制。
二、分页机制存在的问题——页表过大
分页机制存在的核心问题是页表过大。
为提高内存空间利用率，页的大小通常较小（如4K），但程序地址空间（如32位地址对应4G空间）较大，导致逻辑页号众多，每个逻辑页号都需对应一个页表项，使得页表项数量庞大。以32位地址、4K页大小为例，可算出有100万个页表项，每个页表项若占4字节，整个页表就达4兆。并且每个进程都有自己的页表，若系统中有多个进程，会占用大量内存，造成浪费。
实际上，大部分逻辑地址在程序运行中根本不会用到，例如一个普通程序的代码段和数据段远小于4G 。
因此，理论上不需要为所有逻辑页号都建立页表项，但如果只保留用到的页表项，会导致页表不连续，查找物理页号时只能采用顺序查找或折半查找等方式，大大降低指令执行速度。而若保证页表连续，即使某些逻辑页号未使用，也需占位，页表项数量依然很多，空间浪费问题无法解决。
三、解决页表过大问题的尝试——多级页表
为解决页表过大的问题，人们提出了多级页表的方案。其思想类似于书籍的章节目录，将页表分层组织，通过页目录和页表来管理逻辑页号和物理页号的对应关系。以32位地址为例，将20位地址分成两层，第一层为页目录（类似章），有2的10次方（1000个）页目录项；第二层为页表（类似节），每个页目录项对应2的10次方（1000个）页表项，每个页表项指向一个页（4K） 。
通过多级页表，在保证地址空间连续（查找快）的同时，可减少内存中存放的页表项数量。例如，某个程序使用了12兆内存，若采用单级页表需4兆空间存放页表；而采用多级页表，实际在内存中存放的页表项仅16K，大大提高了内存空间利用率。
四、多级页表带来的新问题及解决——快表
多级页表虽然提高了空间效率，但每增加一级页表，就会多一次访存操作，在时间上带来额外代价，尤其在64位系统中，访存次数增加更为明显，会严重降低系统速度。
为弥补多级页表在时间效率上的不足，引入了快表（TLB）。快表是一种相连存储器（寄存器），可快速找到最近使用的逻辑页对应的物理页号。由于寄存器昂贵，快表容量有限，只能存放少量页号。其工作方式是通过复杂硬件电路，根据页号直接查找，无需像普通查找那样逐一比较，速度极快。
当程序访问内存时，先在快表中查找逻辑页对应的物理页号，若命中（找到），则直接访问内存，大大提高访问速度；若未命中，则再去查多级页表，查到后将对应关系存入快表，以便下次快速访问。
五、快表有效工作的原因
快表能够有效工作，主要原因在于程序对地址的访问具有局部性。程序在运行过程中，访问的地址往往集中在某个局部范围内，例如循环语句会反复访问同一区域的地址。这种局部性使得在一段时间内，程序访问的逻辑页号相对固定，因此只需将这些常用的逻辑页号及其对应的物理页号存放在快表中，就能保证较高的命中率。
快表的命中率对其工作效率至关重要。命中率越高，通过快表快速访问内存的概率就越大，系统整体性能也就越好。快表的大小和替换策略会影响命中率，一般快表大小在64 - 1024之间，越大命中率越高，但成本也越高，需要在性能和成本间进行折中。同时，合理的替换策略可确保快表中始终存放最常用的页表项 。
六、总结
多级页表和快表相结合的机制，充分体现了操作系统的折中思想。多级页表保证了页表项的连续性，提高了内存空间利用率；快表则弥补了多级页表在时间效率上的不足。两者有机结合，使得分页机制在空间和时间上都具有较高效率，成为现实操作系统中常用的内存管理机制。