Is it possible for a Dictionary in .Net to cause dead lock when reading and writing to it in parallel?

Question

I was playing with TPL, and trying to find out how big a mess I could make by reading and writing to the same Dictionary in parallel.

So I had this code:

    private static void HowCouldARegularDicionaryDeadLock()     {         for (var i = 0; i < 20000; i++)         {             TryToReproduceProblem();         }     }      private static void TryToReproduceProblem()     {         try         {             var dictionary = new Dictionary<int, int>();             Enumerable.Range(0, 1000000)                 .ToList()                 .AsParallel()                 .ForAll(n =>                 {                     if (!dictionary.ContainsKey(n))                     {                         dictionary[n] = n; //write                     }                     var readValue = dictionary[n]; //read                 });         }         catch (AggregateException e)         {             e.Flatten()                 .InnerExceptions.ToList()                 .ForEach(i => Console.WriteLine(i.Message));         }     } 

It was pretty messed up indeed, there were a lot of exceptions thrown, mostly about key does not exist, a few about index out of bound of array.

But after running the app for a while, it hangs, and the cpu percentage stays at 25%, the machine has 8 cores. So I assume that's 2 threads running at full capacity.

Then I ran dottrace on it, and got this:

It matches my guess, two threads running at 100%.

Both running the FindEntry method of Dictionary.

Then I ran the app again, with dottrace, this time the result is slightly different:

This time, one thread is running FindEntry, the other Insert.

My first intuition was that it's dead locked, but then I thought it could not be, there is only one shared resource, and it's not locked.

So how should this be explained?

ps: I am not looking to solve the problem, it could be fixed by using a ConcurrentDictionary, or by doing parallel aggregation. I am just looking for a reasonable explanation for this.

Answer 1

So your code is executing Dictionary.FindEntry. It's not a deadlock - a deadlock happens when two threads block in a way which makes them wait for one another to release a resource, but in your case you're getting two seemingly infinite loops. The threads aren't locked.

Let's take a look at this method in the reference source:

private int FindEntry(TKey key) {     if( key == null) {         ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);     }      if (buckets != null) {         int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;         for (int i = buckets[hashCode % buckets.Length]; i >= 0; i = entries[i].next) {             if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) return i;         }     }     return -1; } 

Take a look at the for loop. The increment part is i = entries[i].next, and guess what: entries is a field which is updated in the Resize method. next is a field of the inner Entry struct:

public int next;        // Index of next entry, -1 if last 

If your code can't exit the FindEntry method, the most probable cause would be you've managed to mess the entries in such a way that they produce an infinite sequence when you're following the indexes pointed by the next field.

As for the Insert method, it has a very similar for loop:

for (int i = buckets[targetBucket]; i >= 0; i = entries[i].next) 

---

As the Dictionary class is documented to be non-threadsafe, you're in the realm of undefined behavior anyway.

Using a ConcurrentDictionary or a locking pattern such as a ReaderWriterLockSlim (Dictionary is thread-safe for concurrent reads only) or a plain old lock nicely solves the problem.

Answer 2

Looks like a race condition (not a deadlock) - which, as you comment, causes the messed up internal state.

The dictionary is not thread safe so concurrent reads and writes to the same container from seperate threads (even if there are as few as one of each) is not safe.

Once the race condition is hit, it becomes undefined what will happen; in this case what appears to be an infinite loop of some sort.

In general, once write access is required, some form of synchronization is required.