Since the appearance of multi-processor computers and multi-tasking operating systems, programmers have been interested in concurrent programming-- doing several tasks in parallel, then putting the pieces together at the end to produce a final answer. Even on single-processor computers concurrent programs offer advantages, because much of the scheduling and control information that would be needed in a traditional program is managed by the underlying operating system, instead; so programmers only need to concentrate on describing the independent sub-tasks that must be performed.

Multi-Threading

There are problems with concurrency, however. The biggest problem is that if each task is to be performed by a separate program, all running on the same single-processor computer, then we will have to add the time it takes the operating system to switch the processor from one program to another to the overall processing time. This time can be considerable, because when control of the CPU is switched from program A to program B, then some or all of B's data and control information may need to be restored from spacious, low-speed memories to cramped, high-speed memories, while some or all of A's data and control information may need to be saved from the high-speed memories back to the low-speed memories.

Many operating systems solve this problem for us. Instead of implementing a concurrent algorithm as a loose collection of collaborating programs, programmers can implement it as a single master program, which "fathers" several "child programs" that perform the various sub-tasks in parallel, then report their results back to the master. Child programs are called threads, or light-weight processes.

What makes this idea an improvement is that a thread isn't a full fledged program with its own data and control information. Instead, the thread simply uses the data and control information of its parent program (or most of it, anyway). This means switching the CPU from one thread to another is relatively efficient.

Implementing and Scheduling Threads

An object-oriented operating system might represent each thread as an object that "controls" other objects representing system resources such as memory, processors, or I/O devices. In fact processes, the objects that represent ordinary programs, are simply threads that control additional resources:

In a simplified operating system, a thread is always in one of at least four states: Ready (waiting for the CPU), Running (using the CPU), Blocked (waiting for input), or Terminated. We can represent these states, the transitions between them, and the actions that cause transition to occur using a state diagram:

It is the job of an operating system component called the scheduler to perform the switch and preempt actions. Switching means switching control of the processor from the thread that currently controls the processor to the next thread in the ready queue. All threads in the ready queue are in the Ready state, because they are ready to use the processor. A thread that controls a processor is in the Running state, because it uses its processor to run.

What makes a running thread give up control of a processor? When the task performed by a thread is complete, then the thread stops. Also, the operating system will require a running thread to release its processor and enter a Blocked state while it waits for input to arrive. Some operating systems will even preempt a thread that attempts to starve its relatives by consuming large slices of processor time without releasing it to the others. Finally, cooperative threads voluntarily release processor control on occasion, either by auto-transitioning back to their Ready state, or by auto-transitioning to their Blocked state for a specific amount of time (sleeping).

Inter-Thread Communication

Naturally, the more interesting concurrent programs are the ones where the threads collaborate in interesting ways. Obviously, meaningful collaboration requires communication. But how can threads communicate? Broadly speaking, there are two techniques: message passing and shared memory.

In some cases a parent thread might provide message brokering services for its children. Essentially, the parent thread acts like a post office: a child thread gives the parent a message, which the parent eventually forwards to the recipient child thread. Of course this is very similar to the job of the message pump of a Windows application.

While using the parent as a message broker promotes decoupling among the child threads, it introduces two inefficiencies. First, all messages must pass through a middle man-the broker. Second, there will have to be some limit on the amount of information that can be sent in a single message.

All child threads can easily access their parent thread's global data structures. This means they can communicate directly through these data structures: if thread A changes the engine design on a global CAD/CAM model of a car, then thread B will be able to see this change, and therefore will take it into account as it estimates the total cost of the car.

In effect, global data structures act like abstract mailboxes. Thread A places a "message" for thread B in mailbox M. Later, thread B removes the message and reads it. No middle man is required, and messages can hold as much information as we like. But the downside is this: what happens if thread B checks mailbox M before thread A posts the message? In this case B may not get the message, which may result in an error.

