《操作系统原理》学习笔记:第4章 非连续内存分配

2021/11/22 7:13:53

本文主要是介绍《操作系统原理》学习笔记:第4章 非连续内存分配,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

前言:该系列文章为笔者学习清华大学《操作系统原理》相关课程笔记,参考书籍《操作系统概念》《现代操作系统等》。如果涉及相关书籍或课程版权,联系即删~

《操作系统原理》学习笔记:第4章 非连续内存分配

      • 4.1 为什么需要非连续内存分配
      • 4.2 分段(Segmentation)
      • 4.3 分页(Paging)
      • 4.4 页表(Page Table,分页机制中的映射表)
        • 4.4.1 概述
        • 4.4.2 快表(Translation Look Buffer,TLB)
        • 4.4.3 二级/多级页表
        • 4.4.4 反向页表(inverted page table)

4.1 为什么需要非连续内存分配

连续内存分配的缺点:
分配给一个程序的物理内存是连续的
内存利用率低
有外碎片、内碎片问题

非连续分配的优点:
一个程序的物理地址空间是非连续的
更好的内存利用和管理
允许共享代码与数据(共享库等……)
支持动态加载和动态链接

非连续分配缺点:
如何建立虚拟地址和物理地址之间的转换

  • 软件方案(开销过大)
  • 硬件方案
    分段
    分页

4.2 分段(Segmentation)

需要考虑的问题:

  • 程序的分段地址空间(内存地址空间如何寻址)

  • 分段寻址方案(寻址机制如何实现)

虚拟的逻辑地址空间是连续的,通过分段之后将堆栈段,运行库,程序数据等有效隔离开。比如可以使用户代码段和主程序段相互之间访问,有些数据之间可以隔离,更加安全。

逻辑地址到物理地址转换需要映射机制,映射之后大小和位置都不同
请添加图片描述

分段寻址方案:

一个段:一个内存“块”

逻辑地址空间是一维的,程序访问内存地址需要一个二维的二元组(s 段号,addr 段内偏移)

  • 段寄存器+地址寄存器实现方案:segment与address分离

  • 单地址实现方案:段内与段内偏移合并形成完整地址
    请添加图片描述

4.3 分页(Paging)

分段中段的尺寸可变,分页中页大小固定

  • 划分物理内存至固定大小的帧:大小是2的幂,e.g 512, 4096, 8192

  • 划分逻辑地址空间至相同大小的页:大小是2的幂,e.g 512

  • 建立映射方案转换逻辑地址为物理地址(pages to frames),使用到如下技术,可加速地址转换:

    • 页表
    • MMU(内存管理单元)/TLB(快表,完成对页面的缓存)

