How to lock dictionary then safely hand off lock to a value in the dictionary?

Question

I am trying to find a safe approach for synchronizing access to a nested dictionary where operations on the outer dictionary lock any manipulation to the entire collection. However, once the inner dictionary is retrieved I would like to release the outer lock and only prevent threads from manipulating the inner dictionary.

It is trivial to use the lock keyword for this once the inner dictionary exists within the outer dictionary, however, I am struggling to find a safe approach for adding and populating the inner dictionary without introducing a race condition. Assume "Populating" the inner dictionary will be an expensive operation. This is why doing it under lock for the outer dictionary is not an option. Other threads must have access to the outer dictionary to perform operations on OTHER inner dictionaries while "populate" is executed against the new inner dictionary.

I have included examples below which better illustrate my question.

1. A trivial approach which I believe introduces a race condition
2. An approach I believe will work, however, can result in unnecessarily populating multiple inner dictionaries. This will only end up using the first inner dictionary which wins the race.
3. An approach I believe will work, however, it is unfamiliar territory. Even with extensive testing I would be concerned that my lack of experience using the C#'s Monitor object could lead to unexpected consequences.

Example 1: What I believe to be an unsafe approach to my problem. However, this is how I traditionally synchronization. I would prefer to use this approach, however I do not know of a way to use the lock keyword and achieve the behavior I need.

public void SyncronizationExample1(Dictionary<TKey, Dictionary<TKey2, ReferenceTypedValues>> outerDictionary, TKey newKey)
{
    Dictionary<TKey2, ReferenceTypedValues> innerDictionary = null;

    lock (outerDictionary)
    {
        // No need to add a new innerDictionary, it already exists
        if (outerDictionary.ContainsKey(newKey))
        {
            return;
        }

        innerDictionary = new Dictionary<TKey2, ReferenceTypedValues>();
        outerDictionary.Add(newKey, innerDictionary);
    }

    // I want to allow other threads to have access to outerDictionary
    // However, I don't want other threads working against THIS innerDictionary
    lock (innerDictionary)
    {
        // Here lies my concern with this approach. Another thread could have
        //   taken the lock for innerDictionary. Doing this all under the lock
        //   for outerDictionary would be safe but would prevent access to other
        //   inner dictionaries while expensive operations are performed only
        //   pertaining to THIS innerDictionary
        this.PopulateInnerDictionary(innerDictionary);
    }
}

Example 2: An approach using lock that does not encounter the issues portrayed in Example 1. However, not ideal as unnecessary computation may occur if multiple threads attempt the operation at the same time. Note that this approach could be modified to lock against a global "Populate" lock, however, that would prevent multiple threads from concurrently populating different innerDictionaries.

public void SyncronizationExample3(Dictionary<TKey, Dictionary<TKey2, ReferenceTypedValues>> outerDictionary, TKey newKey)
{
    lock (outerDictionary)
    {
        if (outerDictionary.ContainsKey(newKey))
        {
            // No need to add a new innerDictionary, it already exists
            return;
        }
    }

    var innerDictionary = new Dictionary<TKey2, ReferenceTypedValues>();

    // Expensive operation - if called by multiple threads at the same time
    //   multiple innerDictionaries will be populated but only the one to win
    //   the race will be utilized.  
    this.PopulateInnerDictionary(innerDictionary);

    lock (this.outerDictionary)
    {
        if (!outerDictionary.ContainsKey(newKey))
        {
            // If another thread won the race this newKey would be in outerDictionary
            // The innerDictionary we just populated is redundant
            outerDictionary.Add(newKey, innerDictionary);
        }
    }
} 

Example 3: What I believe to be a solution to the potential synchronization issues demonstrated in Example 1. However, I am unfamiliar with using the Monitor pattern and would greatly appreciate feedback.

