1. 什么是死锁？

1.1 生活类比

想象两个人在一条只能单向通行的走廊里相向而行，每个人都在等对方让路，但谁都不肯退——这就是死锁的直觉形象。

1.2 经典例子

系统有一台 3D扫描仪 和一台 打印机：

进程 A：先申请3D扫描仪 → 得到了 → 再申请打印机 → 等待...
进程 B：先申请打印机   → 得到了 → 再申请3D扫描仪 → 等待...

两个进程都在等对方释放资源，永远不会继续执行 —— 死锁发生了。

ASCII 示意图：
  进程A  ──持有──>  3D扫描仪
    |                    ^
    |                    |
   等待               等待
    |                    |
    v                    |
  打印机  <──持有──  进程B

1.3 正式定义

死锁：一组进程中，每个进程都在等待一个只有该组中另一个进程才能触发的事件。因为所有进程都在等待，没有任何进程能触发唤醒事件，所有进程永久阻塞。

2. 资源（Resources）

2.1 资源的定义

资源是指任何必须先申请、再使用、最后释放的东西，包括：

• 硬件设备：打印机、扫描仪、摄像头、磁带机
• 软件资源：数据库记录、文件、信号量、互斥锁

2.2 使用资源的三个步骤

1. 申请（Request）  → 如果资源忙，则阻塞等待
2. 使用（Use）      → 执行需要该资源的操作
3. 释放（Release）  → 归还资源供他人使用

2.3 可抢占资源 vs 不可抢占资源

---

类型	说明	举例
可抢占资源	可以强行从进程手中夺走，不会造成危害	内存（可换出到磁盘）
不可抢占资源	强行夺走会导致错误或数据损坏	3D扫描仪（扫描到一半被抢走 → 模型损坏）

---

关键结论：死锁通常发生在不可抢占资源上。

3. 用信号量管理资源

3.1 单个资源

#include <stdio.h>
#include <semaphore.h>
/* 用信号量保护单个资源 */
sem_t resource1;
void use_resource1(void) {
    /* 实际使用资源的操作 */
    printf("正在使用 resource1\n");
}
void process_A(void) {
    sem_wait(&resource1);   /* 申请资源（down操作）：若值为0则阻塞 */
    use_resource1();        /* 使用资源 */
    sem_post(&resource1);   /* 释放资源（up操作）：唤醒等待者 */
}
int main(void) {
    sem_init(&resource1, 0, 1); /* 初始化信号量为1（二值信号量） */
    process_A();
    sem_destroy(&resource1);
    return 0;
}

3.2 两个资源——安全版（不会死锁）

两个进程申请资源的顺序相同：

#include <stdio.h>
#include <semaphore.h>
#include <pthread.h>
sem_t resource1, resource2;
void use_both_resources(void) {
    printf("正在使用两个资源\n");
}
/* 进程A：先申请resource1，再申请resource2 */
void *process_A(void *arg) {
    sem_wait(&resource1);       /* 申请资源1 */
    sem_wait(&resource2);       /* 申请资源2 */
    use_both_resources();
    sem_post(&resource2);       /* 释放资源2 */
    sem_post(&resource1);       /* 释放资源1 */
    return NULL;
}
/* 进程B：同样先申请resource1，再申请resource2 */
void *process_B(void *arg) {
    sem_wait(&resource1);       /* 申请资源1（顺序与A相同！） */
    sem_wait(&resource2);       /* 申请资源2 */
    use_both_resources();
    sem_post(&resource2);
    sem_post(&resource1);
    return NULL;
}
int main(void) {
    sem_init(&resource1, 0, 1);
    sem_init(&resource2, 0, 1);
    pthread_t ta, tb;
    pthread_create(&ta, NULL, process_A, NULL);
    pthread_create(&tb, NULL, process_B, NULL);
    pthread_join(ta, NULL);
    pthread_join(tb, NULL);
    sem_destroy(&resource1);
    sem_destroy(&resource2);
    return 0;
}

3.3 两个资源——危险版（可能死锁）

两个进程申请资源的顺序不同：

#include <stdio.h>
#include <semaphore.h>
#include <pthread.h>
sem_t resource1, resource2;
void use_both_resources(void) {
    printf("正在使用两个资源\n");
}
/* 进程A：先申请resource1，再申请resource2 */
void *process_A(void *arg) {
    sem_wait(&resource1);   /* A先拿resource1 */
    sem_wait(&resource2);   /* A再尝试拿resource2 → 可能被B占着而阻塞！ */
    use_both_resources();
    sem_post(&resource2);
    sem_post(&resource1);
    return NULL;
}
/* 进程B：先申请resource2，再申请resource1（顺序与A相反！） */
void *process_B(void *arg) {
    sem_wait(&resource2);   /* B先拿resource2 */
    sem_wait(&resource1);   /* B再尝试拿resource1 → 可能被A占着而阻塞！ */
    use_both_resources();
    sem_post(&resource1);
    sem_post(&resource2);
    return NULL;
}
/* 死锁场景：
   时刻1：A拿到resource1，B拿到resource2
   时刻2：A等待resource2（B占着），B等待resource1（A占着）
   结果：两个进程永久阻塞 */
int main(void) {
    sem_init(&resource1, 0, 1);
    sem_init(&resource2, 0, 1);
    pthread_t ta, tb;
    pthread_create(&ta, NULL, process_A, NULL);
    pthread_create(&tb, NULL, process_B, NULL);
    pthread_join(ta, NULL);
    pthread_join(tb, NULL);
    sem_destroy(&resource1);
    sem_destroy(&resource2);
    return 0;
}

4. 哲学家就餐问题（Dining Philosophers Problem）

4.1 问题描述

5位哲学家围坐一桌，每人面前一盘意大利面。每人左右各有一把叉子（共5把）。吃面需要两把叉子。哲学家要么在思考，要么在吃饭。

ASCII 桌面示意图：
        哲学家0
       /       \
    叉子4       叉子0
    /               \
哲学家4           哲学家1
    \               /
    叉子3       叉子1
       \       /
        哲学家3---叉子2---哲学家2

4.2 错误解法（会死锁）

#include <stdio.h>
#define N 5   /* 哲学家数量 */
void think(int i) { printf("哲学家%d 正在思考\n", i); }
void eat(int i)   { printf("哲学家%d 正在吃饭\n", i); }
/* 伪代码：每人先拿左叉，再拿右叉 */
void take_fork(int fork_id) { /* 拿起叉子 */ }
void put_fork(int fork_id)  { /* 放下叉子 */ }
void philosopher(int i) {
    while (1) {
        think(i);
        take_fork(i);           /* 拿起左边的叉子 */
        take_fork((i+1) % N);   /* 拿起右边的叉子 */
        eat(i);
        put_fork(i);            /* 放下左叉 */
        put_fork((i+1) % N);    /* 放下右叉 */
    }
}
/* 死锁场景：
   如果5位哲学家同时拿起左叉
   → 每人都在等右叉（被下一位哲学家持有）
   → 永久等待，死锁！ */

4.3 正确解法（无死锁无饥饿）

#include <stdio.h>
#include <semaphore.h>
#include <pthread.h>
#include <unistd.h>
#define N        5          /* 哲学家数量 */
#define LEFT     (i+N-1)%N  /* 左邻居编号 */
#define RIGHT    (i+1)%N    /* 右邻居编号 */
#define THINKING 0          /* 哲学家状态：思考中 */
#define HUNGRY   1          /* 哲学家状态：想吃饭 */
#define EATING   2          /* 哲学家状态：吃饭中 */
int state[N];               /* 每位哲学家的当前状态 */
sem_t mutex;                /* 临界区互斥锁，保护state数组 */
sem_t s[N];                 /* 每位哲学家一个信号量，用于阻塞/唤醒 */
/*
 * test: 检查哲学家i是否可以开始吃饭
 * 条件：自己处于HUNGRY状态，且左右邻居都没有在EATING
 */
void test(int i) {
    if (state[i] == HUNGRY &&
        state[LEFT] != EATING &&
        state[RIGHT] != EATING) {
        state[i] = EATING;
        sem_post(&s[i]);    /* 允许哲学家i开始吃饭（唤醒或防止阻塞） */
    }
}
/*
 * take_forks: 哲学家i尝试拿两把叉子
 * 如果条件不满足则阻塞，等待邻居唤醒
 */
void take_forks(int i) {
    sem_wait(&mutex);       /* 进入临界区，防止并发修改state */
    state[i] = HUNGRY;      /* 记录自己想吃饭 */
    test(i);                /* 尝试获得两把叉子 */
    sem_post(&mutex);       /* 离开临界区 */
    sem_wait(&s[i]);        /* 若未能拿到叉子，在此阻塞等待 */
}
/*
 * put_forks: 哲学家i放下两把叉子
 * 并通知左右邻居检查自己是否可以开始吃饭
 */
void put_forks(int i) {
    sem_wait(&mutex);       /* 进入临界区 */
    state[i] = THINKING;    /* 从EATING切换回THINKING */
    test(LEFT);             /* 检查左邻居能否现在开始吃 */
    test(RIGHT);            /* 检查右邻居能否现在开始吃 */
    sem_post(&mutex);       /* 离开临界区 */
}
/* 哲学家线程的主循环 */
void *philosopher(void *arg) {
    int i = *(int *)arg;
    while (1) {
        printf("哲学家%d 正在思考\n", i);
        sleep(1);
        take_forks(i);              /* 拿叉子（可能阻塞） */
        printf("哲学家%d 正在吃饭\n", i);
        sleep(1);
        put_forks(i);               /* 放叉子，通知邻居 */
    }
    return NULL;
}
int main(void) {
    pthread_t tid[N];
    int id[N];
    sem_init(&mutex, 0, 1);
    for (int i = 0; i < N; i++) {
        sem_init(&s[i], 0, 0);  /* 初始为0：哲学家开始时必须先等待 */
        state[i] = THINKING;
    }
    for (int i = 0; i < N; i++) {
        id[i] = i;
        pthread_create(&tid[i], NULL, philosopher, &id[i]);
    }
    for (int i = 0; i < N; i++)
        pthread_join(tid[i], NULL);
    return 0;
}

5. 死锁的四个必要条件（Coffman条件）

1971年，Coffman等人证明，死锁发生当且仅当以下四个条件同时成立：

编号	条件名	含义
1	互斥条件（Mutual Exclusion）	每个资源要么被一个进程独占，要么空闲
2	持有并等待（Hold and Wait）	进程持有资源的同时，还在申请新资源
3	不可抢占（No Preemption）	资源不能被强制夺走，只能由持有者主动释放
4	循环等待（Circular Wait）	进程之间形成循环等待链（A等B，B等C，C等A）

---

只要破坏其中任意一个条件，死锁就不会发生。

6. 资源分配图（Resource Allocation Graph）

6.1 图的构成

用有向图来建模资源分配状态：

• 圆形节点：进程
• 方形节点：资源
• 资源 → 进程（箭头）：该资源已被该进程持有
• 进程 → 资源（箭头）：该进程正在等待该资源

6.2 图示例

持有关系：资源R被进程A持有
R ---> A
等待关系：进程B在等待资源S
B ---> S
死锁：存在环路
C ---> T ---> D ---> U ---> C
（C等T，T被D持有；D等U，U被C持有）

用Mermaid描述死锁环路：

6.3 判断规则

资源分配图中存在环路 → 系统处于死锁状态（每种资源只有一个实例时）

7. 死锁的四种处理策略

8. 策略一：鸵鸟算法（Ostrich Algorithm）

思想：把头埋进沙子，假装问题不存在。
适用场景：如果死锁极少发生（如五年一次），但防死锁机制代价很高（影响性能），则可以接受偶尔重启系统。

大多数通用操作系统（Linux、Windows）就是这样做的——用户可以手动重启。

9. 策略二：死锁检测与恢复

9.1 单类资源检测（图的环路检测）

深度优先搜索算法：

算法步骤：
1. 对图中每个节点N，以N为起点执行以下步骤
2. 初始化路径列表L为空，将所有边标记为"未访问"
3. 将当前节点加入L尾部，若该节点在L中出现2次 → 找到环路，停止
4. 若当前节点有未访问的出边 → 转步骤5；否则转步骤6
5. 随机选一条未访问出边，标记它，跟随到新节点，转步骤3
6. 若当前是初始节点 → 无环路；否则回退到上一节点，转步骤3

9.2 多类资源检测（矩阵算法）

设有 $n$ 个进程，$m$ 种资源类型，定义以下向量和矩阵：

• $E$：资源存在向量，$E_i$ = 第 $i$ 类资源总数
• $A$：资源可用向量，$A_i$ = 第 $i$ 类资源当前空闲数
• $C$：当前分配矩阵，$C_{ij}$ = 进程 $i$ 持有第 $j$ 类资源数量
• $R$：请求矩阵，$R_{ij}$ = 进程 $i$ 还需要第 $j$ 类资源数量
  不变式（所有资源要么被分配，要么空闲）：
  $$\sum _{i=1}^n{C}_{ij}+A_j=E_j$$
  检测算法：

1. 寻找一个未标记进程Pi，使得R的第i行 <= A（向量逐元素比较）
2. 若找到：将C的第i行加到A，标记Pi为"可完成"，回到步骤1
3. 若找不到：算法结束，未被标记的进程处于死锁状态

具体例子：
$$E=(4,2,3,1)$$
分配矩阵 $C$ 和请求矩阵 $R$：
$$C=\left(\begin{array}{cccc}0& 1& 0& 0\\ 2& 0& 0& 1\\ 0& 1& 2& 0\end{array}\right),R=\left(\begin{array}{cccc}2& 0& 0& 1\\ 1& 0& 1& 0\\ 2& 1& 0& 0\end{array}\right)$$
$$A=(2,1,0,0)$$
检测步骤：

1. 进程3的请求 $(2,1,0,0)\le A=(2,1,0,0)$，可运行，运行完后 $A=(2,2,2,0)$
2. 进程2的请求 $(1,0,1,0)\le A=(2,2,2,0)$，可运行，运行完后 $A=(4,2,2,1)$
3. 进程1的请求 $(2,0,0,1)\le A=(4,2,2,1)$，可运行
   结论：无死锁

9.3 从死锁中恢复

方法一：抢占资源

• 强制从某进程手中夺走资源，给另一进程使用
• 难度：取决于资源性质，往往需要人工干预
  方法二：回滚（Rollback）
• 定期为进程做检查点（Checkpoint），保存进程完整状态到文件
• 发现死锁后，将某个进程回滚到持有所需资源之前的状态
• 代价：检查点之后做的工作全部丢失
  方法三：杀死进程
• 最粗暴但最简单：直接杀掉死锁环中的一个或多个进程
• 优先选择可以无副作用重新运行的进程（如编译任务）
• 避免杀掉已修改数据库的进程（重跑会产生错误结果）

10. 策略三：死锁避免（Banker’s Algorithm）

10.1 安全状态与不安全状态

• 安全状态：存在某种调度顺序，使得所有进程都能最终完成执行
• 不安全状态：不能保证所有进程都能完成（但不一定立即死锁）

不安全状态 $\ne$ 死锁，但可能导致死锁

10.2 银行家算法（单类资源）

用银行贷款打比方：银行家（操作系统）要确保，在任何时刻给某客户（进程）贷款（分配资源）后，系统仍处于安全状态。
例子（总资源10个）：

进程	已有	最大需求
A	3	9
B	2	4
C	2	7
空闲	3	—

---

检查安全性：先满足B（还需2，空闲有3）→ B完成释放2，空闲5 → 满足C（还需5）→ C完成，空闲7 → 满足A（还需6）→ 全部完成。安全！

10.3 银行家算法（多类资源）

#include <stdio.h>
#include <string.h>
#define MAX_PROCESSES 10
#define MAX_RESOURCES 10
/* 检查向量A是否 <= 向量B（逐元素比较） */
int vector_leq(int a[], int b[], int m) {
    for (int j = 0; j < m; j++) {
        if (a[j] > b[j]) return 0;  /* a[j] > b[j]，不满足 */
    }
    return 1;
}
/*
 * is_safe: 银行家算法安全性检测
 * 参数：
 *   n - 进程数量
 *   m - 资源种类数
 *   avail[] - 当前可用资源向量
 *   need[][] - 每个进程还需要的资源矩阵（= 最大需求 - 已分配）
 *   alloc[][] - 当前分配矩阵
 * 返回值：1=安全，0=不安全
 */
int is_safe(int n, int m,
            int avail[],
            int need[][MAX_RESOURCES],
            int alloc[][MAX_RESOURCES]) {
    int work[MAX_RESOURCES];    /* 当前可用资源的工作副本 */
    int finish[MAX_PROCESSES];  /* finish[i]=1表示进程i可以完成 */
    /* 初始化：work = avail，所有进程标记为未完成 */
    memcpy(work, avail, m * sizeof(int));
    memset(finish, 0, n * sizeof(int));
    int changed = 1;
    while (changed) {
        changed = 0;
        for (int i = 0; i < n; i++) {
            /* 寻找一个未完成且需求可被满足的进程 */
            if (!finish[i] && vector_leq(need[i], work, m)) {
                /* 假设进程i运行完毕，释放其占有的资源 */
                for (int j = 0; j < m; j++)
                    work[j] += alloc[i][j];
                finish[i] = 1;  /* 标记为可完成 */
                changed = 1;    /* 有进程完成，继续循环 */
            }
        }
    }
    /* 若所有进程都能完成，则状态安全 */
    for (int i = 0; i < n; i++) {
        if (!finish[i]) return 0;  /* 进程i无法完成 → 不安全 */
    }
    return 1;
}
int main(void) {
    int n = 5, m = 4;  /* 5个进程，4种资源 */
    /* 当前可用资源 */
    int avail[MAX_RESOURCES] = {1, 0, 2, 0};
    /* 当前分配矩阵 */
    int alloc[MAX_PROCESSES][MAX_RESOURCES] = {
        {0, 0, 1, 2},  /* 进程0 */
        {1, 0, 0, 0},  /* 进程1 */
        {1, 3, 5, 4},  /* 进程2 */
        {0, 6, 3, 2},  /* 进程3 */
        {0, 0, 1, 4}   /* 进程4 */
    };
    /* 最大需求矩阵 */
    int maxd[MAX_PROCESSES][MAX_RESOURCES] = {
        {7, 5, 3, 0},
        {3, 2, 2, 0},
        {9, 0, 2, 0},
        {2, 2, 2, 0},
        {4, 3, 3, 0}
    };
    /* 计算 need = max - alloc */
    int need[MAX_PROCESSES][MAX_RESOURCES];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            need[i][j] = maxd[i][j] - alloc[i][j];
    if (is_safe(n, m, avail, need, alloc))
        printf("当前状态：安全\n");
    else
        printf("当前状态：不安全（可能死锁）\n");
    return 0;
}

