同步与互斥：临界区、软硬件实现

概念

临界资源（critical resource）：一次仅允许一个进程使用的资源（打印机、共享变量、同一文件的前半段）。

临界区（critical section）：进程中访问临界资源的那段代码。

互斥（mutual exclusion）：多个进程因争用同一临界资源而产生的间接制约关系——"你不能和我同时进"。

同步（synchronization）：为完成同一任务而协同步调的直接制约关系——"我必须等你做完这件我才能做"。

$$\text{互斥}=\text{争资源（间接制约）}\text{同步}=\text{讲次序（直接制约）}$$

一句话说清它是什么：同步与互斥解决的都是"并发进程之间的时序依赖"，区别只在依赖的方向——互斥是"互相排斥地抢"，同步是"前赴后继地等"。异步是并发的必然结果，而"同步与互斥"就是驯服异步的那套机制（回顾 os/01-overview.md）。

原理

一、临界区的四段结构（必须能默写）

while (true) {
    ┌─────────────────────────┐
    │  进入区 entry section   │  ← 检查能否进入, 若不能则等待; 能进则"上锁"
    ├─────────────────────────┤
    │  临界区 critical section│  ← 真正访问临界资源的那段代码
    ├─────────────────────────┤
    │  退出区 exit section    │  ← 把锁"打开" (唤醒等待者)
    ├─────────────────────────┤
    │  剩余区 remainder       │  ← 与临界资源无关的代码
    └─────────────────────────┘
}

⚠️ 考点在"进入区与退出区"：临界区本身不需要任何特殊写法，所有同步机制都只作用在进入区与退出区。

二、同步机制必须满足的四条准则（必背，年年考）

准则	含义	违反后果
空闲让进	临界区空闲时，有进程想进就应该让它进	资源白空转（双标志后检查、单标志法违反）
忙则等待	已有进程在临界区时，其他进程必须等	互斥被破坏（双标志先检查违反）
有限等待	等待的进程不能无限期地等（不能饥饿）	饥饿/死锁（双标志后检查违背）
让权等待	进不去时应释放处理机（别死等）	CPU 空转（所有"忙等"方案都违反）

⚠️ 四条准则里，"让权等待"是最容易漏答的一条。所有靠 while 自旋的软件/硬件方法都不满足它——因为它们都在"忙等"（busy waiting）。只有信号量（记录型）与管程才满足让权等待（见 os/13-semaphore.md）。

三、软件实现方法（四种，逐个看它违背哪条）

1. 单标志法（用 turn 表示"该谁进"）

/* 全局: int turn = 0;  turn == i 表示"允许 P_i 进入" */
// P0
while (turn != 0) { }        /* 不是我就自旋 */
/* 临界区 */
turn = 1;                    /* 让给对方 */

准则	是否满足	说明
空闲让进	✗ 违背	turn = 1 而 P1 根本不想进时，P0 想进也进不去（"必须轮流"是硬规定）
忙则等待	✓	只有持 turn 的人能进
有限等待	✓	对方用完会交还
让权等待	✗	忙等

致命缺陷：两个进程必须交替进入——违背"空闲让进"。

2. 双标志先检查法（先检查，后设置）

/* 全局: bool flag[2] = {false, false}; */
// P0
while (flag[1]) { }          /* ① 先看对方想不想进 */
flag[0] = true;              /* ② 再宣布自己想进 */
/* 临界区 */
flag[0] = false;

致命缺陷：两次"检查"可能都发生在两次"设置"之前（检查与设置不是原子的）→ 两个进程同时通过检查、同时进入临界区，违背"忙则等待"。这是本节最著名的反例（见例 2）。

3. 双标志后检查法（先设置，后检查）

/* 全局: bool flag[2] = {false, false}; */
// P0
flag[0] = true;              /* ① 先宣布"我想进" */
while (flag[1]) { }          /* ② 再看对方想不想进 */
/* 临界区 */
flag[0] = false;

致命缺陷：双方都先举手、再互看，结果谁也进不去（双双自旋，临界区空闲却无人能用）→ 违背"空闲让进"与"有限等待"。互斥本身是成立的（没人能进，当然不会同时进）。