帧(Frame)

  • 物理页:物理内存的组织/布局方式

  • 一个内存物理地址是一个二元组(f,o
    f :帧号(F组,共有2^F组)
    o :帧内偏移(S位,每帧有2^S字节)
    物理地址 = 2^S * f + o

页(Page)

  • 逻辑页:逻辑地址空间被划分为大小相等的页

  • 页内偏移的大小=帧内偏移的大小;页号大小 <> 帧号大小

  • 一个逻辑物理地址是一个二元组(p,o
    p :页号(P组,共有2^P组)
    o :页内偏移(S位,每页有2^S字节)
    虚拟地址 = 2^S * p + o
    请添加图片描述

  • 一般逻辑地址空间 > 物理地址空间,不是所有的页都有对应的帧(3.4.3页表中详述原因)

  • 页是连续的虚拟内存,映射到帧后是非连续的物理内存,优点:减少碎片

4.4 页表(Page Table,分页机制中的映射表)

4.4.1 概述

页表:有效实现从逻辑地址到物理地址的转换
PTBR:页表基址寄存器,存储页表的起始位置

操作系统和硬件相互配合实现:更加高效,节省空间的实现
每个运行的程序都有一个页表,属于程序运行状态,会动态变化

页表项的内容

  • Flags(页表项标志位)
    • dirty bit (修改位):判断页是否被修改过
    • resident bit(存在位):判断页是否有物理页与其对应,有为1
    • clock/reference bit(引用位):页是否有过对它的引用
    • 还有其它标志,比如是否读写标志
  • 帧号 f

e.g 地址转换的实例:

具有16位地址(64kB)的系统
32KB的物理内存(逻辑地址空间通常大于物理地址空间)
每页1024byte(物理页与逻辑页大小相等)

逻辑地址
(4,0)逻辑页号为4,页内偏移为0
(3,1023)

对应物理地址
查询页表,标志位页号4对应的物理页帧不存在,3存在,对应的物理页帧为4,则(3,1024)对应的物理地址(4,1023)
分页机制的性能问题

性能问题?

  • 空间的代价问题

    逻辑地址空间很大,导致页表可能非常大,n个程序有n个页表

  • 时间开销问题

    页表非常大,无法放在CPU中,如果放在内存中,访问一个内存单元需要2次内存访问,一个用于获取页表项,一次用于访问数据

如何处理?

  • 缓存(cacheing):把常用数据缓存在离CPU近的地方

  • 间接(Indirection)访问:将大拆分为小,比如索引,多级页表机制

4.4.2 快表(Translation Look Buffer,TLB)

缓存近期访问的页表项于CPU中

  • 由两项(key:p, value:f)组成,使用associative memory(关联内存)实现,具备快速访问特性

  • 访问时,先访问TLB,如果命中,物理页号很快被获取
    如果TLB未命中,查询内存中的页表,对应的页表项被更新到TLB中

  • 注意:
    编程时,将访问集中在一个区域,尽量避免TLB缺失,避免访问内存中页表
    TLB中页号缺失,反写页号到TLB中,在x86,该过程由硬件完成,对于另一类CPU,该过程可能由操作系统实现

4.4.3 二级/多级页表

多级页表:使页表所占空间尽量小,对大page table的寻址转为多个小page table的寻址

  • 二级页表
    p1存二级页表的起始地址,p2中存frame numer
    有些不存在的页表项不会占用内存,比如p1中查找映射关系就不存在,p2中就不需要保存

  • 多级页表
    通过把页号分位为k个部分,来实现多级间接页表
    建立页表“树”
    每次访问的开销越来越大,但节省了空间,以时间换空间,时间的开销又可以通过TLB缓解

4.4.4 反向页表(inverted page table)

根据物理帧号去查逻辑页号

页表大小与逻辑地址大小相关,逻辑地址越大,页表越大。如何使页表与逻辑地址无直接关系,将页表大小与物理地址相关?反向页表

1⃣️ 页寄存器方案

使用页寄存器(Page Registers)每个帧和一个寄存器关联,寄存器内容包括:

  • Residence bit:此帧是否被占用
  • Occupier:对应的页号p
  • Protection bits:保护位

e.g 页寄存器

物理内存大小:4096*4096=4K*4KB=16MB

页面大小:4906bytes=4KB

页寄存器使用的空间(假设8bytes/resgister):8*4096=32Kbytes

页寄存器带来的额外开销:32K/16M=0.2%(大约)

虚拟内存的大小:任意

页寄存器方案的权衡


  • 转换表的大小相对于物理内存来说很小
    转换表的大小跟逻辑地址空间的大小无关


  • 需要的信息回调了,根据帧号可以找到页号,如何转换回来?即根据页号找到帧号
    需要在反向页表中搜索想要的页号

2⃣️ 基于关联存储器(associative memory)的方案
请添加图片描述

  • 优点:可以并行查找页号所对应的页帧号(key 页号,value 帧号)

  • 缺点:开销太大,设计成本过高,硬件设计复杂,导致容量无法变大,需要放在CPU

在反向页表中搜索一个页对应的帧号

  • 如果帧数较少,页寄存器可以被设置在关联内存中

  • 在关联内存中查找逻辑页
    成功:帧号被提取
    失败:页错误异常(page fault)

  • 限制因素:
    大量的关联内存非常昂贵
    难以在单个时钟周期内完成
    耗电

3⃣️ 基于哈希(hash)查找的方案

优点:可以有效缓解完成映射的开销

缺点:查找时可能发生哈希碰撞,通过程序PID缓解这种情况

根据page number查找frame number使用hash table实现,在反向页表中通过哈希算法来搜索一个页对应的帧号

  • 对页做哈希计算,为了在“帧表”(每帧拥有一个表项)中获取对应的帧号
  • p被放置在表中 f(p)= h(PID, p) 的位置,其中f是设定的哈希函数使用
  • 为了查找页i,执行以下操作:
    • 计算哈希函数f(i),并且使用它作为页寄存器表的索引
    • 获取对应的页寄存器
    • 检查寄存器标签是否包含i,如果包含,则代表成功,否则失败


这篇关于《操作系统原理》学习笔记:第4章 非连续内存分配的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程