04-非连续内存分配

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

连续内存分配的缺点

1）分配给一个程序的物理内存是连续的
2）内存利用率较低
3）有外碎片、内碎片的问题

非连续内存分配的优点

一个程序的物理地址空间是非连续的
更好的内存利用和管理
允许共享代码与数据（共享库）
支持动态加载和动态链接

非连续内存分配的缺点

如何建立虚拟地址和物理地址之间的转换
软件方案
硬件方案

两种硬件方案
分段
分页

分段

更好的分离和共享

程序的分段地址空间

可以认为逻辑地址空间是连续的，但是对应的物理地址空间是分散的，例如堆有堆内存空间，运行栈有栈内存空间，程序数据 程序text段

分段寻址方案

段访问机制
新概念：一个段：一个内存块 一个逻辑地址空间
程序访问内存地址需要：
一个二维的二元组
s 段号
addr 段内偏移

两种获取内存地址的实现方式
1）段寄存器+地址寄存器实现方案 x86架构
2）单地址实现方案

分段方式和分页方式的区别 分段方式段的大小是可变的，分页方式 页的大小是固定的

分页（常用的方式）

分页地址空间

划分物理内存至固定大小的帧，大小是2的幂，例如512，4096，8192
划分逻辑地址空间至相同大小的页，大小是2的幂，例如512，4096，8192
建立方案 转换逻辑地址为物理地址（pages to frames）

• 页表
• MMU/TLB

帧（Frame）：物理内存被分割为大小相等的帧

一个内存物理地址是一个二元组（f,o）
f-帧号（F位，共有$2^F$个帧）
o-帧内偏移（S位，每帧有$2^S$字节）
$物理地址=2^S*f+o$

页（Page）：一个程序的逻辑地址空间被划分成大小相等的页
页内偏移的大小=帧内偏移的大小
页号大小和帧号大小可能不一样
p-页号（P位，共有$2^P$个帧）
o-页内偏移（S位，每帧有$2^S$字节）
$虚拟地址(逻辑地址)=2^S*p+o$

页寻址方案

页表保存了逻辑地址--物理地址之间的映射关系，页表是在操作系统初始化的时候由操作系统建立的
根据页号去页表里面查对应的帧号，再加上页内偏移，就得到了物理地址的值

页寻址机制
页映射到帧
页是连续的虚拟内存
帧是非连续的物理内存
不是所有的页都有对应的帧

优势：有助于减少碎片

页表

页表概述

页表结构
每个运行的程序都有一个页表
属于程序的运行状态，会动态变化
PTBR:页表基址寄存器
页表项的内容：
dirty bit
resident bit 0不存在/1存在
clock/reference bit
帧号：f

分页机制的性能问题

• 访问一个内存单元需要2次内存访问
  一次用于获取页表项
  一次用于访问数据
• 页表可能非常大
  64位机器如果每页1024字节，那么一个页表的大小会是多少？
  每个程序都有自己的页表，重复占用空间
  页表很大，没办法放在CPU中，页表放在内存中，就需要访问2次内存
• 如何处理？
  缓存（Cashing）
  间接（Indiretion）访问

转换后背缓冲区（TLB）

TLB:Translation Look-aside Buffer
TLB缓冲区位于CPU内部
缓存近期访问的页帧转换表项

• TLB使用 association memory（关联内存）实现，具备快速访问性能
• 如果TLB命中，物理页号可以很快被获取
• 如果TLB未命中，对应的表项被更新到TLB中
  TLB未命中的情况，如果是x86系统，是通过硬件完成读取页表项更新如缓存中的过程的，如果是MIPS系统，是通过操作系统软件完成的

二级/多级页表

通过把页号分为k个部分，来实现多级间接页表

• 建立页表树
  多级页表，级数越多，时间开销越大，空间开销越小，以时间换空间的方式
  时间可以通过TLB的方式优化

反向页表

为什么需要反向页表

1. 有大地址空间（64-bit）, 前向映射页表变得繁琐
   比如：5级页表
2. 不是让页表与逻辑地址空间的大小相对应，而是让页表与物理地址空间的大小相对应
   逻辑（虚拟）地址空间增长速度快于物理地址空间

使用页寄存器（Page Registers）

• 每个帧和一个寄存器关联，寄存器内容包括
  Residence bit: 此帧是否被占用
  Occupier: 对应的页号p
  Protection bits: 保护位

页寄存器：一个例子

• 物理内存的大小：40964096 = 4K4KB =16MB
• 页面大小：4096 bytes = 4KB
• 页帧数：4096 = 4K
• 页寄存器使用的空间（假设8bytes/register）
  • 8*4096=32K bytes
• 页寄存器带来的额外开销
  • 32K/16M = 0.2%(大约)
• 虚拟内存的大小：任意

页寄存器方案的权衡
利：
转换表的大小相对于物理内存来说很小
转换表的大小跟逻辑地址空间的大小无关
弊：
需要的信息对调了，即根据帧号可找到页号
如何转换回来？即根据页号找到帧号
在需要在反向页表中搜索想要的页号

使用关联内存（associative memory）

在反向页表中搜索一个页对应的帧号
如果帧数较少，页寄存器可以被放置在关联内存中
在关联内存中查找逻辑页号
成功: 帧号被提取
失败: 页错误异常（page fault）
限制因素：
大量的关联内存非常昂贵
难以在单个时钟周期内完成
耗电

使用哈希查找的方案

在反向页表中通过哈希算法来搜索一个页对应的帧号
对页号做哈希计算，为了在"帧表"（每帧拥有一个表项）中获取对应的帧号
页i被放置在表中f(i)位置，其中f是设定的哈希函数
为了查找页i, 执行下列操作

• 计算哈希函数f(i) 并且使用它作为页寄存器表的索引
• 获取对应的页寄存器
• 检查寄存器标签是否包含i, 如果包含，则代表成功，否则失败