核心问题：当程序需要的内存比物理内存还多时，操作系统该怎么办？

背景：之前的假设太理想了

前面几章我们一直假设：每个进程的地址空间都能完整放入物理内存。
现实中这是不可能的：

• 多个大程序同时运行
• 单个程序的数据就可能超过物理内存容量
• 早期程序员需要手动管理"内存覆盖"（Memory Overlay），极其痛苦
  操作系统的目标：让程序感觉自己有一个巨大的、连续的内存空间，但背后实际上只有有限的物理内存。

内存层次结构

访问速度快 ^         CPU 寄存器（极小，极快）
           |         CPU 缓存（L1/L2/L3）
           |         物理内存 RAM（大，但有限）
           |         磁盘 / SSD（极大，但慢）
访问速度慢 v

磁盘比内存慢 $10000\sim 100000$ 倍，但容量可以是内存的几十倍。操作系统正是利用这个特点，用磁盘来"假装"内存更大。

21.1 交换空间（Swap Space）

什么是交换空间

在磁盘上划出一块专用区域，专门用来存放"暂时不用"的内存页。操作系统可以把物理内存中的页换出（swap out）到这里，需要时再换入（swap in）。

图解：物理内存与交换空间

物理内存（4帧）          交换空间（8块，在磁盘上）
+----------------+       +------------------+
| PFN 0          |       | Block 0: Proc0/VPN1 |
| Proc0 / VPN 0  |       | Block 1: Proc0/VPN2 |
+----------------+       | Block 2: (空闲)     |
| PFN 1          |       | Block 3: Proc1/VPN0 |
| Proc1 / VPN 2  |       | Block 4: Proc1/VPN1 |
+----------------+       | Block 5: Proc3/VPN0 |
| PFN 2          |       | Block 6: Proc2/VPN1 |
| Proc1 / VPN 3  |       | Block 7: Proc3/VPN1 |
+----------------+       +------------------+
| PFN 3          |
| Proc2 / VPN 0  |
+----------------+

• Proc0：VPN0 在内存，VPN1 和 VPN2 在磁盘
• Proc1：VPN2、VPN3 在内存，VPN0、VPN1 在磁盘
• Proc2：VPN0 在内存，VPN1 在磁盘
• Proc3：全部页都在磁盘，当前没有运行
  系统就这样"假装"拥有远超物理内存的空间。

交换空间的大小

交换空间决定了系统能同时支持多少内存页：
$$\text{系统最大可用内存页数}=\text{物理内存页数}+\text{交换空间页数}$$

21.2 存在位（Present Bit）

页表项（PTE）需要新增一个字段

之前的页表项只记录"这页在物理内存的哪个帧"。现在需要区分两种情况：

present 位	含义
1	该页在物理内存中，PFN 字段有效
0	该页不在内存，在磁盘的某个位置

---

页表项（PTE）结构：
+--------+-------+--------+---------+-------+
| valid  | prot  | present|  dirty  |  PFN  |
| (1bit) |(3bit) | (1bit) |  (1bit) |(多位) |
+--------+-------+--------+---------+-------+
   是否合法  保护位  是否在内存  是否被修改  物理帧号
                    （新增）

当 present = 0 时，PFN 字段不再是物理帧号，而是磁盘上的地址，OS 用它来找到该页在交换空间中的位置。

访问一个 present=0 的页会怎样？

硬件发现该页不在内存 → 触发缺页异常（Page Fault） → 控制权转交给操作系统的缺页处理程序。

21.3 缺页处理（Page Fault）

整体流程

为什么缺页处理由软件（OS）完成，而不是硬件？

1. 磁盘 I/O 极慢：等磁盘的时间里，OS 软件的开销可以忽略不计
2. 硬件不懂磁盘：硬件不知道如何操作磁盘、管理交换空间，交给 OS 更合理

OS 缺页处理步骤（软件控制流）

1. 找一个空闲的物理帧（PFN）
   如果没有空闲帧 → 运行页面置换算法，踢出一页
2. 发起磁盘 I/O：把目标页从交换空间读入该物理帧
   （此时进程进入阻塞状态，OS 可以运行其他进程）
3. I/O 完成后，更新页表：
   PTE.present = 1
   PTE.PFN = 刚才分配的物理帧号
4. 重试触发缺页的那条指令

完整地址翻译控制流（C语言实现）

下面的代码完整模拟了带交换机制的内存访问过程：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* ========== 常量定义 ========== */
#define PAGE_SIZE        4096   /* 每页4KB */
#define PHYS_FRAMES      4      /* 物理内存共4帧（模拟用，很小） */
#define SWAP_BLOCKS      8      /* 交换空间共8块 */
#define NUM_VPAGES       8      /* 每个进程最多8个虚拟页 */
/* ========== 数据结构定义 ========== */
/* 页表项（Page Table Entry）*/
typedef struct {
    int valid;      /* 合法位：0=非法地址（段错误），1=合法 */
    int present;    /* 存在位：1=在物理内存，0=在磁盘 */
    int pfn;        /* 物理帧号（present=1时有效）*/
    int disk_addr;  /* 磁盘块号（present=0时有效，即在交换空间的位置）*/
    int dirty;      /* 脏位：页内容是否被修改过（置换时需要写回磁盘）*/
} PTE;
/* 物理帧描述符 */
typedef struct {
    int in_use;     /* 是否被占用 */
    int proc_id;    /* 被哪个进程使用 */
    int vpn;        /* 存放的是哪个虚拟页 */
} PhysFrame;
/* TLB 项（简化，只有1项用于演示）*/
typedef struct {
    int valid;
    int vpn;
    int pfn;
} TLBEntry;
/* ========== 全局模拟数据 ========== */
PhysFrame phys_mem[PHYS_FRAMES];   /* 物理内存帧 */
int swap_space[SWAP_BLOCKS];        /* 交换空间（存放vpn，-1表示空闲）*/
PTE page_table[NUM_VPAGES];         /* 进程的页表 */
TLBEntry tlb;                       /* 简化的TLB（只有1项）*/
int clock_hand = 0;  /* 时钟置换算法指针（简单轮转）*/
/* ========== 初始化 ========== */
void init() {
    int i;
    /* 初始化物理内存：全部空闲 */
    for (i = 0; i < PHYS_FRAMES; i++) {
        phys_mem[i].in_use  = 0;
        phys_mem[i].proc_id = -1;
        phys_mem[i].vpn     = -1;
    }
    /* 初始化交换空间：全部空闲（用-1表示）*/
    for (i = 0; i < SWAP_BLOCKS; i++) {
        swap_space[i] = -1;
    }
    /* 初始化页表：前4页在内存，后4页在磁盘 */
    for (i = 0; i < NUM_VPAGES; i++) {
        page_table[i].valid    = 1;   /* 全部是合法地址 */
        page_table[i].dirty    = 0;
        if (i < PHYS_FRAMES) {
            /* VPN 0~3：预先加载到物理内存 */
            page_table[i].present  = 1;
            page_table[i].pfn      = i;     /* 帧号与VPN相同（简化）*/
            page_table[i].disk_addr = i;    /* 磁盘上也有备份 */
            phys_mem[i].in_use  = 1;
            phys_mem[i].vpn     = i;
            swap_space[i]       = i;        /* 磁盘块0~3存放VPN 0~3的备份 */
        } else {
            /* VPN 4~7：只在磁盘 */
            page_table[i].present  = 0;
            page_table[i].pfn      = -1;
            page_table[i].disk_addr = i;    /* 磁盘块4~7 */
            swap_space[i]           = i;    /* 存放VPN i */
        }
    }
    /* 初始化TLB：无效 */
    tlb.valid = 0;
}
/* ========== 工具函数 ========== */
/* 找一个空闲的物理帧，返回帧号，没有则返回-1 */
int find_free_frame() {
    int i;
    for (i = 0; i < PHYS_FRAMES; i++) {
        if (!phys_mem[i].in_use) return i;
    }
    return -1;
}
/* 找一个空闲的磁盘块，返回块号，没有则返回-1 */
int find_free_swap_block() {
    int i;
    for (i = 0; i < SWAP_BLOCKS; i++) {
        if (swap_space[i] == -1) return i;
    }
    return -1;
}
/* 简单的时钟置换：选择一个物理帧踢出，返回被踢出的帧号 */
int evict_page() {
    /* 轮转找一个占用的帧 */
    int victim = clock_hand % PHYS_FRAMES;
    clock_hand = (clock_hand + 1) % PHYS_FRAMES;
    int evicted_vpn = phys_mem[victim].vpn;
    printf("  [置换] 将 VPN=%d 从物理帧 %d 换出到磁盘\n",
           evicted_vpn, victim);
    /* 如果页被修改过（脏页），需要写回磁盘 */
    if (page_table[evicted_vpn].dirty) {
        printf("  [置换] 脏页，写回磁盘块 %d\n",
               page_table[evicted_vpn].disk_addr);
    }
    /* 更新被换出页的页表项：标记为不在内存 */
    page_table[evicted_vpn].present = 0;
    page_table[evicted_vpn].pfn     = -1;
    /* 清空该物理帧 */
    phys_mem[victim].in_use = 0;
    phys_mem[victim].vpn    = -1;
    /* 如果TLB中有该项，使其无效（TLB失效）*/
    if (tlb.valid && tlb.vpn == evicted_vpn) {
        tlb.valid = 0;
        printf("  [TLB] 已清除 VPN=%d 的TLB项\n", evicted_vpn);
    }
    return victim;
}
/* 缺页处理（OS软件处理程序）*/
int handle_page_fault(int vpn) {
    printf("  [缺页处理] VPN=%d 不在内存，开始处理...\n", vpn);
    /* 第一步：找空闲物理帧 */
    int pfn = find_free_frame();
    if (pfn == -1) {
        printf("  [缺页处理] 没有空闲帧，需要置换\n");
        pfn = evict_page();  /* 运行置换算法 */
    }
    /* 第二步：模拟从磁盘读入（实际中这里会有I/O等待）*/
    int disk_addr = page_table[vpn].disk_addr;
    printf("  [磁盘I/O] 从磁盘块 %d 读入 VPN=%d 到物理帧 %d（模拟I/O，耗时...）\n",
           disk_addr, vpn, pfn);
    /* 第三步：更新物理帧信息 */
    phys_mem[pfn].in_use = 1;
    phys_mem[pfn].vpn    = vpn;
    /* 第四步：更新页表项 */
    page_table[vpn].present = 1;
    page_table[vpn].pfn     = pfn;
    page_table[vpn].dirty   = 0;  /* 刚从磁盘读入，尚未修改 */
    printf("  [缺页处理] 完成：VPN=%d 现在在物理帧 %d\n", vpn, pfn);
    return pfn;
}
/* ========== 地址翻译核心（模拟硬件+OS）========== */
int translate(int vpn, int offset, int write_access) {
    printf("\n--- 访问 VPN=%d, offset=%d, %s ---\n",
           vpn, offset, write_access ? "写" : "读");
    /* 合法性检查 */
    if (vpn < 0 || vpn >= NUM_VPAGES) {
        printf("  [错误] VPN=%d 超出范围，段错误！\n", vpn);
        return -1;
    }
    if (!page_table[vpn].valid) {
        printf("  [错误] VPN=%d 页表项无效，段错误！\n", vpn);
        return -1;
    }
    /* 第一步：查TLB */
    if (tlb.valid && tlb.vpn == vpn) {
        printf("  [TLB命中] VPN=%d → PFN=%d\n", vpn, tlb.pfn);
        if (write_access) page_table[vpn].dirty = 1;
        return tlb.pfn * PAGE_SIZE + offset;
    }
    printf("  [TLB未命中] 查页表...\n");
    /* 第二步：查页表 */
    PTE *pte = &page_table[vpn];
    if (!pte->present) {
        /* 缺页！交给OS处理 */
        int pfn = handle_page_fault(vpn);
        if (pfn == -1) {
            printf("  [错误] 缺页处理失败\n");
            return -1;
        }
        /* 更新TLB */
        tlb.valid = 1;
        tlb.vpn   = vpn;
        tlb.pfn   = pfn;
        printf("  [TLB更新] VPN=%d → PFN=%d\n", vpn, pfn);
        if (write_access) page_table[vpn].dirty = 1;
        return pfn * PAGE_SIZE + offset;
    }
    /* 页在内存，更新TLB */
    tlb.valid = 1;
    tlb.vpn   = vpn;
    tlb.pfn   = pte->pfn;
    printf("  [页表命中] VPN=%d → PFN=%d，更新TLB\n", vpn, pte->pfn);
    if (write_access) page_table[vpn].dirty = 1;
    return pte->pfn * PAGE_SIZE + offset;
}
/* 打印当前内存状态 */
void print_state() {
    int i;
    printf("\n当前物理内存状态：\n");
    printf("  帧号 | 占用 | VPN\n");
    for (i = 0; i < PHYS_FRAMES; i++) {
        printf("  %3d  |  %d   | %d\n",
               i, phys_mem[i].in_use,
               phys_mem[i].in_use ? phys_mem[i].vpn : -1);
    }
    printf("当前页表状态（present位）：\n");
    printf("  VPN | valid | present | PFN | disk_addr | dirty\n");
    for (i = 0; i < NUM_VPAGES; i++) {
        printf("  %3d |   %d   |    %d    | %3d |     %d     |   %d\n",
               i,
               page_table[i].valid,
               page_table[i].present,
               page_table[i].pfn,
               page_table[i].disk_addr,
               page_table[i].dirty);
    }
}
/* ========== 主函数：演示 ========== */
int main() {
    init();
    printf("=== 带交换机制的内存访问模拟 ===\n");
    print_state();
    /* 测试1：访问已在内存的页（VPN=0） */
    int phys = translate(0, 100, 0);
    printf("  物理地址 = %d\n", phys);
    /* 测试2：再次访问VPN=0（TLB命中）*/
    phys = translate(0, 200, 0);
    printf("  物理地址 = %d\n", phys);
    /* 测试3：访问不在内存的页（VPN=5，触发缺页）*/
    phys = translate(5, 0, 1);
    printf("  物理地址 = %d\n", phys);
    print_state();
    /* 测试4：访问另一个不在内存的页（VPN=6，可能触发置换）*/
    phys = translate(6, 0, 0);
    printf("  物理地址 = %d\n", phys);
    print_state();
    /* 测试5：访问非法地址 */
    phys = translate(10, 0, 0);
    return 0;
}

https://godbolt.org/z/ehzxo61PG

21.4 内存满了怎么办——页面置换

当所有物理帧都被占用时，OS 必须选择一个页踢出去（evict），为新页腾出空间。这个选择过程叫页面置换策略（Page Replacement Policy）。

被踢出的页是否需要写回磁盘？

---

情况	处理方式
干净页（dirty=0，内容未修改）	直接丢弃，不需要写磁盘（磁盘上已有完整备份）
脏页（dirty=1，内容被修改过）	必须先写回磁盘，再释放该帧

---

置换代价非常高，因为涉及磁盘 I/O：
$$\text{缺页代价}\approx \text{磁盘访问时间}\approx 10\text{ ms}=10^4\mu s$$
而正常内存访问只需约 $100\text{ ns}$，相差约 $10$ 万倍。

21.5 完整控制流总结

硬件部分（每次内存访问都走这条路）

VPN = 虚拟地址高位
查 TLB:
  命中 → 直接生成物理地址，访问内存（最快路径）
  未命中 → 查页表 PTE:
      PTE.valid = 0  → 段错误（非法地址）
      PTE.valid = 1, present = 1 → TLB更新，重试（正常）
      PTE.valid = 1, present = 0 → 触发缺页异常（最慢路径）

软件部分（OS 缺页处理程序）

1. 找空闲物理帧
   有 → 直接用
   无 → 运行置换算法，选一页踢出（脏页写回磁盘）
2. 从磁盘读入目标页（阻塞等待I/O，期间运行其他进程）
3. 更新页表（present=1，PFN=新帧号）
4. 重试原指令（会触发TLB miss，再命中，最终访问到内存）

21.6 主动式内存管理：高低水位线

OS 不会等到内存完全耗尽才开始置换，而是提前维护一个"安全缓冲区"：

内存使用量
100% ████████████████████ ← 内存全满（不应到达这里）
 HW  ██████████████████░░ ← 高水位线（High Watermark）
                           触发后台换页线程开始工作
 LW  █████████████░░░░░░░ ← 低水位线（Low Watermark）
                           后台线程工作直到达到此水位
  0% ░░░░░░░░░░░░░░░░░░░░

• 后台换页线程（swap daemon / page daemon）：在系统空闲时悄悄将页换出，维持一定量的空闲帧
• 好处：
  1. 缺页时总能立刻拿到空闲帧，不用等置换完成
  2. 可以批量换出多页（clustering），减少磁盘寻道次数，提高 I/O 效率