10.4 银行家算法的局限性

• 进程很少提前知道自己最多需要多少资源
• 进程数量动态变化（用户登录/退出）
• 资源可能突然消失（设备故障）
  结论：银行家算法理论上完美，实践中几乎不用。

11. 策略四：死锁预防（Deadlock Prevention）

11.1 破坏互斥条件

方法：假脱机（Spooling）
把所有输出先写到磁盘，由守护进程（daemon）统一管理物理打印机。进程不直接竞争打印机。
局限：不是所有资源都能假脱机（如数据库记录）

11.2 破坏持有并等待条件

方法：进程开始前必须一次性申请所有需要的资源
问题：

• 资源利用率低（分析一个小时，却一直占着打印机）
• 进程往往无法预先知道需要哪些资源

11.3 破坏不可抢占条件

方法：通过虚拟化资源（如打印机假脱机到磁盘）
局限：数据库锁等资源无法虚拟化

11.4 破坏循环等待条件（最实用）

方法：资源编号排序
为所有资源全局编号，规定进程只能按编号从小到大的顺序申请资源。

编号示例：
1. 成像仪（Imagesetter）
2. 打印机（Printer）
3. 绘图仪（Plotter）
4. 磁带机（Tape drive）
5. 蓝光驱动器（Blu-ray drive）

为什么能避免循环等待？
假设进程A持有编号 $i$ 的资源，想申请编号 $j$ 的资源；进程B持有编号 $j$，想申请编号 $i$。

• 若 $i>j$：规则不允许A申请 $j$（比已持有的 $i$ 小）
• 若 $i<j$：规则不允许B申请 $i$（比已持有的 $j$ 小）
  无论哪种情况，循环等待都不可能形成。
  推广到多进程：在任意时刻，持有编号最大资源的进程，永远不需要申请更低编号的资源，它一定能完成并释放资源，从而给后续进程创造条件。

11.5 四种预防方法总结

---

要破坏的条件	方法
互斥条件	对所有资源使用假脱机
持有并等待	开始时一次性申请所有资源
不可抢占	强制夺走资源（虚拟化）
循环等待	对资源按编号排序，强制按序申请

---

12. 其他死锁相关问题

12.1 两阶段锁定（Two-Phase Locking）

应用场景：数据库系统，一个事务需要锁定多条记录。
第一阶段：尝试逐一加锁所有需要的记录。若某条记录已被锁定：

• 释放所有已获得的锁
• 等待一段时间
• 重新从第一阶段开始
  第二阶段：所有锁都获得后，执行更新，然后释放锁。
  特点：类似于"要么全拿，要么不拿"，避免了死锁，但不是所有场景都适用（实时系统、网络操作等不可重复执行的场景无法使用）。

12.2 通信死锁（Communication Deadlock）

场景：进程A向进程B发送请求消息，等待回复；请求消息丢失了。

进程A：发完消息后阻塞，等待B的回复
进程B：等待A的请求（请求已丢失）
→ 两者都阻塞，但没有资源竞争

与资源死锁的区别：没有任何资源被持有，是通信协作出了问题。
解决方案：超时（Timeout）
发送消息后启动计时器，超时未收到回复则重发。简单有效，但需防止消息重复执行（如银行转账消息重发会导致重复扣款）。

12.3 活锁（Livelock）

进程没有阻塞，但也没有进展——就像两个人在走廊里互相谦让，同时向同一方向侧身，永远无法通过。

#include <stdio.h>
#include <pthread.h>
#include <time.h>
pthread_mutex_t resource1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t resource2 = PTHREAD_MUTEX_INITIALIZER;
void fixed_wait(void) {
    /* 等待固定时间（导致活锁的关键：两者等待时间相同！） */
    struct timespec ts = {0, 1000000}; /* 1毫秒 */
    nanosleep(&ts, NULL);
}
/*
 * 进程A：先锁resource1，再尝试锁resource2
 * 若失败，则礼貌地释放resource1，等待后重试
 * 问题：若B也同时做对称操作，双方都"礼让"却都无法推进
 */
void *process_A(void *arg) {
    int attempts = 0;
    while (1) {
        pthread_mutex_lock(&resource1);          /* 锁定resource1 */
        if (pthread_mutex_trylock(&resource2) == 0) {  /* 尝试锁resource2 */
            /* 成功拿到两个资源 */
            printf("进程A：成功拿到两个资源，共尝试%d次\n", attempts+1);
            pthread_mutex_unlock(&resource2);
            pthread_mutex_unlock(&resource1);
            break;
        }
        /* 失败：礼貌地放弃resource1，等待后重试（活锁根源！） */
        pthread_mutex_unlock(&resource1);
        fixed_wait();
        attempts++;
        if (attempts > 10) { printf("进程A：活锁，放弃！\n"); break; }
    }
    return NULL;
}
void *process_B(void *arg) {
    int attempts = 0;
    while (1) {
        pthread_mutex_lock(&resource2);
        if (pthread_mutex_trylock(&resource1) == 0) {
            printf("进程B：成功拿到两个资源，共尝试%d次\n", attempts+1);
            pthread_mutex_unlock(&resource1);
            pthread_mutex_unlock(&resource2);
            break;
        }
        pthread_mutex_unlock(&resource2);
        fixed_wait();
        attempts++;
        if (attempts > 10) { printf("进程B：活锁，放弃！\n"); break; }
    }
    return NULL;
}
int main(void) {
    pthread_t ta, tb;
    pthread_create(&ta, NULL, process_A, NULL);
    pthread_create(&tb, NULL, process_B, NULL);
    pthread_join(ta, NULL);
    pthread_join(tb, NULL);
    return 0;
}

活锁 vs 死锁的区别：

特征	死锁	活锁
进程状态	阻塞（blocked）	运行中（running）
CPU占用	不占用	占用（在循环）
有无进展	无	无
可检测性	较容易（等待队列）	较难（进程看起来在运行）

---

12.4 饥饿（Starvation）

定义：进程虽然未死锁，但由于调度策略，永远得不到所需资源。
例子：打印队列按文件大小从小到大分配打印机。一个巨大文件的进程，面对源源不断的小文件，永远排不上号。
解决方案：先到先得（FCFS，First Come First Served）策略——等待时间最长的进程优先服务。

13. 三个概念对比

死锁（Deadlock）：
  进程A 等待 进程B 持有的资源
  进程B 等待 进程A 持有的资源
  → 两者永久阻塞，CPU使用率为0
活锁（Livelock）：
  进程A 尝试 → 失败 → 退让 → 尝试 → 失败 → ...
  进程B 尝试 → 失败 → 退让 → 尝试 → 失败 → ...
  → 两者都在运行，但没有进展，CPU占用但无效
饥饿（Starvation）：
  进程A 排队等待资源
  总有更高优先级的进程插队
  → 进程A永远等待，但其他进程正常运行

14. 整体知识结构总结

虚拟化与云计算 —— 深度理解笔记

本文基于操作系统教材第7章，用最通俗的语言解释虚拟化的核心概念。

1. 为什么需要虚拟化？

1.1 现实问题

想象一家公司同时运行：邮件服务器、Web 服务器、FTP 服务器、电商服务器……
每个服务跑在一台独立的物理机上，原因有两个：

• 负载问题：一台机器扛不住所有流量
• 可靠性问题：一台服务器崩了，不影响其他服务器（隔离）
• 安全问题：黑客攻破了 Web 服务器，也拿不到邮件数据（沙箱隔离）
  但问题是：太贵了，而且管理起来非常麻烦。

1.2 解决方案：虚拟机技术

核心思路：用一台物理机，虚拟出多台逻辑机器。
负责这件事的软件叫做 VMM（Virtual Machine Monitor，虚拟机监控器），也叫 Hypervisor（虚拟机管理程序）。

物理机硬件
    |
 Hypervisor（虚拟机管理程序）
    |
 +--+--+--+
 |  |  |  |
VM1 VM2 VM3 ...（每个虚拟机跑独立的操作系统）

好处总结：

好处	说明
故障隔离	一个虚拟机崩了，其他不受影响
节省硬件	少买物理机，省电、省空间
多操作系统共存	同一台机器可以跑 Linux、Windows、macOS
方便测试	开发者不需要买十几台电脑测试兼容性
虚拟机迁移	可以把运行中的虚拟机搬到另一台物理机
云计算基础	云服务商用虚拟化把一台物理机租给多个客户

---

潜在风险：
把所有虚拟机都放在一台物理机上，物理机本身坏了，所有虚拟机都完蛋——“把鸡蛋放在一个篮子里”。
但实践中，大多数故障不是硬件坏了，而是软件有 bug。Hypervisor 的代码量只有完整操作系统的 $\frac{1}{100}$，bug 也少得多，所以整体可靠性反而更高。

2. 虚拟化的历史

1960s  IBM 开始实验 Hypervisor（SIMMON、CP-40）
  |
1972   IBM 发布 VM/370，正式商用
  |
1974   Popek & Goldberg 发表论文，提出虚拟化的理论条件
  |         (但 x86 不满足这些条件！)
1979   UNIX v7 引入 chroot —— OS级虚拟化的远祖
  |
1990s  Stanford 的 Disco 项目，VMware 的前身
  |
1998   VMware 公司成立
  |
1999   VMware Workstation 发布 —— x86上第一个商用虚拟机
  |
2000   FreeBSD Jails 发布（OS级虚拟化的重要里程碑）
  |
2001   VMware ESX Server 发布（type 1 hypervisor）
  |
2005   Intel/AMD 在 CPU 中加入硬件虚拟化支持（VT-x / SVM）
  |
2008   Linux LXC 发布
  |
2013   Docker 发布，容器技术爆发式普及

虚拟化技术并不新，1974年理论就已完善，但直到1999年才在 x86 上流行起来。

3. 虚拟化的三大基本要求

设计一个 Hypervisor，必须在以下三个维度做好：

维度	含义
安全性 (Safety)	Hypervisor 必须对虚拟资源有完全控制权，客户机不能越权
保真性 (Fidelity)	程序在虚拟机里的行为，和在真实硬件上一模一样
高效性 (Efficiency)	虚拟机里的大部分代码，不需要 Hypervisor 介入就能直接运行

---

4. Popek & Goldberg 理论：什么样的机器能被虚拟化？

4.1 两种关键指令

• 敏感指令 (Sensitive Instructions)：在内核态和用户态执行，行为不同的指令（比如控制中断、修改页表等）
• 特权指令 (Privileged Instructions)：在用户态执行会触发陷阱（trap）的指令

4.2 虚拟化的充分条件

$$\text{敏感指令}\subseteq \text{特权指令}$$
通俗理解：只要你想做"不该做的事"（执行敏感指令），硬件就必须拦截你（触发陷阱），这样 Hypervisor 才能介入处理。

4.3 x86 的问题

x86（Intel 386 及后续处理器）长期不满足这个条件：

• 某些敏感指令在用户态执行时，不触发陷阱，而是悄悄地被忽略或行为改变
• 例如 POPF 指令：本应修改中断标志位，但在用户态执行时，该位不会被修改，也不会报错
  这导致 x86 在 2005 年之前，原生无法被虚拟化。
  直到 2005 年，Intel 推出 VT-x，AMD 推出 SVM，才在硬件层面解决了这个问题。

5. Type 1 和 Type 2 Hypervisor

5.1 架构对比

Type 1 Hypervisor（裸机型）        Type 2 Hypervisor（寄宿型）
  +-------+-------+               +-------+-------+
  |  VM1  |  VM2  |               |  VM1  |  VM2  |
  +-------+-------+               +-------+-------+
  |   Hypervisor  |               |  Hypervisor   |
  +---------------+               +---------------+
  |    硬件        |               |  宿主操作系统  |
  +---------------+               +---------------+
                                  |    硬件        |
                                  +---------------+

---

特性	Type 1	Type 2
运行位置	直接运行在裸机上	运行在宿主OS之上
性能	更高	略低（多一层OS）
典型产品	VMware ESX Server, Xen, Hyper-V	VMware Workstation, VirtualBox, KVM
适用场景	数据中心、服务器整合	开发测试、个人桌面

---

• Guest OS（客户操作系统）：运行在虚拟机内部的操作系统
• Host OS（宿主操作系统）：Type 2 中，运行在真实硬件上的操作系统

6. 高效虚拟化的技术手段

6.1 陷阱与模拟（Trap-and-Emulate）

有了硬件虚拟化支持（VT-x）后，基本流程如下：

客户操作系统执行敏感指令
        |
        v
  CPU触发陷阱（Trap）
        |
        v
  Hypervisor捕获陷阱
        |
        v
  Hypervisor检查：是OS发的？还是用户进程发的？
        |
     +--+--+
     |     |
  是OS   是用户进程
     |     |
  模拟执行  模拟真实硬件对用户进程的处理

6.2 二进制翻译（Binary Translation）

在硬件虚拟化支持出现之前（2005年前），VMware 用软件方法解决：
核心思路：在客户代码执行之前，扫描代码中的敏感指令，把它们替换成对 Hypervisor 过程的调用。

原始客户OS代码（ring 1执行）:
    MOV  EAX, CR3      ; 敏感！读取页目录基址
    CLI                ; 敏感！关中断
经过二进制翻译后:
    CALL hypervisor_read_cr3   ; 调用hypervisor过程
    CALL hypervisor_disable_int ; 调用hypervisor过程

x86 四个保护环的利用：

Ring 0 ── Hypervisor（最高权限）
Ring 1 ── 客户操作系统（Guest OS）
Ring 2 ── （未使用）
Ring 3 ── 用户进程（最低权限）

正常情况下只用 Ring 0 和 Ring 3，虚拟化时把 Guest OS 放到 Ring 1，这样它的特权指令会陷阱到 Ring 0 的 Hypervisor。
翻译效率优化：

• 翻译过的基本块会被缓存，下次直接用，不需要重复翻译
• 大多数代码块不含敏感指令，可以原生执行
• 基本块末尾的跳转指令可以直接跳到下一个已翻译块，消除查找开销
  一个有趣的性能例子：
  原始的 CLI（关中断）指令在某些 CPU 上需要几十个时钟周期。
  翻译后，变成：

/* 伪代码：不真正关中断，只修改虚拟CPU的中断标志 */
VirtualCPU.IF = 0;  /* 只是一条MOV，1~3个时钟周期 */

$$\text{性能提升}=\frac{\text{原始CLI指令周期数（ 50+）}}{\text{MOV指令周期数（1 3）}}\approx 1050\text{ 倍}$$

6.3 半虚拟化（Paravirtualization）

与全虚拟化不同，半虚拟化不假装自己是真实硬件，而是提供一套专为虚拟化设计的接口。

• 客户OS被修改，把敏感操作替换成 Hypercall（超级调用），类似于系统调用
• 客户OS知道自己运行在虚拟机里
• 优点：更快，因为不需要 trap-and-emulate 的开销
• 缺点：需要修改客户OS源码，Windows 这种闭源OS没法用

全虚拟化:                     半虚拟化:
客户OS以为自己在真实硬件上      客户OS知道自己在虚拟机里
    |                              |
敏感指令 → 触发陷阱            直接调用 Hypercall
    |                              |
Hypervisor捕获并模拟           Hypervisor直接执行
（有额外开销）                 （更高效）

7. 内存虚拟化

7.1 问题的来源

每个虚拟机里的OS都以为自己独占全部物理内存，可以随意分配物理页号。
但实际上多个虚拟机会抢同一个物理页，Hypervisor 必须做"二次映射"。
三层地址翻译：
$$\text{客户虚拟地址（GVA）}\stackrel{\text{客户页表}}{\to }\text{客户物理地址（GPA）}\stackrel{\text{Hypervisor映射}}{\to }\text{宿主物理地址（HPA）}$$

7.2 影子页表（Shadow Page Tables）

软件方法：Hypervisor 为每个虚拟机维护一张影子页表，直接完成 GVA → HPA 的映射，跳过中间层。

客户OS认为的映射:          影子页表（实际硬件使用）:
虚拟页7 → 物理页10         虚拟页7 → 宿主物理页52
虚拟页4 → 物理页11         虚拟页4 → 宿主物理页53
虚拟页3 → 物理页12         虚拟页3 → 宿主物理页54

维护影子页表的挑战：
客户OS修改页表时，只是写内存，不会触发陷阱。Hypervisor 怎么知道？
解决方案：把客户OS的页表所在页面标记为只读，一旦客户OS试图修改，触发缺页异常，Hypervisor 接管并更新影子页表。
缺点：每次更新页表都产生缺页异常，开销极大。

7.3 扩展页表（EPT / 嵌套页表）

2007 年后，Intel（EPT）和 AMD（Nested Page Tables）在硬件层面解决了这个问题：
CPU 硬件自动处理两级页表的遍历，不再需要 Hypervisor 用软件维护影子页表。

扩展页表的遍历过程（以4级页表为例）：
GVA  ──[客户页表L1]──> L1表项 ──[嵌套页表查GPA→HPA]──> 真实地址
                           |
                    L2表项 ──[嵌套页表查GPA→HPA]──> 真实地址
                           |
                    L3表项 ──[嵌套页表查GPA→HPA]──> 真实地址
                           |
                    L4表项 ──[嵌套页表查GPA→HPA]──> 最终HPA

内存访问次数：设页表深度为 $n$，则总内存访问次数约为：
$$\text{访问次数}\approx (n+1{)}^2$$
例如4级页表：$(4+1{)}^2=25$ 次内存访问。虽然多，但避免了 VM exit，整体更快。

