javalockinghierarchicalreentrancyreadwritelock

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

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:

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:

Solution

  • 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