3.1 内存管理基本概念

内存管理的主要功能包括：内存空间的分配与回收、地址转换（逻辑地址→物理地址）、内存扩充（虚拟存储）、存储保护。

3.2 连续分配方式

动态分区分配算法

• 首次适应 (First Fit)：从低地址开始找第一个能满足的空闲分区。简单高效，最常用。
• 最佳适应 (Best Fit)：找能满足的最小空闲分区。产生大量小碎片。
• 最坏适应 (Worst Fit)：找能满足的最大空闲分区。大进程可能无法分配。
• 邻近适应 (Next Fit)：从上次查找位置继续找首次满足的。分配均匀。

3.3 分页存储管理

将内存分为大小相等的物理块/页框 (Frame)，将进程的逻辑地址空间分为与页框等大的页 (Page)。进程的各页可离散地装入不相邻的页框中。

地址转换（分页）

页大小为 2^k，逻辑地址 = 页号 P + 页内偏移 W。物理地址 = 物理块号 F × 页大小 + 偏移 W。

• 页号 P = 逻辑地址 / 页大小；页内偏移 W = 逻辑地址 % 页大小。
• 查页表得物理块号 F。
• 物理地址 = F × 页大小 + W。

两级页表与多级页表

单级页表占用连续内存过大，引入两级页表：页目录表 → 页表 → 物理块。32 位系统中，逻辑地址分为页目录号 (10 位) + 页表号 (10 位) + 页内偏移 (12 位)。避免了页表连续存放的要求。

3.4 页面置换算法

虚拟页式管理中，当访问的页不在内存时产生缺页中断，若内存已满需用页面置换算法选择一页换出。评价指标为缺页率。

• OPT 最佳置换：选择未来最长时间不被访问的页换出。理论最优，缺页率最低，但无法实现（需预知未来），用于性能评价。
• FIFO 先进先出：选择最先进入内存的页换出。实现简单，但存在 Belady 异常（增加物理块反而缺页增多）。
• LRU 最近最久未使用：选择最长时间未被访问的页换出。性能接近 OPT，但实现开销大（需记录访问时间或用栈）。
• CLOCK 时钟置换（二次机会）：将页面组织成环形链表，配访问位。替换时扫描，访问位为 0 则换出，为 1 则清 0 跳过。是 LRU 的近似，开销小。

改进型 CLOCK 算法

基本 CLOCK 仅使用访问位 A（referenced bit）来决定是否淘汰。改进型 CLOCK 在此基础上增加修改位 M（modified bit / dirty bit），综合考虑替换代价：被修改过的页（脏页）换出时需要写回磁盘，开销更大。

改进型 CLOCK 将页面分为四个状态类（A, M 二元组）：

两轮扫描机制：改进型 CLOCK 的扫描指针循环遍历页面，执行两轮扫描：

• 第一轮：寻找 (0, 0) 页——即最近未访问也未修改的页。若找到则直接淘汰，不修改任何访问位。此轮不改变 A 位。
• 第二轮：若第一轮未找到，则寻找 (0, 1) 页（此时所有的 A 均已变为 0）。在扫描过程中将遇见的 A=1 的页的 A 置为 0（相当于第一轮漏掉了将 A 清 0 的操作，第二轮补做）。若找到则淘汰。
• 若第二轮仍未找到，则所有页的 (A, M) 都已变为 (0, 0)，重复第一轮即可找到淘汰页。

// 改进型 CLOCK（增加修改位 M）
int refBit[F], modBit[F];      // 访问位、修改位
int ptr = 0;                      // 扫描指针

void EnhancedCLOCK_Replace(int page){
  // 第一轮：找 (0,0)
  for(int round=0; round<4; round++){
    for(int i=0; iint idx = (ptr + i) % F;
      if(round==0 && refBit[idx]==0 && modBit[idx]==0){
        ptr = (idx+1)%F; goto replace;
      }
      if(round==1 && refBit[idx]==0 && modBit[idx]==1){
        ptr = (idx+1)%F; goto replace;
      }
      if(round==2) refBit[idx] = 0;  // 清访问位
    }
  }
  replace: frames[ptr] = page; refBit[ptr] = 1; modBit[ptr] = 0;
}

