deadlock avoidance

[Axter]

I'm working on a thread safe smart pointer class listed in the following links:



http://code.axter.com/sync_ptr.h

http://code.axter.com/sync_ctrl.h



One feature I'm trying to add to this class is the ability to detect an attempt to create a deadlock.

For those who don't know what a deadlock is, say you have global object A and object B and they're using above smart pointers. Then say you have two threads:



Thread1: obj_A->SomeFunction(obj_B->GetData());

Thread2: obj_B->SomeFunction(obj_A->GetData());

If the above two threads make these calls at the same time, you'll get a deadlock since each lock is waiting for the other lock to unlock.

So I'm looking for any good suggestions, since I'm stumped, and I’m trying to do some brainstorming.

I posted this question in one of the newsgroup, and so far the only really good suggestion I got was to create a priority list for all locks (sync_ptr).

That method could work, but that would require the developer to be proactive in creating priorities for each sync_ptr object created.

I’m looking for a method that would require less work on the developer’s part.



I’ll take any and all suggestions, so please feel free to throw them at me.



Thanks

[wildfrog]

Ok, this is some late night brainstorming using mutexes and a seperate monitoring thread:

Lets say that you've go two maps, one called 'waiting for' (DWORD ThreadId, HANDLE hMutex, BOOL bDeadlock), and one called 'holding' (DWORD ThreadId, HANDLE hMutex).

And then some code like this:

CRITICAL_SECTION   global_cs; // accessed only by lock & unlock & scanthreadfunc

void lock(HANDLE hMutex)
{
	EnterCriticalSection(global_cs);

	// add 'this' thread and hMutex to "waiting for" map 

	//...
	// code here
	//...

	LeaveCriticalSection(global_cs);
	
	DWORD dwRet;

	do
	{
		// wait for the mutex
		dwRet = MsgWaitForSingleObjectEx(1, &hMutex, INFINITE, QS_POSTMESSAGE, 0)

		if (dwRet == WAIT_OBJECT_0 + 1)
		{
			// something woke us up, see if we're in a deadlock situation
			// and do something about it
		}
	} while (dwRet != WAIT_OBJECT_0);


	// We hold the lock on the mutex


	EnterCriticalSection(global_cs);

	// remove 'this' thread and hMutex from the "waiting for" map
	// and add 'this' thread and hMutex to the "holding" map

	//...
	// code here
	//...

	LeaveCriticalSection(global_cs);
}


void unlock(HANDLE hMutex)
{
	EnterCriticalSection(global_cs);

	ReleaseMutex(hMutex);

	// remove 'this' thread and hMutex from the "holding" map

	//...
	// code here
	//...


	LeaveCriticalSection(global_cs);
}



// a thread proc running constantly
void scanthreadfunc(void*)
{
	while (true)
	{
		// sleep for some while

		EnterCriticalSection(global_cs);

		// Scan "waiting for" & "holding" maps to see if there is a thread 'A' that's waiting for a mutex that's
		// locked by a thread 'B' which in turn is waiting for a mutex that is locked by thread 'A'....
		// This is a 'recursive' search, there might be a list of threads between 'A' and 'B'.

		// If such a situation is found raise a flag (relative to the threads and threir mutexes) in the "waiting for" map
		// and post a message to the "deadlocked" threads using PostThreadMessage(...), just to wake them up...
	

		LeaveCriticalSection(global_cs);
		
	}
}

Ok, where would that leave us?

- petter

[kuphryn]

Solution depends on the data and situation of the lock. For example, if the main thread is locked because there is an infinite loop in an worker thread, then the issue is the inifinite loop, not the synchronization mechanism.

In general, synchronization is better solved on paper then via code.

Kuphryn

[Axter]

Ok, this is some late night brainstorming using mutexes and a seperate monitoring thread:

Lets say that you've go two maps, one called 'waiting for' (DWORD ThreadId, HANDLE hMutex, BOOL bDeadlock), and one called 'holding' (DWORD ThreadId, HANDLE hMutex).

And then some code like this:

CRITICAL_SECTION global_cs; // accessed only by lock & unlock & scanthreadfunc
 
void lock(HANDLE hMutex)
{
	EnterCriticalSection(global_cs);
 
	// add 'this' thread and hMutex to "waiting for" map 
 
	//...
	// code here
	//...
 
	LeaveCriticalSection(global_cs);
 
	DWORD dwRet;
 
	do
	{
		// wait for the mutex
		dwRet = MsgWaitForSingleObjectEx(1, &hMutex, INFINITE, QS_POSTMESSAGE, 0)
 
		if (dwRet == WAIT_OBJECT_0 + 1)
		{
			// something woke us up, see if we're in a deadlock situation
			// and do something about it
		}
	} while (dwRet != WAIT_OBJECT_0);
 
 
	// We hold the lock on the mutex
 
 
	EnterCriticalSection(global_cs);
 
	// remove 'this' thread and hMutex from the "waiting for" map
	// and add 'this' thread and hMutex to the "holding" map
 
	//...
	// code here
	//...
 
	LeaveCriticalSection(global_cs);
}
 
 
void unlock(HANDLE hMutex)
{
	EnterCriticalSection(global_cs);
 
	ReleaseMutex(hMutex);
 
	// remove 'this' thread and hMutex from the "holding" map
 
	//...
	// code here
	//...
 
 
	LeaveCriticalSection(global_cs);
}
 
 
 
// a thread proc running constantly
void scanthreadfunc(void*)
{
	while (true)
	{
		// sleep for some while
 
		EnterCriticalSection(global_cs);
 
		// Scan "waiting for" & "holding" maps to see if there is a thread 'A' that's waiting for a mutex that's
		// locked by a thread 'B' which in turn is waiting for a mutex that is locked by thread 'A'....
		// This is a 'recursive' search, there might be a list of threads between 'A' and 'B'.
 
		// If such a situation is found raise a flag (relative to the threads and threir mutexes) in the "waiting for" map
		// and post a message to the "deadlocked" threads using PostThreadMessage(...), just to wake them up...
 
 
		LeaveCriticalSection(global_cs);
 
	}
}

Ok, where would that leave us?

- petter

Very interesting method.

[wildfrog]

Very interesting method.

Please give me a hint if it actually works

- petter