做一个链表线程安全 [英] Make a linked list thread safe

问题描述

我知道这之前已经被问（我会继续研究），但我需要知道如何在一个线程安全的方式特定的链接列表功能。我现在的问题是，我有一个线程，通过在一个链表的所有元素循环，而另一个可以添加更多的元素到此列表的末尾。有时，它发生在一个线程试图另一个元素添加到列表中，而首先是通过它忙迭代（这会导致一个例外）。

I know this has been asked before (and I will keep researching), but I need to know how to make a particular linked list function in a thread safe manner. My current issue is that I have one thread that loops through all elements in a linked list, and another may add more elements to the end of this list. Sometimes it happens that the one thread tries to add another element to the list while the first is busy iterating through it (which causes an exception).

我想的只是增加一个变量（布尔标志）说，名单目前正忙于通过被迭代，但我怎么检查它与第二个线程等待（这是确定的，如果它等待，因为第一个线程奔驰pretty）。我能想到这样做的唯一方法是通过使用whil​​e循环不断地检查这个繁忙的标志。我意识到这是一个非常愚蠢的想法，因为它会导致CPU努力在做任何有用的。而现在我在这里要求一个更好的洞察力。我已阅读有关锁等等，但它似乎并没有在我的情况有关，但也许我错了？

I was thinking of just adding a variable (boolean flag) to say that the list is currently busy being iterated through, but then how do I check it and wait with the second thread (it is ok if it waits, as the first thread runs pretty quickly). The only way I can think of doing this is through the use of a while loop constantly checking this busy flag. I realized this was a very dumb idea as it would cause the CPU to work hard while doing nothing useful. And now I am here to ask for a better insight. I have read about locks and so on, but it does not seem to be relevant in my case, but perhaps I am wrong?

在此期间我会继续搜索互联网和后回来，如果我找到一个解决方案。

In the meanwhile I'll keep searching the internet and post back if I find a solution.

编辑：
让我知道我是否应该发布一些code到明确的事情了，但我会尽量多解释清楚。

Let me know if I should post some code to clear things up, but I'll try and explain it more clearly.

所以我有它包含需要处理的元素的链表一类。我有一个线程，通过这个列表通过函数调用迭代（姑且称之为processElements）。我有一个第二螺纹，增加了元件的过程中的非确定性方式。但是，有时会发生，这会尝试而processElements运行调用此的addElement函数。这意味着一个元素被添加到该链接的表，而它是由第一线程迭代通过。这是不可能的，导致异常。希望这会清除它。

So I have a class with a linked list in it that contains elements that require processing. I have one thread that iterates through this list through a function call (let's call it "processElements"). I have a second thread that adds elements to process in a non-deterministic manner. However, sometimes it happens that it tries to call this addElement function while the processElements is running. This means that the an element is being added to the linked list while it is being iterated through by the first thread. This is not possible and causes an exception. Hope this clears it up.

我需要，增加了新的元素，得到直到processElements方法完成执行线程。

I need the thread that adds new elements to yield until the processElements method is done executing.

• 要绊人在这个问题上。接受答案会给你一个快速，简单的解决方案，但检查出布赖恩基甸的回答下面一个更COM prehensive答案，这一定会让你更深入的了解！

推荐答案

唯一的例外可能是通过的IEnumerator 具有迭代过程中更改集合的结果。还有，你可以用它来保持线程安全的一些技巧。我将present他们艰难的顺序。

The exception is likely the result of having the collection changed in the middle of an iteration via IEnumerator. There are few techniques you can use to maintain thread-safety. I will present them in order of difficultly.

锁定一切

这是迄今为止获取的数据结构线程安全的访问最简单，最平凡的方式。这种模式效果很好，当读取和写入操作的数量不相上下。

This is by far the easiest and most trivial method for getting access to the data structure thread-safe. This pattern works well when the number of read and write operations are equally matched.

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

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

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

复制读取模式

这是一个稍微复杂的模式。你会发现，数据结构的副本之前，阅读它的。这种模式工作良好时相比写入数和复制的惩罚读操作的次数较少是比较小的。

This is a slightly more complex pattern. You will notice that a copy of the data structure is made prior to reading it. This pattern works well when the number of read operations are few compared to the number of writes and the penalty of the copy is relatively small.

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

复制 - 修改 - 交换模式

最后，我们拥有最复杂，最容易出错的模式。 其实我不建议，除非你的使用这种模式真的的知道自己在做什么。从我下面的任何偏差可能导致的问题。这是很容易混乱这一个。事实上，我无意中搞砸这一个，以及过去。你会发现，所述数据结构的副本之前所有修改制成。然后副本被修改并终于原始参考被换出的新实例。基本上我们一直在治疗集就好像它是不可变的。这种模式工作良好时相比，数写操作的数目是很少的读取和复制的惩罚是比较小的。

And finally we have the most complex and error prone pattern. I actually do not recommend using this pattern unless you really know what you are doing. Any deviation from what I have below could lead to problems. It is easy to mess this one up. In fact, I have inadvertently screwed this one up as well in the past. You will notice that a copy of the data structure is made prior to all modifications. The copy is then modified and finally the original reference is swapped out with the new instance. Basically we are always treating collection as if it were immutable. This pattern works well when the number of write operations are few compared to the number of reads and the penalty of the copy is relatively small.

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

的更新：的

所以，我提出在评论部分的两个问题：

So I posed two questions in the comment section:

• 为什么锁（lockobj）而不是锁（集合）写入侧？


• 为什么本地=集合在读出侧？

• Why lock(lockobj) instead of lock(collection) on the write side?
• Why local = collection on the read side?

关于第一个问题，考虑C＃编译器将如何展开锁定。

Concerning the first question consider how the C# compiler will expand the 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);
  }
}

现在希望这是更容易，看看有什么可以去错了，如果我们使用集作为锁定前pression。

Now hopefully it is easier to see what can go wrong if we used collection as the lock expression.

• 线程A执行对象TEMP =集合。


• 线程B执行收集=拷贝。


• 线程C-执行时对象TEMP =集合。


• 线程A获取与的原始的参考锁。


• 线程C-获取与的新的的参考锁。

• Thread A executes object temp = collection.
• Thread B executes collection = copy.
• Thread C executes object temp = collection.
• Thread A acquires the lock with the original reference.
• Thread C acquires the lock with the new reference.

显然，这将是灾难性的！写会迷路，因为关键部分输入一次以上。

Clearly this would be disasterous! Writes would get lost since the critical section is entered more than once.

现在的第二个问题是有点棘手。你不一定的有无的与code我上面贴做到这一点。但是，那是因为我使用了集只有一次。现在考虑下面的code。

Now the second question was a little tricky. You do not necessarily have to do this with the code I posted above. But, that is because I used the collection only once. Now consider the following code.

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

这里的问题是，集可以随时换出。这将是一个的难以置信的错误很难发现。这是在做这个模式的时候，为什么我总是提取在读出侧的局部引用。这确保我们使用的相同的集合每个读取操作。

The problem here is that collection could get swapped out at anytime. This would be an incredibly difficult bug to find. This is why I always extract a local reference on the read side when doing this pattern. That ensure we are using the same collection on each read operation.

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

Again, because problems like these are so subtle I do not recommend using this pattern unless you really need to.

这篇关于做一个链表线程安全的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！