Start Concurrent: A Gentle Introduction to Concurrent Programming

We’ll begin with bugs commonly found in sequential programs, some of which have been mentioned in previous chapters as common mistakes. We won’t discuss syntax errors or any other errors which can be caught at compile time. Instead, all bugs discussed in this chapter are run-time bugs.

There’s an infinite number of possible bugs, so they can’t all be listed. Below are a few of the most common categories of bugs to affect beginner (and occasionally veteran) programmers.

A common cause of program errors is an incorrect assumption by a programmer. A programmer can assume that the user will only enter positive numbers, that a library call won’t throw any exceptions, or that a linked list is never empty. Some assumptions are reasonable, but it’s important to make sure that they’re correct.

Using assertions is a way to check some of your assumptions, often those surrounding a method call. In most languages, an assertion tests a condition. If that condition is true, nothing happens, but if it’s false, the program shuts down or an error or exception is thrown. Using assertion statements is particularly important with methods because you want to be sure that both your input and output are in the ranges you expect them to be.

Java supports assertions natively, as we’ll discuss in the next section. However, virtually every language allows you to create your own assertions should they not be present as a language construct.

Computer programs execute quickly. Even if they executed a million times slower, no human is sensitive enough to decipher the flow of electrons inside the processor as a program executes. The simple truth is that we have no idea what’s really happening when our programs execute. We believe that we understand our programs well, and the output usually confirms that our programs are doing what we imagine they should be doing.

If the output doesn’t match our expectations, we might not have enough data to understand the problem. As long as there have been programmers, they have been printing out additional debug information to find their errors. This technique can go a step beyond simple assertion statements because you can print out the values of the variables rather than just test to see if they’re in a range.

Once you’ve found the error in your code, it can be tedious to remove all of your debug statements. Some programmers use a special print command that can be turned off using a global variable or compiler option. Others send their output to stderr so that it doesn’t interfere with the legitimate output of the program. Much depends upon the system, the language, and the individual tastes of the programmer.

With the rise of modern debugging environments, using print statements has lost some of its appeal. Most languages allow the programmer to run his or her program in a special debug mode where it’s possible to execute a single line of code at a time. These tools usually give the option of stepping over method calls or stepping into them on a case by case basis.

As the program executes, the programmer can inspect the values of the variables in the code. This method of debugging is excellent because it allows the programmer to watch the execution of the code at whatever pace he or she desires. Pinpointing problems becomes trivial if you know which variables you need to watch.

Despite the power of this technique, it has critics. Some older programmers look down on these tools because they make new programmers lazier and, in some cases, less careful about writing code correctly in the first place. It should be noted that step-through execution modes are not available for every language or for every system. Some embedded software or operating system programming cannot be debugged on the real hardware in this way. Of course, most of these systems can be run in virtual environments that do allow step-through debugging.

Even when step-through debugging is available, there are difficulties that can limit its effectiveness. If the bug occurs sporadically, perhaps due to race conditions, a programmer might not know where to start looking. Certain data structures such as the list template in C++ might not be easily traversable using the inspection facilities of the debugger. Likewise, the bug or the source of the unexplained behavior could be buried in library code. The debugger doesn’t always have access to library code for stepping through.

Breakpoints are a feature of step-through debuggers designed to make them easier to use. A user can specify a particular line of code (with some restrictions) as being a place where the debugger should pause execution. Debuggers typically rely on at least one breakpoint in order to skip all the preliminary parts of the code and skip straight to the perceived trouble spot.

Sometimes an error will crop up predictably after many thousands of iterations of a loop or unpredictably due to race conditions or user input. For either of these cases, conditional breakpoints can be used to save the a programmer a great deal of time. Rather than always pausing execution on a given line, a conditional breakpoint will only pause if a certain condition is met.

As we mentioned before, many languages have assertions as a built-in language construct. In Java, there are two forms this feature takes. The simpler can be done by typing the following.

In this case, condition is a boolean value that’s expected to be true for the program to function properly. The more complicated form of the feature can be used as follows.

This form adds a value that can be attached to the assertion to give the user more information about the problem. This value can be any primitive data type, any object type, or a statement that evaluates to one of the two.

If you’ve never used an assert statement before, you might want to test it out by forcing an assertion to fail. You might try the following.

