Start Concurrent: A Gentle Introduction to Concurrent Programming

If you don’t have a lot of experience with computer science, writing a computer program may seem daunting. The programs that run on your computer are complex and varied. Where would you start if you wanted to create something like Microsoft Word or Adobe Photoshop?

A computer program is a sequence of instructions that a computer follows. Even the most complex program is just a list of instructions. The list can get very long, and the computer can jump around the list when it makes decisions about what to do next.

Researchers continue to make progress in the field of artificial intelligence, but there is still an enormous gulf between artificial intelligence and human intelligence. Furthermore, it is the software whose intelligence those researchers strive to improve. Computer hardware is neither smart nor stupid because a computer has no intelligence to measure. A computer is a machine like a sewing machine or an internal combustion engine. It follows the instructions we give it blindly. It doesn’t have feelings or opinions about the instructions it receives. Computers do exactly what we tell them to and rarely make mistakes.

Once in a while, a computer will make a mistake due to faulty construction, a bad power source, or cosmic rays, but well over 99.999% of the things that go wrong with computers are because some human somewhere gave a bad instruction. This point highlights one of the most challenging aspects of programming a computer. How do you organize your thoughts so that you express to the computer exactly what you want it to do? If you give a person directions to a drug store, you might say, “Walk east for two blocks and then go into the third door on the right.” The human will fill in all the necessary details: Stopping for traffic, crossing at crosswalks, watching out for construction, and so on. Given a robot body, a computer would do exactly what you say. The instructions never mentioned opening the door, and so a computer might walk right through the closed door, shattering glass in the process.

What’s the right level of detail for instructions for a computer? It depends on the computer and the application. But how do we give these instructions? Programs are composed of instructions written in a programming language. In this book, we will use the Java programming language.

Why can’t the instructions be given in English or some other natural language? If the previous example of a robot walking through a glass door didn’t convince you, consider the quote from Groucho Marx, “One morning I shot an elephant in my pajamas. How he got into my pajamas, I’ll never know.”

Natural languages are filled with idioms, metaphors, puns, and other ambiguities. Good writers use these to give life to their poetry and prose, but our goal in this book is not to write poetry or prose. We want to write crystal clear instructions for computers.

Learning Java is not like learning Spanish or Swahili. Like most programming languages, Java is highly structured. It has fewer than 100 reserved words and special symbols. There are no exceptions to its grammatical rules. Don’t confuse the process of designing a solution to a problem with the process of implementing that solution in a programming language. Learning to organize your thoughts into a sequential list of instructions is different from learning how to translate that list into Java or another programming language, but there’s a tight connection between the two.

Learning to program is patterning your mind to think like a machine, to break everything down into simple logical steps. At first, Java code will look like gobbledygook. Eventually, it’ll become so familiar that a glance will tell you volumes about how a program works. Learning to program is not easy, but the kind of logical analysis involved is valuable even if you never program afterward. If you do need to learn other programming languages in the future, it will be easy once you’ve mastered Java.

This chapter takes a broad approach to solving problems with a computer, but we need an example to make some of the steps concrete. We use the following problem from physics as an example throughout this chapter.

A rubber ball is dropped on a flat, hard surface from height h. What’s the maximum height the ball will reach after the k^th bounce? We’ll discuss the steps needed to create a program to solve this problem in the next section.

The engineers who built the first digital computers also wrote the programs for them. In those days, programming was closely tied to the hardware, and the programs were not very long. As the capabilities of computers have increased and programming languages have evolved, computer programs have grown more and more complicated. Hundreds of developers, testers, and managers are needed to write a set of programs as complex as Microsoft Windows 10.

Organizing the creation of such complicated programs is challenging, but the industry uses a process called the software development lifecycle to help. This process makes large projects possible, but we can apply it to the simpler programs we’ll write in this book as well. There are many variations on the process, but we’ll use a straightforward version with the following five steps:

The software development lifecycle we presented above is a good guide, but it does not go into details. Different projects require different amounts of time and energy for each step. It’s also useful to focus on the steps because it’s less expensive to fix a problem at an earlier stage in development. It’s impossible to set the exact numbers, but some developers assume that it takes ten times as much effort to fix a problem at the current step than it would have at the previous step.

Now that we have a sense of the software development lifecycle, let’s look at an example using the sample ball bouncing problem to walk some of its steps.

Before we introduce any Java syntax, you should make sure you have a Java compiler set up so that you can follow along and test your solution. Programming is a hands-on skill. It’s impossible to improve your programming abilities without practice. No amount of reading about programming is a substitute for the real thing.

