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

最近我看到一些在Dictionary上使用双重检查锁定模式的C#项目。 像这样的东西:

 private static readonly object _lock = new object(); private static volatile IDictionary _cache = new Dictionary(); 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 (在锁外)正在迭代集合。 在许多情况下这可能是极不可能的,但仍然是错误的。

是否有一个简单的程序来certificate此代码失败?

将其纳入unit testing是否有意义? 如果是这样,怎么样?

在此示例中,exception#1几乎立即在我的机器上抛出:

 var dict = new Dictionary() { { 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"; } 

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

我不确定我是否会对此进行unit testing,因为测试并发代码(并且正确)并不比首先编写并发代码复杂得多。

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

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

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

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

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

我真的不认为你需要certificate这一点,你只需要将人们引用到Dictionary的文档中 :

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

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

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


我将更进一步向你展示为什么,在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; } 

看看即使一个读者调用FindEntry如果Resize方法正好运行会发生什么:

  1. 线程A:添加元素,导致动态resize;
  2. 线程B:将桶的偏移量计算为(哈希码%桶数);
  3. 线程A:将桶更改为具有不同(素数)大小;
  4. 线程B:从桶索引处的桶arrays中选择元素索引;
  5. 线程B的指针不再有效。

这正是dtb的例子中失败的原因。 线程A搜索预先知道在字典中的密钥,但是找不到它。 为什么? 因为FindValue方法选择了它认为正确的桶,但在它甚至有机会进入内部之前,线程B改变了桶,现在线程A正在寻找一些完全随机的桶,它不包含甚至导致正确的进入。

故事的道德: TryGetValue不是primefaces操作,而Dictionary不是线程安全的类。 这不仅仅是您需要担心的并发写入; 你也不能有并发读写。

实际上,由于抖动和CPU的指令重新排序,过时的缓存等等,问题实际上比这更深入了 – 这里没有任何内存障碍 – 但这应该毫无疑问地certificate存在明显的竞争如果您有一个与TryGetValue调用同时运行的Add调用的条件。

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

Pre-2.0,在Generics(BG)之前, Hashtable是.NET中的主要关联容器,它确实提供了一些线程保证。 来自MSDN :
“Hashtable是线程安全的,可供多个读取器线程和单个写入线程使用。当只有一个线程执行写入(更新)操作时,它对multithreading使用是线程安全的,如果编写器允许无锁读取被序列化为Hashtable。“

在任何人都非常兴奋之前,有一些限制。
参见例如拥有Hashtable Brad Abrams的这篇文章 。
关于Hashtable更多历史背景可以在这里找到(……接近结束:“经过漫长的转移 – Hashtable怎么样?”)。

为什么在上述情况下Dictionary失败:

为了certificate它失败了,找到一个例子就足够了,所以我会尝试一下。
随着表的增长,会发生resize。
在resize时,会发生重新散列,并将其视为最后两行:

 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(); // clear the cache... } spinLock = 0; // release lock... } } 

这个程序只是试图让Create在遍历集合时“遍历”它。 它应该在具有至少两个核心(或两个处理器)的计算机上运行,​​并且很可能在此exception一段时间后失败。

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

添加此测试很困难,因为它是一个概率测试,并且您不知道失败需要多长时间(如果有的话)。 我猜你可以选择一个10秒的值,让它运行那么久。 如果在这段时间内没有失败,则测试通过。 不是最好的,而是一些东西。 您还应该在运行测试之前validationEnvironment.ProcessorCount > 1 ,否则它失败的可能性是微不足道的。