Lecture 4：知识 - 同步与互斥

并发题先分清“谁不能同时访问同一资源”（互斥）和“谁必须在谁之后发生”（同步），再为每个资源或前驱关系设置语义清晰的锁/信号量。不能只背 PV 模板而不分析资源和事件。

4.1 同步、异步与互斥

4.1.1 基本关系

• 同步（直接制约关系）：为完成共同任务，进程/线程须在某些事件点相互等待、配合。例如产品放入缓冲区后，消费者才能取出。
• 异步性：并发进程以独立、不可预知的速度推进；同步机制用于建立必要的先后约束。
• 互斥（间接制约关系）：多个进程竞争访问同一数据或资源，执行结果会受交错次序影响，故同一时刻只允许一个访问者。

临界资源是被保护的对象；临界区是访问临界资源的那段代码，二者不能混淆。

4.1.2 临界区结构与四准则

do {
    entry section;     // 进入区：申请许可、上锁或等待
    critical section;  // 临界区：访问临界资源
    exit section;      // 退出区：解锁、释放资源
    remainder section; // 剩余区：其他代码
} while (true);

临界区问题的四项原则：

1. 空闲让进：临界区空闲时，应尽快允许一个请求者进入。
2. 忙则等待：已有进程在临界区时，其他请求者必须等待，保证互斥。
3. 有限等待：一个进程申请后，必须能在有限时间内进入，避免饥饿。
4. 让权等待：不能进入时应让出 CPU，避免持续占用 CPU 自旋。

前 3 项侧重正确性；让权等待侧重效率。自旋锁可保证互斥，但不满足让权等待。

4.2 软件与硬件互斥方法

4.2.1 软件算法的比较

Peterson 的核心不是 turn 的“所有权”，而是双方都申请时的谦让：进程 $i$ 先设置 flag[i]=true，再令 turn=j，在“对方也想进入且轮到对方”时等待。

4.2.2 中断屏蔽

单处理机内核可在进入临界区前关中断、退出后开中断，使临界区执行期间不会因中断被切换。它简单高效，但：

• 不适合多处理器：关闭本 CPU 中断不能阻止其他 CPU 进入临界区。
• 只能由内核使用：关/开中断是特权指令，用户程序不能也不应执行。
• 只能保护很短的内核临界区，否则会损害中断响应。

4.2.3 TestAndSet、Swap 与自旋锁

TestAndSet（TSL）和 Swap/Exchange 是不可中断的硬件原子指令，可将“检查锁”和“置锁”合成为一个原子动作，适用于多处理器：

// 返回 lock 的旧值，同时把 lock 置为 true；整个调用原子完成
while (TestAndSet(&lock)) {
    ;  // busy waiting
}
/* critical section */
lock = false;

• 优点：实现简单，不会出现软件算法中检查/置锁被拆开的漏洞；适合锁持有时间短的多核临界区。
• 缺点：等待者一直占用 CPU，违反让权等待；单核或临界区较长时浪费 CPU。
• 普通函数调用不天然原子；必须由硬件原子指令实现，才可作为互斥基础。

互斥锁可抽象为 acquire()/release()。获取不到锁时，自旋锁循环检查；可阻塞 mutex 则将等待线程挂入队列、让出 CPU。

4.3 信号量与 PV 原语

4.3.1 定义与操作

信号量是表示资源数量或事件状态的整型/记录型变量，只能通过初始化、wait 和 signal 原子访问：

PV 操作都是原语，必须一气呵成。整型信号量的简化形式为：

wait(S)   { while (S <= 0) ; S--; }  // 资源不可用时忙等
signal(S) { S++; }

它仍然忙等。记录型信号量以等待队列实现让权等待：

typedef struct { int value; queue L; } semaphore;

wait(S) {
    S.value--;
    if (S.value < 0) { add_this_process_to(S.L); block(); }
}
signal(S) {
    S.value++;
    if (S.value <= 0) { remove_a_process_from(S.L); wakeup(); }
}

若 S.value<0，其绝对值常可理解为等待该资源的进程数。队列可按 FIFO 等策略组织；多处理机上，PV 的原子性仍要借助硬件原子操作或锁保证。

4.3.2 用 PV 实现互斥和同步

互斥：每个临界资源设置一个互斥信号量，初值通常为 1。

semaphore mutex = 1;
P(mutex);
/* critical section */
V(mutex);

同步：每一对前驱/后继关系设置一个同步信号量，初值通常为 0；前操作完成后 V(S)，后操作开始前 P(S)。

semaphore S = 0;
P1: 前操作; V(S);
P2: P(S); 后操作;

P 可能阻塞，V 不会使执行它的进程因资源不足而阻塞。因此多个 P 的顺序尤其重要：若先 P(mutex)、后因同步 P(S) 阻塞，就会持锁等待，能产生事件的进程可能无法进入临界区，导致死锁。相邻且独立的 V 操作通常可交换，但仍须核对题目所要求的事件顺序。

4.4 PV 题的通用解法

1. 列出并发进程/线程和每个进程是否反复执行；未说明只执行一次时通常要写 while (true)。
2. 找临界资源：同一可写对象的读-写、写-读、写-写通常要互斥；读-读通常可并行。
3. 找每个前驱关系：前操作之后放 V，后操作之前放 P。
4. 为每个资源或关系定义语义明确的信号量，并按资源数或事件是否已发生设置初值。
5. 检查所有 P：是否有对应 V；共享计数器是否被保护；是否出现拿着一把锁再等待另一条件的环。

一个资源存在多组互斥关系时，可设置多个更细粒度的锁来提高并发度，不能因“都是全局变量”就把无冲突的读操作也串行化。

4.5 经典同步问题

4.5.1 生产者-消费者

大小为 $N$ 的有界缓冲区：满时生产者等待，空时消费者等待；放入/取出缓冲区还要互斥。

semaphore mutex = 1, empty = N, full = 0;

producer() {
    while (true) {
        item x = produce();
        P(empty); P(mutex);
        put(x);
        V(mutex); V(full);
    }
}
consumer() {
    while (true) {
        P(full); P(mutex);
        item x = get();
        V(mutex); V(empty);
        consume(x);
    }
}

必须先 P(empty/full) 再 P(mutex)。否则进程可能拿着 mutex 在条件信号量上阻塞，另一类进程无法进入缓冲区改变条件，从而死锁。多生产者/多消费者、一次取/放多个产品时，仍按“资源数量同步 + 缓冲区互斥”拆分，并将批量操作整体分析。

原资料中的单槽水果盘是两类生产者、两类消费者的具体变体：父亲只放苹果、母亲只放橘子；女儿只取苹果、儿子只取橘子。盘子容量为 1，初始为空，可这样设置：

semaphore plate = 1, apple = 0, orange = 0;

father()   { P(plate);  put_apple();   V(apple);  }
mother()   { P(plate);  put_orange();  V(orange); }
daughter() { P(apple);  take_apple();  V(plate);  }
son()      { P(orange); take_orange(); V(plate);  }

四个函数可各自循环执行。plate 保证盘子空时仅有一个生产者能放入水果；apple/orange 分别保证对应消费者只能取到自己需要的水果。仅在这种单槽、一次放/取一个且三个信号量按上面配对使用的模型下，同步信号量已顺带保证盘子的互斥访问，不一定需要额外 mutex；换成多个槽或一次批量操作时必须重新分析，不能直接套用。

4.5.2 读者-写者

共享文件允许多个读者同时读；写者写入时不允许读者或其他写者访问。读者优先模型：

semaphore rw = 1;       // 文件的读写互斥
semaphore mutex = 1;    // 保护 readCount
int readCount = 0;

reader() {
    P(mutex);
    if (readCount == 0) P(rw); // 第一个读者阻止写者
    readCount++;
    V(mutex);
    read_file();
    P(mutex);
    readCount--;
    if (readCount == 0) V(rw); // 最后一个读者放行写者
    V(mutex);
}
writer() { P(rw); write_file(); V(rw); }

