使链表线程安全

本文关键字：安全 线程 链表 | 更新日期: 2023-09-27 18:33:59

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

我

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

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

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

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

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

  • 对于任何偶然发现这个问题的人。接受的答案将为您提供快速，简单的解决方案，但是请查看下面的Brian Gideon的答案以获得更全面的答案，这肯定会给您更多的见解！

使链表线程安全

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

同样，由于此类问题非常微妙，除非您确实需要，否则我不建议使用此模式。

下面是如何使用锁同步对列表的访问权限的快速示例：

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);
    }
}
相关文章：