为什么我的代码死锁？ Java细粒度并发BST实现尝试失败

Question

您能帮我理解为什么我的可重入锁代码卡住了吗？ 我正在实现一个带有整数键和整数

val

的并发二叉搜索树，其中

val

是一个计数变量，如果插入相同的键，它可以增加一定的量。

我只有一个

insert

函数，如果键不存在，我会添加新节点，如果键存在，我会增加存储在节点中的计数器。

我正在尝试实现一种锁定左或右的方法，并且我还在树遍历的路径上有一个先前的锁。我获取一个孩子，然后释放父母，反之亦然，因为我不希望其他线程在我之前潜入孩子。

这是我的思考过程。

Step 1 locking root and going right, because 1 is greater than 0

      root
       |
       |    <------ locked as prev lock
       |
       0
      / \
     /   \  <----- not locked yet
    /     \
  null     1


Step 2 locking right and calling recursion. In recursive call the parent lock should be released

      root
       |
       |    <------ locked as prev lock
       |
       0
      / \
     /   \  <----- locked
    /     \
  null     1

Step 3 unlocking parent vertex, because the right child is secured by right lock, so we are safe

      root
       |
       |    <------ unlocking this.
       |
       0
      / \
     /   \  <----- locked
    /     \
  null     1

然而，现实是我错过了一些东西并且没有任何作用。

这是代码：

class RootBST {
  Lock lock = new ReentrantLock();
  BST root = null;

  void insert(int key, int lose) {
    lock.lock();
    if (root == null) {
      root = new BST(key, lose);
      lock.unlock();
      return;
    }
    root.insertHelper(key, lose, lock);
  }
}

class BST {
  int key;
  int val;
  BST left = null;
  BST right = null;

  Lock leftLock = new ReentrantLock();
  Lock rightLock = new ReentrantLock();

  BST(int key, int val) {
    this.key = key;
    this.val = val;
  }

  void insertHelper(int key, int lose, Lock prevLock) {
    if (!prevLock.tryLock()) {
      System.out.println("ERROR");
      return;
    }
    if (key == this.key) {
      this.val += lose;
      prevLock.unlock();
    } else if (key < this.key) {
      leftLock.lock();
      if (left == null) {
        left = new BST(key, lose);
        leftLock.unlock();
        prevLock.unlock();
      } else {
        leftLock.lock();
        prevLock.unlock();
        left.insertHelper(key, lose, leftLock);
      }
    } else {
      rightLock.lock();
      if (right == null) {
        right = new BST(key, lose);
        rightLock.unlock();
        prevLock.unlock();
      } else {
        prevLock.unlock();
        right.insertHelper(key, lose, rightLock);
      }
    }
  }
}

我该如何解决这个问题？谢谢！

Answer 1

      leftLock.lock();
      if (left == null) {
        ...
      } else {
        leftLock.lock();
        prevLock.unlock();
        left.insertHelper(key, lose, leftLock);
      }

在上面的代码片段中，线程获取

leftLock

两次，但在

left.insertHelper(...)

内仅释放一次。
因此，任何其他想要获取相同

leftLock

的线程都将永远阻塞等待，直到

leftLock

被释放。