C# Concurrent List Questions

Question

I have a situation in C# where I have a list of simple types. This list can be accessed by multiple threads: entries can be added or removed, and the existence of an entry can be checked. I have encapsulated the list in an object exposing just those three operations so far.

I have a few cases to handle (not exactly the same as the methods I just mentioned).

1. A thread can just check for the existence of an entry. (simple)
   
2. A thread can check for the existence of an entry, and if it doesn't exist, add it.
   
3. A thread needs to check whether an entry exists, and if it does, wait until it is removed.
   
4. A combination of 2 and 3, where a thread checks for the existence of an entry, if it does exist, it must wait until it is removed before it can then add it itself.

The whole idea is that the existence of an entry signifies a lock. If an entry exists, the object it identifies cannot be changed and code cannot proceed because it is being modified elsewhere.

These may seem like simple novice situations but I'm refreshing myself on concurrency issues and it's making me a bit paranoid, and I'm also not as familiar with C#'s concurrency mechanisms.

What would be the best way to handle this? Am I totally off? Should check and add (test and set?) be combined into a fourth atomic operation? Would I simply be adding lock blocks to my methods where the list is accessed?

Also, is it possible to unit test this kind of thing (not the simple operations, the concurrency situations)?

Solution 1

Unit testing will certainly be hard.

This can all be done reasonably simply with the "native" concurrency mechanisms in .NET: lock statements and Monitor.Wait/Monitor.PulseAll. Unless you have a separate monitor per item though, you're going to need to wake all the threads up whenever anything is removed - otherwise you won't be able to tell the "right" thread to wake up.

If it really is just a set of items, you might want to use HashSet<T> instead of List<T> to represent the collection, by the way - nothing you've mentioned is to do with ordering.

Sample code, assuming that a set is okay for you:

using System;
using System.Collections.Generic;
using System.Threading;

public class LockCollection<T>
{
    private readonly HashSet<T> items = new HashSet<T>();
    private readonly object padlock = new object();

    public bool Contains(T item)
    {
        lock (padlock)
        {
            return items.Contains(item);
        }
    }

    public bool Add(T item)
    {
        lock (padlock)
        {
            // HashSet<T>.Add does what you want already :)
            // Note that it will return true if the item
            // *was* added (i.e. !Contains(item))
            return items.Add(item);
        }
    }

    public void WaitForNonExistence(T item)
    {
        lock (padlock)
        {
            while (items.Contains(item))
            {
                Monitor.Wait(padlock);
            }
        }
    }

    public void WaitForAndAdd(T item)
    {
        lock (padlock)
        {
            WaitForNonExistence(item);
            items.Add(item);
        }
    }

    public void Remove(T item)
    {
        lock (padlock)
        {
            if (items.Remove(item))
            {
                Monitor.PulseAll(padlock);
            }
        }
    }
}

(Completely untested, admittedly. You might also want to specify timeouts for the waiting code...)

Solution 2

While #1 may be the simplest to write, it's essentially a useless method. Unless you are holding onto the same lock after finishing a query for "existence of an entry", you are actually returning "existence of an entry at some point in the past". It doesn't give you any information about the current existence of the entry.

In between the discovery of a value in the list then doing any operation to retrieve, remove the value, another thread could come and remove it for you.

Contains operations on a concurrent list should be combined with the operation you plan on doing in the case of true/false existence of that check. For instance TestAdd() or TestRemove() is much safer than Contains + Add or Contains + Remove

Solution 3

here is a proper, concurrent, thread-safe, parallelisable concurrent list implementation http://www.deanchalk.me.uk/post/Task-Parallel-Concurrent-List-Implementation.aspx

Solution 4

There is a product for finding race conditions and suchlike in unit tests. It's called TypeMock Racer. I can't say anything for or against its effectiveness, though. :)

View more solutions

Comments

[Joel Coehoorn]

You should link to your blog post on thread safe collection interfaces.

[Henk Holterman]

Yes, but #4 does just that. The usability of the other methods is doubtful, but not necessarily wrong.

[JaredPar]

@Henk, I think #2-#4 are good methods. #1 though is not wrong but it's just not useful.

[Henk Holterman]

+1, I came to a similar solution but the HashSet makes it more efficient. Nice demo for the Monitor class, using nested Locks etc. Only problem could be a 'stampede' when an item is removed.

[Matt H]

Well, here's the thing. There are some cases where if an entry exists, I need to simply skip some code and keep going.

[JaredPar]

@Matt, the problem is you can't think of the element as existing. You must think of it as "used to have existed"

[Matt H]

Alright, so what should I do instead? The scenario I'm talking about is where a user can manually lock an object when editing, but a modification request can come in for the same object, and it should be ignored. Only if the object is not locked should the update request be processed.

[JaredPar]

@Matt, I'm not entirely sure I understand the scenario but would a TryUpdate be sufficient?

[Matt Z]

No, that implementation is completely non-thread safe for enumerating and the excessive locking makes it a poor choice anyway.