13

最近我看到一些 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。在许多情况下，这可能是极不可能的，但仍然是错误的。

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

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

4

5 回答 5

20

显然代码不是线程安全的。我们这里有一个明显的过早优化危险的例子。

请记住，双重检查锁定模式的目的是通过消除锁定成本来提高代码性能。如果锁没有争议，它已经非常便宜了。因此，双重检查锁定模式仅在以下情况下是合理的：(1) 锁将受到激烈竞争，或 (2) 代码对性能非常敏感，以至于无竞争锁的成本仍然太高高的。

显然我们不是第二种情况。看在上帝的份上，您正在使用字典。即使没有锁，它也会进行查找和比较，这将比避免无竞争锁所节省的成本高出数百或数千倍。

如果我们是第一种情况，那么找出导致争用的原因并消除它。如果您在锁上等待了很多时间，那么找出原因并用一个纤细的读写锁替换锁定或重组应用程序，以便没有那么多线程同时敲击同一个锁时间。

在任何一种情况下，都没有理由使用危险的、实现敏感的低锁技术。你应该只在那些非常罕见的情况下使用低锁技术，在这些情况下你真的真的不能承担无竞争锁的成本。

于 2010-04-12T20:37:50.873 回答
13

在这个例子中，异常 #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";
}

但是，并非设计为线程安全的代码的确切行为是不可预测的。
你不能依赖它。因此，双重检查代码确实被破坏了。

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

于 2010-04-12T18:33:22.747 回答
8

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

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

这实际上是一个众所周知的事实（或应该是），当另一个线程正在写入时，您无法从字典中读取。我在 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调用与调用同时运行，则为条件TryGetValue。

于 2010-04-12T18:51:11.070 回答
3

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

Pre-2.0，Before Generics (BG)，Hashtable是 .NET 中的主要关联容器，它确实提供了一些线程保证。来自MSDN：
“哈希表是线程安全的，可供多个读取线程和单个写入线程使用。当只有一个线程执行写入（更新）操作时，它对于多线程使用是线程安全的，这允许提供无锁读取作家被序列化到哈希表。”

在任何人变得非常兴奋之前，有一些限制。
参见例如Brad Abrams 的这篇文章，他拥有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 的示例中）。

这实际上只是一个例子，字典不是设计的，也不是线程安全的。然而，它的设计速度很快——这意味着锁不会被长时间持有。

于 2010-04-12T19:48:12.420 回答
1

包括问题中的代码，你可以用下面的代码进行测试。

//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，否则失败的可能性很小。

于 2010-04-12T18:42:27.850 回答