在 Java 中使用什么策略来实现分层可重入读/写锁定？

Question

我正在寻找一种高效的系统，该系统具有一系列按层次结构组织的读/写锁，以管理对按层次结构组织的资源的访问。如果一个子树被锁定用于写，那么在整个子树中不应该能够获得其他锁，直到它被释放；类似地，子树中的写锁应该防止父树中的锁定。

以下是我正在考虑的想法：

• 使用Apache Commons Transaction。不幸的是，该项目自 2008 年 3 月以来就没有更新过，并已被非正式终止。一些 API 文档似乎表明即将推出的版本（1.3 或 2.0）将包括 某种层次锁定，但源代码无处可寻，而且我们似乎无法再访问他们的 SVN 存储库。

• 使用一系列ReentrantReadWriteLocks，我将对其进行分层组织。我不是并发专家，我有点害怕自己做这件事。初步的想法似乎表明，即使在我尝试锁定子树之前，我也必须在管理 ReentrantReadWriteLock 本身的整个结构上使用外部锁 - 这样即使对于释放一把锁我必须使用外锁...

• 使用java.util.concurrent 和 java.util.concurrent.atomic 以比使用一系列 ReentrantReadWriteLock 更有效的方式实现分层锁s.

我准备走最后一条路，但令我惊讶的是没有找到任何现有的库可以更好地解决这个问题。那么：

• 我是否错过了一些明显的解决方案？
• 或者这个问题特别难以正确解决？

Answer 1

我不知道我是否理解你的问题，正如你所说，当你锁定子树进行写入时，整个结构都被锁定。
因此，一种简单的解决方案是为整个结构设置一个 RW 锁。

顺便说一句，java.util.concurrent.atomic 不会比 RW 锁树对您有更多帮助。

---

如果您希望能够独立锁定同级，您可以采用第二种解决方案（锁树，其中每个节点都有对其父节点的引用）。

锁定一个节点将使用其写锁来锁定它，并使用读锁来锁定每个父节点。
当子级被锁定时，父级不能被锁定，因为您无法获取其写锁，因为锁定子级已经获取了读锁。
仅当没有其他线程对任何父线程进行写锁定时才允许锁定子线程。

上面描述的锁是排他锁。
（读写锁的另一个名称是共享独占锁）

要添加共享锁，每个节点还需要一个原子整数，表示：
如果为正，则为间接写锁定子级的数量；如果为负数，则表示节点被读锁定的次数。
此外，节点及其父节点将被读锁定，以避免在父节点上获取新的写锁。

伪代码：

Node {
    // fields
    parent: Node
    lock: RWLock
    count: AtomicInteger
}

public boolean trylocktree(node: Node, exclusive: boolean) {
    if (exclusive) {
        return trylocktree_ex(node, true);
    } else {
        return trylocktree_sh(node);
    }
}
private boolean switch_count(i: AtomicInteger, diff: int) {
    // adds diff to i if the sign of i is the same as the sign of diff
    while (true) {
        int v = i.get();
        if (diff > 0 ? v < 0 : v > 0)
            return false;
        if (i.compareAndSet(v, v + diff))
            return true;
    }
}
private boolean trylocktree_ex(node: Node, writing: boolean) {
    // check if a node is read-locked
    if (!switch_count(node.count, 1))
        return false;
    // lock using the lock type passed as an arg
    if (!node.lock(writing).trylock()) {
        node.count--;
        return false;
    }
    // read-lock every parent
    if (!trylocktree_ex(node.parent, false)) {
        node.count--
        node.lock(writing).unlock();
        return false;
    }
    return true;
}
private boolean trylocktree_sh(node: Node) {
    // mark as shared-locked subtree
    if (!switch_count(node.count, -1))
        return false;
    // get shared-lock on parents
    if (!readlock_recursively(node)) {
        node.count++;
        return false;
    }
    return true;
}
private boolean readlock_recursively(node: Node) {
    if (!node.lock(false).trylock())
        return false;
    if (!readlock_recursively(node.parent)) {
        node.lock(false).unlock();
        return false;
    }
    return true;
}

如果无法获取任何锁定，则解锁已锁定的内容并稍后重试（可以使用全局条件变量、超时等来实现此目的）。

编辑：添加了读锁定/写锁定树的代码

Answer 2

我将采用您自己的解决方案并采用 Apache Apache Commons Transaction Algorithm 作为起点。
您可以使用 ReentrantReadWriteLock，尽管通常这种锁更适合一个生产者 - 许多读者的情况，这可能不是您想要的。看起来你的锁更像是一个常规的可重入互斥锁。