.Net中的Dictionary在并行读写时是否有可能导致死锁？

Question

我正在玩 TPL，并试图找出通过并行读取和写入同一个字典可以造成多大的混乱。

所以我有这个代码：

    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));
        }
    }

确实很乱，抛出了很多异常，主要是键不存在，少数是索引超出数组范围。

但是应用运行一段时间后挂了，cpu百分比停留在25%，机器8核。所以我假设这是满负荷的 2 个线程运行。

然后我运行 dottrace 在上面，得到了这个：

它符合我的猜测，两个线程运行处于 100%。

同时运行Dictionary的FindEntry方法

然后我再次运行应用程序，使用 dottrace，这次结果略有不同：

这一次，一个线程是运行 FindEntry，另一个是Insert.

我的第一直觉是死锁了，后来觉得不可能，只有一个共享资源，而且没有锁。

那么这应该怎么解释呢？

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

Answer 1

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

我们来看看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;
}

看看 for 循环。 increment 部分是 i = entries[i].next，猜猜看：entries 是在 Resize method. next is a field of the inner Entry struct:

中更新的字段

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

如果您的代码无法退出 FindEntry 方法，最可能的原因是您设法弄乱了条目，以至于当您遵循next 字段指向的索引。

至于 Insert method，它有一个非常相似的 for 循环：

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

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

使用 ConcurrentDictionary 或诸如 ReaderWriterLockSlim 之类的锁定模式（Dictionary 对于并发读取是线程安全的）或普通的旧 lock 很好地解决了问题。

Answer 2

看起来像是竞争条件（不是死锁）- 正如您评论的那样，这会导致混乱的内部状态。

字典不是线程安全的，因此从单独的线程（即使每个线程只有一个）并发读取和写入同一容器是不安全的。

一旦达到竞争条件，将会发生什么就变得不确定了；在这种情况下，似乎是某种无限循环。

一般来说，一旦需要写入权限，就需要某种形式的同步。

Answer 3

只是为了补充（并关联）前 2 个很好的答案：

Dictionary<T> 是一个 HashMap 实现，与大多数 HashMap 实现一样，它 internally uses LinkedLists（用于存储多个元素，以防不同的键在散列和取散列模后进入相同的桶位置) 并使用一个内部数组，它可以随着字典中元素数量的增长而增长。

由于代码以空字典开头并添加了很多元素，因此字典以 small internal array（可能大小=3）开头并频繁增加。由于有多个线程试图向字典中添加元素，很有可能不同的线程同时尝试对字典进行 Resize()。由于 Dictionary 不是 thread-safe class，如果两个线程试图同时修改同一个 LinkedList，这可能会使 LinkedList 处于不一致状态（即竞争条件 - 两个线程修改相同的数据，导致不可预测的结果。

如其他答案中所述，修改 LinkedList 时的竞争条件可能会使 LinkedList 进入无效状态，这将解释循环遍历 LinkedList 的方法（FindEntry 和Insert)。高 cpu（每个线程使用 100% cpu）由这个无限循环解释 - 如果它是一个死锁，线程将处于 low-cpu 状态等待一些锁定的资源。

因为我们知道元素的数量，所以我们可以 pre-initialize 字典的大小更大（比如 1000000），以减少出现竞争条件的机会。但这并不能解决问题 - 最好的解决方案仍然是使用 thread-safe class (ConcurrentDictionary<T>).

.Net中的Dictionary在并行读写时是否有可能导致死锁？

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

.net

c#

parallel-processing

multithreading

task-parallel-library