Concurrency problem when modifying a data in a list that supports synchronization

Question

Good day. I hope you are doing well. I'm trying to perform a unit test to test a Wrapper for a data structure I created (SortedList). This Wrapper is "thread-safe". First, I conducted a test where 10 threads accessed and added information to see if there was concurrency. Initially, I tested an unsynchronized list, and in this case, it was expected to have concurrency issues, which indeed happened. Then, I applied a synchronized list and the problem was resolved. Here is the code for the test (If you think it can be improved, any suggestions would be greatly appreciated).

Test Case:

        //Arrange
        SortedList<int> list = new();
        var synchronizedList = list.Synchronized();
        var expected = new SortedList<int> { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        int len = 10;
        ParallelOptions options = new()
        {
            MaxDegreeOfParallelism = len
        };

        //Act
        Parallel.For(0, len, options, synchronizedList.Add);

        //Asserts
        Assert.Equal(len, list.Count);
        Assert.Equal(expected, list);

In this case, there was no issue; everything worked as expected. The problem arises when I want to create the typical concurrency example, where N threads are created and they increase a value N times. In this example, there must be concurrency without fail. So, I prepared a small test case to verify if it can handle such a problem. Here is the code:

Test Case 2:

        //Arrange
        SortedList<int> list = new()
        {
            0
        };
        var synchronizedList = list.Synchronized();
        int len = 2, maxIter = 1;
        ParallelOptions options = new()
        {
            MaxDegreeOfParallelism = len
        };

        //Act
        Parallel.For(0, len, options, i =>
        {
            for (int j = 0; j != maxIter; ++j)
            {
                synchronizedList[0]++;
            }
        });

        //Asserts
        Assert.Equal(maxIter * len, list[0]);

When I tested the test case, for some strange reason, the expected result was 2 (I initially tested with 10,000 iterations and 10 threads). However, it was giving me 1. Perplexed, I went to check the code for the issue, but I didn't see any. Here is the code snippet of the indexer in the Wrapper class:

Index:

public T this[int index] 
            {
                get
                {
                    lock (_lock)
                    {
                        return _sortedList[index];
                    }
                }
                set
                {
                    lock (_lock)
                    {
                        _sortedList[index] = value;
                    }
                }
            }

As we can see, i have the lock, so it accesses safely. In fact, I did a debug test, and in that case, it passes the test. After this, I went to the code where I initialize the _lock.

Constructor:

internal SynchronizedSortedList(SortedList<T> sortedList)
{
      _sortedList = sortedList;
      _lock = _sortedList.SyncRoot;
}

After verifying that everything was "fine", I proceed to the get method of SyncRoot in the SortedList class.

SyncRoot:

public object SyncRoot
{
     get
     {
           if (_syncRoot == null)
           {
               Interlocked.CompareExchange<object>(ref _syncRoot, new object(), null);
           }
           return _syncRoot;
     }
}

In theory, everything is fine. In fact, I went to check the source code of a much earlier version of the List class, and I saw that it had it the same way. Therefore, there shouldn't be any issues. Finally, I will show the Synchronized method.

Synchronized:

public ISortedList<T> Synchronized()
{
   return new SynchronizedSortedList(this);
}

One obvious way to fix it would be as follows:

        //Arrange
        SortedList<int> list = new()
        {
            0
        };
        var synchronizedList = list.Synchronized();
        int len = 2, maxIter = 1;
        ParallelOptions options = new()
        {
            MaxDegreeOfParallelism = len
        };

        //Act
        Parallel.For(0, len, options, i =>
        {
            for (int j = 0; j != maxIter; ++j)
            {
                lock(list.SyncRoot)
                {
                   synchronizedList[0]++;
                }
            }
        });

        //Asserts
        Assert.Equal(maxIter * len, list[0]);

In this way, it would work excellently, but it's not the way I want to do it because this Wrapper already has locks that protect the resource to prevent threads from accessing it and avoid concurrency. If someone could help me, I would greatly appreciate it because I've been dealing with this problem since yesterday and I can't think of much. Greetings.

It's a very long code, but I can provide the link to the integration test on GitHub, and here is the code for SortedList with the Wrapper.

Answer 1

Your problem is that, in the following code, synchronizedList[0]++ is not thread safe and atomic:

Parallel.For(0, len, options, i =>
{
    for (int j = 0; j != maxIter; ++j)
    {
        // The following is not thread safe:
        synchronizedList[0]++;
    }
});

That's because synchronizedList[0]++ performs the following actions:

1. It gets the value from index 0 (with a lock).
2. It increments the value.
3. It sets the incremented value back at index 0 (with another lock).

The getting and setting are atomic but the overall sequence is not. Thus threads could interrupt and contend with each other. E.g. thread #1 gets a value, thread #2 gets the same value, thread #2 sets back its incremented value, then thread #1 sets back its incremented value. In such a case the value will be incremented only once -- which is exactly what you are seeing.

The correct fix for this is to make the increment atomic -- which is precisely your obvious way to fix it:

Parallel.For(0, len, options, i =>
{
    for (int j = 0; j != maxIter; ++j)
    {
        lock(list.SyncRoot)
        {
           synchronizedList[0]++;
        }
    }
});

Notes:

1. As currently implemented, your SortedList<T> actually reindexes the list inside its setter. I can't really recommend this approach as it could lead to surprising results.

   For instance, imagine you have a SortedList<int> with two zero values instead of one and increment the first value like so:

   SortedList<int> list = new() { 0, 0 };
   list[0]++;
   

   Then the value of list[0] will be 0 not 1, because the incremented value will have been moved to the end of the list.

   The fact that there's no obvious way to integer-index a sorted collection explains why SortedSet<T>, SortedList<TKey,TValue> and the old SortedList do not implement IList or IReadOnlyList<T>.

2. In general writing correct thread-safe code without locks is very hard. You might take a look at Eric Lippert's articles on thread safety, particularly Can I skip the lock when reading an integer?, which wraps up with:

   Code which avoids locks is extremely difficult to reason about, so make your life easier: if you can, don’t write shared memory code to begin with. If you have to, use locks consistently.

   (Emphasis his.) Jon Skeet's Volatility, Atomicity and Interlocking is also worth a look.

3. The fact that the increment operator is not atomic is why Interlocked.Increment() needs to exist. It isn't useful to you however. Since your setter currently reindexes the list merely incrementing a value atomically would not be sufficient.