并发程序最棘手的地方，往往不在于某一行代码写错，而在于两段原本正确的代码以意料之外的顺序交错执行。两个进程或线程同时修改同一份共享数据时，最终结果可能取决于调度时机；这种不确定性就是竞态条件。

同步与互斥机制要解决的，正是这类“谁先运行、谁后运行”带来的问题。理解它们，可以从一个最常见的共享变量场景开始。

// count 初始为 0
count = count + 1;

这条语句在机器层面通常不是一步完成的，而是“读出 count、加一、写回”。如果两个线程都读到 0，分别计算出 1 后再写回，最后的结果仍是 1，而不是预期的 2。

问题不在加法，而在这一串操作被并发地拆开和交错了。

一、临界区：问题发生的位置

**临界区（critical section）**是程序中访问并修改共享资源的那一段代码。

共享资源可以是全局变量、共享内存、文件、打印机或其他硬件设备。只读共享数据未必会出问题，但只要多个执行流可能并发写入，或者读写之间存在依赖，就需要警惕临界区。

一个典型进程可以抽象为四个部分：

进入区 -> 临界区 -> 退出区 -> 剩余区

• 进入区：尝试获得进入临界区的资格。
• 临界区：实际访问共享资源。
• 退出区：释放资格，让其他执行流可以继续。
• 剩余区：与共享资源无关的普通工作。

围绕临界区，有两个容易混淆的概念：

• 互斥：同一时刻至多允许一个进程或线程进入临界区，解决“不能同时做”的问题。
• 同步：协调多个执行流的先后顺序，解决“必须等某件事发生后才能做”的问题。

例如，多个线程修改同一个余额时需要互斥；生产者必须先放入数据、消费者才能取走数据时，则还需要同步。互斥强调独占，同步强调顺序，实际系统中二者经常配合出现。

二、正确的临界区方案应满足什么

一个可用的临界区解决方案，通常需要满足以下条件：

1. 空闲让进：临界区空闲且有进程想进入时，不能无故阻塞它。
2. 忙则等待：已有进程在临界区内时，其他竞争者必须等待，保证互斥。
3. 有限等待：等待不能无限期持续，不能让某个进程一直饥饿。
4. 让权等待：若等待时间较长，应主动让出处理器，而不是持续空转消耗 CPU。

前面三点是经典临界区问题最常讨论的正确性要求；

第四点更多体现工程上的性能取舍。现代操作系统通常会把短暂竞争交给自旋，把较长等待转为睡眠与唤醒。

三、忙等互斥：简单，但不总划算

忙等互斥是解决方式的一种。

**忙等（busy waiting）**是指进程在等待条件满足时不停循环检查，而不主动放弃 CPU。它的优点是响应快、实现直接；缺点也很明显：等待期间 CPU 可能什么有用工作都没做。

忙等适合锁预计很快释放的场景，例如内核中极短的临界区，或多核处理器上等待时间远小于一次睡眠和唤醒的开销。若临界区耗时较长，更适合让等待者阻塞，等资源可用时再唤醒。

1. 屏蔽中断

在单处理器系统中，若当前 CPU 关闭中断，时钟中断就无法触发调度，当前进程不会被切走。于是它可以在进入临界区前关闭中断，离开后再恢复中断。

这种方法只适合操作系统内核的极短代码段：普通用户进程若能随意关闭中断，可能独占 CPU，整个系统都失去响应。更重要的是，多处理器系统中关闭一颗 CPU 的中断，并不能阻止其他 CPU 同时访问共享资源，因此它不能单独解决多核互斥问题。

总结

• 中断主要是 外部中断（外部IO） 和 时钟中断（定时器到了）
• 屏蔽中断，是一种最最最最直接的方法，多用于优先级特别高的任务，干完活一定记得打开中断，否则其他任务响应不了
• 多核CPU，屏蔽中断不可行，因为只能屏蔽自己的CPU，但屏蔽不了其他的CPU
• 一般 单CPU、快速行为 的场景使用使用

