03 内存分配 | 《操作系统》笔记

这一系列是操作系统 (清华大学向勇、陈渝)视频课的课堂笔记，主要是课堂 PPT 和部分讲授内容的文字版，仅供参考。

概述

• 操作系统在内存管理方面的任务
  • 抽象：逻辑地址空间
  • 保护：独立地址空间
  • 共享：访问相同内存
  • 虚拟化：更多的地址空间
• 在操作系统中管理内存的不同方法
  • 程序重定位
  • 分段
  • 分页
  • 虚拟内存
  • 按需分页虚拟内存

连续内存分配：地址空间与地址生成

• 地址空间定义
  • 物理地址空间：硬件支持的地址空间
    • 起始地址 0 到到地址 MAXsystem
  • 逻辑地址空间：一个运行的程序所拥有的内存范围
    • 起始地址 0 到到地址 MAXprocess
  • 
  • 当 CPU 需要执行某个指令时
    • CPU
      • 运算器需要在逻辑地址的内存内容
      • 内存管理单元寻找在逻辑地址和物理地址之同的映射
      • 控制器从总线发送在物理地址的内存内容的请求
    • 内存
      • 内存发送物理地址内存的内容给 CPU
    • 操作系统方面
      • 建立逻辑地址和物理地址之间的映射
• 连续内存分配
  • 内存碎片问题
    • 空闲内存不能被利用
    • 外部碎片：在分配单元间的未使用内存
    • 内部碎片：在分配单元中的未使用内存
  • 分区的动态分配
    • 第一适配
      • 
      • 实现
        • 按地址排序空闲块
        • 寻找第一个可行的分区
        • 回收时尝试合并相邻的空闲分区(若有）
      • 优势
        • 简单
        • 易于产生更大空闲块
      • 劣势
        • 外部碎片
        • 不确定性
    • 最佳适配
      • 
      • 实现
        • 按尺寸排序空闲块
        • 寻找最合适的分区
        • 回收时尝试合并相邻的空闲分区(若有）
      • 优势
        • 当大部分分配是小尺寸时非常有效
        • 比较简单
      • 劣势
        • 外部碎片
        • 重分配慢
        • 易产生很多没用的微小碎片(不怎么好)
    • 最差适配
      • 
      • 实现
        • 按尺寸排序空闲块
        • 寻找最大的分区
        • 回收时尝试合并相邻的空闲分区(若有）
      • 优势
        • 假如分配是中等尺寸效果最好
      • 劣势
        • 重分配慢
        • 外部碎片
        • 易于破碎大的空闲块以致大分区无法被分配
  • 压缩式碎片整理
    • 
    • 劣势
      • 拷贝开销可能很大
      • 无法应对空间的绝对剩余量不够的情况
  • 交换式碎片整理
    • 运行程序需要更多的内存
    • 抢占等待的程序并回收它们的内存
    • 

非连续内存分配

• 概述
  • 连续内存分配的缺点
    • 分配给一个程序的物理内存是连续的
    • 内存利用率较低
    • 有外碎片、内碎片的问题
  • 非连续分配的优点
    • 一个程序的物理地址空间是非连续的
    • 更好的内存利用和管理
    • 允许共享代码与数据(共享库等)
    • 支持动态加载和动态链接
  • 如何建立虛拟地址和物理地址之间的转换
    • 软件方案
    • 硬件方案
  • 两种硬件方案
    • 分段
    • 分页
• 分段
  • 分段地址空间
    • 
  • 分段寻址方案
    • 
    • 
• 分页
  • 分页地址空间
    • 与分段的的最大区别
      • 段的尺寸可变，页的大小固定
    • 概念区分
      • frame：帧（物理页）
      • page：页（逻辑页）
    • 划分物理内存至固定大小的帧
      • 大小是 2 的幂，如 512、4096、8192
    • 划分逻辑地址空间至相同大小的页
      • 大小是 2 的幂，如 512、4096、8192
    • 建立方案转换逻辑地址为物理地址(pages to frames)
      • 页表
      • MMU/TLB
  • 分页寻址方案
    • 
    • 
    • 
    • 

页表

• 概述
  • 
  • 
  • 分页机制的性能问题
    • 访问一个内存单元需要 2 次内存访问
      • 一次用于获取页表项
      • 一次用于访问数据
    • 页表可能非常大
      • 64 位机器如果每页 1024 字节，那么一个页表的大小会是多少？
        • 每页共有 1024 个地址，则机器共有 2^64/1024=2^54 页
        • 每页在页表中占一个字节，那么一个页表的大小为 2^54 字节
    • 如何处理
      • 时间：缓存
      • 空间：多层次页表
• TLB
  • 页表的 cache，位于 MMU 中
  • 
• 二级、多级页表
  • 
  • 对应驻留位为 0 的那个二级页表就可以省去了
  • 
• 反向页表
  • 大地址空间问题
    • 有大地址空间(64-bits)，前向映射页表变得繁琐，如:5 级页表
    • 不是让页表与逻辑地址空间的大小相对应，而是让页表与物理地址空间的大小相对
    • 逻辑（虚拟）地址空间增长速度快于物理地址空间
  • 基于页寄存器(Page Registers)的方案
    • 页表是页号（逻辑）到帧号（物理）的映射，反向页表是帧号（物理）到页号（逻辑）的映射
    • 
    • 
    • 虽然这种方案减少了存储每个页表所需要的内存空间，但是当引用页时，它增加了查找页表所需要的时间。由于反向页表按物理地址排序，而查找是根据虚拟地址，因此可能需要查找整个表来寻求匹配。这种查找会花费很长时间。
    • 为了解决这一问题，可以使用哈希页表来将查询限制在一个或少数几个页表条目。当然，每次访问哈希页表也为整个过程增加了一次内存引用，因此一次虚拟地址引用至少需要两个内存读：一个查找哈希页表条目，另一个查找页表。为了改善性能，可以在访问哈希页表时先查找 TLB。