Java细粒度并发BST实现遇死锁，求原因及修复方案

以下是你的代码引发死锁和异常的几个致命问题：

1. 重复加锁导致锁计数异常 #

在insertHelper的左分支else块中，已经执行了leftLock.lock()，却重复调用了一次leftLock.lock()。ReentrantLock是可重入锁，每次加锁会增加内部计数，解锁需要对应次数才能完全释放。这里重复加锁后仅解锁一次，导致leftLock永远无法被其他线程获取，直接引发死锁。

2. 前置锁逻辑完全错误 #

insertHelper开头的prevLock.tryLock()属于多余且错误的操作：上层调用者已经持有prevLock的锁（比如RootBST.insert中已经锁住了根节点锁），虽然ReentrantLock支持重入，但这个逻辑毫无意义。一旦tryLock意外失败（比如极端情况下的锁竞争），会直接返回并导致prevLock永远无法解锁，引发全局死锁。

3. 节点锁的设计逻辑错误 #

每个BST节点不应该为左右子节点单独设置锁，正确的细粒度锁设计应该是每个节点持有自身的锁，用来保护当前节点的结构和数据，遍历过程中通过"先锁子节点，再释放父节点"的方式保证路径安全。原代码的leftLock/rightLock设计完全违背了这个逻辑。

4. 解锁路径不完整 #

部分分支存在锁泄漏：比如tryLock失败直接返回时，没有释放任何已持有的锁；递归过程中锁的传递和释放逻辑混乱，导致部分锁无法被正确释放。

调整锁的设计逻辑，确保每个节点持有自身锁，并通过正确的锁传递/释放流程避免死锁：

class RootBST {
    private final Lock rootLock = new ReentrantLock();
    private BST root = null;

    public void insert(int key, int value) {
        rootLock.lock();
        try {
            if (root == null) {
                root = new BST(key, value);
                return;
            }
            // 将根节点锁传递给子节点处理
            root.insertHelper(key, value, rootLock);
        } finally {
            // 仅当未进入子节点处理时，才手动释放根节点锁
            if (root == null) {
                rootLock.unlock();
            }
        }
    }
}

class BST {
    private final Lock nodeLock = new ReentrantLock();
    int key;
    int val;
    BST left = null;
    BST right = null;

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

    public void insertHelper(int key, int value, Lock parentLock) {
        // 先锁定当前节点
        nodeLock.lock();
        try {
            // 已持有当前节点锁，安全释放父节点锁
            parentLock.unlock();

            if (key == this.key) {
                this.val += value;
            } else if (key < this.key) {
                if (left == null) {
                    left = new BST(key, value);
                } else {
                    // 递归传递当前节点锁给左子节点
                    left.insertHelper(key, value, nodeLock);
                }
            } else {
                if (right == null) {
                    right = new BST(key, value);
                } else {
                    // 递归传递当前节点锁给右子节点
                    right.insertHelper(key, value, nodeLock);
                }
            }
        } finally {
            // 仅当未进入递归时，释放当前节点锁
            if ((key == this.key) || (key < this.key && left == null) || (key > this.key && right == null)) {
                nodeLock.unlock();
            }
        }
    }
}

• 每个节点持有自身锁：BST类新增nodeLock，用于保护当前节点的结构和数据修改。
• 正确的锁传递逻辑：遍历过程中先获取子节点锁，再释放父节点锁，避免其他线程修改路径上的节点。
• finally块保证锁释放：所有加锁操作都用try-finally包裹，确保即使发生异常，锁也能被正确释放，杜绝锁泄漏。
• 移除重复加锁：删除原代码中重复的leftLock.lock()调用，修复锁计数异常问题。
• 修正前置锁处理：不再对上层传递的锁执行无意义的tryLock，而是在持有当前节点锁后安全释放父节点锁。

内容的提问来源于stack exchange，提问作者Andrey Kachow