Sometimes it's difficult for programmers to cope with problems like this, because they are accustomed to being able to predict the execution order of a sequence of instructions. While the execution order of instructions being executed by a single thread is predictable, the execution order of instructions being executed by different threads isn't.

Once again the operating system comes to our rescue, this time by supplying synchronization mechanisms: objects that work like latches and locks. If we equip mailbox M with a locked latch, L, then if Thread B doesn't have a "key", it must wait next to the mailbox for the latch to be unlocked. Of course this will only happen after thread A, which does have a key, puts its message inside M.

Active Objects

Combining multi-threading and object-orientation produces the powerful idea of an active object: an object that "owns" a thread of control. Until now, all of the objects we have dealt with have been passive. A passive object does nothing unless a client calls one of its member functions. When the member function terminates, the passive object goes back to doing nothing. But an active object doesn't need to wait for a client to call one of its member functions. Instead, it can use its thread to execute a control loop that perpetually searches for work to be done:

Active objects are particularly useful in simulations of systems containing autonomous, active elements.

The Master-Slave Design Pattern

Designing a program as a society of active objects can lead to chaos. To avoid this fate, most multithreaded applications instantiate some variant of the Master-Slave design pattern:

In the Master-Slave pattern active master object creates many active slave objects. Each slave object retains a pointer back to its master:

Each slave performs some task, then reports its result back to the master. The master accumulates results and produces a final result.

Multi-Threading in Windows

Like a window or a file, a thread is a system resource that must be created, managed, and destroyed by the operating system. We have seen that like most operating systems, Windows uses the Wrapper-Body design pattern to protect these resources. For example, an application-level C++ object representing a window is merely a wrapper that encapsulates a handle or identification number of a body, which in this case is a system-level C "object" that is the actual window data structure. Most wrapper member functions simply delegate to the corresponding body member functions through the Window Manager, which filters out unauthorized requests. Recall that CWnd is the MFC class of all window wrappers.

The story for threads is the same. Instances of MFC's CWinThread class are merely application-level wrappers that forward most client requests through the operating system's thread manager to system-level objects that represent the actual thread data structures. Of course the thread manager filters out requests that it deems to be illegal, unauthorized, or dangerous. We will use the terms "application thread" and "system thread" to distinguish between CWinThread wrappers and their corresponding system-level bodies.

Here is an edited version of MFC's CWinThread class declaration that shows some of the important public members:

For example, assume Master is a programmer-defined class derived from CWinThread:

In addition to requesting input or being preempted by the operating system, there are several other ways that a thread looses control of the CPU:

Unless the programmer specifies a different controller function, a running thread executes the pre-defined Run() member function. This function perpetually monitors a message queue associated with the thread. The operating system and application objects can post messages to this queue by calling the PostThreadMessage() member function. When a message arrives, Run() forwards the message to its target.

More specifically, Run() perpetually oscillates between idling and message pumping. As long as there are no messages in the message queue, which is indicated when the global PeekMessage() function returns false, Run() repeatedly calls the OnIdle() member function. The default implementation of this function does nothing at all, but it is a virtual function, which can be redefined in derived classes to perform background tasks from spell checking to searching for radio signals from extra terrestrials.

When a message arrives, the control loop shifts into its message pumping phase, where it repeatedly calls the PumpMessage() member function until the WM_QUIT message arrives and the thread terminates, or until the message queue is empty and the control loop can return to its idle phase:

Threads that use the default Run() function are called user interface threads. Although such a thread could be used as a message broker for any collection of objects, the most common use is to dispatch mouse and keyboard messages coming from the user interface.

In fact, the message broker of every MFC application is an instance of a class derived from the CWinApp class, which itself is derived from CWinThread:

The entry point for a C++ program is a global function called main(), but for a Windows application, the entry point is called AfxWinMain(). MFC programmers rarely see this function because it is buried deep inside the framework. Here it is:

The first time an application runs, a permanent entry is created in the registry. Information about the application's appearance and user preferences will be stored in this entry. Each time the application runs, a temporary entry is created where information about the application's current state is stored.