Then, if you compile your program and run it through the JVM, you’ll be shocked when absolutely nothing happens. Actually, some of you with older Java compilers might have heard complaints when you tried to compile this code. If you have a Java 1.3 compiler or earlier, it’ll treat assert like an identifier. Some old Java 1.4 compilers might also give warnings or require special flags to compile. However, if you have an up-to-date compiler, the problem is that the JVM must have assertions enabled at run time. Assertions are intended to be a special debugging tool and ignored otherwise. To turn run program AssertionTest with assertions enabled, type the following.

With this option, an exception should be thrown at run time.

If you’re using an IDE like Eclipse or IntelliJ, you’ll need to enable assertions on the run configuration for the program, usually by putting -ea in the field for JVM arguments. There are other options allowing you to enable or disable assertions for specific packages or classes.

Now that you know how to use assertions, you need to know when they’re a good idea. The Java Tutorials on the Oracle website suggest five situations where assertions are useful: internal invariants, control-flow invariants, preconditions for methods, postconditions for methods, and class invariants. Internal invariants are those situations when you assume that reaching a certain place in your code, like the else branch of an if statement, will force a variable to have a certain value. For internal invariants, you assert that the variable has the expected value. A control-flow invariant means that you assume that your code will always execute along a certain path. For control-flow invariants, you assert false if the JVM reaches a point in the code you expected it never would. Method preconditions are those conditions you expect to be true about the state of objects or the input to a method before the method is called.

The philosophy of Java is that public methods should not have assertions used to test their preconditions. Instead, illegal input values for a public method should cause exceptions to be thrown, so that improper usage can always be dealt with. In contrast, method postconditions are the states that various variables and objects should have at the end of a method call. Using assertions to check these values is fine, since they reflect an error on the part of whoever wrote the method. Class invariants are conditions about the state of every instance of a class that should be true as long as the class is in a consistent state. Perhaps a method call rearranges the innards of an object, but by the end of the method call, the object should be consistent again. You should use assertions to check class invariants at the end of every method that could make the object violate these invariants.

Wonderful as assertions are, there are times when they shouldn’t be used. The key danger of assertions is that they’re usually turned off. Thus, any statement that’s part of an assertion must not have side-effects that are necessary for the normal operation of the program. For example, imagine you have an object called bacteria that mutates periodically. The mutation returns true if successful and false if there was an unexpected error. You should not test for that failure inside an assert, as follows.

With assertions disabled, the entire assertion is skipped, and the bacteria object won’t mutate. Instead, your assertion should test only the result of the computation.

As stated above, checking for bad input coming into public methods shouldn’t be done with assertions because turning off assertions will remove your error checking.

Print statements are one of the most time-honored methods of debugging and remain a quick, dirty, yet effective means of finding errors. Java does not provide any special tools to make print statements easier to use for debugging. Some purists might argue that this kind of debugging which focuses on progressively narrowing down the location of a problem until the bad assumption, logical mistake, or typographical error can be found should be done only with assertions.

Nevertheless, there are a few tips to make print statements a better debugging tool in Java. The first is the use of System.err. By now, you’ve used System.out.print() and System.out.println() so many times that you’re probably tired of them. Any output method that can be used with System.out can also be used with System.err. For example, there’s a System.err.print() and a System.err.println() method. If you simply run a program from the command line and watch the output, you should see no difference between using System.out and System.err. However, if you redirect the output of your program to a file using the > operator, only the System.out code will be sent to the file. Anything printed with System.err will be sent to the screen. Alternatively, you can redirect System.err to a file by using the 2> operator. Using System.err makes it easier to separate legitimate output from error messages, but it also makes it easier to comment out your debug code by doing a find and replace.

A more extensive method for using print statements to debug is by defining your own class for printing. Every method in it can call a corresponding method in System.out or System.err. You can define a boolean value at the class level that determines whether or not methods in your debug printing class print or stay silent. When you want to change from debugging to your production or retail version of the code, you can simply switch this value to false.

A “modernized” method of using print statements is creating a simple GUI instead. In preparing materials for this textbook, we were occasionally frustrated by the fact that multiple threads can interfere with each other while printing on the screen: You can’t always tell which thread is printing which characters. By displaying the output of each thread in separate JTextArea or JLabel components on a simple GUI, you can disentangle the output of each thread.

Since the Eclipse and IntelliJ IDEs are so widely used, we’re going to review the step-through debugging features of each environment. Similar tools are available with other IDEs and for most languages.

