您当前的位置:首页 > 计算机 > 编程开发 > C语言

分页机制究竟是如何实现的?

时间:05-02来源:作者:点击数:

现代操作系统都使用分页机制来管理内存,这使得每个程序都拥有自己的地址空间。每当程序使用虚拟地址进行读写时,都必须转换为实际的物理地址,才能真正在内存条上定位数据。如下图所示:

内存地址的转换是通过一种叫做页表(Page Table)的机制来完成的,这是本节要讲解的重点,即:

  • 页表是什么?为什么要采用页表机制,而不采用其他机制?
  • 虚拟地址如何通过页表转换为物理地址?

直接使用数组转换

最容易想到的映射方案是使用数组:每个数组元素保存一个物理地址,而把虚拟地址作为数组下标,这样就能够很容易地完成映射,并且效率不低。如下图所示:

但是这样的数组有 2^32 个元素,每个元素大小为4个字节,总共占用16GB的内存,显现是不现实的!

使用一级页表

既然内存是分页的,只要我们能够定位到数据所在的页,以及它在页内的偏移(也就是距离页开头的字节数),就能够转换为物理地址。例如,一个 int 类型的值保存在第 12 页,页内偏移为 240,那么对应的物理地址就是 2^12 * 12 + 240 = 49392。

2^12 为一个页的大小,也就是4K。

虚拟地址空间大小为 4GB,总共包含 2^32 / 2^12 = 2^20 = 1K * 1K  = 1M = 1048576 个页面,我们可以定义一个这样的数组:它包含 2^20 = 1M 个元素,每个元素的值为页面编号(也就是位于第几个页面),长度为4字节,整个数组共占用4MB的内存空间。这样的数组就称为页表(Page Table),它记录了地址空间中所有页的编号。

虚拟地址长度为32位,我们不妨进行一下切割,将高20位作为页表数组的下标,低12位作为页内偏移。如下图所示:

为什么要这样切割呢?因为页表数组共有 2^20 = 1M 个元素,使用虚拟地址的高20位作为下标,正好能够访问数组中的所有元素;并且,一个页面的大小为 2^12 = 4KB,使用虚拟地址的低12位恰好能够表示所有偏移。

注意,表示页面编号只需要 20 位,而页表数组的每个元素的长度却为 4 字节,即 32 位,多出 32 - 20 = 12 位。这 12 位也有很大的用处,可以用来表示当前页的相关属性,例如是否有读写权限、是否已经分配物理内存、是否被换出到硬盘等。

例如一个虚拟地址 0XA010BA01,它的高20位是 0XA010B,所以需要访问页表数组的第 0XA010B 个元素,才能找到数据所在的物理页面。假设页表数组第 0XA010B 个元素的值为 0X0F70AAA0,它的高20位为 0X0F70A,那么就可以确定数据位于第 0X0F70A 个物理页面。再来看虚拟地址,它的低12位是 0XA01,所以页内偏移也是 0XA01。有了页面索引和页内偏移,就可以算出物理地址了。经过计算,最终的物理地址为 0X0F70A * 2^12 + 0XA01 = 0X0F70A000 + 0XA01 = 0X0F70AA01。

这种思路所形成的映射关系如下图所示:

可以发现,有的页被映射到物理内存,有的被映射到硬盘,不同的映射方式可以由页表数组元素的低12位来控制。

使用这种方案,不管程序占用多大的内存,都要为页表数组分配4M的内存空间(页表数组也必须放在物理内存中),因为虚拟地址空间中的高1G或2G是被系统占用的,必须保证较大的数组下标有效。

现在硬件很便宜了,内存容量大了,很多电脑都配备4G或8G的内存,页表数组占用4M内存或许不觉得多,但在32位系统刚刚发布的时候,内存还是很紧缺的资源,很多电脑才配备100M甚至几十兆的内存,4M内存就显得有点大了,所以还得对上面的方案进行改进,压缩页表数组所占用的内存。

使用两级页表

上面的页表共有 2^20 = 2^10 * 2^10 个元素,为了压缩页表的存储空间,可以将上面的页表分拆成 2^10 = 1K = 1024 个小的页表,这样每个页表只包含 2^10 = 1K = 1024 个元素,占用 2^10 * 4 = 4KB 的内存,也即一个页面的大小。这 1024 个小的页表,可以存储在不同的物理页,它们之间可以是不连续的。

那么问题来了,既然这些小的页表分散存储,位于不同的物理页,该如何定位它们呢?也就是如何记录它们的编号(也即在物理内存中位于第几个页面)。

1024 个页表有 1024 个索引,所以不能用一个指针指向它们,必须将这些索引再保存到一个额外的数组中。这个额外的数组有1024个元素,每个元素记录一个页表所在物理页的编号,长度为4个字节,总共占用4KB的内存。我们将这个额外的数组称为页目录(Page Directory),因为它的每一个元素对应一个页表。

如此,只要使用一个指针来记住页目录的地址即可,等到进行地址转换时,可以根据这个指针找到页目录,再根据页目录找到页表,最后找到物理地址,前后共经过3次间接转换。

那么,如何根据虚拟地址找到页目录和页表中相应的元素呢?我们不妨将虚拟地址分割为三分部,高10位作为页目录中元素的下标,中间10位作为页表中元素的下标,最后12位作为页内偏移,如下图所示:

前面我们说过,知道了物理页的索引和页内偏移就可以转换为物理地址了,在这种方案中,页内偏移可以从虚拟地址的低12位得到,但是物理页索引却保存在 1024 个分散的小页表中,所以就必须先根据页目录找到对应的页表,再根据页表找到物理页索引。

例如一个虚拟地址 0011000101  1010001100  111100001010,它的高10位为 0011000101,对应页目录中的第 0011000101 个元素,假设该元素的高20位为 0XF012A,也即对应的页表在物理内存中的编号为 0XF012A,这样就找到了页表。虚拟地址中间10位为 1010001100,它对应页表中的第 1010001100 个元素,假设该元素的高20位为 0X00D20,也即物理页的索引为 0X00D20。通过计算,最终的物理地址为 0X00D20 * 2^12 + 111100001010 = 0X00D20F0A。

这种思路所形成的映射关系如下图所示:

图中的点状虚线说明了最终的映射关系。图中没有考虑映射到硬盘的情况。

采用这样的两级页表的一个明显优点是,如果程序占用的内存较少,分散的小页表的个数就会远远少于1024个,只会占用很少的一部分存储空间(远远小于4M)。

在极少数的情况下,程序占用的内存非常大,布满了4G的虚拟地址空间,这样小页表的数量可能接近甚至等于1024,再加上页目录占用的存储空间,总共是 4MB+4KB,比上面使用一级页表的方案仅仅多出4KB的内存。这是可以容忍的,因为很少出现如此极端的情况。

也就是说,使用两级页表后,页表占用的内存空间不固定,它和程序本身占用的内存空间成正比,从整体上来看,会比使用一级页表占用的内存少得多。

使用多级页表

对于64位环境,虚拟地址空间达到 256TB,使用二级页表占用的存储空间依然不小,所以会更加细化,从而使用三级页表甚至多级页表,这样就会有多个页目录,虚拟地址也会被分割成多个部分,思路和上面是一样的,不再赘述。

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门