Are there any efficient (sub)tree locking mechanisms?

Question

I have a tree T, nodes of which can be addressed by their paths (payloads of nodes contain some names that can be glued together into a path). What I would like to have is some mechanism (algorithm, auxiliary data structure etc.) that will allow, given the path P0, lock an entire sub-tree in such a fashion that:

• attempts to lock on any path P1 (where P1 starts with P0, i.e. P1 belongs to the locked subtree) will result in lock for P1 being the one for P0 (well, it might be not the very same lock, but operations on P1 should wait until P0 lock is free);
• but when P0 lock is released, any lock for P2, where P2 starts with P0, but not P2 starts with P1, i.e. P2 subtree and P1 subtree are different, different locks will be granted for those two paths, and so on.

I tackled this task for a couple of times, but I wound up with an over-complicated code that was messy and used some kind of tree for storing locks itself, which was even heavier that the tree I tried to lock.

In case my question is unclear, please let me know if you'd like to see some drawings/diagrams or anything that would help.

Answer 1

Disclaimer: This is very similar to a HW assignment I did in 2009, so I remember the basic idea, not the details. In any case, I suggest the following idea:

Each node in the tree has it's own lock. Every locking action starts from the root of the tree, and follows down towards the desired node, locking each node on the way down. If it encounters a locked node (that isn't the root), the locking action is terminated (unsuccessfully), or set to wait and try again (like busy wait). If the root itself is locked, it might be a temporary lock for another action taking place. If the root is not locked but an inner node is, it is really locked.
Unlocking might be different, not sure if following the path down from the root is necessary. (it might be, so this is worth checking).

EDIT:
While working up the tree after the required node is locked, also mark the nodes on the path to the tree as ones that have some in their subtree locked. This way when you are locking a node you can know if there is a node in that subtree that is already locked.