一个不可变的数据结构如何不是线程安全的？

Question

一个不可变的数据结构如何不是线程安全的？

multithreadingthread-safetyimmutability

9

在一篇名为“什么是‘线程安全’”的帖子中，Eric Lippert说：

“不可变数据结构的线程安全性在于确保所有操作中使用的数据在逻辑上保持一致，而代价是你正在查看可能已过时的不可变快照。”

我认为不可变数据结构的整个意义在于它们不会改变，因此不可能过时，因此它们本质上是线程安全的。

Lippert在这里是什么意思？

- Joshua Frank

7

一份印刷的报纸是无法改变的。一份印刷的报纸会过时吗？ - Solomon Slow

2

Eric L. 不仅说“不可变的”，他还说“不可变的_快照_”。这意味着可能有一些数据结构随时会发生变化，而不可变的“快照”是该数据结构状态的冻结副本，就像它在最近的某个时刻一样。当一个线程查看“快照”并根据其内容做出决策时，另一个线程可能正在更新“实时”副本。 - Solomon Slow

2

如果原始数据结构是不可变的，那么就不需要“快照”。你引用的文章明确提到了“快照”。 - Solomon Slow

2

@NathanHughes：谢谢分享；我之前没看过这个。对于嵌入在不断变化的世界中的不可变数据结构的纯函数来说，这正是 IDE 所处的情况，当我们设计异步工作流时，我们考虑了许多这篇文章中提出的想法。但仍有很多工作要做，以使它们更易于使用。 - Eric Lippert

我认为他的意思是“不可变数据结构本质上是线程安全的，但你需要牺牲查看可能过时的不可变快照这一事实。” - still_dreaming_1

显示剩余3条评论

2个回答

2

他的意思是，你可能正在查看与其他人不同的快照。考虑一下cons lists的工作原理：在向列表头部添加另一个元素后，实际上有两个列表（快照）。它们都是不可变的，但并不相同。

- michid

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Eric Lippert · Accepted Answer

Lippert在这里指的是什么？

我认为我写那部分内容的方式并不是很清晰。

早在2009年，我们正在设计Roslyn的数据结构——“C#和VB编译器作为服务”，因此考虑了如何在IDE中进行分析。在这个世界中，代码几乎从来都不正确——如果代码正确，为什么还要编辑它呢？——并且当您输入时，代码可能会每秒钟更改多次。

我认为不可变数据结构的全部意义在于它们不会改变，因此不能过时，并且因此具有固有的线程安全性。

正是它们不会改变的事实使它们可能过时。考虑IDE中的常见场景：

using System;
class P
{
  static void Main()
  {
    Console.E
  }
}

我们拥有不可变数据结构，它们代表了在您输入“E”之前的世界，并且我们有一个不可变数据结构，它代表了您刚刚进行的编辑——删除字母E，接下来发生了很多事情。

词法分析器知道以前的词法状态是不可变的，并且与“E”之前的世界匹配，因此重新分析仅限于“E”周围的部分，而不是重新分析整个标记流。同样，解析器会计算出这个新的（错误的！）解析树，用于此编辑。这将创建一个新的不可变解析树，它是旧的不可变解析树的编辑，然后真正的乐趣开始了。语义分析器尝试弄清楚 Console 意味着什么，然后尝试理解您可能通过 E 指的是什么，以便可以对 System.Console 成员进行 IntelliSense 下拉列表中心对齐，如果有的话。（由于程序中现在存在许多语义和句法错误，我们也开始了一个错误报告工作流程。）

现在假设您正在后台线程上处理所有这些内容，同时您按下“退格”并输入“W”。

所有这些分析仍在进行中，但它将为 Console.E 而不是 Console.W 正确。这些分析已经过时了。它属于一个不再相关的世界，我们必须重新开始分析退格和W。

简而言之，在另一个线程上对不可变数据进行分析是完全安全的，但是可能会继续在UI线程上发生使该工作无效的事情；这是将工作农出到工作线程的代价之一。

请记住，这些无效可能非常快速；我们预算了30毫秒用于重新分析、重新解析和 IntelliSense 更新，因为快速的打字者每秒可以输入超过十个按键；拥有重用过去分析的不可变状态的词法分析器和解析器是这种策略的关键部分，但然后您必须计划使当前分析无效并立即重做的情况。

顺便说一下，我们需要发明的机制来有效地跟踪这些无效是相当有趣的，并引发了一些关于基于取消的工作流程的见解，但这是另一个话题。