public void SyncronizationExample3(Dictionary<TKey, Dictionary<TKey2, ReferenceTypedValues>> outerDictionary, TKey newKey)
{
    Dictionary<TKey2, ReferenceTypedValues> innerDictionary = null;
    bool aquiredLockForOuterDictionary = false;
    bool aquiredLockForInnerDictionary = false;

    try
    {
        Monitor.Enter(outerDictionary, ref aquiredLockForOuterDictionary);

        if (outerDictionary.Contains(newKey)
        {
            // No need to add a new innerDictionary, it already exists
            return;
        }

        innerDictionary = new Dictionary<TKey2, ReferenceTypedValues>();
        outerDictionary.Add(newKey, innerDictionary);

        // This is where I "handoff" the lock to innerDictionary to alleviate my concern 
        //   in Example 1 where another thread could steal the innerDictionary lock 
        Monitor.Enter(innerDictionary, ref aquiredLockForInnerDictionary);
    }
    finally
    {
        // I read that this bool pattern was preferred for .net 4+, 
        //   however I am unsure if this is the best practice
        if (aquiredLockForOuterDictionary)
        {
            Monitor.Exit(dictionary);
        }
    }
    try
    {
        if (!aquiredLockForInnerDictionary)
        {
            // An exception must have occurred prior to or during the acquisition
            //   of this lock. Not sure how I'd handle this yet but
            //   I'm pretty shit out of luck.
            return;
        }

        // Here I would perform an expensive operation against the innerDictionary
        //   I do not want to lock consumers form accessing other innerDictionaries 
        //   while this computation is done. 
        this.PopulateInnerDictionary(innerDictionary);
    }
    finally
    {
        // I need to check this here incase an exception in the first  
        //   try finally prevented this from being acquired 
        if (aquiredLockForInnerDictionary)
        {
            Monitor.Exit(innerDictionary);
        }
    }
}

Answer 1

Seems like you're overthinking it. The only question I have is, do you have a reliable way of knowing whether an inner dictionary instance has been populated? I would assume that a non-zero value for the Count property would suffice, no?

With that assumption, you can do this:

public Dictionary<TKey2, ReferenceTypedValues> SyncronizationExample1(Dictionary<TKey, Dictionary<TKey2, ReferenceTypedValues>> outerDictionary, TKey newKey)
{
    Dictionary<TKey2, ReferenceTypedValues> innerDictionary = null;

    lock (outerDictionary)
    {
        // No need to add a new innerDictionary if it already exists
        if (!outerDictionary.TryGetValue(newKey, out innerDictionary))
        {
            innerDictionary = new Dictionary<TKey2, ReferenceTypedValues>();
            outerDictionary.Add(newKey, innerDictionary);
        }    
    }

    // Found the inner dictionary, but might be racing with another thread
    // that also just found it. Lock and check whether it needs populating
    lock (innerDictionary)
    {
        if (innerDictionary.Count == 0)
        {
            this.PopulateInnerDictionary(innerDictionary);
        }
    }

    return innerDictionary;
}

Notes:

• It is not a good idea to use the object itself as the lock object, because you run the risk of some other code having the same bad idea and deadlocking with that code. Instead, store a composite value (e.g. Tuple<object, Dictionary<...>>, a custom named struct, etc.) that contains both the object to use for locking, and the inner dictionary itself. (And of course, have a single dedicated object stored in a field for locking the single outer dictionary.)
• Your question doesn't describe how these objects are used. I'm guessing once populated, they are read-only? If so, the above should be fine, but you should use the ReadOnlyDictionary class to enforce that. Otherwise, you of course need to add synchronization for that too.
• Even assuming they are read-only, your original code doesn't actually return the inner dictionary reference. I've modified the example slightly so that it does. It must. You can't have code looking for the reference without going through the checks in the code above. Best case scenario, it won't be fully populated yet, worst case scenario you'll crash due to trying to access the data structure while it's in an inconsistent state. You could by convention require that callers always call the above method before retrieving the reference value, but if they are going to do that, you might as well make it convenient and return the value from the method itself.