7.5 同步与互斥

同步与互斥是并发编程的核心问题，当多个进程/线程并发访问共享资源时，如果不进行同步控制，就会出现竞态条件，导致程序结果不正确。理解同步与互斥的原理，是写出正确高效的并发程序的基础。

竞态条件与临界区

竞态条件（Race Condition）

当多个进程/线程同时访问和修改共享数据时，最终的结果取决于进程/线程执行的相对时序，结果不确定，这种情况就叫做竞态条件。

示例：两个线程同时对全局变量count做加1操作

int count = 0;

void increment() {
    count++; // 这行代码实际分为三步：读取count的值，加1，写回count
}

如果两个线程同时执行increment：

• 理想情况：线程1执行完三步，线程2再执行，count变成2
• 竞态情况：线程1读取count=0，还没写回的时候，线程2也读取count=0，两个线程都加1写回，最终count=1，而不是正确的2

竞态条件会导致程序结果不确定，出现难以排查的bug，必须避免。

临界区（Critical Section）

访问共享资源的代码片段叫做临界区，同一时间只能有一个进程/线程进入临界区执行，其他进程/线程必须等待，这样才能避免竞态条件。

临界区的访问需要满足四个条件：

1. 互斥：同一时间只能有一个进程进入临界区
2. 前进：如果临界区为空，应该允许一个进程立即进入，不能无限等待
3. 有限等待：进程等待进入临界区的时间必须是有限的，不能出现饥饿
4. 让权等待：进程不能进入临界区时，应该让出CPU，不要忙等

互斥的实现方法

1. 互斥锁（Mutex）

互斥锁是最常用的同步机制，用来保护临界区，保证同一时间只有一个线程持有锁，进入临界区。

• 操作：
  • lock()：获取锁，如果锁已经被持有，就阻塞等待
  • unlock()：释放锁，唤醒等待的线程
• 原理：通常由操作系统内核实现，锁的状态由内核维护，获取失败时线程会阻塞，让出CPU，不会忙等
• 注意：获取锁之后必须在所有路径上释放锁，包括异常路径，否则会导致死锁

2. 自旋锁（Spinlock）

自旋锁和互斥锁类似，区别是获取锁失败时不会阻塞，而是一直循环尝试获取锁，直到成功。

• 优点：不需要上下文切换，开销小，适合临界区非常短，锁持有时间很短的场景
• 缺点：长时间自旋会浪费CPU资源，如果锁持有时间长，性能比互斥锁差
• 适用场景：内核态编程，临界区非常短，多处理器系统
• 注意：单核CPU上不要用自旋锁，自旋的过程中其他线程无法运行，锁永远不会被释放

3. 读写锁（Read-Write Lock）

读写锁适合读多写少的场景，允许多个线程同时读，但同一时间只能有一个线程写，写操作和读操作互斥。

• 锁的状态：
  • 读模式：多个线程可以同时获取读锁，适合读操作
  • 写模式：只能有一个线程获取写锁，写的时候不能读
• 优点：读多写少的场景下比互斥锁并发度高很多
• 缺点：实现复杂，有一定的开销，如果写操作多，性能不如普通互斥锁
• 适用场景：缓存、配置等读多写少的共享资源

4. 信号量（Semaphore）

信号量是一个计数器，用来控制访问共享资源的线程数量，可以实现互斥和同步。

• 操作：
  • P操作（wait）：计数器减1，如果计数器<0，线程阻塞等待
  • V操作（post）：计数器加1，如果有等待的线程，唤醒一个
• 二值信号量：计数器只能是0或1，相当于互斥锁，可以用来实现互斥
• 计数信号量：计数器可以大于1，表示可用资源的数量，用来控制同时访问资源的最大线程数
• 适用场景：生产者消费者问题、限流、资源池等场景

5. 条件变量（Condition Variable）

条件变量用来实现线程之间的等待通知机制，当某个条件不满足时，线程阻塞等待，其他线程满足条件后通知等待的线程。

• 条件变量总是和互斥锁一起使用：
  • wait()：释放互斥锁，阻塞等待条件，被唤醒后重新获取互斥锁
  • signal()：唤醒一个等待的线程
  • broadcast()：唤醒所有等待的线程
• 为什么需要和互斥锁一起使用：条件判断本身是共享的，需要互斥锁保护，避免竞态条件
• 适用场景：生产者消费者问题、事件通知、线程池任务调度等场景

6. 原子操作

对于简单的操作（比如加1、减1、比较交换），可以用CPU提供的原子操作实现同步，不需要锁。

