Thread safe wrapper around generic dictionary

Could someone give me a pointer as to how I might implement a thread safe wrapper around a genric dictionary I've written thread-safe dictionaries in C# 1.x by inheriting from the DictionaryBase but I'm a bit stumped as to how to acheive this using Generics.

TIA

Danny

Answer this question

Thread safe wrapper around generic dictionary

kingofnexus

Consider this link: http://msdn2.microsoft.com/library/xfhwa508(en-us,vs.80).aspx

Which states:
A System.Collections.Generic.Dictionary<,> can support multiple readers concurrently, as long as the collection is not modified. Even so, enumerating through a collection is intrinsically not a thread safe procedure. To guarantee thread safety during enumeration, you can lock the collection during the entire enumeration. To allow the collection to be accessed by multiple threads for reading and writing, you must implement your own synchronization.

What this means is that you either have some limited options:

1) Create a sub-class of System.Collections.Generic.Dictionary<T,U>
2) Create a utility class for modifying the collection safely
3) Creating your own thread-safe dictionary from scratch.

Lets consider these one by one:

The first option: Sub-Class
This seems a bit rediculous. Your methods might look something like the following:

using System;
using System.Collections.Generic;
using System.Text;
using System.Threading;
namespace ThreadedGenerics
{
class ThreadSafeDictionary<T,U> : Dictionary<T,U>
{
     public new void Add(T key, U value)
     {
        // Add your preferred locking mechanism here
        base.Add(key, value);
        // Add your preferred unlocking mechanism here
     }
     // TODO : Remaining Method Implementations
  }
}

or in VB.NET :

Imports System.Threading
Imports System.Collections.Generic
Public Class ThreadSafeDictionary(Of T, U)
   Inherits Dictionary(Of T, U)

   Public Shadows Sub Add(ByVal key As T, ByVal value As U)
        ' Add your preferred locking mechanism here
      MyBase.Add(key, value)
       ' Add your preferred unlocking mechanism here
   End Sub
   ' TODO : Remaining Method Implementations
End Class

This is obviously silly because we have to override all of our functionality anyway only to wrap the call in a lock. You should lock the underlying collection as well, but that's method is up to you to decide.

Additionally you have to qualify the method 'overrides' with "New" (Shadows in VB.NET) instead of override because Dictionary<,> didn't mark the functions as virtual. Lets go ahead and scratch this option off the list. It just doesn't make a lot of sense and violates OO.

The second option: Create a Utility Class
This method seems to make a bit more sense. You simply create a utility class to do all the work for you and do the wrapping. Its cleaner than the "inheritance" method. (I hesitate to call anything inheritance when you can't override the functionality but rather follow a hide-recall pattern.) This would look something like this:

using System;
using System.Collections.Generic;
using System.Text;
using System.Threading;
namespace NewWinFormsFeatures
{
   public class ThreadSafeDictionaryUtility<T,U> {
      Dictionary<T, U> dict;
      public ThreadSafeDictionaryUtility() {
      dict = new Dictionary<T,U>();
   }

    public void SafeAdd(T key, U value) {
      // Add your preferred locking mechanism here
      dict.Add(key, value);
      // Add your preferred unlocking mechanism here
    }
  // TODO : Remaining Method Implementations
  }
}

or in VB.NET

Imports System.Threading
Imports System.Collections.Generic

Friend Class ThreadSafeDictionaryUtility(Of T, U)
   Private dict As Dictionary(Of T, U)
   Public Sub New()
      Me.dict = New Dictionary(Of T, U)
   End Sub
   Public Sub SafeAdd(ByVal key As T, ByVal value As U)
      ' Add your preferred locking mechanism here
      Me.dict.Add(key, value)
      ' Add your preferred unlocking mechanism here
   End Sub
   ' TODO : Remaining Method Implementations
End Class

This should work pretty well but it isn't the most efficient way to get what you want. It does, however, prevent you from performing much implementation. You basically only provide the implementation methods you want and you simply wrap them into an object lock.

The third option: Rolling your own
This last option requires you to create your own implementation from scratch. This would require you to create a class that implemented the IDictionary<,> interface (and any others that you want to implement such as ISerializable). I wont get into details here because to do this right, you really need to do a lot of work and its already 3am here :) What I will say is that Microsoft does state that DictionaryBase is not thread safe. What it does use is the BeginCriticalRegion and EndCriticalRegion methods to let the host know that exceptions in portions of the "add" code may be damaging to other code in the AppDomain. After waking up this morning to TAG's rant (and appropriately so) I feel its neccessary to write an explaination of what those methods do and when its not appropriate. BeginCriticalSection and EndCriticalSection around the ENTIRE Dictionary.Add method would be inappropriate. Where it would be appropriate to use these functions is in this third option -- rolling your own. You want it around the very small portion of the code that does the array shifting and modifying of the underlying value. Otherwise, in the case of wrapping it around the Dictionary.Add method, something as simple as an invalid argument passed into your thread-safe class may cause the entire appdomain to shut down.