Where can you get a Java compiler? Fortunately, there are free options for almost every platform. Non-Windows computers may already have the Java Runtime Environment (JRE) installed, allowing you to run Java programs; however, many Java development options require you to have the Java Development Kit (JDK). Oracle may change the website, but at the time of writing you can download the JDK from the Oracle downloads site. Download a current version (e.g., Java SE 8 or 11) of the Java Platform, Standard Edition JDK and install it.

After having done so, you should be able to compile programs using the javac command, whose name is short for “Java compiler.” To do so, open a terminal window, also known as a command line interface or the console. To open the terminal in Windows, choose the Windows Powershell option from the Start Menu. To open the terminal in macOS, select Terminal from the Utilities folder. Different distributions of Linux have different ways of accessing the terminal, but Linux users are usually familiar with their terminal.

Provided that you have your path set correctly, you should be able to open the terminal, navigate to a directory containing files that end in .java, and compile them using the javac command. For example, to compile a program called Example.java to bytecode, you would type:

Compiling the program creates a .class file, in this case, Example.class. To run the program contained in Example.class, you would type:

Doing so fires up the JVM, which uses the JIT compiler to compile the bytecode inside Example.class into machine code and run it. Note that you type only Example not Example.class when specifying the program to run. Using just these commands from the terminal, you can compile and run Java programs. The command line interface used to be the only way to interact with a computer, and though it seems primitive at first, the command line has amazing power and versatility.

To use the command line interface to compile your own Java program, you must first create a text file with your Java code in it. The world of programming is filled with many text editor applications whose only purpose is to make writing code easier. These editors are not like Microsoft Word: They are not used to format the text into paragraphs or apply bold or italics. Their output is a “plain” text file, containing only unformatted characters, similar to the files created by Notepad. Some text editors have advanced features useful for programmers, such as syntax highlighting (marking special words and symbols in the language with colors or fonts), language-appropriate auto-completion, and powerful find and replace tools. Two of the most popular text editors for command line use are vi-based editors, particularly Vim, and Emacs-based editors, particularly GNU Emacs.

Many computer users, however, are used to a graphical user interface (GUI), where a mouse can be used to interact with windows, buttons, text boxes, and other elements of a modern user interface. There are Java programming environments that provide a GUI from which a user can write Java code, compile it, execute it, and even test and debug it. Because these tools are integrated into a single program, these applications are called integrated development environments (IDEs).

Two of the most popular Java IDEs are Eclipse and IntelliJ IDEA. Eclipse is open-source, free, and available here. Although some versions of IntelliJ IDEA cost money, the Community edition of IntelliJ IDEA is free and available here.

Which text editor or graphical IDE you use is up to you. Programming is a craft, and every artisan has favorite tools. Most of the content of this book is completely independent from the tools you use to write and compile your code. One exception is Chapter 16, in which we briefly discuss the debugging tools in Eclipse and IntelliJ IDEA.

If you choose Eclipse, IntelliJ IDEA, or another complex IDE, you may wish to read online tutorials to get started. These IDEs often require the user to make a project and then create Java files inside. The idea of a project containing related source code files is a useful one and is very common in software engineering, but it is not a part of Java itself.

The first rule of Java is that all code goes inside of a class. A class is a container for blocks of code called methods, and it can also be used as a template to create objects. We’ll talk a bit more about classes in this chapter and then focus on them heavily in Chapter 9.

For now, you only need to remember that every Java program has at least one class. It is possible to put more than one class in a file, but you can only have one top-level public class per file. A public class is one that can be used by other classes. Almost every class in this book is public, and they should be clearly marked as such. To create a public class called Example, you would type the following:

A few words in Java have a special meaning and cannot be used for other purposes (like the name you give a class). These are called keywords or reserved words. The keyword public marks the class as public. The keyword class states that you are declaring a class. All keywords are lowercase in Java.

The name Example gives the name of the class. By convention, all class names start with a capital letter. The braces ({ and }) mark the start and end of the contents of the class. Right now, our class contains nothing.

This text should be saved in a file called Example.java. It’s required that the name of the public class matches the file that it’s in, including capitalization. Once Example.java has been saved, you can compile it into bytecode. However, since there’s nothing in class Example, you can’t run it as a program.

A program is a list of instructions, and that list has to start somewhere. For a normal Java application, that place is the main() method. Throughout this book, we always append parentheses () to mark the name of a method. If we want to do something inside of Example, we’ll have to add a main() method like so:

