在多个线程中以相反顺序执行equals()时，Java的同步集合存在问题

Question

示例场景:

• 创建两个同步集合（s1和s2）
• 将它们传递给两个线程（T1和T2）
• 启动线程

T1的run() : while (forever) s1.equals(s2)

T2的run() : while (forever) s2.equals(s1)

会发生什么？ - 同步集合的equals方法会获取自身的锁

• 它计算传入参数的长度以及包含的内容，以确定是否相等[注意：这是我分析日志后的猜测]

• 如果传入的参数也是同步集合，则调用size()和containAll()需要获取该集合的锁。

• 在上面的示例中，T1和T2的锁获取顺序如下：

  T1: s1 -> s2 T2: s2 -> s1

当然，这会导致死锁。

这个问题不仅仅与同步集合有关。即使使用哈希表或向量也可能发生这种情况。

我认为这是Java API的限制（设计）。如何克服这个问题？如何确保在我的应用程序中不会发生这种情况？是否有一些设计原则可以遵循，而不会陷入这种情况？

- user188223

Answer 1

我认为这是Java API的限制（设计）。

我认为你错了。我使用过的每个编程语言级别的锁定机制都有一个基本要求：线程必须按相同的顺序锁定资源，否则会出现死锁。数据库也是如此。

事实上，我认为你唯一可以避免这种情况的方法是：

- 要求应用程序在单个原子操作中获取所有所需的锁；或者 - 使用单个全局锁进行所有锁定。

这两种方法都不切实际且无法扩展。

如何克服这个问题？

编写应用程序以使所有线程按相同的顺序获取锁。@Maurice和@Nettogrof的答案提供了如何实现此目的的示例，但如果您需要考虑很多集合，则可能更加困难。

- Stephen C

Answer 2

您可以在每个线程中以相同的顺序锁定两个集合：

            synchronized(s1) {
                synchronized(s2) {
                    s1.equals(s2);
                }
            }

并且

            synchronized(s1) {
                synchronized(s2) {
                    s2.equals(s1);
                }
            }

- Maurice Perry

Answer 3

我建议使用synchronized()块。可以像这样写：

``` synchronized(){ // your code here } ```

while(forever){
    synchronized(s1){
        s1.equals(s2);
    }
}

并且

while(forever){
   synchronized(s1){
    s2.equals(s1);
   }
}

- Nettogrof

Answer 4

Stephen C的东西很棒。进一步的信息：如果你不知道集合的顺序，你可以在两个集合需要进行比较时使用一个“全局”锁定：

 private static final Object lock = new Object(); // May be context-local.

 [...]

     synchronized (lock) {
         synchronized (s1) {
             synchronized (s2) {
                 return s1.equals(s2);
             }
          }
     }

如果集合可能产生争用，你可以大部分时间按照标识哈希码进行排序，并退回到全局锁定：

    int h1 = System.identityHashCode(s1);
    int h2 = System.identityHashCode(s2);
    return
         h1<h2 ? lockFirstEquals(h1, h2) :
         h2<h1 ? lockFirstEquals(h2, h1) :
         globalLockEquals(h1, h2);

有时候，你可以使用另一种算法。如果我没记错的话，StringBuffer 可能会在 append 时死锁（尽管对象上的操作组合并没有太多意义）。它可以这样实现：

public StringBuffer append(StringBuffer other) {
    if (other == null) {
        return append("null");
    }
    int thisHash  = System.identityHashCode(this);
    int otherHash = System.identityHashCode(other);
    if (thisHash < otherHash) {
        synchronized (this) {
            synchronized (other) {
                appendImpl(other);
            }
        }
    } else if (otherHash < thisHash) {
        synchronized (other) {
            synchronized (this) {
                appendImpl(other);
            }
        }
    } else {
        append(other.toString()); // Or append((Object)other);
    }
    return this;
}

最好的解决方案可能是改变你的线程策略，这样你就不需要在这里进行任何锁定。

- Tom Hawtin - tackline

---

@Tom：但请注意，如果您没有同时获取子锁，即使使用主锁也可能会遇到麻烦。例如，如果已经持有s2锁的某个线程执行了您代码片段中的第一个操作，则可能会发生死锁。 - Stephen C

@Tom：实际上，我认为你的第一个片段没有理解我的观点。我想说的是，确保没有死锁的一种方法是对所有数据结构使用一个且仅一个锁。当然，这是不切实际的，因为（首先）它无法扩展。 - Stephen C

如果一个线程已经持有锁并调用了随机代码，那么它本身就会出现问题。我猜如果你正在使用java.util.concurrent.locks，你可以对其进行编码来避免这种情况，但我会尝试编写一些更加明智的代码。 - Tom Hawtin - tackline

Answer 5

在调用equals()方法之前，您可以通过它们的identiyHashCode()对集合进行排序。这样锁获取的顺序将始终相同。

- Joachim Sauer

---

@Tom的解决方案暗示了你的解决方案存在的问题。这两个集合具有相同的标识哈希码值的概率很小但不为零。 - Stephen C

由于哈希值的数量是有限的，因此在运行多次操作并在许多机器上运行时，“生日悖论”实际上会经常发生。尽管您可能不会注意到 - 并非每个潜在的死锁事件都会导致死锁。 - Tom Hawtin - tackline