问不变性是否完全消除了多处理器编程中对锁的需求？

EN

一个函数接受某些值并返回其他值，并且不干扰函数之外的任何内容，没有副作用，因此线程是安全的。如果您想考虑函数执行的方式如何影响耗电量，那是另一个问题。

我假设您所指的是一台图灵完整的机器，它正在执行某种定义良好的编程语言，其中实现细节是不相关的。换句话说，如果我用我所选择的编程语言编写的函数能够保证在语言范围内的不可变性，那么堆栈所做的事情就不重要了。当我用高级语言编程时，我不考虑堆栈，也不应该这样做。

为了说明这是如何工作的，我将在C#中提供几个简单的例子。为了使这些例子成为真的，我们必须做几个假设。首先，编译器没有错误地遵循C#规范，其次，它生成正确的程序。

假设我想要一个简单的函数，它接受一个字符串集合，并返回一个字符串，该字符串是集合中所有字符串的连接，由逗号分隔。C#中的一个简单、天真的实现可能如下所示：

public string ConcatenateWithCommas(ImmutableList<string> list)
{
    string result = string.Empty;
    bool isFirst = false;

    foreach (string s in list)
    {
        if (isFirst)
            result += s;
        else
            result += ", " + s;
    }
    return result;
} 

这个例子是不可变的，表面上看。我怎么知道的？因为string对象是不可变的。然而，实施并不理想。因为result是不可变的，所以每次都必须通过循环创建一个新的string对象，替换result指向的原始对象。这可能会对速度产生负面影响，并给垃圾收集器带来压力，因为垃圾收集器必须清理所有这些额外的字符串。

现在，假设我这样做：

public string ConcatenateWithCommas(ImmutableList<string> list)
{
    var result = new StringBuilder();
    bool isFirst = false;

    foreach (string s in list)
    {
        if (isFirst)
            result.Append(s);
        else
            result.Append(", " + s);
    }
    return result.ToString();
} 

注意，我已经将string result替换为可变对象StringBuilder。这比第一个示例要快得多，因为不是每次都通过循环创建一个新字符串。相反，StringBuilder对象只是将每个字符串中的字符添加到一个字符集合中，并在末尾输出整个过程。

即使StringBuilder是可变的，这个函数是不可变的吗？

是的，是这样的。为什么？因为每次调用此函数时，都会创建一个新的StringBuilder，仅用于该调用。所以现在我们有了一个纯函数，它是线程安全的，但是包含可变的组件。

但如果是我干的呢？

public class Concatenate
{
    private StringBuilder result = new StringBuilder();
    bool isFirst = false;

    public string ConcatenateWithCommas(ImmutableList<string> list)
    {
        foreach (string s in list)
        {
            if (isFirst)
                result.Append(s);
            else
                result.Append(", " + s);
        }
        return result.ToString();
    } 
}

这种方法线程安全吗？不，不是。为什么？因为这个类现在保存的是我的方法所依赖的状态。在该方法中现在存在一个争用条件:一个线程可以修改IsFirst，但是另一个线程可以执行第一个Append()，在这种情况下，我现在在字符串的开头有一个逗号，这个逗号不应该在那里。

我为什么要这样做？好吧，我可能希望线程将字符串累积到我的result中，而不考虑顺序，也不考虑线程进入的顺序。也许是个伐木工人，谁知道呢？

无论如何，为了修复它，我在方法的内部放置了一个lock语句。

public class Concatenate
{
    private StringBuilder result = new StringBuilder();
    bool isFirst = false;
    private static object locker = new object();

    public string AppendWithCommas(ImmutableList<string> list)
    {
        lock (locker)
        {
            foreach (string s in list)
            {
                if (isFirst)
                    result.Append(s);
                else
                    result.Append(", " + s);
            }
            return result.ToString();
        }
    } 
}

现在又是线程安全了。

我的不可变方法可能无法实现线程安全的唯一方法是，如果该方法以某种方式泄漏了它的部分实现。会发生这种事吗？如果编译器是正确的，程序是正确的，则不会。我会需要这样的方法的锁吗？不是的。

关于如何在并发场景中泄漏实现的示例，请看这里。

我不确定我是否理解你的问题。

答案是肯定的。如果您的所有对象都是不可变的，那么您不需要任何锁。但是，如果您需要保留一个状态(例如，您实现了一个数据库，或者您需要聚合来自多个线程的结果)，那么您需要使用可变性，因此也需要锁定。不可变性消除了对锁的需求，但通常您无法负担完全不可变的应用程序。

对第2部分的回答-锁应该总是比没有锁慢。

将一组相关状态封装在一个不可变对象的单个可变引用中，可以使用该模式执行多种状态修改：

do
{
   oldState = someObject.State;
   newState = oldState.WithSomeChanges();
} while (Interlocked.CompareExchange(ref someObject.State, newState, oldState) != oldState;

如果两个线程都试图同时更新someObject.state，那么两个对象都将读取旧状态，并确定新状态将是什么，而不会彼此更改。执行CompareExchange的第一个线程将存储它认为下一个状态应该是什么。第二个线程将发现状态不再与它先前读取的状态匹配，因此，随着第一个线程的更改生效，将重新计算系统的适当下一个状态。

这种模式的优点是，被拦截的线程不能阻止其他线程的进程。它的进一步优势是，即使有激烈的竞争，一些线程将始终取得进展。但是，它的缺点是，在存在争用的情况下，许多线程可能会花费大量的时间来做工作，而这些工作最终会被丢弃。例如，如果单独CPU上的30个线程都试图同时更改一个对象，那么一个线程将在第一次尝试中成功，一个线程将在第二次尝试中成功，另一个线程将在第三个线程上成功，因此每个线程平均每个线程将进行15次更新其数据的尝试。使用“咨询”锁可以显著改善情况:在线程尝试更新之前，应该检查是否设置了“争用”指示符。如果是这样的话，它应该在进行更新之前获得一个锁。如果一个线程在更新中做了几次失败的尝试，它应该设置争用标志。如果试图获取锁的线程发现没有其他人在等待，则应该清除争用标志。请注意，这里的锁不是“正确性”所必需的；即使没有它，代码也会正确工作。锁的目的是尽量减少代码在不太可能成功的操作上花费的时间。