物理内存管理(二)


上一篇文章详细讲了物理内存的连续分配,这篇文章讲一下物理内存的非连续分配

非连续内存分配的需求背景

连续分配的缺点:

  • 分配给程序的物理内存必须连续
  • 存在外碎片和内碎片
  • 内存分配的动态修改困难
  • 内存利用率较低

非连续分配的设计目标:提高内存的利用效率

  • 允许一个程序使用非连续的物理地址空间
  • 允许共享代码和数据
  • 支持动态加载和动态链接

段式存储管理

段地址空间

进程的段地址空间由多个段组成,包括:主代码段、子模块代码段、公用库代码段、堆栈段(stack)、堆数据(heap)、初始化数据段、符号表等

段式存储管理的目的:把进程的地址空间能够更细粒度和灵活的分离与共享

段访问机制

段的概念
  • 表示访问方式和存储数据等属性相同的一段地址空间
  • 对应一个连续的内存
  • 若干个段组成进程逻辑地址空间
段访问

逻辑地址由二元组(s,addr)表示,s表示段号,addr表示段内偏移,类似于寻址方式中的基址寻址。

段访问的硬件实现

页式存储管理

概念

页帧(帧、物理页面、Frame、Page Frame):

  • 把物理地址空间划分为大小相同的基本分配单位
  • 2的n次方,如512,4096,8192

页面(页、逻辑页面,Page):

  • 把逻辑地址空间也划分为相同大小的基本分配单位
  • 帧和页的大小必须是相同的

页面到页帧

  • 逻辑地址到物理地址的转换
  • 页表:保存地址转换关系
  • MMU/TLB:保证地址转换的高效进行

物理内存被划分为大小相等的帧

内存物理地址的表示:二元组(f,o),其中f是帧号(F位,共有2F个帧),o是帧内偏移(S位,每帧有2S字节)

物理地址 = f * 2S + o

进程逻辑地址口空间被划分为大小相等的页

逻辑地址也由页号和页内偏移表示

  • 页内偏移 = 帧内偏移(页和帧的大小相等)
  • 通常:页号大小 != 帧号大小

进程逻辑地址的表示:二元组(p,o),其中p表示页号(P位,共有2P个帧),o是页内偏移(S位,每帧有2S字节)

逻辑地址 = p * 2S + o

页式存储的地址映射

  • 页到帧的映射
  • 逻辑地址中的页号是连续的
  • 物理地址中的帧号是不连续的
  • 不是所有的页都有对应的帧

逻辑地址通过页表寻找对应的物理地址,页表存储着逻辑地址与物理地址之间的映射关系

页表

页表结构

每个进程都有一个页表

  • 每个页面对应一个页表项
  • 页表的内容随进程运行状态而动态变化
  • 页表基址寄存器(PTBR)指明页表的起始位置
  • 页号作为页表的索引

页表项包含两部分的内容:帧号f和页表项标志

页表项标志包括:

  • 存在位:说明内存中是否有一个物理帧与该页对应,存在为1,体现了页分配的动态性
  • 修改位:说明这个页面内容是否被修改过,修改过为1,如果被修改过,页面置换时要考虑更新外存中的镜像
  • 引用位:说明这个页面在一段时间内是否被引用过,引用过为1,用于页面置换

页式存储管理的性能问题

  • 内存访问性能问题:访问一个内存单元需要两次内存访问,第一次访问获取页表项,第二次访问获取数据,这样与连续内存分配相比,读写的性能大幅下降
  • 页表大小问题:当内存空间很大时,页表可能会非常大,页表的容量是不可忽视的,比如32位的机器,内存大小为4G,假设页面的大小是1K,则一共有222个页面,每个页表项的地址为4个字节,整个页表的大小为224个字节,也就是16M。而且每个进程都有一个页表,100个进程仅页面大小就有1600M,这是无法忽视的

有两种方法可以解决上述问题:

  • 采用Cache:利用局部性原理,减少缓存次数,TLB
  • 间接访问:多级页表,将一个长的页表切分成多个字表,先确定在哪个字表中,再去子表中寻找

快表和多级页表

快表(TLB)

快表中缓存近期访问的页表项。TLB条目由两部分组成:键(标签)和值。当关联内存通过给定值查找时,它会同时与所有的键进行比较。

  • TLB使用关联存储实现,具备快速访问性能
  • 如果TLB命中(在TLB中找到页号对应的帧号),物理页号可以很快被获取
  • 如果TLB未命中(在在TLB中找不到页号对应的帧号),对应表项被更新到TLB中

图中蓝线表示TLB命中时的情况,红线表示TLB不命中时的情况。

TLB存放在Cache中,有关Cache的详细内容可以看存储器之高速缓冲存储器这篇文章

多级页表

多级页表是通过间接引用,将页号分成多级

  • 建立页表“树”
  • 减小每级页表的长度

下面给出一个三级页表的例子:

