Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

This is based on Alexey Drobyshevsky's excellent article Problems with Iteration

At Alexey's suggestion, I implemented his solution using a ReaderWriterLockSlim. Then I fleshed out a ThreadSafeList : IList implementation.

The idea here is to have a collection that multiple threads can iterate over, execute linq queries against, and modify at the same time without data inconsistencies, InvalidOperationExceptions, or deadlocks.

using System.Collections;
using System.Collections.Generic;
using System.Threading;
namespace ThreadSafeEnumeration
{

public class SafeEnumerator<T> : IEnumerator<T>
{
    private readonly ReaderWriterLockSlim _readerWriterLock;
    private readonly IEnumerator<T> _innerCollection;        

    public SafeEnumerator(IEnumerator<T> innerCollection, ReaderWriterLockSlim readerWriterLock)
    {
        _innerCollection = innerCollection;            
        _readerWriterLock = readerWriterLock;         
        _readerWriterLock.EnterReadLock();
    }

    public void Dispose()
    {            
        _readerWriterLock.ExitReadLock();
    }        

    public bool MoveNext()
    {
        return _innerCollection.MoveNext();
    }

    public void Reset()
    {
        _innerCollection.Reset();
    }

    public T Current
    {
        get { return _innerCollection.Current; }
    }

    object IEnumerator.Current
    {
        get { return Current; }
    }        
}


public class ThreadSafeList<T> : IList<T>
{        
    private readonly ReaderWriterLockSlim _readerWriterLock = new ReaderWriterLockSlim(LockRecursionPolicy.SupportsRecursion);        
    private readonly List<T> _innerList = new List<T>();


    IEnumerator<T> IEnumerable<T>.GetEnumerator()
    {            
        _readerWriterLock.EnterReadLock();
        try
        {
            return new SafeEnumerator<T>(_innerList.GetEnumerator(), _readerWriterLock);
        }
        finally
        {
            _readerWriterLock.ExitReadLock();
        }
    }

    public IEnumerator GetEnumerator()
    {
        return (this as IEnumerable<T>).GetEnumerator();
    }

    public void Add(T item)
    {
        try
        {
            _readerWriterLock.EnterWriteLock();
            _innerList.Add(item);
        }
        finally
        {
            _readerWriterLock.ExitWriteLock();
        }
    }

    public void Clear()
    {
        try
        {
            _readerWriterLock.EnterWriteLock();
            _innerList.Clear();
        }
        finally
        {
            _readerWriterLock.ExitWriteLock();
        }
    }

    public bool Contains(T item)
    {
        try
        {
            _readerWriterLock.EnterReadLock();
            return _innerList.Contains(item);
        }
        finally
        {
            _readerWriterLock.EnterReadLock();
        }

    }

    public void CopyTo(T[] array, int arrayIndex)
    {
        try
        {
            _readerWriterLock.EnterWriteLock();
            _innerList.CopyTo(array, arrayIndex);
        }
        finally
        {
            _readerWriterLock.ExitWriteLock();
        }
    }

    public bool Remove(T item)
    {
        try
        {
            _readerWriterLock.EnterWriteLock();
            return _innerList.Remove(item);
        }
        finally
        {
            _readerWriterLock.ExitWriteLock();
        }
    }

    public int Count
    {
        get
        {
            try
            {
                _readerWriterLock.EnterReadLock();
                return _innerList.Count;
            }
            finally
            {
                _readerWriterLock.ExitReadLock();
            }
        }
    }

    bool ICollection<T>.IsReadOnly
    {
        get
        {
            try
            {
                _readerWriterLock.EnterReadLock();
                return ((ICollection<T>)_innerList).IsReadOnly;
            }
            finally
            {
                _readerWriterLock.ExitReadLock();
            }
        }
    }

    public int IndexOf(T item)
    {
        try
        {
            _readerWriterLock.EnterReadLock();
            return _innerList.IndexOf(item);
        }
        finally
        {
            _readerWriterLock.ExitReadLock();
        }
    }

    public void Insert(int index, T item)
    {
        try
        {
            _readerWriterLock.EnterWriteLock();
            _innerList.Insert(index, item);
        }
        finally
        {
            _readerWriterLock.ExitWriteLock();
        }
    }

    public void RemoveAt(int index)
    {
        try
        {
            _readerWriterLock.EnterWriteLock();
            _innerList.RemoveAt(index);
        }
        finally
        {
            _readerWriterLock.ExitWriteLock();
        }
    }