7.4 内存回收：气球驱动（Balloon Driver）

问题：Hypervisor 想从某个虚拟机那里"拿走"一些内存给另一个用，但不知道哪些内存页对那个虚拟机是"不重要的"。
解决方案：在每个虚拟机里安装一个叫"气球"的伪设备驱动。

Hypervisor需要内存：
    |
    v
通知虚拟机A的气球驱动："充气！"
    |
    v
气球驱动在虚拟机A内申请大量内存页（"充气"）
    |
    v
虚拟机A的OS感到内存紧张
    |
    v
虚拟机A的OS主动把"不重要"的页换出到磁盘
    |
    v
Hypervisor把这些被腾出的页给虚拟机B使用

这招的精妙之处：让客户OS自己决定换出哪些页，因为客户OS比 Hypervisor 更了解哪些数据不重要。这在政治上叫做"甩锅"（passing the buck）。

7.5 去重（Deduplication）

如果多个虚拟机运行相同的操作系统，它们的内存里会有大量内容完全相同的页（比如 Linux 内核代码）。

虚拟机1的内存:    虚拟机2的内存:    虚拟机3的内存:
[Linux内核页A]   [Linux内核页A]   [Linux内核页A]
    |                |                |
    +────────────────+────────────────+
                     |
              实际只存一份
              (写时复制 Copy-on-Write)

$$\text{节省内存}=(\text{虚拟机数}-1)\times \text{共享页数}\times \text{页大小}$$

8. I/O 虚拟化

8.1 基本方案

客户OS探测设备 → 陷阱到 Hypervisor → Hypervisor 汇报"虚假"设备列表 → 客户OS加载对应驱动 → 驱动操作设备寄存器 → 再次陷阱到 Hypervisor → Hypervisor 转发到真实硬件。

8.2 I/O MMU

普通 DMA 使用绝对物理地址，虚拟机里的设备不知道真实物理地址。
I/O MMU 的作用：像普通 MMU 管理 CPU 内存访问一样，管理设备的 DMA 访问，把设备地址翻译成真实物理地址，同时防止设备越界访问其他虚拟机的内存。
I/O MMU 还支持中断重映射：设备发出的中断号经过翻译，发给正确的虚拟机，使用虚拟机期望的中断向量。

8.3 SR-IOV（单根I/O虚拟化）

让硬件本身虚拟化，一个物理网卡可以虚拟出多个虚拟网卡：

• PF（物理功能）：完整的 PCIe 功能，供管理员配置设备
• VF（虚拟功能）：精简版 PCIe 功能，每个虚拟机分一个
  每个 VF 有独立的内存空间、中断和 DMA 流，虚拟机以为自己独占一块网卡。

物理网卡（支持SR-IOV）
    |
    +── VF1 ── 虚拟机1（以为自己有独立网卡）
    +── VF2 ── 虚拟机2
    +── VF3 ── 虚拟机3
    ...
    +── VF256 ── 虚拟机256

9. Hypervisor 与微内核的关系

微内核的思路：操作系统内核只保留最基本功能（进程调度、内存管理），其余服务（文件系统、网络等）作为用户进程运行。
半虚拟化 Hypervisor 的思路：客户OS调用 Hypercall 来完成敏感操作。
这两者越来越像：

Type 1 Hypervisor 架构（半虚拟化）:
  未修改Windows(全虚拟化)    修改后的Linux(半虚拟化)
         |                          |
    敏感指令陷阱               直接Hypercall
         |                          |
  +------+---------------------------+------+
  |   模拟层（处理陷阱）  |  微内核（执行Hypercall）|
  +--------------------------------------------+
  |              硬件                          |
  +--------------------------------------------+

10. OS 级虚拟化（容器）

10.1 与 Hypervisor 的对比

Hypervisor 虚拟化:              OS 级虚拟化（容器）:
+------+------+------+          +------+------+------+
| VM1  | VM2  | VM3  |          | 容器1 | 容器2 | 容器3 |
| OS1  | OS2  | OS3  |          +------+------+------+
+------+------+------+          |   共享同一个OS内核   |
|   Hypervisor       |          +--------------------+
+--------------------+          |       硬件          |
|       硬件          |          +--------------------+
+--------------------+

---

对比项	虚拟机（Hypervisor）	容器（OS级虚拟化）
隔离性	强（完全独立的OS）	较弱（共享内核）
启动速度	慢（需要启动完整OS）	快（秒级）
资源开销	大	小
多OS支持	支持	不支持
典型工具	VMware, VirtualBox	Docker, Kubernetes

---

10.2 容器的技术基础

chroot（1979年，UNIX v7）

最原始的隔离：限制进程能看到的文件系统范围。

/* 把进程的根目录改到 /home/sandbox */
chroot("/home/sandbox");
/* 此后该进程访问 /etc/passwd 实际上是访问 /home/sandbox/etc/passwd */

缺点：只隔离文件系统，进程、网络、用户权限等都没有隔离。

Linux cgroups（控制组）

用于限制和追踪一组进程的资源使用：

cgroup层级结构示例:
root_cgroup（所有CPU、所有内存）
    |
    +── web_service_cgroup
    |       └── 限制：最多使用4个核心，最多4GB内存
    |
    +── database_cgroup
            └── 限制：最多使用8个核心，最多16GB内存

可控制的资源：CPU 时间、内存用量、磁盘I/O带宽、网络带宽等。

Linux Namespace（命名空间）

为进程组创建隔离的"视图"：

命名空间	隔离的资源
PID namespace	进程ID
Network namespace	网络接口、IP地址
Mount namespace	文件系统挂载点
User namespace	用户ID和组ID
IPC namespace	进程间通信

---

Docker = chroot + cgroups + namespace + 镜像管理

11. 云计算

11.1 云的五个基本特征（NIST定义）

1. 按需自助服务：用户无需人工干预，自动申请资源
2. 宽带网络访问：通过标准网络协议访问
3. 资源池化：计算资源动态分配给多个用户
4. 快速弹性伸缩：资源可以随需求自动扩展或收缩
5. 可计量服务：按实际使用量计费

11.2 云服务分类

SaaS（软件即服务）  ← 最高层，用户直接使用软件（如Gmail）
PaaS（平台即服务）  ← 中间层，提供开发环境（如Heroku）
IaaS（基础设施即服务）← 底层，提供虚拟机（如AWS EC2）
FaaS（函数即服务）  ← 无服务器，按函数调用计费（如AWS Lambda）

11.3 虚拟机热迁移（Live Migration）

场景：数据中心需要维护某台物理服务器，但上面的虚拟机不能停机。
预复制迁移（Pre-copy Memory Migration）流程：

阶段1：迭代复制（虚拟机继续运行）
    源机器                          目标机器
      |── 复制所有内存页 ──────────────>|
      |   （虚拟机同时运行，部分页被修改）
      |── 复制被修改的"脏页" ──────────>|
      |── 再次复制新的脏页 ──────────→ |
      |   （脏页越来越少）
阶段2：短暂暂停（毫秒级）
      |── 暂停虚拟机 ─────────────────|
      |── 复制剩余少量脏页 ──────────→|
      |── 切换网络/存储到目标机器 ────→|
      |── 目标机器恢复虚拟机运行 ──────|

关键优化：大部分内存页不会被频繁修改，所以第一轮复制后，脏页数量迅速下降，最终暂停时间极短（通常不到100毫秒），对用户几乎无感知。

11.4 检查点（Checkpointing）

把虚拟机的完整状态（CPU寄存器、内存、磁盘状态）保存到磁盘，相当于"存档"。
好处：软件出错时，可以回滚到上一个快照，就像没发生过一样。
限制：如果虚拟机正在与远端通信，检查点恢复后，对方可能已经断开连接，无法恢复通话状态。

12. 案例分析：VMware

12.1 VMware 的历史背景

1997年，Stanford 的研究项目 Disco 研究了在大规模多处理器上运行商用OS的问题，发现虚拟机监控器可以优雅地解决很多系统软件难题。
1998年，VMware 公司成立，目标：把虚拟化带到 x86 平台。
主要挑战：

1. x86 不满足 Popek-Goldberg 可虚拟化条件
2. x86 架构极其复杂（四种运行模式、分段机制等）
3. PC 外设种类繁多（成千上万种设备驱动）
4. 需要对用户友好，像普通软件一样安装

12.2 VMware 的虚拟硬件平台设计

核心策略：不尝试模拟真实的底层硬件，而是给每个虚拟机提供一套固定的标准虚拟硬件。

VMware Workstation 虚拟硬件平台（约2000年）:
复用（Multiplexed）:
    虚拟x86 CPU（与真实CPU指令集相同）
    最多512MB连续物理内存
模拟（Emulated）:
    AMD Lance 网卡（10Mbps，经典老款）
    IDE/SCSI 磁盘控制器
    虚拟磁盘（存为宿主文件系统上的文件）
    标准VGA显卡
    串口、打印口、键鼠、软驱 ...

前端/后端分离架构：

虚拟机内部（前端）                宿主OS（后端）
客户OS的IDE驱动                     |
      |                             |
  虚拟IDE控制器（前端模拟）── 读写文件 ──> 宿主文件系统上的虚拟磁盘文件
      |
  客户OS以为在操作真实硬件

好处：虚拟机文件可以在不同物理机之间复制，无需重装驱动，为后来的虚拟机迁移、云计算奠定了基础。

12.3 VMware 宿主架构（Hosted Architecture）

VMware Workstation 由三个独立模块构成：

+────────────────────────────────────────────────────+
|                    宿主OS（如Linux/Windows）         |
|  ┌───────────────────────────────────────────┐      |
|  │  VMX（用户态进程）                          │      |
|  │  - 负责UI显示                              │      |
|  │  - 设备模拟的前端                           │      |
|  │  - 调用宿主OS完成I/O后端（write文件等）      │      |
|  └───────────────────────────────────────────┘      |
|  ┌───────────────────────────────────────────┐      |
|  │  VMX Driver（内核态驱动）                   │      |
|  │  - 负责在宿主OS和VMM之间切换（世界切换）     │      |
|  └───────────────────────────────────────────┘      |
+────────────────────────────────────────────────────+
              ^ 世界切换（World Switch）
+────────────────────────────────────────────────────+
|               VMM（内核态，独立上下文）               |
|  - 负责执行虚拟机指令（直接执行 + 二进制翻译）        |
|  - 异常/中断处理                                    |
|  - 影子页表管理                                     |
|  - 完全控制硬件，宿主OS被临时"移出"内存              |
+────────────────────────────────────────────────────+

12.4 世界切换（World Switch）

普通的进程上下文切换只切换用户空间和寄存器。
世界切换则切换一切：整个地址空间、所有异常处理程序、特权寄存器……

普通上下文切换:
  进程A(用户空间) ←─切换─→ 进程B(用户空间)
  内核空间: 不变
世界切换:
  宿主OS整个地址空间 ←─切换─→ VMM整个地址空间
  包括: 中断表、段描述符、页表基址寄存器 全部切换
  （仅需约45条x86汇编指令完成）

用一个生活类比理解：就像一个人租了别人的房子开派对，派对结束前把所有家具原样复原，让房东一点都看不出异样。

12.5 ESX Server：Type 1 Hypervisor

2001年，VMware 发布面向企业数据中心的 Type 1 Hypervisor：

ESX Server 的创新点：

• CPU 调度：保证每个虚拟机公平获得 CPU，多核虚拟机的各 vCPU 同时调度
• 内存管理：首创气球驱动和透明页共享
• VMotion：全球首个虚拟机热迁移技术（2002年）
• VMFS：专为虚拟机镜像优化的文件系统，2011年演示单台机器每秒100万次磁盘操作

13. 关键概念速查

---

概念	一句话解释
VMM / Hypervisor	管理虚拟机的软件层
Type 1 Hypervisor	直接运行在裸机上的虚拟机管理程序
Type 2 Hypervisor	运行在宿主操作系统上的虚拟机管理程序
Guest OS	运行在虚拟机里的操作系统
Host OS	Type 2 中运行在真实硬件上的操作系统
陷阱与模拟	敏感指令触发陷阱，由Hypervisor模拟执行
二进制翻译	把敏感指令替换为对Hypervisor的调用
半虚拟化	修改客户OS，用Hypercall替代敏感指令
影子页表	Hypervisor维护的额外页表，直接映射GVA→HPA
EPT / 嵌套页表	硬件支持的两级页表遍历，消除影子页表开销
气球驱动	让客户OS主动释放内存，供Hypervisor重分配
去重	共享多个虚拟机中内容相同的内存页
世界切换	VMware的完整上下文切换机制
热迁移	虚拟机在运行中迁移到另一台物理机
容器	OS级虚拟化，共享内核但隔离进程空间
cgroups	Linux 控制组，限制进程资源使用
IaaS/PaaS/SaaS	云服务的三大层次
SR-IOV	硬件层面的I/O设备虚拟化

---

14. 一个完整的C语言演示程序

下面用 C 语言模拟一个极简的"虚拟机概念演示"，展示二进制翻译和陷阱模拟的基本思路：

/*
 * 极简虚拟机概念演示
 * 模拟一个简单的指令集，演示：
 *   1. 普通指令直接执行
 *   2. 敏感指令被拦截并由"Hypervisor"模拟执行
 *
 * 编译: gcc -o minivm minivm.c
 * 运行: ./minivm
 */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
/* ===== 虚拟机指令集定义 ===== */
#define INST_NOP      0x00  /* 空操作，直接执行 */
#define INST_ADD      0x01  /* 加法，直接执行（普通指令） */
#define INST_PRINT    0x02  /* 打印寄存器，直接执行（普通指令） */
#define INST_SET_INT  0x10  /* 设置中断标志（敏感指令！需要拦截） */
#define INST_CLR_INT  0x11  /* 清除中断标志（敏感指令！需要拦截） */
#define INST_LOAD_CR3 0x12  /* 加载页表基址（敏感指令！需要拦截） */
#define INST_HALT     0xFF  /* 停机 */
/* ===== 虚拟CPU状态 ===== */
typedef struct {
    int reg_a;           /* 通用寄存器A */
    int reg_b;           /* 通用寄存器B */
    int interrupt_flag;  /* 中断标志（虚拟的，不影响真实硬件）*/
    int page_table_base; /* 页表基址（虚拟的）*/
    int halted;          /* 是否已停机 */
    int instruction_count;  /* 已执行指令数 */
    int trapped_count;      /* 被拦截的敏感指令数 */
} VirtualCPU;
/* ===== 虚拟机指令格式 ===== */
typedef struct {
    unsigned char opcode;   /* 操作码 */
    int operand1;           /* 操作数1 */
    int operand2;           /* 操作数2 */
} Instruction;
/* ===== 判断指令是否为敏感指令 ===== */
/* 这对应 Popek-Goldberg 理论中"敏感指令"的概念 */
int is_sensitive(unsigned char opcode) {
    return (opcode == INST_SET_INT ||
            opcode == INST_CLR_INT ||
            opcode == INST_LOAD_CR3);
}
/* ===== Hypervisor：模拟执行敏感指令 ===== */
/*
 * 这相当于真实系统中 Hypervisor 的 trap handler：
 * 捕获到敏感指令后，安全地模拟其效果，
 * 但不影响真实的硬件状态。
 */
void hypervisor_emulate(VirtualCPU *vcpu, const Instruction *inst) {
    vcpu->trapped_count++;  /* 记录拦截次数 */
    switch (inst->opcode) {
        case INST_SET_INT:
            /*
             * 真实情况：CLI指令可能需要50+个时钟周期
             * 虚拟化后：只是一个简单的内存写操作，1~3个时钟周期
             * 关键：不真正修改硬件中断，只修改虚拟CPU的标志
             */
            vcpu->interrupt_flag = 1;
            printf("[Hypervisor] 拦截到 SET_INT 指令，"
                   "设置虚拟中断标志=1 (真实硬件中断未受影响)\n");
            break;
        case INST_CLR_INT:
            /* 同上，只修改虚拟标志，不真正关闭硬件中断 */
            vcpu->interrupt_flag = 0;
            printf("[Hypervisor] 拦截到 CLR_INT 指令，"
                   "设置虚拟中断标志=0 (真实硬件中断未受影响)\n");
            break;
        case INST_LOAD_CR3:
            /*
             * 真实情况：修改CR3寄存器会切换整个进程的地址空间
             * 虚拟化后：Hypervisor记录客户OS想要的页表基址，
             *           然后更新影子页表，不让客户OS直接操作真实CR3
             */
            vcpu->page_table_base = inst->operand1;
            printf("[Hypervisor] 拦截到 LOAD_CR3 指令，"
                   "记录客户OS请求的页表基址=0x%X，"
                   "将更新影子页表\n", inst->operand1);
            break;
        default:
            printf("[Hypervisor] 未知的敏感指令: 0x%02X\n", inst->opcode);
            break;
    }
}
/* ===== 直接执行普通指令 ===== */
/* 这模拟"大多数代码可以原生执行"的情况 */
void execute_normal(VirtualCPU *vcpu, const Instruction *inst) {
    switch (inst->opcode) {
        case INST_NOP:
            /* 空操作，什么都不做 */
            break;
        case INST_ADD:
            /* 普通加法，直接在CPU上执行 */
            vcpu->reg_a = vcpu->reg_a + inst->operand1;
            printf("[VM执行] ADD: reg_a = %d + %d = %d\n",
                   vcpu->reg_a - inst->operand1,
                   inst->operand1,
                   vcpu->reg_a);
            break;
        case INST_PRINT:
            /* 打印当前寄存器状态 */
            printf("[VM执行] 寄存器状态: "
                   "reg_a=%d, reg_b=%d, 中断标志=%d\n",
                   vcpu->reg_a, vcpu->reg_b, vcpu->interrupt_flag);
            break;
        case INST_HALT:
            vcpu->halted = 1;
            printf("[VM执行] 虚拟机停机\n");
            break;
        default:
            printf("[VM执行] 未知普通指令: 0x%02X\n", inst->opcode);
            break;
    }
}
/* ===== 虚拟机主执行循环 ===== */
/*
 * 这模拟了 Hypervisor 的指令分发逻辑：
 * - 普通指令：直接执行（高性能路径）
 * - 敏感指令：由 Hypervisor 拦截并模拟（安全路径）
 *
 * 对应真实系统中的：
 *   - 二进制翻译（Software Binary Translation）
 *   - 或 VT-x 的 trap-and-emulate
 */