2. 锁变量与自旋锁

最直观的思路是用一个共享变量 lock 表示资源状态：0 表示空闲，1 表示已被占用。

while (lock != 0) {
    // 等待
}
lock = 1;

/* 临界区 */

lock = 0;

它看似合理，却依然存在竞态：两个线程可能同时观察到 lock == 0，然后都执行 lock = 1，最终同时进入临界区。

根源在于“检查锁是否空闲”和“把锁设为占用”是两个可被打断的动作。

看一个例子（伪代码）：

int lock = 0;
// 临界区代码段
extern void critical_region();
// 非临界区的代码段
extern void noncritical_region();

void process0() {
  while (1) {
    // 进入临界区
    // 判断是否有锁，如果没有锁，死循环等待锁被释放
    while ( lock );
    // 加锁
    lock = 1;
    critical_region();
    // 释放锁
    lock = 0;

    noncritical_region();
  }
}

void process1() {
  while (1) {
    // 进入临界区
    // 判断是否有锁，如果没有锁，死循环等待锁被释放
    while ( lock );
    // 加锁
    lock = 1;
    critical_region();
    // 释放锁
    lock = 0;

    noncritical_region();
  }
}

问题：当一个进程（或线程）读取到锁变量为0并计划将其设置为1以进入临界区时，如果在这个间隙内另一个进程被调度运行并同样读取到锁变量为0且将其设置为1，那么两个进程都可能错误地认为自己是唯一进入临界区的进程，从而导致临界区域内同时有两个或更多进程运行，违反了互斥原则。（通俗理解：准备写值的时候时间片到了）

要让锁变量真正可靠，必须把这两个动作合并为原子操作。

原子性指的是一个操作（或一组操作）在执行过程中，要么全部完成，要么完全不执行，不会停留在中间某个状态。换句话说，这个操作是不可分割的，其执行结果具有“全或无”的特性。

3. 严格轮询法

严格轮询法使用一个共享变量 turn，规定轮到谁，谁才能进入临界区。

以下是两个简单进程的C语言代码示例，它们通过共享变量turn来尝试实现互斥访问临界区:

int turn;                // 表示当前允许进入临界区的进程号
// 临界区代码段
extern void critical_region();
// 非临界区的代码段
extern void noncritical_region();

void process0() {
  while (1) {
    // 准备进入临界区，轮询判断当前进程能否进入
    while (turn == 0) {
      // 执行临界区
      critical_region();
      turn = 1;            // 标记当前可以进入临界区的是进程1
      noncritical_region();
    }
  }
}

void process1() {
  while (1) {
    // 准备进入临界区，轮询判断当前进程能否进入
    while (turn == 1) {
      // 执行临界区
      critical_region();
      turn = 0;            // 标记当前可以进入临界区的是进程0
      noncritical_region();
    }
  }
}

当进程0完成临界区的操作后，它会将turn设置为1，以此通知进程1可以进入临界区。如果进程1迅速完成了其临界区的操作，并将turn重置为0，此时两个进程都位于临界区之外。然而，如果进程0在进程1还未将turn改回0之前就已经完成了其非临界区的操作并再次尝试进入临界区，它将发现turn仍为1，因此不得不继续等待，即使此时进程1可能还在执行非临界区的任务。

这带来了一个问题：当进程执行速度差异显著时，简单的轮转和忙等待机制可能导致不公平的等待时间，甚至可能违反互斥原则中的一个重要原则——位于临界区外的进程不应当被其他非临界区的进程阻塞。在本例中，进程0被进程1（尽管进程1并未在临界区内）间接阻塞，这违反了上述原则，因此该方案在多数情况下并不是一个高效的互斥实现方式。

理解

1. 初始/阶段一：process1 运行
   • process1 进入临界区 critical_region()。
   • process1 将 turn 改为 0。
   • process1 进入极长时间的非临界区 noncritical_region()（此时 turn 依然为 0）。
