锁执行死锁

Question

我有两个线程，一个id为0，一个id为1。根据这些信息我试图构造一个锁，但似乎死锁了，但我不明白为什么，谁能请帮帮我？

发生这种情况时，我试图构建一个场景，但这真的很难

  private int turn = 0;
  private boolean [] flag = new boolean [2];
   
  public void lock(int tid) {
    int other;
 
    other = (tid == 0) ? 1 : 0;

    flag[tid] = true;
    while (flag[other] == true) {
      if (turn == other) {
        flag[tid] = false;
        while (turn == other){}
        flag[tid] = true;
      }
    }
  }
 
  public void unlock(int tid) {
    //turn = 1-t;
    turn = (tid == 0) ? 1 : 0;
    flag[tid] = false;
  }

Answer 1

是的，此代码已损坏。这是..一个复杂的话题。如果您想了解更多信息，请深入了解 Java 内存模型 (JMM) - 您可以在网络表单中搜索该术语。

在基础上，JVM 中的每个字段 具有以下属性，除非它被标记为 volatile：

任何线程都可以自由地制作或不制作此字段的本地克隆。
VM 可以随时以任意方式自由同步这些克隆。可能在 5 秒内，也可能在 5 年内。 VM 可以自由地做任何它想做的事，规范有意不做很多保证。
为了解决这个问题，建立HB/HA（一个Happens-Before/Happens-After关系）。

换句话说，如果2个线程都查看同一个字段，而你还没有建立HB/HA，你的代码被破坏了，并且它被破坏了一种您无法可靠地测试的方式，因为 JVM 可以做任何它想做的事情。这包括在测试期间按预期工作。

要建立 HB/HA，您几乎需要 volatile/synchronized。不过，名单很长：

x.start() 是该线程 HA 中第一行的 HB。
退出 synchronized(x) {} 块是 HB 到 synchronized (x) {} 块的开始，假设两个 x 都指向同一个对象。
可变访问建立 HB/HA，但您无法真正控制在哪个方向。
请注意，许多库调用，例如对 ReadWriteLock 和 co 的调用，很可能在幕后 synchronizing/using 易变，因此顺便建立了某种形式的 HB/HA。
"Natural" HB/HA: 在单个线程中，先执行的行HB 后执行的行。有人可能会对这个说 'duh'。

请注意，HB/HA 并不意味着它们确实发生过。这只是意味着除了通过定时攻击之外，不可能从 HA 线观察到 HB 线之前的状态。这通常无关紧要。

问题

您的代码有两个线程，它们都查看同一个字段，不包含 volatile 或 synchronized 或以其他方式在任何地方建立 HB/HA，并且不使用库调用这样做。因此，此代码已损坏。

解决办法是在某个地方介绍一下。不确定您为什么要自行锁定 - 编写 ReadWriteLock 的人和 java.util.concurrent 包中的朋友非常聪明。你比他们做得更好的机会为零，所以就用它吧。

Answer 2

Dekker 算法是解释顺序一致性的一个很好的例子。

让我们先给你一些背景信息。当 CPU 执行存储时，CPU 不会等待将存储插入（一致的）缓存；一旦它被插入到缓存中，它就对所有其他 CPU 全局可见。 CPU 不等待的原因是，包含您要写入的字段的缓存行可能需要很长时间才能处于适当的状态；在可以在缓存行上执行写入之前，首先需要在所有其他 CPU 上使缓存行无效，这可能会使 CPU.

停止

为了解决这个问题，现代 CPU 使用存储缓冲区。所以商店被写入商店缓冲区，在未来的某个时候，商店将被提交到缓存。

如果存储之后是加载到不同的地址，则可能是存储和加载被重新排序。例如。稍后加载的缓存行可能已经处于正确状态，而较早存储的缓存行则不是。因此加载 'globally' 在存储 'globally' 执行之前执行；所以我们重新排序。

现在让我们看一下您的示例：

 flag[tid] = true;
 while (flag[other] == true) {

所以我们这里有一个存储，然后加载到不同的地址，因此存储和加载可以重新排序，结果是锁不会提供互斥，因为 2 个线程同时时间可以进入临界区

[PS] 这 2 个标志很可能在同一缓存行上，但这不是保证。

这是您在 X86 上看到的典型情况；可以用较新的负载重新订购较旧的商店。 X86 的内存模型称为 TSO。我不会详细介绍，因为有一个称为存储到负载转发的优化使 TSO 模型复杂化。 TSO 是对顺序一致性的放宽。

Dekker 和 Peterson 的互斥算法不依赖于像比较和设置这样的原子指令；但它们确实依赖于顺序一致的系统，并且顺序一致性的要求之一是加载和存储不会被重新排序（或者至少没有人应该能够证明它们被重新排序）。

因此，编译器需要做的是添加适当的 CPU 内存栅栏，以确保旧存储和新加载到不同地址不会被重新排序。在这种情况下，这将是一个昂贵的 [StoreLoad] 围栏。这取决于 ISA，但在 Intel X86 上，[StoreLoad] 将导致加载存储单元停止执行加载，直到存储缓冲区被耗尽。

您不能将数组的字段声明为可变的。但是有几个选项：

不使用数组，而是显式字段。
使用 AtomicIntegerArray
开始使用 VarHandle 摆弄栅栏。确保使用至少内存顺序不透明的 VarHandle 访问字段，以防止编译器优化任何 loads/stores.

除了我上面所说的，不仅仅是CPU会导致问题。因为在写入和读取标志之前没有适当的发生，JIT 也可以优化此代码。

例如：

if(!flag[other])
   return;

while (true) {
      if (turn == other) {
        flag[tid] = false;
        while (turn == other){}
        flag[tid] = true;
      }
    }

现在很明显这个锁可以无限期地等待（死锁）并且不需要看到标志的变化。可以进行更多优化，这可能会使您的代码完全混乱。

if (turn == other) {
      while (true) {}
}

如果在边缘之前添加适当的 happens，编译器将添加：

编译器围栏
CPU 内存栅栏。

Dekker 的算法应该按预期工作。

我还建议使用 JCStress 设置测试。 https://github.com/openjdk/jcstress 看看这个测试： https://github.com/openjdk/jcstress/blob/master/jcstress-samples/src/main/java/org/openjdk/jcstress/samples/concurrency/mutex/Mutex_02_DekkerAlgorithm.java

锁执行死锁

Lock implementation deadlock

java

deadlock

问题