5. LFU 最不经常使用置换

选择访问次数最少的页面换出。若有多页频率相同，可结合 LRU 选其中最久未访问的。LFU 对高频访问的页保护更好，对扫描型工作负载效果好。

页面置换算法伪代码

// FIFO 先进先出
int frames[F];              // 物理块
int queue[F];              // FIFO 队列
int qh = 0;                  // 队头指针

void FIFO_Access(int page){
  if(page 在 frames 中) return;   // 命中
  if(frames 未满)
    frames[nextEmpty++] = page;
  else {                              // 缺页
    int victim = queue[qh];
    queue[qh] = page;
    qh = (qh+1) % F;
    replace(victim, page);
  }
}

// LRU 最近最久未使用
int lastAccess[F];          // 上次访问时间戳
int clock = 0;

void LRU_Access(int page){
  clock++;
  if(page 在 frames 中){
    lastAccess[idx[page]] = clock;      // 更新最近访问时间
    return;
  }
  if(frames 未满){
    frames[nextEmpty] = page;
    lastAccess[nextEmpty] = clock;
  } else {
    // 找 lastAccess 最小的页
    int victim = argmin(lastAccess);
    frames[victim] = page;
    lastAccess[victim] = clock;
  }
}

// CLOCK 时钟置换（二次机会）
int refBit[F];               // 访问位
int ptr = 0;

void CLOCK_Access(int page){
  if(page 在 frames 中){ refBit[idx[page]] = 1; return; }
  while(true){
    if(refBit[ptr]==0){
      frames[ptr] = page;            // 牺牲页
      refBit[ptr] = 1;              // 新页面访问位置 1
      ptr = (ptr+1) % F;           // 指针前进
      break;
    } else {
      refBit[ptr] = 0;            // 给二次机会
      ptr = (ptr+1) % F;
    }
  }
}

// LFU 最不经常使用
int freq[F];              // 访问次数
int last[F];              // 上次访问时间
int clock = 0;

void LFU_Access(int page){
  clock++;
  if(page 在 frames 中){
    freq[idx[page]]++;              // 命中：频率+1
    last[idx[page]] = clock;
    return;
  }
  if(frames 未满){
    frames[nextEmpty] = page;
    freq[nextEmpty] = 1;
    last[nextEmpty] = clock;
  } else {
    // 找频率最小；同频率选最久未用
    int victim = 0;
    for(int j=1; jif(freq[j] < freq[victim] ||
         (freq[j]==freq[victim] && last[j] < last[victim]))
        victim = j;
    }
    frames[victim] = page;
    freq[victim] = 1;
    last[victim] = clock;
  }
}

3.5 虚拟页式管理

虚拟页式管理的工作流程：

• 进程启动时只装入部分页，其余在外存。
• 访问页时查页表，有效位=1 则直接访问（地址转换）。
• 有效位=0 产生缺页中断，OS 从外存调入该页。
• 若内存已满，调用置换算法选一页换出；若换出页被修改过（脏页），还需写回外存。
• 更新页表，恢复执行被中断的指令。

局部性原理

• 时间局部性：近期访问的指令/数据很可能再次被访问（如循环）。
• 空间局部性：访问某地址后，其相邻地址很可能被访问（如顺序执行、数组）。

页面分配与置换策略

工作集模型 (Working Set Model)

• 工作集大小 WSS (Working Set Size)：|W(t, Δ)|，即集合中的页面数量。WSS 随时间动态变化。
• Δ 的选择：Δ 太小 → 工作集不能完整覆盖局部性（缺页多）；Δ 太大 → 包含了不属于当前局部性的页（内存浪费）。Δ 的合理选择对系统性能至关重要。

缺页率与工作集的关系

根据工作集模型，系统为每个进程分配的物理块数应 ≥ 该进程当前的工作集大小 WSS：

• 分配给进程的块数 < WSS → 缺页频繁 → 可能引发抖动。
• 分配给进程的块数 ≥ WSS → 缺页率大幅下降，进程正常运行。
• 所有活跃进程的 WSS 之和 ≤ 内存总块数 → 系统整体健康；否则需挂起部分进程。

页框分配策略

多道程序环境下，如何将有限的内存页框分配给多个进程？常用的分配策略如下：

