10

我知道以前有人问过这个问题（我会继续研究），但我需要知道如何以线程安全的方式制作特定的链表函数。我当前的问题是我有一个线程循环遍历链表中的所有元素，而另一个线程可能会在此列表的末尾添加更多元素。有时会发生一个线程尝试将另一个元素添加到列表中，而第一个线程正忙于迭代它（这会导致异常）。

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

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

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

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

我需要添加新元素以产生的线程，直到 processElements 方法完成执行。

  • 对于任何绊倒这个问题的人。接受的答案将为您提供一个快速、简单的解决方案，但请查看下面 Brian Gideon 的答案以获得更全面的答案，这肯定会给您更多的洞察力！
4

2 回答 2

28

异常可能是由于在迭代过程中通过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可能随时被换掉。这将是一个非常难以找到的错误。这就是为什么我在执行此模式时总是在读取端提取本地引用。这确保我们在每个读取操作上使用相同的集合。

同样，因为这些问题非常微妙，我不建议使用这种模式，除非你真的需要。

于 2012-05-11T19:00:08.220 回答
6

下面是一个快速示例，说明如何使用锁来同步您对列表的访问：

private readonly IList<string> elements = new List<string>();

public void ProcessElements()
{
    lock (this.elements)
    {
        foreach (string element in this.elements)
            ProcessElement(element);
    }
}

public void AddElement(string newElement)
{
    lock (this.elements)
    {
        this.elements.Add(element);
    }
}

语句意味着执行线程应该在lock(o)对象上获取互斥锁o，执行语句块，最后释放对象上的锁o。如果另一个线程尝试同时获取锁o（对于相同的代码块或任何其他），那么它将阻塞（等待）直到锁被释放。

因此，关键点是您对lock要同步的所有语句使用相同的对象。您使用的实际对象可能是任意的，只要它是一致的。在上面的示例中，我们将集合声明为只读，因此我们可以安全地将其用作我们的锁。但是，如果不是这种情况，您应该锁定另一个对象：

private IList<string> elements = new List<string>();

private readonly object syncLock = new object();

public void ProcessElements()
{
    lock (this.syncLock)
    {
        foreach (string element in this.elements)
            ProcessElement(element);
    }
}

public void AddElement(string newElement)
{
    lock (this.syncLock)
    {
        this.elements.Add(element);
    }
}
于 2012-05-11T18:48:17.577 回答