Experience is often the difference between a good programmer and a bad programmer. Having seen a bug before means you know to expect it in the future. Don’t be discouraged if it takes hours to find a bug and squash it. Although that time is stressful, spending hours poring over your program makes you better at reading code, a skill just as valuable as writing code. And when you’ve spent hours trying to fix a simple mistake, you’re unlikely to make the same mistake again. To make it easier to spot some of these mistakes, we give a few examples corresponding to the common bugs listed in Section 16.1.

Loops give Java much of its expressive power, which includes the power to express incorrect code. Here are examples of a few of the most common loop errors.

Any time you have a large collection of data, there are always opportunities for bugs. With catastrophic array bugs, Java usually gives clear exceptions that point you to the line number. Once the exception is thrown, the bug should be obvious. The biggest difficulties arise when some unusual course of events is responsible for the bug cropping up and you have to reconstruct what it is.

We don’t have variables in real life, and as a consequence, our intuition about them is sometimes wrong. Which variable you’re accessing at any given time can appear obvious, even if it really isn’t.

Null pointer errors usually raise a NullPointerException in Java. This category of errors is something of a catch-all that could happen for many different reasons, some of which have already been mentioned. A NullPointerException could be raised because the elements of an object array haven’t been initialized. Scope problems could cause a reference to be null if the programmer was mistakenly updating another reference, leaving the reference in question uninitialized.

Though they are common, it’s difficult to give a blanket explanation for why most null pointer errors happen. Usually there’s some fundamental error in program logic. Linked lists and tree structures that rely on null references to mark the end of a list or an empty child node are especially susceptible to these errors.

One significant source of errors is careless usage of method parameters. A programmer might pass in objects that don’t conform to expectations or even null references instead of objects. Well written methods, particularly library calls, should be designed to throw an appropriate exception when this happens. Poorly designed code might blindly use a null reference without checking it first, causing a NullPointerException.

A race condition describes the situation when the output of a program is dependent on the timing of the execution of two or more threads. Because of the complexity of the JVM and the OS and the fact that many other processes might be running and interacting, it’s usually impossible to determine how two threads will be scheduled. As a consequence, if the output of the program depends on unpredictable timing, the output will also be unpredictable.

In Java, the way that race conditions often impact the program is through some variable shared between multiple threads. When the schedule of threads becomes unpredictable, the changes made to this variable can come out of sequence, and its value becomes unpredictable. Incorrect output means that your program has a bug, but the most frustrating aspect of race conditions is that they’re nondeterministic. Your program could sometimes have the right answer and sometimes not. Your program could always have the wrong answer but not always the same one. The truly insidious issue with race conditions is that they’ll usually cause errors only a tiny percentage of the time. Thus, rigorous testing such as we’ll discuss in the second half of this chapter is necessary to show that a race condition is occurring.

Both deadlocks and livelocks describe situations in which some part of your program will stop making progress because of thread interaction. In the case of deadlock, there will be a circular wait in which thread A is waiting for thread B which is waiting, directly or indirectly, on thread A. In the case of livelock, some repetitive pattern of waiting for a condition that will never be satisfied is still going on, but the threads continue to use CPU time and aren’t simply waiting.

If your program reaches a deadlock state, it won’t terminate. If threads updating a GUI become deadlocked, your window might freeze. Typically, deadlocks are nondeterministic and occur only some of the time. Like all race conditions, they can be difficult to detect and duplicate. In fact, Thread.stop(), Thread.suspend(), and Thread.resume(), three seemingly useful and fundamental methods that were originally part of the Java Thread class, have been deprecated because they are deadlock prone.

One bug that isn’t even a bug in non-parallel code is sequential execution. This situation arises when, usually due to overuse of synchronization tools, parallel code runs sequentially. Each segment of code, instead of running in parallel, is forced to wait for another to complete. A certain amount of serial execution is necessary to maintain program correctness and avoid race conditions, but Amdahl’s Law gives a rigid, mathematical characterization of how easily speedup can be lost if serial execution makes up large portions of program execution. Because setting up threads and using other concurrency tools has some overheard, a parallel program executing sequentially often runs more slowly than a completely sequential version.

Since programs are usually parallelized for the sake of speedup, it’s useful to time sections of programs to see how well you’ve parallelized them. Sequential execution due to synchronization tools is only one of the many problems that can cause slow execution. The threads might be competing for a limited resource such as an I/O device or might be fighting over a small section of memory, causing cache misses. Tuning applications for maximum performance requires an expert understanding of the concurrency issues within software as well as the underlying OS and hardware characteristics. For now, it’s enough to be aware of the risk of sequential execution and to be as careful as possible when applying locks and other synchronization tools.

