《操作系统概念精要》之内存篇(三)-分页的页表结构

如题所述

第1个回答  2022-06-17

之前讨论了分段和分页,现在看下页表的主要涉及的页表结构。

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

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

其中p1表示的用来访问外部页表的索引,而p2是内部页表的页偏移。采用这种结构的地址转换方法。由于地址转换有外向内,所以这种也称为 向前映射页表

在这种分页结构的方案中,假设,系统是64位系统,那么当它的地址空间就有2^64, 当再以4KB作为地址的话,那么页表就会2^52个条目,那么就把页表进行细分,从而形成三级分层分页,四级分层分页等等。

为了装换每个逻辑地址,74位的系统需要7个级别的分页,如此多的内存访问时不可取的,从而分层分页在64位的系统并不是最优的。

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

这里书上提到的虚拟页码可以只看作是页码。(之所以叫虚拟页码,是因为根据虚拟内存的概念,逻辑地址空间可以比物理地址大,所以多出来的部分被称为虚拟的,具体介绍会在下一章提到)。

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

通常,每个进程都有一个关联的页表。该进程所使用的每个页都在也表中有一项(或者每个虚拟页都有一项)。这种表示方法比较自然,因为进程是通过虚拟地址来引用页的。然后是操作系统将这些地址转换为物理内存地址。
由于页表是按照虚拟地址排序的,操作系统可计算所对应条目在页表的位置,可以直接使用该值。这种方法缺点就是:当每个页表包含百万级的数目时。会有性能问题,而且需要大量的内存来保存页表信息。

解决的方法处理上面的两种方法外,还有一种就是 倒置页表
这里先介绍一个IBM RT 的倒置页表的表示方法:

对于每个真正的内存页或者帧,倒置页表只有一个条目。每个条目包含 保存在真正内存位置上的页的虚拟地址 ,以及拥有 该页的进程信息 。具体的过程如图:

这里的进程的信息就是以前提到的 空间地址标识符(ASID)。主要原因是由于一个倒置页表通常包含了多个不同的映射物理内存的地址空间。具体进程的每个逻辑页可映射相应的物理帧。

采用倒置页表的系统在实现共享内存的时候会有问题,因为共享内存的实现为:将多个地址空间映射到同一个物理地址。这种方法,不能用于倒置页表,因为每个物理页只有一个虚拟的页条目,一个物理页不能有多个共享的虚拟地址。

IA-32 系统的内存管理可以分为分段和分页两个部分,工作如下:CPU 生成逻辑地址,并交给分段单元,分段单元为每个逻辑地址生成 一个线性地址。 然后线性地址交给分页单元,以生成内存的物理地址。

IA-32 架构允许一个段的大小最多可以达到4G, 每个进程最多有16K个段。进程的逻辑地址空间分为两部分。
第一部分最多由8K段组成,这部分是单个进程私有;
第二部分也是最多由8K段组成,这部分是所有进程共享。

第一部分保存在 局部描述符表(LTD) 中,第二部分保存在 全局描述符表(GDT) 中,他们的每个 条目都是8个字节,包括一个段的详细信息。比如段基地址和段界限。
逻辑地址一般为二元数组(选择器,偏移),选择器是一个16位的数:

其中s表示段号,g表示实在LTD中还是在GDT中, p表示保护信息。
段的寻址过程为:

IA-32架构的页可分为4K,或者4M 。采用4K的页,IA-32采用二级分页方法。其中的32位的寻址和表示请参照二级分页算法。

为了提高物理内存的使用率,IA-32 的页表可以被交换存在磁盘。因此,页目录的条目通过一个 有效位 ,以表示该条目所指的页表实在内存还是在磁盘上。如果页表再磁盘上,则操作系统可通过其他31位来表示页表的磁盘位置。之后根据需要调入内存。

随着软件开发人员的逐步发现,32位架构的4GB内存限制,Inter通过 页地址扩展 ,以便允许访问大于4GB的物理地址空间。

引入页地址扩展,主要是将两级的分页方案扩展到了三级方案, 后者的最后两位用于指向页目录指针表。

页地址扩展使得地址地址空间从32位增加到了36位。Linux和Mac OS X 都支持了这项技术。

X86-64 支持更大的逻辑和物理地址空间。支持64位的地址空间意味着可寻址的内存达到惊人的2^64字节。64位系统有能力访问那么多的内存,但是实际上,目前设计的地址远没有那么多。
目前提供的x86-64 架构的机器最多采用四级分页,支持48位的虚拟地址。它的页面大小可以4KB,2MB,或者1G。

虽然Intel的芯片占了大部分的市场,但是移动设备的架构一直采用的是32位ARM的架构。现在的iPhone 和iPad 都或得了ARM的授权。Android的智能手机也都是ARM的处理器。
ARM支持的页面大小:

ARM架构还支持两级TLB(高速缓存)。在外部,有两个微TLB: 一个用于数据,另一个用于指令。微TLB也支持 (ASID)进程地址空间标识符。 在内部 有一个主 TLB。 地址转换从微TLB级开始。如果没有找到,那么再检查主TLB。如果还没找到,再通过页表进行硬件查找。