如果所有的页表项都存在的话,那么采用多级页表并不会减小所占的内存空间,反而还会因为多了子页表占用内存会更大,但是进程不会用到所有的内存空间,所以会有很多页表项不存在,此时可以通过各级页表的存在位标记,将不存在的省掉,从而减少了内存的占用。

第一级页表的起始地址存放在固定的寄存器中(比如Intel芯片中的CR3寄存器),p1作为一级页表的索引,页表项存放着对应二级页表的起始地址,再加上p2,就可以找到三级页表的地址,以此类推,最终的子页表的形式就是前面提到的页表的形式,有帧号f和标志位,帧号加页内偏移就可以找到对应的物理地址。

反置页表

大地址空间问题

对于大地址空间(64位)系统,多级会变得特别繁琐

  • 比如5级页表,CPU要存取数据要访存6次,开销很大
  • 多进程的情况下,每个进程有一个页表,逻辑地址空间增长速度快于物理地址空间

解决方法:反置页表和页寄存器

反置页表和页寄存器是两个相似的做法,思路是:

  • 不让页表与逻辑地址空间的大小相对应
  • 让页表与物理地址空间的大小相对应

在多级页表中,页表是与逻辑地址空间相对应的,进程所使用的的每一个页都在页表中有一个页表项与之对应(无论该页表项是否有效),这样随着进程的增加,页表会消耗大量的物理内存。

反置页表和页寄存器不与逻辑地址挂钩,而与物理地址挂钩,对于每个真正的内存页或者帧才有一个条目。每个条目包含保存在真正内存位置的页的虚拟地址以及拥有该页的进程信息。因此,整个系统只有一个页表,对每个物理内存的页只有一条相应的条目。此时进程的增加和逻辑地址空间的增大都对页表占用的空间没有影响。

页寄存器

每个帧与一个页寄存器关联,寄存器的内容包括:

  • 使用位:表明此帧是否被进程占用
  • 占用页号:帧对应的页号p
  • 保护位:可读、可写、只读等

页寄存器示例:

整个物理内存的大小是16M,每页的大小是4K,那么页帧的数目是16M/4K = 4K,假设每个页寄存器占8个字节,则页寄存器占用的空间为8*4K = 32K,占整个内存的大小为32K/16M = 0.2%,此时虚拟内存的大小是任意的。

优缺点

优点:

  • 页表大小相对于物理内存而言很小
  • 页表大小与逻辑地址空间大小无关

缺点:

  • 页表信息对调后,需要根据帧号寻找页号
  • 在页寄存器中搜索逻辑地址中的页号,这个搜索是比较困难的

页寄存器中的地址转换

如何由逻辑地址寻找相应的物理地址:

  • 对逻辑地址进行Hash映射,以减少搜索范围
  • 需要解决可能存在的冲突,两个不同的逻辑地址Hash后得到相同的值

可以将快表与页寄存器结合起来,用快表缓存页表项后的页寄存器的搜索步骤:

  • 对逻辑地址进行Hash变换
  • 在快表中查找对应的页表项
  • 有冲突时遍历冲突页表项
  • 查找失败时,产生异常

但是快表本身由容量限制和功耗限制,这也限制了页寄存器机制

反置页表

反置页表与页寄存器相似,也需要做Hash,不同之处在于,反置页表将进程id也加入进去一起做Hash,Hash之后也可能存在冲突

注意反置页表是以帧号为索引的

Hash完的结果在页表中是按帧号进行排序的,每个Hash结果都对应着一个页表项,页表项包含着Hash成此位置的进程pid和逻辑页面p,还有就是下一个Hash成此位置的元素next,用来处理Hash冲突。

段页式存储管理

段式存储将进程划分为不同的段,存储时按段存储,同一个段的访问方式和存储的数据是相似的,不同的段之间很少互相访问,这样有利于内存的保护。

页式存储将内存划分为大小相等的块,在内存的利用和优化转移到后备存储方面有优势。

段页式存储就是将段式存储和页式存储的优势相结合起来。

具体做法是在段式存储管理的基础上,给每个段增加一个一级页表(多级也可以),从而将逻辑地址变为段号+页号+页内偏移,由逻辑地址转化为物理地址时,先根据段号找到相应的段表项,得到段的页表的起始位置,在根据页号在页表中找到帧号,帧号与页内偏移加起来就找到了响应的物理地址。


文章作者: likai
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 likai !
评论
 上一篇
数据结构之树 数据结构之树
前面提到的列表,队列,栈和链表都是线性的数据结构,数据元素之间都是一对一的关系,比如除了首尾元素外,内部的元素都有唯一的前驱和唯一的后缀。 除了线性结构外,另外一类数据结构是非线性结构,代表性的就是树,在非线性结构中,数据元素之间是一对多的
2020-08-02
下一篇 
物理内存管理 物理内存管理
操作系统内存管理系列之一
2020-07-29
  目录