Multithreaded programming in C++: A reusable pattern for queuing background tasks

To accomplish this task, I used the rule of dependency to define two patterns for thread management, the first of which I describe below. These patterns have since found use, both together and separately, in other projects. In this installment, I begin a series on threading and synchronization in which I invite you to retrace with me the creation of a multithreaded application. We will construct a C++ program titled MultiCalc, which calculates multiple cases in the background. We will use Microsoft Visual C++ 6.0 and the Microsoft Foundation Classes (MFC). We will also employ Microsoft's implementation of the Standard Template Library (STL) for some container classes. This pattern, however, applies well to any object-oriented language that supports threading and synchronization.

The structure of the data
We begin planning the multithreaded application by defining the objects in the system. In MultiCalc we have several cases, represented by MFC documents, containing parameters (inputs to calculations) and results (outputs from calculations). We also have several windows, represented by MFC views, that provide the facility for parameter entry and display the results. The resulting structure appears in the following UML diagram:

The rule of dependency
We now describe the dependency between objects. The rule of dependency controls the flow of information through the system. It defines the relationships between dependent attributes and the precedents upon which they depend. A precedent is defined as any piece of information that is referenced when a dependent attribute is updated. All precedents must be up-to-date and available when the dependent needs them. Furthermore, when a precedent changes, the dependent becomes out-of-date.

Dependency is not a new idea. We think about dependency when designing even the simplest algorithm. If z depends upon y and y depends upon x, we write the algorithm such that it calculates x, then y, then z. In a single-threaded application, the order of execution is deterministic, so we hardly give dependency a second thought.

When writing a multithreaded application, however, it is difficult to enforce that one thing happens before another. It is difficult to say for certain that x is calculated before y if those calculations take place in different threads. Thus, we must carefully analyze dependency relationships among our objects to determine how the threads are to interact.

In MultiCalc, the results of each document depend upon that document's parameters. Furthermore, the state of each view's controls depends upon the parameters and results of the associated document. We draw these dependency relationships in a UML object instance diagram as dotted arrows, from dependent to precedent:

The rule of dependency reveals a problem with this diagram. Since the results depend directly upon the parameters, the results become out-of-date when the user changes the parameters. MultiCalc must allow the user to modify the parameters while the results are being calculated, but this would invalidate the calculation currently taking place. We must break the dependency chain to prevent invalidation.

The solution I choose is to copy all of the parameters to another object, the task object, just prior to calculation. The results of the calculation then depend upon the copy of the parameters, not upon the originals. The user can change the original parameters without invalidating the calculation results. The modified UML object instance diagram appears below:

Queuing the tasks
With the dependency problem averted, we then focus on queuing tasks for background calculation. In MultiCalc, a queue serves as a communication and synchronization mechanism between two threads. One thread pushes objects to the back of a queue, while the other pulls them from the front.

The main thread, also known as the user-interface thread, pushes task objects to a queue to request background calculation. The worker thread, or the background thread, pulls task objects from this queue to process them.

But we are not finished. When tasks are completed, the results must find their way back to the appropriate document. Because the user is still working with the document, and because the view needs to display those results, it makes sense that the document is accessed only within the main thread. Therefore, to get the results back into the main thread, the worker thread pushes the completed task object to the back of a second queue, the results queue. The main thread periodically checks the results queue and pulls completed tasks from the front, thus finishing the round-trip. The following UML structure diagram shows the entire system:

In the next installment, we will implement the system in C++. We will explore some of the threading and synchronization options available to us, and decide on the most appropriate set of tools for the job.