Threading

This article gives an introduction to threading and, in particular, multi-threading in computer programs. It first describes the concept of a thread, explains the shortcoming of a program with only one thread, and explains how multiple threads can be used to overcome those shortcomings.
This is followed by a discussion of the issues that arise when threads have to communicate. The article concludes with a discussion of how object-oriented programming improves the reliability of multi-threaded applications.

This article has code examples that follow the C syntax. "< function >" is used in places where a function is called that must be supplied before the example code can actually be used.

The definition of a thread

"Threading" for computer programs refers to the sequence of instructions that is being executed. A program describes the sequence of instructions that must be executed to implement its behavior. This sequence of instructions is called a thread. Of particular importance is the fact that in a thread there is exactly one instruction that is executed at any point in time.

Consider the following small piece of a C program:

The following picture shows the activities that are caused by this section of code. The different activities are marked with numbers and are connected with lines, giving the appearance of a tangled "thread."

"Untangling" the thread gives the following sequence of activities:

1. Put the number zero into the memory location "sum."

2. Put the number zero into the memory location "i"

3. Test if i is less than 3

4. Add i to sum

5. Add 1 to i

6. Test if i is less than 3

7. Add i to sum

8. Add 1 to i

9. Test if i is less than 3

10. Add i to sum

11. Add 1 to i

12. Test if i is less than 3

13. Print the value of sum (which in itself is a whole set of actions, each executed at its turn).

Typically when analyzing a computer program, one looks at only one thread.

When one thread is problematic

Suppose your job is to write a program that prints out the current time once a second, until the user hits the enter key. UpdateTimeDisplay is a function that prints out the current time. We assume for now that it is given to us. Getchar is a function provided by most operating systems to read a key that was typed on the keyboard. What would such a program look like? The first approach might look like this:

int main ( int argc , char** argv )
{
  <UpdateTimeDisplay> ();
  getchar ();
  return 0 ;
}

This program prints the time, but only once. As soon as it enters getchar, it is stuck until the user presses the enter key. What is missing is a loop that prints the time. So a second try might be:

int main ( int argc , char** argv )
{
  do {
    <UpdateTimeDisplay> ();
    Sleep ( 1000 );
  }
  getchar ();
  return 0 ;
}

This program has another problem: It will never get to the getchar command. It will be stuck endlessly in the do {...} loop.

One solution to this problem is to have two threads: The first thread simply waits for the user to hit the enter key, and then causes the program to exit, while the second thread prints the time every second.

The two threads would be as follows:

c = getchar ();
return 0 ;

while ( true ){
     <UpdateTimeDisplay> ();
     Sleep ( 1000 );//time in milli-seconds
     }

If both threads are executed simultaneously, the time display will be updated every second, and the user can terminate the program by hitting the enter key.

Simultaneous execution

How can two threads be executed simultaneously? If your computer has two CPUs, each of them could run one of the two programs. But chances are that yours has only one CPU. In this case the two program aren't really executed simultaneously, rather, the operating system in effect simulates two CPUs. Your single CPU executes the first thread for a certain amount of time, then it executes the second thread. The switching back and forth goes fast enough that we don't notice it. Even though the operating system fools us, and executes only one thread at a time, we still get the benefit of an updated clock and a way to wait for the enter key to be pressed.

The beginning and the end of a thread

Our example above works fine once the two threads are created. But so far we have not looked at how threads are actually created. Generally, a program is started with one thread. For C programs the thread is considered started when it enters the procedure "main", and it is considered ended after it leaves "main". Different operating systems have different ways of letting you create threads, but generally they all provide a call to create a new thread. This call typically requires a pointer to a function. The thread is considered started when it enters that function (which will happen when the operating system has done the necessary initialization of the new thread). The thread will end after it has left that function. The Windows operating system has the _beginthreadex call to accomplish this. If you are programming on a Unix system, you may have the Posix Thread (pthread) library available to you. Pthread's call to create a new thread is pthread_create.

Communication between threads