• 原子操作是不可中断的，要么全部执行完成，要么不执行，不会被其他线程打断
• 常见的原子操作：原子加、原子减、比较并交换（CAS）
• 优点：开销极小，不需要上下文切换，没有死锁问题
• 缺点：只能用于简单的操作，复杂场景还是需要锁
• 适用场景：计数器、状态标志等简单的共享变量操作

死锁

死锁是指多个进程/线程互相等待对方持有的资源，导致所有线程都无限期阻塞，无法继续执行。

死锁产生的四个必要条件

1. 互斥条件：资源是独占的，同一时间只能被一个进程持有
2. 持有并等待：进程已经持有了至少一个资源，又请求其他进程持有的资源
3. 不可剥夺：进程持有的资源只能自己释放，不能被其他进程强行剥夺
4. 循环等待：多个进程之间形成循环等待资源的关系，每个进程都等待下一个进程持有的资源

四个条件同时满足时，就会产生死锁。

死锁的预防

预防死锁就是破坏四个必要条件中的一个或多个：

1. 破坏互斥条件：让资源可以共享，比如只读资源可以同时访问，但很多资源无法共享，适用场景有限
2. 破坏持有并等待：进程一次性申请所有需要的资源，或者申请资源时先释放已经持有的资源
3. 破坏不可剥夺条件：进程申请的资源无法满足时，强制释放已经持有的资源
4. 破坏循环等待：对资源进行编号，进程必须按编号顺序申请资源，避免循环等待

死锁的避免

• 银行家算法：在分配资源前检查系统是否处于安全状态，如果分配后系统可能进入死锁，就拒绝分配
• 实现复杂，开销大，实际系统中很少使用

死锁的检测和恢复

• 允许系统发生死锁，定期检测死锁，然后通过剥夺资源、终止进程等方式恢复
• 检测方法：资源分配图、检测循环等待
• 恢复方法：终止一个或多个死锁进程，剥夺资源

死锁的最佳实践

实际开发中避免死锁的最佳实践：

1. 避免一个线程同时持有多个锁
2. 如果必须持有多个锁，所有线程都按相同的顺序获取锁，避免循环等待
3. 不要持有锁的同时等待其他资源
4. 使用定时锁，获取锁超时后释放已经持有的锁，避免无限等待
5. 尽量减少锁的粒度和持有时间，减少锁冲突的概率

经典同步问题

1. 生产者消费者问题

• 问题描述：多个生产者线程生产数据放到缓冲区，多个消费者线程从缓冲区取数据消费，需要保证缓冲区满时生产者等待，缓冲区空时消费者等待，线程之间不会互相干扰。
• 解决方案：用一个互斥锁保护缓冲区，两个条件变量（非空、非满），或者用信号量实现。

2. 读者写者问题

• 问题描述：多个读者可以同时读，写者和其他写者、读者都互斥，分为读优先和写优先两种模式。
• 解决方案：用读写锁实现，或者用互斥锁和条件变量实现。

3. 哲学家进餐问题

• 问题描述：五个哲学家围坐在桌子旁，每人左右两边各有一根筷子，哲学家要么思考，要么吃饭，吃饭需要同时拿到左右两根筷子，如何避免死锁和饥饿。
• 解决方案：最多允许四个哲学家同时拿左边的筷子，或者哲学家先拿编号小的筷子再拿编号大的，破坏循环等待条件。

同步与互斥的最佳实践

1. 尽量避免共享：最好的同步就是没有同步，尽量不要共享可变数据，使用消息传递代替共享内存，从根源上避免竞态条件
2. 最小化临界区：临界区越小越好，只在必须保护的地方加锁，减少锁的持有时间
3. 避免锁嵌套：尽量不要同时持有多个锁，如果必须持有，严格按顺序获取，避免死锁
4. 选择合适的同步原语：根据场景选择合适的锁，读多写少用读写锁，短临界区用自旋锁，简单操作用原子操作
5. 避免忙等：除了非常短的临界区，不要用自旋锁忙等，浪费CPU资源
6. 小心使用无锁编程：无锁编程（CAS等）复杂度很高，容易出现问题，优先使用成熟的锁机制，没有特殊必要不要自己实现无锁数据结构

思考问题

1. 什么是竞态条件？举一个你开发中遇到的竞态条件的例子。
2. 互斥锁和自旋锁有什么区别？分别适合什么场景？
3. 死锁产生的四个必要条件是什么？如何预防死锁？
4. 条件变量为什么要和互斥锁一起使用？单独使用条件变量会有什么问题？