并发编程bug之源：死锁成因与重排序

Posted on Edited on In

Java 内存模型

每学习一个新概念时，一个有效的办法就是问自己，为什么需要这个技术，这个技术试图解决什么问题？怎么解决的？套用在 Java 内存模型 JMM 上，就是如下的问题：

  • 为什么需要JMM，它试图解决什么问题？
  • JMM是如何解决可见性等各种问题的？类似volatile，体现在具体用例中有什么效果？

这篇文章先分析为什么需要 JMM，然后顺便分析另一大并发 bug 来源，死锁。

从源代码到机器码会经历重排序

重排序，这就是需要一个统一 JMM 模型的原因。

  1. 编译器在不改变程序语义的前提下，重新安排语句执行顺序。（例子）
  2. 指令级并行 Instruction Level Parallelism（搜索关键词：ILP），改变机器指令的执行顺序。（用于方便流水线，提高并行度 parallelism）
  3. 内存系统重排序。现代的处理器使用写缓冲区（CPU cache）临时保存向内存写入的数据。
    为什么内存重排：写缓冲区可以保证指令流水线持续运行，它可以避免由于处理器停顿下来等待向内存写入数据而产生的延迟。同时，通过以批处理的方式刷新写缓冲区，以及合并写缓冲区中对同一内存地址的多次写，减少对内存总线的占用。
    导致的问题：当多个CPU同时（在另一个CPU写回之前）将同一个变量读入cache，任意一个CPU对该块内存的操作对于其他CPU来说都是不可见的。到写回内存时，先写入内存的就会被后写入的覆盖。

编译器重排序：1，处理器重排序：2，3。

ILP 重排应对方式：在编译生成指令序列时，插入由CPU支持的内存屏障 Memory Barriers（搜索关键词：Intel Memory Fence）

重排的依据：

数据依赖性：如果两个操作访问同一个变量，且这两个操作中有一个为写操作，此时这两个操作之间就存在数据依赖性。

控制依赖性：看一段程序：if (flag) int i *= 3; 。在这里，if这个操作A 和i *= 3这个操作B 存在控制依赖关系，只有操作A 完成了，才能确定是否执行操作 B。这样，并行度就被降低了。处理器通过猜测执行（Speculation），可以在执行操作A的同时计算 i 的值，如果操作A 为 true 就让 i 等于计算结果，否则不等于。

给（应用）程序员提供统一的内存模型还有一个原因是覆盖掉各种不同底层机器的差异，Intel，AMD，PowerPC，不同处理器有些内存一致（Cache Coherence）有些不遵循。

死锁的成因与各种应对

银行两个账户之间的 Transfer 是很好的例子。

1
2
3
4
5
6
7
8
void transfer(Account from, Account to, int amnt) {
    synchronized(from) {
        synchronized(to) {
            from.setAmount(from.getAmount() - amnt);
            to.setAmount(to.getAmount() + amnt);
        }
    }
}

要形成死锁 Deadlock，必备的四个条件，缺一不可：

  1. 互斥。某一代码块同一时刻只能一个线程执行。一般都会存在。
  2. hold and wait。抢到锁却继续等待其他资源（锁）
  3. 循环等待。两个线程互相等待对方
  4. 无法超时/剥夺的等待。

对应方法：

  1. 一般是基础条件，无法破除
  2. 用一把锁一次性获得所有资源。例子中，可以加上全局锁，确保from 和 to 可以被同时拿到。缺点：效率低下。
  3. 在锁之间创造先后顺序。需要获取两个锁时，优先尝试 id 大的那个。
  4. 加入超时。缺点：等待时间太久。拿到锁 from 后尝试获取锁 to，失败则立即释放锁 from，过一段时间（）再尝试。