We’ve remarked in the past that good design pays off ten-fold in implementation, and that payoff continues to increase by factors of ten as you move on to testing and eventually deployment.

One of the first design decisions you might have to make is choice of language. Some languages are better designed for certain tasks than others. For example, languages like Ada have been carefully designed to minimize programming mistakes such as mis-matched else blocks. Many functional languages like ML are designed so that memory errors such as a NullPointerException are impossible. Even Java has taken clear steps to avoid some of the errors possible, such as bus errors, in C and similar languages that allow pointer arithmetic. However, many other factors such as portability, compatibility, and speed will affect your language choice.

If you’re working in the software development industry, you might be given a specification from your client or your supervisors. As you design the software needed to meet the specification, you might use UML diagrams to map out the classes and interactions you plan to implement in your program.

There are many questions you might ask yourself as you design your solution. Will your solution be compatible with the system and future changes made to the system? Is it easy to add features to your solution? Does your solution deal gracefully with mistakes in user input or external hardware and software failures? Is your code easy to maintain, particularly by future programmers who were not involved in its initial development? Are the components of the system modular? Can they be worked on, tested, and upgraded independently? Are the components of your system designed well enough to be reused for other applications? Are the elements of your system secure from malicious attacks? Finally, is it easy for the user to work with your software?

Each one of these questions is related to a separate sub-field in software engineering. It might be impossible to address them all completely, but different applications will have different priorities. One method for OO software engineering uses design patterns. The idea behind design patterns is that most classes share some common design principles with a large category of other classes. By naming and recognizing each category, you can apply the same rules to designing new classes from a category you’re already familiar with. Each category is called a design pattern. Java uses design patterns extensively in its API. Describing design patterns in greater depth is beyond the scope of this book, but you might want to consult the Gang of Four’s popular book Design Patterns.

Another important idea in design is design by contract. Although this is also a rich, complex area of software engineering, the idea can be applied to methods in a straightforward way. For each method, you have a formal explanation of what its input should be, what its output should be, and what else can be changed in the process. For some languages and some segments of code, it’s possible to prove that a given method does exactly what it’s supposed to do. Nevertheless, Donald Knuth, a giant in computer science, is famous for having said, "Beware of bugs in the above code; I have only proved it correct, not tried it."

Once you have gotten your design to the implementation phase, there are a number of other techniques you can use to minimize errors. One interesting technique is pair programming, in which two programmers sit at a single computer and work together. Ideally, the programmer who is currently typing, often called the driver, is thinking about the immediate problems posed by the next few lines of code while the other programmer, often called the navigator, is thinking about the larger context of the program and watching for errors. Two sets of eyes are always beneficial when looking at something as detailed and confusing as a computer program.

In keeping with the theme of having more than one set of eyes looking at a program, it’s also useful to have the individuals who test the software be independent from those who develop it. By keeping the testers separate, they’re not infected by the assumptions and biases that the developers made while writing the software. Some communication between the two groups is necessary, but there’s value in black-box testing, which we’ll explain in the next subsection.

Another piece of general advice is to rely on standard libraries as much as possible. Reinventing your own libraries is partly a waste of time and partly dangerous because your own libraries haven’t undergone as much testing as the standard ones. Likewise, it makes your code less portable. Some expert developers might need to write special libraries for speed or memory efficiency, but they’re the exception, not the rule.

There are a number of Java specific implementation guidelines. People have written entire books about good software engineering in Java, and so we’ll only give a few obvious pointers.

Although it’s tempting to do so when working under time pressure, never write empty exception handlers. Doing so swallows exceptions blindly, giving the user no information about the errors in his or her program. By the same token, always make your exception handlers as narrow as possible. Simply putting catch(Exception e) at the end of any try-block has one of two possible outcomes: In one case your handler is vague and the user is informed that a general error of some kind has occurred. In the other your handler is more specific than it has a right to be. You might have assumed that a file I/O error was likely to occur and always report that failure. Instead, an ArrayOutOfBoundsException could happen and be mistakenly reported as a file I/O problem.

You should test the input to any public methods you write and throw a pre-determined exception if the input is invalid. Never use assertions to test input to public methods. In fact, you should never depend on assertions to catch errors since they must be turned on in the JVM to have effect. Assertions are great for debugging code before it’s released but have little or no value in the field.

