java - 解决Java中链表的手动锁定死锁问题

Question

我正在尝试使用在 LinkedList 的 Node 类中初始化的 ReentrantLock 在 Java 中实现手动锁定，但我似乎遇到了死锁，并且不知道如何修复它。任何帮助将不胜感激。

// Insert value for key.
public boolean add( K key, V value ) {
    // Require key != null and value != null
    // Get hash code
    int hash = key.hashCode();
    Node pred = null, curr = null;

    try {
        pred = head;
        pred.lock.lock();
        curr = pred.next;
        curr.lock.lock();

        while( curr.hash <= hash ) {
            if( key.equals( curr.key ) ) { // key present, update value
                curr.value = value;
                return false;
            }
            pred = curr;
            pred.lock.lock();
            curr = curr.next;
            curr.lock.lock();
        }

        // key not present
        Node node = new Node( hash, key, value );
        node.next = pred.next;
        pred.next = node;

        return true;
    } finally {
        curr.lock.unlock();
        pred.lock.unlock();
    }
}
// Remove key/value pair
public boolean remove( K key ) {
    // Require key != null
    // Get hash code
    int hash = key.hashCode();
    Node pred = null, curr = null;

    try {
        // Predecessor node
        pred = this.head;
        pred.lock.lock();
        //Current node
        curr = pred.next;
        curr.lock.lock();

        // traversing list
        while( curr.hash <= hash ) {
            if( key.equals( curr.key ) ) { // key present, update value
                pred.next = curr.next;
                return true;
            }
            pred.lock.unlock();
            pred = curr;
            curr = curr.next;
            curr.lock.lock();
        }

        // key not found
        return false;
    }finally {
        curr.lock.unlock();
        pred.lock.unlock();
    }
}

Answer 1

在 add() 内部的 while 循环中，实际上有几个问题。

1. 您的 pred 节点未解锁。
2. 您锁定 curr 节点两次。

pred节点怎么没有解锁？

pred = curr;
pred.lock.lock();

因此，在这里，您覆盖了 pred 节点的本地引用，现在 pred 和 curr 都指向同一个节点。因此，在覆盖 pred 引用之前，您需要确保该节点处于解锁状态。

curr节点如何被锁定两次？

pred = curr;
pred.lock.lock();

同样的原因与上面相同。 pred 与此处的 curr 是同一节点，并且您已经在方法的开头锁定了 curr。

因此，调用 pred.lock.lock() 就是发生死锁的地方。

应为:

pred.lock.unlock();
pred = curr;
curr = curr.next;
curr.lock.lock();