The first time the MFC version of AfxWinMain() is called, it calls InitApplication(), which creates the permanent registry entry. Next, instances of CTestDoc, CTestView, and CMainFrame are created by the call to InitInstance(). These objects are bound together in a data structure called a document template. Finally, the message loop is started. Test is now listening for mouse and keyboard inputs.

Worker Threads

A thread that is controlled by the default Run() member function is called a user interface thread, so called because this function perpetually listens for and dispatches user interface messages. Of course most applications only have one user interface, and therefore only need one user interface thread. A typical multi-threaded application might instantiate the Master-Slave design pattern. In this case the master thread might be a user interface thread, while slave threads perform various "background" tasks. Microsoft refers to slave threads using the more politically correct term "worker thread".

There are two ways to create worker threads. Programmers can redefine the Run() method in a CWinThread-derived class, or they can create an application thread with an alternate controller function.

Recall that CWinThread has two mysterious member variables:

For example, suppose we want to create a worker thread that will perform a specific background task. We begin by describing this task as a global function parameterized by a void pointer and returning an unsigned integer:

A Reusable Worker Thread Class

Creating worker threads that execute global functions operating on global data structures isn't a very object-oriented approach. A better idea is to define a reusable WorkerThread class that programmers can customize by overriding a single virtual function. Either the WorkerThread class is derived from the CWinThread class and redefines the inherited Run() function, or the WorkerThread class is a wrapper for the CWinThread class (i.e., a wrapper for a wrapper). The second approach is left as an exercise for the reader.

Our worker thread class is derived from CWinThread, and overrides the inherited Run() function. Initially, it will be used in an application called Bounce, which will be described in detail later. We begin by creating a single document project:

Bounce

The Bounce application we have already begun allows users to create "balls" that "bounce" around inside the view window. A ball is created simply by clicking somewhere in the window. The new ball veers off in a random direction and at a random speed.

Pressing the [s] key causes all of the balls to suspend bouncing. Pressing the [r] key causes the suspended balls to resume bouncing. Pressing the [k] key kills all of the balls.

Designing Bounce

The design of Bounce is simple. Each ball is controlled by a separate worker thread and encapsulates the x- and y-coordinates of its position in the view window as well as its speed in the x and y directions. The Update() function updates the position of a single ball, then invalidates the view window:

Implementing Bounce

Each ball is an instance of a Ball class, which is derived from the WorkerThread class.

Producer-Consumer Problems

Bounce is a fairly simple example of a multi-threaded application, because the threads that control the bouncing balls don't need to communicate with each other. In more complicated problems threads do need to communicate with each other.

User interface threads can communicate with each other by message passing: thread A creates a message an places it in the message queue of thread B:

A more efficient method of communication is through shared memory. This is particularly easy to set up in the Master-Slave architecture because all slaves share their master's heap and static memory segments. In this case thread A simply makes a modification to some global data structure. For example, the data structure might represent a mailbox where messages can be stored. Later, thread B simply examines the global data structure to see what thread A has done. For example, thread B might remove the message from the mailbox and read it.

But there is a problem. Suppose thread B checks the mailbox before thread A has had a chance to put the message inside? While we can predict the execution order of instructions within a single thread, there is no way in general to predict the execution order for instructions executed by different threads. If thread B misses the message, this could change the behavior of the entire application. This may even result in an error!

This type of problem is particularly difficult for programmers who feel the need to control every aspect of their program's behavior. To solve problems like these programmers use synchronization mechanisms provided by the operating system. A synchronization mechanism allows one thread to lock the global data structure until it is finished. Other threads must wait for the data structure to be unlocked before they can access it.

Producer-Consumer problems are a family of similar problems that are traditionally used to demonstrate synchronization problems and solutions. Generally speaking, a master thread creates a global buffer and two slave threads. One slave is called the producer. The producer perpetually creates imaginary objects called widgets and places them in the global buffer. The other slave is called the consumer. The consumer repeatedly removes widgets from the buffer and consumes them:

