什么会限制虚拟内存(内存保护都是啥)

内存是计算机五大组分里的存储器,指令和数据,都要先加载到内存,才能被CPU读取执行。

Linux下,程序并不能直接访问物理内存。

什么会限制虚拟内存(内存保护都是啥)(1)

内存需被分成固定大小页(Page),再通过虚拟内存地址(Virtual Address)到物理内存地址(Physical Address)的地址转换(Address Translation),才能到达实际存放数据的物理内存位置。我们的程序看到的内存地址,都是虚拟内存地址。

那这些虚拟内存地址究竟是怎么转换成物理内存地址的呢?

简单页表

很直观啊,建张映射表,完成虚拟内存里面的页 =》物理内存页的一一映射,这就是页表(Page Table)。

页表把一个内存地址分成:

  • 页号(Directory)
  • 偏移量(Offset)

如32位内存地址:

  • 前面高位,内存地址的页号
  • 后面低位,内存地址里的偏移量

做地址转换的页表,只需保留虚拟内存地址的页号 => 物理内存地址的页号之间的映射关系

同一页里的内存,物理层面连续。比如页大小4K比特(4KiB),需20位高位,12位低位。

什么会限制虚拟内存(内存保护都是啥)(2)

一个内存地址转换,就是如下步骤:

  • 把虚拟内存地址,分为页号、偏移量
  • 从页表里,查询出虚拟页号,对应的物理页号
  • 直接拿物理页号,加上前面的偏移量,即得物理内存地址

那这样一个页表需多大空间呢?

如32位内存地址空间,页表共需记录 2^20 个到物理页号的映射关系。该存储关系就像一个2^20大小数组。一个页号是完整的32位4字节,这一个页表就要4MB

什么会限制虚拟内存(内存保护都是啥)(3)

但这空间可不是只占用一份。每个进程都有独立的虚拟内存地址空间。这意味着,每个进程都要这样一个页表。不管这进程需几KB or 几GB内存空间,都要这样一个页表。这还只是32位内存地址空间,更多的64位os,用这数组的数据结构保存页面,内存占用更大。

有啥更好的解决办法呢?

多级页表

没必要存2^20个物理页表,大部分进程所占内存有限,需要的页自然很有限。只需存那些用到的页之间的映射关系即可。是不是应该用哈希表?No!实际采用的多级页表(Multi-Level Page Table),为什么不用哈希表呢?

一个进程的内存地址空间是怎么分配的

整个进程的内存地址空间,通常“两头实、中间空”。程序运行时,内存地址从顶部往下,不断分配占用的栈的空间。而堆的空间,内存地址则是从底部往上,不断分配占用。

所以,实际程序进程里,虚拟内存占用的地址空间,通常是两段连续空间。而非完全随机的内存地址。而多级页表,就特别适合这样的内存地址分布。

示例

4级的多级页表,同样一个虚拟内存地址,偏移量的部分和上面简单页表一样,但页号部分拆成四段,从高到低,分成4级到1级,4个页表索引。

什么会限制虚拟内存(内存保护都是啥)(4)

  • 对应一个进程会有个4级页表。先通过4级页表索引,找到4级页表里对应的条目(Entry)。该条目里存放一张3级页表所在位置。4级页面里的每个条目,都对应一张3级页表,所以可能有多张3级页表。
  • 找到对应这张3级页表后,用3级索引去找到对应的3级索引的条目。3级索引的条目再会指向一个2级页表。
  • 同理,2级页表里可用2级索引指向一个1级页表。
  • 最后一层的1级页表里面的条目,对应数据内容就是物理页号。拿到物理页号,同样可用“页号 偏移量”获取物理内存地址。

可能有多张1级页表、2级页表乃至3级页表。但因实际虚拟内存空间通常连续,很可能只需很少的2级页表,甚至只需1张3级页表即可。

多级页表就像一个多叉树,所以常称为页表树(Page Table Tree)。因为虚拟内存地址分布的连续性,树第一层节点的指针,很多空的,也就无需有对应子树,不需要子树就是不需要对应2级、3级页表。找到最终物理页号,就好像通过一个特定访问路径,走到树最底层的叶节点。

什么会限制虚拟内存(内存保护都是啥)(5)

以分成4级的多级页表为例,每级若都用5比特表示。则每张某1级的页表,只需2^5=3225=32个条目。若每个条目还4字节,则共需128字节。一个1级索引表对应32个4KiB,即16KB。一个填满的2级索引表,对应32个1级索引表,即512KB。

若某进程占用1MB内存空间,分成了2个512KB连续空间。则它共需2个独立、填满的2级索引表,即64个1级索引表,2个独立3级索引表,1个4级索引表。共69个索引表,每个128字节,约9KB空间。比起4MB,差不多1/500了。

虽多级页表节约存储空间,却带来时间开销,是个“时间换空间”策略。 原进行一次地址转换,只需访问一次内存就能找到物理页号,算出物理内存地址。但用了4级页表,就得访问4次内存才能找到物理页号。内存访问比Cache慢很多,本只是做个简单的地址转换,反而要多访问了好多次内存。对这时间性能损失,如何更好解决呢?

总结

从最简单的进行虚拟页号一一映射的简单页表说起,仔细讲解了现在实际应用的多级页表。多级页表就像是一颗树。因为一个进程的内存地址相对集中和连续,所以采用这种页表树的方式,可以大大节省页表所需要的空间。而因为每个进程都需要一个独立的页表,这个空间的节省是非常可观的。

在优化页表的过程中,我们可以观察到,数组这样的紧凑的数据结构,以及树这样稀疏的数据结构,在时间复杂度和空间复杂度的差异。另外,纯粹理论软件的数据结构和硬件的设计也是高度相关的。

参考

《计算机组成与设计:硬件/软件接口》的第5.7章节

《What Every Programmer Should Know About Memory》的第4部分,Virtual Memory

,

免责声明:本文仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。文章投诉邮箱:anhduc.ph@yahoo.com

    分享
    投诉
    首页