Resolving concurrency problem around collections

Question

Hi,

I'm having issues with concurrent usage of a shared collection with a multi-player synchronous game I'm working on. I did some digging around and found a neat thread-safe IEnumerator/IList implementation on Alexey Drobyshevsky's post on codeproject here:

http://www.codeproject.com/KB/cs/safe_enumerable.aspx

After adopting his implementation I have even replaced all Linq queries on the shared collection with for/foreach loops because the Linq queries were still using the unsafe IEnumerable underneath.

Here's my implementation of the SafeList, and the list itself is being exposed to as a ReadOnlyCollection to the consuming classes.

http://theburningmonk.com/2010/03/thread-safe-enumeration-in-csharp/

After switching to this SafeList I am seeing far less problems, but under heavy load (80+ threads all of which read/write from and to the list at different points) I'm still seeing InvalidOperationException being thrown:

The element list has changed. The enumeration operation failed to continue

I have even tried using ReadWriterLockSlim in place of the lock object in my implementation of the SafeList but that proved fruitless too. The only other suggestion I have had so far is cloning the list every time a threads needs to loop through it. I'm hoping to avoid cloning the list every single time as the list is being used in way too many places it might be a performance hit and might introduce other bugs that are difficult to spot.

Given the time constraints I'll have to be pragmatic about it and if cloning is the safest and quickest way to go about solving this problem then I'm fine with it, but before resorting to this last ditch-attempt I'm just wondering if anyone out there has come across something similar is able to offer some advice.

Many thanks in advance!

[EDIT] Here is a little more information about the problem I'm seeing as requested:

For one 'game', there can be up to 100 or so synchronous clients connected and the game needs to message each connected client with updates every few seconds and so every few seconds this game needs to iterate through the shared list of players. When a player joins, or leaves, the list needs to be updated accordingly to reflect the changes. To add to that, the players can interact with the game and chat to other players, and every time a message is received from the player the game would again need to iterate through the same list and do a broadcast. The exceptions are typically thrown when the game is trying to broadcast messages to players (read operation) at the same time as many players leaving/joining (write operation) at the same time.

Answer 1

Given your description of the game structure, considering having a single thread that is the only thread that can directly access the list of players. Make the list effectively private to that one thread.

The way any other threads access the list is by sending messages to the list-manager thread. So that thread has a queue of messages that it waits on. While the queue is non-empty, it chews through the messages, following their instructions. They might say "Add a new player", or "Remove a player", or "Update the status of this player to 'unhappy'".

This thread can also periodically scan the list to send updates out to clients, or it can (even better) use the fact that it has a known stream of changes that are occurring to the list, and forward just those changes on to the clients.

Basic principle: make data private to one thread, and have the threads communicate via message queues.

Your basic data structure is a thread-safe queue class. There are dozens of examples on SO already. (And steer clear of any that claim to be "lock free" and yet thread safe. It's just not worth the risk.)

Answer 2

Even though the other suggestions about a refactoring is the way to go, one error in the 'thread-safe' class spills out (there might be more):

IEnumerator<T> IEnumerable<T>.GetEnumerator()
{
    // instead of returning an usafe enumerator,
    // we wrap it into our thread-safe class
    return new SafeEnumerator<T>(_inner.GetEnumerator(), _lock);
}

You create the enumerator from the _inner.GetEnumerator BEFORE the constructor is run, and thus any thread is free to modify the collection until you lock in the constructor. It is a small time slot, but with 80 threads it will happen. You need to lock around the the return .. statement to protect the enumerator.

EDIT: And also in the other places where you use the same pattern.