Hierarchical mutex locks in Java

Question

I want to be able to lock based on a filesystem hierarchy. For example:

Thread 1:

lock("/");
doStuff();
unlock();

Thread 2:

lock("/sub/foo");
doStuff();
unlock();

Thread 3:

lock("/sub/bar");
doStuff();
unlock();

If Thread 1 acquires the lock first then threads 2 and 3 will be blocked until Thread 1 unlocks. However, if Thread 2 acquires the lock first, then Thread 3 should be able to execute at the same time as Thread 2. The general rule is that if there is a lock on a parent directory, then the thread must block.

Does Java have anything built-in that can help solve this? I want to avoid storing a lock per directory because there will be hundreds of thousands of directories.

Answer 1

I'd store the directory paths in a tree like this:

- /
 - sub
  - foo
  - bar

Whenever you need to lock anything in that tree you go down from the root and acquire a read-lock on everything except the target node itself. The target node gets a write lock.

This scheme guarantees you deadlock-freedom and stability of the relevant parts of the tree.

I don't see a particular problem storing hundreds of thousands of locks. This is probably going to waste maybe 100 bytes of RAM per lock. But it simplifies the architecture. Did you measure if it actually is a problem?

As an alternative you can have a map from path to lock. All operations on that dictionary must be synchronized by callers. This allows you to lazily initialize locks. You can also periodically garbage-collect unused locks by first taking a write-lock on the root which quiesces all operations. Once everything is quiet you discard all non-root locks.