4. Peterson 算法（双标志 + turn 谦让）

/* 全局: bool flag[2] = {false, false};  int turn = 0; */
// P0
flag[0] = true;              /* 我想进 */
turn = 1;                    /* 但先让你 (谦让) */
while (flag[1] && turn == 1) { }   /* 你既想进、又轮到你先, 那我就等 */
/* 临界区 */
flag[0] = false;

为什么它能对：turn 是"最后一次谦让的赢家"——两个进程都谦让时，turn 只会取一个值，所以只有一个能通过 while。

准则	是否满足
空闲让进	✓
忙则等待	✓
有限等待	✓（等待时间有界：对方出临界区后必然放开）
让权等待	✗（仍然忙等）

⚠️ Peterson 是"软件方法的天花板"：它满足了前三条，却永远解决不了第四条——因为"检查"这个动作本身需要 CPU。要"让权等待"，必须由操作系统提供阻塞原语——这就是信号量出现的原因。

四种软件方法对照总表

方法	空闲让进	忙则等待	有限等待	让权等待	结论
单标志法	✗	✓	✓	✗	强制轮流，违背空闲让进
双标志先检查	✓	✗	✓	✗	两进程可能同时进临界区
双标志后检查	✗	✓	✗	✗	双双自旋，谁也进不去
Peterson	✓	✓	✓	✗	软件方法里最好的

四、硬件实现方法（三种）

1. 中断屏蔽（关中断）

/* 进入区 */
关中断;
/* 临界区 */
/* 退出区 */
开中断;

优点：简单、彻底（本处理机上"没有任何事件能打断我"）。 三个致命限制（必答）：

1. 只适用于单处理机——多处理机上关掉本 CPU 的中断，别的 CPU 照样能跑（本 CPU 只是"听不见"，不是"禁止别人执行"）。
2. "关中断"是特权指令——用户程序不能执行（用户随便关中断会让系统失去时钟与 I/O 响应）。
3. 只适合内核临界区，且关得太久会丢失中断、影响实时性。

2. TestAndSet（TS）指令——原子地"读旧值、置 true"

/* 硬件原子实现: 返回 *lock 的旧值, 并把 *lock 置为 true */
bool TestAndSet(bool *lock) {
    bool old = *lock;
    *lock = true;
    return old;                  /* 读与写之间不能被插入 —— 靠硬件保证 */
}

/* 用 TS 实现互斥 */
while (TestAndSet(&lock)) { }    /* 旧值是 true 说明别人占着 —— 自旋 */
/* 临界区 */
lock = false;                    /* 退出区: 直接置 false */

3. Swap（XCHG）指令——原子地把锁"换"过来

void Swap(bool *a, bool *b) { bool t = *a; *a = *b; *b = t; }   /* 硬件原子实现 */

/* 用 Swap 实现互斥 */
bool key = true;
while (key) {
    Swap(&lock, &key);           /* 与锁交换: 换完 key=false 说明锁原本空闲 */
}
/* 临界区 */
lock = false;

⚠️ TS 与 Swap 的共同点（考点）：

1. 都靠"一条指令不可打断"来实现原子性——不需要关中断，因此多处理机也能用（这是相对"中断屏蔽"的最大优势）。
2. 都仍然"忙等"——不满足"让权等待"。
3. 都可能导致饥饿：多条进程同时自旋，谁先抢到锁由硬件调度决定，可能长期抢不到。

示例

例 1：四种软件方法到底违背了哪条准则（穷举交错验证）

把两个进程的每一条语句当作不可分割的原子步骤，穷举所有交错执行顺序，检查：（a）是否存在"两进程同时在临界区"；（b）是否存在"双方同时自旋、谁也进不去"；（c）当只有一个进程想进（另一个完全不动）时，它能否进入。

穷举结果（下方 Python 程序实跑）：

方法	可达状态数	互斥性（忙则等待）	双方同时自旋（饥饿）	单独一个进程能否进入（空闲让进）
单标志法	9	满足	否	不能 → 违背空闲让进
双标志先检查	36	违反	否	能
双标志后检查	27	满足	是 → 违背有限等待	能
Peterson	42	满足	否	能

