Problem

Part A:

lock(A)  // 1. Thread 1 has entered, no other threads can enter lock(A) in Part A or Part B.
{
   sleep(20);  // Sleeps 20 milliseconds to demonstrate race condition failing.
   lock(B)      // 3.
   {

   }
}

Part B:

lock(B)  // 2. Thread 2 has entered, no other threads can enter lock(B) in Part A or Part B.
{
   sleep(20);  // Sleeps 20 milliseconds to demonstrate race condition failing.
   lock(A)      // 4.
   {

   }
}

The above is pseudo-code which demonstrates how hard locking occurs. Each lock will only allow one thread to enter it. If two threads enter, the first one that enters goes through, while any other threads are paused at that locks position.

Thread 1 enters lock(A) in Part A. Then it sleeps for a short bit. Thread 2 enters lock(B) in Part B. Then it sleeps a bit too. Then at #3 in Part A, Thread 1 gets held by trying to lock on lock(B), which is already held by Thread 2. Then at #4 in Part B, Thread 2 gets held by lock(A), causing a hard lock.

Solution

My solution is to allow this hard lock almost occur. But I keep track of all threads coming in. So when the number of threads that have entered read and write locks equals the number of threads being locked (checked right before the lock occurs), I let that thread "run its course."

By run its course, I mean I track it after assigning it as a super thread. If it enters other locks while being the super thread, it blocks all other threads until this otherwise hard-locked thread is finished, and unlocks. So this hard-lock prevention scheme is recursive.

Information

http://en.wikipedia.org/wiki/Deadlock has more information about deadlocks and algorithms designed to prevent them.  I initially used a list which kept track of how locking occurred, and tested when hard locks might happen.  This is called Avoidance according to wikipedia, and it degraded performance drastically.

So I switched to an algorithm of tracking threads and almost allowing deadlocks to occur.  This is called Prevention, which made things many times simpler to code, and removed complications I was having from the halting issue.  I had to use this deadlock prevention algorithm for both inside a single read-write locker instance (Local DeadLock Detection), and among all the read-write lockers (Distributed DeadLock Detection).

This link and the code below should help if you would like an advanced understanding.  The code below is pseudo-code.  Please compare this with the Source Code to get a more accurate depiction in how Lock Detection and Prevention works.



//          ManagedThreadId, Number of times each thread recursively locked.
Dictionary <int,             int> ThreadsEntered  = new Dictionary<int, int>();

//          ManagedThreadId, Number of times each thread recursively locked.
Dictionary <int,             int> ThreadsLocked = new Dictionary<int, int>();

int SuperThreadId    = -1;
int SuperThreadCount = 0;
bool LockIsNeeded(int currentThreadId) { lock(ThreadsEntered) { lock(ThreadsLocked) { // Guarantees that a hard lock will occur. Then lets the super thread continue. return SuperThreadId != currentThreadId; } // End lock } // End lock } // End LockIsNeeded() Function // This could be either read locking, write locking, or normal // locking, depending on how LockIsNeeded() is setup. void LockFunction() { Dim CurrentThreadId As Integer = Thread.CurrentThread.ManagedThreadId; Dim CountValue As Integer

  // This is part of the super thread's "Running its course."
  if (SuperThreadId == CurrentThreadId)
  {
    SuperThreadCount += 1;
  }

lock(ThreadsEntered) { if (ThreadsEntered.TryGetValue(CurrentThreadId, CountValue)) { ThreadsEntered(CurrentThreadId) = CountValue + 1; } else { ThreadsEntered.Add(CurrentThreadId, 0); } // End If } // End lock if (LockIsNeeded(CurrentThreadId)) { lock(ThreadsLocked) { if (ThreadsLocked.TryGetValue(CurrentThreadId, CountValue)) { ThreadsLocked(CurrentThreadId) = CountValue + 1; } else { ThreadsLocked.Add(CurrentThreadId, 0); } // End If } // End lock while (LockIsNeeded(CurrentThreadId)) { lock(ThreadsEntered) { lock(ThreadsLocked) { if (SuperThreadId == -1 && ThreadsEntered.Count == ThreadsLocked.Count) { SuperThreadId = CurrentThreadId; } } } if (SuperThreadId == CurrentThreadId) { break; } // End if Thread.Wait(6000); } // End while lock(ThreadsLocked) { if (ThreadsLocked.TryGetValue(CurrentThreadId, CountValue)) { if (CountValue == 0) { ThreadsLocked.Remove(CurrentThreadId); } else { ThreadsLocked(CurrentThreadId) = CountValue - 1; } // End if } // End if } // End lock } // End [LockIsNeeded()] if } // End LockFunction() Function void UnlockFunction() { Dim CurrentThreadId As Integer = Thread.CurrentThread.ManagedThreadId; Dim CountValue As Integer lock(ThreadsEntered) { if (ThreadsEntered.TryGetValue(CurrentThreadId, CountValue)) { if (CountValue == 0) { ThreadsEntered.Remove(CurrentThreadId); } else { ThreadsEntered(CurrentThreadId) = CountValue - 1; } // End if } // End if } // End lock lock(ThreadsEntered) { lock(ThreadsLocked) {
      // Only after the super thread has ran its course is another thread allowed to take its place.
if (SuperThreadCount == 0 && SuperThreadId == CurrentThreadId) { SuperThreadId = -1; }

      // This is part of the super thread's "Running its course"
      if (SuperThreadId == CurrentThreadId)
      {
        SuperThreadCount -= 1;
      }
} } } // End UnlockFunction() Function

Last edited Sep 25, 2010 at 7:13 PM by TamusJRoyce, version 41

Comments

TamusJRoyce Sep 25, 2010 at 7:02 PM 
At the very bottom of the code shown,

// This is part of the super thread's "Running its course"
if (SuperThreadId == CurrentThreadId)
{
SuperThreadCount -= 1;
}

May need to be above

// Only after the super thread has ran its course is another thread allowed to take its place.
if (SuperThreadCount == 0 && SuperThreadId == CurrentThreadId)
{
SuperThreadId = -1;
}