为什么我的线程安全字典实现会产生数据竞争?

本文关键字:数据 竞争 实现 我的 线程 安全 字典 为什么 | 更新日期: 2023-09-27 18:08:09

我目前正在c#中实现一个线程安全的字典,它在内部使用不可变的AVL树作为桶。这样做的目的是在没有锁的情况下提供快速的读访问,因为在我的应用程序上下文中,我们只在启动时向这个字典中添加条目,之后,值主要是读取的(但仍然有一些写操作)。

我以以下方式构建了我的TryGetValueGetOrAdd方法:

public sealed class FastReadThreadSafeDictionary<TKey, TValue> where TKey : IEquatable<TKey>
{
    private readonly object _bucketContainerLock = new object();
    private ImmutableBucketContainer<TKey, TValue> _bucketContainer;
    public bool TryGetValue(TKey key, out TValue value)
    {
        var bucketContainer = _bucketContainer;
        return bucketContainer.TryFind(key.GetHashCode(), key, out value);
    }
    public bool GetOrAdd(TKey key, Func<TValue> createValue, out TValue value)
    {
        createValue.MustNotBeNull(nameof(createValue));
        var hashCode = key.GetHashCode();
        lock (_bucketContainerLock)
        {
            ImmutableBucketContainer<TKey, TValue> newBucketContainer;
            if (_bucketContainer.GetOrAdd(hashCode, key, createValue, out value, out newBucketContainer) == false)
                return false;
            _bucketContainer = newBucketContainer;
            return true;
        }
    }
    // Other members omitted for sake of brevity
}

正如你所看到的,我没有在TryGetValue中使用锁,因为。net运行时中的引用赋值是一个原子操作。通过将字段_bucketContainer的引用复制到一个局部变量,我确信可以安全地访问实例,因为它是不可变的。在GetOrAdd中,我使用锁来访问私有的_bucketContainer,这样我就可以确保一个值不会被创建两次(即,如果两个或更多线程试图添加一个值,只有一个线程可以实际创建一个新的ImmutableBucketContainer,因为锁增加了值)。

我使用Microsoft Chess测试并发性,在我的一个测试中,MCUT (Microsoft并发单元测试)报告当我用旧的桶容器交换新的桶容器时GetOrAdd中的数据竞争:

[DataRaceTestMethod]
public void ReadWhileAdd()
{
    var testTarget = new FastReadThreadSafeDictionary<int, object>();
    var writeThread = new Thread(() =>
                                 {
                                     for (var i = 5; i < 10; i++)
                                     {
                                         testTarget.GetOrAdd(i, () => new object());
                                         Thread.Sleep(0);
                                     }
                                 });
    var readThread = new Thread(() =>
                                {
                                    object value;
                                    testTarget.TryGetValue(5, out value);
                                    Thread.Sleep(0);
                                    testTarget.TryGetValue(7, out value);
                                    Thread.Sleep(10);
                                    testTarget.TryGetValue(9, out value);
                                });
    readThread.Start();
    writeThread.Start();
    readThread.Join();
    writeThread.Join();
}

MCUT报告以下消息:

23>测试结果:DataRace23> ReadWhileAdd() (Context=, TestType=MChess): [DataRace] find data race at GetOrAdd: fastreadthreadsafedictiondictionary .cs(68)

,即赋值GetOrAdd中的_bucketContainer = newBucketContainer;

我的实际问题是:为什么分配_bucketContainer = newBucketContainer是竞争条件?当前执行TryGetValue的线程总是复制_bucketContainer字段,因此不应该为更新而烦恼(除了在复制发生后可能将搜索值添加到_bucketContainer,但这与数据竞争无关)。在GetOrAdd中,有一个显式锁来防止并发访问。这是《象棋》中的一个漏洞,还是我遗漏了一些明显的内容?

为什么我的线程安全字典实现会产生数据竞争?

正如@CodesInChaos在问题评论中提到的,我错过了TryGetValue中的一个易失性读取。这个方法现在看起来像这样:

public bool TryGetValue(TypeKey typeKey, out TValue value)
{
    var bucketContainer = Volatile.Read(ref _bucketContainer);
    return bucketContainer.TryFind(typeKey, out value);
}

这个volatile read是必要的,因为访问这个字典的不同线程可能会缓存数据并相互独立地重新排序指令,这可能会导致数据竞争。此外,运行代码的CPU架构也很重要,例如x86和x64处理器默认执行易失性读取,而对于其他架构(如ARM或Itanium)可能不是这样。这就是为什么读访问必须使用内存屏障与其他线程同步,这是在Volatile.Read内部执行的(注意lock语句也在内部使用内存屏障)。Joseph Albahari在这里写了一个全面的教程:http://www.albahari.com/threading/part4.aspx