如何证明带有 Dictionary 的 TryGetValue 的双重检查锁模式不是线程安全的

StackOverflow https://stackoverflow.com/questions/2624301

题

最近我看到一些 C# 项目在 Dictionary. 。像这样的东西：

private static readonly object _lock = new object();
private static volatile IDictionary<string, object> _cache = 
    new Dictionary<string, object>();

public static object Create(string key)
{
    object val;
    if (!_cache.TryGetValue(key, out val))
    {
        lock (_lock)
        {
            if (!_cache.TryGetValue(key, out val))
            {
                val = new object(); // factory construction based on key here.
                _cache.Add(key, val);
            }
        }
    }
    return val;
}

此代码不正确，因为 Dictionary 可以“增长”收藏 _cache.Add() 尽管 _cache.TryGetValue （锁外）正在迭代集合。在许多情况下这可能极不可能，但仍然是错误的。

有没有一个简单的程序来证明这段代码失败了？

将其合并到单元测试中是否有意义？如果是这样，怎么办？

有帮助吗？

解决方案

在此示例中，例外＃1几乎立即抛向我的机器：

var dict = new Dictionary<int, string>() { { 1234, "OK" } };

new Thread(() =>
{
    for (; ; )
    {
        string s;
        if (!dict.TryGetValue(1234, out s))
        {
            throw new Exception();  // #1
        }
        else if (s != "OK")
        {
            throw new Exception();  // #2
        }
    }
}).Start();

Thread.Sleep(1000);
Random r = new Random();
for (; ; )
{
    int k;
    do { k = r.Next(); } while (k == 1234);
    Debug.Assert(k != 1234);
    dict[k] = "FAIL";
}

但是，不是设计为线程安全的代码的确切行为是 不可预料的.
你 不能依靠它. 。因此，双重检查代码确实被打破了。

不过，我不确定是否会进行单元测试，因为测试并发代码（并正确处理）比首先编写并发代码要复杂得多。

其他提示

显然，代码不是线程安全。我们在这里拥有的是一个明显的过早优化危害的情况。

请记住，双检查锁定模式的目的是 提高性能 通过消除锁定成本来进行代码。如果锁定不合时宜，它已经非常便宜了。因此，仅在锁定锁定的情况下（1），两次检查的锁定模式仅是合理的 令人难以置信的 表现敏感的是，不受争议的锁的成本仍然太高。

显然，我们不在第二种情况下。您是为了天堂而使用的词典。即使没有锁，它也会进行查找和比较，而避免避免使用无争议的锁的节省的数百或数千倍。

如果我们在第一种情况下 弄清是什么原因导致争论并消除. 。如果您要在锁上等待很多时间时间。

无论哪种情况，都没有理由做危险的实施敏感的低锁技术。您应该只在那些非常罕见的情况下使用低锁技术，在这种情况下，您真的无法承担无争议的锁的费用。

我真的不认为你 需要 为了证明这一点，你只需要让人们参考 的文档 Dictionary<TKey, TValue>:

一个字典可以同时支持多个读者， 只要集合不被修改。 即便如此，通过集合进行枚举本质上是 不是线程安全的过程。 在枚举与写访问发生冲突的极少数情况下，必须在整个枚举期间锁定集合。 要允许多个线程访问集合以进行读写，您必须实现自己的同步。

实际上（或者应该是）众所周知的事实是，当另一个线程正在写入字典时，您无法从字典中读取内容。我在这里看到了一些“奇怪的多线程问题”类型的问题，结果发现作者没有意识到这不安全。

该问题与双重检查锁定无关，只是字典不是线程安全的类，即使对于单写入器/单读取器场景也是如此。

我将更进一步向您展示为什么在 Reflector 中这不是线程安全的：

private int FindEntry(TKey key)
{
    // Snip a bunch of code
    for (int i = this.buckets[num % this.buckets.Length]; i >= 0;
        i = this.entries[i].next)
    // Snip a bunch more code
}

private void Resize()
{
    int prime = HashHelpers.GetPrime(this.count * 2);
    int[] numArray = new int[prime];
    // Snip a whole lot of code
    this.buckets = numArray;
}

看看如果 Resize 方法恰好在运行，甚至有一个读者调用 FindEntry:

  1. 线程A：添加一个元素，导致动态调整大小；
  2. 线程B：计算桶偏移量为（哈希码%桶计数）；
  3. 线程A：将存储桶更改为具有不同的（主要）大小；
  4. 线程B：从中选择一个元素索引 新的 桶数组位于 老的 桶索引；
  5. 线程 B 的指针不再有效。

