Make a linked list thread safe

Question

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).

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.

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

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.

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

• To anyone stumbling on this problem. The accepted answer will give you a quick, an easy solution, but check out Brian Gideon's answer below for a more comprehensive answer, which will definitely give you more insight!

Answer 1

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.

Lock Everything

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

Copy-Read Pattern

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

Copy-Modify-Swap Pattern

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

Update:

So I posed two questions in the comment section:

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

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

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

• 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.

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.