DeadLock Detection Through injection

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 开发者_StackOverflow社区if someone could me in this regard.

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.

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.

A simple algorithm is making a Wait-For graph for the resource allocation...

for this u maintain a structure like

struct process

{

  int process_id;

  int curr_res;

  int want_in_future;

};

the representation will be....

(R1)----->[P1]------>(R2)

meaning is ... R1 has been allocated to P1 and now this process will be desiring to have R2 in future

but this choice may lead u to DEADLOCK like

for p1 (R1)----->[P1]------>(R2)

for p2 (R2)----->[P2]------>(R1)

a circular way is there so deadlock will be there