如何显示字典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";
}

但是,不设计为线程安全的代码的确切行为是 不可预知的 .
你 不能依靠它 . 所以双重检查代码确实被破坏了。

不过,我不确定是否要进行单元测试,因为测试并发代码(并使其正确)比首先编写并发代码要复杂得多。

显然,代码不是threadsafe。我们这里有一个明确的案例,说明了过早优化的危害。

记住,双重检查锁定模式的目的是 提高性能 通过消除锁的成本来消除代码。如果锁是未经检验的,那么它已经非常便宜了。因此,只有在以下情况下,双重检查的锁定模式才是合理的:(1)在锁将受到严重竞争的情况下,或(2)在代码如此的情况下 难以置信地 性能敏感,未经测试的锁的成本仍然过高。

显然,我们不是第二种情况。你在用字典看在上帝的份上。即使没有锁,它也会进行查找和比较,这比避免未经测试的锁节省的成本高出数百或数千倍。

如果我们是第一个病例,那么 找出引起争用的原因并消除 . 如果你在等待一个锁的时候做了很多事情,那么就找出原因,用一个瘦的读写器锁替换这个锁,或者重新构造应用程序,这样就不会有那么多线程同时攻击同一个锁。

在这两种情况下,都没有理由进行危险的、对实现敏感的低锁技术。您应该只在那些非常罕见的情况下使用低锁技术,在这些情况下,您真的,真的不能承担未经测试的锁的成本。

我真的不认为你 需要 为了证明这一点,你只需要让人们 documentation for 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:计算bucket偏移量为(散列码%bucket count);
3. A线:将桶改为不同的(基本)尺寸;
4. 线程B:从 新的 在 古老的 桶指数;
5. 线程B的指针不再有效。

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

故事的寓意: TryGetValue 不是原子操作,并且 字典<tkey,tvalue> 不是线程安全类。这不仅仅是需要担心的并发写操作;您也不能同时进行读写操作。

事实上,由于抖动和CPU、陈旧的缓存等指令重新排序,问题实际上比这要严重得多——这里没有任何内存障碍——但这应该证明 毫无疑问 如果你有一个 Add 调用与 TryGetValue公司 调用。

我想这个问题反复出现的原因是:

2.0之前,在普通医学(B.G.)之前, Hashtable 是.NET中的主要关联容器,它确实提供了一些线程保证。从 MSDN :
“哈希表是线程安全的,可供多个读卡器线程和单个写入线程使用。当只有一个线程执行写(更新)操作时,多线程使用它是线程安全的,如果写入程序序列化到哈希表,则允许无锁读取。”

在任何人得到之前 极其 兴奋,有一些限制。
参见例如 this post from Brad Abrams ,谁拥有 哈希表 .
更多历史背景 哈希表 可以找到 here (...near the end: "After this lengthy diversion - What about Hashtable?").

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

为了证明它是失败的,找到一个例子就足够了,所以我将尝试一下。
调整大小会随着表的增长而发生。
在调整大小时,会发生重新刷新,其中一个将此视为最后两行:

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

这个 buckets 数组将索引保存到 entries 数组。 假设到目前为止我们有10个条目,现在我们正在添加一个新条目。
为了简单起见,让我们进一步假设我们没有也不会发生碰撞。
在旧的 桶 ,我们有从0到9的索引-如果没有冲突。
现在索引在新的 桶 数组从0运行到10(!).
我们现在改变了隐私 桶 指向新存储桶的字段。
如果有读者在做 TryGetValue() 此时,它使用 新的 bucket获取索引,但随后使用 新的 要读取的索引 古老的 条目数组,因为 条目 字段仍指向旧条目。
除了错误的阅读之外,一个人能得到的东西之一是友好的 IndexOutOfRangeException .
另一个“好”的方法是 @Aaronaught's 解释。(…两者都可能发生,例如 dtb's 示例)。

这真的只是一个例子,口述并没有被设计出来,也不意味着线程安全。不过,它的设计速度很快——这意味着锁不会保持很长时间。

包括问题中的代码,您可以使用以下代码对其进行测试。

//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 在运行测试之前,否则失败的可能性很小。