If you look carefully at thread 2 of the previous example, you will notice that it has the "while" loop and will never leave it. This thread has no end, which is not a good programming practice. The code should have a way to exit the loop (in our case thread 2 should leave the loop once thread 1 noticed that the user has pressed a key. What is needed is a way for the two threads to communicate. In our example, thread 1 should be able to tell thread 2 to end, and thread 2 should tell thread1 that it has ended. When thread 1 finds out that thread 2 has ended, it can exit the function main.

So here is what the modified program might look like. Thread 1 will run through function main, and thread 2 will run through function th2.

The two procedures are written into one C program as follows:

int req = 0 ;
int ack = 0 ;

int th2 ()
{
  while ( 0 == req ){
    UpdateTimeDisplay ();
    Sleep ( 1000 );//time in milli-second
  }

  ack = 1 ;
}

int main ()
{
  StartThread ( th2 );//os-dependent call.
  getchar ();

  req = 1 ;
  while ( 0 == ack ){
    Sleep ( 100 );//milli seconds
  }
}

Let's analyze the behavior of this program by listing the activities of both threads side by side. The left side is the "main thread", and the right side is "thread 2." Over time, the program will go through several phases, as outlined below

StartThread (th2)

c = getchar ();

while ( 0 == req ){
	UpdateTimeDisplay (); 
	Sleep ( 1000 );//time in milli-second 
	}

req = 1 ;

while ( 0 ==ack ){
	Sleep ( 100 );
	}

ack = 1 ;

The problem of accessing variables simultaneously by multiple threads

Suppose that we now change our example program such that UpdateTimeDisplay () does two things: It updates the display of the time on the user's display, but it also returns a string of characters, which contain the time in a human readable form. Its prototype could look something like:

const char* UpdateTimeDisplay ().

Each time UpdateTimeDisplay returns it will return a const char pointer to a textual representation of the time. It may be a different pointer on each return. The pointers returned previously may not point to valid memory locations, or they may point to memory that has since been used for some other purpose.

Suppose furthermore, that the main thread is using the pointer that has been returned by updateTimeDisplay itself in its printf instruction.

Our program now looks like this:

int req = 0 ;
int ack = 0 ;
const char* ti ;
int th2 ()
{
	while ( 0 == req ){
		ti = UpdateTimeDisplay ();
		Sleep ( 1000 );//time in milli-second
	}

	ack = 1 ;
}

int main ()
{
  ti = UpdateTimeDisplay (); //make sure that ti is initialized

  StartThread ( th2 ); //os-specific call 

  getchar ();
  printf ( "You have requested to exit at %s\n" , ti );

  req = 1 ;

  while ( 0 == ack ){
    Sleep ( 100 );//milli seconds
  }
}

The variable ti is now used in both threads: th2 modifies it when UpdateTimeDisplay returns, and main uses it in the printf instruction. There is a small, but non-zero chance for disaster in this code: What happens if main uses ti, while th2 modifies it? The results are unpredictable, since we don't know precisely what th2 and main are doing when both access the memory that is referenced by ti. This bug could lurk in your program undetected for a long time, because the simultaneous access to ti by both threads happens extremely rarely. Maybe in all of your tests this simultaneous access never happens, but when you show it to your client for the first time - bam!

What you really want is to make sure that ti is never accessed by both threads at the same time. While th2 is in the UpdateTimeDisplay instruction, main should not be allowed to access ti, and while main is in the printf instruction, th2 should not be allowed to modify it. We therefore need the capability to make sure that each thread waits for its turn.

The MS Windows Operating system provides a CRITICALSECTION for this purpose. When a CRITICALSECTION is obtained by a thread, no other thread can obtain it. If any other thread tries to obtain it, that thread will be suspended until the CRITICALSECTION is released by the thread currently using it. The pthread library provides pthread_mutex_t and a set of calls to implement the same functionality

Our program should now be as follows (added instructions are in blue)

<os-specific type for mutex> m ;//os-specific
int req = 0 ;
int ack = 0 ;
const char* ti ;
int th2 ()
{
  while ( 0 == req ){
    <call to get mutex> ( m ); //os-specific
    ti = UpdateTimeDisplay ();
    <call to release mutex> ( m ); //os-specific
    Sleep ( 1000 );//time in milli-second
  }

  ack = 1 ;
}

int main ()
{
  <initialize mutex> ( m ); //os-specific
  ti = UpdateTimeDisplay (); //make sure that ti is initialized

  StartThread ( th2 );

  getchar ();

  <call to get mutex> ( m ); //os-specific
  printf ( "You have requested to exit at %s\n" , ti );
  <call to release mutex> ( m ) ;//os-specific

  req = 1 ;

  while ( 0 == ack ){
    Sleep ( 100 );//milli seconds
  }
}

If you forget to Release the mutex, the other thread will never get it. The other thread is then stuck in the ObtainMutex. This is not a good thing! Generally, it is also bad practice to keep a mutex for long periods of time, since this increases the chance that another thread will be stopped for long periods of time.

More elaborate thread interactions

Threads may be in a situation in which they cannot continue to do their work until another thread has finished a particular task. Consider the following scenario: Your program has a "queue." One thread (thread A) has data that it puts into the queue, and another thread (thread B) takes the data out. Whatever is put into the queue first is taken out first. Such a queue is also called a FIFO (first in/first out).
What should thread B do if there are no data in the queue? It has to wait until thread A has placed something into the queue. Furthermore, at some point your program's job will be finished, and thread B will need to exit.

To solve this problem, thread B tells the operating system that it wants to be suspended for a while. Thread B also indicates to the operating system when it should be activated again. It does this by something called a "signal" by Windows, or a "trigger" by pthread. When thread B calls the operating system to be suspended, it indicates what signal or trigger should be used to activate it again. From thread B's perspective, it will not return from the call into the OS until the signal/trigger has been received. This signal or trigger will be issued by thread A as soon as it has put data into the queue. The same signal or trigger may also be issued, by thread A or another thread, when the program should finish. For thread B this means the following: Once it returns from the OS call, it checks if the queue has any data, or if there is an indication that it should exit.

Let's look at a possible implementation of this queue with threads to fill and empty it. 

//********************************************************* //variables, which are needed by both threads: char* queue int queueCount ; int endThreadB ; int ackThreadB ; <mutex> mx ; <trigger> tg ; //********************************************************** //the function that empties the queue //it is run in thread b void readQueue () { <grab mutex> ( mx ); while ( true ){ while ( 0 == queueCount && 0 == endThreadB ){ //nothing in queue. Must wait for data to arrive. <wait for trigger> ( tg , mx ); //will return only when the trigger has been sent. //In our case by thread a. //wait for trigger () will also release mx temporarily, //so that thread a can grab it. } if ( 0 != endThreadB ){ break ; } //we have some data. Do something with it: <call routine to process data> ( queue , queueCount ); <call routine to remove processed data from queue > ( queue ); queueCount = 0 ; } ackThreadB = 1 ; < release mutex > ( mx ); } //********************************************************** //the function that fills the queue //it is run in thread a void writeQueue () { //we assume that there is a source of data that we can read, //and that delivers data at some time intervals. char* d ; int size ; do { size = <call routine to get data > ( d ); //returns -1 if no more data to read. if ( 0 > size ){ break ; } //get mutex < grab mutex > ( mx ); <call routine to put d into queue >( d ); queueCount = queueCount + size ; <send trigger > ( tg ); < release mutex > ( mx ); } while ( true ); < grab mutex > ( mx ); endThreadB = 1 ; < release mutex > ( mx ); do { < grab mutex > ( mx ); ack = ackThreadB ; < release mutex > ( mx ); } while ( 0 == ack ); } //********************************************************** //main. It is automatically entered at startup. //The thread that enters in main is //thread a. void main () { <initialize mutex> ( mx ); <initialize trigger> (tg ); <initialize queue buffer > ( queue ); queuCount = 0 ; ackThreadB = 0 ; endThreadB = 0 ; <start thread b> (readQueue) writeQueue (); }

Using C++ classes to make multi-threading less error prone

Multiple threads in a program can become a big headache: Starting threads, ending threads, avoiding simultaneous access to the same variable, and avoiding an indefinite suspension of a thread are difficult to assure in programs with even moderate complexity.

To reduce the chances to introduce errors into the application code, a set of ground rules are typically established, and all programmers are expected to follow these rules. When the ground rules are appropriate, and the programmers follow them well, usually the problems become manageable. 

But often problems still occur during the lifetime of the program. As the original design team moves on, and engineers who have not participated in the architectural design are given the task of code modifications, violations of the rules can easily slip into the code. Object-oriented techniques can be used to have the rules be applied "by default." While this does not assure the continuation of good programming practice, it is a tremendous help towards that goal. Using objects of well-defined classes can automatically apply the rules, resulting in less chance of inadvertent rule violations, even in later stages of the program's life cycle.

Furthermore, if desired, a set of classes can be developed, which are independent of the specifics of an operating system. The application developer can write the application more efficiently by concentrating on the functionality of the application, rather than spending time and energy on intricacies of the operating system's thread technology.

Component Software, Inc. has developed a family of classes to make multi-threading easier. This family of classes is written in C++. These classes can be used to achieve the following benefits:

• Encapsulate a thread into a class. This class has methods to allow suspending, resuming, and terminating a thread.

• Specify an interface class that is used as the object in which the thread will execute

• Provide a set of classes to manage mutually-exclusive access to variables.

• Provide these class definitions independent of operating system-specific implementations, so that the application code can be compiled for different operating systems without requiring modifications (of course, operating-specific code is added in the form of sub classes, and operating system-specific class factories are required).

The classes and their usage are described further in the article threadclasses.htm.