What strategy to use in Java for hierarchical reentrant read/write locking?

Question

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:

• 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.

• 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…

• 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:

• Have I missed some obvious solution?
• Or is this problem just especially hard to solve properly?

Answer 1

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.

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.

The lock described above is an exclusive lock. (another name for read-write locks is shared-exclusive locks)

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.

The pseudo-code:

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).

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