Design a class which provides a lock only if there are no possible deadlocks?

Deadlock will occur with a lock only if the locks can be held in a circular fashion; that is, if you define an ordering.

Deadlock will occur with a lock only if the locks can be held in a circular fashion; that is, if you define an ordering To detect this sort of condition dynamically, one option is to maintain a directed graph of the locks in the system. Whenever a thread tries to acquire a lock, add an edge from each lock that it holds to the lock it's trying to acquire. If this action forms a cycle, then deadlock is about to occur because some other thread owns the lock you're pointing at and is trying to acquire some other lock.

This structure would be global and you'd need to take the appropriate precautions to ensure that it was synchronized correctly. However, it would give you a very direct way of detecting whether or not deadlock was about to occur. EDIT: Here's a sketch of a simple implementation scheme.

I assume that you have as a primitive a naive mutex lock that does not prevent deadlock, along with the ability to store some data on a per-thread basis. Inside of the smart lock class, create a static mutex shared by all instances of the lock that guards access to the ownership graph. Also, create a map associating each lock with the set of locks it has edges to.

Finally, set up a per-thread set of all the locks owned by that thread. When a thread tries to acquire a smart lock, first acquire the static mutex to ensure exclusive access to the graph structure. For each of the locks owned by that thread, add an edge in the static graph from that lock to the lock being acquired.

Now, run a depth-first search over the graph starting from each of the locks held by the current thread looking for cycles. This takes time linear in the size of the graph, which is at worst quadratic in the number of locks in the system (though this is extremely unlikely to occur, since it would mean that a large fraction of the locks are somehow reachable from the thread's locks). If a cycle is found, deadlock is about to occur and you should take some sort of corrective action.

Otherwise, release the static lock to allow other threads access to the graph. When a thread actually acquires a lock, add that lock to the thread's set of owned locks. When a thread releases a lock, acquire the static graph lock and remove all incoming edges to the node for that lock that correspond to other locks held by the current thread, then release the lock.

Hope this helps!

– maxpayne Mar 3 at 17:05 @maxpayne- I Just updated the answer with an implementation sketch. Hope it helps! – templatetypedef Mar 3 at 20:34 it does help...thanks!

Let me see if I can actually translate this into code.. – maxpayne Mar 4 at 7:46 Love the application of graph theory to this problem! – Raj May 31 at 17:49.

Well, I'd say the key insight required is that the only way a class can orchestrate that is by having control of the entire set of related locks that might be involved in such deadlocks. It can then, for example, require they be taken in some specific order (e.g. Alphabetic ordering based on a name associated with each lock, arbitrary unique integers hardcoded in the source).

Thanks for the answer..that makes sense.. – maxpayne Mar 3 at 17:01.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.