地址空间与抽象 Address Space and Abstract

  • os视角: 地址空间是在 process
    内部的用于不同进程之间对物理内存高效, 安全访问的一种抽象方式;
    • Process = one or more threads running in an address space;
  • 组成: 包括 code, data, heap, stack
  • Phisical Machine Interface: 多个任务共享同一个物理内存, 比如一个 config 文件
  • Virtual Machine Interface: 每个任务有独立的虚拟内存空间

地址空间抽象的三条准则

  • Address Space Independence:
  • Protection (controlled isolation):
  • Large Address Space:

单进程执行缺陷

多个进程执行

动态地址翻译 Dynamic Address Translation

Method 1: Base + Bound

  • 机制
  • 优点
  • 缺点

Method 2: Segmentation

Method 3: Paging

页地址转换方式

页替换基础(Page Replacement Basics)

  • 触发条件: 当发生页错误(Page Fault)且物理页框(Page Frame)已满时, 需选择牺牲页(Victim Page)替换;
  • 目标: 最小化页错误率(Page Fault Rate), 提升虚拟内存(Virtual Memory)性能;
  • 关键概念:
    • 局部性原理(Locality):
      • 时间局部性(Temporal Locality): 近期访问的页可能再次被访问;
      • 空间局部性(Spatial Locality): 邻近地址的页可能被连续访问;

页替换算法(Page Replacement Algorithms)

1. 先进先出(First-In First-Out, FIFO)

  • 机制: 淘汰最早进入内存的页;
  • 缺陷:
    • Belady异常(Belady’s Anomaly): (主要是fifo情况会导致)增加num of page in memory 可能增加 page fault;

2. 最优替换(Optimal Replacement, OPT)

  • 机制: 淘汰 未来 最长时间不被访问的页(需预知未来访问序列);
  • 困难: 很难预知未来访问模式, 仅作为理论基准;
  • 意义: 作为理论 opt 基准(Yardstick)评估其他算法;

3. 最近最少使用(Least Recently Used, LRU)

  • 机制: 淘汰最久未被访问的页, 基于最优 temporal locality, 对比 opt
    更加展现过去的访问模式;
  • 最不利于 lru 算法的访问顺序: 正序访问一个大于物理内存大小的page array,
    使得每次访问都需要替换一个页;
  • Implement Problem:
    1. 记录每次调用的时候的 cpu 时间, evict 的时候找到时间最老的 page: 占用内存更大, 且 Scanning 所有优先级的时间开销很大;
    2. 使用一个 doubly-linked list, 每次访问将当前 node 放到尾部: 内存开销很大

4. 时钟队列算法(Clock Queue Algorithm)

  • MMU 存储每个 page 的访问位(Accessed/Referenced Bit);
  • evict 未被访问的页(ref=0), 访问过的页 ref = 0 并跳过(防止死循环);
  • 二次机会(Second-Chance): 别称
  • evict 页处理
    • data 写回? 可能有 write-back 和 write-through 策略;
      • write-back: 仅dirty页且非swap数据页需写回, 需要额外记录 dirty-bit

页替换优化(Optimizations)

  • 脏位管理(Dirty Bit Management):
    • 脏位(Dirty Bit): 标记页是否被修改, 或者说内存中的数据和磁盘中的数据是否一致;
    • 写回策略(Write-Back): 仅脏页需写回;
  • 硬件支持:
    • 访问位(Accessed Bit): 由内存管理单元(MMU)自动更新, 用于近似LRU;
    • 页表项(Page Table Entry, PTE): 包含物理页号, 有效位(Valid), 驻留位(Resident), 保护位(Protection), 脏位(Dirty), 访问位(Accessed);

pte 优化策略

  • valid: mmu 可以不用保存 valid bit, 而由 os (Pager) 根据 r/w 权限来判断是否
    valid, 即将 invalid page 标记为 non-resident, 只需要判断是否 resident 就行;
  • resident: mmu 可以不用保存 resident bit, 而由 os (Pager) 根据 r/w 来判断是否 resident,
    即将 non-resident 标记为 r=0, w=0, 只需要判断是否 resident 就行;
  • dirty: mmu 可以不用保存 dirty bit, 而由 os (Pager) 自行记录是否 dirty
    就可以, 即将每次写入的 page 标记为 dirty
  • ref: mmu 可以不用保存 ref bit, 而由 os (Pager) 自行记录是否 accessed
    就可以, 即将每次访问的 page 标记为 accessed

算法对比与选择

算法 优点 缺点
FIFO 实现简单 Belady异常, 忽略访问模式
OPT 理论最优 不可实现(需预知未来)
LRU 近似OPT, 利用时间局部性 实现开销大, 需硬件支持
时钟算法(Clock) 低开销, 近似LRU 可能淘汰频繁访问页(循环扫描)