批量换出（Clustering）的效果

$$\text{随机写N页的磁盘时间}\gg \text{顺序写N页的磁盘时间}$$
后台线程收集多个待换出的页，一次性顺序写入磁盘，大幅减少磁盘旋转和寻道开销。

关键概念对照表

---

术语	中文	含义
Swap Space	交换空间	磁盘上专门存放被换出页的区域
Present Bit	存在位	PTE 中标记页是否在物理内存的标志
Page Fault	缺页异常	访问不在内存中的页时触发的异常
Page-fault Handler	缺页处理程序	OS 中处理缺页异常的代码
Evict	换出	把物理内存中的某页写到磁盘并释放该帧
Dirty Bit	脏位	标记页内容是否被修改，决定换出时是否需要写回
High/Low Watermark	高/低水位线	触发后台换页线程的内存使用量阈值
Swap Daemon	换页守护进程	后台主动维护空闲内存帧的线程
Clustering	批量写	将多个页一次性顺序写入磁盘，提高效率

---

总结

操作系统通过以下机制实现"超越物理内存"的幻象：

1. 交换空间：在磁盘上预留区域，用于存放暂时不用的页
2. 存在位（present bit）：页表项增加一个标志，区分页在内存还是在磁盘
3. 缺页处理：访问不在内存的页时，由 OS 负责从磁盘换入
4. 页面置换：内存满时，选择一页换出，为新页腾出空间
5. 高低水位线：后台线程主动维护空闲帧，避免临时置换的延迟
   整个过程对进程完全透明：进程只看到一个巨大的、连续的虚拟地址空间，完全不知道背后发生的换入换出。
   $$\text{虚拟内存大小}=\text{物理内存}+\text{交换空间}\gg \text{物理内存}$$
   代价是：当发生缺页时，访问速度从纳秒级跌落到毫秒级，相差约 $10^5$ 倍。因此，减少缺页次数是虚拟内存性能优化的核心目标（下一章的页面置换算法正是为此而生）。

第22章：超越物理内存——页面置换策略

核心问题：内存不够用时，应该把哪一页踢出去？

前言：为什么需要置换策略？

上一章说的是"缺页后怎么把页从磁盘读进来"，但没解决一个关键问题：如果物理内存已经满了，必须先踢出一页，应该踢哪一页？
踢错了代价极大——被踢出的页马上又要用，又得从磁盘读回来，程序速度从内存级别降到磁盘级别，性能相差约 $10^5$ 倍。

22.1 把内存当缓存来理解

物理内存 = 磁盘（虚拟内存）的缓存。
置换策略的目标：最小化缓存未命中次数（miss），即最少次数地访问磁盘。

平均内存访问时间（AMAT）

$$\text{AMAT}=T_M+(P_{Miss}\cdot T_D)$$

• $T_M$：访问内存的时间（约 100 ns）
• $T_D$：访问磁盘的时间（约 10 ms）
• $P_{Miss}$：缺页概率（0.0 ~ 1.0）
  注意：无论是否命中，都要付出 $T_M$ 的代价；缺页时，还要额外付出 $T_D$ 的代价。

数值感受

假设 $T_M=100\text{ ns}$，$T_D=10\text{ ms}$：

$P_{Miss}$（缺页率）	AMAT
10%（0.1）	$100\text{ ns}+0.1\times 10\text{ ms}=1.0001\text{ ms}$
0.1%（0.001）	$100\text{ ns}+0.001\times 10\text{ ms}\approx 10.1\text{ μs}$
接近 0%	接近 $100\text{ ns}$

---

结论：哪怕只有 10% 的缺页率，AMAT 就被拖慢到毫秒级，比纯内存访问慢约 10000 倍。

22.2 最优置换策略（OPT / MIN）

核心思想

每次置换时，踢出未来最晚才会被用到的那一页。
这是理论上的最优解，由 Belady 于 1966 年提出（又叫 MIN 算法）。

直觉解释

如果你必须扔掉一样东西，当然选那个最久不需要用的扔掉，这样对当前工作影响最小。

示例追踪

访问序列：0, 1, 2, 0, 1, 3, 0, 3, 1, 2, 1（缓存容量 = 3页）

访问 | 命中/缺页 | 踢出 | 缓存状态（□=空槽）
  0  |   缺页    |  -   | [0]
  1  |   缺页    |  -   | [0, 1]
  2  |   缺页    |  -   | [0, 1, 2]   ← 冷启动缺页（必然的）
  0  |   命中    |  -   | [0, 1, 2]
  1  |   命中    |  -   | [0, 1, 2]
  3  |   缺页    |  2   | [0, 1, 3]   ← 2是三者中最晚用到的，踢2
  0  |   命中    |  -   | [0, 1, 3]
  3  |   命中    |  -   | [0, 1, 3]
  1  |   命中    |  -   | [0, 1, 3]
  2  |   缺页    |  3   | [0, 1, 2]   ← 踢3（0和1马上就要用）
  1  |   命中    |  -   | [0, 1, 2]

命中率 = $\frac{6}{11}\approx 54.5\%$，排除冷启动缺页后 = $\frac{6}{7}\approx 85.7\%$

为什么不能实用？

需要预知未来！ 操作系统不可能知道程序接下来会访问哪些页。OPT 只作为理论对照基准，用来评估其他算法离最优有多远。

22.3 简单策略一：FIFO（先进先出）

核心思想

把最早进入内存的页踢出去（像排队一样，先来先走）。
实现极简：维护一个队列，新页加入队尾，踢出队头。

示例追踪

访问序列：0, 1, 2, 0, 1, 3, 0, 3, 1, 2, 1（缓存容量 = 3页）

访问 | 命中/缺页 | 踢出 | 缓存状态（先进→靠左）
  0  |   缺页    |  -   | [0]
  1  |   缺页    |  -   | [0, 1]
  2  |   缺页    |  -   | [0, 1, 2]
  0  |   命中    |  -   | [0, 1, 2]
  1  |   命中    |  -   | [0, 1, 2]
  3  |   缺页    |  0   | [1, 2, 3]   ← 踢出最早进来的0，但0马上就要用了！
  0  |   缺页    |  1   | [2, 3, 0]   ← 悲剧：刚踢出0，马上又需要0
  3  |   命中    |  -   | [2, 3, 0]
  1  |   缺页    |  2   | [3, 0, 1]
  2  |   缺页    |  3   | [0, 1, 2]
  1  |   命中    |  -   | [0, 1, 2]

命中率 = $\frac{4}{11}\approx 36.4\%$，比 OPT 差很多。
问题所在：FIFO 不考虑页的重要性，即使某页被频繁访问，只要它进来得早，就会被踢出。

Belady 异常

FIFO 有一个反直觉的特性：增大缓存容量，有时命中率反而下降！
经典反例（访问序列：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5）：

• 缓存容量 3 时命中数 = 3
• 缓存容量 4 时命中数 = 2（反而更差！）
  这就是著名的 Belady 异常。LRU 不存在此问题（因为 LRU 具有"栈属性"）。

22.4 简单策略二：Random（随机置换）

核心思想

随机选一页踢出去。
实现极简，无需维护任何历史信息。

特点

• 平均表现比 FIFO 略好，但不稳定（取决于运气）
• 不存在 Belady 异常
• 对循环顺序访问（见下文）表现比 LRU/FIFO 更好（因为不会系统性地踢错）

22.5 利用历史：LRU（最近最少使用）

核心思想

局部性原理：程序倾向于反复访问同一批页（时间局部性）和相邻的页（空间局部性）。

如果一页最近被频繁使用，它在不久的将来也很可能继续被使用。
反之，如果一页很久没被用了，它很可能不再需要了——踢掉它。

LRU vs LFU

---

算法	全称	淘汰依据
LRU	Least-Recently-Used	最近最久没被访问的页
LFU	Least-Frequently-Used	被访问次数最少的页
MRU	Most-Recently-Used	最近刚被访问的页（通常很差）

---

示例追踪

访问序列：0, 1, 2, 0, 1, 3, 0, 3, 1, 2, 1（缓存容量 = 3页，右边=最近使用）

访问 | 命中/缺页 | 踢出 | 缓存状态（LRU→最左，MRU→最右）
  0  |   缺页    |  -   | [0]
  1  |   缺页    |  -   | [0, 1]
  2  |   缺页    |  -   | [0, 1, 2]
  0  |   命中    |  -   | [1, 2, 0]   ← 0被访问，移到最右（最新）
  1  |   命中    |  -   | [2, 0, 1]
  3  |   缺页    |  2   | [0, 1, 3]   ← 踢出最久未用的2（合理！）
  0  |   命中    |  -   | [1, 3, 0]
  3  |   命中    |  -   | [1, 0, 3]
  1  |   命中    |  -   | [0, 3, 1]
  2  |   缺页    |  0   | [3, 1, 2]   ← 踢出最久未用的0
  1  |   命中    |  -   | [3, 2, 1]

命中率 = $\frac{6}{11}\approx 54.5\%$，与 OPT 结果相同（本例中 LRU 恰好等于最优）。

三种策略的性能对比

不同工作负载下的表现

工作负载类型       OPT   LRU   FIFO  Random
-----------------------------------------
无局部性（随机访问） 最好  =     =      =    （大家差不多）
80-20热点访问      最好  好    还行   还行
循环顺序访问       最好  最差  最差   还行  ← LRU/FIFO在此失效！

循环顺序访问是 LRU 和 FIFO 的噩梦：
例如循环访问 50 个页，缓存只有 49 个槽。每次循环，LRU 都把"即将要用的页"踢出，命中率为 0%！Random 在这种情况下反而不为零，因为它有概率不踢出马上要用的页。

22.7 LRU 的实现困难

理想 LRU 的代价

每次内存访问都需要：

1. 更新时间戳或维护链表顺序（把该页移到"最近使用"端）
2. 置换时扫描所有页，找到时间戳最小（最久未用）的页
   现代系统内存动辄 4GB，页大小 4KB，共有：
   $$\frac{4\times 10^9\text{ B}}{4\times 10^3\text{ B/页}}=10^6\text{ 页（100万页）}$$
   每次置换扫描 100 万页的时间戳 → 代价太高，无法实用。

22.8 近似 LRU：时钟算法（Clock Algorithm）

硬件支持：使用位（Use Bit / Reference Bit）

每个物理页有一个使用位：

• 页被访问（读或写）时，硬件自动将使用位置为 1
• OS 负责将其清零

时钟算法工作原理

想象所有物理页排成一个圆圈，有一个"时钟指针"在转：

        使用位=1
           |
   +---[页A:1]---+
   |              |
[页F:0]        [页B:1]
   |              |
[页E:1]        [页C:0]  ← 时钟指针当前指这里（use=0，直接踢出！）
   |              |
   +---[页D:1]---+

算法步骤：

当需要置换时：
  循环检查时钟指针指向的页 P：
    如果 P.use == 1：
        P.use = 0        ← 给它一次"第二次机会"
        指针前进到下一页
    如果 P.use == 0：
        踢出 P           ← 找到受害者！
        break

关键思想：use=1 的页说明"最近用过，给它留下来的机会"，use=0 的页说明"最近没用过，可以踢出"。

与 LRU 的区别

对比	精确 LRU	时钟算法（近似 LRU）
历史信息	精确时间戳	只有一位（用过/没用过）
每次访问开销	高（更新链表/时间戳）	低（硬件自动设位）
置换时开销	高（扫描全部时间戳）	低（只需转几格）
置换质量	最好	接近 LRU，略差

22.9 考虑脏页（Dirty Bit）

踢出一页时，是否需要写回磁盘？

页的状态	需要写回磁盘？	代价
干净页（dirty=0，没被修改）	不需要，直接丢弃	低
脏页（dirty=1，被修改过）	必须先写回磁盘	高（一次磁盘写 I/O）

---

改进的时钟算法：优先踢出"既没用过、又是干净页"的页（双重条件），实在找不到再退而求其次。

22.10 其他 VM 策略

页面载入策略（什么时候把页读进来？）

• 按需分页（Demand Paging）：缺页时才读入，懒加载，最常用
• 预取（Prefetching）：预测即将使用的页提前读入（例如读了代码页P，顺便读P+1）

写回策略（怎么把脏页写出去？）

• 单页写回：每次有脏页时立刻写磁盘，低效
• 聚集写（Clustering）：积攒多个脏页，一次性批量顺序写磁盘，效率高

22.11 抖动（Thrashing）

什么是抖动？

当系统内存严重不足，所有进程加在一起需要的内存远超物理内存容量时，系统陷入不断换页的恶性循环：

换出页A → 需要页A → 换入页A（踢出页B）
→ 需要页B → 换入页B（踢出页A）
→ 需要页A → ...（无限循环）

CPU 把大部分时间用在等磁盘上，有效计算时间接近于零。

应对方法