读-读不互斥，读-写、写-读、写-写互斥。读者优先可能让写者饥饿；写者优先或公平策略需增加门闩/排队信号量，阻止新读者越过已等待的写者。

4.5.3 哲学家进餐

$n$ 名哲学家各需同时取得左右两支筷子才能进餐；每支筷子一次只能被一人使用。所有人都先取左再等待右会形成环路等待，可能死锁。

• 最多允许 $n-1$ 人同时尝试取筷子。
• 为筷子编号，统一按小编号到大编号申请，破坏循环等待。
• 引入服务员/全局锁，使“检查两支筷子都可用并占用”成为原子动作；不足则等待。
• 可为每支筷子设置资源信号量，但必须注意全局锁的释放位置，不能持锁等待筷子。

原资料中的“还需一只碗”变体：$n>3$ 名哲学家围坐，中央有 $m>1$ 只共享碗，每人须同时取得一只碗和左右两支筷子才能吃。任意相邻两人不能同时用餐，因此同时用餐人数的上界为

$$\min\left(m,\left\lfloor\frac n2\right\rfloor\right).$$

若希望避免“已拿到碗和一支筷子，却永远等另一支”的死锁，可让服务员在短暂持有互斥锁期间一次性检查并分配这三件资源；三件不齐时先释放该锁，再等待条件变化，不能持锁睡眠或让所有人先各占一件资源。就餐阶段不持服务员锁，归还资源时再短暂加锁并唤醒等待者。这样互不相邻且有碗可用的哲学家仍可并行用餐；具体唤醒顺序还需考虑公平性，避免个别人饥饿。

4.6 管程

4.6.1 基本思想

管程（monitor）是高级同步模块，封装：共享数据结构、初始化语句、操作共享数据的一组入口过程，以及管程名称。外部只能通过入口过程访问共享数据；同一时刻最多一个进程/线程在管程内执行，因此入口过程天然互斥。

它把 PV 代码中的锁、共享变量和操作封装起来，降低漏锁、错序的风险；管程不等同于管道。

4.6.2 条件变量

管程内的条件变量用于“条件不满足则等待、条件满足则唤醒”：

• x.wait()：调用者阻塞并插入 x 的等待队列，同时释放管程，以便其他进程进入。
• x.signal()：若 x 队列有等待者，唤醒其中一个；若没有等待者，通常不累计资源数量。

条件变量用于同步，不是普通资源计数信号量。生产者-消费者可在管程中封装 count、缓冲区、full、empty 条件变量：满时生产者等待，空时消费者等待，插入或取出后唤醒对应队列。

IMPORTANT · 等待条件要重检 原 PDF 第 39 页示例用 if (count==N) wait(full) 和 if (count==0) wait(empty) 表达条件等待。它不能无条件搬到常见的 Mesa 式条件变量：被唤醒者只是重新变为可竞争管程的线程，等它再次进入时，条件可能已被别人改变；实现还可能发生虚假唤醒。因此通常写成 while (count==N) full.wait()、while (count==0) empty.wait()，醒后重新检查。只有在明确采用立即移交执行权、无虚假唤醒等更强语义的模型下，才可按相应前提讨论一次 if 检查。

相关知识

• 科目导航：操作系统导航
• 阅读顺序：上一篇：处理器调度 · 下一篇：死锁

4.7 本节复盘

1. 互斥保护同一时刻的资源访问；同步保证前驱事件先发生；一个题往往同时需要二者。
2. 临界区要满足空闲让进、忙则等待、有限等待和让权等待；自旋锁不满足让权等待。
3. P 申请/等待且可能阻塞，V 释放/通知且可能唤醒一个进程；PV 必须原子执行。
4. 互斥锁初值通常为 1；资源计数按可用数量初始化；纯前驱同步信号量通常初值为 0。
5. 生产者消费者中先 P(empty/full) 后 P(mutex)；读者写者关注首读者加锁和末读者解锁；哲学家问题核心是破坏循环等待。
6. 写完 PV 代码后，逐个核对每个 P 的唤醒来源、每个共享计数的保护和是否存在持锁阻塞。