Threads and Concurrent Programming

The technique of concurrently executing several tasks within a program is known as multitasking. A task in this sense is a computer operation of some sort, such as reading or saving a file, compiling a program, or displaying an image on the screen. Multitasking requires the use of a separate thread for each of the tasks. The methods available in the Java Thread class make it possible (and quite simple) to implement multithreaded programs.

Most computers, including personal computers, are sequential machines that consist of a single CPU, which is capable of executing one machine instruction at a time. In contrast, parallel computers, used primarily for large scale scientific and engineering applications, are made up of multiple CPUs working in tandem.

Today’s personal computers, running at clock speeds over 1 gigahertz— 1 gigahertz equals 1 billion cycles per second—are capable of executing millions of machine instructions per second. Despite its great speed, however, a single CPU can process only one instruction at a time.

Each CPU uses a fetch-execute cycle to retrieve the next instruction from memory and execute it. Since CPUs can execute only one instruction at a time, multithreaded programs are made possible by dividing the CPU’s time and sharing it among the threads. The CPU’s schedule is managed by a scheduling algorithm, which is an algorithm that schedules threads for execution on the CPU. The choice of a scheduling algorithm depends on the platform on which the program is running. Thus, thread scheduling might be handled differently on Unix, Windows, and Macintosh systems.

One common scheduling technique is known as time slicing, in which each thread alternatively gets a slice of the CPU’s time. For example, suppose we have a program that consists of two threads. Using this technique, the system would give each thread a small quantum of CPU time— say, one thousandth of a second (one millisecond)—to execute its instructions. When its quantum expires, the thread would be preempted and the other thread would be given a chance to run. The algorithm would then alternate in this round-robin fashion between one thread and the other(Fig. 14.1). During each millisecond on a 300-megahertz CPU, a thread can execute 300,000 machine instructions. One megahertz equals 1 million cycles per second. Thus, within each second of real time, each thread will receive 500 time slices and will be able to execute something like 150 million machine instructions.

Figure 14.1: Each thread gets a slice of the CPU’s time.

Under priority scheduling, threads of higher priority are allowed to run to completion before lower-priority threads are given a chance. An example of a high-priority thread would be one that is processing keyboard input or any other kind of interactive input from the user. If such tasks were given low priority, users would experience noticeable delays in their interaction, which would be quite unacceptable.

The only way a high-priority thread can be preempted is if a thread of still higher priority becomes available to run. In many cases, higherpriority threads are those that can complete their task within a few milliseconds, so they can be allowed to run to completion without starving the lower-priority threads. An example would be processing a user’s keystroke, a task that can begin as soon as the key is struck and can be completed very quickly. Starvation occurs when one thread is repeatedly preempted by other threads.