c# - 使链表线程安全

Question

我知道之前有人问过这个问题(我会继续研究)，但我需要知道如何以线程安全的方式创建特定的链表函数。我当前的问题是我有一个线程循环遍历链表中的所有元素，而另一个线程可能会向该列表的末尾添加更多元素。有时，当第一个线程忙于遍历它时，一个线程试图向列表中添加另一个元素(这会导致异常)。

我正在考虑只添加一个变量( bool 标志)来表示列表当前正忙于迭代，但是我如何检查它并等待第二个线程(如果它等待就可以，因为第一个线程运行得非常快)。我能想到的唯一方法是使用 while 循环不断地检查这个繁忙的标志。我意识到这是一个非常愚蠢的想法，因为它会导致 CPU 努力工作而无所事事。现在我来这里是为了寻求更好的见解。我读过锁等等，但它似乎与我的情况无关，但也许我错了？

与此同时，我会继续搜索互联网，如果找到解决方案，我会发回。

编辑:让我知道是否应该发布一些代码来解决问题，但我会尝试更清楚地解释它。

所以我有一个类，其中有一个链表，其中包含需要处理的元素。我有一个线程通过函数调用(我们称它为“processElements”)遍历此列表。我有第二个线程以不确定的方式添加要处理的元素。但是，有时它会在 processElements 运行时尝试调用此 addElement 函数。这意味着 an 元素在第一个线程迭代时被添加到链表中。这是不可能的，会导致异常。希望这能解决问题。

我需要在 processElements 方法执行完毕之前添加新元素的线程。

• 致遇到此问题的任何人。已接受的答案将为您提供一个快速、简单的解决方案，但请查看下面 Brian Gideon 的答案以获得更全面的答案，这肯定会让您有更多见识!

Answer 1

异常可能是在迭代过程中通过 IEnumerator 更改集合的结果。您可以使用很少的技术来维护线程安全。我将按难度顺序介绍它们。

锁定一切

这是迄今为止线程安全地访问数据结构的最简单和最简单的方法。当读取和写入操作的数量相等时，这种模式很有效。

LinkedList<object> collection = new LinkedList<object>();

void Write()
{
  lock (collection)
  {
    collection.AddLast(GetSomeObject());
  }
}

void Read()
{
  lock (collection)
  {
    foreach (object item in collection)
    {
      DoSomething(item);
    }
  }
}

复制-阅读模式

这是一个稍微复杂的模式。您会注意到在读取数据结构之前先创建了一份数据结构的副本。当读取操作的数量与写入的数量相比很少并且复制的惩罚相对较小时，这种模式很有效。

LinkedList<object> collection = new LinkedList<object>();

void Write()
{
  lock (collection)
  {
    collection.AddLast(GetSomeObject());
  }
}

void Read()
{
  LinkedList<object> copy;
  lock (collection)
  {
    copy = new LinkedList<object>(collection);
  }
  foreach (object item in copy)
  {
    DoSomething(item);
  }
}

复制-修改-交换模式

最后我们有了最复杂和最容易出错的模式。 我实际上不建议使用这种模式，除非你真的知道你在做什么。任何与我下面的内容的偏差都可能导致问题。这很容易搞砸。事实上，我过去也无意中搞砸了这个。您会注意到在所有修改之前创建了数据结构的副本。然后修改副本，最后用新实例换出原始引用。基本上，我们总是将 collection 视为不可变的。当写操作的数量与读取的数量相比很少并且复制的惩罚相对较小时，这种模式很有效。

object lockobj = new object();
volatile LinkedList<object> collection = new LinkedList<object>();

void Write()
{
  lock (lockobj)
  {
    var copy = new LinkedList<object>(collection);
    copy.AddLast(GetSomeObject());
    collection = copy;
  }
}

void Read()
{
  LinkedList<object> local = collection;
  foreach (object item in local)
  {
    DoSomething(item);
  }
}

更新:

所以我在评论区提出了两个问题:

• 为什么在写入端使用 lock(lockobj) 而不是 lock(collection)？
• 为什么在读取端 local = collection？

关于第一个问题，请考虑 C# 编译器将如何扩展 lock。

void Write()
{
  bool acquired = false;
  object temp = lockobj;
  try
  {
    Monitor.Enter(temp, ref acquired);
    var copy = new LinkedList<object>(collection);
    copy.AddLast(GetSomeObject());
    collection = copy;
  }
  finally
  {
    if (acquired) Monitor.Exit(temp);
  }
}

现在希望如果我们使用 collection 作为锁定表达式，可以更容易地看到会出现什么问题。

• 线程 A 执行 object temp = collection。
• 线程 B 执行 collection = copy。
• 线程 C 执行 object temp = collection。
• 线程 A 获取带有原始引用的锁。
• 线程 C 使用新 引用获取锁。

显然这将是灾难性的!由于多次进入临界区，写入会丢失。

现在第二个问题有点棘手。您不一定必须使用我在上面发布的代码来执行此操作。但是，那是因为我只使用了一次 collection。现在考虑以下代码。

void Read()
{
  object x = collection.Last;
  // The collection may get swapped out right here.
  object y = collection.Last;
  if (x != y)
  {
    Console.WriteLine("It could happen!");
  }
}

这里的问题是 collection 可能随时被换掉。这将是一个难以置信 很难找到的错误。这就是为什么我在执行此模式时总是在读取端提取本地引用。这确保我们在每次读取操作时使用相同 集合。

再次强调，因为这些问题非常微妙，所以我不建议使用这种模式，除非您确实需要。