四条结论：

1. 单标志法：互斥没问题，但"对方不动时我进不去"——空闲让进被破坏。
2. 双标志先检查：存在"两进程同时在临界区"的交错（3 ≈ 3 号状态）——忙则等待被破坏。
3. 双标志后检查：互斥成立（因为谁都进不去），但存在双方同时自旋的交错——空闲让进与有限等待被破坏。
4. Peterson：前三条全满足，只差"让权等待"（因为它是忙等）。

⚠️ 一个必须澄清的错觉："双标志后检查是互斥的" ≠ "它是可用的"——互斥只是入门要求。一个"谁也进不去"的方案，互斥性当然成立，但它毫无用处。

例 2：双标志先检查的致命交错（逐步）

为什么"先检查、后设置"会出事？把两次检查都排到两次设置之前：

步骤	动作	flag[0]	flag[1]	在临界区?
1	P0 检查 flag[1] → 假（P1 还没表态）	假	假	无
2	P1 检查 flag[0] → 假（P0 也还没表态）	假	假	无
3	P0 设置 flag[0] = true	真	假	无
4	P1 设置 flag[1] = true	真	真	无
5	P0 进入临界区	真	真	P0
6	P1 进入临界区（同时！）	真	真	P0 + P1 ← 互斥被破坏

根因："检查"与"设置"是两条独立的指令，中间可以被插入。只要"检查"与"设置"不是原子的，"先检查后设置"就永远不可靠——这正是 TS/Swap 提供"原子读改写"的意义。

例 3：C 实现——打印双标志先检查的反例交错

#include <stdio.h>

/* 用四个状态位模拟"双标志先检查法"的一次致命交错 */
typedef struct { int flag0, flag1, in0, in1; } state;

static void show(const char *ev, state s) {
    /* 事件放最后: printf 对中文按字节补齐, 放前面必然错位 */
    printf("%d %d | %d %d | %s\n", s.flag0, s.flag1, s.in0, s.in1, ev);
}

int main(void) {
    state s = {0, 0, 0, 0};
    printf("flag0 flag1 | in0 in1 | 事件\n");

    show("P1 与 P0 都还没表态, 两次检查都得到 false", s);
    show("P1 检查 flag0 -> false", s);      /* 检查不改状态 */
    show("P0 检查 flag1 -> false", s);
    s.flag0 = 1; show("P0 先设置 flag0 = true", s);
    s.flag1 = 1; show("P1 再设置 flag1 = true", s);
    s.in0 = 1;   show("P0 进入临界区", s);
    s.in1 = 1;   show("P1 进入临界区(同时!)", s);

    printf("判定: in0 == 1 且 in1 == 1 -> %s\n",
           (s.in0 && s.in1) ? "两进程同时在临界区, 违背 忙则等待" : "互斥成立");
    return 0;
}

c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

预期输出：

flag0 flag1 | in0 in1 | 事件
0 0 | 0 0 | P1 与 P0 都还没表态, 两次检查都得到 false
0 0 | 0 0 | P1 检查 flag0 -> false
0 0 | 0 0 | P0 检查 flag1 -> false
1 0 | 0 0 | P0 先设置 flag0 = true
1 1 | 0 0 | P1 再设置 flag1 = true
1 1 | 1 0 | P0 进入临界区
1 1 | 1 1 | P1 进入临界区(同时!)
判定: in0 == 1 且 in1 == 1 -> 两进程同时在临界区, 违背 忙则等待

⚠️ 两点说明：

1. printf 对中文按"字节"补齐（%-18s 会把汉字当 3 字节），所以中文事件串一律放在格式串最后，让前面的数字列严格对齐。
2. 这段 C 不是在"真跑两个进程"（本机没有并发运行环境），它是把"已被穷举确认存在的那个交错"按顺序演一遍——逻辑上与例 1 的穷举结果等价。

例 4：C 实现——TS 与 Swap 的互斥骨架

