Making Single-Threaded Code Multithreaded

Making Single-Threaded Code Multithreaded

Many current programs were written for single-threaded processes. Converting these to multithreading is much complicated than it may at first appear. Below we will study just a few of the drawbacks.

As a start, the code of a thread usually consists of multiple procedures, just like a process. These may have local variables, global variables, and parameters. Local variables and parameters do not cause any trouble, but variables that are global to a thread but not global to the entire program are a problem. These are variables that are global in the sense that many procedures within the thread use them (as  they might use any global variable), but other threads should logically leave them alone.

As an example, think about the errno variable maintained by UNIX. When a process (or a thread) makes a system call that fails, the error code is put into errno. In figure 1, thread 1 performs the system call access to find out if it has permission to access a certain file. The operating system returns the answer in the global variable errno. After control has returned to thread 1, but before it has a chance to read  errno, the scheduler decides that thread 1 has had enough CPU time for the moment and decides to switch to thread 2. Thread 2 performs an open call that fails, which causes errno to be overwritten and thread 1's access code to be lost forever. When thread 1 starts up later, it will read the wrong value and behave incorrectly.

Conflicts between threads over the use of a global variable

Many solutions to this problem are possible. One is to forbid global variables altogether. However worthy this ideal may be, it conflicts with much existing software. Another is to allocate each thread its own private global variables, as shown in figure 2. In this way, each thread has its own private copy of errno and other global variables, so conflicts are avoided. In effect, this decision creates a new scoping level, variables visible to all the procedures of a thread, in addition to the existing scoping levels of variables visible only to one procedure and variables visible everywhere in the program.

Threads can have private global variables

Accessing the private global variables is a bit complicated, however, since most programming languages have a way of expressing local variables and global variables, but not intermediate forms. It is possible to allocate a chunk of memory for the globals and pass it to each procedure in the thread as an extra parameter. While hardly an elegant solution, it works.

On the other hand, new library procedures can be introduced to make, set, and read these thread-wide global variables. The first call might look like this:

create_ global("bufptr");

It assigns storage for a pointer called bufptr on the heap or in a special storage area reserved for the calling thread. No matter where the storage is assigned, only the calling thread has access to the global variable. If another thread creates a global variable with the same name, it gets a different storage location that does not conflict with the existing one.

Two calls are required to access global variables: one for writing them and the other for reading them. For writing, something like

set_global("bufptr", &buf);

will do. It stores the value of a pointer in the storage location previously created by the call to create_global. To read a global variable, the call might look like

bufptr = read_global("bufptr");

It returns the address stored in the global variable, so its data can be accessed.

The next problem turning a single-threaded program into a multithreaded program is that many library procedures are not reentrant. That is, they were not designed to have a second call made to any given procedure while a previous call has not yet finished. For instance, sending  a message over the network may well be programmed to assemble the message in a fixed buffer within the library, then to trap to the  kernel to send it. What happens if one thread has assembled its message in the buffer, then a clock interrupt forces a switch to a second thread that immediately overwrites the buffer with its own message?

Likewise, memory allotment procedures, for instance malloc in UNIX, maintain crucial tables about memory usage, for instance, a linked list of available chunks of memory. While malloc is busy updating these lists, they may temporarily be in an inconsistent state, with pointers that point nowhere. If a thread switch happens while the tables are inconsistent and a new call comes in from a different thread, an invalid pointer may be used, leading to a program crash. Fixing all these problems efficiently means rewriting the entire library. Doing so is a nontrivial activity.

A different solution is to provide each procedure with a jacket that sets a bit to mark the library as in use. Any effort for another thread to  use a library procedure while a previous call has not yet finished is blocked. Although this approach can be made to work, it very much removes potential parallelism.

Next, think about signals. Some signals are logically thread specific, whereas others are not. For instance, if a thread calls alarm, it makes sense for the resulting signal to go to the thread that made the call. However, when threads are implemented completely in user space, the kernel does not even know about threads and can hardly direct the signal to the right one. An additional complication happens if a process may only have one alarm pending at a time and various threads call alarm independently.

Other signals, such as keyboard interrupt, are not thread specific. Who should catch them? One designated thread? All the threads? A newly created pop-up thread? Moreover, what happens if one thread changes the signal handlers without telling other threads? And what happens if one thread wants to catch a specific signal (say, the user hitting CTRL-C), and another thread wants this signal to finish the process? This situation can arise if one or more threads run standard library procedures and others are user-written. Obviously, these wishes are incompatible. Generally, signals are difficult enough to manage in a single-threaded environment. Going to a multithreaded environment does not make them any easier to handle.

One last problem introduced by threads is stack management. In many systems, when a process stack overflows, the kernel just provides that process with more stack automatically. When a process has various threads, it must also have various stacks. If the kernel is not aware of all these stacks, it cannot grow them automatically upon stack fault. Actually, it may not even realize that a memory fault is related to the growth of some thread's stack.

These problems are certainly not impossible, but they do show that just introducing threads into an existing system without a fairly substantial system redesign is not going to work at all. The semantics of system calls may have to be redefined and libraries have to be rewritten, at the very least. And all of these things must be done in such a way as to remain backward compatible with existing programs for the limiting case of a process with only one thread. For further information about threads, see (Hauser et al., 1993; and Marsh et al., 1991).


Tags

thread, process, system call, global variable