CODEWITHSUNDEEP
c#concurrency
Matt H
Matt H

Reputation: 7389

C# Concurrent List Questions

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

Upvotes: 8

Views: 14449

Answers (4)

Dean Chalk
Dean Chalk

Reputation: 20451

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

Upvotes: 2

Rytmis
Rytmis

Reputation: 32037

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

Upvotes: 1

Jon Skeet
Jon Skeet

Reputation: 1499860

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

Upvotes: 8

JaredPar
JaredPar

Reputation: 754565

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

Upvotes: 8

Related Questions