操作系统基础34-页表结构

操作系统基础34-页表结构

2020-12-24 13:01·重学IT的老猫

下面将探讨组织页表的一些最常用技术,包括分层分页哈希页表倒置页表

分层分页

大多数现代计算机系统支持大逻辑地址空间(2^32〜2^64)。在这种情况下,页表本身可以非常大。例如,假设具有 32 位逻辑地址空间的一个计算机系统。如果系统的页大小为4KB(2^12),那么页表可以多达 100万的条目(2^32/2^12)。假设每个条目有4字节,那么每个进程需要4MB 物理地址空间来存储页表本身。显然,我们并不想在内存中连续地分配这个页表。这个问题的一个简单解决方法是将页表划分为更小的块。完成这种划分有多个方法。

操作系统基础34-页表结构

两级页表方案

一种方法是使用两层分页算法,就是将页表再分页(如上图 )。例如,再次假设一个系统,具有32 位逻辑地址空间和4K大小的页。一个逻辑地址被分为20位的页码和12位的页偏移。因为要对页表进行再分页,所以该页码可分为10位的页码和10位的页偏移。这样,一个逻辑地址就分为如下形式:

操作系统基础34-页表结构

其中 p1 是用来访问外部页表的索引,而 p2 是内部页表的页偏移。采用这种结构的地址转换方法如下图所示。

操作系统基础34-页表结构

两级32位分页架构的地址转换

由于地址转换由外向内,这种方案也称为向前映射页表

为了转换每个逻辑地址,64 位系统将需要多个级别的分页,太多的级别内存访问是不可取的,所以分层页表通常被认为对于64位的架构是不适当的。

哈希页表

处理大于32位地址空间的常用方法是使用哈希页表,采用虚拟页码作为哈希值。哈希页表的每一个条目都包括一个链表,该链表的元素哈希到同一位置(该链表用来解决处理碰撞)。每个元素由三个字段组成:虚拟页码,映射的帧码,指向链表内下一个元素的指针。
该算法工作如下,虚拟地址的虚拟页码哈希到哈希表,用虚拟页码与链表内的第一个元素的第一个字段相比较,如果匹配,那么相应的帧码(第二个字段)就用来形成物理地址;反之,如果不匹配,那么与链表内的后续节点的第一个字段进行比较,以查找匹配的页码。
该方案如下图所示

操作系统基础34-页表结构

哈希页表

已提出用于64位地址空间的这个方案的一个变体。此变体采用聚簇页表,类似于哈希页表;不过,哈希表内的每个条目引用多个页(例如16)不是单个页。因此,单个页表条目可以映射到多个物理帧。聚簇页表对于稀疏地址空间特别有用,这里的引用是不连续的并且散布在整个地址空间中。

倒置页表

通常,每个进程都有一个关联的页表。该进程所使用的每个页都在页表中有一项(或者每个虚拟页都有一项,不管后者是否有效)。这种表示方式比较自然,因为进程是通过虚拟地址来引用页的。操作系统应将这种引用转换成物理内存的地址。
由于页表是按虚拟地址排序的,操作系统可计算出所对应条目在页表中的位置,可以直接使用该值。这种方法的缺点之一是,每个页表可能包含数以百万计的条目。这些表可能需要大量的物理内存,以跟踪其他物理内存是如何使用的。
为了解决这个问题,我们可以使用倒置页表。对于每个真正的内存页或帧,倒置页表才有一个条目。每个条目包含保存在真正内存位置上的页的虚拟地址,以及拥有该页进程的信息。因此,整个系统只有一个页表,并且每个物理内存的页只有一条相应的条目。

操作系统基础34-页表结构

倒置页表

上图显示了倒置页表的工作原理,由于一个倒置页表通常包含多个不同的映射物理内存的地址空间,通常要求它的每个条目保存一个地址空间标识符。地址空间标识符的保存确保了,具体进程的每个逻辑页可映射到相应的物理帧。

1
2
3
4
IBM 是最早采用倒置页表的大公司:从 IBM System 38、RS/6000,到现代的 IBM Power CPU。

对 IBM RT,系统内的每个虚拟地址为一个三元组:
〈进程id,页码,偏移〉

每个倒置页表条目为二元组〈进程 id,页码〉,这里进程id用来作为地址空间的标识符。当发生内存引用时,由〈进程 id,页码〉组成的虚拟地址被提交到内存子系统。然后,搜索倒置页表来寻找匹配。如果找到匹配条目,如条目 i,则生成物理地址〈i,偏移〉。如果找不到匹配,则为非法地址访问。
虽然这种方案减少了存储每个页表所需的内存空间,但是它增加了由于引用页而查找页表所需的时间。由于倒置页表是按物理地址来排序的,而查找是根据虚拟地址的,因此查找匹配可能需要搜索整个表。这种搜索需要很长时间。
为了解决这个问题,可以使用一个哈希表,以将搜索限制在一个或最多数个页表条目。当然,每次访问哈希表也增加了一次内存引用,因此每次虚拟地址的引用至少需要两个内存读:一个用于哈希表条目,另一个用于页表。(在搜索哈希表之前,先搜索转换表缓冲区(TLB),这可改善性能。)
采用倒置页表的系统在实现共享内存时会有困难。共享内存的通常实现为,将多个虚拟地址(共享内存的每个进程都有一个虚拟地址)映射到一个物理地址。这种标准的方法不能用于倒置页表,因为每个物理页只有一个虚拟页条目,一个物理页不可能有两个(或多个)共享的虚拟地址。
解决这个问题的一个简单技术是,只允许页表包含一个虚拟地址到共享物理地址的映射。这意味着,对未映射的虚拟地址的引用会导致页错误。

参考:《操作系统概念》

-------------本文结束 感谢阅读-------------