illegalCreed

中文

English

中文

English

Appearance

入门：竞态条件、临界区与互斥锁/信号量 ​

基于通用操作系统概念 · 核于 2026-08

速查 ​

  • 竞态条件（Race Condition）：多个线程并发访问共享变量且至少一个写，结果取决于执行时序——如 i++ 实际是"读-改-写"三步，两线程交错会丢失更新。根因是临界区没有互斥保护。
  • 临界区（Critical Section）：访问共享资源的代码段。临界区问题需满足四条件：①互斥（同一时刻只有一个进程在临界区内）；②前进（空闲时必须快速决定谁进，不能无限拖延）；③有限等待（任一请求进入者必须在有限时间内获准，不能饿死）；④让权等待（不能进的应让出 CPU，不能忙等——软考/经典教材的第四条）。
  • 互斥锁（mutex）：最朴素的互斥原语，二元状态（锁定/未锁定）。lock() 抢锁，unlock() 释放——谁加锁谁解锁（有所有权概念）。临界区套 lock/unlock 即可互斥。
  • 信号量（semaphore）：Dijkstra 提出，整型变量 + P（wait，减 1，<0 则阻塞）/V（signal，加 1，≤0 则唤醒一个） 原子操作。分二元信号量（0/1，等价 mutex）与计数信号量（初值 N，表示 N 个可用资源/位置）。
  • mutex vs semaphore 区别：mutex 有所有权（加锁者必须解锁），用于互斥；信号量无所有权（任意线程都能 V），既可互斥（初值 1）又可同步/计数（初值 N）。mutex 可"递归/带优先级继承"，信号量更适合资源池/事件通知。
  • 实现层级：硬件层（关中断、原子指令 test-and-set/compare-and-swap）、软件层（Peterson 算法）、OS/语言层（mutex/semaphore/管程）。
  • 进阶顺序：经典同步问题 → 管程、优先级反转与 Peterson 算法 → 参考。

一、竞态条件：为何并发出错 ​

并发编程的第一大坑就是竞态条件。看一段看似无害的计数器代码：

c
// 全局共享变量
int counter = 0;

// 线程函数：自增 10000 次
void* increment(void* arg) {
    for (int i = 0; i < 10000; i++) {
        counter++;   // 看似一条语句，实际是三条机器指令
    }
    return NULL;
}

counter++ 在机器层面是三步：

1. mov eax, [counter]    ; 读：把 counter 从内存读到寄存器
2. inc eax               ; 改：寄存器值 +1
3. mov [counter], eax    ; 写：把新值写回内存

两个线程并发执行时，这三步会交错：

线程 A                       线程 B
读 counter=5
                            读 counter=5   ← 读到了旧值！
改 6
                            改 6
写 counter=6
                            写 counter=6   ← 两次自增，结果只 +1（丢失更新）

期望结果是 7，实际是 6——这就是丢失更新（Lost Update）。counter 最终值可能远小于 20000，且每次运行结果不同（取决于时序）。这就是竞态条件：结果依赖于不可控的执行顺序。

  • 根因：counter++ 的"读-改-写"不是原子的，中间能被其他线程插入。
  • 解决：把这段代码包进临界区，用互斥锁保证同一时刻只有一个线程执行它。

二、临界区问题：四条件 ​

临界区（Critical Section）是进程/线程访问共享可变资源的代码段。临界区问题的目标是设计一个协议，让进程互斥进入临界区，且不死锁/饿死。经典教材（如 Silberschatz《操作系统概念》）要求满足三个条件，国内教材常加第四条"让权等待"：

条件含义反例
① 互斥（Mutual Exclusion）任一时刻最多一个进程在临界区内不满足→竞态条件
② 前进（Progress）临界区空闲时，想进的进程必须能尽快决定谁进（不能无限推诿）不满足→死锁（谁都不进）
③ 有限等待（Bounded Waiting）任一进程提出进入请求后，必须在有限时间内获准（有上界）不满足→饿死（某进程永远等不到）
④ 让权等待（让权/空闲让进）不能立即进入的进程应让出 CPU（不忙等），提高效率不满足→自旋浪费 CPU
  • 前三条是正确性要求（互斥、不死锁、不饿死），第四条是效率要求（避免空转）。
  • 忙等待（Busy Waiting / 自旋）：进程不睡眠，循环反复检查锁是否释放——浪费 CPU，但无上下文切换开销，适合临界区极短的场景（自旋锁）。

