Threads, in the computer science sense, provide a way for applications to split themselves into several tasks, each running logically (and depending on the underlying hardware, potentially even physically) in parallel. While they may seem similar at first glance, a thread is far different from a process in that a process generally maintains a lot of state information (i.e., in its process control block), has its own address spaces, and typically only interacts with other processes via inter-process communication (IPC) constructs (e.g., sockets). On the other hand, threads share state information of a single process (although each thread usually has its own mini process control block) and directly share memory and resources. Context-switching (i.e., the act of swapping an executing entity with a waiting entity) also typically occurs much faster between threads than between processes. As such, threads are often referred to as lightweight processes used to increase the performance and responsiveness of an application.
Why Would I Want to Use Threads?
There are a variety of reasons to employ threads. Since threads can execute tasks in parallel, programs can finish more work per unit of execution time, thus increasing the overall performance of the program. For example, imagine that you have two sets, x and y, of numbers that need to be sorted. One solution would be to sequentially sort x, sort y, and then complete. This solution is fine if x and y are smaller sets, but this is grossly ineffective if each sort operation takes 30 minutes. Instead, we could create two threads that sort x and y simultaneously and complete when both sort operations complete. By doing so, our program might complete in half of the original time. It's worth noting that spawning n threads does not result in 1/n of the original running time as there is some additional overhead in thread management, and at a certain point, scalability issues arise.
In general, there are four primary benefits of using threads:
- Responsiveness—Multithreading an interactive application may allow a program to continue running even if part of it is blocked or is performing a length operation, thereby increasing responsiveness to the user. For example, a multithreaded Web browser could allow user interaction in one thread while a large table is being loaded in another thread.
- Resource sharing—By default, threads share the same memory and the resources of the process to which they belong. The benefit of resource-sharing is that it allows an application to have several different threads of execution within the same address space.
- Economy—Allocating memory and resources for process creation is costly. Alternatively, because threads share resources of their parent process, it's far more economical to create and context-switch threads than processes.
- Utilization of multiprocessor architectures—The benefits of multithreading can be greatly increased in a multiprocessor architecture, where each thread may be running in parallel on a different processor. A single-threaded process can run on only one CPU, regardless of how many physical processors are available. Multithreading on a multi-CPU machine increases concurrency and decreases runtime.
Depending on the type of application you're creating, the above benefits will carry different weights. For example, if you're creating a GUI, responsiveness is absolutely critical to keeping users happy; everyone gets disgruntled when the GUI freezes up for long periods of time. However, if you're writing programs on enterprise-level systems, it's probably important to make effective use of its multiprocessor architecture and harness all those CPU cycles.
What About Single-Processor Systems?
A common misconception is that, because a system only has one processor, threading won't help since the system can do only one thing at a time anyway. While it's certainly true that a processor can execute only one instruction at a time, threading applications on single-processor systems can still have dramatic impacts. The majority of applications spend most of their time waiting on I/O operations (e.g., user input, disk, network, etc.), so while one thread is blocked on an I/O operation, another thread may be performing useful work (or waiting on I/O from another source).
That Seems Easy. What's the Difficulty?
If you're new to threads, you're probably thinking, "This seems easy enough. I'm going to start multithreading my programs." While there are certainly a lot of opportunities to use threads, there are also a lot of (often hidden) challenges that present themselves when working in a multithreaded environment.
First and foremost, testing and debugging multithreaded programs can be extremely difficult. Threads introduce a whole new slew of challenges. With multiple threads of execution (instead of simply one), the overall sequence of events isn't guaranteed to match from one execution to the next (and usually never does). In a nutshell, this means that your program, all things equal, may appear to work in some cases and not in others because of the manner in which the threads are context-switched. This effect is alternatively known as a "race condition" and is described further later in this article.
Another common problem in multithreaded programs is a condition known as "deadlock." A deadlock occurs when a cycle of wait dependencies occurs between threads. For example, imagine that thread x is waiting for thread y to finish its current operation and thread y is waiting for thread x to finish its current operation. See the problem? This is known as a deadlock because neither thread x nor thread y will ever advance its execution since they're both engaged in a cycle of waits. Deadlocks can be very difficult to detect and can be hard to reproduce, since they're often dependent on a specific sequence of events occurring at just the right times (i.e., race conditions).
Because threads share the same address space, data incoherency is another major problem. That is, if you don't use the right techniques (which I'll discuss later) to access shared data between two or more threads, the data integrity of the program can (and believe me, it will be) compromised as a result of the threads "stepping on each other's toes."
The use of a good program debugger is often needed to resolve these types of problems. For example, the Eclipse-based Java debugger has excellent support for debugging multithreaded programs.
Thread Support in Java
Now that we've covered some of the basics of threads and their accompanying pros and cons, let's take a look at threads in the Java world. Because Java was designed with threads in mind, it has a very rich thread API set. Every thread extends from the java.lang.Thread class. The thread class supports a variety of methods, but these are some of the most commonly used methods:
- Thread(String threadName)—This version of the constructor instantiates a new thread with the specified name. Naming threads can be useful when debugging as it provides a mechanism by which the threads can easily be disambiguated. It's also important to note that all data members of an instantiated thread belong to the thread itself; this effectively provides a thread local storage (TLS) mechanism, which is somewhat tedious to deal with in languages such as C.
- public void run()—This method will be internally invoked by the Java Virtual Machine (JVM) when the thread's start method is invoked. In essence, this is the thread equivalent of the main method for the main program entry point.
- public void start()—Invoking this method causes the thread to start execution. Prior to invoking this method, the thread is in an inactive state.
- public void join()—This method can be used to force the currently executing thread to wait for the thread on which the join method is invoked to finish its execution. This is effective for creating a rendezvous point of sorts.
- public static void sleep(long millis)—This static method can be invoked to force the currently executing thread to sleep for the specified time.
Putting the pieces together, here's a simple program that defines a thread class that simply counts from 0 to 100, printing each number to standard out. The program will spawn 10 threads to perform their count operations in parallel and then wait for the threads to finish before terminating.
|
That's all there is to it: Extend the Thread class, complete the implementation of the run method, and invoke the start method. Your thread's off and running! One noteworthy point here is how threading an application affects exception handling. In the above example, the main thread (i.e., the thread that all programs implicitly contain) spawns several worker threads. Any exceptions generated within the worker threads' call stacks don't percolate back to the main thread. The run method of each thread is effectively the bottom-most level within its call stack, which is the lowest point to which an exception can be thrown. Since the example above is trivial, there's not much room for error.
Let's take a look at some other thread terminology and constructs to help us in more complex cases.
Multithreaded Programming Terms and Techniques
When working in a multithreaded environment, it's important to have a fundamental understanding of some of the terminology. This section introduces some of the commonly encountered multithreaded terms.
Critical Section
A critical section is a block of code that accesses some resource (e.g., a data structure) that will be shared among several threads of execution, but with the limitation that only a single thread should be able to execute the block at any given time (i.e., it should be executed mutually exclusively). The shared piece is the key here. Imagine an array-based linked list structure. When an item is inserted into the array, some positional index is modified to prepare for the next insert. If two or more threads are logically within the insert operation, there's the potential for the positional index to become corrupted. In general, this is where it's critical to pay attention to the "thread-safetiness" of any APIs your code uses. That is, if they're not thread-safe, you'll have to call the APIs within a critical section to ensure the integrity of your application.
A mistake programmers new to multithreaded programming often make is being too liberal with locking mechanisms. For example, take the following simple method that returns an array of floats containing the areas of the specified triangles (let's also assume that once a triangle is created, it's not modified):
|
Is this method thread-safe without the use of any additional locking mechanisms? The answer is yes. The method's not accessing any shared resources; rather, it deals only with arguments and local variables. Each thread has its own private stack on which all of the arguments and local variables exist. This means that should any two threads be within the scope of the getArea method, they'll both be working with their own copies of the variables as they're context-switched in and out. However, if the method accessed a static global variable, you'd need to include additional thread-safety mechanisms, which will be discussed later in this section.
Race Condition
A race condition is the result of a flaw in the design of a concurrent program whereby the output of the program is somehow dependent on the order in which the program's events occur. A classic example illustrating a race condition is a program that contains two threads whose jobs are simply to increment some global integer counter (e.g., via i = i + 1). If the counter is initially 0, you would expect the final output to be 2. However, if the program runs without proper thread synchronization, it's possible that the first thread executed the i = i portion of the expression, then the second thread was context-switched in and executed i = i + 1 (so i is now 1), and then the first thread resumed (but it already loaded i when it was 0) and completed the expression. In this case, the final value is (incorrectly) 1.
Semaphore
Proposed by E. Dijkstra in the 1960s, a semaphore is now considered a primitive construct in multithreaded programming. It's essentially an overloaded counter supporting two basic operations, P (also called wait) and V (also called signal). The P operation decrements the counter, and if it's less than 0, the current thread will block on the semaphore. The V operation increments the counter, and if it's less than or equal to 0 (i.e., there are still threads waiting to acquire the semaphore), one of the blocked threads is woken up and allowed to progress. Here's an example implementation of a semaphore in Java:
|
A semaphore can be used for several purposes. Its most frequent use is to protect access to critical sections. A semaphore whose initial value is 1 (also called a binary semaphore or a mutex) can be used to ensure a block of code is executed mutually exclusively from other threads. For example, let's revisit the example above in the race condition definition. If a shared binary semaphore S was used such that S.P (i.e., obtain the lock) was invoked before the increment and S.V (i.e., release the lock) was invoked after the increment, then the second thread would be blocked until the first thread released the lock. Thus, the final value would be 2, and the race condition would have been completely eliminated.
Another common use for a semaphore is a semaphore S whose initial value is 0, also called a "blocking semaphore." That is, the first call to S.P results in a block operation. When another thread calls S.V, the blocked thread can progress. This is useful in controlling the order in which events occur in a threaded environment.
While semaphores are much-needed and excellent problem solvers in multithreaded programming, they can cause problems if used incorrectly. For example, should any thread attempt to acquire a lock on a binary semaphore to which it already has the lock, a deadlock will occur. That said, pay extra attention when you're acquiring and releasing semaphore locks to avoid these difficult-to-detect problems. A good word of advice is to always signal a semaphore in a finally { } block because even in the event of a RuntimeException (i.e., a special exception class that doesn't need to be explicitly caught), the semaphore will still be signaled. For instance, the logic might look something like this:
|
Prior to Java 1.5, if you wanted to use a semaphore, you had to construct your own (using code similar to the example provided above). However, with the 1.5 release of Java and the addition of the java.util.concurrent package, a very feature-rich semaphore class is provided out of the box.
Thread Pool
A thread pool is a group of threads to which tasks can be submitted. Since creating and destroying threads can carry additional overhead (albeit nowhere near to that of creating and destroying processes), the idea is to create a (fixed) pool of threads that continuously run, waiting to perform work. With the release of Java 1.5, there's now java.util.concurrent.Executors, a class that supports several static methods to create all kinds of thread pools.
Java "Synchronized" Keyword
The "synchronized" keyword in Java serves as a primitive (in Java) lock acquisition and release mechanism. Every object in Java has a hidden lock associated with it, accessible only through the synchronized keyword. For example, an object's method could be written as follows:
public synchronized void doSomething() { ... }
Using the synchronized keyword on the method's signature ensures that if more than one thread at a time tries to execute the doSomething method, subsequent threads will be blocked until the first thread is completed, at which time only one other thread will be allowed to enter the method. This cycle repeats itself until all threads have (serially) executed the doSomething method. This effectively makes the entire body of the doSomething method a critical section. However, this use of synchronized often has side effects that not everyone's aware of. Let's say the object supports another method whose logic is completely unrelated to the doSomething method's logic:
public synchronized void doSomethingElse() { ... }
Using the synchronized keyword in this fashion will not only prevent any two threads from executing each method, but also prevent any two threads from executing the doSomething method and the doSomethingElse method at the same time! While functionally everything will work as expected, this solution has the unwanted side effect of slowing down the entire system. This is because the same lock is used between the two methods. So how can we fix this (without using another locking mechanism, such as a semaphore)? We can use another form of the synchronized keyword that allows us to obtain and release locks on user-specified objects:
|
In this case, we've explicitly defined two different lock objects. This way, we now get the effect we want; no two threads can execute a particular method in parallel, but two threads can execute doSomething and doSomethingElse in parallel.
The curious reader might wonder what would happen if the doSomething method was recursive (or called any other method attempting to acquire a lock on LOCK_1). Would a deadlock occur? The answer is unexpectedly no! That's because Java's synchronized locking mechanism supports lock escalation. That is, if any thread T holds a lock L, any subsequent request T makes to acquire L will succeed via lock escalation (this is a major difference between synchronized and semaphores). While this may or may not be desirable, it's definitely something you need to be aware of.
Threading the Pieces Together
If this seems like it's a lot of information to digest, it's because it is! Threads in a programmer's tool belt are similar to a hammer in a carpenter's tool belt. If used correctly, they can save you a lot of time, and if used incorrectly can cause you a wealth of problems. Should threads be used in all applications? Definitely not. We've seen that although they can increase performance and responsiveness, they make applications much more difficult to test and debug and can introduce an entirely new classification of problems that even the best compilers can't assist you with. However, in certain applications, their use is absolutely necessary and some general thread background knowledge is a huge asset to any development team. As is true with anything, knowing when to use them and identifying the potential areas of conflict comes with experience; practice makes (almost) perfect! If I could leave you with one piece of advice when dealing with threads, it'd be to think thoroughly through the paths of execution, and then do it again and again.
Joe Cropper is a Software Engineer at IBM in Rochester, Minnesota. Joe works as part of the System i Software Final System Test team, and his areas of expertise include database, multi-tiered client-server technologies, and a variety of object-oriented programming languages. Joe can be reached via email at
LATEST COMMENTS
MC Press Online