Once you’ve designed and implemented your program (or ideally throughout the process of implementation), you should test it to see if it behaves as expected and required. The most common form of software testing done by students is a form of smoke test. A smoke test is a basic test of functionality. Such a test should simply run through the major features of a program and verify that they seem to work under ordinary circumstances. Often a student will barely finish the program before the deadline and be unable to perform anything but the most basic tests.

Smoke tests are useful because it’s pointless to test the finer details of a system that’s clearly broken, but the software engineering industry uses many other kinds of testing to ensure that a given piece of software meets its specification. We’ll briefly cover three broad areas of testing: black-box testing, white-box testing, and regression testing.

JUnit testing is used for unit testing Java. Unit testing is the process of testing separate software components that will eventually work together. By testing them individually, debugging can be done before interactions between different components make it more difficult to find the underlying bugs. After unit testing comes integration testing to test how the components work together. Finally, system testing is the testing of the complete, integrated system against its specifications.

One tool that used this idea was ConTest from IBM. Normal JVM operation makes some interleavings more likely than others. If the correct output is very likely and the incorrect is very unlikely, it’s easy for a tester to believe that the program works correctly. ConTest was a tool that instrumented class files after they’d been compiled by Java. When it instrumented these files, it added extra method calls into concurrent code designed to introduce some randomness into the system. By introducing sleep() and yield() methods in random places, the JVM could be forced into producing interleavings that would otherwise be unusual. The designers of ConTest used heuristics so that ConTest added this randomness in “smart” locations designed to maximize unusual interleavings and catch bugs.

ConTest was not a panacea. Although it revealed bugs that were rare, it still had to be combined with strong testing methodologies so that those bugs could be caught when they appeared. Another difficulty with using ConTest was that it couldn’t tell you where the problem happened or when it was likely to happen under normal circumstances. You were still dependent on your test design to reveal the source of the problem. ConTest also didn’t guarantee every possible ordering. Very rare bugs might not have manifested even after thousands of runs with ConTest instrumented code. Although ConTest was one of the most promising tools taking this approach, it is no longer available.

The open-source Lin-check framework has some similarities to ConTest. It was designed by Devexperts specifically to test data structures such as those we will discuss in Chapter 18. Like ConTest, Lin-check executes tests in parallel many times in an effort to find a concurrent interleaving that causes an error condition.

The Dl-check tool was also designed by Devexperts. Its goal is to find deadlocks that could happen in concurrent programs.

We hope we’ve convinced you of the value of using JUnit testing to unit test your programs. Of course, JUnit has limitations, especially when testing concurrent programs. JUnit uses exceptions to report failed test cases, but JUnit only reports exceptions from the main thread, not from any child threads that might be spawned. ConcJUnit allows exceptions thrown by child threads to be reported and also forces all child threads to join with the main thread.

In this way, it will be clear if any errors happened while a child thread was being executed, either causing an exception to be thrown or causing a child thread to fail to rejoin the main thread. ConcJUnit is intended as a drop-in replacement for JUnit, but only for JUnit 3 and 4. ConcJUnit is no longer under active development and is unlikely to have a version compatible with JUnit 5. ConcJUnit is part of a larger suite of open-source tools called Concutest maintained at the Concutest site.

ConcurrentUnit is another testing framework with annotations similar to those found in JUnit. Although it’s not intended as a replacement for JUnit, it has facilities like ConcJUnit that allow testers to discover when an exception occurs on child threads.

SpotBugs (previously called FindBugs), is a static analysis tool that examines programs for a long list of errors. SpotBugs looks for patterns that match known errors. Most of the errors that SpotBugs looks for have nothing to do with concurrency, but a whole section of its bug list is devoted to multithreaded correctness. SpotBugs can help you find incorrect usage of synchronization tools as well as unsafe concurrent library usage.

There are industry tools for debugging and optimizing threaded programs outside of Java. Intel^® produces software such as the Intel^® Inspector to find concurrent errors as well as the Intel^® Vtune™ Amplifier to help tune threaded programs. These products from Intel^®, like many concurrency tools, are focused on C/C++ and Fortran platforms. Historically, concurrency has been centered in the high performance and scientific computing markets. Java, in contrast, has been perceived as a slow language, better suited to desktop applications. As the role of concurrency continues to evolve, so will the tools to help programmers.