/* ---------- 1. TestAndSet 版 ---------- */
bool TestAndSet(bool *lock) {          /* 由硬件保证"读 + 写"原子 */
    bool old = *lock;
    *lock = true;
    return old;
}
void lock_TS(bool *lock) {
    while (TestAndSet(lock)) { }       /* 旧值为 true -> 自旋等待 */
}
void unlock_TS(bool *lock) { *lock = false; }

/* ---------- 2. Swap 版 ---------- */
void Swap(bool *a, bool *b) { bool t = *a; *a = *b; *b = t; }
void lock_Swap(bool *lock) {
    bool key = true;
    while (key) {                      /* 换到手之后 key 反映"交换前锁的状态" */
        Swap(lock, &key);
    }
}
void unlock_Swap(bool *lock) { *lock = false; }

/* ---------- 3. 中断屏蔽版(仅单处理机 + 仅内核) ---------- */
void lock_intr(void) { 关中断(); }      /* 伪代码: 真实实现是特权指令 cli */
void unlock_intr(void) { 开中断(); }

三者的取舍（必须能背）：

方法	原子性靠什么	多处理机可用?	满足让权等待?	典型用途
中断屏蔽	关中断	✗	✗	单处理机的内核短临界区
TestAndSet	一条原子指令	✓	✗	自旋锁、内核低层互斥
Swap	一条原子指令	✓	✗	同上（x86 上是 xchg）

例 5：Python——穷举交错检查器（例 1 的数据来源）

# 把每个算法的每条语句当作"原子步骤", 穷举两个进程的所有交错
# 状态 = (pc0, pc1, turn, flag0, flag1, in0, in1)

def setpc(st, who, d):
    s = list(st); s[who] += d; return tuple(s)

def setvar(st, var, val):
    s = list(st); s[{'turn': 2, 'flag0': 3, 'flag1': 4}[var]] = val; return tuple(s)

def apply(st, who, op):
    pc0, pc1, turn, f0, f1, i0, i1 = st
    env = {'turn': turn, 'flag0': f0, 'flag1': f1}
    if op[0] == 'guard':                     # while(cond){} : 真则自旋(状态不变), 假则前进
        return (st, False) if eval(op[1], {}, env) else (setpc(st, who, 1), True)
    if op[0] == 'assign':
        return setvar(setpc(st, who, 1), op[1], op[2]), True
    if op[0] == 'cs':                        # 进入临界区
        return (pc0 + 1 if who == 0 else pc0, pc1 if who == 0 else pc1 + 1,
                turn, f0, f1, True if who == 0 else i0, True if who == 1 else i1), True
    if op[0] == 'leave':
        return (pc0 + 1 if who == 0 else pc0, pc1 if who == 0 else pc1 + 1,
                turn, f0, f1, False if who == 0 else i0, False if who == 1 else i1), True

def explore(ops0, ops1, turn0=0):
    start = (0, 0, turn0, False, False, False, False)
    seen, stack, viol, stuck = {start}, [start], None, None
    while stack:
        st = stack.pop()
        pc0, pc1, turn, f0, f1, i0, i1 = st
        if i0 and i1 and viol is None:
            viol = st                                  # 两进程同时在临界区
        both = True
        for who in (0, 1):
            pc, ops = (pc0, ops0) if who == 0 else (pc1, ops1)
            if pc >= len(ops):
                both = False; continue
            op = ops[pc]
            if op[0] != 'guard' or not eval(op[1], {}, {'turn': turn, 'flag0': f0, 'flag1': f1}):
                both = False                           # 有人能推进, 不算双双自旋
            ns, _ = apply(st, who, op)
            if ns not in seen:
                seen.add(ns); stack.append(ns)
        if both and stuck is None:
            stuck = st
    return viol, stuck, len(seen)

def can_enter_alone(ops0, ops1, turn0):
    st = (0, 0, turn0, False, False, False, False)
    seen = {st}; stack = [st]
    while stack:
        s = stack.pop()
        if s[5]:
            return True
        if s[0] >= len(ops0):
            continue
        ns, _ = apply(s, 0, ops0[s[0]])
        if ns not in seen:
            seen.add(ns); stack.append(ns)
    return False

ALGOS = {
    '单标志法': ([('guard', 'turn != 0'), ('cs',), ('leave',), ('assign', 'turn', 1)],
                 [('guard', 'turn != 1'), ('cs',), ('leave',), ('assign', 'turn', 0)], 1),
    '双标志先检查': ([('guard', 'flag1'), ('assign', 'flag0', True), ('cs',), ('leave',), ('assign', 'flag0', False)],
                     [('guard', 'flag0'), ('assign', 'flag1', True), ('cs',), ('leave',), ('assign', 'flag1', False)], 0),
    '双标志后检查': ([('assign', 'flag0', True), ('guard', 'flag1'), ('cs',), ('leave',), ('assign', 'flag0', False)],
                     [('assign', 'flag1', True), ('guard', 'flag0'), ('cs',), ('leave',), ('assign', 'flag1', False)], 0),
    'Peterson': ([('assign', 'flag0', True), ('assign', 'turn', 1), ('guard', 'flag1 and turn == 1'),
                  ('cs',), ('leave',), ('assign', 'flag0', False)],
                 [('assign', 'flag1', True), ('assign', 'turn', 0), ('guard', 'flag0 and turn == 0'),
                  ('cs',), ('leave',), ('assign', 'flag1', False)], 0),
}

print('%-14s %8s %10s %14s %14s' % ('方法', '状态数', '互斥性', '双方同时自旋', '单独能否进入'))
for name, (o0, o1, t0) in ALGOS.items():
    viol, stuck, n = explore(o0, o1, t0)
    print('%-14s %8d %10s %14s %14s' % (name, n, '违反' if viol else '满足',
                                        '是' if stuck else '否',
                                        '能' if can_enter_alone(o0, o1, t0) else '不能'))
print('')
print('注: 单标志法的 turn 初值取 1 (即"轮到 P1"), 因此 P0 单独想进时进不去 -> 违背空闲让进')
print('    双标志先检查的违反状态: (pc0,pc1,turn,flag0,flag1,in0,in1) =',
      explore(*ALGOS['双标志先检查'][:2], ALGOS['双标志先检查'][2])[0])

python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

输出对照：穷举得 单标志法 9 个状态、双标志先检查 36 个、双标志后检查 27 个、Peterson 42 个；互斥性分别为 满足 / 违反 / 满足 / 满足；双方同时自旋只有"双标志后检查"可达；单独一个进程能否进入只有"单标志法"不能。违反状态为 (3, 3, 0, True, True, True, True)——in0 与 in1 同时为真，正是例 2 那张表。

⚠️ 穷举的意义："某方法正确/错误"不能靠举一个例子说明"——上表把两个进程的所有交错都走了一遍（状态数分别是 9/36/27/42），得到的是"存在违反"或"存在即违反、所有交错都不违反"的确定结论。这也说明"检查-设置不是原子操作"为什么致命：反例并不罕见，它就在交错空间里。

考点

考点

1. 必背结论

• 临界区四段：进入区 → 临界区 → 退出区 → 剩余区；所有机制只作用于进入区与退出区。
• 四条准则：空闲让进、忙则等待、有限等待、让权等待。"让权等待"最易漏。
• 单标志法违背"空闲让进"（强制轮流）；双标志先检查违背"忙则等待"（检查与设置非原子）；双标志后检查违背"空闲让进"与"有限等待"（双双自旋）；Peterson 满足前三条，唯独不满足"让权等待"。
• 软件方法一律"忙等"，都不满足让权等待——要"让权等待"必须由 OS 提供阻塞/唤醒原语（信号量、管程）。
• 中断屏蔽只适用单处理机、只适合内核临界区、且是特权指令。
• TS / Swap 靠"一条原子指令"实现，多处理机可用、不关中断，但仍是忙等。
• TS 的语义 = "读旧值 + 置 true"（旧值为 true 表示"别人占着"）；Swap 的语义 = "原子交换"。
• Peterson 的 turn 是"最后一次谦让的赢家"——这是它互斥成立的关键。

2. 高频陷阱

• 只答"互斥"不答"同步"：两者是不同的制约关系（间接 vs 直接）；题目问"同步机制"时四条准则要一起答。
• 把"双标志后检查"说成"互斥失败"：错。它的互斥成立（谁都进不去），失败的是"空闲让进/有限等待"。答反了直接 0 分。
• 把"双标志先检查"说成"会死锁"：错。它是"两进程同时进临界区"（忙则等待被破坏），不是死锁。
• 认为"关中断可以解决一切互斥"：错。多处理机上关本 CPU 的中断无效——别的 CPU 依然并发访问。
• 说"TS/Swap 满足让权等待"：错。它们都是自旋（忙等），只是原子性不发愁。
• 把"空闲让进"与"忙则等待"混淆：空闲让进管"没人时该放行"；忙则等待管"有人时必须拦"。两者是互补的两侧。
• 以为"临界区越短越安全所以不用管"：临界区长度影响的是性能（别人被挡多久），安全性由进入区/退出区保证。
• 忘了"互斥是同步的一种特例"这个说法要谨慎：408 教材把"互斥"与"同步"并列；答"同步机制的四条准则"时两者共用。不要写成"同步包含互斥"这种含糊话。
• 忽略"检查 + 设置必须原子"的统一根因：双标志先检查、TS、Swap 三个知识点串起来看——它们都在解决同一个问题："谁先宣布"必须是不可分割的一步。

3. 解题模板（"互斥方案判断题"）

① 写出方案的"进入区/退出区"代码, 标出每一步是不是原子操作
② 按四条准则逐条检查:
     空闲让进 -> 假设"只有一个进程想进", 它能不能进?
     忙则等待 -> 假设"两个都想进", 有没有交错让两人同时进?
     有限等待 -> 有没有人能无限期等下去?
     让权等待 -> 进不去时是自旋还是阻塞?
③ 找出反例交错: 把"检查"与"设置"排成"都检查、再都设置"
④ 结论要写"违背了哪一条", 不能只写"有缺陷"
⑤ 若问"如何改进": 把"检查+设置"变成原子(TS/Swap), 或引入阻塞队列(信号量)

4. 与相邻章节的接口

• os/10-process.md（进程与线程）："运行 → 阻塞"的典型原因就是"进不了临界区/等不到信号量"；原语必须不可中断，正是本篇"关中断"的动机。
• os/13-semaphore.md（信号量）：信号量把"自旋等待"换成了"阻塞等待"——它是四条准则中"让权等待"的第一个满足者。
• os/14-classic.md（经典同步问题）：生产者-消费者 / 读者-写者 / 哲学家都是本篇机制的"应用题"。
• os/15-monitor.md（管程）：管程把"进入区/退出区"交给编译器生成——程序员再也不用自己写 while(flag)。
• arch/31-controller.md（控制器）：TS/Swap 这类"原子读改写"指令在数据通路里怎么保证不被插入，靠的是控制器发出的总线锁定信号——"原子性"的硬件根在这里。

小结

• 临界区四段：进入区 → 临界区 → 退出区 → 剩余区；四条准则：空闲让进、忙则等待、有限等待、让权等待。
• 互斥是"抢资源"（间接制约），同步是"讲次序"（直接制约）——方向不同，机制同源。
• 四种软件方法一句话记住：单标志——强制轮流（违背空闲让进）；双标志先检查——都检查再都设置（两进程同时进临界区）；双标志后检查——都举手再互看（双双自旋）；Peterson——加一个 turn 谦让，前三条全满足。
• 穷举结果（例 1）：状态数 9 / 36 / 27 / 42，互斥性 满足 / 违反 / 满足 / 满足——"存在违反"是确定的，不是举例子碰巧。
• 三种硬件方法：中断屏蔽（单处理机+内核专用）、TS（原子读+置位）、Swap（原子交换）——后两者多处理机可用，但都忙等。
• 唯一出路是"让权等待"：必须由 OS 提供阻塞原语——下一篇的信号量就是它。

下一篇：信号量与 PV 操作