HTH.

kumarsv
Here is several public sources with technology different from yours:

http://blogs.msdn.com/bclteam/archive/2005/03/15/396335.aspx
"Calling RuntimeHelpers.PrepareConstrainedRegions() tells the CLR to treat the subsequent try-finally block as CER and eagerly prepare the code block. "

http://msdn.microsoft.com/msdnmag/issues/05/03/TokenPrivileges/default.aspx
"Before the try block is entered, a special method, RuntimeHelpers.PrepareConstrainedRegions, is invoked. This instructs the runtime to perform any operations necessary to ensure that the following catch and finally blocks will be allowed to execute. Pretty simple for such a complex piece of functionality, isn't it It gets more interesting still. In cases in which the code undertakes a nontrivial sequence of steps, making the back-out code too complex, the trick that is shown in Figure 10 can be employed."

As welll you can see that this technology has some documented diagnistics errors.
Take a look on this and compare with your source.

As well take a look on permission requests on this method. This is too strict.

I think it's better to contact somebody from BCL/CLR teams to clarify this matter (will do now). As you are an author of book - if something will be wrong in your book - this will mean a lot of people will duplicate same error.

PCZ

Sure TAG.

I typically like to help people under new topics instead of hijacking another one, but I will be more than happy to help you in this thread if you feel more comfortable asking the questions here.

Yes, you are right. I was a C++ programmer some years ago but now I'm mostly a .NET developer and have been for some time. In response to your other statement, I didn't say that the Begin/EndCriticalRegion was a preferred locking mechanism. I said that you would want to use your preferred locking mechanism. You were right, however, that I did put these in the wrong place in my original post. This has been corrected in the existing code.

