使链接列表线程安全

Question

我知道之前已经问过这个问题(我将继续研究),但我需要知道如何以线程安全的方式创建特定的链表功能.我当前的问题是我有一个循环遍历链表中所有元素的线程,另一个可能会在此列表的末尾添加更多元素.有时会发生这样的情况:一个线程尝试将另一个元素添加到列表中,而第一个元素正忙于迭代它(这会导致异常).

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

与此同时,如果我找到解决方案,我将继续搜索互联网并发回.

编辑:让我知道我是否应该发布一些代码来清理,但我会尝试更清楚地解释它.

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

我需要添加新元素的线程,直到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可以随时换掉.这将是一个难以置信的难以找到的bug.这就是我在执行此模式时总是在读取端提取本地引用的原因.这确保我们在每次读取操作中使用相同的集合.

同样,因为像这样的问题是如此微妙,我不建议使用这种模式,除非你真的需要.

Answer 2

以下是如何使用锁来同步对列表的访问的快速示例:

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);
    }
}