第3章：连续内存分配

操作系统

3.1 地址空间与地址生成

（一）地址空间

• 物理地址空间--硬件支持的地址空间
• 逻辑地址空间--一个运行的程序所拥有的内存范围

（二）逻辑地址生成

.c file -> 编译 -> .s file -> 汇编 -> .o file -> 链接 -> .exe file -> 载入（程序重定位） -> 程序在内存中

（三）物理地址生成

• CPU方面
  
  • 运算器需要在逻辑地址内存内容
  • 内存管理单元寻找在逻辑地址和物理地址之间的映射
  • 控制器从总线发送在物理地址的内存内容的请求
• 内存方面
  
  • 内存发送物理地址内存的内容给CPU
• OS方面
  
  • 建立逻辑地址和物理地址之间的映射

3.2 连续内存分配：内存碎片与分区的动态分配

（一）内存碎片问题

• 空闲内存不能被利用
• 外部碎片：在分配单元间的未使用内存
• 内部碎片：在分配单元中的未使用内存

（二）分区的动态分配

• 简单的内存管理方法

  • 当一个程序准许运行在内存中时，分配一个连续的区间
  • 分配一个连续的区间给运行的程序以访问数据

• 分配策略

  • 首次适配
  • 最优适配
  • 最差适配

第一匹配适配

• defs

  • 为了分配 n 字节，使用第一个可用空闲块以致块的尺寸比 n 大

• 基本原理&实现

  • 简单实现
  • 需求：
    
    • 按地址排序的空闲块列表
    • 分配需要寻找一个合适的分区
    • 重分配需要检查，看是否自由分区能合并于相邻的空闲分区（若有）

• 优势

  • 简单
  • 易于产生更大空闲块，向着地址空间的结尾

• 劣势

  • 外部碎片
  • 不确定性

最优匹配

• defs

  • 为了分配 n 字节，使用最小的可用空闲块，以致块的尺寸比 n 大

• 基本原理&实现

  • 为了避免分割大的空闲块
  • 为了最小化外部碎片产生的尺寸
  • 需求：
    
    • 按尺寸排序的空闲块列表
    • 分配需要寻找一个合适的分区
    • 重分配需要搜索及合并于相邻的空闲分区（若有）

• 优势

  • 当大部分分配是小尺寸时非常有效
  • 比较简单

• 劣势

  • 外部碎片
  • 重分配慢
  • 易产生很多没用的微小碎片（不怎么好）

最差匹配

• defs

  • 为了分配 n 字节，使用最大可用空闲块，以致块的尺寸比 n 大

• 基本原理&实现

  • 为了避免太多微小的碎片
  • 需求：
    
    • 按尺寸排序的空闲块列表
    • 分配很快（获得最大的分区）
    • 重分配需要合并于相邻的空闲分区（若有），然后调整空闲块列表

• 优势

  • 假如分配是中等尺寸效果最好

• 劣势

  • 重分配慢
  • 外部碎片
  • 易于破碎大的空闲块以致大分区无法被分配

3.3 连续内存分配：压缩式与交换式碎片整理

（一）压缩式碎片整理

• 重置程序以合并孔洞
• 要求所有程序是动态可重置的

（二）交换式碎片整理

• 运行程序需要更多的内存
• 抢占等待的程序&回收它们的内存