.Net中的字典是否可能在并行读取和写入时导致死锁？

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.

我正在玩TPL,并试图通过并行读取和写入同一个词典来找出我可以做多么大的混乱。

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.

但在运行应用程序一段时间后,它会挂起,并且cpu百分比保持在25%,机器有8个核心。所以我假设2个线程满负荷运行。

Then I ran dottrace on it, and got this:

然后我在上面运行了dottrace,得到了这个:

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

它符合我的猜测,两个线程以100%运行。

Both running the FindEntry method of Dictionary.

两者都运行Dictionary的FindEntry方法。

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

然后我用dottrace再次运行应用程序,这次结果略有不同:

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

这一次,一个线程正在运行FindEntry,另一个正在运行。

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.

ps:我不打算解决问题,可以通过使用ConcurrentDictionary或通过并行聚合来解决。我只是在寻找一个合理的解释。

2 个解决方案

#1

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.

通常,一旦需要写访问,就需要某种形式的同步。

#2

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.

所以你的代码正在执行Dictionary.FindEntry。这不是一个死锁 - 当两个线程以一种让他们等待彼此释放资源的方式阻塞时会发生死锁,但在你的情况下你会得到两个看似无限的循环。线程未锁定。

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:

看看for循环。增量部分是i = entries [i] .next,并猜测:条目是在Resize方法中更新的字段。 next是内部Entry结构的字段:

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.

如果你的代码无法退出FindEntry方法,那么最可能的原因就是你已经设法弄乱条目,使得当你遵循下一个字段指向的索引时它们会产生无限序列。

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

至于Insert方法,它有一个非常相似的for循环:

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.

由于Dictionary类被记录为非线程安全的,因此无论如何你都处于未定义的行为领域。

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.

使用ConcurrentDictionary或锁定模式(如ReaderWriterLockSlim(Dictionary对于并发读取仅是线程安全的)或普通的旧锁可以很好地解决问题。

#1