Channels ▼
RSS

Security

Concurrent Programming with Chain Locking


ChainLockerGenerator: A Python Script to Generate a Customized ChainLocker

ChainLocker[Ex] is generic, but does require some customization in regard to the depth of the hierarchy it needs to support and to address whether you want ChainLocker (no shared state) or ChainLockerEx (with shared state). You may opt create one file with many variations or just the one particular configuration you need. I decided to create a little Python program that can generate any combination of ChainLockers based on a few text templates. The added benefit is that if I decide to add a new feature or modify the design, I don't have to go and edit all the instances manually. I can edit just the templates and regenerate everything. For example, if I decide that the first level lock should be ReaderWriterLockSlim instead of the standard Monitor, I can add this option to the script and generate any combination of locks for my ChainLocker instances. The code and templates for ChainLockerGenerator are available on GitHub. Here is the usage message that explains how to use it:

"""
Usage: python ChainLockerGenerator.py <namespace> <N> [kind]

namespace - The C# namespace of your project
N - the maximal number of stages to generate
Kind - one of standard, extended, both

ChainLockerGenerator generates a C# file that contains multiple generic ChainLocker classes.
If you don't know what that is you have no business running this script :-)
There are two variants of chain lockers: standard and extended. The extended one provides
a shared state that is not locked to the stage operations.

Each generated instance has a certain number of stages that are locked. All instances 
from 2 to N will be generated. For example, if you specified N=4 then 3 instances will be
generated with 2, 3 and 4 stages.

If you specified Kind=standard (or omitted it) only the standard instances will be generated.
If you specified Kind=extended only the extended instances will be generated.
If you specified both then you get both standard and extended. Everything is printed out
to standard output as a single C# module with the namespace you chose. The standard instances
are named ChainLocker<T1,...,Tn>. The extended instances are named ChainLockerEx<T, T1,...,Tn>
"""

Implementing with ChainLocker

Let's implement a few operations of the online school with ChainLocker and discuss it from a concurrent programming point of view. Before I go on, remember that the purpose of this code is to demonstrate how to use ChainLocker. It is not industrial strength and is not part of any real-world system.

Listing Two contains the abstract object model of the school's central scheduling service. It consists of an ILecture interface that contains classes, an IClass interface that contains students, a Student class with and associated ID and the IClass it attends, and a Status enum shared by lectures and classes (LIVE or CANCELLED).

Listing Two

using System.Collections.Generic;

namespace LectureManager
{
    public enum Status
    {
        LIVE,
        CANCELLED,
        REMOVED
    }

    public interface ILecture
    {
        int ID { get; set; }
        Status Status { get; set; }
        IEnumerable<IClass> Classes { get; }
        
        IClass FindAvailableClass();
        IClass LookupClass(int classId);
        void RemoveClass(int classId);
        void AddClass(IClass theClass);
    }

    public interface IClass
    {
        int LectureID { get; set; }
        int ID { get; set; }
        Status Status { get; set; }
        IEnumerable<int> Students { get; }

        void AddStudent(int studentId);
        void ExpelStudent(int studentId);
    }

    public class Student
    {
        public int ID { get; set; }
        public int ClassID { get; set; } // attending class
    }

    public class Stats
    {
        public int TotalClasses;
        public int TotalStudents;
    }
}

Removing a Student

A student may be removed from a class for one of several reasons: The lecturer decides to expel the student, the entire class is cancelled, or the student joins a new lecture/class. The service doesn't really care. From concurrency point of view, it's important to lock the class that the student is removed from because the class manages the student list. If multiple students need to be removed from the same class (say, if the class is cancelled), it makes sense to lock the class once and remove all the students instead of locking out each student. The IClass interface has an ExpelStudent() that handles all the mundane details like removing the student from the student list and notifying other interested parties. This method can be called by several other methods that are responsible for locking (via SchoolLocker, of course) at the right granularity. Here is the code for the external ExpelStudent() method. Notice its concision:

public void ExpelStudent(int lectureId, int classId, int studentId)
{
    new SchoolLocker().Do(
        _lectures,
        lectures => LookupLecture(lectures, lectureId),
        lecture => lecture.LookupClass(classId),
        theClass => theClass.ExpelStudent(studentId));
}

The first delegate uses the LookupLecture() method to look for the proper lecture, locking the entire lectures tree just for the brief moment it takes to look up the class. The second delegate finds the proper class (again locking the lecture just for the brief moment needed to find the class). Finally, the third delegate actually expels the student.

Canceling a Class

