反置页表

在分页系统中为每个进程配置一张页表，进程逻辑地址空间中的每一页，在页表中都对应有一个页表项。在现代计算机系统中通常允许一个进程的逻辑地址空间非常大，因此就有很多页表项，从而占用很多的内存空间。为了减少页表占用的内存空间而引入了反置页表(Inverted Page Table)。一般页表的表项是按页号进行排序，页表项中的内容是物理块号。而倒置页表是为每一个物理块设置一个页表项并将按物理块号排序，其中的内容则是页号及其隶属进程的标志符。

在利用反置页表进行地址变换时，是用进程标志符和页号去检索反置页表；若检索完整个页表都未找到与之匹配的页表项，表明此页此时尚未调入内存，对于具有请求调页功能的存储器系统应产生请求调页中断，若无此功能则表示地址出错；如果检索到与之匹配的表项，则该表项的序号i便是该页所在的物理块号，将该块号与页内地址一起构成物理地址。

虽然反置页表可以有效地减少页表占用的内存，然而该表中却只包含已经调入内存的页面，并未包含那些未调入内存的各个进程的页面，因而必须为每个进程建立一个外部页表(External Page Table)，该页表与传统页表一样，当所访问的页面在内存时并不访问这些页表，只是当不在主存时才使用这些页表。该页表中包含了页面在外存的物理位置，通过该页表可将所需要的页面调入内存。

由于在反置页表中是为每一个物理块设置一个页表项的，通常页表项的数目很大，从几千项到几万项，要利用进程标识符和页号去检索这样大的线性表是相当费时的。于是又利用一种Hash表来检索。