void run_vm(VirtualCPU *vcpu, const Instruction *program, int prog_len) {
    int pc = 0;  /* 程序计数器（Program Counter）*/
    printf("===== 虚拟机启动 =====\n\n");
    while (pc < prog_len && !vcpu->halted) {
        const Instruction *inst = &program[pc];
        printf("PC=%02d | 指令: 0x%02X | ", pc, inst->opcode);
        vcpu->instruction_count++;
        if (is_sensitive(inst->opcode)) {
            /*
             * 检测到敏感指令！
             * 真实系统：CPU触发陷阱，控制权转移给Hypervisor
             * 本演示：直接调用hypervisor_emulate函数
             */
            printf("【敏感指令被拦截】\n");
            hypervisor_emulate(vcpu, inst);
        } else {
            /*
             * 普通指令，直接执行
             * 真实系统：CPU直接运行，速度接近原生
             */
            execute_normal(vcpu, inst);
        }
        pc++;
    }
    printf("\n===== 虚拟机执行完毕 =====\n");
    printf("总执行指令数: %d\n", vcpu->instruction_count);
    printf("被拦截的敏感指令数: %d\n", vcpu->trapped_count);
    printf("普通指令数: %d\n",
           vcpu->instruction_count - vcpu->trapped_count);
    /* 计算敏感指令占比 */
    if (vcpu->instruction_count > 0) {
        double ratio = (double)vcpu->trapped_count
                       / vcpu->instruction_count * 100.0;
        printf("敏感指令占比: %.1f%%\n", ratio);
        printf("（占比越低，虚拟机性能越接近原生）\n");
    }
}
/* ===== 主函数 ===== */
int main(void) {
    /*
     * 初始化虚拟CPU
     * 对应真实Hypervisor中的 VMCS（虚拟机控制结构）初始化
     */
    VirtualCPU vcpu;
    memset(&vcpu, 0, sizeof(vcpu));
    /*
     * 定义一段"客户OS"程序
     * 混合了普通指令和敏感指令，演示Hypervisor的分发逻辑
     */
    Instruction guest_program[] = {
        /* 普通计算指令 */
        {INST_ADD, 10, 0},      /* reg_a = reg_a + 10 */
        {INST_ADD, 20, 0},      /* reg_a = reg_a + 20 */
        {INST_PRINT, 0, 0},     /* 打印寄存器状态 */
        /* 客户OS尝试关闭中断（进入临界区） */
        {INST_CLR_INT, 0, 0},   /* 敏感！关中断 */
        /* 临界区内的普通操作 */
        {INST_ADD, 5, 0},       /* reg_a = reg_a + 5（临界区内） */
        /* 客户OS尝试修改页表 */
        {INST_LOAD_CR3, 0xDEAD0000, 0},  /* 敏感！修改页表基址 */
        /* 客户OS重新开启中断（退出临界区） */
        {INST_SET_INT, 0, 0},   /* 敏感！开中断 */
        /* 继续普通操作 */
        {INST_ADD, 3, 0},
        {INST_PRINT, 0, 0},     /* 最终寄存器状态 */
        /* 停机 */
        {INST_HALT, 0, 0}
    };
    int prog_len = sizeof(guest_program) / sizeof(guest_program[0]);
    /* 运行虚拟机 */
    run_vm(&vcpu, guest_program, prog_len);
    printf("\n===== 最终虚拟CPU状态 =====\n");
    printf("reg_a = %d\n", vcpu.reg_a);
    printf("reg_b = %d\n", vcpu.reg_b);
    printf("中断标志 = %d\n", vcpu.interrupt_flag);
    printf("页表基址 = 0x%X\n", vcpu.page_table_base);
    return 0;
}

预期输出：

===== 虚拟机启动 =====
PC=00 | 指令: 0x01 | [VM执行] ADD: reg_a = 0 + 10 = 10
PC=01 | 指令: 0x01 | [VM执行] ADD: reg_a = 10 + 20 = 30
PC=02 | 指令: 0x02 | [VM执行] 寄存器状态: reg_a=30, reg_b=0, 中断标志=0
PC=03 | 指令: 0x11 | 【敏感指令被拦截】
[Hypervisor] 拦截到 CLR_INT 指令，设置虚拟中断标志=0 (真实硬件中断未受影响)
PC=04 | 指令: 0x01 | [VM执行] ADD: reg_a = 30 + 5 = 35
PC=05 | 指令: 0x12 | 【敏感指令被拦截】
[Hypervisor] 拦截到 LOAD_CR3 指令，记录客户OS请求的页表基址=0xDEAD0000，将更新影子页表
PC=06 | 指令: 0x10 | 【敏感指令被拦截】
[Hypervisor] 拦截到 SET_INT 指令，设置虚拟中断标志=1 (真实硬件中断未受影响)
PC=07 | 指令: 0x01 | [VM执行] ADD: reg_a = 35 + 3 = 38
PC=08 | 指令: 0x02 | [VM执行] 寄存器状态: reg_a=38, reg_b=0, 中断标志=1
PC=09 | 指令: 0xFF | [VM执行] 虚拟机停机
===== 虚拟机执行完毕 =====
总执行指令数: 10
被拦截的敏感指令数: 3
普通指令数: 7
敏感指令占比: 30.0%
（占比越低，虚拟机性能越接近原生）

15. 总结

虚拟化的本质是：在软件或硬件的帮助下，让一台物理机变成多台逻辑机器。
核心技术演进：

1974年理论基础（Popek-Goldberg）
        |
软件解决方案（二进制翻译，1999年VMware）
        |
硬件支持（Intel VT-x / AMD SVM，2005年）
        |
内存虚拟化硬件（EPT / 嵌套页表，2007年）
        |
OS级虚拟化爆发（Docker，2013年）
        |
云原生 + 无服务器（现在）

$$\text{理想虚拟机}=\text{完全隔离}+\text{原生性能}+\text{对客户OS透明}$$
三者在实践中需要不断权衡，这也是虚拟化技术持续演进的动力所在。

第8章 多处理器系统 — 详细中文解析

本文基于《现代操作系统》第8章，尽量用通俗的语言解释各个概念。

目录

1. 为什么需要多处理器
2. 三种多CPU系统模型
3. 多处理器硬件
4. 多处理器操作系统类型
5. 多处理器同步
6. 多处理器调度
7. 多计算机系统
8. 分布式系统

1. 为什么需要多处理器

1.1 计算速度的瓶颈

从最早的计算机 ENIAC（每秒300次运算）到现在，人类对算力的渴望从未停止。但是，单纯提高时钟频率（让CPU跑得更快）正在遇到物理极限。
根据爱因斯坦的狭义相对论，电信号的传播速度不能超过光速：

• 真空中光速约为 $30\text{cm/ns}$
• 铜线或光纤中约为 $20\text{cm/ns}$
  这意味着：
  $$\text{信号在一个时钟周期内的最大路径长度}=\frac{20\text{cm/ns}}{\text{时钟频率(GHz)}}$$

---

时钟频率	一个周期内信号最远走多远
10 GHz	2 cm
100 GHz	2 mm
1 THz	100 微米

---

CPU越来越小，散热就越来越难，高端 x86 系统上，散热器甚至比 CPU 本体还大。
结论： 从 1 MHz 到 1 GHz，靠改进工艺就能做到；但从 1 GHz 到 1 THz，必须采用全新思路 —— 多处理器并行计算。

2. 三种多CPU系统模型

这三种模型按照"耦合程度"从紧到松排列：

紧耦合 <-----------------------------------------> 松耦合
  |                                                    |
共享内存多处理器     消息传递多计算机          广域分布式系统
(Multiprocessor)  (Multicomputer)        (Distributed System)
  延迟: 1-10 ns      延迟: 10-50 us         延迟: 10-100 ms

模型一：共享内存多处理器（图a）

CPU1  CPU2  CPU3  CPU4
  |     |     |     |
  +-----+-----+-----+
           |
       共享内存 (RAM)

• 所有 CPU 访问同一块物理内存
• 用 LOAD/STORE 指令直接读写
• 程序员视角：和普通单CPU程序几乎一样
• 优点： 编程简单
• 缺点： 大规模时硬件难造且贵

模型二：消息传递多计算机（图b）

[CPU1+内存1]  [CPU2+内存2]  [CPU3+内存3]
      |              |              |
      +------高速互联网络-----------+

• 每个 CPU 只能访问自己的本地内存
• CPU 之间靠发送消息通信
• 优点： 硬件容易制造，可扩展到更大规模
• 缺点： 编程复杂，需要显式处理消息传递

模型三：广域分布式系统（图c）

[完整计算机A]          [完整计算机B]
   (有键盘显示器等)      (有键盘显示器等)
         |                    |
         +--------互联网-------+

• 每个节点是完整的计算机
• 通过互联网通信
• 消息延迟最大（10-100 ms）
• 例子： 云计算集群、P2P网络
  三种模型的延迟差距约 三个数量级（1000倍），就像"一天"和"三年"的区别。

3. 多处理器硬件

3.1 UMA vs NUMA

UMA（一致性内存访问）： 每个 CPU 访问任何内存位置的速度相同。
NUMA（非一致性内存访问）： 访问"近处"的内存比访问"远处"的内存更快。

3.2 基于总线的UMA多处理器

方案一：无缓存（最简单但最差）

CPU1  CPU2  CPU3  CPU4
  |     |     |     |
  +-----+-----+-----+-----+ (总线)
                           |
                        共享内存

问题： 32个CPU同时抢一条总线，总线会成为严重瓶颈，大多数CPU都在等待。

方案二：带缓存（常见方案）

[CPU1+Cache1]  [CPU2+Cache2]  [CPU3+Cache3]
      |                |               |
      +---------总线-------------------+
                       |
                    共享内存

缓存以 缓存行（cache line） 为单位（通常32或64字节）。
缓存一致性问题： 如果 CPU1 修改了某个数据，而这个数据在 CPU2 的缓存中也有一份，怎么办？
解决方案叫 缓存一致性协议（cache-coherence protocol）：

• 缓存行分为"只读"和"读写"两种状态
• 如果某 CPU 要写一个数据，先通知总线，其他所有 CPU 把自己缓存中的那份副本作废
• 这个过程完全由硬件自动完成，程序员感觉不到

方案三：带缓存+私有内存

[CPU1+Cache1+私有内存1]  [CPU2+Cache2+私有内存2]
          |                         |
          +-----------总线----------+
                        |
                     共享内存

把程序代码、常量等只读数据放在私有内存，可共享的变量才放共享内存，进一步减少总线流量。

3.3 使用交叉开关（Crossbar Switch）的UMA

总线方案极限大约只能支持 16到32个CPU。要支持更多，就需要交叉开关：

        内存0  内存1  内存2  内存3
          |      |      |      |
CPU0 ----[X]---[X]---[X]---[X]---
CPU1 ----[X]---[X]---[X]---[X]---
CPU2 ----[X]---[X]---[X]---[X]---
CPU3 ----[X]---[X]---[X]---[X]---
          (X=交叉点开关)

• 每个交叉点是一个小型电子开关（开/关）
• 非阻塞网络： 任何一个CPU和任何一个内存之间都可以同时建立连接，不会互相阻塞
• 缺点： 交叉点数量 = $n^2$，1000个CPU就需要100万个交叉点，代价极高

3.4 多级交换网络（Omega网络）

交叉开关代价太高，Omega网络用更少的硬件实现类似功能：
对于 $n$ 个CPU和 $n$ 个内存，Omega网络需要：
$$\text{交换机总数}=\frac{n}{2}\cdot {\log }_{2}n$$
比交叉开关的 $n^2$ 少得多。
Omega网络路由示例（8个CPU，8个内存）：
CPU 011 访问内存 110 的路径：

1. 第一级开关：取模块号最高位 1 → 走下方输出
2. 第二级开关：取次高位 1 → 走下方输出
3. 第三级开关：取最低位 0 → 走上方输出
4. 到达内存 110
   缺点： Omega网络是阻塞网络 —— 某些访问组合会在同一个开关或线路上产生冲突，需要等待。

3.5 NUMA多处理器

当CPU数量超过100个，就无法保证所有内存访问速度相同了。NUMA的三个关键特性：

1. 所有CPU共享同一地址空间（逻辑上统一）
2. 访问远程内存仍用 LOAD/STORE 指令
3. 访问远程内存比访问本地内存慢

基于目录的CC-NUMA

为了保证缓存一致性，系统维护一个目录，记录每条缓存行在哪里、是否被修改：

节点0            节点1            节点255
[CPU][内存][目录]  [CPU][内存][目录]  [CPU][内存][目录]
      |                 |                  |
      +-------互联网络--+------------------+

工作原理示例（256节点系统）：
地址被分成三部分：
$$\underset{\text{节点号}}{\underbrace{8\text{ bits}}}\underset{\text{块号}}{\underbrace{18\text{ bits}}}\underset{\text{块内偏移}}{\underbrace{6\text{ bits}}}$$

• CPU 20 想读节点36上的第4行缓存
• 目录显示：该缓存行没被缓存 → 从本地RAM取出，发给节点20，更新目录
  目录内存开销计算：
  $$\text{开销比例}=\frac{9\text{ bits}\times 2^{18}}{16\text{ MB}}\approx 1.76\%$$
  基本可以接受。

3.6 多核芯片（Multicore）

根据摩尔定律，芯片上的晶体管越来越多。与其全部用于增大缓存，不如在同一芯片上放多个完整的CPU核心：

       +-----------芯片-----------+
       |  Core0    Core1          |
       |  [L1$]    [L1$]          |
       |     \      /             |
       |      [L2$]               |
       |         |                |
       |       [L3$ 共享]          |
       +-----------+-------------|
                   |
                主内存(RAM)

• AMD EPYC Milan：64核，每核2个硬件线程 = 128虚拟核
• 每核有 32 KB L1指令缓存 + 32 KB L1数据缓存 + 512 KB L2缓存
• 所有核共享 256 MB L3缓存
  多核 = 非常小的多处理器，也叫 CMP（Chip MultiProcessor）。
  SoC（片上系统）： 把GPU、NPU、通用核心等都集成到一块芯片（如苹果M1芯片）。

3.7 众核芯片（Manycore）与GPU

当核心数超过几十上百，进入"众核"领域，典型代表是GPU：

特性	通用CPU	GPU
核心数	几个到几十个	数千个小核心
核心能力	复杂逻辑，单核性能强	简单计算，极度并行
缓存	大量缓存	较少缓存
适合任务	串行任务、复杂逻辑	大量相同计算（数据并行）
编程难度	相对简单	困难（CUDA/OpenGL）

---

GPU 是 SIMD（单指令多数据） 架构：所有核心执行相同指令，但作用于不同数据。
TPU（Tensor Processing Unit）： Google 专为矩阵乘法（机器学习核心运算）设计的处理器。
一致性墙（Coherency Wall）： 当核心数达到1024时，缓存目录条目中的位向量本身就有128字节，和缓存行大小相当，开销不可接受。可能的解决方案：将1024核分成64个"岛"，每岛16个核保持一致性，岛间不保证一致性。

3.8 同步多线程（SMT / 超线程）

一个物理核心可以有多个硬件上下文（超线程/虚拟核）：

物理核心
  +------------------+
  |  超线程0  超线程1  |
  |  [寄存器] [寄存器]|  <- 各自独立的寄存器组
  |                   |
  |   执行单元（共享） |  <- 共享计算资源
  |   L1/L2 缓存（共享）|
  |   TLB（共享）      |
  +------------------+

• 超线程是"几乎一个额外核心"，但代价很低
• 性能提升因工作负载而异，最多可达 30%
• 安全隐患： 共享TLB和缓存可能导致侧信道攻击（Meltdown/Spectre）

4. 多处理器操作系统类型

4.1 每个CPU独立运行操作系统

CPU1(OS1)  CPU2(OS2)  CPU3(OS3)  CPU4(OS4)
    |           |           |           |
    +-------内存（静态分区）--------------+
            [OS代码共享区][数据1][数据2][数据3][数据4]

• 每个CPU有自己的进程表、内存、缓冲区
• 优点： 简单，移植快
• 缺点：
  • CPU间不能动态分配负载（CPU1 空闲，CPU2 过载，无法平衡）
  • 各自独立的磁盘缓冲区可能导致数据不一致
  • 内存分配固定，浪费严重

4.2 主从（Leader-Follower）模型

CPU1（主，跑OS）   CPU2（从）   CPU3（从）   CPU4（从）
      |                |            |            |
      +----------------内存----------+------------+
                  [OS] [用户进程]

• 只有 CPU1 运行操作系统，处理所有系统调用
• 从CPU需要系统调用时，把请求发给主CPU处理
• 优点： 解决了负载不平衡和数据不一致问题
• 缺点： 主CPU是瓶颈。如果10%时间在操作系统中，10个CPU就能让主CPU饱和，20个CPU则完全瓶颈。

4.3 对称多处理（SMP）—— 现代主流方案

CPU1  CPU2  CPU3  CPU4
（任何一个都可以跑OS）
  |     |     |     |
  +-----+-----+-----+
              |
           内存[OS][用户进程]

• 内存中只有一份操作系统代码
• 任何CPU都可以执行操作系统代码
• 用 互斥锁（mutex） 保护共享数据结构
  关键挑战：防止竞态条件
  假设两个CPU同时从就绪队列取进程：

CPU1: 读就绪队列 → 选中进程A
CPU2: 读就绪队列 → 选中进程A  (同一个！)
结果: 两个CPU同时运行进程A，灾难！

解决方案：
方案1 — 大内核锁（Big Kernel Lock）：整个OS代码只允许一个CPU进入，效果类似leader-follower，并发度差。
方案2 — 细粒度锁：把OS分成多个独立的临界区，每个区有自己的锁：

[进程调度器] → 锁A
[文件系统]   → 锁B
[内存管理]   → 锁C
[页错误处理] → 锁D

不同CPU可以同时执行不同的临界区，并发度大幅提升。
难点：死锁问题
如果临界区1需要锁A和锁B，临界区2也需要锁A和锁B，但获取顺序不同：

CPU1: 获得锁A → 等待锁B
CPU2: 获得锁B → 等待锁A
→ 死锁！

预防方案： 给所有锁编号，规定必须按编号从小到大的顺序获取锁。

5. 多处理器同步

5.1 为什么单处理器的方法不够用

单处理器上，进入临界区前"关中断"就够了。但在多处理器上：

• CPU1 关中断 → 只影响CPU1本身
• CPU2 还在跑，照样访问共享数据
• 关中断无效！

5.2 TSL指令（Test and Set Lock）

TSL 是一条原子指令：一次性完成"读出内存值"和"写入1"两个操作，中间不能被打断。
在多处理器上TSL可能失败的情况：

时刻1: CPU1 读内存地址1000，得到 0
时刻2: CPU2 读内存地址1000，得到 0   (CPU1 还没写回！)
时刻3: CPU1 写 1 到地址1000
时刻4: CPU2 写 1 到地址1000
结果: 两个CPU都认为自己成功获得了锁！

正确实现： TSL 执行前必须先锁住总线，完成读+写后再释放总线，确保真正原子性。

5.3 自旋锁与缓存抖动

用 TSL 实现的锁是自旋锁（spin lock）：获取不到锁就一直循环测试（“忙等待”）。
问题： TSL 是写操作，会使其他CPU缓存中的锁副本失效，然后抢占独占的缓存行：

[锁持有者CPU] ←→ 缓存行在两者之间来回传递 ←→ [等待CPU]
   每次TSL都导致一次缓存行传输，大量浪费总线带宽

优化方案：先读后写（Read Before TSL）

/* 优化版自旋等待 */
/* 先纯读，不触发写操作 */
while (lock != 0) { /* 仅读，不导致缓存失效 */ }
/* 读到0后，再用TSL真正获取 */
TSL lock  /* 此时才写 */

大多数时间是读操作，可以在本地缓存中满足，减少总线流量。
二进制指数退避（Binary Exponential Backoff）：

第1次失败 → 等 1 条指令的时间
第2次失败 → 等 2 条指令的时间
第3次失败 → 等 4 条指令的时间
...
第n次失败 → 等 2^(n-1) 条指令的时间（最多等到上限）

私有锁变量方案（最优）：
每个等待CPU在链表中注册一个私有锁变量，只监视自己那个变量：

当前锁持有者: CPU1 (持有真正的锁)
等待队列: CPU2 → CPU3 → CPU4
          (各自自旋在自己的私有变量上)
当CPU1释放锁：通知CPU2的私有变量，CPU2进入临界区
当CPU2释放锁：通知CPU3的私有变量，CPU3进入临界区

效果：完全消除缓存抖动，每次只有一次缓存操作。

5.4 自旋 vs 切换

---

比较项	自旋（Spinning）	切换线程（Switching）
适用场景	锁持有时间短（< 上下文切换时间）	锁持有时间长
开销	浪费CPU周期（空转）	上下文切换开销 + 缓存miss
典型上下文切换时间	—	约 1 ms（切换+切回 = 2 ms）

---

自适应策略（最优）：
系统记录最近几次等待该锁花了多少时间：

• 如果历史平均等待时间 < 2 ms → 继续自旋
• 如果历史平均等待时间 > 2 ms → 立即切换线程
  x86架构的 MONITOR/MWAIT 指令：让线程在等待时进入低功耗状态，直到内存某区域被写入才唤醒，比普通自旋更节能。

6. 多处理器调度

6.1 分时共享（Time Sharing）

最简单：所有CPU共享一个全局就绪队列：

优先级 7: [进程A]
优先级 5: [进程B][进程C]
优先级 4: [进程D][进程E][进程F]
...
              |
    CPU1, CPU2, ... CPU16 竞争取用

优点： 自动负载均衡，绝不会出现"一个CPU空着，另一个满载"。
缺点：

• 多CPU竞争就绪队列本身的锁
• CPU不总是在上次运行进程A的同一个核心上运行A，缓存利用率低
  亲和调度（Affinity Scheduling）： 尽量让线程在上次运行它的CPU上继续运行，最大化缓存命中率。
  实现：两层调度
• 上层：创建进程时分配给某个CPU（基于当前负载）
• 下层：每个CPU只从自己的就绪队列里取任务（缓存亲和性好）
• 自己队列空了才去"偷"其他CPU的任务（负载均衡）
  智能调度（Smart Scheduling）： 一个线程持有自旋锁时，调度器不抢占它（即使时间片到了），让它尽快释放锁，避免其他CPU长时间空转。

6.2 空间共享（Space Sharing）

当一组线程密切协作时，把它们同时分配到多个CPU：

32个CPU:
┌────────────────────┐
│  进程A: 8个CPU      │
├────────────────────┤
│  进程B: 6个CPU      │
├────────────────────┤
│  进程C: 12个CPU     │
├────────────────────┤
│  进程D: 4个CPU      │
├──┬─────────────────┤
│未分配: 2个CPU       │
└──┴─────────────────┘

优点： 无需上下文切换，减少开销。
缺点： 一个CPU因I/O阻塞后，该CPU闲置直到线程醒来（利用率低）。

6.3 群调度（Gang Scheduling）

解决问题：线程A0和A1需要频繁通信，但如果调度错位：

时间片 0 (0-100ms):  CPU0 跑 A0,  CPU1 跑 B1
时间片 1 (100-200ms): CPU0 跑 B0,  CPU1 跑 A1
A0在t=0发消息 → A1直到t=100ms才能收到 → A1回复 → A0直到t=200ms才能收到
结果: 每200ms只能完成一次请求-回复！

群调度解决方案：所有CPU同步时间片，同组线程同时运行：

时间片 0: CPU0=A0, CPU1=A1, CPU2=A2, ... (A的所有线程同时跑)
时间片 1: CPU0=B0, CPU1=B1, CPU2=B2, ... (B的所有线程同时跑)
时间片 2: CPU0=D0, CPU1=D1, ...

这样，A0发消息后A1几乎立即能收到并回复（在同一个时间片内完成多次通信）。

6.4 调度与安全（侧信道攻击）

TLB侧信道攻击原理：
假设加密程序有如下逻辑：

/* 伪代码：根据密钥每一位选择执行哪个函数 */
for (每个密钥位 b) {
    if (b == 0) f0();  /* f0 在页 P0 */
    else        f1();  /* f1 在页 P1 */
}

攻击者在同一核心的另一个超线程上运行：

1. 用大量页面覆盖整个TLB
2. 测量访问每个页面的时间
3. 时间长 → TLB miss → 该页刚被别的线程（受害者）访问过
4. 通过"哪些页很慢"推断密钥序列
   防护措施：

Windows Hyper-V的核心调度器：
同一物理核心的两个超线程，必须来自同一个虚拟机
如果没有，就让第二个超线程空闲

OpenBSD 等操作系统默认禁用超线程以防御此类攻击。

7. 多计算机系统

多计算机 = 每个节点有自己的内存，节点间通过消息传递通信。也叫集群计算机或COW（Clusters Of Workstations）。

7.1 互联拓扑

(a) 星形（单交换机）      (b) 环形
    N - S - N                N - N - N
    |       |                |       |
    N       N                N - N - N
(c) 网格/Grid             (d) 双环面（Grid边缘相连）
    N-N-N-N                  环绕连接
    | | | |
    N-N-N-N
(e) 三维立方体             (f) 超立方体（4D）

超立方体（Hypercube）：

• $n$ 维超立方体有 $2^n$ 个节点
• 直径（任意两节点间最长路径）= $n={\log }_2(\text{节点数})$
  $${\text{直径}}_{\text{超立方体}}={\log }_{2}N\text{vs}{\text{直径}}_{\text{网格}}=2(\sqrt{N}-1)$$
  例：1024节点：
• 超立方体直径 = 10
• 32×32网格直径 = 62（超立方体好6倍以上）
  代价： 超立方体每个节点连接 ${\log }_{2}N$ 条线，连线数量多，成本高。

7.2 两种交换方式

存储转发分组交换（Store-and-Forward）：

CPU1 → [包到达交换机A，完整存储后转发] → [包到达交换机B，完整存储后转发] → CPU2
延迟: 包经过k个跳，每跳需等完整包到达，延迟 = k × T

电路交换（Circuit Switching）：

先建立路径: CPU1 → A → B → CPU2 (预留好通路)
然后数据一路流过，不在中间节点缓冲
延迟: 只有建立路径的一次性开销 + 实际传输时间

虫孔路由（Wormhole Routing）： 把包分成子包，子包到达第一个交换机就开始转发，不等完整包，兼顾两者优点。

7.3 低级通信软件

拷贝次数是性能关键：
理想情况（网络接口映射到用户空间）：

源RAM → 网络接口板 → 目标网络接口板 → 目标RAM  (3次拷贝)

实际情况（网络接口在内核空间）：

用户空间包 → 内核缓冲区 → 网络接口 → 目标网络接口 → 内核缓冲区 → 用户空间  (5次拷贝)

5次拷贝比3次拷贝带宽减半、延迟加倍。
RDMA（远程直接内存访问）：
一台机器直接读写另一台机器的内存，完全绕过操作系统：

机器A的应用程序 --RDMA--> 机器B的应用程序内存
         (不经过任何OS！)

缺点：需要固定（pin）相关内存页，接收方需要轮询某个字节来感知数据到达。

7.4 用户级通信：阻塞 vs 非阻塞调用

阻塞式send（最简单）：

send(dest, &msg);  /* 调用后CPU挂起，直到消息完全发送完毕才返回 */
/* 下一行代码要等消息发完才执行 */

非阻塞式send（四种方案）：

方案	原理	优点	缺点
阻塞发送	等待完成	简单	CPU空等
内核拷贝	先把包拷到内核，立即返回	简单	多一次拷贝
中断通知	发完后发中断告知	无需拷贝	中断难调试
写时复制	发完前标只读，写时才拷	通常无需拷贝	管理复杂

---

弹出线程（Pop-up Thread）： 消息到达时，自动在接收进程中创建一个新线程处理消息，处理完自动销毁。
主动消息（Active Messages）： 消息头中直接包含处理函数地址，消息到达时立即在中断处理程序中调用，零拷贝：

消息格式: [处理函数地址 | 数据]
到达后: 直接调用 处理函数(数据)，不需要额外的缓冲和分派

7.5 远程过程调用（RPC）

核心思想： 让调用远程机器上的函数看起来和调用本地函数一模一样。

客户端（机器1）                    服务端（机器2）
+-----------+                    +------------+
|  客户程序  |                    |   服务程序  |
|  call f() |                    |   f(...):  |
+-----------+                    |     ...    |
      |                          +------------+
      v                                ^
+-----------+                    +------------+
| 客户端桩  | ---网络消息-------> | 服务端桩   |
| (stub)    | <--网络回复-------- | (stub)     |
+-----------+                    +------------+

RPC的6个步骤：

1. 客户程序 调用 客户端桩（本地调用）
2. 客户端桩 把参数打包（marshaling）成消息
3. 内核 把消息从客户机发到服务机
4. 内核 把消息交给服务端桩
5. 服务端桩 解包参数，调用真正的服务函数
6. 返回值按反向路径传回

RPC的四大难题：

1. 指针参数： 客户端的指针在服务端无效，需要"拷贝-恢复（copy-restore）"技术
2. 未知数组大小： C语言数组不知道长度，桩无法序列化
3. 未知参数类型： printf 可以接受任意类型参数，无法处理
4. 全局变量： 客户端和服务端全局变量不共享，调用后行为可能不同

7.6 分布式共享内存（DSM）

核心思想： 用软件制造"共享内存"的假象，即使物理上并不存在共享内存。
工作原理：

• 每台机器有自己的页表
• 访问不存在的页 → 触发缺页异常
• OS从当前持有该页的机器取来该页 → 重新执行失败的指令

机器0               机器1
页0,2,5,9 (本地)    页1,3,6,8,10 (本地)
访问页10 → 缺页!
OS发消息 → 机器1把页10发过来
页10 现在在机器0

假共享（False Sharing）问题：

[  变量A  |  变量B  ]  ← 同一个页面！
     |           |
  CPU1用A      CPU2用B
  CPU1修改A → 整个页面失效
  CPU2需要B → 重新获取整个页面（其实B没变！）
  ...来回传输页面，性能极差

解决： 让编译器把频繁被不同CPU访问的变量放在不同页面。
一致性协议：
写一个被多个机器缓存的页面之前，先通知所有持有副本的机器把副本作废：

机器A要写页X：
  1. 广播"请作废页X"
  2. 等所有机器确认
  3. 机器A修改页X

7.7 多计算机调度与负载均衡

发送方发起算法（Sender-Initiated）：

节点过载时：
  随机选一个节点探测负载
  如果对方负载低 → 把进程迁移过去
  如果对方也忙   → 再探测下一个（最多N次）

问题：系统最忙时（最不需要额外开销），探测流量最大。
接收方发起算法（Receiver-Initiated）：

节点空闲时：
  随机选一个节点问"有没有多余的工作？"
  有 → 接收并运行
  没有 → 最多问N个，如果都没有就暂时空闲

优点：系统轻载时探测流量大（系统有余量），系统重载时很少有空闲节点，探测流量小。
图论算法（确定性算法）：
把进程间通信用带权图表示，求最优划分：

目标: 把进程分配到各节点，使得跨节点的通信流量（弧的权重之和）最小

8. 分布式系统

8.1 三种系统对比

---

特性	多处理器	多计算机	分布式系统
节点配置	CPU	CPU+内存+网卡	完整计算机
外设	全部共享	除磁盘外共享	每节点独立
地理位置	同一机架	同一机房	可遍布全球
节点间通信	共享RAM	专用互联网络	互联网
操作系统	一个，共享	多个，相同	可各不相同
文件系统	一个，共享	一个，共享	各节点独立

---

8.2 中间件（Middleware）

分布式系统用中间件屏蔽底层的不同操作系统和硬件，对应用提供统一接口：

应用程序          应用程序          应用程序
    |                 |                 |
中间件(统一API)   中间件(统一API)   中间件(统一API)
    |                 |                 |
Windows/Intel    Linux/Intel      macOS/ARM
    |                 |                 |
                    网络

8.3 网络基础

以太网（LAN）：
经典以太网用 CSMA/CD 协议：

1. 先听总线（Carrier Sense）
2. 总线空闲才发送
3. 检测到碰撞（Collision Detection）→ 停止发送
4. 等待随机时间后重试（二进制指数退避）
   现代以太网用交换机（Switch）：每台机器独占端口，完全消除碰撞。
   互联网：
   互联网诞生于1969年ARPANET（美国国防部的实验性分组交换网络），设计目标是即使遭受核打击也能继续工作。

• 路由器（Router）： 根据目标IP地址转发数据包
• IP协议： 无连接、不可靠的数据报服务（尽力而为）
• TCP协议： 建立在IP上的可靠、面向连接的字节流服务
• DNS： 把人类可读的域名（如 cs.example.com）转换为IP地址（如 192.168.1.1）

8.4 四种中间件范式

范式一：文档模型 —— 万维网（Web）
把整个分布式系统看成一个超大的超链接文档集合：

每个Web页面有唯一的URL: 协议://域名/路径
浏览器访问页面的步骤:
  1. DNS查询 → 获得IP
  2. TCP连接到80端口
  3. 发送HTTP请求
  4. 接收HTML响应
  5. 渲染页面（获取图片等资源）

范式二：文件系统模型
把分布式系统看成一个大文件系统：

• 上传/下载模型： 先把整个文件拷到本地，操作完再传回去
• 远程访问模型： 文件留在服务器，客户端发命令操作
  Session语义（会话语义）：
• 对打开文件的修改，只有关闭文件后才对其他机器可见
• 如果两个机器同时修改同一文件，最后关闭的那个"赢"
  命名透明性：
• 位置透明（Location Transparency）： 路径名不包含服务器位置信息
• 位置独立（Location Independence）： 文件可以迁移到其他服务器而路径名不变（更难实现）
  范式三：对象模型 —— CORBA
  把一切看作对象，远程调用对象的方法：

客户端                    服务端
  |                         |
客户端存根 → ORB → 网络 → ORB → 服务端骨架 → 对象

ORB（Object Request Broker）隐藏所有底层细节，包括服务器位置、操作系统差异等。
缺点： 每个对象只在一个服务器上，重负载下性能差，只适合小规模系统。
范式四：协调模型 —— Linda / 发布订阅
Linda的元组空间（Tuple Space）：
全局共享的"虚拟黑板"，任何进程都可以存取元组：

/* 存入一个元组 */
out("matrix-1", 1, 6, 3.14);
/* 取出一个匹配的元组（?i 表示任意整数，赋给变量i） */
in("abc", 2, ?i);
/* 读取但不删除 */
read("abc", 2, ?i);
/* 并行计算多个值，结果放入元组空间 */
eval(f(x), g(y));

用Linda实现信号量：

/* Up操作（V） */
out("semaphore S");
/* Down操作（P）—— 如果没有对应元组，自动阻塞等待 */
in("semaphore S");

发布/订阅（Publish/Subscribe）：

生产者 → 发布元组（带层级主题，如 "stock.US.NASDAQ.AAPL"）
                 |
              LAN广播
                 |
           每台机器的守护进程
           (匹配订阅者的兴趣)
                 |
    消费者订阅 "stock.US.*.AAPL" → 收到所有苹果股票数据
    消费者订阅 "stock.US.*.*"    → 收到所有美股数据

生产者和消费者完全解耦，互不知道对方的存在。

附录A：完整C代码示例

A.1 自旋锁实现

#include <stdio.h>
#include <stdint.h>
#include <pthread.h>
#include <stdlib.h>
#include <unistd.h>
/*
 * 简单自旋锁
 * 用 GCC 内建原子操作模拟 TSL 指令
 */