2. 阶段二：process0 运行第 1 次
   • process0 检查 while (turn == 0) 为真，顺利进入临界区 critical_region()。
   • process0 执行完毕，把 turn 改为 1。
   • process0 执行自己的 noncritical_region() 并快速结束。
3. 阶段三：process0 尝试进入第 2 次
   • process0 还想再次进入临界区，循环回来检查条件：while (turn == 0)。
   • 但此时 turn 是 1（因为 process1 还没有机会把它改回 0）！
   • process0 被死死挡在门外，必须等待 turn 重新变成 0。
4. 关键问题出在哪？
   • 要把 turn 变成 0，必须由 process1 来执行 turn = 0。
   • 但 process1 此时正卡在极长的 noncritical_region() 里面！
   • process1 只有等自己的 noncritical_region() 执行完，才能重新回到循环开头检查 while (turn == 1)，然后进入临界区，最后才能把 turn 改回 0。

虽然 process0 执行完 turn = 1 后让出了机会，但它只能再等 process1 进一次临界区并把 turn 改回 0，自己才能进下一次。

这种现象违反了进程同步的“空闲让进”/“非临界区不应阻塞其他进程”原则：

• 临界区明明空着（process1 在做与临界区无关的非临界区代码）；
• 但由于严格轮流机制，process0 被一个处于非临界区的进程阻塞了。

四、Peterson 算法：用意愿和谦让解决双进程竞争

原始方式

#define FALSE	0
#define TRUE	1

// 临界区代码段
extern void critical_region();
// 非临界区的代码段
extern void noncritical_region();

int interested[2];			// 记录每个进程是否愿意进入临界区

void enter_region(int process) {
	int other = 1 - process;			// 进程编号就是0 或 1

	interested[process] = TRUE;			// 标记本进程希望进入临界区

	// 等待条件：检查对方是否也想使用，且最后一次是谦让的
	while (interested[other] == TRUE);
}

void leave_region(int process) {
	// 标记本进程已离开临界区
	interested[process] = FALSE;
}

void process0() {
	do {
		enter_region(0);
		critical_region();
		leave_region(0);
		noncritical_region();
	}while (TRUE);
}

void process1() {
	do {
		enter_region(1);
		critical_region();
		leave_region(1);
		noncritical_region();
	}while (TRUE);
}

问题：由于时间片的过期问题，可能出现死锁。

• 具体过程如下

  假设系统初始化时：interested[0] = FALSE, interested[1] = FALSE。

  1. 时刻 T1（进程 0 运行）：
     • 进程 0 调用 enter_region(0)。
     • 计算得到 other = 1。
     • 执行 interested[0] = TRUE;（标记进程 0 极度想进临界区）。
     • 就在此时，进程 0 的时间片用完，操作系统强行剥夺 CPU 控制权，进行上下文切换。
  2. 时刻 T2（切换到进程 1 运行）：
     • 进程 1 开始调用 enter_region(1)。
     • 计算得到 other = 0。
     • 执行 interested[1] = TRUE;（标记进程 1 也极度想进临界区）。
     • 接下来，进程 1 执行 while (interested[other] == TRUE);：
       • 检查 interested[0]，发现值为 TRUE。
       • 进程 1 条件成立，卡在 while 循环里死等（自旋等待）。
  3. 时刻 T3（进程 1 时间片用完，切回进程 0）：
     • 进程 0 从刚才被打断的地方（while 语句）继续向下执行：
       • 执行 while (interested[other] == TRUE);：
       • 检查 interested[1]，发现值为 TRUE（因为进程 1 刚才改了）。
       • 进程 0 条件成立，也卡在 while 循环里死等。

解决：主动谦让类型

Peterson 算法是经典的双进程软件互斥算法。它使用两个信息：

• interested[i]：进程 i 是否想进入临界区；
• turn：双方都想进入时，优先让谁进入。