这正是 dtb 示例中失败的地方。线程 A 搜索一个键 预先知道 字典里有，但没找到。为什么？因为 FindValue 方法选择了它认为正确的存储桶，但在它有机会查看内部之前，线程 B 更改了存储桶，现在线程 A 正在寻找一些完全随机的存储桶，该存储桶不包含甚至不导致正确的条目。

故事的道德启示： TryGetValue 不是原子操作，并且 Dictionary<TKey, TValue> 不是线程安全的类。您需要担心的不仅仅是并发写入；你也不能有并发读写。

事实上，由于抖动和 CPU、过时的缓存等造成的指令重新排序，问题实际上比这要严重得多。- 这里没有使用任何内存屏障 - 但这应该证明 毫无疑问 如果你有一个明显的竞争条件 Add 调用同时运行 TryGetValue 调用。

我猜这个问题一次又一次地出现的原因：

2.0前，仿制药（BG）之前， Hashtable 是.NET中的主要关联容器，它确实提供了一些线程保证。从 MSDN:
“ Hashtable是线程可安全地由多个读取器线程和一个单个写作线程使用的。当只有一个线程执行写入（更新）操作时，它可以安全地使用多线程，这允许无锁的读数提供，规定作者提供了作家的规定。被序列化与散布。”

在任何人得到之前 极其 兴奋，有一些局限性。
参见例如 布拉德·艾布拉姆斯的这篇文章, ， 谁拥有 Hashtable.
关于更多历史背景 Hashtable 可以被找寻到 在这里（...接近末端：“在这个漫长的转移之后 - 散布呢？”）。

为什么 Dictionary<TKey, TValue> 在上述情况下失败：

为了证明它失败了，足以找到一个例子，所以我将尝试一下。
随着表的成长，调整大小。
在调整大小上，发生了重新仪，一个人将其视为最后两行：

this.buckets = newBuckets;
//One of the problems here.
this.entries = newEntries;

这 buckets 数组将索引纳入 entries 大批。假设到目前为止，我们有10个条目，现在我们正在添加一个新条目。
让我们进一步假装为简单起见，我们没有并且不会发生冲突。
在旧 buckets, ，如果没有碰撞，我们的索引从0到9。
现在新的索引 buckets 阵列从0到10（！）。
我们现在更改私人 buckets 字段指向新的存储桶。
如果有读者在做 TryGetValue() 目前，它使用了 新的 获取索引的存储桶，但然后使用 新的 索引阅读 老的 条目数组，因为 entries 字段仍然指向旧条目。
除了虚假阅读外，还可以得到的一件事是友好的 IndexOutOfRangeException.
解决此问题的另一种“好方法”是 @aaronaught 解释。 （...两者都可以发生，例如 DTB的 例子）。

这实际上只是一个例子，dictonary不是设计的，也从来没有想到线程安全。但是，它被设计为快速 - 这意味着锁不会长时间保存。

在问题中包括代码，您可以使用以下代码进行测试。

//using System.Collections.Generic;
//using System.Threading;

private static volatile int numRunning = 2;
private static volatile int spinLock = 0;

static void Main(string[] args)
{
    new Thread(TryWrite).Start();
    new Thread(TryWrite).Start();
}

static void TryWrite()
{
    while(true) 
    {
        for (int i = 0; i < 1000000; i++ )
        {
            Create(i.ToString());
        }

        Interlocked.Decrement(ref numRunning);
        while (numRunning > 0) { } // make sure every thread has passed the previous line before proceeding (call this barrier 1)

        while (Interlocked.CompareExchange(ref spinLock, 1, 0) != 0){Thread.Sleep(0);} // Aquire lock (spin lock)
        // only one thread can be here at a time...

        if (numRunning == 0) // only the first thread to get here executes this...
        {
            numRunning = 2; // resets barrier 1
            // since the other thread is beyond the barrier, but is waiting on the spin lock,
            //  nobody is accessing the cache, so we can clear it...
            _cache = new Dictionary<string, object>(); // clear the cache... 
        }

        spinLock = 0; // release lock...
    }

}

这个程序只是试图获得 Create 在“成长”时穿越该系列。它应该在具有至少两个内核（或两个处理器）的机器上运行，并且在此例外很可能会在一段时间后失败。

System.Collections.Generic.Dictionary`2.FindEntry(TKey key)

添加此测试很困难，因为它是一个概率测试，您不知道失败需要多长时间（如果有的话）。我想您可以选择大约10秒钟的值，然后让它运行这么长时间。如果在这段时间内没有失败，则测试会通过。不是最好的，而是什么。您还应该验证 Environment.ProcessorCount > 1 在进行测试之前，否则失败的可能性很小。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top