Channels ▼
RSS

.NET

Concurrent Programming with Chain Locking


Another important issue is making sure currently held locks are always released even if an exception is thrown. ChainLocker does it for you by managing a list of held locks and wrapping the processing in try-finally block, where all held locks are released in the finally block. The hand-over-hand locking strategy of ChainLocker means that up to two locks may be held at any point in the processing. Here is what it looks like:

    if (state0 == null)
    {
        throw new Exception("state0 can't be null");
    }

    var takenLocks = Enumerable.Repeat(false, 3).ToArray();
    var states = Enumerable.Repeat<object>(null, 3).ToArray();
    states[0] = state0;
    try
    {
        ...
    }
    finally
    {
        // Release still held locks (If an exception was thrown)
        for (int i = 0; i < 3; ++i)
        {
            if (states[i] != null && takenLocks[i])
            {
                Monitor.Exit(states[i]);
            }
        }
    }

(Please ignore the hard-coded number 3 in the code: This is generated code, so the DRY principle is not violated. When I write code manually, I don't hard-code the constant; but in generated code, it is acceptable and saves space.)

In the aforementioned code, the takenLocks variable is a Boolean flag array initialized to [false, false, false]. This means that, at this point, no lock is taken. The states variable is an array of objects that represent the objects that are locked/unlocked during processing. During normal processing, the locks will be released by ChainLocker in the hand-over-hand fashion; but if an exception is thrown, the finally block will unlock any remaining state objects that are still locked. It is crucial that the order in which the locks are taken by all threads is identical to avoid deadlocks.

Let's look at the actual processing done by ChainLocker inside the try block:

    // Lock state0
    Monitor.Enter(states[0], ref takenLocks[0]);
    // Execute stage0
    states[1] = stage0((T0)(states[0]));
    // Bail out if returned null
    if (states[1] == null)
    {
        return;
    }

    // Lock state1
    Monitor.Enter(states[1], ref takenLocks[1]);
    // Execute stage1
    states[2] = stage1((T1)(states[1]));
    // Bail out if returned null
    if (states[2] == null)
    {
        return;
    }

    // Lock state2
    Monitor.Enter(states[2], ref takenLocks[2]);
    // Release the state1 lock so other threads can work on it
    Monitor.Exit(states[1]);
    takenLocks[1] = false;
    // Execute stage2
    stage2((T2)(states[2]));

The processing for each stage is similar (identical except that the last stage doesn't do an early bail out check). In each stage x, the corresponding state object states[x] is locked and the Boolean flag takenLocks[x] is set by Monitor.Enter(). Then, the stage x itself is executed (casting the state object to its actual Tx type), and the result is stored in states[x+1]. If the result is null, Do() simply returns (the finally block will clear the held lock).

Concrete ChainLocker Subclass

ChainLocker is great, but if you misuse it, you can enter a deadlock. Consider the following two methods using a two-level deep ChainLocker:

void Foo(A a)
{
    ChainLocker<A, B>.Do(a, () => { return a.LookupChild() }, () => { ... });
}


void Bar(B b)
{
    ChainLocker<B, A>.Do(b, () => { return b.Parent() }, () => { ... });
}

Assume the hierarchical data structure is "A contains a list of B objects." The Foo() method works in the order A -> B. But the Bar() method works in the order B -> A. If Foo() and Bar() are called from two separate threads, you may easily get into a deadlock where each method is trying to lock an object currently locked by the other thread. The generic ChainLocker will not protect you from this situation; but a trivial subclass/specialization can do it. Consider the following subclass for the MS:

public class SchoolLocker : ChainLocker<IDictionary<int, Lecture>, Lecture, Class>
{
}

Using SchoolLocker is less verbose than using the generic ChainLocker because you don't have to specify the parameterized types in each call and, of course, it guarantees that the locks are taken in the correct order.

public AttendLecture(int lectureId, int studentId)
{
    SchoolLocker.Do(
        _lectures,
        lectures =>
        {
            Lecture lecture = null;
            lectures.TryGetValue(lectureId, lecture);
            return lecture;
        },
        lecture => lecture.FindAvailableClass(),
        availableClass => availableClass.AddStudent(studentId));
}

Sharing State and Stage Isolation

In the AttendLecture() method shown in the last code snippet, I used the SchoolLocker subclass. It ensures only that the locks ChainLocker takes itself are taken in the right order. However, each stage delegate has access to its outer scope, and because it is defined inside a method, it also has access to the entire object state (including the root). This is very convenient if you want all stages to have access to some shared state or object, such as a logger. But it also allows the stage delegates to ignore all the nice machinations of the ChainLocker and potentially wreak havoc on the system. One way to minimize this risk is to define the stage delegates as static methods instead of in-place anonymous methods. This way, each delegate will have access only to the state variable passed to it by ChainLocker and to static variables of the hosting class. If you don't want to expose even static variables, you can define the delegates in a separate class altogether. Here is what it looks like:

private static Lecture LookupLecture(IDictionary<int, Lecture> lectures, int lectureId)
{
    Lecture lecture = null;
    lectures.TryGetValue(lectureId,  out lecture);
    return lecture;
}

private static Class FindAvailableClass(Lecture lecture)
{
    return lecture.FindAvailableClass();
}

private static void AddStudent(Class availableClass, int studentId)
{
    availableClass.AddStudent(studentId);
}


public void AttendLecture(int lectureId, int studentId)
{
    new SchoolLocker().Do(
        _lectures,
        lectures => LookupLecture(lectures, lectureId),
        lecture => FindAvailableClass(lecture),
        availableClass => AddStudent(studentId));            
}

Another benefit of this approach is that stages that are used by several methods (like LookupLecture()) can be reused. What about sharing something between all stages (like a logger) without exposing the entire outer scope? There is a special version of ChainLocker that accommodates this scenario. It's called StateLockerEx and has an extra argument called shared that is passed to each stage function. Here is ChainLockerEx for a two-level deep hierarchy:

    public class ChainLockerEx<T, T0, T1>
        where T0 : class
        where T1 : class
    {
        T _sharedState;
        public ChainLockerEx(T sharedState)
        {
            _sharedState = sharedState;
        }

        public void Do(T0 state0,
                       Func<T, T0, T1> stage0,
                       Action<T, T1> stage1)
        {
            if (state0 == null)
            {
                throw new Exception("state0 can't be null");
            }

            var takenLocks = Enumerable.Repeat(false, 2).ToArray();
            var states = Enumerable.Repeat<object>(null, 2).ToArray();
            states[0] = state0;
            try
            {
                // Lock state0
                Monitor.Enter(states[0], ref takenLocks[0]);
                // Execute stage0
                states[1] = stage0(_sharedState, (T0)(states[0]));
                // Bail out if returned null
                if (states[1] == null)
                {
                    return;
                }

                // Lock state1
                Monitor.Enter(states[1], ref takenLocks[1]);
                // Release the state1 lock so other threads can work on it
                Monitor.Exit(states[0]);
                takenLocks[0] = false;
                // Execute stage1
                stage1(_sharedState, (T1)(states[1]));
            }
            finally
            {
                // Release still held locks (If an exception was thrown)
                for (int i = 0; i < 2; ++i)
                {
                    if (states[i] != null && takenLocks[i])
                    {
                        Monitor.Exit(states[i]);
                    }
                }
            }
        }
    }


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video