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

Question

最近我看到一些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

是否有一个简单的程序来证明此代码失败了？

将其纳入单元测试是否有意义？如果是这样,怎么样？

Answer 1

显然,代码不是线程安全的.我们在这里有一个明显的过早优化危害的案例.

请记住,双重检查锁定模式的目的是通过消除锁定成本来提高代码性能.如果锁是无可争议的,它已经非常便宜了.因此,双重检查锁定模式仅在锁定将受到严重争议的情况下(1)或(2)代码如此令人难以置信的性能敏感以至于未经检测的锁定的成本仍然过高时才是合理的.高.

显然,我们不是第二种情况.你是为了天堂而使用字典.即使没有锁定,它也会进行查找和比较,这比避免无争议锁定的成本高出数百或数千倍.

如果我们处于第一种情况,那么找出导致争用的原因并消除它.如果你在锁定上做了很多等待,那么找出原因并用一个超薄的读写器锁替换锁定或重组应用程序,这样就不会有太多的线程在同一个锁上敲打时间.

在任何一种情况下,都没有理由采用危险的,实现敏感的低锁技术.你应该只在那些非常罕见的情况下使用低锁技术,你真的无法承担无争议锁定的成本.

Answer 2

在此示例中,异常#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";
}

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

我不确定我是否会对此进行单元测试,因为测试并发代码(并且正确)比编写并发代码要复杂得多.

Answer 3

我真的不认为你需要证明这一点,你只需要将人们引用到以下文档Dictionary<TKey, TValue>:

只要未修改集合,Dictionary就可以同时支持多个读取器.即便如此,通过集合枚举本质上不是一个线程安全的过程.在枚举与写访问争用的极少数情况下,必须在整个枚举期间锁定该集合.要允许多个线程访问集合以进行读写,您必须实现自己的同步.

它实际上是一个众所周知的事实(或应该是),当另一个线程写入它时,你无法从字典中读取.我在SO上看到了一些"奇怪的多线程问题"类型的问题,结果发现作者没有意识到这不安全.

问题与双重检查锁定没有特别关系,只是字典不是线程安全的类,即使对于单一编写器/单读取器场景也是如此.

我将更进一步向你展示为什么,在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调用的同时运行调用,则调用condition TryGetValue.