多级页表的构成及作用（操作系统原理）

1.两级页表

对于32位逻辑地址程序，若规定页面大小为4KB，则程序装入内存时页表项可达1M个。又因为每个页表项要占用若干个字节记录页框号（字节数应能够记录页框号），所以每个进程的页表就要占用几兆的内存空间；并且为了实现随机访问，还要求页表存储空间是连续的。为了解决这个问题，我们可以离散存储页表，将页表以页为单位分隔存储，建立页表的页表，即外层页表，以记录页表所在页框号。

以32位逻辑地址程序为例，按页面大小为4KB离散存储，把产生的1M个页表项进一步分成若干个页存储，并建立外层页表。若每个页表项占用4B（足够表示页框号），则一个页框会容纳1K个页表项。对于1M个页表项来说，可以分割成1K个页表，每个页表占用一个页框。再为这1K个页表建立外层页表，用一个页框正好可以容纳下1K个外层页表项，如图6-8所示。

图6-8　两级页表

按照两级页表，32位逻辑地址可以分为外层页号、页号和页内偏移。由于外层页表和页表容纳1K个页表项，则外层页号用32位逻辑地址的22～31位，页号用32位逻辑地址的12～21位，页内偏移用余下的0～11位，如图6-9所示。

图6-9　两级页表逻辑地址结构(www.xing528.com)

为了实现地址变换，系统需要增加一个外层页表寄存器。当进程从就绪态转到执行态，需要将外层页表的起始物理地址，即外层页表基址，装入外层页表寄存器中。对于任一个逻辑地址，利用其外层页号作为外层页表的索引，从外层页表中获取页表在内存中的页框号；再利用页号作为页表的索引，从页表中获取所要访问的页面在内存中的页框号；最后，将页框号与页内偏移拼接即可构成要访问的内存物理地址。图6-10显示了两级页表地址变换过程，外层页表位于5号页框，页表位于104号页框。采用两级页表，对逻辑地址所对应的物理地址访问需要经过三次内存访问，第一次是对外层页表的访问，第二次是对页表的访问，第三次是对相应内存单元的访问。

图6-10　两级页表地址变换机构

一方面，两级页表突破了页表需要大量连续内存空间存储的限制，并且，程序运行时仅需要构造外层页表和部分页表，从而减少页表占用的内存空间。以32位程序逻辑地址空间为例，外层页表号10位，则正好是2的倍数，且与222地址对齐的漏洞（这里漏洞是指程序中未用的逻辑地址空间）所对应的页表可以不用构建。另一方面，页表也可以部分构建，在外层页表项中增设一个状态位P，表示某页面的页表是否已经调入内存，若为0表示尚未调入内存，若为1表示已经调入内存。程序运行时，根据逻辑地址索引外层页表，若外层页表项P位为0，则产生一中断信号，请求OS将该页表调入内存。对于一级页表，即使程序不使用全部的逻辑地址空间，程序中存在某些地址空间漏洞，页表中仍要有这些漏洞对应的页表项，以实现页表的随机访问。

2.多级页表

对于32位计算机，程序逻辑地址空间采用32位表示，两级页表结构是合适的。但对于64位计算机，程序逻辑地址空间采用64位，采用两级页表就有些问题。如果页面仍然采用4KB，那么页表项会有252个。页框同样存储210个页表项，则外层页表项还有242个，用一个页框是无法容纳下这些外层页表项的。因此，还要对外层页表进行分页，从而建立多级页表。例如，HP 64位Alpha微处理器采用三级页表结构。