Canceling a class is a little more complicated. The service needs to expel all the students and then get rid of the class itself (remove it from the class list managed by the lecture). This means that it needs to lock the lecture when removing the class. One way to do it is to lock the lecture, expel all the students, and finally remove the class. But that means locking the lecture for a relatively long time, which will block all threads that may want to access other classes. Another approach is to find the class, release the lecture, and then set the class status to CANCELLED first (thus unlocking the lecture), and then proceed to expel all the students. Other threads may work with other classes of this lecture. Once all the students have been expelled, the schedule service can start a new SchoolLocker instance and (in its Do() method) remove the class. Note that once the first SchoolLocker.Do() method completes, the cancelled class will be unlocked, and other threads may try to access the class before it is removed. This is OK because its status is CANCELLED, so it will not be available to other threads.

        public void CancelClass(int lectureId, int classId)
        {
            // Set the class status to CANCELLED
            new SchoolLocker().Do(
                _lectures,
                lectures => LookupLecture(lectures, lectureId),
                lecture => lecture.LookupClass(classId),
                theClass =>
                {
                    theClass.Status = Status.CANCELLED;
                    foreach (var studentId in theClass.Students)
                    {
                        theClass.ExpelStudent(studentId);
                    }
                });

            // Remove the cancelled class from its lecture 
            new SchoolLocker().Do(
                _lectures,
                lectures => LookupLecture(lectures, lectureId),
                lecture =>
                    {
                        lecture.RemoveClass(classId);
                        return null;
                    },
                null);
        }

Canceling a Lecture

Canceling a lecture is very much like canceling a class except that in order to remove the lecture, we need to cancel all the classes properly and expel all the students because there may be other parts of the system that depend on orderly cancellation. We must ensure that once the lecture is cancelled, each of its classes is locked directly (to avoid conflicts with other threads that might have started working on a class before the lecture was cancelled) and all its students are expelled. Finally, the lecture is removed from the lectures tree (with a simple lock):

        public void CancelLecture(int lectureId)
        {
            ILecture cancelledLecture = null;

            // Set the lecture status to CANCELLED
            new SchoolLocker().Do(
                _lectures,
                lectures => LookupLecture(lectures, lectureId),
                lecture =>
                {
                    lecture.Status = Status.CANCELLED;
                    cancelledLecture = lecture;
                    return null;
                },
                null);

            // Now cancel all the classes and expel all their students
            foreach (var theClass in cancelledLecture.Classes)
            {
                lock (theClass)
                {
                    theClass.Status = Status.CANCELLED;         
                }

                foreach (var studentId in theClass.Students)
                {
                    theClass.ExpelStudent(studentId);
                }
            }

            // Finally, remove the lecture from the lectures dictionary
            lock (_lectures)
            {
                _lectures.Remove(lectureId);
            }
        }

Getting Statistics

Getting statistics out of a highly multithreaded service involves trade-offs. You can lock the whole system and accumulate your statistics: This will give you an exact snapshot, but will freeze your system for the duration of statistics collection. Alternatively, you can iterate over your data structures without locking and know that you collect data from a system in flux, and by the time you finish, some of the statistics will already be stale. For example, suppose you just want to count how many students attend classes at a given moment. If you just iterate over all the classes and count their students without locking, you may count students that were expelled by the time you finish your count, but also include students that attended a class after you started your count. You may even count the same student twice if that individual switched classes while you were counting. There are other approaches, such as copying your entire state and calculating your statistics off the copy. That makes sense if your data structures don't take much space, but is inefficient if your statistics computations are sophisticated and take a relatively long time to compute.

Here, I implement the simplest approach of just locking everything and counting classes and students. There is no need for SchoolLocker in this scenario because we lock the entire lectures tree, so a simple lock will suffice:

    public Stats GetStatistics()
    {
        var stats = new Stats();
        
        lock (_lectures)
        {
            foreach (var lecture in _lectures.Values)
            {
                foreach (var theClass in lecture.Classes)
                {
                    stats.TotalClasses += 1;
                    stats.TotalStudents += theClass.Students.Count();
                }
            }                
        }

        return stats;
    }

Conclusion

Concurrent programming will become ubiquitous as the number of cores continues to increase and more threads are expected to execute in parallel. To take advantage of all these cores, you'll have to make sure your code is thread-safe and doesn't use too coarse a locking strategy. The ChainLocker construct can assist you by providing an abstraction of safe fine-grained locking for hierarchical data structures that hides most of the gnarly locking details.


Gigi Sayfan specializes in cross-platform object-oriented programming in C/C++/ C#/Python/Java with emphasis on large-scale distributed systems, and is a long-time contributor to Dr. Dobb's.

More on Coarse-Grained versus Fine-Grained Parallelism

Will Parallel Code Ever Be Embraced?

Parallel Evolution, Not Revolution


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