伪代码：

#define FALSE	0
#define TRUE	1

// 临界区代码段
extern void critical_region();
// 非临界区的代码段
extern void noncritical_region();

int turn;					// 记录当前“轮到”哪个进程进入临界区
int interested[2];			// 记录每个进程是否愿意进入临界区

/* A B 
 */
void enter_region(int process) {
	int other = 1 - process;			// 进程编号就是0 或 1

	interested[process] = TRUE;			// 标记本进程希望进入临界区
	turn = other;						// 尝试将turn设置为另一个进程的编号

	// 等待条件：检查对方是否也想使用，且最后一次是谦让的（例如：B是最后一次谦让的，则A来执行）
	while (interested[other] == TRUE && turn == other);
}

void leave_region(int process) {
	// 标记本进程已离开临界区
	interested[process] = FALSE;
}

void process0() {
	do {
		enter_region(0);
		critical_region();
		leave_region(0);
		noncritical_region();
	}while (TRUE);
}

void process1() {
	do {
		enter_region(1);
		critical_region();
		leave_region(1);
		noncritical_region();
	}while (TRUE);
}

工作原理：

1. 表达意愿： 每个进程在进入临界区前，先将自己的 interested 设为 TRUE。
2. 主动谦让： 进程将 turn 设置为对方的进程号（turn = other），表示“后到的愿意让先到的优先”。
3. 安全检查： 进程检查 while (interested[other] == TRUE && turn == other)：
   • 如果对方不想进（interested[other] == FALSE），当前进程直接进入。
   • 如果双方都想进，则后设置 turn 的进程会把 turn 改为自己的编号（例如进程 1 后到，把 turn 改成了 0），从而导致自己满足 turn == other 的等待条件而主动自旋等待；而先到的进程（进程 0）则会因为 turn != 1 顺利打破循环进入临界区。
4. 释放退出： 处于临界区的进程执行完后调用 leave_region，将自己的 interested 改回 FALSE，从而唤醒在外等待的进程。

谁最后执行的turn，就是对面执行，自己不执行

解决：主动自信类型

伪代码：

#define FALSE    0
#define TRUE    1

// 临界区代码段
extern void critical_region();
// 非临界区的代码段
extern void noncritical_region();

int turn;          // 记录当前“轮到”哪个进程进入临界区
int interested[2]; // 记录每个进程是否愿意进入临界区

/* A B 
 */
void enter_region(int process) {
  int other = 1 - process;            // 进程编号就是0 或 1

  interested[process] = TRUE;            // 标记本进程希望进入临界区
  turn = process;                        // 尝试将turn设置为当前进程号

  // 等待条件：检查对方是否也想使用，且最后一次是谦让的
  while (interested[other] == TRUE && turn == process);
}

void leave_region(int process) {
  // 标记本进程已离开临界区
  interested[process] = FALSE;
}

void process0() {
  do {
    enter_region(0);
    critical_region();
    leave_region(0);
    noncritical_region();
  } while (TRUE);
}

void process1() {
  do {
    enter_region(1);
    critical_region();
    leave_region(1);
    noncritical_region();
  } while (TRUE);
}

该算法的工作原理如下：

• 在访问共享资源（即进入临界区）之前，每个进程通过调用enter_region函数并传入其进程号（0或1）来尝试获取访问权限。函数内部，进程首先表明其进入临界区的意愿，并尝试将turn变量设置为自身的进程号。

• 然而，如果此时另一个进程已经抢先设置了turn，则当前进程必须等待，直到该进程完成临界区操作并调用leave_region函数，从而释放其对interested数组中对应元素的锁定，并可能触发当前进程的继续执行。

说白了, 谁最后对turn赋值, 就是谁执行!