The Begin/EndCriticalRegion were meant to be placed around pieces of code such as the very inner workings of an implemented dictionary or other collection class. For instance you may want to set the reliability contract as "WillNotCorruptState" but that the contrained execution may fail. So for instance, you may implement the method Add() as follows (and no, this isn't complete either):

public void Add(T key, U value) {

    // PARAMTER VALIDATIOn
            if( key == null )
                throw new ArgumentNullException(key);
            // TODO: additional parameter validation

    // BEGIN ADDING YOUR ITEM
            // TODO: LOCK
            Thread.BeginCriticalRegion();
            this.Writing = true;
            // TODO: Add to your internal collection
            this.internalCount++;
            this.Writing = false;
            Thread.EndCriticalRegion();
            // TODO: UNLOCK

    // DO CLEANUP
             // TODO: Clean up any resources as necessary
}

The idea here is that you want to create a region whereby an asynchronous failure is reported to the host. Obviously a failure could create an unreliable state (whereby your reliability contract is now unreliable). My mistake yesterday was to wrap the critical region around the entire add method. This is a mistake because we are obviously going to throw exceptions if the parameters are invalid. This would cause a mess. The correction is to move the BeginCriticalRegion to the last possible moment you can, and call it at the earliest possible moment. This DOES NOT lock the underlying collection. It would still be up to you to do your thread locking for thread safety. (most likely around the same time you are starting or ending your critical region). I haven't really decided if it makes more sense to put the lock inside or outside of the critical region. I say this because obviously if the lock fails, you would want it to throw the exception, but would you want to enforce the reliability contract over this I don't think so. That's why I put the TODOs on the outside.

If you still need help with this, or need a fully implemented function, I'll be glad to help you in my spare time if you contact me directly. However, I'm pretty busy these days. I've co-written three books on threading in .NET (C# 1.0, VB.NET 1.0 and VB.NET 1.1) and I'm studying all the new threading material to put into a fourth 2.0 version of a threading handbook. Perhaps I'll put some of your questions at the end of the book as real-life threading problems you may have.

AnandMVP
I agree, TAG. I posted this last night after we finished moving and I was in a bit of a hurry. The problem I had was that I created my "third" option first and worked backwards to the other two options. In my "roll your own" exercize, I actually implemented the BeginCriticalRegion and EndCriticalRegion around the bits that modified the underlying dictionary but it still also required a thread lock. I did mention in my post that you should Lock your collection and stated that you should use your preferred method. I went ahead and modified the sample code above to put that "use preferred locking mechanism" comments in place.
Makler
Sorry for misunderstanding.

"Begin/EndCriticalRegion provide the ability to block of regions of code that will unload the appdomain to automatically clean up any locks on your code. The purpose of these two functions is entirely different. "

I think most of users will not be willing their AppDomain to unload in case of OutOfMemory or Thread.Abort or unhanded exception failures in one of their threads while adding elements to some basic collection.

Thanks for clarifing everything.
Peterleex
Can you tell us (if this is not a secret) that What kind of applications you are developing that requere to use Begin/EndCriticalRegion

I think in the past you were a C/C++ programmer as was using EnterCriticalSection but Thread.BeginCriticalRegion has different meaning contrast sounds similar.

More - thouse methods are new to .NET 2.0 and I do not think they are your "preferred locking mechanism".
mshafiq
Tobin, thanks for the feedback. In the absence of any other guidance over the last month I implemented the first option, the 'sub'-class. Not elegant but it works. I am very much a threading newbie so to be honest the discussions you've been having with Tag have largely gone over my head.

All I'm doing in my class is using a lock {this.SyncRoot){} statement around methods that modify/access the dictionary. Where SyncRoot is a private object. The application this is for is low volume so efficiency is not that important, but concurrency has enabled me to greatly speed up some key functionality which is proving a big bonus to my users.

If you have time, I'm interested to see how you might ideally implement a thread safe dictionary but as I said I do have a solution so I'm not desperate.

Thanks again for your feedback.

Danny
Litey

I think you are failing to understand that I've already contacted three members of the BCL/CLR team to discuss this.

PrepareConstrainedRegions is an entirely different animal. This method guarantees that your try/catch will execute and allows you to use the finally block to do any backing out code that you need to -- such as releasing thread locks.

Begin/EndCriticalRegion provide the ability to block of regions of code that will unload the appdomain to automatically clean up any locks on your code. The purpose of these two functions is entirely different.

PrepareConstrainedRegions could also be helful and is just "another" way to look at and handle the problem. We can go around all day on these topics and you can continue to misdirect and redirect the conversation however you feel, but the point is, that my original post to the caller is correct.

I sincerely thank you for your interest in this topic and the back and forth will help better my book for certain. You are free to contact whomever you want and point them to this thread. Three members have already talked to me about this issue. I'm really not sure how many more need to look at it before you'll consider it right. That's entirely up to you though.

I'm also confused as to why you continue to argue the subject. Your suggestions are valid and I've never disputed that. They are simply a different way of handling the situation. The original poster, at this point, is probably more confused than helped by this entire conversation and for this I am extremely sorry.

To the orginal poster, if you want a working example of a thread safe dictionary, I still hold my offer to provide a working (but most likely only partially implemented) sample and further guidance if necessary.
the user
The original intent of this hijacked thread was to provide locking help on the Dictionary<,> class. I provided three ways, only one of which describes using the Begin/EndCriticalRegion. Discussion beyond answering this guys question has become truly self-serving. These items can and should be used in some cases (such as my third option).

One member of the CLR team informed me that you should "use BeginCriticalRegion and EndCriticalRegion to inform the runtime that your code is taking a lock outside of a normal synchronization primitive."

Paraphrased, he also said that within the hashtable, they are attempting to take something approximating a lock without using a real synchronization primitive. If a thread abort exception occurs while modifying the hash table, the CLR needs to escalate that thread abort to an appdomain unload. This is done by calling Begin/EndCriticalRegion. These methods control the critical region count on your threads to escalate thread aborts. These methods also affect memmory allocation in the CLR. Obviously within a critical region, it is imperative that memory allocations succeed so the CLR works harder to clean up memory and "satisy" the memory request. There is no guarantee that the request for memory can be satisified, but obviously a failure to do so would unload the appdomain.

Another CLR team member gave me another example:

If you’re doing a tight spin lock with a CEX, for example, you should definitely mark critical regions yourself, e.g.:

try{
    Thread.BeginCriticalRegion();
    while (Interlocked.CompareExchange(lock, 0, 1) == 0);
}
finally {
    Thread.EndCriticalRegion();
}

Whatever your beef is with these two methods, they are definitely public and useful when creating your own thread-safe collection. They obviously dont' provide the thread safety themselves, but they do serve their purpose as I've described.
Fallen Ghost
The fact that you have found BeginCriticalRegion() inside Hashtable does not mean that this method requered to be used by end-user or custom library writer.

If you will compare Hashtable versus Dictionary<K,V> you will see they have threading contract - and Hashtable must be wrapped into Hashtable.Synchronized wrapper to make it truly safe.
It was original question - answer is to simply do lock(underlaying collection) {} for all methods.

If you realy need CER = then you need to place your critical code in finally block (and possibly use RuntimeHelpers.PrepareConstrainedRegions from System.Runtime.CompilerServices)
As well if it was your concert - it was nice to mark your method with reliability attributes (or at least to tell this) to make it possible call it from others critical blocks (if possible; for Add() this is impossible - as there are memory allocation can be requered to increase hashtable size). You did not this.

P.S> Copy-paste from decompiled source is evil.
andreskruse
MCSD,

Have you read documentation for Thread.BeginCriticalRegion()
This has nothing to thread safety but to AppDomain stability in case if failures.

I think correct code is Monitor.Enter / Exit with mandatory try / finally or simply a lock() statement.
Thread safe wrapper around generic dictionary

Answer this question