concurrent programming

Traditional computer programs do only one thing at a time. Execution begins at a specified point and proceeds accord-ing to decision statements or loops that control the process-ing. This means that a program generally cannot begin one step until a previous step ends. Concurrent programming is the organization of pro-grams so that two or more tasks can be executed at the same time. Each task is called a thread. Each thread is itself a traditional sequentially ordered program. One advantage of concurrent programming is that the processor can be used more efficiently. For example, instead of waiting for the user to enter some data, then performing calculations, then waiting for more data, a concurrent program can have a data-gathering thread and a data-processing thread. The data-processing thread can work on previously gathered data while the data-gathering thread waits for the user to enter more data. The same principle is used in multitasking operating systems such as UNIX or Microsoft Windows. If the system has only a single processor, the programs are allocated “slices” of processor time according to some scheme of priorities. The result is that while the proces-sor can be executing only one task (program) at a time, for practical purposes it appears that all the programs are run-ning simultaneously (see multitasking).

Multiprocessing involves the use of more than one proces-sor or processor “core.” In such a system each task (or even each thread within a task) might be assigned its own proces-sor. Multiprocessing is particularly useful for programs that involve intensive calculations, such as image processing or pattern recognition systems (see multiprocessing).

Programming Issues

Regular programs written for operating systems such as Microsoft Windows generally require no special code to deal with the multitasking environment, because the operating system itself will handle the scheduling. (This is true with preemptive multitasking, which has generally supplanted an earlier scheme where programs were respon-sible for yielding control so the operating system could give another program a turn.)

Managing threads within a program, however, requires the use of programming languages that have special state-ments. Depending on the language, a thread might be started by a fork statement, or it might be coded in a way similar to a traditional subroutine or procedure. (The dif-ference is that the main program continues to run while the procedure runs, rather than waiting for the procedure to return with the results of its processing.)

The coordination of threads is a key issue in concur-rent programming. Most problems arise when two or more threads must use the same resource, such as a processor register (at the machine language level) or the contents of the same variable. Let’s say two threads, A and B, have statements such as: Counter = Counter + 1. Thread A gets the value of Counter (let’s say it’s 10) and adds one to it. Meanwhile, thread B has also fetched the value 10 from Counter. Thread A now stores 11 back in counter. Thread B, now adds 1 and stores 11 back in Counter. The result is that Counter, which should be 12 after both threads have processed it, contains only 11. A situation where the result depends on which thread gets to execute first is called a race condition.

One way to prevent race conditions is to specify that code that deals with shared resources have the ability to “lock” the resource until it is finished. If thread A can lock the value of Counter, thread B cannot begin to work with it until thread A is finished and releases it. In hardware terms, this can be done on a single-processor system by disabling interrupts, which prevents any other thread from gaining access to the processor. In multiprocessor systems, an inter-lock mechanism allows one thread to lock a memory loca-tion so that it can’t be accessed by any other thread. This coordination can be achieved in software through the use of a semaphore, a variable that can be used by two threads to signal when it is safe for the other to resume process-ing. In this scheme, of course, it is important that a thread not “forget” to release the semaphore, or execution of the blocked thread will halt indefinitely.

A more sophisticated method involves the use of mes-sage passing, where processes or threads can send a variety of messages to one another. A message can be used to pass data (when the two threads don’t have access to a shared memory location). It can also be used to relinquish access to a resource that can only be used by one process at a time. Message-passing can be used to coordinate programs or threads running on a distributed system where different threads may not only be using different processors, but run-ning on separate machines (a cluster computing facility).

Programming language support for concurrent pro-gramming originally came through devising new dialects of existing languages (such as Concurrent Pascal), building facilities into new languages (such as Modula-2), or creating program libraries for languages such as C and C++.

However, in recent years concurrent programming lan-guages and techniques have been unable to keep up with the growth in multiprocessor computers and distributed computing (such as “clusters” of coordinated machines). With most new desktop PCs having two or more process-ing cores, there is a pressing need to develop new programs that can carry out tasks (such as image processing) using multiple streams of execution. Meanwhile, in very high-performance machines (see supercomputer), the Defense Advanced Research Projects Agency (DARPA) has been try-ing to work with manufacturers to develop languages to work better with computers that may have hundreds of processors as well as distributed systems or clusters. Such languages include Sun’s Fortress, intended as a modern replacement for Fortran for scientific applications.

The new generation of concurrent languages tries to automate much of the allocation of processing, allowing programmers to focus on their algorithms rather than implementation issues. For example, program structures such as loops can be automatically “parallelized,” such as by assigning them to separate cores.