Multithreading – Making Multiple Data Structures Thread Safe Without Multiple Mutexes

multithreadingmutex

In my application, I have a class which I call a "Signal" (Think Qt signals if you are familiar with that) that represents a one-to-many connection. Objects can register handlers to the signal which, when "emitted" calls each of the handlers.

This is implemented under the hood as a list of function pointers. Making a "connection" adds a function pointer to the list. "Emitting" the signal loops through the list calling each function pointer in turn.

Since "connections" may be made from a thread different than the thread "emitting" the signal, I needed to make signals thread-safe. Since the list of function pointers is a shared resource, this mean adding a mutex to each signal instance that gets lock both when a connection is occurring and when it is being emitted.

This has all been working beautifully until I realized a problem. Mutexes take a relatively large amount of RAM to implement on my system. And, since each signal has a mutex and there are many signals, this means there is a lot of RAM used just to protect the data structures (which is actually more RAM than the data structure itself).

My first thought was to just use a shared mutex for the class, but this would mean only a single signal could ever be emitted at a time no matter the thread. A shared mutex or each thread isn't much better. In either case, there is an ever more fatal problem. With a shared mutex, if an emit ever caused a connection to occur, thus taking the mutex, the mutex would already be blocked because of the emit, thus resulting in a deadlock!

So, after that long explanation, here's my question. Is there some way in which to protect a data structure keeping in mind that, while one is being accessed, that may result in another simultaneous (i.e, nested) access?

This answer does not need to be specific to any language or framework, I just need some ideas as to the concepts.

Best Answer

Use an immutable list. Avoid stomping on other threads by taking a temporary copy.

First, define a global pointer to the most current list.

var globalList = new List<EmitAction>();

Never modify this list in place.

Instead, when you need to add, do this:

lock
{
    var newList = globalList.Clone().Append(newEntry);
    globalList = newList;
}

When you need to remove, do this:

lock
{
    var newList = globalList.Clone().Remove(entryToRemove);
    globalList = newList;
}

When you need to emit, do this:

var temporaryCopy = globalList;
foreach (entry in temporaryCopy) entry.Emit();

Since globalList never points to a list that might change, you don't have to lock anything when emitting. The pointer itself might change, but you can make a copy of that.

You still need to lock when adding or removing-- otherwise entries can get lost. But I assume adding and removing is a minority use case compared to emitting.

P.S. Some languages have constructs designed exactly for this purpose, e.g. c#'s ImmutableList.

Related Topic