三、互斥锁（mutex）：最朴素的互斥 ​

互斥锁（Mutual Exclusion Lock，mutex）是最简单也最常用的互斥原语。它是一个二元状态变量（锁定/未锁定），配两个原子操作：

c
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

pthread_mutex_lock(&lock);    // 进入临界区：抢锁（已被占则阻塞）
// ──────── 临界区开始 ────────
counter++;                    // 受保护，不会被其他线程打断
// ──────── 临界区结束 ────────
pthread_mutex_unlock(&lock);  // 离开临界区：释放锁，唤醒一个等待者
  • 所有权（Ownership）：mutex 谁加锁谁解锁——线程 A lock 的，必须由线程 A unlock，不能由 B 代劳。这是 mutex 与信号量的关键区别。
  • 阻塞 vs 自旋：标准 mutex 抢不到锁会让线程睡眠（进入内核等待队列，不占 CPU）；自旋锁（spinlock）则忙等（循环检查，占 CPU）。
  • 典型实现：mutex 内部用原子指令（如 xchg/cmpxchg）测试锁状态，配合 OS 的等待队列（futex/Linux）实现阻塞与唤醒。

四、信号量（semaphore）：Dijkstra 的发明 ​

信号量（Semaphore）由 Dijkstra 在 1965 年提出，是一个整型变量 S，配两个原子操作。Dijkstra 用荷兰语命名：**P（proberen，测试/减）**和 V（verhogen，增加），英文常叫 wait/signal 或 down/up：

P(S):  while S <= 0 do nothing;   // 等待（S≤0 表示无资源）
       S = S - 1;                 // 占用一个资源

V(S):  S = S + 1;                 // 释放一个资源
       // 若有等待者，唤醒一个

现代实现把"忙等"换成"阻塞"，P 在 S<=0 时让线程睡眠：

c
sem_t sem;
sem_init(&sem, 0, 1);   // 初值 1

sem_wait(&sem);    // P 操作：S-1，若 <0 阻塞
// 临界区
sem_post(&sem);    // V 操作：S+1，若 ≤0 唤醒一个等待者

信号量分两类：

类型初值用途等价物
二元信号量（Binary Semaphore）0/1互斥≈ mutex
计数信号量（Counting Semaphore）N表示 N 个可用资源/位置（如连接池、缓冲区格子）mutex 管不了
  • 二元信号量初值 1，行为类似 mutex——但没有所有权（任意线程都能 post）。
  • 计数信号量初值 N，常用于资源计数：如"缓冲区还能放几个数据"（empty 槽位数）。

五、mutex vs semaphore：区别与混淆 ​

很多人把 mutex 和 semaphore 混用，但它们有本质区别：

维度mutex（互斥锁）semaphore（信号量）
所有权✅ 有（谁 lock 谁 unlock）❌ 无（任意线程可 V）
状态二元（锁定/未锁定）整数（可 >1）
主要用途互斥（保护临界区）互斥 + 同步/计数
典型场景保护共享变量生产者-消费者的 empty/full、事件通知
优先级继承通常支持（解决优先级反转）一般不支持
递归可做可重入（同线程多次 lock）不支持递归
  • 关键区别：mutex 强调"所有权"——加锁的线程必须负责解锁；信号量没有所有权，任意线程都能 post。这让信号量能做跨线程同步（A 生产、B 消费），而 mutex 只能做单线程内的互斥。
  • 何时用 mutex：保护一段共享数据（如链表、计数器）——"我要独占访问这个资源"。
  • 何时用信号量：协调多个线程的执行顺序或资源数量——"等到有数据了再消费""最多 N 个连接"。
  • 易错：用信号量初值 1 当 mutex，若非所有者线程 post 会破坏互斥——这是常见 bug。

下一步 ​

理解了竞态条件、临界区四条件与 mutex/semaphore 后，下一步用它们解决三大经典问题——经典同步问题（生产者-消费者、读者-写者、哲学家就餐的信号量伪代码详解）。