完整 C 代码：实现四种置换算法并对比

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
/* ===== 常量定义 ===== */
#define MAX_FRAMES   10    /* 最大缓存帧数 */
#define MAX_REFS     100   /* 最大访问序列长度 */
#define EMPTY        -1    /* 空槽标记 */
/* ===== 工具函数 ===== */
/* 在缓存中查找页，找到返回槽位下标，否则返回-1 */
int find_in_cache(int *cache, int frames, int page) {
    int i;
    for (i = 0; i < frames; i++)
        if (cache[i] == page) return i;
    return -1;
}
/* 找第一个空槽（值为EMPTY），返回下标，没有则返回-1 */
int find_empty_slot(int *cache, int frames) {
    int i;
    for (i = 0; i < frames; i++)
        if (cache[i] == EMPTY) return i;
    return -1;
}
/* 打印当前缓存状态 */
void print_cache(int *cache, int frames) {
    int i;
    printf("[");
    for (i = 0; i < frames; i++) {
        if (cache[i] == EMPTY) printf(" -");
        else printf("%2d", cache[i]);
        if (i < frames - 1) printf(",");
    }
    printf("]");
}
/* ===== 1. FIFO：先进先出 ===== */
int fifo(int *refs, int n, int frames) {
    int cache[MAX_FRAMES];
    int hits = 0, misses = 0;
    int fifo_ptr = 0;  /* 指向下一个要被替换的槽位（最老的页）*/
    int i;
    /* 初始化缓存为空 */
    for (i = 0; i < frames; i++) cache[i] = EMPTY;
    printf("\n--- FIFO (缓存容量=%d) ---\n", frames);
    printf("访问 | 结果 | 踢出 | 缓存状态\n");
    for (i = 0; i < n; i++) {
        int page = refs[i];
        int slot = find_in_cache(cache, frames, page);
        if (slot != -1) {
            /* 命中：什么都不用做 */
            hits++;
            printf("%3d  |  命中 |  -  | ", page);
        } else {
            /* 缺页 */
            misses++;
            int evicted = cache[fifo_ptr];
            cache[fifo_ptr] = page;
            fifo_ptr = (fifo_ptr + 1) % frames;  /* 指针轮转 */
            if (evicted == EMPTY)
                printf("%3d  |  缺页 |  -  | ", page);
            else
                printf("%3d  |  缺页 | %2d  | ", page, evicted);
        }
        print_cache(cache, frames);
        printf("\n");
    }
    printf("命中=%d  缺页=%d  命中率=%.1f%%\n",
           hits, misses, 100.0 * hits / n);
    return hits;
}
/* ===== 2. LRU：最近最少使用 ===== */
int lru(int *refs, int n, int frames) {
    int cache[MAX_FRAMES];
    int last_used[MAX_FRAMES]; /* 每个槽位上的页最后一次被使用的时间 */
    int hits = 0, misses = 0;
    int timer = 0;
    int i, j;
    for (i = 0; i < frames; i++) {
        cache[i] = EMPTY;
        last_used[i] = 0;
    }
    printf("\n--- LRU (缓存容量=%d) ---\n", frames);
    printf("访问 | 结果 | 踢出 | 缓存状态\n");
    for (i = 0; i < n; i++) {
        int page = refs[i];
        int slot = find_in_cache(cache, frames, page);
        timer++;
        if (slot != -1) {
            /* 命中：更新该槽位的最后使用时间 */
            hits++;
            last_used[slot] = timer;
            printf("%3d  |  命中 |  -  | ", page);
        } else {
            misses++;
            /* 找空槽；没有空槽则找最久未用的槽（last_used最小）*/
            int target = find_empty_slot(cache, frames);
            if (target == -1) {
                /* 找LRU：last_used最小的 */
                int min_time = last_used[0];
                target = 0;
                for (j = 1; j < frames; j++) {
                    if (last_used[j] < min_time) {
                        min_time = last_used[j];
                        target = j;
                    }
                }
            }
            int evicted = cache[target];
            cache[target] = page;
            last_used[target] = timer;
            if (evicted == EMPTY)
                printf("%3d  |  缺页 |  -  | ", page);
            else
                printf("%3d  |  缺页 | %2d  | ", page, evicted);
        }
        print_cache(cache, frames);
        printf("\n");
    }
    printf("命中=%d  缺页=%d  命中率=%.1f%%\n",
           hits, misses, 100.0 * hits / n);
    return hits;
}
/* ===== 3. Random：随机置换 ===== */
int random_policy(int *refs, int n, int frames) {
    int cache[MAX_FRAMES];
    int hits = 0, misses = 0;
    int used = 0; /* 当前已用槽数 */
    int i;
    for (i = 0; i < frames; i++) cache[i] = EMPTY;
    printf("\n--- Random (缓存容量=%d) ---\n", frames);
    printf("访问 | 结果 | 踢出 | 缓存状态\n");
    for (i = 0; i < n; i++) {
        int page = refs[i];
        int slot = find_in_cache(cache, frames, page);
        if (slot != -1) {
            hits++;
            printf("%3d  |  命中 |  -  | ", page);
        } else {
            misses++;
            int target;
            if (used < frames) {
                /* 还有空槽，直接填入 */
                target = used++;
            } else {
                /* 随机选一个槽踢出 */
                target = rand() % frames;
            }
            int evicted = cache[target];
            cache[target] = page;
            if (evicted == EMPTY)
                printf("%3d  |  缺页 |  -  | ", page);
            else
                printf("%3d  |  缺页 | %2d  | ", page, evicted);
        }
        print_cache(cache, frames);
        printf("\n");
    }
    printf("命中=%d  缺页=%d  命中率=%.1f%%\n",
           hits, misses, 100.0 * hits / n);
    return hits;
}
/* ===== 4. OPT：最优置换（需要提前知道未来）===== */
/* 返回缓存中"下次使用时间最晚"的槽位下标 */
int find_opt_victim(int *cache, int frames, int *refs, int n, int cur_pos) {
    int i, j;
    int farthest = -1;     /* 下次使用距现在最远的距离 */
    int victim = 0;
    for (i = 0; i < frames; i++) {
        int page = cache[i];
        /* 在refs[cur_pos+1 .. n-1]中找page下一次出现的位置 */
        int next_use = n; /* 如果再也不用了，设为n（无穷远）*/
        for (j = cur_pos + 1; j < n; j++) {
            if (refs[j] == page) {
                next_use = j;
                break;
            }
        }
        if (next_use > farthest) {
            farthest = next_use;
            victim = i;
        }
    }
    return victim;
}
int opt(int *refs, int n, int frames) {
    int cache[MAX_FRAMES];
    int hits = 0, misses = 0;
    int i;
    for (i = 0; i < frames; i++) cache[i] = EMPTY;
    printf("\n--- OPT (缓存容量=%d) ---\n", frames);
    printf("访问 | 结果 | 踢出 | 缓存状态\n");
    for (i = 0; i < n; i++) {
        int page = refs[i];
        int slot = find_in_cache(cache, frames, page);
        if (slot != -1) {
            hits++;
            printf("%3d  |  命中 |  -  | ", page);
        } else {
            misses++;
            int empty_slot = find_empty_slot(cache, frames);
            int target;
            if (empty_slot != -1) {
                target = empty_slot;
            } else {
                /* 找下次使用时间最远的页踢出 */
                target = find_opt_victim(cache, frames, refs, n, i);
            }
            int evicted = cache[target];
            cache[target] = page;
            if (evicted == EMPTY)
                printf("%3d  |  缺页 |  -  | ", page);
            else
                printf("%3d  |  缺页 | %2d  | ", page, evicted);
        }
        print_cache(cache, frames);
        printf("\n");
    }
    printf("命中=%d  缺页=%d  命中率=%.1f%%\n",
           hits, misses, 100.0 * hits / n);
    return hits;
}
/* ===== 5. Clock：时钟算法（近似LRU）===== */
int clock_algo(int *refs, int n, int frames) {
    int cache[MAX_FRAMES];
    int use_bit[MAX_FRAMES]; /* 使用位：硬件访问时置1，时钟扫描时清0 */
    int hits = 0, misses = 0;
    int hand = 0;            /* 时钟指针 */
    int used = 0;
    int i;
    for (i = 0; i < frames; i++) {
        cache[i] = EMPTY;
        use_bit[i] = 0;
    }
    printf("\n--- Clock (缓存容量=%d) ---\n", frames);
    printf("访问 | 结果 | 踢出 | 缓存状态\n");
    for (i = 0; i < n; i++) {
        int page = refs[i];
        int slot = find_in_cache(cache, frames, page);
        if (slot != -1) {
            /* 命中：将该页的使用位置1 */
            hits++;
            use_bit[slot] = 1;
            printf("%3d  |  命中 |  -  | ", page);
        } else {
            misses++;
            int target;
            if (used < frames) {
                /* 还有空槽，直接用 */
                target = used++;
                use_bit[target] = 1;
            } else {
                /* 时钟算法：找use_bit=0的槽 */
                while (use_bit[hand] == 1) {
                    use_bit[hand] = 0; /* 给第二次机会，清零，指针前进 */
                    hand = (hand + 1) % frames;
                }
                target = hand;
                hand = (hand + 1) % frames;
                use_bit[target] = 1;
            }
            int evicted = cache[target];
            cache[target] = page;
            if (evicted == EMPTY)
                printf("%3d  |  缺页 |  -  | ", page);
            else
                printf("%3d  |  缺页 | %2d  | ", page, evicted);
        }
        print_cache(cache, frames);
        printf("\n");
    }
    printf("命中=%d  缺页=%d  命中率=%.1f%%\n",
           hits, misses, 100.0 * hits / n);
    return hits;
}
/* ===== 主函数：对比所有算法 ===== */
int main() {
    /* 书中示例访问序列 */
    int refs[] = {0, 1, 2, 0, 1, 3, 0, 3, 1, 2, 1};
    int n = sizeof(refs) / sizeof(refs[0]);
    int frames = 3;
    srand(42); /* 固定随机种子，使Random结果可复现 */
    printf("=== 页面置换算法对比 ===\n");
    printf("访问序列：");
    for (int i = 0; i < n; i++) printf("%d ", refs[i]);
    printf("\n缓存容量：%d 页\n", frames);
    int h_opt   = opt(refs, n, frames);
    int h_lru   = lru(refs, n, frames);
    int h_fifo  = fifo(refs, n, frames);
    int h_rand  = random_policy(refs, n, frames);
    int h_clock = clock_algo(refs, n, frames);
    printf("\n=== 命中率汇总 ===\n");
    printf("OPT   : %d/%d = %.1f%%\n", h_opt,   n, 100.0*h_opt/n);
    printf("LRU   : %d/%d = %.1f%%\n", h_lru,   n, 100.0*h_lru/n);
    printf("Clock : %d/%d = %.1f%%\n", h_clock, n, 100.0*h_clock/n);
    printf("FIFO  : %d/%d = %.1f%%\n", h_fifo,  n, 100.0*h_fifo/n);
    printf("Random: %d/%d = %.1f%%\n", h_rand,  n, 100.0*h_rand/n);
    return 0;
}

https://godbolt.org/z/3MPcqnzPE

各算法综合对比

算法     | 命中率（本例）| 实现难度 | 优点               | 缺点
---------|-------------|---------|-------------------|------------------
OPT      |  54.5%      |  不可实现 | 理论最优，作为基准  | 需要预知未来
LRU      |  54.5%      |  中等    | 利用局部性，效果好  | 完整实现开销大
Clock    |  接近LRU    |  低      | 近似LRU，硬件支持  | 精度略低于LRU
FIFO     |  36.4%      |  极低    | 实现简单           | 不考虑访问频率，Belady异常
Random   |  不确定      |  极低    | 无corner-case     | 性能不稳定

总结：如何选择置换策略？

实践中的选择：现代操作系统普遍使用时钟算法的变种（如 Linux 的 LRU 近似），同时配合脏位（dirty bit）优先淘汰干净页的优化，以及预取和批量写回等辅助策略，在性能和实现复杂度之间取得平衡。
$$\text{核心原则：缺页代价}\approx 10^5\times \text{内存访问代价，减少缺页 = 最重要的优化目标}$$

第23章：完整的虚拟内存系统

本章把前面所有零散的知识拼在一起，通过两个真实系统（VAX/VMS 和 Linux）看一个完整的虚拟内存系统长什么样。

为什么要研究完整系统？

前面几章分别讲了：页表结构、TLB、页面置换算法……但这些都是零件。真实系统还需要考虑：

• 安全性（防止进程互相访问）
• 性能（减少 TLB 未命中、减少磁盘 I/O）
• 灵活性（从手机到服务器都能跑）
• 各种"懒惰优化"（延迟做事，只在真正需要时才工作）
  本章通过 VAX/VMS（1970年代的经典）和 Linux（现代主流）两个系统来讲清楚这些问题。

23.1 VAX/VMS 虚拟内存系统

VAX/VMS 是 1970～80 年代 DEC 公司开发的操作系统，其首席架构师 Dave Cutler 后来主导了 Windows NT 的开发。它的很多思想沿用至今。

地址空间布局

VAX-11 的虚拟地址是 32 位，但页面只有 512 字节（非常小！），因此 VPN 有 23 位，offset 有 9 位。
地址空间分为三段（混合了分页和分段）：

虚拟地址空间（32位 = 4GB）
+---------------------------+  地址 0
|  页0：故意标记为无效         |  ← 用于捕获空指针访问
|  用户代码（P0段）           |
|  用户堆（向上增长）          |
+---------------------------+  地址 2^30
|  用户栈（P1段，向下增长）    |
+---------------------------+  地址 2^31
|  系统空间（S段）            |
|  内核代码、内核数据           |
|  陷阱表（Trap Tables）      |
+---------------------------+  地址 2^32

关键设计：

• P0（低地址）：用户代码 + 堆
• P1（中段）：用户栈
• S（高地址）：内核，所有进程共享（上下文切换时 S 的基址寄存器不变）

为什么页面小（512字节）是个问题？

页表项数量 = $\frac{2^{32}}{2^9}=2^{23}\approx 800\text{ 万项}$
每个 PTE 4 字节，线性页表大小 = $2^{23}\times 4=32\text{ MB}$，每个进程都要占这么多，根本扛不住。

VMS 如何缩小页表？

两个技巧组合使用：
技巧一：只给 P0 和 P1 各维护一张页表
P0 的页表只覆盖代码+堆，P1 的页表只覆盖栈。中间没用的地址空间不需要任何页表项（用 base/bounds 寄存器限定范围）。

P0 页表（只有代码+堆用到的部分）：小
P1 页表（只有栈用到的部分）：小
S  页表（内核，物理内存中，所有进程共享）

技巧二：把用户页表本身放在内核虚拟内存里
用户进程的 P0 和 P1 页表不放在固定的物理内存，而是放在内核自己的虚拟地址空间（S 段）中。好处：

• 内存紧张时，页表本身也可以被换出到磁盘
• 内核统一管理，按需分配
  代价是翻译时多了一层间接：

幸运的是，TLB 通常能命中，绕过这个复杂流程。

空指针为什么会崩溃？

进程访问虚拟地址 0（int *p = NULL; *p = 10;）
→ 硬件查 TLB，VPN=0 未命中
→ 查页表，VPN=0 对应的 PTE 标记为"无效"
→ 触发异常
→ OS 收到异常，终止进程（发送信号）

第0页被故意标记为无效，就是为了捕获这种错误。

VAX/VMS 的页面置换：分段 FIFO

VAX 的页表项（PTE）结构：

+--------+----------+--------+-----------+--------+
| valid  | prot(4b) | dirty  | 保留OS用   |  PFN   |
+--------+----------+--------+-----------+--------+

注意：VAX 硬件没有"引用位（reference bit）"！ 不能直接做 LRU。
解决方案：分段 FIFO（Segmented FIFO）
每个进程有一个驻留集大小（RSS，Resident Set Size），即允许占用的最大物理帧数。

核心思想：踢出的页不立刻扔掉，而是放在"二次机会列表"里。如果原进程很快又访问它，可以直接从列表里取回，避免一次磁盘读操作。

如何模拟引用位（无硬件支持）

将所有页临时标记为"不可访问"：

• 进程访问该页 → 触发 OS 陷阱
• OS 检查：该页实际上应该可以访问 → 恢复权限，记录"此页被引用过"
• 置换时：未被引用的页就是候选者
  这是用保护位模拟引用位的技巧。

聚集写（Clustering）优化

512 字节的小页导致换出时磁盘 I/O 效率低（磁盘每次 I/O 有固定开销，写一小页很浪费）。
解决方案：把脏页列表中的多个页一次性批量写入磁盘，大幅提升 I/O 效率。
$$\text{写 N 个小页（分N次）的时间}\gg \text{写 N 个小页（一次顺序 I/O）的时间}$$

懒惰优化一：按需清零（Demand Zeroing）

问题：进程申请新页时，OS 必须先把该页内容清零（安全要求：不能让进程看到前一个进程留下的数据）。但如果进程申请了页却不用，清零工作白做了。
按需清零方案：

进程申请新页
→ OS 只在页表里插入一个特殊标记（"此页需要清零"），不实际分配物理内存
→ 进程真正读写该页时 → 触发 OS 陷阱
→ OS 才真正找一个物理帧、清零、映射
→ 如果进程从未访问该页 → 全程零开销

懒惰优化二：写时复制（Copy-on-Write，COW）

问题：Unix 的 fork() 调用会复制整个父进程的地址空间，但随后往往立刻调用 exec() 把地址空间全部覆盖，复制工作白做了。
COW 方案：

fork() 时：
  不实际复制物理页
  只让父子进程的页表都指向同一批物理页
  把这些页的保护位设为"只读"
如果父或子进程只读这些页 → 完全不需要复制，零开销
如果某一方试图写某页：
  触发保护错误（写只读页）
  OS 识别这是 COW 页
  分配一个新的物理页，复制内容
  更新写方的页表指向新页，恢复读写权限
  另一方继续使用原物理页

fork() 之后（COW状态）：
父进程页表          共享物理页          子进程页表
[VPN0 → PFN5 只读] → [PFN5: 数据A] ← [VPN0 → PFN5 只读]
[VPN1 → PFN6 只读] → [PFN6: 数据B] ← [VPN1 → PFN6 只读]
子进程写 VPN1 时：
  OS 分配新 PFN9，复制 PFN6 内容
  子进程页表更新：[VPN1 → PFN9 读写]
  父进程不受影响
