不可变的数据结构和并发性

本文关键字:并发 数据结构 不可变 | 更新日期: 2023-09-27 17:59:10

我正在努力了解在并发编程中使用不可变数据结构可以避免锁定的需要。我在网上读过一些东西,但还没有看到任何具体的例子。

例如,假设我们有一些代码(C#)在Dictionary< string, object>周围使用锁:

class Cache
{
    private readonly Dictionary<string, object> _cache = new Dictionary<string, object>();
    private readonly object _lock = new object();
    object Get(string key, Func<object> expensiveFn)
    {
        if (!_cache.ContainsKey("key"))
        {
            lock (_lock)
            {
                if (!_cache.ContainsKey("key"))
                    _cache["key"] = expensiveFn();
            }
        }
        return _cache["key"];
    }
}

如果_cache是不可变的,它会是什么样子?是否可以删除lock并确保不会多次调用expensiveFn

不可变的数据结构和并发性

简短的回答是它没有,至少没有完全。

不可更改性只能保证另一个线程在您使用数据结构时无法修改它的内容。一旦您有了实例,就永远无法修改该实例,因此您始终可以安全地读取它。任何编辑都需要创建实例的副本,但这些副本不会直接干扰任何已引用的实例。

在多线程应用程序中需要锁定和同步结构的原因仍然很多,即使使用不可变对象也是如此。它们主要处理与时间相关的问题,例如竞赛条件,或控制线程流以使活动在正确的时间发生。不可变对象并不能真正帮助解决这类问题。

不可变性使多线程更容易,但它并不能使变得容易


至于你关于不可变字典的问题。我不得不说,在大多数情况下,在你的例子中,甚至使用一个不可变的字典都没有多大意义。由于它被用作"活动"对象,随着项目的添加和删除,它会发生固有的变化。即使在像F#这样围绕不变性设计的语言中,也存在用于此目的的可变对象。有关详细信息,请参阅此链接。不可变的版本可以在这里找到。

不可变数据结构减少(注意,我说的是"减少",而不是"消除")并发锁定需求背后的基本思想是,每个线程都在本地副本上或针对不可变的数据结构工作,因此不需要锁定(没有线程可以修改任何其他线程的数据,只有它们自己的数据)。只有当多个线程可以同时修改同一可变状态时,才需要锁定,否则可能会出现"脏读取"和其他类似问题。

为什么不可变数据很重要的一个例子:假设您有一个person对象,它由两个不同的线程访问。如果thread1将人员保存到映射中(人员哈希包含人员名称),那么另一个thread2将更改人员名称。现在thread1将无法在地图中找到这个人,而它实际上在那里!

如果person是不可变的,那么不同线程持有的引用将是不同的,即使user2更改了名称,thread1也能够在映射中找到该人(因为将创建一个新的person实例)。