    public T this[int index]
    {
        get
        {
            try
            {
                _readerWriterLock.EnterReadLock();
                return _innerList[index];
            }
            finally
            {
                _readerWriterLock.ExitReadLock();
            }
        }

        set
        {
            try
            {
                _readerWriterLock.EnterWriteLock();
                _innerList[index] = value;
            }
            finally
            {
                _readerWriterLock.ExitWriteLock();
            }
        }
    }
}


}
share|improve this question
    
I believe this implementation may be prone to deadlocks. I have a unit test that starts 300 CRUD threads against a collection of 1,000,000 objects in a random fashion. 90% of the time the test returns within 10 seconds (8 core cpu) with all assertions passing. However, about 1 in 10 runs hangs indefinitely and throws no errors. My attempts to try to observe or log the deadlock come up empty. It never hangs in debug mode, and any writing to disk appears to change the timing just enough for the deadlock case to never occur. Your experience in solving deadlocks would be appreciated. –  Tion Jan 3 '12 at 14:51
    
I think that having concurrent threads reading & writing the collection without inconsistencies or deadlocks cannot be achieved. There has to be a compromise somewhere; regarding either data integrity or locking policy. Anyway, I find your question and Alexey's article very interesting. –  w0lf Jan 4 '12 at 10:26
    
I'm certainly finding out that it's very hard and may not be worth the effort. However, I'm still under the impression that it's theoretically possible to safely implement a collection that can be read and written to by multiple threads. I believe I should be able to avoid deadlocks while locking only on one resource. I think at this point I need a tool that will help me do a StackTrace dump of all the running threads. This is proving to be an extremely challenging exercise in Windows 7 with x64 .Net 4. –  Tion Jan 4 '12 at 18:16
    
I finally managed to create .dmp files that i can actually debug. (had to use procdump.exe because of 32 bit process on an x64 issues) I discovered some very odd behavior that occurs only when running in ReSharper test runner, and only when in run mode (not in debug mode). Very strangely the threads seem to hang at _readerWriterLock.ExitWriteLock(); why would RELEASING a lock be blocked!? What is it waiting for!? When running in as a console app, or even in R# test runner in debug mode, this bizarre blocking does not occur and it works perfectly as designed. R# must be doing something weird. –  Tion Jan 6 '12 at 20:34
    
I think that your CopyTo method only requires a read lock, not a write lock. –  Dr. Wily's Apprentice Jan 12 '12 at 20:32
add comment

2 Answers

Debugging multi threaded apps, for me, has always had the affect of aligning the threads and hiding deadlocks. This experience is mostly in native code, however i could imagine same thing could happen in managed. Not sure exactly why, but I think it has to do with introducing a delay on context switching in the debugger introspecting the stack and running it with symbols loaded. Depending on what the test is doing(Console.Write) running in console may have a similar affect aligning the thread while waiting for io.

Just my 2 cents i guess...

share|improve this answer
    
I wonder if Visual Studio's Intellitrace feature (Ultimate edition only, for now) would make it easier to debug multi-threading issues. If I understand it, one can use the dump file to effectively step through an already completed execution. –  Dr. Wily's Apprentice Jan 12 '12 at 20:42
add comment

I see that you're using the ReaderWriterLockSlim constructor with the SupportsRecursion LockRecursionPolicy.

Notice this line in the documentation for ReaderWriterLockSlim: "Regardless of recursion policy, a thread that initially entered read mode is not allowed to upgrade to upgradeable mode or write mode, because that pattern creates a strong probability of deadlocks."

However, I don't see anything in your code that makes me think that this is causing you a problem. In fact, calls to the EnterWriteLock method will throw a SynchronizationLockException if you have previously called EnterReadLock, so I'm sure you would have noticed that happening.


I see that there are multiple places in your code where you are doing this:

    try
    {
        _readerWriterLock.EnterWriteLock();
        // ...
    }
    finally
    {
        _readerWriterLock.ExitWriteLock();
    }

You should keep the call to EnterWriteLock outside of the try block, because if it fails for some reason, you don't want to call ExitWriteLock. The same goes for calls to EnterReadLock. It should be like this:

    _readerWriterLock.EnterWriteLock();
    try
    {
        // ...
    }
    finally
    {
        _readerWriterLock.ExitWriteLock();
    }
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.