Lockfree customer producer problem

Question

We have following class:

class ProcessStore
{
   ConcurrentDictionary<int, MyDisposableClass> _processes = new();
   bool _disposed;

   void Store(int Id)
   {
        if(_disposed) { throw; } 
        var mdc = new MyDisposableClass();
       _requests.Add(Id, mdc);
   }

   void Dispose()
   {
       if(_disposed)
       {
            return;
       }
       _disposed = true;
        
       foreach(var process in _processes)
       {
           process.Dispose();

       }
   }
}

Multiple threads may Store processes, and another thread will dispose it (but only single thread will dispose at time). This is effectively producer-consumer problem.

How can we make this class thread-safe? By thread-safe I mean that disposing instance disposes all Store requests and throws on new attempts. Simple answer is using locks, but I wonder if it's possible to do it correctly lock-free. I have following idea:

class ProcessStore
{
   ConcurrentDictionary<int, MyDisposableClass> _processes = new();
   volatile bool _disposed;

   void Store(int Id)
   {
        if(_disposed) { throw; } 
        var mdc= new MyDisposableClass();
       _requests.Add(Id, mdc);

        if(_disposed) { _requests.Remove(mdc); mdc.Dispose(); throw; } 
   }

   void Dispose()
   {
       if(_disposed)
       {
            return;
       }
       _disposed = true;
        
       foreach(var process in _processes)
       {
           process.Dispose();

       }
   }
}

So two new things are volatile on disposal, which ensures all threads see latest state, and additional check after adding to _requests dictionary, which eventually undoes it if object was disposed in meanwhile.

So if class was disposed after first dispose check, but before adding to dictionary, thread running Store thread will see that operation failed after adding, and will reverse it.

Answer 1

The blockingCollection essentially provides this functionality with the CompleteAdding and GetConsumingEnumerable methods. But as far as I know it does not provide provide a dictionary API.

Looking at the source it seems like this keeps a count of the number of Add methods that are currently running, so that CompleteAdding can wait for them. However, the source code for this is rather complex, and just because something is 'lock free' does not necessarily mean its better. So I would personally stick with a lock since I would be confident that it is safe.

In your example code I would be concerned about the lack of memory barriers, that could potentially allow for instructions to be reordered. As far as I understand, volatile does only guarantees that a load will be issued, not that it cannot be reordered in regards to other instructions. See Eric Lippert on reordering optimizations for details.

Another option might be a ReaderWriterLock, so that any number of threads could take a read lock, while dispose would take the writer lock.

Note that taking an uncontested lock is fairly cheap to take, in the same order of magnitude as using an interlocked instruction. So unless the store method is called very frequently I would not worry about it.

Answer 2

Your proposed solution depends on the assumption that thread executing Store() will see a modification to _disposed if it were modified after the check and add have been completed. This isn't guaranteed to be the case work on multiprocessor systems as stated here (under the first 'Note'):

On a multiprocessor system, a volatile read operation is not guaranteed to obtain the latest value written to that memory location by any processor. Similarly, a volatile write operation does not guarantee that the value written would be immediately visible to other processors.

[emphasis mine]

In other word, either check of _disposed in Store() could fail to see that another thread (on another processor) has set _disposed prior.

I think it might be viable on a single processor system but another problem:

These operations might involve memory barriers on some processors, which can affect performance.

So even in that context, it may not be 'lock-free'.

I think if you replace your volatile boolean with Interlock and the appropriate usage pattern, your overall approach is valid with one potential issue:

You could have both threads attempting to call dispose() on the same instance of MyDisposable class if Store() has added it to _processes prior to Dispose() executing but then checks _disposed after Dispose() has set _disposed to true. If calling dispose on the same instance twice from different threads is a problem, you need locks or something else to prevent that.

One thing to keep in mind as well. As JonasH alludes to, locks should be pretty fast. The performance issues around them come from contention i.e. lots of threads trying to acquire them. If you don't have high-contention, a lock-free approach may actually be slower overall.

Answer 3

Your assumption is wrong. In a multi-processor system, the state of a volatile variable after it is changed is not immediately visible to other threads. It is only visible after the OS takes some action, and for example a lock operation will take that action.

Could the compiler be changed so that changes to volatile variables are immediately visible elsewhere? Sure, no problem. Just change the compiler to protect every access to a volatile variable by a lock. Now you don’t need lock calls. But you actually have many more locks than before.

Use locks. They work. And uncontested locks are usually very fast. And contested locks - you have to wait anyway. If you are still tempted: Measure it. But keep in mind that your benchmark might have many (slow) contested locks, while in real life they are rare.

Using locks: We assume that Store and Dispose can be called at any time, when another call is running. It’s always good to hold locks for the shortest possible time.

We assume “disposed” means: Dispose has been called once, further Dispose calls have no effect, further Store calls throw exceptions. You need one lock.

Store: Create a new MyDisposeableClass. Under protection of the lock: If disposable is true then free MyDisposableClass and throw an exception, otherwise add the MyDisposableClass to requests.

Dispose: Under protection of the lock determine whether to dispose the processes (if disposed is false) and set disposed to true. Outside lock protection dispose the processes.