/* 锁的类型：0 = 未锁，1 = 已锁 */
typedef int spinlock_t;
/* 初始化锁为未锁状态 */
void spinlock_init(spinlock_t *lock) {
    *lock = 0;
}
/*
 * 获取自旋锁（忙等待版本）
 * __sync_lock_test_and_set: 原子地将 *lock 设为 1，返回旧值
 * 如果旧值是 1（已锁），就一直循环
 */
void spinlock_lock(spinlock_t *lock) {
    /* 先纯读检查，减少总线流量（Read Before TSL 优化） */
    while (*lock != 0) {
        /* 空等，等锁被释放 */
    }
    /* 看到锁空闲了，用原子操作真正获取 */
    while (__sync_lock_test_and_set(lock, 1) != 0) {
        /* 可能有竞争，继续等 */
        while (*lock != 0) { /* 再次等待 */ }
    }
}
/*
 * 释放自旋锁
 * __sync_lock_release: 原子地将 *lock 设为 0，并生成内存屏障
 */
void spinlock_unlock(spinlock_t *lock) {
    __sync_lock_release(lock);
}
/* ---- 带指数退避的自旋锁 ---- */
#define MAX_BACKOFF 1024  /* 最大退避等待次数 */
void spinlock_lock_backoff(spinlock_t *lock) {
    int backoff = 1;  /* 初始退避量 */
    while (1) {
        /* 先纯读 */
        while (*lock != 0) { /* 等待 */ }
        /* 尝试原子获取 */
        if (__sync_lock_test_and_set(lock, 1) == 0) {
            return;  /* 成功获得锁 */
        }
        /* 失败：等待 backoff 次循环后再试 */
        for (int i = 0; i < backoff; i++) {
            /* 空循环，模拟等待 */
        }
        /* 指数增加退避量，但不超过上限 */
        if (backoff < MAX_BACKOFF) {
            backoff *= 2;
        }
    }
}
/* ---- 测试代码 ---- */
spinlock_t g_lock;  /* 全局锁 */
int g_counter = 0;  /* 共享计数器，需要锁保护 */
/* 线程函数：每个线程对计数器增加 1000 次 */
void *thread_func(void *arg) {
    int thread_id = *(int *)arg;
    for (int i = 0; i < 1000; i++) {
        spinlock_lock(&g_lock);     /* 进入临界区 */
        g_counter++;                /* 修改共享数据 */
        spinlock_unlock(&g_lock);   /* 退出临界区 */
    }
    printf("线程 %d 完成\n", thread_id);
    return NULL;
}
int main(void) {
    spinlock_init(&g_lock);  /* 初始化锁 */
    int num_threads = 4;
    pthread_t threads[4];
    int thread_ids[4];
    printf("启动 %d 个线程，每个对计数器+1000\n", num_threads);
    printf("预期结果: %d\n", num_threads * 1000);
    /* 创建线程 */
    for (int i = 0; i < num_threads; i++) {
        thread_ids[i] = i;
        pthread_create(&threads[i], NULL, thread_func, &thread_ids[i]);
    }
    /* 等待所有线程结束 */
    for (int i = 0; i < num_threads; i++) {
        pthread_join(threads[i], NULL);
    }
    printf("最终计数器值: %d\n", g_counter);
    if (g_counter == num_threads * 1000) {
        printf("正确！自旋锁工作正常\n");
    } else {
        printf("错误！存在竞态条件\n");
    }
    return 0;
}
/*
 * 编译方法:
 * gcc -o spinlock spinlock.c -lpthread
 *
 * 运行:
 * ./spinlock
 */

A.2 简单消息传递模拟（多计算机通信）

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>
#include <unistd.h>
/*
 * 模拟多计算机节点间的消息传递
 * 用共享内存 + 互斥锁模拟网络通信队列
 */
#define MAX_NODES    4      /* 节点数量 */
#define MAX_MSG_LEN  256    /* 消息最大长度 */
#define QUEUE_SIZE   10     /* 每个节点的消息队列大小 */
/* 消息结构 */
typedef struct {
    int   src;               /* 源节点编号 */
    int   dst;               /* 目标节点编号 */
    char  data[MAX_MSG_LEN]; /* 消息内容 */
} Message;
/* 每个节点的消息队列 */
typedef struct {
    Message       msgs[QUEUE_SIZE]; /* 消息缓冲区（环形队列） */
    int           head;             /* 队列头（读指针） */
    int           tail;             /* 队列尾（写指针） */
    int           count;            /* 当前队列中的消息数 */
    pthread_mutex_t lock;           /* 保护队列的互斥锁 */
    pthread_cond_t  not_empty;      /* 条件变量：队列非空 */
    pthread_cond_t  not_full;       /* 条件变量：队列未满 */
} MsgQueue;
/* 全局：每个节点一个消息队列 */
MsgQueue node_queues[MAX_NODES];
/* 初始化节点消息队列 */
void init_node(int node_id) {
    MsgQueue *q = &node_queues[node_id];
    q->head  = 0;
    q->tail  = 0;
    q->count = 0;
    pthread_mutex_init(&q->lock, NULL);
    pthread_cond_init(&q->not_empty, NULL);
    pthread_cond_init(&q->not_full, NULL);
}
/*
 * 发送消息：把消息放入目标节点的队列
 * 如果队列满，阻塞等待（模拟阻塞式send）
 */
void send_msg(int src, int dst, const char *data) {
    MsgQueue *q = &node_queues[dst];  /* 目标节点的队列 */
    pthread_mutex_lock(&q->lock);
    /* 队列满时等待 */
    while (q->count == QUEUE_SIZE) {
        pthread_cond_wait(&q->not_full, &q->lock);
    }
    /* 把消息放入队列尾部 */
    Message *m = &q->msgs[q->tail];
    m->src = src;
    m->dst = dst;
    strncpy(m->data, data, MAX_MSG_LEN - 1);
    m->data[MAX_MSG_LEN - 1] = '\0';
    q->tail = (q->tail + 1) % QUEUE_SIZE;  /* 移动尾指针（环形） */
    q->count++;
    printf("[节点%d → 节点%d] 发送: \"%s\"\n", src, dst, data);
    pthread_cond_signal(&q->not_empty);  /* 通知接收方有消息了 */
    pthread_mutex_unlock(&q->lock);
}
/*
 * 接收消息：从自己的队列取出消息
 * 如果队列空，阻塞等待（模拟阻塞式receive）
 */
void receive_msg(int my_id, Message *out_msg) {
    MsgQueue *q = &node_queues[my_id];  /* 自己的队列 */
    pthread_mutex_lock(&q->lock);
    /* 队列空时等待 */
    while (q->count == 0) {
        pthread_cond_wait(&q->not_empty, &q->lock);
    }
    /* 从队列头部取出消息 */
    *out_msg = q->msgs[q->head];
    q->head = (q->head + 1) % QUEUE_SIZE;  /* 移动头指针 */
    q->count--;
    pthread_cond_signal(&q->not_full);  /* 通知发送方队列有空间了 */
    pthread_mutex_unlock(&q->lock);
}
/* ---- 节点线程函数 ---- */
/* 节点参数 */
typedef struct {
    int node_id;      /* 本节点编号 */
    int partner_id;   /* 通信对端编号 */
    int is_initiator; /* 是否主动发消息的一方 */
} NodeArgs;
void *node_thread(void *arg) {
    NodeArgs *na = (NodeArgs *)arg;
    int me = na->node_id;
    int partner = na->partner_id;
    if (na->is_initiator) {
        /* 发起方：先发一条消息，等对方回复 */
        char buf[64];
        for (int i = 0; i < 3; i++) {
            snprintf(buf, sizeof(buf), "请求 #%d 来自节点%d", i, me);
            send_msg(me, partner, buf);    /* 发送 */
            Message reply;
            receive_msg(me, &reply);       /* 等回复 */
            printf("[节点%d] 收到回复: \"%s\"\n", me, reply.data);
        }
    } else {
        /* 响应方：收到消息后回复 */
        for (int i = 0; i < 3; i++) {
            Message req;
            receive_msg(me, &req);         /* 等请求 */
            printf("[节点%d] 收到请求: \"%s\"\n", me, req.data);
            char reply_buf[64];
            snprintf(reply_buf, sizeof(reply_buf), "回复 #%d 来自节点%d", i, me);
            send_msg(me, req.src, reply_buf);  /* 发回复 */
        }
    }
    return NULL;
}
int main(void) {
    printf("=== 多节点消息传递模拟 ===\n\n");
    /* 初始化所有节点 */
    for (int i = 0; i < MAX_NODES; i++) {
        init_node(i);
    }
    /* 创建4个节点线程：节点0和1互相通信，节点2和3互相通信 */
    pthread_t threads[MAX_NODES];
    NodeArgs args[MAX_NODES];
    /* 节点0：主动发消息 */
    args[0] = (NodeArgs){ .node_id = 0, .partner_id = 1, .is_initiator = 1 };
    /* 节点1：响应方 */
    args[1] = (NodeArgs){ .node_id = 1, .partner_id = 0, .is_initiator = 0 };
    /* 节点2：主动发消息 */
    args[2] = (NodeArgs){ .node_id = 2, .partner_id = 3, .is_initiator = 1 };
    /* 节点3：响应方 */
    args[3] = (NodeArgs){ .node_id = 3, .partner_id = 2, .is_initiator = 0 };
    for (int i = 0; i < MAX_NODES; i++) {
        pthread_create(&threads[i], NULL, node_thread, &args[i]);
    }
    for (int i = 0; i < MAX_NODES; i++) {
        pthread_join(threads[i], NULL);
    }
    printf("\n所有节点通信完毕\n");
    /* 清理资源 */
    for (int i = 0; i < MAX_NODES; i++) {
        pthread_mutex_destroy(&node_queues[i].lock);
        pthread_cond_destroy(&node_queues[i].not_empty);
        pthread_cond_destroy(&node_queues[i].not_full);
    }
    return 0;
}
/*
 * 编译方法:
 * gcc -o msgpass msgpass.c -lpthread
 *
 * 运行:
 * ./msgpass
 */

附录B：关键概念速查表

---

概念	一句话解释
UMA	所有CPU访问内存速度相同
NUMA	访问本地内存比远程内存快
缓存一致性	多个缓存中的同一数据保持同步
TSL	原子的"读-置1"指令，用于实现锁
自旋锁	获取不到就一直循环等待的锁
缓存抖动	缓存行在多个CPU间不断传递，浪费带宽
群调度	相关线程同时在不同CPU上运行
DSM	用软件在无共享内存的机器间模拟共享内存
RPC	把远程函数调用伪装成本地调用
中间件	分布式系统中屏蔽底层差异的软件层
Linda元组空间	全局共享的虚拟黑板，用于进程协调
发布/订阅	生产者发布消息，消费者按主题订阅接收
超线程(SMT)	一个物理核模拟多个逻辑核
众核/GPU	数千个小核心，适合高度并行计算
RDMA	绕过OS直接读写远程机器内存

---

附录C：系统结构演示图

C.1 SMP操作系统中的锁竞争

CPU0          CPU1          CPU2          CPU3
  |             |             |             |
  | 想进临界区  | 已在临界区  | 想进临界区  | 想进临界区
  |             |             |             |
  +-- 等待锁 --+-- 持有锁 --+-- 等待锁 --+-- 等待锁
                |
            执行OS代码
                |
            释放锁
                |
      (CPU0, CPU2, CPU3竞争获取锁)

C.2 Omega网络路由路径

CPU端                          内存端
000 --+-- [1A] --+-- [2A] --+-- [3A] --> 000
001 --+          |          +-- [3B] --> 001
010 --+-- [1B] --+-- [2B] --+-- [3A] --> 010 (路径a: CPU011->内存110)
011 --+          |    ^     +-- [3B] --> 011
100 --+-- [1C] --+-- [2C] --+-- [3C] --> 100
101 --+          |          +-- [3D] --> 101
110 --+-- [1D] --+-- [2D] --+-- [3C] --> 110
111 --+               ^    +-- [3D] --> 111
          路径a: 011->1D->2D->3C->110
          路径b: 001->1A->2A->3A->001

C.3 DSM缺页处理流程

机器0 (CPU想访问页10)          机器1 (持有页10)
1. CPU访问页10
      |
2. MMU: 页10不在本地 → 缺页异常
      |
3. OS发消息 ─────────────────> 4. 收到请求
                                      |
                               5. 把页10发回来
      |  <──────────────────────────
6. 收到页10，建立映射
      |
7. 重新执行之前失败的指令
      |（这次成功了）

操作系统安全 —— 详细中文笔记

本文对应教材第9章，力求用最通俗的语言把每个概念讲清楚。

目录

1. 安全基础概念
2. CIA 安全三元组
3. 安全设计原则
4. 操作系统结构与安全
5. 可信计算基（TCB）
6. 访问控制：保护域与矩阵
7. 访问控制列表（ACL）
8. 能力列表（Capabilities）
9. 多级安全模型
10. 密码学基础
11. 用户认证
12. 软件漏洞与攻击
13. 硬件漏洞
14. 内部攻击
15. 操作系统加固

1. 安全基础概念

为什么需要安全？

想象你的电脑里存着：

• 纳税申报表、银行账号
• 公司商业计划、竞争情报
• 私人照片、情书
  这些都是"宝贝"，需要保护。随着越来越多的信息存入计算机，保护这些信息变得极其重要。

几个关键术语

---

术语	中文	解释
Security	安全性	整体问题——防止未授权访问或篡改
Protection Domain	保护域	一个进程/用户被允许执行哪些具体操作的集合
Security Mechanism	安全机制	操作系统用来保护信息的具体技术手段
Security Domain	安全域	需要安全隔离的软件单元，如进程、内核、虚拟机
Vulnerability	漏洞	软件中存在安全隐患的 Bug
Exploit	利用代码	专门触发某个漏洞的输入或程序
Malware	恶意软件	各种恶意程序的统称

---

恶意软件分类

Virus（病毒）
  - 需要"宿主"程序（嵌入其他可执行文件）
  - 需要用户操作触发（如点击附件）
Worm（蠕虫）
  - 自我传播，不需要用户帮忙
  - 自动扫描网络，找到有漏洞的机器就感染
Trojan Horse（特洛伊木马）
  - 伪装成合法软件（免费游戏、破解软件）
  - 安装后悄悄开后门，把控制权交给攻击者

2. CIA 安全三元组

这是信息安全最核心的三个目标，简称 CIA（巧合的是，和美国中央情报局缩写一样）。

        保密性 Confidentiality
           /
          /
         /
        +-------------- 完整性 Integrity
         \
          \
           \
        可用性 Availability

2.1 保密性（Confidentiality）

一句话：秘密的东西只有被允许的人才能看到。

• 目标：防止数据被未授权者获取
• 威胁：数据泄露（Exposure of data）
• 例子：你的工资单，只有你和HR能看，同事不能看

2.2 完整性（Integrity）

一句话：数据不能被未授权者修改、删除或伪造。

• 目标：保证数据从存入到取出保持原样
• 威胁：数据篡改（Tampering with data）
• 例子：你的成绩单，老师录入后，学生不能私自改分

2.3 可用性（Availability）

一句话：系统要能正常提供服务，不能被人搞垮。

• 目标：防止拒绝服务攻击（DoS）
• 威胁：拒绝服务（Denial of Service）
• 例子：黑客向服务器每秒发 10000 个请求，服务器被淹没，合法用户反而无法访问
  拒绝服务的数学：
  假设处理一个请求需要 $100\mu s$，即 $10^{-4}$ 秒。那么每秒能处理的请求数为：
  $$\text{最大处理能力}=\frac{1}{10^{-4}}=10^4=10000\text{ 请求/秒}$$
  只要攻击者能发出超过这个速率的请求，服务器就会被瘫痪。

---

安全目标	对应威胁
保密性	数据泄露
完整性	数据篡改
可用性	拒绝服务

---

3. 安全设计原则

这8条原则是1975年由 Saltzer 和 Schroeder 提出的，几十年过去了，依然是"金科玉律"。

原则一：经济性（简单性）原则

核心思想：系统越简单越安全。

• 复杂系统 Bug 更多，用户容易用错
• 简单系统攻击面小（攻击面 = 攻击者能接触到的所有入口）
• 不需要的功能，坚决不加
• 现代系统动辄几百万行代码，Bug 无处不在

类比：一栋只有一扇门的房子，比有100扇窗户的房子更容易守护。

原则二：默认失效安全原则

核心思想：默认情况下，拒绝一切访问；只有明确授权的才允许。

• 好比：门默认是锁着的，你得有钥匙才能进
• 不要试图列出"哪些情况下拒绝"，而是列出"哪些情况下允许"

原则三：完全仲裁原则

核心思想：对每一个资源的每一次访问，都要检查权限。

• 不能因为"上次查过了"就跳过本次检查
• 每次访问都必须有明确的权限来源

原则四：最小权限原则（POLA）

核心思想：每个子系统只拥有完成自己任务所需的最小权限，不多给一分。

• 即使这个子系统被攻击，攻击者获得的权限也是最小的
• 好比：前台收银员不需要有公司财务室的钥匙

原则五：权限分离原则

核心思想：把系统拆成多个符合最小权限原则的小组件，而不是一个大组件拥有所有权限。

• 一个组件被攻破，不影响其他组件
• 好比：银行出纳和金库管理员各司其职，一个人出问题不影响全局

原则六：最小公共机制原则

核心思想：尽量减少被多个用户共享的机制。

• 共享的东西越多，信息泄露的通道（侧信道）就越多
• 例：能在用户空间实现的功能，就不要放进内核（内核的全局变量被所有用户共享）

原则七：开放设计原则

核心思想：安全不应该依赖"设计保密"，算法应该公开，只有密钥保密。

• 来自密码学的 Kerckhoffs 原则（1883年）：即使敌人知道你用的加密算法，也不能破解，因为他们不知道密钥
• 反例：“安全靠混淆”（Security by Obscurity）—— 这是业余做法，迟早被破解

真正的安全：公开算法 + 保密密钥。

原则八：心理可接受性原则

核心思想：安全措施要易用，用户能理解为什么需要这些措施。

• 太复杂的安全措施，用户会绕过或不遵守
• 好比：要求用户每天换20位随机密码 —— 大家都会把密码贴在显示器上

4. 操作系统结构与安全

操作系统的架构设计直接影响其安全性。

4.1 无隔离架构（嵌入式/早期系统）

+------------------------------------------+
|  应用代码 + 操作系统代码  （同一个域）    |
+------------------------------------------+

• 所有代码都有最高权限
• 没有权限分离，没有最小权限
• 一个Bug就能搞垮整个系统

4.2 宏内核架构（Linux、Windows）

+------------------------------------------+
|         用户进程（低权限）               |
+------------------------------------------+
|     内核（高权限，数百万行代码）         |
|   核心功能 + 驱动程序 + 文件系统 + ...  |
+------------------------------------------+
|              硬件                        |
+------------------------------------------+

• 用户进程和内核之间有隔离
• 但内核本身是一个大单体
• 内核中任何一行代码有漏洞，整个系统完蛋
• 第三方驱动程序Bug多，风险极高（如打印机驱动）

4.3 微内核架构（MINIX 3）

+----+  +----+  +----+  +----+
|进程|  |内存|  |文件|  |驱动|   ← 各自独立，互相隔离
|管理|  |管理|  |系统|  |程序|
+----+  +----+  +----+  +----+
+------------------------------------------+
|    微内核（极小，约15000行代码）          |
+------------------------------------------+
|              硬件                        |
+------------------------------------------+

• 内核极小，TCB极小，易于验证
• 各组件用IPC通信，即使驱动被攻破也不影响内核
• 代价：IPC通信比函数调用慢

4.4 Unikernel 架构

• 为单个应用定制最小化内核
• 去掉一切用不到的功能，攻击面极小
• 代价：不通用

5. 可信计算基（TCB）

什么是 TCB？

可信计算基（Trusted Computing Base，TCB） = 系统中必须正确工作、才能保证整体安全的所有软硬件的集合。

类比：TCB 就是整栋大楼最核心的那道防火门。门是好的，整栋楼的防火安全就有保障。

TCB 包含什么？

TCB 典型组成部分：
  - 大部分硬件（除了不影响安全的 I/O 设备）
  - 操作系统内核的一部分（进程创建、切换、内存管理等）
  - 具有超级用户权限的程序（如 UNIX 中的 SETUID root 程序）

引用监视器（Reference Monitor）

TCB 的重要组成部分是引用监视器：

用户进程
   |
   | 所有涉及安全的系统调用（打开文件、创建进程等）
   v
+------------------+
|   引用监视器     |  ← 检查：允许还是拒绝？
+------------------+
   |
   v
  操作系统内核（TCB 内部）

引用监视器的作用：

• 集中处理所有安全决策
• 无法被绕过
• 大多数实际操作系统没有严格实现这一点，这是它们不安全的原因之一

TCB 大小与安全性

$$\text{安全性}\propto \frac{1}{\text{TCB 大小}}$$

系统	TCB 大小	安全性
Linux/Windows（宏内核）	数百万行代码	低
MINIX 3（微内核）	约 15000 行代码	高
Unikernel	极少代码	很高（针对特定应用）

---

6. 访问控制：保护域与矩阵

6.1 保护域（Protection Domain）

保护域 = 一组(对象, 权限)对的集合，表示"谁能对什么做什么"。

• 每个进程在某一时刻运行在某个保护域中
• UNIX 中，保护域由 (UID, GID) 决定

6.2 保护矩阵

用一张大表格来表示所有访问权限：

• 行 = 域（用户/进程）
• 列 = 对象（文件、设备等）
• 单元格 = 该域对该对象的权限（R读、W写、X执行）

           File1   File2   File3   File4   File5   File6   Printer1  Plotter2
域1         R       RW      -       -       -       -       W         -
域2         RW      -       R       RWX     RW      -       W         -
域3         -       -       -       -       -       RWX     -         W

保护矩阵告诉系统：某个域发起某种访问，允不允许。
问题：矩阵非常稀疏（大多数格子是空的），直接存储浪费空间。
解决方案：按行存储 → 能力列表；按列存储 → 访问控制列表。

7. 访问控制列表（ACL）

概念

ACL（Access Control List，访问控制列表） = 按列存储保护矩阵，每个对象附带一个列表，说明哪些用户有什么权限。

文件 F1 的 ACL：
  [用户A: 读写]  [用户B: 只读]
文件 F2 的 ACL：
  [用户A: 只读]  [用户B: 读写]  [用户C: 只读]
文件 F3 的 ACL：
  [用户B: 读写执行]  [用户C: 读执行]

UNIX 中的 ACL

UNIX 传统权限（rwxrwxrwx）是简化版 ACL：

-rw-r----- 1 herbertb staff 6 Nov 20 11:05 hello.txt
 ^^^        所有者(herbertb): 读写
    ^^^     组(staff): 只读
       ^^^  其他人: 无权限

扩展 ACL（精细控制）：

# 给 yossarian 用户添加读写权限，不影响原有权限
setfacl -m u:yossarian:rw hello.txt

支持组和通配符

ACL 示例（支持组）：
  UID=anna,  GID=*  : 无权限   ← 先匹配，优先级高
  UID=*,     GID=*  : 读写     ← 除 anna 外，所有人有读写权
规则：按顺序匹配，找到第一个匹配就停止
结果：anna 没有权限，其他人有读写权

ACL 的优缺点

---

优点	缺点
可以精细撤销某个用户的权限	授权给所有用户时，需要枚举所有人
直观，大多数用户熟悉	文件已打开时修改ACL，对已打开的文件不立即生效

---

8. 能力列表（Capabilities）

概念

能力列表（Capability List，C-list） = 按行存储保护矩阵，每个进程/用户有一个列表，说明自己能访问哪些对象。

用户A的C-list：
  [F1: 读]  [F2: 读]
用户B的C-list：
  [F1: 读]  [F2: 读写]  [F3: 读写执行]
用户C的C-list：
  [F2: 只读]  [F3: 读执行]

每一项叫做一个能力（Capability），包含：对象标识符 + 权限位图。

能力的保护

能力必须防止用户伪造！三种保护方式：
方式1：标记架构（Tagged Architecture）

• 每个内存字有一个额外的"标记位"，表示这个字是否是能力
• 只有内核可以修改标记位，用户程序无法伪造
  方式2：内核管理（Kernel-managed）
• 能力存在内核中，用户只能用"能力编号"引用
• 类似 UNIX 的文件描述符（fd）
  方式3：密码保护（Cryptographic Protection）
  服务器为每个对象生成一个能力，包含：

+--------+--------+--------+----------------------------+
| 服务器 |  对象  |  权限  |  f(对象, 权限, 随机数)     |
+--------+--------+--------+----------------------------+

其中 $f$ 是单向函数：
$$\text{能力的第4字段}=f(\text{对象号},\text{权限位},\text{秘密随机数})$$

• 用户无法伪造，因为不知道服务器保存的秘密随机数
• 用户可以请求更弱的能力（减少权限），但不能增加权限

ACL vs 能力 对比

---

特性	ACL	能力
效率	需要搜索ACL列表	直接用能力，无需搜索，效率高
撤销权限	简单，修改ACL即可	困难，需找到所有已发出的能力
封装进程	困难	容易
常见场景	Windows、UNIX	L4内核、FreeBSD Capsicum

---

9. 多级安全模型

9.1 Bell-LaPadula 模型（保密性）

主要用于军事场景，目标是防止信息泄露（保密性）。
安全级别：公开 < 机密 < 秘密 < 绝密
两条规则：

1. 简单安全属性（no read up）：运行在安全级别 $k$ 的进程，只能读取级别 $\le k$ 的对象。
   • 下级不能读上级的文件（中尉看不了将军的文件）
2. 星号属性（no write down）：运行在安全级别 $k$ 的进程，只能写入级别 $\ge k$ 的对象。
   • 上级不能把秘密写到低级别的地方（将军不能把机密内容写进中尉的文件）
     图示：

级别4    进程E        对象6（级别3）
          |           |
          | 读(向下)  | 读(向下)
级别3    进程C        对象3（级别3）
          |           |
          ^ 写(向上) ^ 写(向上)
级别2    进程B        对象1（级别1）
          |
级别1    进程A        对象2（级别1）
规则：读箭头向下或水平，写箭头向上或水平
信息只能向上流动，不会向下泄露

口诀：读下，写上（Read Down, Write Up）

9.2 Biba 模型（完整性）

与 Bell-LaPadula 相反，目标是保证数据完整性（防止低质量数据污染高质量数据）。
两条规则：

1. 简单完整性属性（no write down）：运行在级别 $k$ 的进程，只能写入级别 $\le k$ 的对象。
2. 完整性星号属性（no read down）：运行在级别 $k$ 的进程，只能读取级别 $\ge k$ 的对象。
   口诀：读上，写下（Read Up, Write Down）—— 与 Bell-LaPadula 恰好相反

---

模型	目标	读	写
Bell-LaPadula	保密性	只读下级（read down）	只写上级（write up）
Biba	完整性	只读上级（read up）	只写下级（write down）

---

两者相互矛盾，难以同时满足。

10. 密码学基础

10.1 基本概念

明文（Plaintext P）
     |
     | 加密密钥 KE
     v
密文（Ciphertext C） = E(P, KE)
     |
     | 解密密钥 KD
     v
明文（Plaintext P） = D(C, KD)

$$C=E(P,K_E)$$
$$P=D(C,K_D)$$
Kerckhoffs 原则：算法公开，密钥保密。

10.2 对称密钥密码（Secret-Key Cryptography）

• 加密密钥 = 解密密钥（共享同一个密钥）
• 优点：速度快
• 缺点：双方必须事先安全地共享密钥
• 安全要求：密钥至少 256 位
  密钥空间大小：
  $$\text{密钥空间}=2^{256}\approx 1.2\times 10^{77}$$
  这个数字大约是宇宙中所有原子数量 $(\approx 10^{78})$ 的十分之一，暴力破解不可能。

10.3 公钥密码（Public-Key Cryptography）

• 每个人有一对密钥：公钥（公开） + 私钥（保密）
• 用对方的公钥加密，只有对方的私钥能解密
• 优点：无需提前共享密钥
• 缺点：比对称密钥慢约1000倍
  典型算法：RSA
• 基于大整数分解的困难性
• 乘法容易，分解难：
  $$n=p\times q\text{（已知 p、q，乘法容易）}$$
  $$\text{已知 n，分解出 p、q 极其困难}$$
  实际使用：用公钥密码安全交换对称密钥，然后用对称密钥加密实际数据。

10.4 数字签名

目的：证明文件确实来自你，且未被篡改（不可抵赖）。
流程：

发送方：
  文件
   |
   | 哈希函数（如 SHA-256）
   v
  哈希值（固定长度，如32字节）
   |
   | 用发送方【私钥】加密
   v
  签名块
   |
   | 附加到文件末尾，一起发送
   v
  (文件 + 签名块)
接收方：
  收到 (文件 + 签名块)
   |
   +-- 对文件重新计算哈希值 A
   +-- 用发送方【公钥】解密签名块 → 得到哈希值 B
   |
   | 比较 A 和 B
   v
  A == B → 文件真实且未被篡改
  A != B → 文件被篡改或签名是假的

哈希函数性质：给定 $x$，计算 $y=f(x)$ 容易；给定 $y$，找到 $x$ 计算上不可行。
$$\text{SHA-256 输出}=256\text{ 位}=32\text{ 字节（固定长度）}$$

11. 用户认证

认证方式分三类：

类别	说明	例子
你知道的东西	只有你知道的信息	密码、PIN
你拥有的东西	只有你持有的物品	银行卡、智能卡、手机
你本身是什么	你的生物特征	指纹、面部识别、虹膜

---

11.1 密码安全

UNIX 密码存储方案（加盐哈希）：
不存储明文密码，存储 f(密码 + 盐值)。

/* UNIX 密码文件示例（概念演示） */
/* 格式：用户名, 盐值, 加密后的(密码+盐值) */
/*
Bobbie, 4238, e(Dog, 4238)
Tony,   2918, e(6%%TaeFF, 2918)
Laura,  6902, e(Shakespeare, 6902)
*/

为什么要加盐？
不加盐时，攻击者可以预先计算所有常见密码的哈希值（彩虹表），然后直接查表。
加盐后，攻击者必须对每个盐值分别计算：若盐值有 $n$ 位，则工作量增加 $2^n$ 倍。UNIX 使用 12 位盐，工作量增加 $2^{12}=4096$ 倍。
$$\text{加盐后攻击复杂度}=2^n\times \text{原始复杂度}$$
现代 UNIX（Linux）额外措施：

• 加密后的密码存在 /etc/shadow 文件，只有 root 可读
• /etc/passwd 可被所有人读，但里面密码字段只有 x（占位符）

11.2 一次性密码（Lamport 方案）

用于解决"在不安全网络上安全登录"的问题。
算法（设 $n=4$，单向函数为 $f$）：

1. 用户选择秘密密码 $s$
2. 生成密码序列：
   $$P_1=f(f(f(f(s))))=f^4(s)$$
   $$P_2=f(f(f(s)))=f^3(s)$$
   $$P_3=f^2(s),P_4=f(s)$$
3. 服务器存储 $P_0=f(P_1)=f^5(s)$
   登录过程：

• 第1次登录：用户发送 $P_1$，服务器计算 $f(P_1)$ 是否等于 $P_0$，验证后存入 $P_1$
• 第2次登录：用户发送 $P_2$，服务器计算 $f(P_2)$ 是否等于 $P_1$，验证后存入 $P_2$
  安全性：即使攻击者截获了 $P_i$，也无法计算出 $P_{i+1}$（单向函数不可逆），截获的密码只能用一次，下次就失效了。

12. 软件漏洞与攻击

12.1 缓冲区溢出攻击（Buffer Overflow）

这是历史上最重要、使用最广泛的攻击技术之一，1988年第一个互联网蠕虫就用了它。
根本原因：C/C++ 不做数组越界检查。

漏洞代码示例

#include <stdio.h>
#include <string.h>
/* 演示缓冲区溢出漏洞 */
/* 警告：这是故意写的有漏洞的代码，仅用于教学！ */
void writeLog(char *msg) {
    printf("[LOG] %s\n", msg);
}
/* 有漏洞的函数 */
void A() {
    char B[128];   /* 栈上分配128字节的缓冲区 */
    printf("Type log message: ");
    gets(B);       /* 危险！gets 不检查边界，输入超过128字节就会溢出 */
    writeLog(B);
}
int main() {
    A();
    return 0;
}
/*
 * 编译方法（关闭保护，仅用于实验）：
 * gcc -fno-stack-protector -o demo demo.c
 *
 * 正常运行：输入不超过128字节的字符串，正常打印
 * 攻击：输入超过128字节，覆盖栈上的返回地址
 */

栈内存布局（调用 A() 后）：

高地址
+------------------------+
|   main 的局部变量      |
+------------------------+
|   返回地址（ret addr） |  ← 攻击者的目标：覆盖这里
+------------------------+
|   缓冲区 B[128]        |  ← gets() 写入，超过128字节就往上覆盖
|   ...                  |
|   B[0]                 |
+------------------------+
低地址（栈顶 SP）

攻击原理：

1. 攻击者输入超过 128 字节的数据
2. 多出的字节覆盖了"返回地址"
3. 攻击者把返回地址改成缓冲区B的起始地址
4. 函数返回时，CPU 跳到缓冲区B执行
5. 缓冲区B里存的是攻击者的 shellcode（如打开一个shell）

防御手段一：栈金丝雀（Stack Canary）

名字来自矿工用的金丝雀——有毒气体先杀死金丝雀，给矿工预警。

高地址
+------------------------+
|   返回地址              |
+------------------------+
|   金丝雀值（随机数）   |  ← 函数调用时放在这里
+------------------------+
|   缓冲区 B[128]        |
+------------------------+
低地址

• 函数调用时，在返回地址下面放一个随机的"金丝雀值"
• 函数返回前，检查金丝雀值有没有变
• 如果变了，说明缓冲区溢出发生了，立即终止程序
  绕过金丝雀的方法：不直接覆盖返回地址，而是先覆盖附近的变量（如 len），再利用这个变量间接改变执行路径，跳过金丝雀。

防御手段二：数据执行保护（DEP/NX）

核心思想：数据区域（栈、堆）标记为"不可执行"，代码段标记为"不可写"。
$$\text{内存策略}:W\oplus X=1\text{（可写 XOR 可执行，二者不能同时为1）}$$

• 即使攻击者把 shellcode 注入了缓冲区，也无法执行
• Intel/AMD CPU 的 NX 位（No-eXecute）实现这一功能

防御手段三：代码复用攻击（ROP）—— DEP 的反制

攻击思路：不注入新代码，利用程序里已有的代码片段。
Gadget（小工具）：程序中以 ret 指令结尾的短小代码片段。

文本段（已有代码）：
  ...
  add eax, ebx    ← Gadget A
  ret
  ...
  pop ecx         ← Gadget B
  ret
  ...
  mov [edx], eax  ← Gadget C
  ret
  ...

攻击者通过控制栈，把一系列 gadget 的地址串起来：

栈内容（攻击者控制）：
  地址(Gadget A)   ← 第一个 ret 弹出，跳到 Gadget A
  地址(Gadget B)   ← Gadget A 的 ret 弹出，跳到 Gadget B
  地址(Gadget C)   ← Gadget B 的 ret 弹出，跳到 Gadget C
  ...

每个 gadget 完成一小步操作，组合起来实现任意功能。

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

核心思想：每次程序运行时，栈、堆、库的起始地址都随机化，攻击者无法预测 gadget 的地址。
$$\text{攻击成功概率}=\frac{1}{2^{熵值}}$$

• 32位系统熵值有限（约9位 → 512种可能），容易暴力破解
• 64位系统熵值更大，更安全
  三层防御组合：

