tags:

views:

57

answers:

2

How can I device an algorithem for deadlock detection through an Injecting DLL containing the hooked Functions for locking and Unlocking.

Actually I want to device and algorithem for deadlock detection. Kindly if someone could me in this regard.

+2  A: 

Conceptually deadlock detection is simple in principle, but hard to implement.

From a high-level point of view, what you want is to record the locks held by each thread and see if acquiring the lock would result in a dead-lock. You can visualize this with a dependency graph, a cycle meaning a deadlock.

However, there are other operations that you can use for synchronizations: spin-locking for example. Those will screw up any attempt on detection, so be aware of the restrictions.

So let's have a simulation first: Imagine 3 threads (T1, T2, T3) and 3 mutexes (M1, M2, M3)

  • T1 grab M1
  • T2 grab M2, wait for M1
  • T3 grab M3, wait for M2

If T1 waits for M3 you're screwed (you have a cycle), thus before trying to grab, you need to check for this condition.

You can modelize this using:

  • a table, which lists the threads holding a given mutex
  • a graph, representing the dependencies between threads

If we modelize the situation when T1 tries to grab M3 we have:

Table
M1 -> T1,
M2 -> T2,
M3 -> T3,

Graph
{T1, T2, T3} x {T2 -> T1, T3 -> T2}

When T1 tries to grab M3:

  • It looks up the table and list the threads holding it, here T3.
  • It checks if adding the edge T1 -> T3 in the graph forms a cycle.
Matthieu M.
+1  A: 

See this CP article - you're not original I'm afraid. See also this microsoft.public.win32.programmer.kernel article where a Microsoft employee explains the WIndows built-in options.

MSalters