There are several new items now. As before, public means that other classes can use the main() method. The static keyword means that the method is associated with the class as a whole and not a particular object. The void keyword means that the method does not give back a result. The word main is obviously the name of the method, but it has to be spelled exactly that way (including capitalization) to work. Perhaps the most confusing part is the expression String[] args, which is a list of text (strings) given as input to the main() method from the command line. As with the class, the braces mark the start and end of the contents of the main() method, which is currently empty.

Right now, you don’t need to understand any of this. All you need to know is that, to start a program, you need a main() method and its syntax is always the same as the code listed above. If you save this code, you can compile Example.java and then run it, and…​nothing happens! It’s a perfectly legal Java program, but the list of instructions is empty.

An important thing for a Java program to do is to communicate with the outside world (where humans live). First, let’s look at printing data to the command line and reading data in from the command line.

If you’re used to GUI-based programs, you might wonder how to do input and output with a GUI instead of on the command line. GUIs can become complex, but in this chapter we introduce a simple way to do GUI input and output and expand on it further in Chapter 7. Then, we go into GUIs in much more depth in Chapter 15.

A limited tool for displaying output and reading input with a GUI is the JOptionPane class. This class has a complicated method called showMessageDialog() that opens a small dialog box to display a message to the user. If we want to create the equivalent of the command-line program that displays the number 42, the code would be as follows.

Figure 2.3 shows what the resulting GUI might look like.

One way to do input with a GUI uses the showInputDialog() method, which is also inside the JOptionPane class. The showInputDialog() method returns a value. This means it gives back an answer which you can store into a variable by putting the method call on the right hand side of an assignment statement. Otherwise, it’s nearly the same as showMessageDialog(). The following program prompts the user for his or her favorite word with a showInputDialog() method and then displays it again using a showMessageDialog() method.

Note that whatever the user typed in will be stored in word. Finally, the last line of the program displays this information with showMessageDialog(). Figure 2.4 shows the GUI as the user is entering input.

Remember that the value returned from the showInputDialog() method is always text; that is, it always has type String. Although there are lots of great things you can do with a String value, you can’t do normal arithmetic like you can with an integer or a floating-point number. However, there are ways to convert a String representation of a number to the number itself. If you have a String that represents an integer, you use the Integer.parseInt() method to convert it. If you have a String that represents a floating-point number, you use the Double.parseDouble() method to convert it. The following segment of code illustrates these issues.

You might wonder why the computer isn’t smart enough to know that "23" means 23. Remember, the computer has no intelligence. If something is marked as text, it doesn’t know that it can interpret it as a number. What kind of data something is depends on its type, which doesn’t change. We’ll discuss types more deeply in Chapter 3.

The next example uses these two type conversion methods with methods from JOptionPane in a GUI-based solution to subproblem 1 of the bouncing ball problem.

Writing good Java code has some similarities to writing effectively in English. There are rules you have to follow in order to make sense, but there are also guidelines you should follow to make your code easier to read for yourself and everyone else.

In Example 2.2, we made sure we understood the problem and then formed a three-part plan to read in the input, compute the height of the bounce, and then output it.

In Program 2.1, we implemented subproblem 1, reading the input from the command line. In Program 2.4, we implemented subproblem 2, computing the height of the final bounce. In Program 2.5, we implemented subproblem 3, displaying the height that was computed. In the final, integrated program, the portion of the code that corresponds to solving subproblem 1 is below.

With the imports, class declaration, and main() method set up by the solution to subproblem 1, the solution to subproblem 2 is very short.

The solution to subproblem 3 and the braces that mark the end of the main() method and then the end of the class only take up a few more lines.

If you prefer a GUI for your input and output, we can integrate the GUI-based versions of the solutions to subproblems 1, 2, and 3 from Program 2.1, Program 2.4, and Program 2.6. The final program is below. It only differs from the command line version in a few details.

Testing and maintenance are key elements of the software engineering lifecycle and often take more time and resources than the rest. However, we only discuss them briefly here.

The ball bouncing problem is not complex. There are a few obvious things to test. We should pick a “normal” test case such as a height of 15 units, a coefficient of restitution of 0.3, and 10 bounces. The height should be 15 ⋅ 0.3¹⁰ = 0.0000885735. The result computed by our program should be the same, ignoring floating-point error. We can also check some boundary test cases. If the coefficient of restitution is 1, the ball should bounce back perfectly, reaching whatever height we input. If the coefficient of restitution is 0, the ball doesn’t bounce at all, and the final height should be 0.

