Why is my code deadlocking? Java fine-grained concurrent BST implementation attempt failed-CodePudding

Could you please help me understand why my Reentrant Lock code is getting stuck? I am implementing a Concurrent Binary Search Tree with an integer key and an integer val, where val is a counting variable, which can get incremented by some amount if the same key is inserted.

I have only an insert function, where I add new nodes if the key is absent and increment counter stored in the node if the key exists.

I am trying to implement an approach where I lock either left or right and I also have a previous lock on the path of tree traversal. I acquire a child and then release the parent, not vice versa because I don't want other threads to sneak into the child before me.

Here is my thought process.

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

However, the reality is that I am missing something and nothing works.

Here is the code:

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);
      }
    }
  }
}

How can I fix this? Thank you!

CodePudding user response：

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

In the code snippet above a thread acquires leftLock twice, but release it only once inside left.insertHelper(...).
As a result, any other thread that wants to acquire the same leftLock will block forever waiting until leftLock is released.