金丝雀（Canary）+ DEP/NX + ASLR
   |                |           |
   防止覆盖返回地址  防止执行数据  防止预测地址

12.2 格式化字符串攻击（Format String Attack）

根本原因：程序员偷懒，直接把用户输入当作 printf 的格式字符串。

#include <stdio.h>
#include <string.h>
/* 有漏洞的代码示例 */
int main() {
    char s[100];
    char g[100] = "Hello ";
    fgets(s, 100, stdin);  /* 读取用户输入 */
    strcat(g, s);          /* 拼接到 g */
    printf(g);             /* 危险！g 可能含格式控制符 */
    return 0;
}
/*
 * 正常输入：World
 * 输出：Hello World
 *
 * 恶意输入：%08x %08x %08x
 * printf 以为有3个整数参数，从栈上读取并打印
 * 泄露了栈上的数据！
 *
 * 更危险：%n 格式符
 * %n 把"已打印的字符数"写入到下一个参数指向的地址
 * 攻击者可以向任意内存地址写入值！
 */

防御：

• 永远用 printf("%s", g) 而不是 printf(g)
• 编译器会对危险用法发出警告
• 现代C库默认禁用 %n

12.3 释放后使用（Use-After-Free）

#include <stdio.h>
#include <stdlib.h>
int main() {
    int *A = (int *)malloc(128 * sizeof(int));  /* 分配内存 */
    int year_of_birth;
    printf("Enter year of birth: ");
    scanf("%d", &year_of_birth);
    if (year_of_birth < 1900) {
        printf("Error: year must be > 1900\n");
        free(A);              /* 释放内存 */
        /* 注意：A 指针还指向原来的地址，变成"悬空指针" */
    } else {
        /* ... 使用 A ... */
    }
    /* BUG：这里 A 可能已经被 free 了！ */
    A[0] = year_of_birth;    /* 写入已释放的内存 —— 未定义行为！ */
    /* 如果攻击者通过 heap feng shui 在这块内存放了别的对象，
       这里就会覆盖那个对象的字段 */
    return 0;
}

攻击利用：攻击者通过精心控制内存分配/释放顺序（Heap Feng Shui，堆风水），让释放的内存被另一个关键对象占用，然后触发 UAF 覆盖该对象的字段。

12.4 整数溢出攻击（Integer Overflow）

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main() {
    unsigned short width  = 40000;  /* 16位无符号整数 */
    unsigned short height = 40000;
    /* 整数溢出！
     * 40000 * 40000 = 1,600,000,000
     * 超过 unsigned short 最大值 65535
     * 实际结果：1600000000 % 65536 = 4096（错误的值！）
     */
    unsigned short size = width * height;
    printf("Computed size: %u\n", size);  /* 输出 4096，不是真实大小 */
    /* 程序以为只需要 4096 字节，但实际图像数据有 1.6GB */
    char *buffer = (char *)malloc(size);  /* 分配太小的缓冲区 */
    if (buffer) {
        /* 后续写入会导致缓冲区溢出！ */
        /* memcpy(buffer, image_data, real_size); ← 溢出 */
        free(buffer);
    }
    return 0;
}

$$40000\times 40000=1.6\times 10^9>65535=2^{16}-1$$
$$1.6\times 10^9\mathrm{mod}65536=4096\text{（错误的内存大小）}$$

12.5 TOCTOU 攻击（Time of Check to Time of Use）

问题：检查权限的时间和实际使用的时间之间有"窗口"，攻击者可以在这个窗口内偷梁换柱。

#include <unistd.h>
#include <fcntl.h>
#include <string.h>
/* SETUID root 程序，代表用户写文件 */
int main() {
    int fd;
    char user_input[] = "some data";
    /* 步骤1：检查权限（用真实UID检查 ./my_document 是否可写） */
    if (access("./my_document", W_OK) != 0) {
        return 1;  /* 没有权限，拒绝 */
    }
    /* ！！！时间窗口！！！
     * 攻击者在这里把 ./my_document 替换成指向 /etc/passwd 的符号链接
     * 检查通过了（检查的是原始文件），但打开的是 /etc/passwd！
     */
    /* 步骤2：打开并写入（已经不是原来的文件了！） */
    fd = open("./my_document", O_WRONLY);  /* 实际打开了 /etc/passwd */
    write(fd, user_input, strlen(user_input));  /* 破坏了密码文件！ */
    close(fd);
    return 0;
}
/*
 * 正确做法：先打开文件，再用 fstat() 检查文件描述符的权限
 * 文件描述符不能在 open 和 write 之间被攻击者修改
 *
 * int fd = open("./my_document", O_WRONLY);
 * struct stat st;
 * fstat(fd, &st);  ← 检查 fd 的权限，而不是路径
 * if (合法) write(fd, ...);
 */

时间线：
[检查 my_document 权限] → [攻击者把 my_document 替换成 /etc/passwd 的符号链接] → [打开并写入 /etc/passwd]
      ^                                    ^                                               ^
    access()                         攻击者操作                                          open()
     时刻1                              (间隙)                                            时刻2
TOCTOU = Time Of Check To Time Of Use（从检查到使用之间的时间差）

13. 硬件漏洞

13.1 隐蔽信道（Covert Channel）

即使系统的安全模型被正式证明是安全的，信息仍然可以通过"隐蔽信道"泄露。
Lampson 模型（1973）：三个进程——客户、服务器、合谋者。

客户（Client）
  |  发送敏感数据（合法）
  v
服务器（Server）  ← 被限制在"沙盒"中，无法直接传数据给合谋者
  |
  | 隐蔽信道（Covert Channel）
  v
合谋者（Collaborator）

隐蔽信道示例：

发送 1 → 服务器疯狂计算（占满CPU）→ 合谋者检测到响应变慢 → 判断为 1
发送 0 → 服务器休眠（CPU空闲）  → 合谋者检测到响应正常 → 判断为 0

其他隐蔽信道：页面错误频率、文件锁状态、磁盘I/O负载……
文件锁隐蔽信道：

时间线（每格代表一个时间单位）：
发送方：  ████ ████ ░░░░ ████ ░░░░ ████ ░░░░ ░░░░
          1    1    0    1    0    1    0    0    ← 发送的比特
接收方：通过尝试获取锁来判断当前比特值
████ = 文件被锁（发送1）
░░░░ = 文件未锁（发送0）
传输的比特流：1 1 0 1 0 1 0 0

13.2 侧信道（Side Channel）

与隐蔽信道不同：侧信道是单方面的，受害者不知道信息被泄露。
缓存侧信道（Cache Side Channel）— Flush & Reload 攻击：
场景：用户 Andy 的加密软件使用 do_one_thing()（密钥位=0时执行）和 do_another_thing()（密钥位=1时执行）。
攻击者 Herbert 通过观察缓存状态推断密钥：

Herbert 的攻击循环：
1. 把 do_one_thing 和 do_another_thing 的代码从缓存中清除（flush）
2. 发一条消息给 Andy，触发加密操作
3. 立即测量读取 do_one_thing 的时间（快 or 慢？）
   - 快 → do_one_thing 被加密程序加载进了缓存 → 当前密钥位 = 0
   - 慢 → do_one_thing 不在缓存 → do_another_thing 在缓存 → 密钥位 = 1
4. 重复，一位一位地推断出整个密钥
关键原理：
  缓存命中  → ~4 纳秒
  缓存缺失 → ~100 纳秒（从内存读）
  时间差异足以区分！

13.3 瞬态执行攻击（Meltdown & Spectre）

背景：现代 CPU 为了性能，会预测性地提前执行还没"轮到"的指令。

Meltdown（熔断，2018）

原理：CPU 在发现权限错误之前，已经（瞬态地）执行了读取内核内存的指令。

/* 攻击代码（概念演示，无法直接运行） */
char *kaddr = ...; /* 内核地址（普通用户本不能读） */
/* 步骤1：（瞬态地）读取内核字节 */
reg0 = kaddr[0];          /* 会触发异常！但 CPU 在异常处理前已经把值放到 reg0 */
/* 步骤2：（瞬态地）用读到的值作为索引访问数组 */
reg1 = array[reg0 * 4096]; /* 这条指令被瞬态执行，把 array[secret*4096] 加载进缓存 */
/* 异常触发，以上两条指令的"结构影响"被撤销 */
/* 但：array[secret*4096] 已经在缓存中了！（微架构影响留存） */
/* 步骤3：通过测时间，找出哪个数组元素最快（在缓存中） */
for (int i = 0; i < 256; i++) {
    time = measure(array[i * 4096]); /* 最快的那个 i 就是 secret 的值 */
}

时间线：

CPU 执行时序：
地址翻译（检查权限）─────────────────────────────►  发现权限错误，触发异常
                                                      |
瞬态执行：                                            |
  读取内核字节 ──► 用结果作索引 ──► 加载array元素到缓存  |
                                          |            |
                                          | 留在缓存中（结构影响被撤销，微架构影响留存）
                                          v
攻击者：遍历array，测时间 ──► 找到最快的元素 ──► 推断出内核字节

修复（KPTI，内核页表隔离）：彻底分离内核和用户的页表，内核内存不再映射到用户进程的地址空间。
代价：系统调用变慢（需要切换页表）。

Spectre（幽灵）

原理：CPU 的分支预测器被训练"猜错"，从而瞬态地执行了越界访问。

/* 受害者代码（如操作系统内核） */
/* input 是攻击者控制的值 */
if (input < MaxArrayElements) {  /* 安全检查 */
    char x = A[input];           /* 如果 input 越界，本不该执行 */
    char y = B[x * 4096];        /* 同上 */
}
/*
 * 攻击步骤：
 * 1. 攻击者先发送100次合法的 input（如 input=5），训练分支预测器认为条件"总是真"
 * 2. 攻击者发送恶意的 input（如 input=63261，越界值）
 * 3. CPU 预测条件为真，瞬态地执行了 A[63261] 的读取（越界！）
 * 4. 用读到的值作索引，把 B[x*4096] 加载进缓存
 * 5. 预测错误被发现，结构影响撤销，但缓存状态留存
 * 6. 攻击者通过缓存侧信道读出 x 的值
 */

Meltdown vs Spectre 对比：

特性	Meltdown	Spectre
触发原因	异常（越权访问）	分支预测错误
攻击目标	读内核内存	读受害者进程内存
修复难度	相对容易（KPTI）	极难，部分永远无法完全修复
影响范围	较窄	更广

---

14. 内部攻击

14.1 逻辑炸弹（Logic Bomb）

内部员工（担心被解雇）在代码中偷偷埋下的定时炸弹：

/* 逻辑炸弹示例（教学演示，切勿用于实际） */
/* 员工每天喂给炸弹一个"密码"，如果某天没收到，就爆炸 */
/* 真实案例：检查工资单 */
void check_payroll() {
    if (!employee_in_payroll("programmer_id")) {
        /* 程序员不在工资单上了（被解雇了） */
        /* 触发破坏行为：清空磁盘、加密文件勒索 */
        trigger_damage();
    }
}

14.2 后门（Back Door）

在登录程序中偷偷加入一个万能密码：

/* 正常的登录逻辑 */
int normal_login(char *name, char *password) {
    return check_validity(name, password);
}
/* 带后门的登录逻辑 */
int backdoor_login(char *name, char *password) {
    /* 如果用户名是 "zzzzz"，不管密码是什么，都允许登录 */
    if (strcmp(name, "zzzzz") == 0) {
        return 1;  /* 后门！让程序员可以登录任何人的账户 */
    }
    return check_validity(name, password);
}

防御：代码审查（Code Review）—— 每个模块都要让其他程序员看一遍，逐行解释。

14.3 登录欺骗（Login Spoofing）

攻击者写一个假的登录程序，界面和真的一模一样：

真实登录界面：          假冒登录界面（攻击者写的）：
+--------------+        +--------------+
| Login:       |        | Login:       |  ← 看起来完全一样！
+--------------+        +--------------+
用户在假界面输入用户名和密码
→ 假程序把账号密码记录下来，发给攻击者
→ 假程序退出，真的登录界面出现
→ 用户以为刚才是输错了，重新输入，成功登录
→ 攻击者获得了账号密码

防御：操作系统在登录屏幕使用只有内核才能触发的"安全注意键"（如 Windows 的 Ctrl+Alt+Del），普通程序无法拦截这个信号。

15. 操作系统加固

15.1 细粒度随机化

普通 ASLR（粗粒度）：每次运行时，代码段、堆、栈的起始地址随机，但内部布局固定。

粗粒度 ASLR（同一运行）：
  [随机偏移 + main()] [随机偏移 + myFunc()] ← 相对偏移固定
  泄露一个地址 → 知道所有函数的地址
细粒度 ASLR（每次运行）：
  [随机偏移1 + main()] [随机偏移2 + myFunc()] ← 相对偏移也随机
  泄露一个地址 → 只知道这一个函数的地址

15.2 控制流完整性（CFI）

核心思想：限制 ret、call、jmp 指令只能跳到"合法目标"，不能乱跳。
实现方式（伪汇编，概念演示）：

未加CFI的代码：
  foo:
    ...
    ret              ← 弹出返回地址，跳过去（攻击者可以改这个地址！）
加了CFI的代码：
  foo:
    ...
    pop reg0         ← 把返回地址放到 reg0
    if (*reg0 != L3) raise_alarm()   ← 检查返回地址前面是否有合法标签
    else jmp (reg0 + 8)              ← 跳到标签后面的合法指令
  合法返回位置：
    L3 （8字节标签）
    instr_after_call ← 真正要返回的地方

CFI 流程图：
程序执行 ret 指令
       |
       v
   弹出返回地址
       |
       v
   检查地址前是否有合法标签(L3)?
       |              |
      是              否
       |              |
   跳转执行      触发报警，终止程序

15.3 可信平台模块（TPM）与安全启动

安全启动链（Secure Boot）：

ROM/固件（根信任）
   |
   | 验证签名
   v
引导加载程序（Bootloader）
   |
   | 验证签名
   v
操作系统内核
   |
   | 验证签名
   v
驱动程序和其他组件
每一步都验证下一步的数字签名
任何一步被篡改 → 签名验证失败 → 启动终止

远程认证（Remote Attestation）：
TPM 有平台配置寄存器（PCR），每次启动时被扩展：
$${\text{新PCR}}_0=\text{Hash}({\text{旧PCR}}_0\Vert \text{加载内容的Hash})$$
远程计算机可以询问 TPM：

1. 你的 PCR-0 值是多少？
2. 用你的私密密钥签名（PCR-0值 + 随机数）
   这样就能验证目标机器是否按照正确步骤启动，且答复是新鲜的（防止重放）。

15.4 可信执行环境（TEE）

当连操作系统都不能信任时（如云计算场景），需要更强的隔离。
ARM TrustZone 示例：

+---------------------------+---------------------------+
|       普通世界             |       安全世界             |
|  (Normal World)           |  (Secure World)           |
|                           |                           |
|  Android/Linux            |  银行核心逻辑              |
|  普通应用程序              |  密钥管理                  |
|  甚至被攻破的OS            |  ← 硬件保护，OS无法访问     |
+---------------------------+---------------------------+
           ^                           ^
           |   特殊指令切换世界          |
           +---------------------------+
即使普通世界的OS被完全攻破，安全世界的数据依然安全

15.5 沙箱（Sandboxing）

目的：让不信任的代码（如JavaScript、eBPF程序）在受限环境中运行。
实现思路：

虚拟地址空间划分：
+------------------+  高地址
|  引用监视器代码  |
+------------------+
|                  |
|  代码沙箱2       |  ← 外来代码2 只能在这里执行
|                  |
+------------------+
|  数据沙箱2       |  ← 外来代码2 只能访问这里的数据
+------------------+
|  代码沙箱1       |
+------------------+
|  数据沙箱1       |
+------------------+  低地址
对间接跳转指令，插入运行时检查：
  MOV R1, 目标地址
  SHR #24, R1       ← 取高位
  CMP R1, 沙箱前缀  ← 比较
  TRAPNE             ← 不匹配则报警，杀死进程
  JMP (目标地址)    ← 匹配才跳转

综合总结

安全知识体系总览：
操作系统安全
├── 目标：CIA 三元组
│   ├── 保密性 (Confidentiality)
│   ├── 完整性 (Integrity)
│   └── 可用性 (Availability)
│
├── 原则：Saltzer & Schroeder 8条原则
│   ├── 简单性、默认失效安全、完全仲裁
│   ├── 最小权限(POLA)、权限分离
│   ├── 最小公共机制、开放设计、心理可接受性
│
├── 访问控制
│   ├── 保护矩阵
│   ├── ACL（按列，与对象关联）
│   └── Capabilities（按行，与用户关联）
│
├── 正式模型
│   ├── Bell-LaPadula（保密性：读下写上）
│   └── Biba（完整性：读上写下）
│
├── 密码学
│   ├── 对称密钥（快，需共享密钥）
│   ├── 非对称/公钥（慢，无需预共享）
│   └── 数字签名（哈希+私钥加密）
│
├── 认证
│   ├── 知道的（密码，加盐哈希）
│   ├── 拥有的（智能卡）
│   └── 本身是（生物特征）
│
├── 软件攻击与防御
│   ├── 缓冲区溢出 → 金丝雀/DEP/ASLR
│   ├── 格式化字符串 → 编译器警告/禁用%n
│   ├── UAF → 语言级保护（Rust）
│   ├── 整数溢出 → 边界检查
│   └── TOCTOU → 使用文件描述符而非路径
│
├── 硬件攻击
│   ├── 隐蔽信道（主动泄露）
│   ├── 侧信道（被动泄露，缓存时序）
│   └── 瞬态执行（Meltdown/Spectre）
│
├── 内部攻击
│   ├── 逻辑炸弹 → 代码审查
│   ├── 后门 → 代码审查
│   └── 登录欺骗 → 安全注意键
│
└── OS 加固
    ├── 细粒度 ASLR/KASLR
    ├── 控制流完整性（CFI）
    ├── 安全启动（Secure Boot）
    ├── TPM 与远程认证
    ├── TEE（可信执行环境）
    └── 沙箱（Sandboxing）