• 均等分配 (Equal Allocation)：将 m 个页框平均分配给 n 个进程，每个进程获 m/n 个页框。简单但不考虑进程差异（大进程可能不足，小进程浪费）。
• 比例分配 (Proportional Allocation)：按各进程的大小（虚拟地址空间大小）比例分配页框。进程 i 获得 (sᵢ / Σsⱼ) × m 个页框，其中 sᵢ 为进程 i 的大小。
• 优先级分配 (Priority Allocation)：按进程优先级分配页框。高优先级进程获得更多页框，以减少其缺页率、提升响应速度。

页面分配与置换策略详细对比

交互式动画 · 缺页中断处理流程

当访问的页面不在内存时，触发缺页中断，OS将页面从外存调入内存。步进观察完整流程。

3.6 进程内存布局与装入链接

程序从源代码到在内存中执行，需经历编译→汇编→链接→装入四个阶段。理解进程在内存中的布局是内存管理的基础。

进程内存布局

从低地址到高地址，进程的虚拟地址空间依次为：

装入与链接方式

3.7 分段存储管理

分页管理对用户不可见，分段按程序的逻辑结构（如主程序、子程序、数据区）划分段，每段从 0 开始编址，方便编程、共享和保护。

• 段表：实现段号到段基址、段长的映射，存于内存中，段表基址寄存器 (STBR) 存放段表起始地址。
• 地址转换：段号 s → 查段表得 (b, l) → 检查 w < l → 物理地址 = b + w。一次访存需访问 2 次内存（查段表 + 取数据）。
• 越界检查：若偏移 w ≥ 段长 l，产生越界中断，实现存储保护。

3.8 段页式存储管理

段页式结合分段（方便共享保护）与分页（无外部碎片）的优点：先将程序分段，每段内再分页。

• 第 1 次访存：查段表，由段号 s 得到该段的页表起始地址和页表长度。
• 第 2 次访存：查页表，由段内页号 p 得到物理块号 f。
• 第 3 次访存：物理地址 = f × 页大小 + w，访问目标数据。

3.9 TLB 快表与有效访问时间

快表 TLB (Translation Lookaside Buffer) 是 CPU 内部的高速相联存储器，缓存近期访问的页表项（页号→物理块号映射），用于加速分页/段页式的地址转换。

• 工作流程：CPU 给出逻辑地址 → 先查 TLB；命中则直接得物理块号，只需 1 次访存；未命中则查内存页表（1 次访存），并将表项装入 TLB，再取数据（共 2 次访存）。
• 局部性原理：TLB 容量小（通常 64~1024 项）但命中率高（可达 90%+），源于时间/空间局部性。

有效访问时间 EAT

设 TLB 命中率为 h，TLB 查找时间为 ε（约 1ns，常忽略），内存访问时间为 ma（约 50~200ns）：

含义：命中时一次访存（查 TLB + 取数据），未命中时两次访存（查页表 + 取数据）。

3.10 内存映射文件 (mmap)

mmap 基本原理

mmap 在进程的虚拟地址空间中创建一段映射区域（通常在堆与栈之间），将磁盘文件的某些块映射到该区域：

• 首次访问映射区域时，产生缺页中断，操作系统从磁盘读入对应文件块到物理内存页框，建立页表映射。
• 后续访问时走正常的地址转换流程（TLB/页表），直接读写内存即操作文件。
• 修改过的页被标记为脏页，由 OS 负责在适当时机（munmap、msync、或页换出时）写回磁盘。

mmap 与 read/write 的区别

内存映射文件的优点

• 零拷贝 (Zero-Copy)：数据直接从页缓存映射到用户空间，避免了从内核缓冲区到用户缓冲区的额外拷贝。大幅降低 CPU 开销。
• 共享内存基础：多个进程可 mmap 同一文件，实现进程间共享内存——一个进程的写入对另一个进程立即可见（无需 IPC 系统调用）。这是 POSIX 共享内存的实现基础。
• 惰性加载 (Lazy Loading)：大文件不必一次性全部读入内存，按需加载，节省物理内存。
• 简化编程：文件操作抽象为内存操作，编程更简单（如用 memcpy 代替 read/write 循环）。