Our code does not account for users entering badly formatted data like two instead of 2. Likewise, our code does not detect invalid values such as a coefficient of restitution greater than 1 or a negative number of bounces. An industrial-grade program should. We’ll discuss testing further in Chapter 16.

As with most of the problems we discuss in this book, issues of maintenance will not apply: we don’t have a customer base to keep happy. Even so, it’s a good thought exercise to imagine a large-scale version of this program that can solve many different kinds of physics problems. Who are likely to be your clients? What kinds of bugs are likely to creep into such a program? How would you provide bug-fixes and develop new features?

The terms parallelism and concurrency are often confused and sometimes used interchangeably. Parallelism or parallel computing occurs when multiple computations are being performed at the same time. Concurrency occurs when multiple computations may interact with each other. The distinction is subtle since many parallel computations are concurrent and vice versa.

An example of parallelism without concurrency is two separate programs running on a multicore system. They are both performing computations at the same time, but for the most part, they aren’t interacting with each other. Concurrency issues might arise if these programs try to access a shared resource, such as a file, at the same time.

An example of concurrency without parallelism is a program with multiple threads of execution running on a single-core system. These threads will not execute at the same time as each other. However, the OS or run-time system will interleave the execution of these threads, switching back and forth between them whenever it wants to. Since these threads can share memory, they can still interact with each other in complicated and often unpredictable ways.

With multicore computers, we want good and effective parallelism, computing many things at the same time. Unfortunately, striving to reach parallelism often means struggling with concurrency and carefully managing the interactions between threads.

Imagine that the evil Lellarap aliens are attacking Earth. They have sent an extensive list of demands to the world’s leaders, but only a few people, including you, have mastered their language, Lellarapian. To save the people of Earth, it’s imperative that you translate their demands as quickly as possible so world leaders can choose a course of action. If you do it alone, as illustrated in Figure 2.5(a), the Lellaraps might attack before you finish.

In order to finish the work faster, you hire a second translator whose skills in Lellarap are as good as yours. As shown in Figure 2.5(b), you divide the document into two nearly equal parts, Document A and Document B. You translate Document A, and your colleague translates Document B. When both translations are complete, you merge the two, check the translation, and send the result to the world’s leaders.

Translating the demands alone is a sequential approach. In this context, sequential mean non-parallel. Translating the demands with two people is a parallel approach. It’s concurrent as well because you have to decide how to split up the document and how to merge it back together.

If you wrote a computer program to translate the demands using the sequential approach, you’d produce a sequential program. If you wrote a computer program that uses the approach shown in Figure 2.5(b), it would be a concurrent program. A concurrent program is also referred to as a multi-threaded program. Threads are sequences of code that can execute independently and access each other’s memory. Imagine you’re one thread of execution and your colleague is another. Thus, the concurrent approach will have at least two threads. It may have more if separate threads are used to divide up the document or merge it back together.

Because we’re interested in the time the process takes, we’ve labeled different tasks in Figure 2.5 with their running times. We let t_s be the time for one person to complete the translation. The times t₁ through t₄ mark the times needed to complete tasks 1 through 4, indicated in Figure 2.5(b).

A sequential program, like the single translator, uses a single processor on a multi-processor system or a single core on a multicore chip. To speed up the solution of a program on a multicore chip, it may be necessary to divide a problem so that different parts of it can be executed concurrently.

This process of dividing up a problem falls into the category of domain decomposition, task decomposition, or some combination of the two. In domain decomposition, we take a large amount of data or elements to be processed and divide up the data among workers that all do the same thing to different parts of the data. In task decomposition, each worker is assigned a different task that needs to be done. The following two examples explore each of these approaches.

In the example above, the tasks are the same (measuring the area) but are performed on two different input domains (the floors). This type of task division is also known as domain decomposition. Here, to achieve concurrency, we take the domain of the problem (the house) and divide it into smaller subdomains (its floors). Then, each processor (or robot in this example) performs the same task on each subdomain. When done, the final answer is found by combining the answers. Running the robots on each floor is purely parallel, but combining the answers is concurrent since some interaction between the robots is necessary.

Another way of solving a problem concurrently is to divide it into fundamentally different tasks. The tasks could be executed on different processors and perhaps on different input domains. Eventually, some coordination of the tasks must be done to generate the final result. The next example illustrates such a division.