Reader-writer collection

Question

This is based on Alexey Drobyshevsky's excellent article, "Problems with Iteration". With Alexey's suggestion, I implemented his solution using a ReaderWriterLockSlim. Then I fleshed out a ThreadSafeList<T> : IList<T> 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();
            }
        }
    }
}


}

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
– Tion, Commented Jan 3, 2012 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. — Cristian Lupascu
– Cristian Lupascu, Commented Jan 4, 2012 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
– Tion, Commented Jan 4, 2012 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
– Tion, Commented Jan 6, 2012 at 20:34
I think that your CopyTo method only requires a read lock, not a write lock. — Dr. Wily's Apprentice
– Dr. Wily's Apprentice, Commented Jan 12, 2012 at 20:32

Jamal · Accepted Answer · 2015-10-24 06:14:54Z

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

Jamal · Accepted Answer · 2015-10-24 06:13:03Z

1

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 the same thing could happen in managed. I'm not exactly sure 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 I/O.

edited Oct 24, 2015 at 6:13

Jamal

35.2k13 gold badges134 silver badges238 bronze badges

answered Jan 12, 2012 at 20:27

Dmitry Orlovsky

111 bronze badge

\$\begingroup\$ 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. \$\endgroup\$

Dr. Wily's Apprentice
– Dr. Wily's Apprentice

2012-01-12 20:42:16 +00:00
Commented Jan 12, 2012 at 20:42

Add a comment |

Stack Exchange Network

Reader-writer collection

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Reader-writer collection

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions