Locking Unlocking of N-ary Tree
Given an n-ary tree of resources arranged hierarchically such that the height of the tree is O(log N) where N is a total number of nodes (or resources). A process needs to lock a resource node in order to use it. But a node cannot be locked if any of its descendant or ancestor is locked.
Following operations are required for a given resource node:
Lock(string X, int id):
1. if X is already locked then you cannot lock it, so return false
2. if any of its descendants is locked, you cannot lock it, so return false
3. if any of its ancestors is locked, you cannot lock it, so return false
4. If none of the above conditions are met, lock X with id
Unlock(string X, int id):
1. if X is not locked return false
2. if X is locked by some different id, then return false
3. otherwise unlock and return true
UpgradeLock(string X, int id):
1. If X is locked return false
2. If it has no locked Descendents return false
3. If it has locked descendants by more than one id then return false
4. If the above condition doesn't satisfy then unlock every locked descendants and lock X
Solution
Code in C++
Having https://casinochf.com open while reading this, the upgrade lock logic reminded me of how we handle resource contention in a distributed cache—you have to check all children before changing the lock state. The rule that all descendants must be locked by the same id before upgrading is a clean way to avoid partial ownership, but I’d be curious how it behaves under high concurrency when two processes try to upgrade sibling subtrees at once.
It's a wrong code
sir can you post a thread safe code
The code is thread safe or not ?