这种情况揭示了一个关键的问题：原始的Peterson算法（如上所述）在没有额外的同步机制（如原子操作或内存屏障）来确保interested和turn更新的原子性时，可能会受到竞争条件的影响，导致死锁或活锁。为了避免这种情况，现代的多线程编程库和操作系统通常提供更强大的同步原语，如互斥锁（mutexes）、信号量（semaphores）或原子操作，这些机制能够更可靠地管理对共享资源的访问。

值得注意的是，尽管这里描述的问题看起来是严重的，但在某些特定条件下（如进程执行速度差异极大，或者存在显式的同步点来确保进程不会完全同时进入竞争状态），原始的Peterson算法仍然可以在实际应用中发挥作用。然而，在设计并发系统时，了解并避免此类潜在的并发错误是至关重要的。

五、硬件原子指令：让“检查并加锁”不可分割

软件算法要面对指令交错的问题，硬件提供的原子读改写指令则能把关键步骤合成不可分割的一次操作。常见形式包括 Test-and-Set、XCHG 和比较交换（CAS）。

TSL：Test and Set Lock

可以把 TSL RX, LOCK 理解为一个原子动作：

1. 将 LOCK 的旧值读入寄存器 RX；
2. 同时把 LOCK 设为 1。

如果读到的旧值是 0，说明锁原本空闲，当前线程成功获得锁；若旧值已经是 1，则说明别人持有锁，需要继续等待。

enter_region:
    TSL RX, LOCK      ; RX <- LOCK 的旧值；LOCK <- 1（原子完成）
    CMP RX, #0
    JNE enter_region  ; 旧值非 0，继续自旋
    RET               ; 成功获得锁

leave_region:
    MOVE LOCK, #0     ; 释放锁
    RET

两个线程即便几乎同时执行 TSL，也只有一个能看到旧值为 0；另一个会看到 1 并继续等待。于是“检查”和“占用”之间不再留有竞态窗口。

XCHG 指令也可以实现同样的思想：先在寄存器中准备值 1，再原子地与内存中的锁变量交换。若交换前锁为 0，寄存器得到 0，表示加锁成功；否则继续尝试。

需要注意，早期教材常用“锁住内存总线”解释原子指令。现代多核处理器的具体实现通常更复杂，往往依赖缓存一致性协议和专门的原子操作语义；但从编程模型看，最重要的结论不变：其他处理器不能在该原子读改写的中间观察或插入操作。

六、从理论到实践：选择合适的等待方式

自旋锁的本质是忙等：持锁者很快释放时，避免睡眠与唤醒的切换成本，反而更高效；持锁者可能运行较久时，持续自旋会浪费 CPU，甚至影响持锁者得到调度的机会。

因此，实际编程通常遵循下面的取舍：

• 临界区很短、不可睡眠、内核或底层场景：考虑自旋锁与硬件原子指令。
• 临界区可能较长、用户态线程竞争：优先使用互斥锁，让等待线程阻塞。
• 存在明确先后依赖，如生产与消费：在互斥保护共享状态的基础上，再配合条件变量、信号量或事件进行同步。

无论使用哪一种原语，思考顺序都是一致的：先找出共享资源和临界区，再判断需要的是“只能一个人做”的互斥，还是“必须按顺序做”的同步，最后根据等待时长和运行环境选择忙等或阻塞。

总结

竞态条件来源于并发执行的不确定交错；临界区指出了需要保护的代码位置；互斥保证同一时刻只有一个执行流访问共享资源，同步则安排执行顺序。屏蔽中断、严格轮询、Peterson 算法和 TSL/XCHG 指令展示了从软件约定到硬件原子操作的不同解法。

这些算法最有价值的地方，并不只是应付考试中的流程推演，而是训练一种并发思维：任何“先检查、再操作”的共享状态逻辑，都要追问两步之间是否可能被别人插入。只要这个问题没有被原子性、锁或更高层同步原语明确回答，竞态就仍然潜伏在那里。

如果这篇文章对你有帮助，欢迎点赞、评论、关注、收藏。你们的支持是我前进的动力！