Producer-Consumer present several synchronization problems. For example, if the slaves aren't clever, the consumer slave may consume the last widget in the buffer and suspend itself, waiting for the producer to produce more widgets. At the same time, the producer slave adds a second widget to the buffer, failing to realize that the first widget is in the process of being consumed. Since the producer only notifies the consumer when it adds a widget to the empty buffer, no notification is sent. The producer proceeds to fill the buffer with widgets. When the buffer is full, the producer suspends itself, waiting for the consumer to consume some widgets to make more room in the buffer. Of course at this point both the producer and consumer are suspended!

Example: A Joint Checking Account Simulation

A joint checking account is a simple example of a producer-consumer problem. Our simulation will run as a Win32 console application. Consumer and producer worker threads will be equipped with pointers to a shared checking account (the buffer). The producer repeatedly deposits money in the joint account, while the consumer repeatedly withdraws money. (We won't name names.)

Because our simulation runs in a console window, we won't need the MFC App Wizard to create the project.

But wait, something is wrong. The "insufficient funds" message never appears, so the consumer withdrew $8 five times; a total of $40. Of course the producer deposits $10 five times for a total of $50. There was $100 in the account initially, so the closing balance should have been $100 + $50 - $40 = $110, not $116. What happened?

Things went wrong at the very start of the run:

We can represent this situation using a sequence diagram:

Indivisibility

Readers might think that the root of the problem is the leisurely pace of the Account's Deposit() and Withdraw() member functions. Perhaps if we reduced these functions to single lines we could have avoided the interruption problem:

Locks and Latches

One way to coordinate access to a shared resource like a joint bank account is to associate a "latch" with the resource. Like a latch on a door, a client can attach a lock to a resource latch. Locking the lock prevents other clients from accessing the resource until the lock is removed from the latch.

Locks and latches are difficult for programmers to build from scratch. Consider some of the requirements. First, locking a lock must be an indivisible operation. Otherwise, we will simply transfer the problem of simultaneous access from the locked resource to the lock itself. Second, when a client attempts to lock a latch that is already locked, the client must be automatically suspended until the latch is unlocked. Of course there may be many suspended clients waiting to access the shared resource. These clients must be stored in a wait queue associated with the latch. Finally, when a client unlocks a latch, one of two things must happen. If there are no suspended clients waiting in the queue associated with the latch, then the lock is simply removed from the latch. If there are clients in the wait queue, then the latch is left locked, and the first member of the queue is resumed.

Like windows and threads, most operating systems provide locks and latches as system resources. (Clearly the operating system is in a better position than an ordinary application to implement the special requirements described earlier.)

The Windows operating systems provide four types of latches: semaphores, mutexes, critical sections, and events; and two types of locks: single locks and multi-locks. A multi-lock can lock several latches at the same time, while a single lock locks a single latch. We won't need or discuss multi-locks.

The main difference between a critical section and a mutex, is that a mutex (like semaphores and events) can latch a resource shared by clients running inside different programs. The main difference between a mutex and a semaphore is that a semaphore allows several clients to simultaneously access a shared resource, not just one. (Of course the programmer specifies the maximum number of clients that can simultaneously access the resource.) Events are also similar to mutexes, only they can time out, releasing all of the clients on their wait queues.

Critical Sections

A critical section is an instance of MFC's CCriticalSection class. Of course instances of this class are simply wrappers for system-level critical sections. Let's associate a critical section with each instance of our Account class.

We can re-declare latch as an instance of MFC's CMutex class. No other changes need to be made to the code:

Semaphores

Semaphores also have system-wide identities. A semaphore encapsulates three numbers: maximum capacity, current capacity, and current count. The maximum capacity is the maximum number of clients that may access the associated resource. The current count is the number of clients that currently have access to the associated resource. The current capacity is the maximum capacity minus the current count:

Another approach to synchronization is to use events rather than latches. An event is an object that can be in one of two states: signaled (the event has occurred) or non-signaled (the event has yet to occur).

MFC events are instances of the CEvent class. If a client thread attempts to lock a non-signaled event, it is automatically suspended and moved to a wait queue associated with the event. An event can be signaled by calling its SetEvent() member function. An automatic event-the default case-- returns to its non-signaled state as soon as the first client thread suspended on its associated wait queue resumes execution. A manual event remains in its signaled state until its ResetEvent() function is called:

Problem 5.1

Build and test the Bounce application.

Problem 5.2

Create a WorkerThread wrapper class. Test your implementation by re-implementing the Bounce application.

Problem 5.3

Modify Bounce so that a modeless dialog box allows users to set the color, speed, and state (pause, resume, stop) of each ball. (Balls are specified by their array indices.)

Problem 5.4

Modify bounce so that balls perform "collision detection". That is, when the bounding boxes of two balls intersect, then both balls reverse the signs of their dx and dy member variables and make a colliding beep.

Problem 5.5

Build and test the PC (Producer-Consumer) project. Experiment with multiple producers and consumers.

Problem 5.6: Interlocked Functions

In the PC project, experiment with the "single-line" implementations of Account::Deposit() and Account::Withdraw():

We can actually make this idea work if we use one of the Windows platform's interlocked functions. An interlocked function disables interrupts upon entry and enables interrupts upon exit. For example, if all monetary amounts are represented as long integers rather than doubles, we can use the InterlockedExchangeAdd() function to increment and decrement balance:

Problem 5.7: Readers and Writers

Create a producer consumer simulation in which the producer writes strings to a file (the buffer) while the producer reads strings from the file.

Problem 5.8: Predators and Prey

In a predator-prey game predators-ghosts, which appear as blue circles or bitmaps-- pursue a prey-- the hero, who appears as a yellow circle or bitmap-- around the view window. Each ghost is controlled by a worker thread. The Update() function of a ghost worker thread locates the hero, then moves the ghost several steps in the hero's direction. The number of steps is determined by the ghost's speed attribute.

The hero is controlled by the application's main thread, which listens for the user to press the arrow keys. Pressing an arrow key moves the hero a single step in the direction of the arrow. When the bounding box of a ghost intersects the bounding box of a hero, the ghost "eats" the hero and the game ends. Unlike ghosts, the hero can wrap around the screen. In other words, if the hero moves off the bottom of the view window, he reappears at the top of the view window, and all ghosts will need to change direction.

A [Game] menu allows the user to set the number and speed of the ghosts, and to start the game.

Problem 5.9: Dining Philosophers

Dining Philosophers is another classic example of a synchronization problem. Plato, Buddha, Spinoza, Kant, and Hume sit at a circular table in a Chinese restaurant. Each has a plate of food in front of him. Between each pair of plates is a single chopstick. Plato grabs the chopsticks on either side of his plate and begins eating. Of course Plato's neighbors, Buddha and Hume, must wait for Plato to release the chopsticks so they can begin eating (a philosopher must acquire the chopsticks on both sides of his plate before he can eat). If philosophers are worker threads, then the Update() function might look something like this:

The first goal of the program is to guarantee that no philosopher starves. The second goal is to guarantee that each philosopher gets approximately the same amount to eat. For example, suppose at the beginning of the program each philosopher grabs the chopstick to his left, then waits for the chopstick on his right. Of course Buddha's right chopstick is Spinoza's left chopstick, which Spinoza holds and won't release until he acquires Kant's left chopstick. The result is deadlock and all five philosophers starve. It's also possible for two or three of the philosophers to eat, while the remaining philosophers starve.

One solution is to have the master thread play the role of a moderator who schedules the chopsticks for the philosophers.

Problem 5.10: Marquee

Create a single document application called Marquee. Marquee is a form view application that scrolls a string in an edit box. The form view also has [Pause] and [Resume] buttons that pause and resume the scrolling. User can type new strings into the edit box. This application requires a worker thread to scroll the string, and a user interface thread to listen for button clicks.