分页:较小的表

Thursday, October 31, 2019

分页:较小的表

前文我们说过,每个进程都会有一个页表,而一个页表大小为4MB(假如为32位地址,每个页4KB每个页表项4字节,那一个地址空间就有一百万个虚拟页),那这样的话,进程多了之后,将非常占用内存空间。

简单的方案:更大的页

最直接的方案就是让页更大,这样地址空间的虚拟页将会减少,但这样做的缺陷也非常明显,大内存页会造成每页内的浪费,这就被称为内部碎片。很多程序只用到了页的一部分,造成了极大的浪费,所以大多数系统都是用较小的页。

混合方法:分页和分段

我们从前面的知识可以知道,一个页表,有大量的空间试浪费的,真正用到的页表项只是很小一部分。

所以我们可以将分页和分段结合起来,不再是为一整个进程分配一个页表,而是为每个逻辑段各分配一个,比如代码,堆,栈各分配一个页表。

在之前,我们用多个基址寄存器和界限寄存器,来告诉我们段的位置和大小,在这里,我们使用基址寄存器不是指向段本身,而是保存该段的页表的物理地址,界限用于指示页表的结尾(表示有几个有效页)。

OS20.1

我们使用地址空间的前两位,来确定引用哪个段,比如00是代码段,10是堆,11是栈。现在进程里有3个基本/界限对,有3个与其关联的页表,在上下文切换时,必须更改这些寄存器。

在 TLB 未命中时,硬件使用分段位来确定使用哪个基址,界限对,然后将其中的 VPN 和物理地址结合起来,形成页表项的地址。

因为每个分段都有界限寄存器,保存了最大有效页的值,这样极大的节省了内存空间,栈和堆之间未分配的页不再占用页表的空间。

但是缺点也很明显,首先它仍需要分段,分段就不够灵活了,它需要地址空间有一定的使用模式。如果是一个大而稀疏的堆,也会造成大量的页表浪费,这种杂合也会再次导致外部碎片出现。尽管大部分内存是页面大小单位管理,但是页表现在可以是任意大小。

多级页表

多级页表,将线性页表变成了类似树的东西,非常的有效,很多现代系统都在用它。

OS20.2

多级页表的思路很简单,将页表分成页大小,如果整页的页表项无效,就完全不分配该页的页表。为了追踪页表是否有效,使用了页目录的新结构,来告诉你页表的页在哪里。

多级页表的最明显优势就是多级页表分配的空间,与你正在使用的地址空间内存量成正比,因为它通常很紧凑,并且支持稀疏的地址空间。

其次,页表的每个部分都可以整齐的放入一页中,从而更容易管理内存。使用了页目录,他指向页表的各个部分,这种间接的方式,让我们能够把页表页放在物理内存的任何地方,而无需找出一块连续的4MB的内存空间。

使用多级页表也是有成本的,比如 TLB 缓存未命中时,需要从内存加载两次,一次用于页目录,一次用于 PTE 本身。

OS20.3

超过两级

我们构建多级页表的目标是,使页表的每一部分都能放入一个页。要确定多级表中需要多少级别才能使页表的所有部分都能放入一页,首先要确定多少页表项能放入一页。假如我们有一个30位的虚拟地址空间,和512字节大小的页,假设 PTE 为4字节,那么单页为128个 PTE,需要保留 VPN 的最后7位做为索引,那么页目录就留了14位了,如果页目录有2的14次方个,那它就不是一个页了,而是128个。

所以我们需要把页目录拆分成多个页。

OS20.4

OS20.5

OS

超越物理内存:机制

分页:快速地址转换(TLB)