父进程页表          物理页              子进程页表
[VPN0 → PFN5 只读] → [PFN5: 数据A] ← [VPN0 → PFN5 只读]
[VPN1 → PFN6 只读] → [PFN6: 数据B]
                       [PFN9: 数据B'] ← [VPN1 → PFN9 读写]

23.2 Linux 虚拟内存系统

Linux 在 x86 上运行，继承了 VMS 的很多思想，并加入了大量现代特性。

Linux 地址空间布局（32位）

32位 Linux 的地址空间在 0xC0000000（即 3GB 处）分割：

虚拟地址空间（0 ~ 4GB）
0x00000000 ─────────────────────────────
           |  页0：无效（捕获空指针）     |
           |  用户代码                   |
           |  用户堆（向上增长）          |  用户空间
           |  ...                        |  （0 ~ 3GB）
           |  用户栈（向下增长）          |
0xC0000000 ─────────────────────────────
           |  内核逻辑地址空间            |
           |  （页表、内核栈、数据...）    |  内核空间
           |  内核虚拟地址空间            |  （3GB ~ 4GB）
0xFFFFFFFF ─────────────────────────────

64位 Linux 有类似的分割，但位置不同，用户和内核各有更大空间。

两种内核地址

Linux 内核空间有两种不同性质的地址：

类型	申请方式	与物理内存关系	能否交换到磁盘	适用场景
内核逻辑地址（Kernel Logical）	kmalloc	直接映射，地址 - 偏移量 = 物理地址	不能	页表、内核栈、DMA 操作
内核虚拟地址（Kernel Virtual）	vmalloc	任意映射，物理上不连续	能	大缓冲区

---

内核逻辑地址的直接映射非常有用：
$$\text{物理地址}=\text{内核逻辑地址}-0xC0000000$$
这意味着内核不需要复杂的翻译就能直接操作物理内存，对 DMA（直接内存访问）设备特别重要。

x86 四级页表（64位）

64位 x86 Linux 使用四级页表，但实际只用了 48 位虚拟地址：

虚拟地址（64位，实际使用48位）：
63      48 47    39 38    30 29    21 20    12 11       0
+----------+--------+--------+--------+--------+---------+
| 未使用   |  P1    |  P2    |  P3    |  P4    | Offset  |
| (16位)  | (9位)  | (9位)  | (9位)  | (9位)  | (12位)  |
+----------+--------+--------+--------+--------+---------+
              |        |        |        |
              v        v        v        v
           顶层页   二级页   三级页   四级页
           目录     目录     目录     表（PTE）

翻译过程（树形结构）：

随着内存越来越大，未来可能出现五级甚至六级页表。

大页支持（Huge Pages）

除了标准的 4KB 页，x86 支持 2MB 和 1GB 的大页。
为什么需要大页？
现代程序使用几十 GB 内存，TLB 只有几百个槽。如果全用 4KB 页：
$$\text{TLB 能覆盖的内存}=512\text{个槽}\times 4\text{ KB}=2\text{ MB}$$
访问 10GB 数据时，几乎每次都 TLB 未命中。研究表明，某些大内存程序有 10% 的 CPU 时间消耗在处理 TLB 未命中上。
改用 2MB 大页：
$$\text{TLB 能覆盖的内存}=512\text{个槽}\times 2\text{ MB}=1\text{ GB}$$
效果提升 512 倍！
Linux 的两种大页使用方式：

• 显式申请：通过 mmap() 或 shmget() 指定大页，适合数据库等高性能应用
• 透明大页（THP）：OS 自动在后台合并普通页为大页，程序无需修改
  大页的代价：内部碎片（申请了 2MB，实际只用了 1KB，浪费 2MB-1KB）。

Linux 页面缓存（Page Cache）

Linux 把以下三类内容统一放在"页面缓存"中：

页面缓存（Page Cache）
+---------------------------+
| 内存映射的文件数据          |  mmap() 映射的文件
| 文件系统的文件数据/元数据    |  read()/write() 访问的文件
| 进程的匿名内存（堆/栈）     |  没有对应文件，用交换空间
+---------------------------+

脏页管理：被修改的页（dirty）由后台线程 pdflush 定期写回磁盘，满足以下两个条件之一就触发：

1. 脏页等待时间超过阈值
2. 脏页数量占比过高

Linux 的 2Q 置换算法

标准 LRU 有一个弱点：循环扫描大文件会把缓存里的其他有用页全部踢光（因为大文件的每一页都被访问一次，全部被认为是"最近使用"）。
2Q 算法（Linux 的改进版）维护两个列表：

活跃列表（active list）：约占 2/3 空间
+------------------------------------------+
| 最近被"二次访问"的页（真正热门）           |
+------------------------------------------+
                          ↑ 从非活跃列表晋升
非活跃列表（inactive list）：约占 1/3 空间
+------------------------------------------+
| 第一次被访问的页（新来的，还不确定热不热）  |
+------------------------------------------+
  ↑ 新页进入这里          ↓ 置换时从这里踢

工作流程：

对循环扫描大文件的保护：大文件的页只会进入非活跃列表，扫描一遍后再也不被访问，直接从非活跃列表被踢出，不会影响活跃列表里的真正热门页。

安全：缓冲区溢出与防御

缓冲区溢出攻击

/* 有漏洞的函数 */
int some_function(char *input) {
    char dest_buffer[100];    /* 只有100字节的缓冲区 */
    strcpy(dest_buffer, input); /* 如果input超过100字节，就溢出了！*/
}

攻击者精心构造超长输入，覆盖栈上的返回地址，让函数返回时跳转到攻击者注入的恶意代码处。

防御手段一：NX 位（不可执行位）

在页表项中加入 NX（No-eXecute）位，标记栈和堆页为不可执行：

栈页的 PTE：
+-------+------+-----+----+--------+
| valid | prot | ... | NX |  PFN   |
+-------+------+-----+----+--------+
                       ↑
                  NX=1：该页不可执行
                  攻击者注入的代码无法运行

防御手段二：ASLR（地址空间布局随机化）

问题：即使有 NX，攻击者可以用"返回导向编程（ROP）"——不注入新代码，而是利用程序中已有的代码片段（gadgets）拼凑出恶意操作。这需要知道代码的确切地址。
ASLR 方案：每次运行时，随机化代码、栈、堆的起始地址：

第一次运行：
  代码段：0x400000
  栈：    0x7ffd3e55d000
第二次运行：
  代码段：0x7f3a4b200000（不同！）
  栈：    0x7ffe1033b000（不同！）

攻击者无法预测地址，ROP 链无法构造，攻击只会导致程序崩溃而无法成功劫持。
KASLR：内核地址也随机化（Kernel ASLR）。

防御手段三：KPTI（内核页表隔离）

针对 Meltdown/Spectre 漏洞：
问题：CPU 的推测执行（Speculative Execution）会提前执行一些"猜测性"指令，这些指令会留下缓存痕迹，攻击者可以通过测量缓存命中率来推断内核内存的内容——即使那些内存标记为"不可访问"。
KPTI 方案：用户态运行时，内核几乎从地址空间中"消失"，只保留最少量的内核映射；进入内核时切换到专用内核页表。

用户态运行时的地址空间：
+----------------------+
| 用户代码、堆、栈      |
+----------------------+
| 极少量内核映射        |  ← 仅够完成系统调用入口
| （大部分内核被移走）  |
+----------------------+
进入内核时：切换到内核专用页表（含完整内核映射）

代价：每次系统调用需要切换页表，性能损失约 5%~30%（取决于系统调用频率）。

完整 C 代码：演示 COW 和懒惰初始化思想

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* ====================================================
 * 演示写时复制（COW）和按需清零（Demand Zero）的核心思想
 * 注意：真实 COW 由 OS 内核在硬件层完成，这里用软件模拟逻辑
 * ==================================================== */
#define NUM_PAGES   8
#define PAGE_SIZE   64   /* 模拟用，每页64字节 */
/* ===== 模拟物理内存 ===== */
typedef struct {
    char data[PAGE_SIZE];
    int  ref_count;   /* 引用计数：多少个进程在共享这一帧 */
    int  in_use;
} PhysPage;
PhysPage phys_pages[64];  /* 模拟64个物理页 */
int next_free_page = 0;
/* 分配一个新物理页，返回其编号 */
int alloc_phys_page() {
    if (next_free_page >= 64) {
        fprintf(stderr, "物理内存耗尽！\n");
        return -1;
    }
    int pfn = next_free_page++;
    memset(phys_pages[pfn].data, 0, PAGE_SIZE); /* 清零：安全要求 */
    phys_pages[pfn].ref_count = 1;
    phys_pages[pfn].in_use    = 1;
    return pfn;
}
/* ===== 页表项定义 ===== */
typedef struct {
    int valid;        /* 此 VPN 是否合法 */
    int present;      /* 页是否在内存中 */
    int pfn;          /* 物理帧号 */
    int read_only;    /* 是否只读（COW时设为1）*/
    int demand_zero;  /* 是否是按需清零页（还未实际分配）*/
    int cow;          /* 是否是写时复制页 */
} PTE;
/* ===== 进程结构 ===== */
typedef struct {
    int  pid;
    PTE  page_table[NUM_PAGES];
    char name[32];
} Process;
/* ===== 辅助函数 ===== */
void print_page_table(Process *proc) {
    printf("进程 %s (pid=%d) 的页表：\n", proc->name, proc->pid);
    printf("  VPN | valid | present | pfn | ro | dz | cow\n");
    for (int i = 0; i < NUM_PAGES; i++) {
        PTE *p = &proc->page_table[i];
        if (p->valid) {
            printf("  %3d |   1   |    %d    | %3d |  %d |  %d |  %d\n",
                   i, p->present, p->pfn,
                   p->read_only, p->demand_zero, p->cow);
        }
    }
}
/* ===== 按需清零（Demand Zero）===== */
/* 初始化一个"按需清零"页：只设标记，不实际分配物理内存 */
void map_demand_zero(Process *proc, int vpn) {
    proc->page_table[vpn].valid       = 1;
    proc->page_table[vpn].present     = 0;  /* 尚未在内存中 */
    proc->page_table[vpn].demand_zero = 1;  /* 标记：需要清零 */
    proc->page_table[vpn].pfn         = -1;
    printf("[按需清零] %s: VPN=%d 标记为按需清零，未分配物理内存\n",
           proc->name, vpn);
}
/* 触发按需清零页的实际分配（模拟缺页处理程序）*/
int handle_demand_zero(Process *proc, int vpn) {
    printf("[缺页处理] %s: VPN=%d 首次访问，触发按需清零\n",
           proc->name, vpn);
    int pfn = alloc_phys_page(); /* 此时才真正分配并清零 */
    if (pfn < 0) return -1;
    proc->page_table[vpn].pfn         = pfn;
    proc->page_table[vpn].present     = 1;
    proc->page_table[vpn].demand_zero = 0;
    printf("[按需清零] %s: VPN=%d → PFN=%d（已清零）\n",
           proc->name, vpn, pfn);
    return pfn;
}
/* ===== 写时复制（COW）===== */
/* 模拟 fork()：子进程与父进程共享所有页，全部设为只读 */
void cow_fork(Process *parent, Process *child) {
    printf("\n[fork] 进程 %s fork 出子进程 %s\n",
           parent->name, child->name);
    for (int i = 0; i < NUM_PAGES; i++) {
        PTE *pp = &parent->page_table[i];
        PTE *cp = &child->page_table[i];
        if (pp->valid && pp->present) {
            /* 子进程指向同一物理页 */
            *cp = *pp;
            cp->read_only = 1;  /* 设为只读 */
            cp->cow       = 1;  /* 标记为 COW 页 */
            pp->read_only = 1;  /* 父进程也设为只读 */
            pp->cow       = 1;
            /* 引用计数 +1 */
            phys_pages[pp->pfn].ref_count++;
            printf("  VPN=%d: 父子共享 PFN=%d（均设为只读 COW）\n",
                   i, pp->pfn);
        } else {
            cp->valid = 0; /* 父进程没有的页，子进程也没有 */
        }
    }
}
/* 模拟写操作：如果是 COW 页，触发实际复制 */
int cow_write(Process *proc, int vpn, char *data) {
    PTE *pte = &proc->page_table[vpn];
    if (!pte->valid || !pte->present) {
        /* 按需清零场景 */
        if (pte->demand_zero) {
            handle_demand_zero(proc, vpn);
            pte = &proc->page_table[vpn];
        } else {
            printf("[错误] %s: VPN=%d 无效访问\n", proc->name, vpn);
            return -1;
        }
    }
    if (pte->cow && pte->read_only) {
        /* 写了只读的 COW 页：触发复制 */
        int old_pfn = pte->pfn;
        printf("[COW] %s: VPN=%d 写只读页 PFN=%d，触发复制\n",
               proc->name, vpn, old_pfn);
        /* 分配新物理页，复制内容 */
        int new_pfn = alloc_phys_page();
        if (new_pfn < 0) return -1;
        memcpy(phys_pages[new_pfn].data,
               phys_pages[old_pfn].data, PAGE_SIZE);
        /* 更新该进程的页表：指向新页，恢复可写 */
        pte->pfn       = new_pfn;
        pte->read_only = 0;
        pte->cow       = 0;
        /* 减少旧页的引用计数 */
        phys_pages[old_pfn].ref_count--;
        printf("[COW] %s: 复制完成，VPN=%d → 新 PFN=%d，旧 PFN=%d 引用计数=%d\n",
               proc->name, vpn, new_pfn, old_pfn,
               phys_pages[old_pfn].ref_count);
    }
    /* 实际写入数据 */
    strncpy(phys_pages[pte->pfn].data, data, PAGE_SIZE - 1);
    printf("[写入] %s: VPN=%d(PFN=%d) 写入: \"%s\"\n",
           proc->name, vpn, pte->pfn, data);
    return 0;
}
/* 读操作（简单） */
void cow_read(Process *proc, int vpn) {
    PTE *pte = &proc->page_table[vpn];
    if (!pte->valid) {
        printf("[读取] %s: VPN=%d 无效\n", proc->name, vpn);
        return;
    }
    if (pte->demand_zero && !pte->present) {
        handle_demand_zero(proc, vpn);
        pte = &proc->page_table[vpn];
    }
    printf("[读取] %s: VPN=%d(PFN=%d) 内容: \"%s\"\n",
           proc->name, vpn, pte->pfn,
           phys_pages[pte->pfn].data[0] ? phys_pages[pte->pfn].data : "(全零)");
}
/* ===== 主函数 ===== */
int main() {
    /* 创建父进程 */
    Process parent = {0};
    parent.pid = 1;
    strcpy(parent.name, "parent");
    /* 父进程分配几个页（正常分配，已在内存）*/
    printf("=== 初始化父进程 ===\n");
    for (int i = 0; i < 3; i++) {
        int pfn = alloc_phys_page();
        parent.page_table[i].valid   = 1;
        parent.page_table[i].present = 1;
        parent.page_table[i].pfn     = pfn;
        char buf[32];
        snprintf(buf, sizeof(buf), "parent_page_%d", i);
        strncpy(phys_pages[pfn].data, buf, PAGE_SIZE);
        printf("  父进程 VPN=%d → PFN=%d，内容=\"%s\"\n", i, pfn, buf);
    }
    /* 父进程的第4页设置为按需清零（还没真正分配）*/
    map_demand_zero(&parent, 3);
    printf("\n=== fork() 操作（COW）===\n");
    Process child = {0};
    child.pid = 2;
    strcpy(child.name, "child");
    cow_fork(&parent, &child);
    printf("\n=== fork 后，父子页表 ===\n");
    print_page_table(&parent);
    print_page_table(&child);
    printf("\n=== 子进程读 VPN=0（共享页，不触发复制）===\n");
    cow_read(&child, 0);
    printf("\n=== 子进程写 VPN=1（触发 COW 复制）===\n");
    cow_write(&child, 1, "child_modified_page1");
    printf("\n=== 父进程写 VPN=2（触发 COW 复制）===\n");
    cow_write(&parent, 2, "parent_modified_page2");
    printf("\n=== 子进程读 VPN=3（按需清零页，首次访问）===\n");
    cow_read(&child, 3);
    printf("\n=== 操作完成后，父子页表 ===\n");
    print_page_table(&parent);
    print_page_table(&child);
    printf("\n=== 物理页引用计数 ===\n");
    for (int i = 0; i < next_free_page; i++) {
        printf("  PFN=%d：引用计数=%d，内容=\"%s\"\n",
               i, phys_pages[i].ref_count, phys_pages[i].data);
    }
    return 0;
}

https://godbolt.org/z/MorT819j8

VAX/VMS 与 Linux 核心特性对比

特性                  VAX/VMS（1970s）       Linux（现代）
--------------------  ---------------------  -----------------------
地址空间分割          P0/P1/S 三段            用户/内核两段（3:1 或更大）
页面大小              512 字节（很小！）       4KB（标准）/ 2MB / 1GB
页表缩小方案          分段+分页混合            多级页表（32位4级，64位4级）
置换算法              分段 FIFO + 二次机会     2Q（活跃/非活跃双列表）
引用位                无（用保护位模拟）        有（硬件提供，近似 LRU）
写时复制（COW）       支持                    支持（fork 时使用）
按需清零              支持                    支持（/dev/zero 映射）
聚集写（Clustering）  支持                    支持（pdflush 后台线程）
大页支持              无                      2MB / 1GB 透明大页（THP）
安全防护              基本保护位              NX 位 + ASLR + KASLR + KPTI

总结

一个完整的虚拟内存系统，绝不只是"把 VPN 翻译成 PFN"这么简单，它需要：

1. 地址空间设计：合理划分用户和内核空间，第0页设为无效捕获空指针
2. 页表结构优化：分段减少无效项，多级页表节省空间，大页减少 TLB 压力
3. 懒惰优化：按需清零（Demand Zero）和写时复制（COW）避免无效工作
4. 置换算法：2Q 或近似 LRU，抵抗循环访问场景
5. 统一缓存：页面缓存统一管理文件、匿名内存，后台线程定期刷新
6. 安全机制：NX 防止代码注入，ASLR 防止 ROP，KPTI 防止推测执行泄露
   $$\text{好的VM系统}=\text{正确性}+\text{性能}+\text{安全性}+\text{对程序员透明}$$

内存虚拟化总结对话 — 详细中文解析

原文来源：《操作系统：三大件》(OSTEP) 第24章 Summary Dialogue on Memory Virtualization

一、整体背景：为什么要学内存虚拟化？

对话开头，学生担心考试记不住内容，教授纠正了这种思路：

学习的目的不是应付考试，而是建立"心智模型"（Mental Model），让你在真实工作中遇到奇怪的系统行为时，能够快速诊断原因。
教授举了一个亲身经历的例子：

• 研究生时期，他们测量内存访问时间，偶尔出现远超预期的高延迟
• 他们以为数据都在二级缓存（L2 Cache）里，应该很快
• 请教教授后，对方只说了一个词：“TLB”
• 恍然大悟：是 TLB Miss（地址转换缓存缺失） 导致的性能下降
  这个例子说明：理解虚拟内存的工作原理，能帮你解决真实的性能问题。

二、核心知识点逐一解析

2.1 所有用户程序看到的地址都是虚拟地址

用户程序
   |
   | 使用虚拟地址（如 0x7fff...）
   v
操作系统 + 硬件（MMU）
   |
   | 翻译为物理地址
   v
实际内存（DRAM）

关键理解：

• 你在 C 程序里用 printf("%p", ptr) 打印出来的指针地址，是虚拟地址，不是真实的物理内存地址
• 操作系统刻意对用户隐藏物理地址，每个进程都以为自己独占整个地址空间
• 这种"幻觉"就是**内存虚拟化（Memory Virtualization）**的核心目的
  C 语言演示：

/*
 * 演示：打印指针地址只能看到虚拟地址
 * 编译：gcc -o demo demo.c
 * 运行：./demo
 */
#include <stdio.h>
#include <stdlib.h>
int global_var = 42;  /* 全局变量，位于数据段 */
int main(void) {
    int local_var = 10;          /* 局部变量，位于栈上 */
    int *heap_var = malloc(sizeof(int));  /* 堆上分配的内存 */
    *heap_var = 99;
    /* 以下打印的全部是"虚拟地址"，不是物理地址 */
    printf("全局变量地址（虚拟）: %p\n", (void *)&global_var);
    printf("栈变量地址（虚拟）:   %p\n", (void *)&local_var);
    printf("堆变量地址（虚拟）:   %p\n", (void *)heap_var);
    free(heap_var);
    return 0;
}

https://godbolt.org/z/EWqeE4c1E
运行两次，你会发现地址可能不同（ASLR 地址随机化），但它们都是虚拟地址，OS 在背后维护着到物理地址的映射。

2.2 TLB：地址转换的"快速缓存"

问题背景

进程访问内存时，CPU 需要把虚拟地址翻译成物理地址。翻译依赖页表（Page Table），但页表存在内存里，访问一次需要额外的内存读取，极大拖慢速度。

TLB 的作用

TLB（Translation Lookaside Buffer，地址转换旁路缓冲器） 是 CPU 内部的一块小型硬件缓存，专门存储最近用过的虚拟地址到物理地址的映射。

CPU 发出虚拟地址 VA
        |
        v
   [TLB 查找]
   /         \
命中(Hit)   缺失(Miss)
   |              |
   |         去内存里查页表
   |              |
   v              v
得到物理地址 PA，访问内存

性能影响

设页表访问需要额外 $N$ 次内存访问，TLB 命中率为 $h$，则平均有效访问时间（EAT）为：
$$EAT=h\times t_{mem}+(1-h)\times (N\times t_{mem}+t_{mem})$$
其中 $t_{mem}$ 是一次内存访问时间。
极端情况举例（假设 $t_{mem}=100ns$，页表需要 1 次额外访问，即 $N=1$）：

• TLB 命中率 $h=0.99$：$EAT=0.99\times 100+0.01\times 200=101ns$，几乎无额外开销
• TLB 命中率 $h=0.50$：$EAT=0.50\times 100+0.50\times 200=150ns$，慢了 50%

Working Set 与 TLB Coverage

工作集（Working Set）：程序在某段时间内频繁访问的页面集合。
如果工作集的大小超过了 TLB 能覆盖的地址范围，就会频繁发生 TLB Miss，性能急剧下降。
设 TLB 条目数为 $E$，页大小为 $P$ 字节，则 TLB 能覆盖的地址范围为：
$$Coverage=E\times P$$
例如：TLB 有 64 条，页大小 4KB，则覆盖范围 = $64\times 4096=256KB$

2.3 页表：核心数据结构

页表的本质是一个数据结构，记录虚拟页号（VPN）到物理帧号（PFN）的映射。

线性页表（数组结构）

最简单的实现：一个大数组，下标是虚拟页号，值是物理帧号。

虚拟地址：[ VPN | 页内偏移 ]
                |
                v
         page_table[VPN] = PFN
                |
                v
物理地址：[ PFN | 页内偏移 ]

问题：空间浪费极大。 若地址空间 4GB，页大小 4KB，则页表有 $\frac{4GB}{4KB}=2^{20}\approx 100$ 万条目，每条 4 字节，页表本身就占 4MB——每个进程都要一份！

多级页表（树状结构）

用"按需分配"思想，只为实际使用的地址段分配页表。

优势： 未使用的地址空间不需要分配页表空间，节省内存。

多级页表地址翻译过程（ASCII 演示）

64位虚拟地址（以x86-64四级为例）：
 63      48 47    39 38    30 29    21 20    12 11       0
 +---------+--------+--------+--------+--------+---------+
 | 符号扩展 |  L4索引 |  L3索引 |  L2索引 |  L1索引 |  页内偏移 |
 +---------+--------+--------+--------+--------+---------+
      16       9        9        9        9        12
翻译步骤：
  CR3寄存器
     |
     +--[L4索引]--> L4页表 --> L3页表基地址
                                    |
                               +--[L3索引]--> L3页表 --> L2页表基地址
                                                              |
                                                         +--[L2索引]--> L2页表 --> L1页表基地址
                                                                                       |
                                                                                  +--[L1索引]--> 物理帧号PFN
                                                                                                     |
                                                                                              PFN + 页内偏移 = 物理地址

2.4 地址空间的灵活性：从基址/界限到多级页表

早期系统使用基址寄存器（Base）+ 界限寄存器（Bounds）：

物理地址 = 虚拟地址 + Base
条件：虚拟地址 < Bounds

缺陷： 地址空间必须连续分配，碎片化严重，无法支持稀疏地址空间（如栈和堆之间的大片空洞）。
多级页表解决了这个问题：只为有数据的地址段建立页表，空洞不占空间。

2.5 磁盘换页（Swapping）与页面替换策略

当物理内存不足时，OS 将部分页面换出到磁盘（Swap 分区），需要时再换回来。

常见页面替换算法对比

算法         | 原理                     | 优点           | 缺点
------------|--------------------------|----------------|------------------
OPT（最优）  | 替换未来最晚用到的页      | 理论最优         | 需要预知未来，不可实现
LRU          | 替换最近最久未使用的页    | 近似最优         | 实现开销大（需记录时间戳）
FIFO         | 替换最先进入的页          | 实现简单         | Belady异常，性能差
Clock        | LRU近似，用引用位         | 开销低，效果较好  | 近似而非精确

LRU 的数学直觉

设时间窗口 $T$ 内访问了 $k$ 个不同页面，若 TLB/缓存大小为 $m$：

• 若 $m\ge k$，则 LRU 缺页率接近 0
• 若 $m<k$，缺页率 $\approx \frac{k-m}{k}$（近似）

学生的终极领悟

“策略问题的最佳解答其实很简单：买更多内存。但机制你必须搞懂，因为那才是系统真正运作的方式。”
这句话揭示了一个工程哲学：理解底层机制比记住具体策略更重要，因为硬件会变，策略会变，但原理不会变。

三、整体知识框架总结

四、关键公式汇总

---

概念	公式
物理地址（基址/界限）	$PA=VA+Base$，且 $VA<Bounds$
物理地址（分页）	$PA=PFN\times PageSize+Offset$
页表大小（线性）	$TableSize=\frac{AddressSpaceSize}{PageSize}\times EntrySize$
TLB 覆盖范围	$Coverage=TL{B}_{entries}\times PageSize$
有效访问时间（EAT）	$EAT=h\cdot t_{mem}+(1-h)(N\cdot t_{mem}+t_{mem})$

---

五、一句话记忆法

• 虚拟地址：你看到的地址都是假的，OS 在背后偷换
• TLB：地址翻译的"快速通道"，没它内存访问慢几倍
• 页表：虚拟→物理的"字典"，多级结构节省空间
• 换页：内存不够就借用磁盘，但代价极高（磁盘比内存慢 $10^5$ 倍）
• 最终哲学：理解机制，策略靠加钱（加内存）

并发入门 — 详细中文解析

原文来源：《操作系统：三大件》(OSTEP) 第25-26章 Concurrency: An Introduction

一、什么是并发？用桃子来理解

教授用一个生活场景打比方：

桌子上有很多桃子，很多人都想吃。每个人先用眼睛找到一个桃子，然后伸手去拿。
问题在哪？

• 你和另一个人同时看中了同一个桃子
• 对方先拿到了，你伸手扑了个空
• 这就是竞争条件（Race Condition）
  解决方案：排队
• 一次只让一个人上前拿桃子
• 正确了，但是慢了（串行化）
  理想目标：又快又正确
  这个桃子故事，其实已经把并发的核心问题说清楚了：

多线程 = 多人同时抢桃子 → 快，但可能出错
单线程 = 排队一个个来 → 正确，但慢
并发控制 = 用协调机制，既快又正确

二、线程是什么？

2.1 线程 vs 进程

传统进程：只有一个执行点（一个程序计数器 PC），同一时刻只执行一条指令序列。
线程：进程内的多个执行点，每个线程有自己的 PC，可以同时执行不同的代码路径。
关键区别：

比较项	进程	线程
地址空间	独立	共享同一个
寄存器	独立	独立（每线程一套）
栈	一个	每线程一个独立的栈
切换开销	大（需换页表）	小（不换页表）
数据共享	困难（需IPC）	容易（共享全局变量）

---

2.2 线程的地址空间布局

单线程进程：

高地址
+------------------+
|      Stack       |  ← 栈（向下增长）
+------------------+
|    (空闲空间)    |
+------------------+
|      Heap        |  ← 堆（向上增长）
+------------------+
|   Program Code   |  ← 代码段
+------------------+
低地址

双线程进程：

高地址
+------------------+
|    Stack (T2)    |  ← 线程2的栈
+------------------+
|    (空闲空间)    |
+------------------+
|    Stack (T1)    |  ← 线程1的栈
+------------------+
|    (空闲空间)    |
+------------------+
|      Heap        |  ← 两个线程共享同一个堆！
+------------------+
|   Program Code   |  ← 两个线程共享同一份代码！
+------------------+
低地址

注意：堆和全局变量是共享的，这既是线程的优势（方便共享数据），也是麻烦的根源（容易出冲突）。

2.3 线程切换与 TCB

线程切换时，OS 要保存当前线程的寄存器状态到线程控制块（TCB, Thread Control Block），再恢复下一个线程的状态。
与进程切换的区别：不需要切换页表，因为同一进程内所有线程共用同一地址空间，切换更快。

三、为什么要用线程？

原因一：并行利用多核 CPU

设有 $N$ 个 CPU 核，将一个耗时 $T$ 的任务分给 $N$ 个线程：
$$理论加速比=\frac{T}{T/N}=N$$
（实际受 Amdahl 定律限制，串行部分会成为瓶颈）
例子：对一个大数组的每个元素加 1，单线程需要全部自己做，多线程可以每个核处理一段，大幅加速。

原因二：避免 I/O 阻塞浪费 CPU

单线程程序：
  [计算] → [等待磁盘I/O，CPU空闲] → [计算] → [等待网络，CPU空闲] → ...
多线程程序：
  线程A: [计算] → [等待I/O，挂起]
  线程B:               [计算] → [等待I/O，挂起]
  线程C:                             [计算] ...
  CPU始终有事可做！

这就是 Web 服务器、数据库等服务器软件大量使用线程的原因。

四、线程创建示例（完整可运行 C 代码）

原书代码经过补全，以下是完整可运行版本：

/*
 * 示例1：创建两个线程，分别打印 "A" 和 "B"
 *
 * 编译命令：gcc -o thread_demo thread_demo.c -lpthread
 * 运行命令：./thread_demo
 *
 * 注意：输出顺序不固定，A和B谁先谁后取决于调度器
 */
#include <stdio.h>      /* printf */
#include <stdlib.h>     /* exit */
#include <pthread.h>    /* pthread_t, pthread_create, pthread_join */
/*
 * 线程执行的函数
 * 参数：arg 是 void* 类型，这里传入的是字符串 "A" 或 "B"
 * 返回：NULL（线程结束）
 */
void *mythread(void *arg) {
    /* 将 void* 强制转换回 char*，打印线程标识 */
    printf("%s\n", (char *)arg);
    return NULL;
}
int main(int argc, char *argv[]) {
    pthread_t p1, p2;   /* 线程句柄，用于标识两个线程 */
    int rc;             /* 返回值，用于检查错误 */
    printf("main: begin\n");
    /* 创建线程1，执行 mythread 函数，传入参数 "A" */
    rc = pthread_create(&p1, NULL, mythread, "A");
    if (rc != 0) {
        fprintf(stderr, "pthread_create failed\n");
        exit(1);
    }
    /* 创建线程2，执行 mythread 函数，传入参数 "B" */
    rc = pthread_create(&p2, NULL, mythread, "B");
    if (rc != 0) {
        fprintf(stderr, "pthread_create failed\n");
        exit(1);
    }
    /*
     * pthread_join：等待指定线程结束
     * 如果不 join，主线程可能先退出，导致子线程被强制终止
     */
    rc = pthread_join(p1, NULL);
    if (rc != 0) { fprintf(stderr, "pthread_join failed\n"); exit(1); }
    rc = pthread_join(p2, NULL);
    if (rc != 0) { fprintf(stderr, "pthread_join failed\n"); exit(1); }
    printf("main: end\n");
    return 0;
}

https://godbolt.org/z/4cjx7sTb8

三种可能的输出顺序

调度器可以以任意顺序运行线程，以下三种执行顺序都合法：
情况1（最常见直觉）：

main → 创建T1 → 创建T2 → T1打印A → T2打印B → main结束
时间轴：
main:  [begin][create T1][create T2][join T1等待][join T2等待][end]
T1:                           [打印A][结束]
T2:                                       [打印B][结束]
输出：
main: begin
A
B
main: end

情况2（T1创建后立即运行）：

时间轴：
main:  [begin][create T1]          [create T2][join...][end]
T1:                  [打印A][结束]
T2:                                    [打印B][结束]
输出：
main: begin
A
B
main: end

情况3（T2先于T1运行）：

时间轴：
main:  [begin][create T1][create T2][join...][end]
T1:                                    [打印A][结束]
T2:                          [打印B][结束]
输出：
main: begin
B
A
main: end

结论：线程的执行顺序是不确定的，程序员不能依赖某种特定顺序。

五、共享数据的问题：竞争条件

5.1 问题代码（完整可运行 C 代码）

/*
 * 示例2：两个线程共同对同一个计数器加 1000万次
 * 预期结果：counter = 20,000,000
 * 实际结果：每次运行都不同，且往往小于 20,000,000！
 *
 * 编译：gcc -o counter_race counter_race.c -lpthread
 * 运行：./counter_race
 */
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
/*
 * volatile 关键字：告诉编译器不要把 counter 缓存到寄存器
 * 每次访问都必须真正读写内存
 * （但这并不能解决竞争条件！）
 */
static volatile int counter = 0;
/*
 * 每个线程执行的函数：循环 1000万次，每次给 counter 加 1
 */
void *mythread(void *arg) {
    int i;
    printf("%s: begin\n", (char *)arg);
    for (i = 0; i < 10000000; i++) {
        /*
         * 这一行看起来简单，实际上被编译成三条汇编指令：
         *   1. 从内存读 counter 到寄存器（mov）
         *   2. 寄存器加 1（add）
         *   3. 把寄存器写回内存（mov）
         * 这三步不是原子的，中间可能被打断！
         */
        counter = counter + 1;
    }
    printf("%s: done\n", (char *)arg);
    return NULL;
}
int main(int argc, char *argv[]) {
    pthread_t p1, p2;
    printf("main: begin (counter = %d)\n", counter);
    pthread_create(&p1, NULL, mythread, "A");
    pthread_create(&p2, NULL, mythread, "B");
    pthread_join(p1, NULL);
    pthread_join(p2, NULL);
    /* 预期输出 20000000，但实际往往是一个更小的随机数 */
    printf("main: done with both (counter = %d)\n", counter);
    return 0;
}

https://godbolt.org/z/3zGaEM31n
典型输出（每次不同）：

main: begin (counter = 0)
A: begin
B: begin
A: done
B: done
main: done with both (counter = 19345221)   ← 少了！
再运行一次：
main: done with both (counter = 19221041)   ← 每次都不同！

5.2 为什么会出错？深入分析

counter = counter + 1 这一行 C 代码，编译后变成三条 x86 汇编指令：

; 假设 counter 变量在内存地址 0x8049a1c
mov  0x8049a1c, %eax    ; 第1步：从内存读 counter 的值，放入寄存器 eax
add  $0x1,      %eax    ; 第2步：寄存器 eax 加 1
mov  %eax,  0x8049a1c   ; 第3步：把 eax 的值写回内存

这三步不是一个整体，操作系统的定时中断可以在任意两步之间打断线程。

5.3 竞争条件的完整时序演示

设 counter 初始值为 50，两个线程同时执行：

时间 | 线程1（T1）              | 线程2（T2）              | counter内存值 | T1的eax | T2的eax
-----|--------------------------|--------------------------|--------------|---------|--------
  1  | mov 0x..., %eax          |                          |     50       |   50    |   -
  2  | add $1, %eax             |                          |     50       |   51    |   -
  3  | [定时中断！保存T1状态]    |                          |     50       |   51    |   -
  4  |                          | mov 0x..., %eax          |     50       |   51    |   50
  5  |                          | add $1, %eax             |     50       |   51    |   51
  6  |                          | mov %eax, 0x...          |     51       |   51    |   51
  7  |                          | [中断，恢复T1]           |     51       |   51    |   51
  8  | mov %eax, 0x...          |                          |     51       |   51    |   51
     | (T1的eax还是51，覆盖了!)  |                          |              |         |

结果：counter = 51，但两个线程各自+1，正确结果应该是 52！
丢失了一次加法操作，这就叫**“更新丢失”（Lost Update）**。
用 Mermaid 图表示这个时序：

六、核心概念定义

6.1 临界区（Critical Section）

定义： 访问共享资源（变量、数据结构等）的那段代码。

/* 以下就是一个临界区 */
counter = counter + 1;   /* 访问共享变量 counter */

要求： 同一时刻，最多只能有一个线程在临界区内执行。

6.2 竞争条件（Race Condition）

定义： 程序的运行结果依赖于多个线程的执行顺序，结果不可预测。
用公式表达：若线程 $T_1$ 和 $T_2$ 都执行操作 $op(x)$，但没有同步，则：
$$result=f(执行顺序)$$
执行顺序是随机的，所以 $result$ 也是随机的。

6.3 不确定性（Indeterminate）

定义： 程序多次运行输出不同结果，无法预测。这与计算机通常给我们的"确定性"预期相反。

6.4 互斥（Mutual Exclusion）

定义： 保证同一时刻最多一个线程进入临界区的机制。

互斥 = 门上的锁
临界区 = 门里的资源
只有拿到锁的线程才能进门
出来时还锁

这四个概念由 Edsger Dijkstra（1968年图灵奖得主）在1960年代提出，是并发领域的奠基性工作。

七、原子操作：解决之道

7.1 为什么需要原子操作

问题根源：counter++ 不是原子的，它是三步操作，中间可能被打断。
**原子（Atomic）**的含义：“全部完成，或者全部不做”，没有中间状态。
如果硬件能提供一条原子的"内存加法"指令：

; 假设有这样一条原子指令（x86 实际有 LOCK 前缀）
memory-add 0x8049a1c, $0x1   ; 原子地：读-加-写，不可被打断

那么竞争条件就消失了，因为这三步变成了硬件保证的"一步"。

7.2 现实中的同步原语

现实中不可能对所有操作都有专用原子指令（比如原子更新 B 树？不现实）。
所以 OS 和硬件提供同步原语（Synchronization Primitives），常见的有：

使用互斥锁修复计数器问题（预告）：

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;  /* 定义一把锁 */
void *mythread(void *arg) {
    int i;
    for (i = 0; i < 10000000; i++) {
        pthread_mutex_lock(&lock);    /* 加锁：进入临界区 */
        counter = counter + 1;        /* 临界区：只有一个线程能在这里 */
        pthread_mutex_unlock(&lock);  /* 解锁：离开临界区 */
    }
    return NULL;
}

加了锁之后，结果永远是正确的 20,000,000。代价是性能下降（因为串行化了临界区）。

八、另一个问题：线程间等待

除了保护共享数据，线程间还有另一种交互：一个线程需要等另一个线程完成某件事才能继续。
例子：

线程A（磁盘读取线程）：发起磁盘读取 → 等待完成 → 通知线程B
线程B（数据处理线程）：等待线程A读完 → 处理数据

这用**条件变量（Condition Variable）**来实现，后续章节会详细讲。

九、为什么在操作系统课讲并发？

历史原因：OS 是第一个并发程序。
OS 本身处理中断，多个进程同时运行时，OS 的内核数据结构（页表、进程列表、文件系统结构等）都是共享的，必须小心保护。
具体例子： 两个进程同时调用 write() 写同一个文件

进程A：找空闲块 → [中断！] → 进程B也找到同一个"空闲"块
→ 两个进程写同一块，数据互相覆盖！

这就是为什么内核代码里到处都是锁——从最一开始设计中断机制时，OS 设计者就必须考虑并发问题。

十、整体知识框架

十一、关键术语速查

---

术语	英文	一句话解释
线程	Thread	进程内的一个执行流，共享地址空间
线程控制块	TCB	存储线程寄存器状态的数据结构
竞争条件	Race Condition	结果取决于执行顺序的 bug
临界区	Critical Section	访问共享资源的代码段
互斥	Mutual Exclusion	同一时刻只有一个线程能进临界区
不确定性	Indeterminate	多次运行结果不同，无法预测
原子操作	Atomic Operation	不可被打断的操作，“全做或全不做”
同步原语	Sync Primitive	实现线程协调的基础工具（锁、信号量等）

---

十二、一句话总结

• 线程：进程内的多个执行流，共享内存，创建和切换比进程轻量
• 为什么用：利用多核并行、避免 I/O 阻塞
• 为什么麻烦：共享内存 + 非原子操作 = 竞争条件 = 结果随机
• 解决方向：用同步原语（锁、条件变量）保证互斥和有序协作
• 核心矛盾：并发带来性能，同步带来正确性，二者之间需要权衡

线程 API 详解 — 详细中文解析

原文来源：《操作系统：三大件》(OSTEP) 第27章 Interlude: Thread API

一、整体概览

本章是 POSIX 线程（pthread）API 的使用指南，涵盖四大核心功能：

pthread API
├── 线程创建   pthread_create()
├── 线程等待   pthread_join()
├── 互斥锁     pthread_mutex_lock() / unlock()
└── 条件变量   pthread_cond_wait() / signal()

编译所有多线程程序都需要加 -pthread 链接标志：

gcc -o main main.c -Wall -pthread

二、线程创建：pthread_create

2.1 函数原型解析

int pthread_create(
    pthread_t            *thread,        /* 输出：线程句柄 */
    const pthread_attr_t *attr,          /* 输入：线程属性（通常传NULL） */
    void *(*start_routine)(void *),      /* 输入：线程执行的函数指针 */
    void                 *arg            /* 输入：传给函数的参数 */
);

逐参数说明：

参数1 thread      ← 传入一个 pthread_t 变量的地址，函数会填充它
                    之后用这个句柄来 join 或控制线程
参数2 attr        ← 线程属性（栈大小、调度优先级等）
                    绝大多数情况传 NULL，使用默认值即可
参数3 start_routine ← 函数指针，新线程从这个函数开始执行
                      签名必须是：void* func(void* arg)
参数4 arg         ← 传给 start_routine 的参数
                    类型是 void*，可以传任何类型（强制转换）

2.2 函数指针的三种形态

根据线程函数的参数和返回值类型，函数指针写法不同：

/* 形态1（标准形态）：参数 void*，返回 void* */
void *(*start_routine)(void *);
/* 形态2：参数 int，返回 void* */
void *(*start_routine)(int);
/* 形态3：参数 void*，返回 int */
int (*start_routine)(void *);

为什么统一用 void*？

• void* 可以转换成任何指针类型，相当于 C 语言里的"万能指针"
• 这样线程函数可以接受和返回任意类型的数据，只需在内部做强制转换

2.3 传递多个参数（完整可运行代码）

/*
 * 示例：通过结构体向线程传递多个参数
 *
 * 编译：gcc -o thread_args thread_args.c -lpthread
 * 运行：./thread_args
 * 预期输出：10 20
 */
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
/*
 * 自定义参数结构体
 * 把需要传给线程的多个参数打包成一个结构体，
 * 再把结构体地址转成 void* 传进去
 */
typedef struct {
    int a;  /* 第一个参数 */
    int b;  /* 第二个参数 */
} myarg_t;
/*
 * 线程函数：接收 void* 参数，内部转换回 myarg_t*
 */
void *mythread(void *arg) {
    /* 将 void* 强制转换回我们实际传入的类型 */
    myarg_t *args = (myarg_t *)arg;
    /* 现在可以正常使用结构体的成员 */
    printf("%d %d\n", args->a, args->b);
    return NULL;  /* 线程正常结束，不返回有意义的值 */
}
int main(int argc, char *argv[]) {
    pthread_t p;                    /* 线程句柄 */
    myarg_t args = { 10, 20 };     /* 初始化参数结构体 */
    int rc;
    /* 创建线程，传入结构体地址（转成 void*） */
    rc = pthread_create(&p, NULL, mythread, &args);
    if (rc != 0) {
        fprintf(stderr, "pthread_create 失败\n");
        exit(1);
    }
    /* 等待线程结束（暂时不取返回值） */
    rc = pthread_join(p, NULL);
    if (rc != 0) {
        fprintf(stderr, "pthread_join 失败\n");
        exit(1);
    }
    return 0;
}

https://godbolt.org/z/jzcx41xz3

三、线程等待：pthread_join

3.1 函数原型

int pthread_join(
    pthread_t   thread,      /* 要等待的线程句柄 */
    void      **value_ptr    /* 输出：接收线程的返回值（可传NULL） */
);

注意 value_ptr 是指向指针的指针（void**），原因：

• 线程函数返回 void*（一个指针）
• pthread_join 需要修改调用方的那个 void* 变量
• 修改变量需要传变量的地址，所以是 void**

3.2 接收线程返回值（完整可运行代码）

/*
 * 示例：线程通过堆内存返回多个值
 *
 * 编译：gcc -o thread_return thread_return.c -lpthread
 * 运行：./thread_return
 * 预期输出：returned 1 2
 *
 * 重点：返回值必须分配在堆上（malloc），不能是栈上的局部变量！
 */
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
typedef struct { int a; int b; } myarg_t;
typedef struct { int x; int y; } myret_t;  /* 返回值结构体 */
void *mythread(void *arg) {
    /*
     * 用 malloc 在堆上分配返回值结构体
     * 堆上的内存在函数返回后依然存在，主线程可以安全读取
     *
     * 注意：调用方（main）负责 free 这块内存！
     */
    myret_t *rvals = (myret_t *)malloc(sizeof(myret_t));
    if (rvals == NULL) {
        fprintf(stderr, "malloc 失败\n");
        return NULL;
    }
    rvals->x = 1;
    rvals->y = 2;
    /* 将堆上的指针转成 void* 返回 */
    return (void *)rvals;
}
int main(int argc, char *argv[]) {
    pthread_t p;
    myret_t *rvals;           /* 用于接收线程返回的指针 */
    myarg_t args = { 10, 20 };
    int rc;
    rc = pthread_create(&p, NULL, mythread, &args);
    if (rc != 0) { fprintf(stderr, "create 失败\n"); exit(1); }
    /*
     * pthread_join 的第二个参数是 void**
     * 我们有一个 myret_t* 变量 rvals，传入它的地址 &rvals
     * join 结束后，rvals 就指向线程返回的堆内存
     */
    rc = pthread_join(p, (void **)&rvals);
    if (rc != 0) { fprintf(stderr, "join 失败\n"); exit(1); }
    printf("returned %d %d\n", rvals->x, rvals->y);
    free(rvals);   /* 记得释放线程分配的堆内存！ */
    return 0;
}

https://godbolt.org/z/5ehq8M7b8

3.3 传递简单值（不用结构体）

当参数和返回值都是简单整数时，可以直接把整数强转成 void* 传递：

/*
 * 示例：直接用 void* 传递整数值（适合简单场景）
 *
 * 编译：gcc -o thread_simple thread_simple.c -lpthread
 * 运行：./thread_simple
 * 预期输出：
 *   100
 *   returned 101
 *
 * 原理：long long int 和指针在64位系统上都是8字节，可以互转
 */
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
void *mythread(void *arg) {
    /* 把 void* 强转回 long long int（注意：是值，不是指针！） */
    long long int value = (long long int)arg;
    printf("%lld\n", value);
    /* 把返回值（整数+1）转成 void* 返回 */
    return (void *)(value + 1);
}
int main(int argc, char *argv[]) {
    pthread_t p;
    long long int rvalue;   /* 接收返回值 */
    int rc;
    /* 直接把整数 100 转成 void* 传入 */
    rc = pthread_create(&p, NULL, mythread, (void *)100);
    if (rc != 0) { fprintf(stderr, "create 失败\n"); exit(1); }
    rc = pthread_join(p, (void **)&rvalue);
    if (rc != 0) { fprintf(stderr, "join 失败\n"); exit(1); }
    printf("returned %lld\n", rvalue);
    return 0;
}

https://godbolt.org/z/nbx5PGv9b

3.4 绝对不能做的事：返回栈上的指针

/*
 * 错误示例（不要运行！仅作说明）
 * 这段代码有未定义行为：返回了指向已销毁栈帧的指针
 */
void *mythread(void *arg) {
    myret_t oops;    /* 分配在栈上！函数返回后这块内存被回收 */
    oops.x = 1;
    oops.y = 2;
    return (void *)&oops;   /* 危险！返回了一个"悬空指针" */
}

内存示意图，展示为何危险：

线程函数运行时：
栈帧（mythread）:
  +----------+
  | oops.x=1 |  ← &oops 指向这里
  | oops.y=2 |
  +----------+
  | 返回地址 |
  +----------+
线程函数返回后，栈帧被回收：
  +----------+
  | ???????? |  ← 内存已被其他用途覆盖！
  | ???????? |    但 &oops 还指向这里
  +----------+
主线程读取 rvals->x 时：读到的是垃圾值，甚至可能崩溃

规则：跨线程传递数据，必须用堆（malloc）或全局变量，绝不能用局部变量的地址。

四、互斥锁：Mutex

4.1 基本用法

/*
 * 互斥锁使用模板
 *
 * 锁的核心语义：
 *   lock()  → 如果锁空闲，则获取锁，继续执行
 *              如果锁被占用，则阻塞等待，直到锁被释放
 *   unlock() → 释放锁，唤醒等待的线程
 */
pthread_mutex_t lock;  /* 声明一把锁 */
pthread_mutex_lock(&lock);   /* 加锁（进入临界区） */
x = x + 1;                  /* 临界区：同时只有一个线程在这里 */
pthread_mutex_unlock(&lock); /* 解锁（离开临界区） */

4.2 锁的初始化：两种方式

/* 方式1：静态初始化（编译时，适合全局变量） */
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
/* 方式2：动态初始化（运行时，适合动态分配的场景） */
pthread_mutex_t lock;
int rc = pthread_mutex_init(&lock, NULL);  /* 第二个参数NULL用默认属性 */
if (rc != 0) {
    /* 初始化失败，必须处理！ */
    fprintf(stderr, "mutex init 失败\n");
    exit(1);
}
/* ... 使用锁 ... */
pthread_mutex_destroy(&lock);  /* 用完必须销毁，释放资源 */

4.3 其他锁操作

/* trylock：尝试加锁，加不上立即返回失败（不阻塞） */
int rc = pthread_mutex_trylock(&lock);
if (rc == 0) {
    /* 成功获取锁 */
} else {
    /* 锁被占用，可以做其他事情再试 */
}
/* timedlock：最多等 abs_timeout 时间，超时返回失败 */
struct timespec timeout;
timeout.tv_sec = time(NULL) + 1;  /* 等待1秒 */
timeout.tv_nsec = 0;
int rc = pthread_mutex_timedlock(&lock, &timeout);

4.4 完整的计数器修复示例（完整可运行代码）

/*
 * 用互斥锁修复上一章的竞争条件
 *
 * 编译：gcc -o counter_fixed counter_fixed.c -lpthread
 * 运行：./counter_fixed
 * 预期输出：counter = 20000000（每次都正确）
 *
 * 注意：加锁后正确，但比无锁版本慢很多（因为临界区串行化了）
 */
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
static int counter = 0;
/*
 * 全局互斥锁：保护 counter
 * 静态初始化，简单方便
 */
static pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
/*
 * 包装函数：调用 lock/unlock 并检查返回值
 * 生产代码中应该这样做，而不是忽略返回值
 */
void safe_lock(pthread_mutex_t *m) {
    int rc = pthread_mutex_lock(m);
    if (rc != 0) {
        fprintf(stderr, "mutex lock 失败: %d\n", rc);
        exit(1);
    }
}
void safe_unlock(pthread_mutex_t *m) {
    int rc = pthread_mutex_unlock(m);
    if (rc != 0) {
        fprintf(stderr, "mutex unlock 失败: %d\n", rc);
        exit(1);
    }
}
void *mythread(void *arg) {
    int i;
    printf("%s: begin\n", (char *)arg);
    for (i = 0; i < 10000000; i++) {
        safe_lock(&lock);       /* 加锁：只有我能进临界区 */
        counter = counter + 1;  /* 临界区：安全地修改共享变量 */
        safe_unlock(&lock);     /* 解锁：让其他线程有机会进来 */
    }
    printf("%s: done\n", (char *)arg);
    return NULL;
}
int main(int argc, char *argv[]) {
    pthread_t p1, p2;
    printf("main: begin (counter = %d)\n", counter);
    pthread_create(&p1, NULL, mythread, "A");
    pthread_create(&p2, NULL, mythread, "B");
    pthread_join(p1, NULL);
    pthread_join(p2, NULL);
    /* 每次都输出正确结果 20000000 */
    printf("main: done with both (counter = %d)\n", counter);
    return 0;
}

https://godbolt.org/z/v7q6jEqhf

五、条件变量：Condition Variable

5.1 解决什么问题？

互斥锁解决的是"保护共享数据"的问题。
条件变量解决的是"线程间等待与通知"的问题：

场景：线程B需要等线程A完成某件事之后才能继续
错误做法（忙等/自旋）：
  while (ready == 0)
      ;    // 死循环检查，浪费CPU！
正确做法（条件变量）：
  线程B：检查条件 → 条件不满足 → 睡眠（释放CPU）
  线程A：完成任务 → 发送信号 → 唤醒线程B

5.2 函数原型

/* 等待：调用线程睡眠，同时释放 mutex，等待被 signal 唤醒 */
int pthread_cond_wait(
    pthread_cond_t  *cond,   /* 条件变量 */
    pthread_mutex_t *mutex   /* 与条件变量配套的锁 */
);
/* 通知：唤醒至少一个正在等待该条件变量的线程 */
int pthread_cond_signal(pthread_cond_t *cond);

5.3 使用模式（生产者-消费者）

等待方（消费者线程）：
  1. 加锁
  2. while (条件不满足) → 调用 wait（自动释放锁+睡眠）
  3. 被唤醒时 wait 自动重新加锁
  4. 执行任务
  5. 解锁
通知方（生产者线程）：
  1. 加锁
  2. 修改条件（让条件变为满足）
  3. 调用 signal（唤醒等待的线程）
  4. 解锁

为什么用 while 而不是 if？

• 某些 pthread 实现存在"虚假唤醒（Spurious Wakeup）"：线程可能在没有 signal 的情况下被唤醒
• 用 while 确保醒来后重新检查条件，如果条件仍不满足就继续睡

5.4 完整示例：父线程等待子线程完成（完整可运行代码）

/*
 * 示例：用条件变量实现"父等子"
 *
 * 编译：gcc -o cond_demo cond_demo.c -lpthread
 * 运行：./cond_demo
 * 预期输出：
 *   parent: begin
 *   child: running
 *   child: done, signaling parent
 *   parent: woke up, child is done
 */
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
/* 共享状态：子线程是否完成 */
static int done = 0;
/* 条件变量和配套的锁（必须一起使用！） */
static pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t  cond = PTHREAD_COND_INITIALIZER;
void *child(void *arg) {
    printf("child: running\n");
    /* 模拟一些工作 */
    int i;
    for (i = 0; i < 100000000; i++)
        ;  /* 空循环消耗时间 */
    /* 通知父线程：我完成了 */
    pthread_mutex_lock(&lock);    /* 修改共享变量前必须加锁 */
    done = 1;                     /* 设置完成标志 */
    pthread_cond_signal(&cond);   /* 唤醒等待的父线程 */
    pthread_mutex_unlock(&lock);  /* 解锁 */
    printf("child: done, signaling parent\n");
    return NULL;
}
int main(int argc, char *argv[]) {
    pthread_t p;
    printf("parent: begin\n");
    pthread_create(&p, NULL, child, NULL);
    /*
     * 父线程等待子线程完成
     * 必须用 while，不能用 if（防止虚假唤醒）
     */
    pthread_mutex_lock(&lock);       /* 加锁后才能检查条件 */
    while (done == 0) {
        /*
         * pthread_cond_wait 做三件事：
         *   1. 原子地释放 lock（让子线程有机会加锁）
         *   2. 把父线程挂起（不占CPU）
         *   3. 被唤醒后，重新获取 lock，再返回
         */
        pthread_cond_wait(&cond, &lock);
    }
    pthread_mutex_unlock(&lock);     /* 解锁 */
    printf("parent: woke up, child is done\n");
    pthread_join(p, NULL);
    return 0;
}

https://godbolt.org/z/oEeWbGzsq

5.5 条件变量 vs 自旋等待对比

自旋等待（错误做法）：
  while (ready == 0)
      ;   ← CPU 100% 占用，纯浪费
  问题：
  - 浪费 CPU 资源
  - 可能导致持锁线程无法运行（CPU 被等待者占满）
  - 代码难以正确实现（研究表明约50%的临时同步代码有 bug）
条件变量（正确做法）：
  while (ready == 0)
      pthread_cond_wait(&cond, &lock);  ← 睡眠，不占CPU
  优势：
  - 等待期间线程挂起，CPU 可以做其他事
  - 原子地释放锁+睡眠，避免信号丢失
  - 经过验证的标准模式，可靠性高

六、完整流程图

6.1 pthread_cond_wait 内部机制

调用线程                     其他线程
    |
    | lock(&mutex)
    |
    | while (条件不满足)
    |   cond_wait(&cond, &mutex)
    |       |
    |       +--- 原子操作 ---+
    |       | 1.释放 mutex   |
    |       | 2.线程挂起     |       lock(&mutex)
    |       |               |       修改共享状态
    |       |               |       cond_signal(&cond)
    |       |               |       unlock(&mutex)
    |       |               |
    |       | 3.被唤醒       |
    |       | 4.重新获取mutex|
    |       +----------------+
    |   （while 重新检查条件）
    |
    | unlock(&mutex)

6.2 线程 API 整体流程

七、编程规范：避免常见错误

7.1 常见错误及修复

错误1：忘记初始化锁

/* 错误：未初始化就使用 */
pthread_mutex_t lock;
pthread_mutex_lock(&lock);   /* 未定义行为！ */
/* 正确：静态初始化 */
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
/* 或者动态初始化 */
pthread_mutex_t lock;
pthread_mutex_init(&lock, NULL);

错误2：不检查返回值

/* 错误：忽略返回值，失败时静默继续 */
pthread_mutex_lock(&lock);  /* 如果失败，多个线程都进了临界区！ */
/* 正确：检查每个调用的返回值 */
int rc = pthread_mutex_lock(&lock);
if (rc != 0) {
    fprintf(stderr, "lock 失败: %d\n", rc);
    exit(1);
}

错误3：返回栈上的指针

/* 错误：oops 在栈上，函数返回后销毁 */
myret_t oops;
return (void *)&oops;   /* 悬空指针！ */
/* 正确：用 malloc 在堆上分配 */
myret_t *result = malloc(sizeof(myret_t));
return (void *)result;  /* 堆上的内存持续存在 */

错误4：用自旋替代条件变量

/* 错误：忙等待，浪费CPU */
while (ready == 0)
    ;
/* 正确：条件变量 */
while (ready == 0)
    pthread_cond_wait(&cond, &lock);

7.2 编程准则速查

---

准则	说明
保持简单	锁和信号的逻辑越简单越好，复杂的线程交互容易出 bug
最小化交互	减少线程间共享数据的数量，降低出错概率
始终初始化	锁和条件变量使用前必须初始化
检查返回值	每个 pthread 函数都可能失败，不能忽略
堆上传值	跨线程传数据用堆或全局，绝不用栈上局部变量地址
每线程独立栈	线程的局部变量对其他线程不可见
用条件变量	线程间等待通知，永远用条件变量，不用自旋标志
用 while 检查	等待条件变量时，用 while 而不是 if

---

八、工具推荐：Helgrind

Helgrind 是 Valgrind 工具集中专门检测线程错误的工具，能发现：

• 数据竞争（Race Condition）
• 锁的使用错误
• 死锁（Deadlock）
  使用方法：

# 编译时加调试信息
gcc -g -o main main.c -lpthread
# 用 helgrind 运行
valgrind --tool=helgrind ./main

九、知识结构总览

POSIX 线程 API
│
├── pthread_create()     创建线程
│     ├── 参数：函数指针 + void* 参数
│     └── 用结构体打包多参数，void* 是万能载体
│
├── pthread_join()       等待线程结束 + 获取返回值
│     ├── 返回值必须在堆上分配
│     └── 不需要返回值时传 NULL
│
├── pthread_mutex_*      互斥锁（保护临界区）
│     ├── lock() / unlock() 基本操作
│     ├── trylock() 非阻塞尝试
│     ├── timedlock() 超时等待
│     └── 必须初始化，必须检查返回值
│
└── pthread_cond_*       条件变量（线程间等待通知）
      ├── wait()  睡眠 + 释放锁（原子）
      ├── signal() 唤醒一个等待者
      └── 等待时用 while 循环，防虚假唤醒

锁的实现原理 — 详细中文解析

原文来源：《操作系统：三大件》(OSTEP) 第28章 Locks

一、锁的基本概念

1.1 为什么需要锁？

上一章我们看到，balance = balance + 1 这样一行代码，实际上是三条汇编指令，中间可以被中断打断，导致结果错误。
锁（Lock）就是为了解决这个问题：把一段本来不原子的代码，包装成好像是原子执行的。

lock_t mutex;          /* 声明一把锁变量 */
lock(&mutex);          /* 加锁：进入临界区 */
balance = balance + 1; /* 临界区：此刻只有我在执行 */
unlock(&mutex);        /* 解锁：离开临界区 */

1.2 锁的状态

锁在任意时刻只有两种状态：

状态1：空闲（available / unlocked / free）
        → 没有线程持有这把锁
        → 任何调用 lock() 的线程都能立即获取
状态2：已持有（acquired / locked / held）
        → 恰好一个线程持有这把锁，正在临界区内
        → 其他调用 lock() 的线程必须等待

用 ASCII 状态机表示：

           lock() 调用，锁空闲
   [空闲] ─────────────────────→ [已持有]
     ↑                               |
     |         unlock() 调用         |
     └───────────────────────────────┘

1.3 锁的三个评价标准

---

标准	问题	说明
正确性	是否真正实现了互斥？	最基本要求，同时只有一个线程在临界区
公平性	每个等待的线程都能最终获取锁吗？	有无饥饿（starvation）现象
性能	使用锁带来多少额外开销？	分无竞争/单CPU竞争/多CPU竞争三种场景

---

二、方案一：关闭中断（最早期方案）

2.1 原理

在单处理器系统上，线程切换依赖定时中断。关掉中断，就没有调度，也就没有并发问题。

/*
 * 最早期的互斥方案：关闭中断
 * 只适用于单处理器系统，且只有OS内核自己用
 */
void lock() {
    DisableInterrupts();   /* 硬件特权指令：屏蔽所有中断 */
}
void unlock() {
    EnableInterrupts();    /* 硬件特权指令：重新允许中断 */
}

2.2 优缺点分析

优点： 实现极其简单，在单处理器上确实有效。
缺点（致命的）：

缺点1：需要信任应用程序
  恶意程序调用 lock() 后死循环 → OS 永远无法夺回 CPU → 只能重启
  贪婪程序在程序开始就加锁 → 独占处理器
缺点2：多处理器无效
  关掉 CPU1 的中断，但 CPU2 仍在运行
  另一个线程在 CPU2 上照样能进入临界区
缺点3：可能丢失中断
  磁盘读取完成的中断在屏蔽期间发生 → OS 不知道 → 进程永远等不到唤醒

结论： 关中断方案只在 OS 内核内部使用（内核信任自己），不对用户程序开放。

三、方案二：纯软件标志位（失败的尝试）

3.1 思路

用一个普通整数变量 flag 表示锁的状态，0 表示空闲，1 表示已持有。

/*
 * 失败的锁实现：用普通变量做标志
 * 这段代码有严重的竞争条件 BUG，仅作反面教材
 */
typedef struct {
    int flag;  /* 0: 锁空闲；1: 锁被持有 */
} lock_t;
void init(lock_t *mutex) {
    mutex->flag = 0;   /* 初始状态：空闲 */
}
void lock(lock_t *mutex) {
    /* 先测试（TEST）flag 是否为 1 */
    while (mutex->flag == 1)
        ;              /* 如果为 1，自旋等待（spin-wait） */
    /* 再设置（SET）flag 为 1 */
    mutex->flag = 1;   /* 声明"我拿到锁了" */
}
void unlock(lock_t *mutex) {
    mutex->flag = 0;   /* 释放锁 */
}

3.2 为什么失败？时序分析

关键问题："测试"和"设置"是两个分开的操作，中间可以被打断！

初始状态：flag = 0
时间 | 线程1                        | 线程2
-----|------------------------------|------------------------------
  1  | while(flag==1) → false，退出 |
  2  | [中断！切换到线程2]           |
  3  |                              | while(flag==1) → false，退出
  4  |                              | flag = 1  ← 线程2以为自己拿到锁了
  5  | [恢复线程1]                  |
  6  | flag = 1  ← 线程1也以为拿到锁|
  7  | 进入临界区！                  | 进入临界区！← 两个线程都进去了！

两个线程同时进入临界区，互斥失败！
还有另一个性能问题：自旋等待（Spin-wait），线程在 while 循环里空转，白白消耗 CPU。

四、方案三：Test-And-Set 硬件原子指令

4.1 硬件原语：TestAndSet

软件方案失败的根本原因："测试"和"设置"不是原子的。
硬件解决方案：提供一条能**原子地完成"测试+设置"**的指令：

/*
 * TestAndSet 的 C 语言伪代码
 * 实际上这是一条硬件指令，执行时不可被打断
 *
 * 功能：原子地把 *old_ptr 的值设为 new，并返回旧值
 * x86 对应指令：xchg（exchange，锁总线保证原子性）
 * SPARC 对应指令：ldstub
 */
int TestAndSet(int *old_ptr, int new) {
    int old = *old_ptr;   /* 读取旧值 */
    *old_ptr = new;        /* 写入新值 */
    return old;            /* 返回旧值 */
    /* 以上三步由硬件保证原子执行，中间不可被打断 */
}

4.2 基于 TestAndSet 的自旋锁

/*
 * 自旋锁（Spin Lock）实现
 * 使用 TestAndSet 硬件原语，正确实现了互斥
 *
 * 工作原理：
 *   TestAndSet(&flag, 1) 原子地：
 *     - 读出 flag 的旧值
 *     - 把 flag 设为 1
 *     - 返回旧值
 *
 *   如果旧值是 0（锁空闲）→ 我成功获取了锁，退出循环
 *   如果旧值是 1（锁已持有）→ 继续自旋
 */
typedef struct {
    int flag;
} lock_t;
void init(lock_t *lock) {
    lock->flag = 0;   /* 0: 空闲 */
}
void lock(lock_t *lock) {
    /*
     * TestAndSet 把 flag 设为 1，返回旧值
     * 如果旧值是 1（别人持有锁）→ while 条件为真 → 继续自旋
     * 如果旧值是 0（锁空闲）→ while 条件为假 → 成功获取锁，退出
     */
    while (TestAndSet(&lock->flag, 1) == 1)
        ;  /* 自旋等待 */
}
void unlock(lock_t *lock) {
    lock->flag = 0;   /* 释放锁：把 flag 清零 */
}

4.3 为什么这次正确？

两个线程同时调用 lock()：

初始：flag = 0
线程1 调用 TestAndSet(&flag, 1)：
  → 原子地读出 flag=0，写入 flag=1，返回 0
  → while(0==1) 为假，线程1获取锁，进入临界区 ✓
线程2（同时或稍后）调用 TestAndSet(&flag, 1)：
  → 原子地读出 flag=1，写入 flag=1（不变），返回 1
  → while(1==1) 为真，线程2自旋等待 ✓
线程1 unlock()：flag = 0
线程2 再次 TestAndSet(&flag, 1)：
  → 读出 flag=0，写入 flag=1，返回 0
  → while(0==1) 为假，线程2获取锁 ✓

关键：两个线程不可能同时拿到旧值 0，因为 TestAndSet 是原子的。

4.4 自旋锁评价

---

标准	评价
正确性	正确，真正实现了互斥
公平性	不公平，可能有线程永远自旋（饥饿）
性能（单CPU）	差，持锁线程被抢占时，其他 $N-1$ 个线程白白自旋整个时间片
性能（多CPU）	尚可，临界区短时，等待时间短，自旋开销有限

---

单CPU 情况下，设有 $N$ 个线程，持锁线程被抢占后：
$$浪费的时间片数=N-1$$
每个等待线程都要白白运行一整个时间片，只做自旋，什么也不做。

五、方案四：Compare-And-Swap（比较并交换）

5.1 硬件原语

/*
 * Compare-And-Swap (CAS) 的 C 语言伪代码
 * x86 对应指令：cmpxchg（compare and exchange）
 *
 * 功能：如果 *ptr 等于 expected，则把 *ptr 设为 new，返回原始值
 *       如果不等于，不做任何修改，直接返回原始值
 * 调用方通过判断返回值是否等于 expected，来知道是否成功
 */
int CompareAndSwap(int *ptr, int expected, int new) {
    int original = *ptr;          /* 读取当前值 */
    if (original == expected)     /* 如果当前值等于预期值 */
        *ptr = new;               /* 才更新为新值 */
    return original;              /* 总是返回原始值 */
}

5.2 用 CAS 实现锁

void lock(lock_t *lock) {
    /*
     * 期望 flag 是 0（空闲），如果是就设为 1（获取锁）
     * 返回值：
     *   返回 0 → 说明之前是空闲的，我成功拿到锁
     *   返回 1 → 锁已被占用，继续自旋
     */
    while (CompareAndSwap(&lock->flag, 0, 1) == 1)
        ;  /* 自旋 */
}

CAS 比 TAS 更强大，可以用来实现无锁数据结构（Lock-Free），后续章节会讲到。

六、方案五：Load-Linked / Store-Conditional（LL/SC）

6.1 硬件原语（MIPS、ARM、PowerPC 架构）

/*
 * Load-Linked（LL）：像普通 load 一样读内存，但同时记录这个地址
 * Store-Conditional（SC）：条件写入
 *   - 如果自从 LL 之后，该地址没有被其他人写过 → 写入成功，返回 1
 *   - 如果自从 LL 之后，该地址被写过（哪怕值相同）→ 写入失败，返回 0
 */
int LoadLinked(int *ptr) {
    return *ptr;          /* 读取值，同时标记这个地址正在被监视 */
}
int StoreConditional(int *ptr, int value) {
    if (/* 自从上次 LL 以来，*ptr 没有被其他线程写过 */) {
        *ptr = value;
        return 1;   /* 写入成功 */
    } else {
        return 0;   /* 写入失败，需要重试 */
    }
}

6.2 用 LL/SC 实现锁

void lock(lock_t *lock) {
    while (1) {
        /* 第一步：等待锁变为空闲（flag == 0） */
        while (LoadLinked(&lock->flag) == 1)
            ;  /* 锁被占用，自旋等待 */
        /* 第二步：尝试原子地获取锁 */
        if (StoreConditional(&lock->flag, 1) == 1)
            return;  /* SC 成功 → 我拿到锁了 */
        /* SC 失败 → 说明有其他线程也在抢，重新开始 */
    }
}
/* 简洁版（等价） */
void lock_concise(lock_t *lock) {
    /*
     * LoadLinked 返回 1（锁被占用）→ while 条件为真，继续
     * LoadLinked 返回 0（锁空闲）→ 尝试 SC
     *   SC 成功返回 1 → !1 = false → while 结束，获取锁
     *   SC 失败返回 0 → !0 = true → while 继续，重试
     */
    while (LoadLinked(&lock->flag) ||
           !StoreConditional(&lock->flag, 1))
        ;  /* 自旋 */
}
void unlock(lock_t *lock) {
    lock->flag = 0;
}

七、方案六：Fetch-And-Add + 票号锁（公平的自旋锁）

7.1 硬件原语：Fetch-And-Add

/*
 * FetchAndAdd：原子地把 *ptr 加 1，返回旧值
 * 相当于 (*ptr)++，但是原子的
 */
int FetchAndAdd(int *ptr) {
    int old = *ptr;
    *ptr = old + 1;
    return old;
}

7.2 票号锁（Ticket Lock）——解决饥饿问题

类比：银行排队叫号系统

• 进门时取一个号（my_turn = ticket++）
• 柜台显示屏显示当前服务号（turn）
• 当 my_turn == turn 时，轮到你了

/*
 * 票号锁（Ticket Lock）
 * 优点：公平！每个线程都按照取号顺序获取锁，不会饥饿
 *
 * 编译：gcc -o ticket_lock ticket_lock.c -lpthread
 */
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
/*
 * 票号锁结构体
 * ticket：下一个可分配的票号（原子递增）
 * turn：当前"叫到"的号码（轮到谁了）
 */
typedef struct {
    int ticket;   /* 分票计数器，原子递增 */
    int turn;     /* 当前服务号 */
} lock_t;
void lock_init(lock_t *lock) {
    lock->ticket = 0;
    lock->turn   = 0;
}
void lock(lock_t *lock) {
    /*
     * 原子取号：我的号码 = 当前 ticket 值，然后 ticket++
     * 无论多少线程同时调用，每人拿到的 myturn 都不同
     */
    int myturn = FetchAndAdd(&lock->ticket);
    /* 等待叫到我的号 */
    while (lock->turn != myturn)
        ;  /* 自旋等待 */
    /* 到这里说明轮到我了，进入临界区 */
}
void unlock(lock_t *lock) {
    /*
     * 叫下一个号：turn++
     * 下一个等待的线程发现 turn == myturn，退出自旋
     */
    lock->turn = lock->turn + 1;
}
/* ---- 演示使用 ---- */
static lock_t mylock;
static int counter = 0;
void *worker(void *arg) {
    int i;
    for (i = 0; i < 1000000; i++) {
        lock(&mylock);
        counter++;
        unlock(&mylock);
    }
    return NULL;
}
int main(void) {
    pthread_t t1, t2;
    lock_init(&mylock);
    pthread_create(&t1, NULL, worker, NULL);
    pthread_create(&t2, NULL, worker, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    printf("counter = %d (期望 2000000)\n", counter);
    return 0;
}

票号锁的公平性保证：一旦线程取到号，它一定会在有限时间内被叫到（按照取号顺序），不会被后来的线程"插队"。

八、自旋锁的性能问题与改进

8.1 自旋的代价

设 $N$ 个线程竞争，锁持有线程 T0 被抢占，剩余 $N-1$ 个线程各自自旋一个完整时间片：
$$浪费的CPU时间=(N-1)\times T_{slice}$$
随着线程数增加，浪费急剧增大。

8.2 改进方案一：Yield（主动让出 CPU）

/*
 * 加入 yield() 的自旋锁
 * 当发现锁被占用时，主动调用 yield() 放弃 CPU
 * 让调度器运行其他线程，避免白白自旋消耗时间片
 *
 * yield() 的效果：将线程状态从 running → ready，立即触发调度
 */
void lock(lock_t *lock) {
    while (TestAndSet(&lock->flag, 1) == 1)
        yield();  /* 不要自旋，主动让出 CPU！ */
}

Yield 方案的流程：

线程A 持有锁，被抢占
   ↓
线程B 调用 lock() → 发现锁被占用 → yield() → 状态变为 ready
   ↓
线程C 调用 lock() → 发现锁被占用 → yield() → 状态变为 ready
   ↓
调度器重新运行线程A → unlock() → 某个等待线程获取锁

Yield 方案的问题：

• 有 100 个线程时：99 个线程各做一次"运行→yield→切换"，产生大量上下文切换开销
• 仍然不公平：可能有线程反复 yield 却始终得不到锁（饥饿）

8.3 改进方案二：队列 + 睡眠（最终方案）

根本解决方案：让等待的线程真正睡眠，由 unlock() 精确唤醒它。
使用 Solaris 提供的两个系统调用：

• park()：让当前线程睡眠（进入 blocked 状态，不占 CPU）
• unpark(threadID)：唤醒指定线程

/*
 * 基于队列+睡眠的锁（类似 futex 的思想）
 *
 * 结构：
 *   flag：锁本身（0=空闲，1=持有）
 *   guard：保护 flag 和队列操作的小自旋锁（只在极短时间内自旋）
 *   q：等待线程的 ID 队列
 */
typedef struct {
    int      flag;    /* 锁的状态 */
    int      guard;   /* 保护内部数据结构的自旋锁 */
    queue_t *q;       /* 等待线程队列 */
} lock_t;
void lock_init(lock_t *m) {
    m->flag  = 0;
    m->guard = 0;
    queue_init(m->q);
}
void lock(lock_t *m) {
    /* 先用 guard 保护内部操作（只短暂自旋） */
    while (TestAndSet(&m->guard, 1) == 1)
        ;  /* 获取 guard 锁 */
    if (m->flag == 0) {
        /* 锁空闲：直接获取 */
        m->flag  = 1;
        m->guard = 0;   /* 释放 guard */
    } else {
        /* 锁被占用：把自己加入等待队列，然后睡眠 */
        queue_add(m->q, gettid());  /* 把当前线程 ID 加入队列 */
        m->guard = 0;               /* 释放 guard（必须在 park 之前！） */
        park();                     /* 睡眠，等待被唤醒 */
        /* 被 unpark 唤醒后从这里继续，此时已经持有锁 */
    }
}
void unlock(lock_t *m) {
    while (TestAndSet(&m->guard, 1) == 1)
        ;  /* 获取 guard 锁 */
    if (queue_empty(m->q)) {
        /* 没有等待者：直接释放锁 */
        m->flag = 0;
    } else {
        /* 有等待者：不清零 flag，直接把锁"传递"给下一个线程 */
        unpark(queue_remove(m->q));  /* 唤醒队列头部的线程 */
        /* 注意：flag 保持为 1，因为锁已经传给了下一个线程 */
    }
    m->guard = 0;
}

为什么 guard 要在 park() 之前释放？

如果先 park() 再释放 guard：
线程A 调用 lock()，获取 guard，发现 flag=1，准备 park()
                    ↑ 此时 guard=1，其他人无法进入 unlock()！
线程B（持有锁）调用 unlock()
  → 尝试获取 guard → 被阻塞 → 无法调用 unpark(A)
  → 线程A 永远睡眠，线程B 也永远阻塞 → 死锁！

8.4 唤醒/等待竞争（wakeup/waiting race）

还有一个微妙的 bug：

线程A：发现锁被占 → 加入队列 → guard=0 → [即将 park()]
                                               ↑ 在这一瞬间被切换！
线程B：unlock() → 发现队列有 A → unpark(A)（A 还没 park！）
线程A：[恢复] → park() → 永远睡眠！

Solaris 的解决方案：setpark()

queue_add(m->q, gettid());
setpark();    /* 设置"我即将 park"的标志 */
m->guard = 0;
park();       /* 如果在 setpark 之后 unpark 已被调用，则立即返回不睡眠 */

九、Linux 的 Futex 锁

Linux 提供了 futex（Fast Userspace muTEX），结合用户态快速路径和内核态睡眠，是实际使用的高性能锁：

无竞争时（常见情况）：
  完全在用户态完成（原子操作），不进内核，极快
有竞争时：
  进内核，放入等待队列睡眠，等待 futex_wake 唤醒

Linux futex 用一个整数同时记录两个信息：

整数的第31位（符号位）= 锁是否被持有
  符号位为1（负数）→ 锁被持有
  符号位为0（正数）→ 锁空闲
其余位 = 等待该锁的线程数量

十、两阶段锁（Two-Phase Lock）

Linux 实际使用的锁融合了自旋和睡眠两种策略：

第一阶段：先自旋一会儿
  → 如果锁很快就释放了，自旋等待比睡眠更高效（避免了昂贵的上下文切换）
第二阶段：如果自旋超时还没拿到锁
  → 进入睡眠，等待唤醒
  → 避免长时间自旋浪费 CPU

$$两阶段锁=自旋锁（快速响应）+睡眠锁（避免浪费）的混合$$

十一、优先级反转问题（Priority Inversion）

自旋锁还有一个正确性问题，甚至在火星探测器上发生过！
场景：

线程优先级：T3 > T2 > T1
T1（低优先级）获取了锁，进入临界区
T3（高优先级）启动，尝试获取同一把锁 → 自旋等待（因为锁在 T1 手里）
T2（中优先级）启动，优先级高于 T1，抢占 CPU 运行
结果：T2 一直运行，T1 永远得不到 CPU，无法释放锁，T3 永远等待！

解决方案：

• 优先级继承（Priority Inheritance）：让低优先级线程临时继承等待者中最高的优先级
• 避免自旋锁：改用让线程睡眠的锁，不会阻塞调度器
• 所有线程相同优先级：最简单粗暴

十二、各种锁方案对比总结

---

方案	正确性	公平性	单CPU性能	多CPU性能
关闭中断	单CPU可以	可以	好	无效
纯标志位	失败	-	-	-
自旋锁(TAS)	正确	不公平	差	还行
自旋锁(CAS)	正确	不公平	差	还行
票号锁	正确	公平	差	还行
队列+睡眠	正确	公平	好	好
两阶段(futex)	正确	公平	最好	最好

---

十三、完整演示：自旋锁 vs 互斥锁性能对比（完整可运行代码）

/*
 * 演示：自旋锁（用 TAS 模拟）vs pthread_mutex 性能对比
 *
 * 编译：gcc -o lock_compare lock_compare.c -lpthread -O2
 * 运行：./lock_compare
 */
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <time.h>
#define ITERATIONS 5000000  /* 每个线程循环次数 */
/* ======= 自旋锁实现（使用 GCC 内置原子操作模拟 TAS）======= */
typedef struct {
    int flag;
} spinlock_t;
void spinlock_init(spinlock_t *l)  { l->flag = 0; }
void spinlock_lock(spinlock_t *l) {
    /* __sync_lock_test_and_set 是 GCC 提供的原子 TAS */
    while (__sync_lock_test_and_set(&l->flag, 1) == 1)
        ;  /* 自旋 */
}
void spinlock_unlock(spinlock_t *l) {
    /* __sync_lock_release 原子地写入 0 */
    __sync_lock_release(&l->flag);
}
/* ======= 共享数据 ======= */
static int counter_spin  = 0;
static int counter_mutex = 0;
static spinlock_t          spin_lock;
static pthread_mutex_t     mutex_lock = PTHREAD_MUTEX_INITIALIZER;
/* ======= 线程函数 ======= */
void *worker_spin(void *arg) {
    int i;
    for (i = 0; i < ITERATIONS; i++) {
        spinlock_lock(&spin_lock);
        counter_spin++;
        spinlock_unlock(&spin_lock);
    }
    return NULL;
}
void *worker_mutex(void *arg) {
    int i;
    for (i = 0; i < ITERATIONS; i++) {
        pthread_mutex_lock(&mutex_lock);
        counter_mutex++;
        pthread_mutex_unlock(&mutex_lock);
    }
    return NULL;
}
/* ======= 计时工具 ======= */
double get_time_ms(void) {
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return ts.tv_sec * 1000.0 + ts.tv_nsec / 1e6;
}
int main(void) {
    pthread_t t1, t2;
    double start, end;
    spinlock_init(&spin_lock);
    /* 测试自旋锁 */
    start = get_time_ms();
    pthread_create(&t1, NULL, worker_spin, NULL);
    pthread_create(&t2, NULL, worker_spin, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    end = get_time_ms();
    printf("自旋锁:  counter=%d, 耗时=%.1f ms\n", counter_spin, end - start);
    /* 测试 pthread_mutex */
    start = get_time_ms();
    pthread_create(&t1, NULL, worker_mutex, NULL);
    pthread_create(&t2, NULL, worker_mutex, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    end = get_time_ms();
    printf("互斥锁:  counter=%d, 耗时=%.1f ms\n", counter_mutex, end - start);
    /* 两个 counter 都应该等于 ITERATIONS*2 */
    printf("期望值:  %d\n", ITERATIONS * 2);
    return 0;
}

十四、一句话总结每个方案

• 关闭中断：最简单，但只能在内核内部用，多核无效
• 纯标志位：看起来对，但测试和设置不是原子的，有竞争条件
• TestAndSet 自旋锁：硬件保证原子，正确，但自旋浪费 CPU
• Compare-And-Swap：比 TAS 更强大，行为类似，还能做无锁编程
• LL/SC：RISC 架构的优雅方案，失败时重试，无 ABA 问题
• 票号锁：公平的自旋锁，按取号顺序服务，但仍然自旋
• 队列+睡眠：等待者真正睡眠，不浪费 CPU，OS 精确控制唤醒
• 两阶段锁(futex)：先自旋再睡眠，兼顾响应速度和 CPU 效率，Linux 实际使用