在Java中使用哪种策略进行分层可重入的读/写锁定?

问题描述

我正在寻找一个高效的系统，以使其具有一系列按层次结构组织的读/写锁，以管理对按层次结构组织的资源的访问.如果一个子树被锁定以进行写操作，那么在整个子树中，除非释放它，否则将无法获得其他任何锁定；同样，子树中的写锁定应防止锁定父级.

I'm looking for en efficient system to have a series of read/write locks organized hierarchically to manage access to hierarchically organized resources. If a subtree is locked for write, then no other lock should be able to be obtained in the whole subtree until it is released; similarly, a write lock in a subtree should prevent locking in a parent.

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

Here are the ideas I was contemplating:

• 使用 Apache Commons Transaction .不幸的是，该项目自2008年3月以来未进行任何更新，并且已非正式终止.一些API文档似乎表明即将发布的版本(1.3或2.0)将包括某种类型的层次锁定，但是找不到源，而且似乎我们再也不能访问其SVN存储库了.

• Use the Apache Commons Transaction. Unforunately, the project hasn't been updated since March 2008 and has unofficially been terminated. Some API docs seemed to indicate that the version to come (1.3 or 2.0) would include some kind of hierarchical locking, but the sources are nowhere to be found and it seems we can't access their SVN repository any more.

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

Use a series of ReentrantReadWriteLocks, which I would organize hierarchically. I'm no concurrency expert, and I'm a bit afraid to do that on my own. Preliminary thoughts seemed to indicate that even before I can try to lock a subtree, I'd have to use an outer lock on the whole structure managing the ReentrantReadWriteLocks itself — so that even for releasing a lock I'd have to use the outer lock…

使用 java.util.concurrent 和 java.util.concurrent.atomic ，以比使用一系列ReentrantReadWriteLock s更为有效的方式来实现我的层次结构锁定.

Use classes from java.util.concurrent and java.util.concurrent.atomic to implement my hierarchical lock in a more efficient way than I could do with a series of ReentrantReadWriteLocks.

我已经准备好走最后一条路了，但是我很惊讶地没有找到任何可以更好地解决该问题的现有库.所以:

I'm ready to go down that last road, but I was surprised not to find any exiting library that would solve this problem better. So:

• 我错过了一些明显的解决方案吗?
• 或者这个问题很难正确解决吗?

推荐答案

我不知道我是否很好地理解了您的问题，正如您所说的那样，当您锁定要写的子树时，整个结构都被锁定了.因此，简单的解决方案是为整个结构设置一个RW锁.

I don't know if I understood well your question, as you say that when you lock a subtree for write, the whole structure is locked.So, the simple solution is to have one RW lock for the whole structure.

顺便说一句，java.util.concurrent.atomic只会帮您一堆RW锁.

By the way, java.util.concurrent.atomic won't help you more than a tree of RW locks.

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

If you want to be able locking siblings independly, you may go with the second solution (a tree of locks where each node has a reference to its parent).

锁定节点将使用其写入锁定来锁定它，并使用读取锁定来锁定每个父节点.父项无法锁定，而子项无法锁定，因为您无法像锁定子项一样获得读锁定，因此无法获得其写锁定.只有在没有其他线程将任何父对象写锁定的情况下，才可以锁定孩子.

Locking a node would be locking it using its write lock and locking every parent using read locks.A parent cannot be locked while a child is, because you cannot acquire its write lock as locking a child already acquired the read lock.Locking a child is only permitted if no other thread has write-locked any parent.

上述锁是排他锁.(读写锁的另一个名称是共享独占锁)

要添加共享锁，每个节点还需要一个原子整数，该整数指示:如果是肯定的，则为间接写锁子代的数量；如果为负，则节点已被读取锁定的次数.另外，节点及其父节点将被读取锁定，以避免在父节点上获得新的写锁定.

To add shared locks, each node also needs an atomic integer indicating:if it's positive, the number of indirect write-locked children; if it's negative the number of times the node has been read-locked.Also, the node and its parents will be read locked to avoid new write locks being acquired on parents.

伪代码:

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

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

If any lock couldn't be acquired, then you unlock what you have locked and retry later (you can use a global condition variable, a timeout, etc to achieve this).

编辑:添加了用于对树进行读锁定/写锁定的代码

added code to read-lock/write-lock a tree

这篇关于在Java中使用哪种策略进行分层可重入的读/写锁定?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！