it on to the Parent
class.
11.3.4.  It’s possible to override a parent method in the child class. Then, when that method is called on child objects, the new method will be called. The new method has exactly the same name and parameters. The return type must either be exactly the same or a child class of the original return type.
We can return to the Fish
class example and make a new kind of fish
that never moves.
public class LazyFish extends Fish {
public void swim() {
System.out.println("I think I'll just sit here.");
}
}
Whenever someone calls the swim()
method on a LazyFish
object, it
will announce that it’s going to sit where it is. Its location isn’t
updated, and its energy doesn’t change.
On the other hand, we could create another child class that swims twice
as fast as the original Fish
.
public class FastFish extends Fish {
public void swim() {
super.swim();
super.swim();
}
}
Every time swim()
is called on objects of type FastFish
, those
objects will call the swim()
method from Fish
twice. Thus, this fish
will move twice as fast (and consume twice as much energy). Because the
location
and energy
fields are private
, we must use methods from
Fish
to affect them. Note the use of the keyword super
, allowing us
to specify that we want to call the swim()
method from Fish
and not
just call the same method from FastFish
again. Using the super
keyword, we can call methods from the parent. If the parent didn’t
override a method from an ancestor class, we can still use super
to
call a method from the most recent ancestor class that did implement the method.
However, Java does not allow us to skip over a parent method to call a
grandparent method if there’s an implementation in the parent class. In
other words, there’s no way to call something like a
super.super.swim()
method.
Just as methods are overridden, fields are hidden. It’s perfectly legal to declare a field with the same name as a field from a parent class, but the new field will then be used instead of the old one.
public class A {
protected int a;
public int getA() { return a; }
public void setA(int value) { a = value; }
}
public class B extends A {
protected int a;
public void setA(int value) { a = value; }
}
Class B
is a child of class A
and declares a field called a
,
hiding a field of the same name from A
. However, which a
is which
can cause some confusion. Consider the following fragment of code.
A objectA = new A();
B objectB = new B();
objectA.setA(5);
objectB.setA(10);
System.out.println("A = " + objectA.getA());
System.out.println("B = " + objectB.getA());
The output of this code is:
A = 5 B = 0
Calling the setA()
method on an A
object sets the a
field inside
of A
. Calling the overridden setA()
method on a B
object sets the
a
field inside of B
, but since the getA()
method hasn’t been
overridden, the a
field from the A
parent class part of B
is
returned. Since that a
field in B
hasn’t been given a value, it
still has the default value of 0
. Both a
fields exist inside of B
,
but the methods are poorly designed, leaving one field capable only of
being set and the other capable only of being retrieved.
11.3.5. The Object
class
You may not have realized it, but every class you’ve created in Java uses
inheritance. To provide uniformity, the designers of Java made every
class the child (or grandchild or great-grandchild…) of a class
called Object
. When you omit the extends
clause in a class
definition, you’re making that class a direct child of Object
.
As a consequence, all classes in Java are guaranteed to have the following methods.
| Method | Purpose |
|---|---|
|
Make a separate copy of an object. |
|
Determine if two objects are the same. |
|
Perform cleanup when an object is garbage collected. Similar to a destructor in C++. Rarely used. |
|
Find out what the class type of a given object is. |
|
Get the hash code for an object, useful for making hash tables of objects. |
|
Used for synchronization with threaded programs. More in Chapter 14. |
|
Same as previous. |
|
Get a |
|
Used with |
Java provides basic implementations for most of these, but if you want
them to work well for your object, you’ll have to override some of
them with appropriate methods. For example, the Object
version of
toString()
returns the virtual address of the object in JVM memory,
which is not very useful information.
Nevertheless, API classes usually have good equals()
and toString()
methods. Aside from making a few useful methods available, having a
common ancestor for all classes means that you can store any object in
an Object
reference. An array of type Object
can hold anything,
provided that you know how to retrieve it. We discuss the finer points
of inheritance and polymorphism in Chapter 17 and
how to build lists and other data structures using Object
references
in Chapter 18.
11.4. Examples: Problem solving with inheritance
Here are two extended examples showing how we can use inheritance to solve problems. First, we revisit the student roster example from Chapter 9 and then move onto an inheritance hierarchy of polygons.
The Student
class we created in Example 9.1 is useful
but works only for undergraduate students. With only a few additions, we
can make it suitable for graduate students as well. First, let’s take
another look at the Student
class.
public class Student {
public static final String[] YEARS = {"Freshman", "Sophomore", "Junior", "Senior"};
private String name;
private int year;
private double GPA;
public Student(String name, int year, double GPA) {
setName(name);
setYear(year);
setGPA(GPA);
}
public void setName(String name) { this.name = name; }
public void setYear(int year) { this.year = year; }
public void setGPA(double GPA) {
if(GPA >= 0 && GPA <= 4.0)
this.GPA = GPA;
else
System.out.println("Invalid GPA: " + GPA);
}
public String getName() { return name; };
public int getYear() { return year; };
public double getGPA() { return GPA; };
public String toString() {
return name + "\t" + YEARS[year] + "\t" + GPA;
}
}
We want to create a GraduateStudent
class that inherits from
Student
. We need to add a thesis topic for each graduate student.
Likewise, we need to update the toString()
method so that outputs the
appropriate data. We use 4
as the year value for graduate students.
Student
to add graduate student capabilities.public class GraduateStudent extends Student {
private String topic; (1)
public GraduateStudent(String name, double GPA, String topic) {
super(name, 4, GPA); (2)
setTopic(topic);
}
public void setTopic(String topic) { this.topic = topic; }
public String toString() { (3)
return getName() + "\tGraduate\t" + getGPA() + "\tTopic: " + topic;
}
}
| 1 | Because we’re inheriting most of the fields we need, we only need to
declare the topic field. |
| 2 | Then, in the GraduateStudent constructor,
we call the parent constructor with the name, year, and GPA and then set
topic to the input value. |
| 3 | Finally, we override the toString() method so that "Graduate" and
the thesis topic are output. Note that we must use the getName() and
getGPA() accessors since those fields are private in Student . |
Most code that uses Student
objects should be able to incorporate
GraduateStudent
objects easily. Code that creates Student
objects
from input will need slight modifications to handle the thesis topic.
Also, old code that only expects values of 0
, 1
, 2
, or 3
for
year may need to be modified so that it doesn’t break.
Let’s examine a class hierarchy used to create several different
polygons. Our base class needs to be general. It can represent any kind
of closed polygon, using an array of Point
objects. The Point
library class
is a way to package up x
and y
values of type int
. Each coordinate
in the array gives the next vertex of the polygon.
import java.awt.*; (1)
public class Polygon {
protected Point[] points; (2)
public Polygon(Point[] points) { (3)
this.points = points;
}
| 1 | The import statement allows us to use the Point class as well as the
Graphics class. |
| 2 | Our array of type Point is declared protected so
that the child classes we want to create can access it directly. |
| 3 | The constructor takes an array of type Point and stores it. |
public double getPerimeter() { (1)
double perimeter = 0.0;
for(int i = 0; i < points.length - 1; i++)
perimeter += points[i].distance(points[i + 1]);
perimeter += points[0].distance(points[points.length - 1]);
return perimeter;
}
public void draw(Graphics g) { (2)
for(int i = 0; i < points.length - 1; i++)
g.drawLine(points[i].x, points[i].y, points[i+1].x, points[i+1].y);
g.drawLine(points[0].x, points[0].y,
points[points.length - 1].x, points[points.length - 1].y);
}
}
| 1 | The getPerimeter() method can determine the length
of the perimeter by adding the lengths of the segments connecting the
vertices. Although it’s also possible to determine the area enclosed by a list of
vertices, the algorithm is complex. |
| 2 | The draw() method draws the
polygon by drawing each line segment that connects adjacent vertices. We
discuss the Graphics class in Chapter 15. If you compile and run this code, please note that in
Java graphics, like many computer graphics environments, the upper left
hand corner of the screen or window is considered (0,0), and
y values increase going downward, not upward. |
The number of things that can be done with this very general Polygon
class are limited, but with this basic parent class defined, we can
design a Triangle
class as a child of it.
import java.awt.*; (1)
public class Triangle extends Polygon {
public Triangle(int x1, int y1, int x2, int y2, int x3, int y3) { (2)
super(toPointArray(x1, y1, x2, y2, x3, y3));
}
protected static Point[] toPointArray(int x1, int y1, int x2, int y2, int x3, int y3) {
Point[] array = {new Point(x1, y1), new Point(x2, y2), new Point(x3, y3)}; (3)
return array;
}
| 1 | Again, the import statement is for the Point class. |
| 2 | One reasonable
constructor for a triangle takes in six values, giving the
x and y coordinates of the three vertices of
the triangle. Of course, the Polygon class requires an array of type
Point , but the super constructor must be the first line of the
Triangle constructor. |
| 3 | To solve this problem, we create a static
method to package the values into an array. We could have done the same
thing in the argument list of the super constructor, but it would have
looked messier. The toPointArray() is protected because there’s no
reason to let external code have access to it. |
public String getType() {
double a = points[0].distance(points[1]);
double b = points[1].distance(points[2]);
double c = points[2].distance(points[0]);
if(a == b && b == c)
return "Equilateral";
if(a == b || b == c || a == c)
return "Isosceles";
return "Scalene";
}
}
Finally, the getType()
method allows us to do something specific with
triangles. We can use the distance()
method from the Point
class to
find the length of each of the three sides. By comparing these lengths,
we can determine whether the triangle represented is equilateral,
isosceles, or scalene. Of course, computing the perimeter and drawing
the triangle are already taken care of by the Polygon
class.
We can easily make a Rectangle
class along the same lines.
import java.awt.*;
public class Rectangle extends Polygon {
public Rectangle(int x, int y, int length, int width) { (1)
super(toArray(x, y, length, width));
}
protected static Point[] toArray(int x, int y, int length, int width) { (2)
Point[] array = {new Point(x, y), new Point(x + length, y),
new Point(x + length, y + width), new Point(x, y + width)};
return array;
}
public int getArea() { (3)
int length = points[1].x - points[0].x;
int width = points[2].y - points[1].y;
return length * width;
}
}
| 1 | The constructor is similar to the Triangle constructor except that the
upper left corner of the rectangle is specified, along with the length
and the width. |
| 2 | From these values, the appropriate array of Point
values is generated. |
| 3 | The rectangle-specific code that we add is the
getArea() method, which determines the length and width of the
rectangle by examining the points array and then calculates area. |
Using inheritance as form of specialization, we can go one step further
and make a Square
class.
public class Square extends Rectangle {
public Square(int x, int y, int size) {
super(x, y, size, size);
}
}
This very short class uses everything available in Rectangle
but
simplifies the constructor slightly so that the user doesn’t have to
enter both length and width.
11.5. Solution: Boolean circuits
Here we present our solution to the Boolean Circuits problem. First, we
define a parent class for all circuit components, called Gate
.
public class Gate {
private String name;
public Gate(String name) { this.name = name; }
public String getName() { return name; }
public String toString() {
return getName() + ": " + getValue();
}
public boolean getValue() { return false; }
}
The Gate
class doesn’t do anything except set up ways to store a name
and to get a value. It
doesn’t really matter what getValue()
gives back for Gate
, but we
can say that it’s false
.
In principle, it shouldn’t be possible to create an object of type Gate
,
UnaryOperator
, or BinaryOperator
. Classes that are designed only to
be parent classes and never to be instantiated are called abstract classes and
are discussed in Section 17.3.1.
From Gate
, we can define the most basic circuit
components: gates whose value is either always true or always false.
public class True extends Gate {
public True() { super("true"); }
public boolean getValue() { return true; }
}
public class False extends Gate {
public False() { super("false"); }
public boolean getValue() { return false; }
}
To conform with the constructor for Gate
, these new classes must pass
a String
giving their name to the super
constructor. The values
returned by the getValue()
method are clear. Next, we want to create a
class that can be used as a parent for all unary operators.
public class UnaryOperator extends Gate {
private Gate input;
public UnaryOperator(String name) { super(name); }
public void setInput(Gate input) { this.input = input; }
public Gate getInput() { return input; }
}
The important addition in the UnaryOperator
class is the input
field. Any unary operator must have a single input gate that it operates
on. This class provides a mutator and accessor for input
, as well as
an appropriate constructor. From UnaryOperator
, we can derive two
specific operators.
public class Output extends UnaryOperator {
public Output(int i) { super("OUTPUT " + i); }
public boolean getValue() { return getInput().getValue(); }
}
The Output
class takes in an int
value and uses it to make a
numbered name. Its getValue()
method simply returns the value of its
input. The Output
class doesn’t do anything except serve as a marker
for circuit output.
public class Not extends UnaryOperator {
public Not() { super("NOT"); }
public boolean getValue() { return !getInput().getValue(); }
}
The Not
class uses "NOT"
as the name supplied to
the super
constructor and returns the logical NOT of the value of its
input.
Just as we did for unary operators, we also need a parent class for binary operators.
public class BinaryOperator extends Gate {
private Gate operand1;
private Gate operand2;
public BinaryOperator(String name) { super(name); }
public Gate getOperand1() { return operand1; }
public Gate getOperand2() { return operand2; }
public void setOperand1(Gate operand) { operand1 = operand; }
public void setOperand2(Gate operand) { operand2 = operand; }
}
A BinaryOperator
has two Gate
fields, operand1
and operand2
,
representing the inputs to the operator. The BinaryOperator
class has
an appropriate constructor and then accessors and mutators for the
operands. With BinaryOperator
as a parent, only a few lines of code
are necessary to define any logical binary operator.
public class And extends BinaryOperator {
public And() { super("AND"); }
public boolean getValue() {
return getOperand1().getValue() && getOperand1().getValue();
}
}
public class Or extends BinaryOperator {
public Or() { super("OR"); }
public boolean getValue() {
return getOperand1().getValue() || getOperand1().getValue();
}
}
public class Xor extends BinaryOperator {
public Xor() { super("XOR"); }
public boolean getValue() {
return getOperand1().getValue() ^ getOperand1().getValue();
}
}
In each case, a constructor passes the name of the gate to the super
constructor. Then, each getValue()
method gets the values from the two
operands and combines them with AND, OR, or XOR, respectively. This
design allows the programmer to focus only on the important element of
each class. Adding new classes for NAND, NOR, or any other possible
logical binary operator would be quick.
The client code that uses these classes to simulate a circuit follows.
import java.util.*;
public class BooleanCircuit {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int count = in.nextInt();
Gate[] gates = new Gate[count];
String name;
int value;
First we have the import
needed for Scanner
. In main()
, we read in the
total number of gates, create an array of type Gate
of that length,
and declare a few useful temporary variables.
// Create gates
for(int i = 0; i < count; i++) {
name = in.next().toUpperCase();
if(name.equals("true"))
gates[i] = new True();
else if(name.equals("false"))
gates[i] = new False();
else if(name.equals("AND"))
gates[i] = new And();
else if(name.equals("OR"))
gates[i] = new Or();
else if(name.equals("XOR"))
gates[i] = new Xor();
else if(name.equals("NOT"))
gates[i] = new Not();
else if(name.equals("OUTPUT")) {
value = in.nextInt();
gates[i] = new Output(value);
}
}
Then, we parse the input, creating an appropriate gate based on the name read in. In the case of an OUTPUT gate, we must also read in a number so that we can identify which OUTPUT gate is which later.
//connect gates
while(in.hasNextInt()) {
value = in.nextInt();
name = gates[value].getName();
if(name.equals("AND") || name.equals("OR") || name.equals("XOR")) {
BinaryOperator operator = (BinaryOperator)gates[value];
operator.setOperand1(gates[in.nextInt()]);
operator.setOperand2(gates[in.nextInt()]);
}
else if(name.equals("NOT") || name.startsWith("OUTPUT")) {
UnaryOperator operator = (UnaryOperator)gates[value];
operator.setInput(gates[in.nextInt()]);
}
}
As long as there’s input remaining, we read in an index. Based on the name of the gate at that index in the array, we either read in two more indexes (for binary operators) or just a single additional index (for unary operators). In either case, we set the input or inputs of the operator to the gate or gates at those indexes.
// Compute output
for(int i = 0; i < count; i++)
if(gates[i].getName().startsWith("OUTPUT"))
System.out.println(gates[i]);
}
}
Finally, the simulation of the circuit is surprisingly simple. We look
through array until we find a gate whose name starts with "OUTPUT"
.
Then, we print out its value. In order to determine its value, it will
ask its input what its value is, which in turn will ask for the values
from its input. The toString()
in the Gate
class will assure us that
the final output is nicely formatted. This system accommodates any
number of output gates connected arbitrarily, as long as the circuit has
no loops inside of it, such as an AND gate whose output is also one of
its inputs.
11.6. Concurrency: Inheritance
Like interfaces, inheritance in Java is not closely related to concurrency. However, two ways in which inheritance interacts with concurrency deserve attention.
The first is the Thread
class. Each thread of execution in Java
(except the main thread) is managed with a Thread
object or an object
whose type inherits from Thread
. Creating such types is done by
extending Thread
, just as you would extend any other class. Further
information about extending Thread
for concurrency is given in
Section 13.4. Extending the Thread
class to make
your own customized threads of execution is an alternative to
implementing the Runnable
interface mentioned in
Section 10.6 and is discussed in greater detail in
Section 13.4.5.
The second interaction between inheritance and concurrency is again very
similar to the problem with interfaces and concurrency: There’s no way
to specify that a method is thread-safe. Recall that it’s not allowed
to use the synchronized
keyword on a method in an interface
declaration. Likewise, there’s no restriction on overriding a
synchronized method with a non-synchronized method or vice versa.
The rules for overriding methods in Java guarantee that an object of a child class is usable anywhere that an object of the parent class is usable. Thus, you cannot override a public method with a private one, reducing the visibility of a method. We discuss a similar restriction with exceptions in Section 17.3.4.
If it has these restrictions, why doesn’t Java prevent a synchronized method from being overridden by a non-synchronized method? In the first place, a non-synchronized method can be used anywhere a synchronized one could (unlike a private method, which is not accessible everywhere a public one is). In the second, the designers of Java put thread safety in the category of implementation details left up to the programmer. Some classes need specific methods to be synchronized and others (even child classes) do not. However, if you override a class with a synchronized method, it’s safest to mark your method synchronized as well.
11.7. Exercises
Conceptual Problems
-
Give three advantages of using inheritance instead of copying and pasting code from a parent class. Are there any disadvantages to using inheritance?
-
Consider classes
Radish
andCarrot
which both extend classVegetable
and implement interfaceCrunchable
. Which of the following sets of assignments are legal and why?-
Radish radish = new Radish();
-
Radish radish = new Vegetable();
-
Vegetable vegetable = new Radish();
-
Crunchable crunchy = new Radish();
-
Radish radish = new Carrot();
-
-
In the context of inheritance, the keyword
super
can be used for two different purposes. What are they? -
Consider the following class definitions.
public class A { private String value; public A(String s) { value = "A" + s + "A"; } public String toString() { return value; } } public class B extends A { public B(String s) { super("B" + s + "B"); } } public class C extends B { public C(String s) { super("C" + s + "C"); } }
What’s output by the following code fragment?
C c = new C("ABC"); System.out.println(c);
-
Beginning Java programmers often confuse package-private access (no explicit specifier) with
public
access. How is this confusion possible when default access is more constrained than bothpublic
andprotected
access? (Hint: The file system plays a role.) -
What are the similarities and differences between overloading a method and overriding a method?
-
What’s field hiding? How can software bugs arise from this Java feature?
-
Give reasons why the designers of Java decided not to allow multiple inheritance. Would you have made the same decision? Why or why not?
-
Draw a class hierarchy establishing a sensible relationship between the
Human
,Soldier
,Sailor
,Marine
,General
, andAdmiral
classes. For this class hierarchy, refer to the U.S. military structure in which the U.S. Marine Corps is a part of the U.S. Navy.
Programming Practice
-
Create an
InternationalStudent
class that extendsStudent
. It should includeString
fields for country of origin and visa status. It should include mutator and accessor methods for these two new fields. -
Add
Pentagon
andHexagon
classes that extend thePolygon
class. The constructor for each class should take an x, y and radius value, each ofint
type. Both classes should be implemented to create regular polygons, that is, polygons in which all five or six sides have the same length. The x and y values should give the center of the polygon, and each of the five or six points should be the radius distance away from that center.Because the internal structure of
Polygon
keeps all vertices asPoint
values, the x and y coordinates of the points must beint
values. This requirement will force you to round these x and y coordinates after using trigonometry to determine their locations. As a result, the final pentagons and hexagons stored and displayed will be slightly irregular. -
The inheritance design of our solution to the Boolean circuits problem given in Section 11.5 makes adding new gates easy. Add classes that implement a NAND gate and a NOR gate. Then, rewrite the
main()
method ofBooleanCircuit
to accommodate these two extra classes. -
Re-implement the object hierarchy in the solution from Section 10.5 to the sort it out problem. This time, let the
Cat
,Dog
, andPerson
classes extend theCreature
class defined below.public class Creature implements Ageable, Weighable { protected int age; protected double weight; public Creature(int age, double weight) { this.age = age; this.weight = weight; } public int getAge() { return age; } public double getWeight() { return weight; } }
Refactor your code so that the
Cat
,Dog
, andPerson
classes are as short as possible. How many lines of code do you save? -
Design a celestial body simulator. You’ll need to create a class containing fields for the x, y, and z locations, x, y, and z velocities, radii, and masses of each object. For each time step of length t, you must do the following.
-
Compute the sum of forces exerted on each body by every other body. The equation for gravitational force on body b exerted by body a is given by the following equation.
As mentioned in Example 8.1, the gravitational constant G = 6.673 × 10-11 N⋅m2⋅kg-2. Also, |rab| is the distance between the centers of objects a and b. Finally, the unit vector between the centers of the two objects is given by the equation below.
-
Compute the x, y, and z components of the acceleration vector a for each object using the equation F = ma once the sum of forces has been calculated.
-
Update the x, y, and z components of the velocity vector v for each object using the equation vnew = vold + at.
-
Experiments
-
Inheritance is a powerful technique, but it comes with some overhead costs. Create a class called
A
with the following implementation.public class A { protected int a; }
Then, create 25 more classes named
B
throughZ
. ClassB
should extendA
and add aprotected
int
field calledb
. Continue in this manner, with each new class extending the previous one and adding anint
field named the lowercase version of the class name. Thus, if you create an object of typeZ
, it will contain, through inheritance, 26int
fields nameda
throughz
. But for a singleZ
object to be created, it must call 27 (Z
back throughA
plusObject
) constructors. You may wish to use the file I/O material in Chapter 20 to write a program to create all these classes so that you do not have to do so by hand.Finally, create a new class called
All
which contains 26protected
fields ofint
type nameda
throughz
. Now, the purpose of creating all these classes is to compare the time needed to instantiate an object of typeZ
with one of typeAll
, though they both only contain 26int
fields nameda
throughz
.Create an array of 100,000 elements of type
Z
and then populate it with 100,000Z
objects. Time this process. Create an array of 100,000 elements of typeAll
and then populate that array with 100,000All
objects. You may wish to use theSystem.nanoTime()
method described in Chapter 13 to accurately time these processes. Is there a significant difference in the times you found?
12. Exceptions
The vulgar mind always mistakes the exceptional for the important.
12.1. Problem: Bank burglary
Let’s consider a problem in which various aspects of a bank burglary are modeled as Java objects. You want to write some code that will accomplish the following steps:
-
Disable the burglar alarm
-
Break into the bank
-
Find the vault
-
Open the vault
-
Carry away the loot
But any number of things could go wrong! When trying to disable the burglar alarm, you might set it off. When you try to break into the bank, you might have thought that you’d disabled the burglar alarm but actually failed to do so. The door of the bank might be too difficult to open. The vault might be impossible to find, or the vault might be impossible to open. It could even be empty! The money might be made of enormous gold blocks that are too heavy to carry away. Finally, at any time during the heist, a night watchman might catch you in the act.
If you’re the criminal mastermind who planned this deed, you need to know if (and preferably how) your henchman bungled the burglary. You need a simple system that can inform you of any errors that have occurred along the way. Likewise, you need to be able to react differently depending on what went wrong.
We are going to model each of these error conditions with Java
exceptions. An exception is how Java indicates exceptional or
incorrect situations inside of a program. These exceptions are thrown
when the error happens. You must then write code to catch the error
and deal with it appropriately. The bank burglar program will deal with
three different classes, Bank
, Vault
, and Loot
.
The Bank
class has three methods, disableAlarm()
, breakIn()
, and
findVault()
, which returns a Vault
object. The Vault
class has an
open()
method and a getLoot()
method, which returns a Loot
object.
The Loot
class has a carryAway()
method. Below is a table of the
exceptions which can be thrown by each of the methods.
| Class | Method | Exceptions |
|---|---|---|
Bank |
disableAlarm() |
BurglarAlarmException |
WatchmanException |
||
breakIn() |
BurglarAlarmException |
|
LockPickFailException |
||
WatchmanException |
||
findVault() |
WatchmanException |
|
Vault |
open() |
LockPickFailException |
WatchmanException |
||
getLoot() |
WatchmanException |
|
Loot |
carryAway() |
LootTooHeavyException |
WatchmanException |
In order to deal with each of these possible errors, you need some special Java syntax.
12.2. Concepts: Error handling
As a rule, computer programs are filled with errors. Writing a program is a difficult and complex process. Even if a segment of code is free from errors, it may call other code which contains mistakes. The user could be making mistakes and issuing commands to a program that are impossible to execute. Even hardware can produce errors, as in a hard drive crash or a network connectivity problem.
12.2.1. Error codes
A robust program should deal with as many errors as possible. One
strategy is to have every method give back a special error code
corresponding to an error when it occurs. Then, the code
calling the method can react appropriately. Of course, many methods do
not return a numerical type, limiting this kind of error handling. A
solution that was very common in the C language, particularly in Unix
system calls, was to set a globally visible int
variable called
errno
to a value corresponding to the error that has just happened.
These approaches have a number of drawbacks. In the case of errno
, if a
number of different threads were running at the same time, different
errors could occur simultaneously, but only one value could be kept in
errno
. For any system that relies on checking for an error condition
after each method call, a large amount of error handling code must be
mixed in with normal code. Doing so reduces code readability and makes
it difficult to handle errors in a central place. Likewise, a numerical value
doesn’t describe the error, requiring good documentation to know what
the number means.
12.2.2. Exceptions
Java adopts a different error handling strategy called exceptions.
Whenever a specified error state or unusual situation is reached, an
exception is thrown. When an exception is thrown, normal execution stops
immediately. The JVM starts backtracking, looking for code that’s designed to deal with
that specific exception. The code that will handle the exception can be
in the current method, in the calling method, in the caller of the
calling method, or arbitrarily far back in the chain of method calls,
all the way to main()
. Each method will return, looking for code to
handle this exception, until it’s found. If no handling code is found,
the exception will propagate all the way past main()
, and
the program will end.
 You can choose to deal with errors directly or delegate that responsibility to methods that call the code you’ve written. Selection statements and loops are forms of local control flow, but exceptions give us the power of non-local control flow, able to jump back through any number of method calls.
12.3. Syntax: Exceptions in Java
In Java syntax, there are two important sides of using exceptions:
throwing the exception when an error occurs and then handling that
exception properly. Below we explain both of these as well as the
catch or specify requirement, the finally
keyword, and the process of
creating custom exceptions.
12.3.1. Throwing exceptions
By now you’ve probably experienced a NullPointerException
in the
process of coding. This exception happens when an object reference is
null
but we try to access one of its methods or fields.
String text = null;
int x = text.length(); // NullPointerException
In this case, the exception is thrown by the JVM itself. It is possible
to catch this exception and deal with it, but a NullPointerException
generally means a mistake in the program, not an error that can be
recovered from. Although many useful exceptions such as NullPointerException
,
ArithmeticException
, and ArrayIndexOutOfBoundsException
are implicitly
thrown by the JVM, we’re also allowed to throw them explicitly.
if(y < 14)
throw new NullPointerException();
Like any other object, we use the new
keyword to instantiate a
NullPointerException
using its default constructor. Once created, we
use the throw
keyword to cause the exception to go into effect. Any
exception you throw explicitly must use the throw
keyword, but the
majority of exceptions thrown by your programs will either be mistakes
or exceptions thrown by library code you’re calling. If you write a
significant amount of library or API code, you might use throw
more
often.
12.3.2. Handling exceptions
Normal application programmers will find themselves writing code that
handles exceptions much more often than code that throws them. In order
to catch an exception, you must enclose the code you think is going
to throw an exception in a try
block. Immediately after the try
block, you can list one or more catch
blocks. The first catch
block that matches your exception will be executed.
try {
String text = null;
int x = text.length(); // NullPointerException
System.out.println("This will never be printed.");
}
catch(NullPointerException e) {
System.out.println("Surprise! A NullPointerException!");
}
In this case, trying to access the length()
method of a null
reference will still throw a NullPointerException
, but now it’ll be
caught by the catch
block below. The message
"Surprise! A NullPointerException!"
will be printed to the screen, and
execution will continue normally after the catch
block. Once the
exception is caught, it stops trying to propagate. Of course, whatever
the code was doing when the exception was thrown was abandoned
immediately because it might have depended on successful execution of
the code that threw the exception. Thus, the call to the
System.out.println()
method in the try
block will never be executed.
An exception will match the first catch
block with the same class or
any superclass. Since Exception
is the parent of RuntimeException
which is the parent of NullPointerException
, we could write our
example with Exception
instead.
try {
String text = null;
int x = text.length(); // NullPointerException
System.out.println("This will never be printed.");
}
catch(Exception e) {
System.out.println("Well, of course you got a NullPointerException!");
}
In general, you should write the most specific exception class possible
for your catch
blocks. Otherwise, you might be catching a different
exception than you planned for, preventing that exception from propagating
up to an appropriate handler. For example, the following code will randomly
throw either a NullPointerException
or an
ArithmeticException
(because of a division by 0).
try {
String text = null;
int x;
if(Math.random() > 0.5)
x = text.length(); // NullPointerException
else
x = 5 / 0; // ArithmeticException
}
catch(Exception e) {
System.out.println("You got some kind of exception!");
}
This code will catch either kind of exception, but it won’t tell you
which you got. Instead, the correct approach is to have one catch
block for each possible kind of exception.
try {
String text = null;
int x;
if(Math.random() > 0.5)
x = text.length(); // NullPointerException
else
x = 5 / 0; // ArithmeticException
}
catch(NullPointerException e) {
System.out.println("You used a null pointer!");
}
catch(ArithmeticException e) {
System.out.println("You divided by zero!");
}
The list of catch
blocks can be arbitrarily long. You must always go
from the most specific exceptions to the most general, like Exception
,
otherwise some exceptions could never be reached. The Java compiler
enforces this requirement. The e
is a reference to the exception
itself, which behaves something like a parameter in a method. It’s
common to use e
as the identifier, but you’re allowed to call it any
legal variable name. Usually, the kind of exception is all you need to
know, but every exception is an object and has fields and methods.
Particularly useful is the getMessage()
method which can give
additional information about the exception.
12.3.3. Catch or specify
In contrast to the examples given above, you’ll rarely write code to catch a
NullPointerException
or an ArithmeticException
. Both of these
exceptions are called unchecked exceptions. In
Chapter 6, we used the Thread.sleep()
method to put
the execution of our program to sleep for a short period of time. We
were forced to enclose this method call in a try
block with a catch
block for InterruptedException
.
try{
Thread.sleep(100);
}
catch(InterruptedException e) {
System.out.println("Wake up!");
}
An InterruptedException
is thrown when another thread tells your
thread of execution to wake up before it finishes sleeping or waiting.
This exception is a checked exception, meaning that Java insists that
you use a try
-catch
pair anytime there’s even a chance of it being
thrown. Otherwise, your code won’t compile.
Checked exceptions are those exceptions that your program must plan for. Library and API code often throw checked exceptions. For example, when trying to open a file with an API call, it’s possible that no file with that name exists or that the user might not have permission to access it. A program should catch the corresponding exceptions and recover rather than crashing. Perhaps the program should prompt the user for a new name or explain that the required permission is not set.
In Chapter 6, there were no executable statements in
the catch
block used with the Thread.sleep()
method. However, you
should never write an empty catch
block. Doing so allows errors to fail silently.
We’re allowed to put code that can throw a checked exception into a
try
-catch
block, but there’s another option. Java has a catch
or specify requirement, meaning that your code is required either to
catch a checked exception or to specify that it has the potential for
causing that exception. To specify that a method can throw certain
exceptions, we use the throws
keyword. Note that this is not the
same as the throw
keyword.
public static void sleepWithoutTry(int milliseconds) throws InterruptedException {
Thread.sleep(milliseconds);
}
In this case, there’s no need for a try
-catch
block because the
method announces that it has a risk of throwing an
InterruptedException
. Of course, any code that uses this method will
have to have a try
-catch
block or specify that it also throws
InterruptedException
. A method can throw many different exceptions,
and you can simply list them out after the throws
keyword, separated
by commas.
Almost every exception thrown in Java is a child class of Exception
,
RuntimeException
, or Error
. Any descendant of RuntimeException
or
Error
is an unchecked exception and is exempt from the catch or
specify requirement. Any direct descendant of Exception
is a checked
exception and must either be caught with a try
-catch
block or
specified with the throws
keyword. We say direct descendant because
RuntimeException
is a child of Exception
, leading to the confusing
situation where only those descendants of Exception
which are not also
descendants of RuntimeException
are checked.
12.3.4. The finally
keyword
To deal with the situation in which an important cleanup or finalizing
task must be done no matter what, the designers of Java introduced the
finally
keyword. A finally
block comes after all the catch
blocks
following a try
block. The code inside the finally
block will be
executed whether or not any exception was thrown. A finally
block is
often used with file I/O to close the file, which should be closed
whether or not something went wrong in the process of reading it, as
we’ll demonstrate in Section 20.3.2.
The finally
keyword is unusually powerful.  Even a return
statement
will wait for a finally
block to be executed before returning, leading
to the following bizarre possibility.
public static boolean neverTrue() {
try {
return true;
}
finally {
return false;
}
}
This method attempts to return true
, but before it can finish, the
finally
block returns false
. Only one value can be returned, and the
finally
block wins. You should be aware of finally
blocks and their
unusual semantics. Use them sparingly and only for careful cleanup
operations when needed to guarantee that some event occurs.
Code in a finally
block will execute no matter what unless the JVM
exits or the thread in question terminates.
12.3.5. Customized exceptions
Exceptions are most useful when dealing with problems encountered by API code. In those cases, your code must merely catch exceptions defined by someone else; however, it’s sometimes useful to define your own exceptions. For one thing, you might write some API code yourself. Generally, you’ll want to use the standard exceptions whenever possible, but your code might generate some unusual or specific error condition that you want to communicate to a programmer, using your own exception.
Defining a new exception is surprisingly simple. All you have to do is
write a class that extends Exception
. Theoretically, you could
extend RuntimeException
or Error
instead, but you typically won’t.
Children of RuntimeException
are intended to indicate a bug in
the program, and children of Error
are intended to indicate a system
error.
When creating your new exception, you don’t even have to create
any methods, but it’s wise to implement a default constructor and one
that takes a String
as an additional message.
public class EndOfWorldException extends Exception {
public EndOfWorldException() {}
public EndOfWorldException(String message) {
super(message);
}
}
As with all other classes, your exceptions should be named in a readable
way. This exception is apparently thrown when the world ends. It’s
considered good style to end the name of any exception class with
Exception
. An exception class is a fully fledged class. If you need to
add other fields or methods to give your exception the functionality it
needs, go ahead. However, the main value of an exception lies in
its existence as a named error, not in any tricks it can perform.
Here we’ll give a few examples of exception handling, although
exceptions are more useful in large systems with heavy API use. We’ll
start with an example of a simple calculator that detects division by
zero, then look at exceptions as a tool to detect array bounds problems,
and end with a custom exception used with the Color
class.
Here we implement a quick calculator that reads input from the user
in the form of integer operator integer, where operator is one
of the four basic arithmetic operators (+
, -
, *
, /
). Our code
will perform the appropriate operation and output the answer, but we’ll
use exception handling to avoid killing the program when a division
by zero occurs.
import java.util.*;
public class QuickCalculator {
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int answer = 0;
String line = in.nextLine().trim().toLowerCase(); (1)
while(!line.equals("quit")) { (2)
String[] terms = line.split(" "); (3)
int a = Integer.parseInt(terms[0]);
char operator = terms[1].charAt(0);
int b = Integer.parseInt(terms[2]);
| 1 | The program reads a line of input from the user. |
| 2 | It tests to see if it’s the sentinel value "quit" . |
| 3 | If it isn’t, the program parses it into two int values and a char . |
try{ (1)
switch(operator) { (2)
case '+': answer = a + b; break;
case '-': answer = a - b; break;
case '*': answer = a * b; break;
case '/': answer = a / b; break;
}
System.out.println("Answer: " + answer); (3)
}
catch(ArithmeticException e) { (4)
System.out.println("You can't divide by 0!");
}
line = in.nextLine().trim().toLowerCase();
}
}
}
| 1 | Here we have a try block enclosing the code where the operations
occur. |
| 2 | Inside the switch statement, the code blindly performs
addition, subtraction, multiplication, or division, depending on the
value of operator . |
| 3 | Then, it prints the answer. |
| 4 | However, if a division by zero occurs, the execution jumps to the catch block
and prints an appropriate message. |
This try
-catch
pair is situated
inside the loop so that the input will continue even if there was a
division by zero. We could achieve the same effect by using an if
statement to test if the divisor is zero, but our solution allows easy
extensions if there are other exceptions we want to catch.
Exceptions provide a lot of power. If we want, we can use the
ArrayOutOfBoundsException
as a crutch when we don’t want to think
about the bounds of our array. Although this makes for an interesting
example, exceptions should not be used in Java to perform normal tasks.
This method takes in an array of int
values and prints them all out.
public static void exceptionalArrayPrint(int[] array) {
try {
int i = 0;
while(true)
System.out.print(array[i++] + " ");
}
catch(ArrayIndexOutOfBoundsException e) {}
}
Although the while
loop will run without stopping, the moment that i
reaches array.length
, it will throw an ArrayIndexOutOfBoundsException
when
it tries to access that element in array
. Since we left the catch
block empty, nothing will happen, the method will return, and everything
will work fine. This example is a peculiar kind of laziness, indeed,
since a for
loop could achieve the same effect with fewer lines of
code.
Programmers can be tempted to abuse exceptions in this way when a lot of calculations are needed to determine the correct bounds. Consider a game of Connect Four. To see if a player has won, the computer must examine all horizontal, vertical, and diagonal possibilities for four in a row. If the game board is represented as a 2D array, the programmer must be careful to make sure that checking for four in a row does not access any index greater than the last row or column or smaller than 0.
The danger of using exceptions for these kinds of tasks has several sources. First, the programmer may not deeply understand the problem and may be careless about the solution. Second, there’s a risk of hiding exceptions that are generated because of real errors. Third, the code becomes difficult to read and unintuitive. Finally, excessive use of exceptions can negatively impact performance.
The Color
class provided by Java allows us to represent a color as a
triple of red, green, and blue values with each value in the range
[0,255]. Using these three components, we can produce
2563 = 16,777,216 colors. If we were programming some
image manipulation software, we might want to be able to increase the
red, green, or blue values separately. If changing a value makes it
larger than 255, we could throw an exception. Likewise, if changing a
value makes it less than 0, we could throw a different exception. Let’s
give two custom exceptions that could serve in these roles.
public class ColorUnderflowException extends Exception {
public ColorUnderflowException(String message) {
super(message);
}
public ColorUnderflowException() { super(); }
}
public class ColorOverflowException extends Exception {
public ColorOverflowException(String message) {
super(message);
}
public ColorOverflowException() { super(); }
}
Now we can write six methods, each of which increases or decreases the
red, green, or blue component of a Color
object by 5. If the value of
the component is out of range, an appropriate exception will be thrown.
public static Color increaseRed(Color color)
throws ColorOverflowException {
if(color.getRed() + 5 > 255)
throw new ColorOverflowException("Red: " + (color.getRed() + 5));
else
return new Color(color.getRed() + 5, color.getGreen(), color.getBlue());
}
public static Color increaseGreen(Color color)
throws ColorOverflowException {
if(color.getGreen() + 5 > 255)
throw new ColorOverflowException("Green: " + (color.getGreen() + 5));
else
return new Color(color.getRed(), color.getGreen() + 5, color.getBlue());
}
public static Color increaseBlue(Color color)
throws ColorOverflowException {
if(color.getBlue() + 5 > 255)
throw new ColorOverflowException("Blue: " + (color.getBlue() + 5));
else
return new Color(color.getRed(), color.getGreen(), color.getBlue() + 5);
}
public static Color decreaseRed(Color color) throws ColorUnderflowException {
if(color.getRed() - 5 < 0)
throw new ColorUnderflowException("Red: " + (color.getRed() - 5));
else
return new Color(color.getRed() - 5, color.getGreen(), color.getBlue());
}
public static Color decreaseGreen(Color color)
throws ColorUnderflowException {
if(color.getGreen() - 5 < 0)
throw new ColorUnderflowException("Green: " + (color.getGreen() - 5));
else
return new Color(color.getRed(), color.getGreen() - 5, color.getBlue());
}
public static Color decreaseBlue(Color color)
throws ColorUnderflowException {
if(color.getBlue() - 5 < 0)
throw new ColorUnderflowException("Blue: " + (color.getBlue() - 5));
else
return new Color(color.getRed(), color.getGreen(), color.getBlue() - 5);
}
Finally, we can write a short method that changes a given color based on user input and deals with exceptions appropriately.
public static Color changeColor(Color color) {
System.out.println("Enter 'R', 'G', or 'B' to increase " +
"the amount of red, green, or blue in your color. " +
"Enter 'r', 'g', or 'b' to decrease the amount of " +
"red, green, or blue in your color.");
Scanner in = new Scanner(System.in);
try {
switch(in.next().trim().charAt(0)) {
case 'R': color = increaseRed(color); break;
case 'G': color = increaseGreen(color); break;
case 'B': color = increaseBlue(color); break;
case 'r': color = decreaseRed(color); break;
case 'g': color = decreaseGreen(color); break;
case 'b': color = decreaseBlue(color); break;
}
}
catch(ColorOverflowException e) {
System.out.println(e);
}
catch(ColorUnderflowException e) {
System.out.println(e);
}
return color;
}
The code that uses these methods and exceptions is compact. One try
block enclosing the method calls is needed so that the exceptions can be
caught. Following the try
, there’s a catch
block for the
ColorOverflowException
and one for the ColorUnderflowException
. Each
will print out its exception, including the customized message inside.
If an exception occurred, the value of color
would remain unchanged
because the execution would have jumped to a catch
block before the
assignment could happen.
Note that when catching the ColorOverflowException
or the ColorUnderflowException
in the above code, we do the same thing in either case: print the exception.
To reduce the amount of code, we could have caught Exception
instead of those two specific exceptions, but doing so would catch all
exceptions, not just the two related to color that we care about.
In Java 7 and higher, there’s special syntax to deal with situations like the
one above where several specific exceptions are handled in the same way. The
exception types are listed in a catch
block with pipe symbols (|
) between
them. There’s still only a single reference to the exception (often named
e
). Using this updated syntax, we could have written the try
-catch
above
as follows.
try {
switch(in.next().trim().charAt(0)) {
case 'R': color = increaseRed(color); break;
case 'G': color = increaseGreen(color); break;
case 'B': color = increaseBlue(color); break;
case 'r': color = decreaseRed(color); break;
case 'g': color = decreaseGreen(color); break;
case 'b': color = decreaseBlue(color); break;
}
}
catch(ColorOverflowException | ColorUnderflowException e) {
System.out.println(e);
}
12.4. Solution: Bank burglary
Here’s our solution to the bank burglary problem. Although somewhat fanciful, the process could be expanded into a more serious simulation. We begin by defining each of the exceptions.
public class BurglarAlarmException extends Exception {
public BurglarAlarmException(String message) {
super(message);
}
public BurglarAlarmException() { super(); }
}
public class WatchmanException extends Exception {
public WatchmanException(String message) {
super(message);
}
public WatchmanException() { super(); }
}
public class LockPickFailException extends Exception {
public LockPickFailException(String message) {
super(message);
}
public LockPickFailException() { super(); }
}
public class LootTooHeavyException extends Exception {
public LootTooHeavyException(String message) {
super(message);
}
public LootTooHeavyException() { super(); }
}
Note that the default constructor for each exception is necessary, since
constructors taking a String
value are provided for each class.
Although these default constructors do nothing other than call their
parent constructor, they are needed so that it is possible to create
each of these constructors without a customized message.
With the exceptions defined, we can assume that the Bank
class and the
Vault
class throw the appropriate exceptions when something goes
wrong. Thus, we can make a Henchman
class who can try to do the heist
and react appropriately if there’s a problem.
public class Henchman {
public void burgle(Bank bank) { (1)
try {
bank.disableAlarm(); (2)
bank.breakIn();
Vault vault = bank.findVault();
vault.open();
Loot loot = vault.getLoot();
loot.carryAway();
System.out.println("We got " + loot + "!"); (3)
}
| 1 | To burgle a bank, one must create a Henchman object then pass a Bank
object into its burgle() method. |
| 2 | The method will try to disable the alarm, break into the bank, find the vault, open the vault, get the loot out of the vault, and carry it away. |
| 3 | If all those steps happen
successfully, the method will print out a String version of the loot. |
All of this code is inside of a try
block. If an exception is thrown
at any point, the following catch
blocks will deal with it.
catch(BurglarAlarmException e) { (1)
System.out.println("I set off the burglar because " + e.getMessage());
System.out.println("I had to run away.");
}
catch(WatchmanException e) { (2)
System.out.println("A watchman caught me because " + e.getMessage());
System.out.println("Please bail me out of jail.");
}
catch(LockPickFailException e) { (3)
System.out.println("I couldn't pick the vault lock.");
System.out.println("No loot for us.");
}
catch(LootTooHeavyException e) { (4)
System.out.println("The loot was too heavy to carry.");
System.out.println("No loot for us.");
}
catch(NullPointerException e) { (5)
System.out.println("The vault was hidden or empty.");
System.out.println("No loot for us.");
}
}
}
| 1 | If a BurglarAlarmException happens, the henchman is forced to run
away. |
| 2 | If a WatchmanException happens, the henchman is caught and must
be bailed out of jail. |
| 3 | If a LockPickFailException the henchman is unable to carry the
loot off. |
| 4 | Something similar happens for a LootTooHeavyException . |
| 5 | The last catch block is a little unusual. In this case, a
NullPointerException has occurred. Within the try block, two obvious
sources of this exception are the vault and the loot variables. If
either of them were null , in the case of a vault that could not be
found or a vault that was empty, trying to call a method on that null
reference would throw a NullPointerException . Although this code shows
the power of exception handling, it’s a little unwieldy since we don’t
know which variable was null . Also, it’ll hide any
NullPointerException that might happen for other reasons. A better
solution would be to check for each of these null cases or create more
specific exceptions thrown by findVault() and getLoot() if either
returns null . |
12.5. Concurrency: Exceptions
Any thread in Java can throw an exception. That thread might be the main thread or it might be an extra one that you spawned yourself. (Or even one spawned behind the scenes through a library call.)
What happens when a thread throws an exception? As we’ve been
discussing in this chapter, the exception will either be caught or
propagate back to its caller. If the exception is caught, the catch
block
determines what happens. If the exception propagates back and back and back and
is never caught, then what? If you’ve coded some of the examples in this
chapter, you might think the entire program crashes, but only the thread
throwing the exception dies.
In a program with a single thread, an exception thrown by the main()
method will crash the program, completely halting execution. In a
multi-threaded program, execution will continue on all threads that have
not thrown exceptions. If even a single thread is executing, the program
will run to completion before the JVM shuts down.
public class CrazyThread extends Thread {
private int value;
public static void main(String[] args) {
for(int i = 0; i < 10; i++)
new CrazyThread(i).start();
throw new RuntimeException();
}
public CrazyThread(int value) {
this.value = value;
}
public void run() {
if(value == 7) {
double sum = 0;
for(int i = 1; i <= 1000000; i++)
sum += Math.sin(i);
System.out.println("Sum: " + sum);
}
else
throw new RuntimeException();
}
}
In the program given above, all of the threads except one will die
because of the RuntimeException
that they throw. Note that we use the unchecked
RuntimeException
so that Java does not complain about the lack of
catch
blocks. The thread with a value
of 7
will complete its
calculation and print it to the screen even though the main thread has
died. For more information on how to spawn threads, refer to
Chapter 13.
This behavior can cause a program that never seems to finish. You might
write a program that spawns a number of threads and does some work. Even
if the main()
method has completed and all the important data has been
output, the program won’t terminate if any threads are still alive.
This problem can also be caused by creating a GUI (such as a JFrame
),
which spawns one or more threads indirectly, if the GUI isn’t properly
disposed.
12.5.1. InterruptedException
In conjunction with concurrency, one exception deserves special
attention: InterruptedException
. This exception can happen when a thread calls
wait()
, join()
, or sleep()
. It’s a checked exception, requiring
either a catch
block or a throws
specification.
This exception is used in cases where the executing thread must wait for
some event to occur or some time to pass. In extreme circumstances,
another thread can interrupt the waiting thread, forcing it to continue
executing before it’s done waiting. If that happens, the code in the
catch
block determines how the thread should recover from being awoken
prematurely.
Programmers who are new to concurrency in Java are often confused or
annoyed by InterruptedException
, particularly since it never seems to be thrown.
Although it’s thrown rarely, situations such as a system shutting down
may be best dealt with by calling interrupt()
on a waiting thread,
causing such an exception. Although we’ll generally leave the
InterruptedException
catch
block empty in this book, threads written
for production code should always handle interruptions gracefully.
12.6. Exercises
Conceptual Problems
-
What are the advantages of using exceptions instead of returning error codes?
-
The keywords
final
andfinally
, as well as theObject
methodfinalize()
, are sometimes confused. What’s the purpose of each one? -
What’s the difference between the
throw
keyword and thethrows
keyword? -
What must be done differently when using methods that throw checked exceptions as compared to unchecked exceptions? How do the classes
Exception
,RuntimeException
, andError
play a role? -
For every program you write, you could choose to put the entire body of your
main()
method in a largetry
block with acatch
block at the end that catchesException
. In this way, no exception would cause your program to crash. Why is this approach a bad programming decision? -
Why did the designers of Java choose to make
NullPointerException
andArithmeticException
unchecked exceptions even though a program that unintentionally dereferences anull
pointer or divides by zero will often crash? -
Consider the following two classes.
public class Trouble { public makeTrouble() { throw new ArithmeticException(); } } public class Hazard { public makeHazard() { throw new InterruptedException(); } }
Class
Trouble
will compile, but classHazard
will not. Explain why and what could be done to makeHazard
compile. -
What value will the following method always return and why?
public static int magic(String value) { try { int x = Integer.parseInt(value); return x; } catch(Exception e) { System.out.println("Some exception occurred."); return 0; } finally { return -1; } }
-
Why will the following segment of code fail to compile?
try{ Thread.sleep(1000); } catch(Exception e) { System.out.println("Exception occurred!"); } catch(InterruptedException e) { System.out.println("Woke up early!"); }
-
Consider the following fragment of Java.
try { throw new NullPointerException(); } finally { throw new ArrayIndexOutOfBoundsException(); }
This code is legal Java. It’s possible to have a
finally
block after atry
block without anycatch
blocks between them. However, only a single exception can be active at once. Which exception will propagate up from this code and why?
Programming Practice
-
The
NumberFormatException
exception is thrown whenever theInteger.parseInt()
method receives a poorly formattedString
representation of an integer. Re-implementQuickCalculator
to catch anyNumberFormatException
and give an appropriate message to the user. -
Refer to Exercise 11.14 and add to the basic mechanics of the simulation by designing two custom exceptions,
CollisionException
andLightSpeedException
. These exceptions should be thrown, respectively, if two bodies collide or if the total magnitude of a body’s velocity exceeds the speed of light. -
Users often log onto systems by entering their user name and a password. Unfortunately, human beings are notoriously bad at picking passwords. In computer security, a tool called a proactive password checker allows a user to pick a password but rejects the choice if it doesn’t meet certain criteria.
Common criteria for a password are that it must be at least a certain length, must contain must contain uppercase and lowercase letters, must contain numerical digits, must contain symbols, cannot be the same as a list of words from a dictionary, and others.
Write a short program with a
check()
method that takes a singleString
parameter giving a possible password. This method should throw an exception if the password does not meet the matching criteria listed below.Password criteria Exception At least 8 characters in length
TooShortException
Contains both upper- and lowercase letters
NoMixedCaseException
Contains at least one numerical digit
NoDigitException
Contains at least one symbol
NoSymbolException
Your
main()
method should prompt the user to select a password and then pass it to thecheck()
method. If the method throws an exception, you should catch it and print an appropriate error message. Otherwise, you should report to the user that the password is acceptable. Note that you’ll need to define each of the four exceptions as well.
Experiments
-
Throwing and catching exceptions is a useful tool for making robust programs in Java. However, the JVM machinery needed to implement such a powerful tool is complex. Create an array containing 100,000 random
int
values. First, sum all these variables up using afor
loop and time how long it takes. Then, do the same thing, but, inside of thefor
loop, put atry
block containing a simple division by zero instruction such asx = 5 / 0;
. After thetry
block, put acatch
block catching anArithmeticException
. Time this version of the code. Again, you may wish to useSystem.nanoTime()
to measure the time accurately. Was there a large difference in the time taken? Do your findings have any implications for code that routinely throws thousands of exceptions?
13. Concurrent Programming
Time is the substance from which I am made. Time is a river which carries me along, but I am the river; it is a tiger that devours me, but I am the tiger; it is a fire that consumes me, but I am the fire.
13.1. Introduction
So far we’ve focused mostly on writing sequential programs. Sequential execution means that program statements are executed one at a time in a sequence determined by program logic and input data. However, more than one program statement can be executed independently by a multicore processor. While it’s common for programmers to write sequential programs, the widespread availability of multicore processors in a single computer has led to an increase in the demand for programmers who can write concurrent programs.
A concurrent program is one in which several statements can be executed simultaneously by two or more cores. In this chapter we show how to write simple concurrent programs in Java that exploit the power of a multicore computer. We begin with a problem where the fate of the planet’s in grave danger!
13.2. Problem: Deadly virus
A deadly virus capable of wiping out the world’s population is about to be released by an evil mastermind. Only he knows the security code that can stop the countdown. The world is doomed. The single hope for salvation lies with you and your Java programming skills. Through the investigations of a top secret, government-funded spy ring, it’s been revealed that the security code is tied to the number 59,984,005,171,248,659. This large number is the product of two prime numbers, and the security code is their sum. All you need to do is factor the number 59,984,005,171,248,659 into its two prime factors and add them.
Of course, there’s a catch. The deadly virus is going to be released soon, so soon that there might not be enough time for your computer to search through all the numbers one by one. Instead, you must use concurrency to check more than one number at a time.
Does this problem sound contrived? To keep information sent over the Internet private, many kinds of public key cryptography rely on the difficulty of factoring large numbers. Although factoring the number in this problem isn’t difficult, the numbers used for public key cryptography, typically more than 300 decimal digits long, have resisted factorization by even the fastest computers.
13.3. Concepts: Splitting up work
The deadly virus problem has one large task (factoring a number) to perform. How should we split up this task so that we can do it more quickly? Splitting up the work to be done is at the heart of any concurrent solution to a problem.
In a multicore processor, each core is an independent worker. It takes some care to coordinate these workers. First of all, we still need to get the right answer. A concurrent solution is worthless if it’s incorrect, and by reading and writing to the same shared memory, answers found by one core can corrupt answers found by other cores. Preventing that problem will be addressed in Chapter 14. Once we can guarantee the concurrent solution is correct, we also want to improve performance. Perhaps we want the task to finish more quickly. Perhaps we have an interactive system that should continue to handle user requests even though it’s working on a solution in the background. Again, if the overhead of coordinating our workers takes more time than a sequential solution or makes the system less responsive, it’s not useful.
There are two main ways to split up work. The first is called task decomposition. In this approach, each worker is given a different job to do. The second is called domain decomposition. In this approach, the workers do the same job but to different data.
It’s possible to use both task and domain decomposition together to solve the same problem. With both kinds of decomposition, it’s usually necessary to coordinate the workers so that they can share information. In the next two subsections, we describe task decomposition and domain decomposition in greater depth. Then we discuss mapping tasks to threads of execution and the different memory architectures that can be used for concurrent programming.
13.3.1. Task decomposition
The idea of breaking a task down into smaller subtasks is a natural one. Imagine you’re planning a dinner party. You need to buy supplies, cook the dinner, clean your house, and set the table. If four of you were planning the party, each could perform a separate activity. The preparations could go much faster than if a single person was doing the work, but coordination is still important. Perhaps the person cooking the dinner couldn’t finish until certain supplies were bought.
Task decomposition is often easier than domain decomposition because many tasks have natural divisions. Unfortunately, it’s not always an effective way to use multiple cores on a computer. If one task finishes long before the others, a core might sit idle.
The next two examples give simple illustrations of the process of splitting a task into smaller subtasks in the context of multicore programming.
Consider a simple video game that consists of the following tasks.
-
Start game
-
Process move
-
Update score
-
Repaint screen
-
End game
Suppose that tasks B and D are independent and can be executed concurrently if two cores are available. Task D continually updates the screen with the old data until task C updates the information.
Figure 13.1(a) and (b) show how the tasks in this video game can be sequenced, respectively, on a single core or on two cores. All tasks are executed sequentially on a single-core processor. In a dual-core processor tasks B and C can execute on one core while task D is executing concurrently on another. Note from the figure that task C sends the score and any other data to task D which is continuously updating the screen. Having two cores can allow a faster refresh of the display since the processor doesn’t have to wait for tasks B or C to complete.
Suppose we need to evaluate the mathematical expression 2Kate-at² with parameters a and K at a given value of t. We can divide the expression into two terms: 2Kat and e-at². Each of these terms can be assigned to a different task for evaluation. On a dual-core processor, these two tasks can be executed on separate cores and the results from each combined to find the value of the expression for the main task.
Figure 13.2 shows how this expression can be evaluated on single core and dual-core processors. Sometimes, using multiple cores to evaluate an expression like this will take less time than a single core. However, there’s no guarantee that using multiple cores will always be faster since tasks take time to set up and to communicate with each other.
These examples illustrate how a task can be divided into two or more subtasks executed by different cores of a processor. We use a dual-core processor for our examples, but the same ideas can be expanded to a larger number of cores.
13.3.2. Domain decomposition
In a computer program, every task performs operations on data. This data is called the domain of that task. In domain decomposition, the data is divided into smaller chunks where each chunk is assigned to a different core, instead of dividing a task into subtasks. Thus, each core executes the same task but on different data.
In the example of the dinner party, we could have used domain decomposition instead of (or in addition to) task decomposition. If you want to cook a massive batch of mashed potatoes, you could peel 24 potatoes yourself. However, if there are four people (and each has a potato peeler), each person would only need to peel 6 potatoes.
The strategy of domain decomposition is very useful and is one of the major focuses of concurrency in this book. Problems in modern computing often use massive data, comprising millions of values or thousands of database records. Writing programs that can chop up data so that multiple cores can process smaller sections of it can greatly speed up the time it takes to finish computation.
In some ways, domain decomposition can be more difficult than task decomposition. The data must be divided evenly and fairly. Once each section of data has been processed, the results must be combined. Companies like Google that process massive amounts of information have developed terminology to describe this process. Dividing up the data and assigning it to workers is called the map step. Combining the partial answers into the final answer is called the reduce step.
We illustrate the domain decomposition strategy in the next two examples.
Suppose we want to apply function f to each element of an array a and sum the results. Mathematically, we want to compute the following sum.
In this formula, ai is the ith element of array a. Let’s assume we have a dual-core processor available to compute the sum. We split up the array so that each core performs the task on half of the array. Let S1 and S2 denote the sums computed by core 1 and core 2, respectively.
Assuming that N is even, both cores process exactly the same amount of data. For odd N, one of the cores processes one more data item than the other.
After S1 and S2 have been computed, one of the cores can add these two numbers together to get S. This strategy is illustrated in Figure 13.3. After the two cores have completed their work on each half of the array, the individual sums are added together to produce the final sum.
The need to multiply matrices arises in many mathematical, scientific, and engineering applications. Suppose we’re asked to write a program to multiply two square matrices A and B, which are both n × n matrices. The product matrix C will also be n × n. A sequential program will compute each element of matrix C one at a time. However, a concurrent program can compute more than one element of C simultaneously using multiple cores.
In this problem, the task is to multiply matrices A and B. Through domain decomposition, we can replicate this task on each core. As shown in Figure 13.4, each core computes only a portion of C. For example, if A and B are 4 × 4 matrices, we can ask one core to compute the product of the first two rows of A with all four columns of B to generate the first two rows of C. The second core computes the remaining two rows of C. Both cores can access matrices A and B.
13.3.3. Tasks and threads
It’s the programmer’s responsibility to divide his or her solution into a number of tasks and subtasks which will run on one or more cores on a processor. In previous sections, we described concurrent programs as if specific tasks could be assigned specific cores, but Java doesn’t provide a direct way to do so.
Instead, a Java programmer must group together a set of tasks and subtasks into a thread. A thread is very much like a sequential program. In fact, all sequential programs are made up of a single thread. A thread is a segment of executing code that runs through its instructions step by step. Each thread can run independently. If you have a single core processor, only one thread can run at a time, and all the threads will take turns. If you have a multicore processor, as many threads as there are cores can execute at the same time. You can’t pick which core a given thread will run on. In most cases, you won’t even be able to tell which core a given thread is using.
It takes care to package up the right set of tasks into a single thread of execution. Recall the previous examples of concurrent programming in this chapter.
Consider dividing the tasks in Example 13.1 into two threads. Tasks B and C in can be packaged into thread 1, and task D can be packaged into thread 2. This division is shown in Figure 13.5(a).
Tasks to evaluate different subexpressions in Example 13.2 can also be divided into two threads as shown in Figure 13.5(b). In many problems there are several reasonable ways of dividing a set of subtasks into threads.
Note that these figures look exactly like the earlier figures, except that the tasks are grouped as threads instead of cores. This grouping matches reality better, since we can control how the tasks are packaged into threads but not how they are assigned to cores.
In both examples, we have two threads. It’s possible that some other
thread started these threads running. Every Java program, concurrent or
sequential, starts with one thread. We’ll refer to this thread as the
main thread since it contains the main()
method.
Example 13.3 and Example 13.4 use multiple identical tasks, but these tasks operate on different data. In Example 13.3, the two tasks can be assigned to two threads that operate on different portions of the input array. The task of summing the results from the two threads can either be a separate thread or a subtask included in one of the other threads. In Example 13.4, the two tasks can again be assigned to two distinct threads that operate on different parts of the input matrix A to generate the corresponding portions of the output matrix C.
There can be many ways to package tasks into threads. There can also be many ways to decompose data into smaller chunks. The best ways to perform these subdivisions of tasks or data depend on the problem at hand and the processor architecture on which the program will be executed.
13.3.4. Memory architectures and concurrency
The two most important paradigms for concurrent programming are message passing and shared memory systems. Each paradigm handles communication between the various units of code running in parallel in a different way. Message passing systems such as MPI approach this problem by sending messages between otherwise independent units of code called processes. A process which is executing a task may have to wait until it receives a message from another process before it knows how to proceed. Messages can be sent from a single process to one other or broadcast to many. Message passing systems are especially useful when the processors doing the work do not share memory.
In contrast, the built-in system for concurrency in Java uses the shared memory paradigm. In Java, a programmer can create a number of threads which share the same memory space. Each thread is an object which can perform work. We described threads as a way to package up a group of tasks, and processes are another. People use the term processes to describe units of code executing with separate memory and threads to describe units of code executing with shared memory.
When you first learned to program, one of the biggest challenges was probably learning to solve a problem step by step. Each line of the program had to be executed one at a time, logically and deterministically. Human beings don’t naturally think that way. We tend to jump from one thing to another, making inferences and guesses, thinking about two unrelated things at once, and so on. As you know now, it’s only possible to write and debug programs because of the methodical way they work.
You can imagine the execution of a program as an arrow that points to
one line of code, then the next, then the next, and so on. We can think
of the movement of this arrow as the thread of execution of the program.
The code does the actual work, but the arrow keeps track of where
execution in the program currently is. The code can move the arrow
forward, it can do basic arithmetic, it can decide between choices with
if
statements, it can do things repeatedly with loops, it can jump
into a method and then come back. A single thread of execution can do
all of these things, but its arrow can’t be two places at once. It can’t
be dividing two numbers in one part of the program and evaluating an
if
statement in another. However, there’s a way to split this thread
of execution so that two or more threads are executing different parts
of the program, and the next section will show you how this is done in
Java.
13.4. Syntax: Threads in Java
13.4.1. The Thread
class
Java, like many programming languages, includes the necessary features
to package tasks and subtasks into threads. The Thread
class and its
subclasses provide the tools for creating and managing threads. For
example, the following class definition allows objects of type
ThreadedTask
to be created. Such an object can be executed as a
separate thread.
public class ThreadedTask extends Thread {
// Add constructor and body of class
}
The constructor is written just like any other constructor, but there’s
a special run()
method in Thread
that can be overridden by any of
its subclasses. This method is the starting point for the thread of
execution associated with an instance of the class. Most Java
applications begin with a single main thread which starts in a main()
method. Additional threads must start somewhere, and that place is the
run()
method. A Java application will continue to run as long as at
least one thread is active. The following example shows two threads,
each evaluating a separate subexpression as in Figure 13.5(b).
We’ll create Thread1
and Thread2
classes. The threads of execution
created by instances of these classes compute, respectively, the two
subexpressions in Figure 13.5(b) and save the
computed values.
public class Thread1 extends Thread {
private double K, a, t, value;
public Thread1(double K, double a, double t) {
this.K = K;
this.a = a;
this.t = t;
}
public void run() { value = 2*K*a*t; }
public double getValue() { return value; }
}
public class Thread2 extends Thread {
private double a, t, value;
public Thread2(double a, double t) {
this.a = a;
this.t = t;
}
public void run() { value = Math.exp(-a*t*t); }
public double getValue() { return value; }
}
The run()
method in each thread above computes a subexpression and
saves its value. We show how these threads can be executed to solve the
math expression problem in Example 13.6.
13.4.2. Creating a thread object
Creating an object from a subclass of Thread
is the same as creating
any other object in Java. For example, we can instantiate the Thread1
class above to create an object called thread1
.
Thread1 thread1 = new Thread1(15.1, 2.8, 7.53);
Using the new
keyword to invoke the constructor creates a Thread1
object, but it doesn’t start executing it as a new thread. As with all
other classes, the constructor initializes the values inside of the new
object. A subclass of Thread
can have many different constructors with
whatever parameters its designer thinks appropriate.
13.4.3. Starting a thread
To start the thread object executing, its start()
method must be
called. For example, the thread1
object created above can be started
as follows.
thread1.start();
Once started, a thread executes independently. Calling the start()
method automatically calls the object’s run()
method behind the
scenes. When a thread needs to share data with another thread, it
might have to wait.
13.4.4. Waiting for a thread
Often some thread, main or otherwise, needs to wait for another thread
before proceeding further with its execution. The join()
method is
used to wait for a thread to finish executing. For example, whichever
thread executes the following code will wait for thread1
to complete.
thread1.join();
Calling join()
is a blocking call, meaning that the code calling
this method will wait until it returns. Since it can throw a a checked
InterruptedException
while the code’s waiting, the join()
method
is generally used within a try
-catch
block. We can add a
try
-catch
block to the thread1
example so that we can recover from
being interrupted while waiting for thread1
to finish.
try {
System.out.println("Waiting for thread 1...");
thread1.join();
System.out.println("Thread 1 finished!");
}
catch (InterruptedException e) {
System.out.println("Thread 1 didn't finish!");
}
Note that the InterruptedException
is thrown because the main thread
was interrupted while waiting for thread1
to finish. If the join()
call returns, then thread1
must have finished, and we inform the user.
If an InterruptedException
is thrown, some outside thread must have
interrupted the main thread, forcing it to stop waiting for thread1
.
In earlier versions of Java, there was a stop()
method which would
stop an executing thread. Although this method still exists, it’s been
deprecated and shouldn’t be used because it can make a program behave
in an unexpected way.
Now that we have the syntax to start threads and wait for them to
finish, we can use the threads defined in Example 13.5 with a
main thread to make our first complete concurrent
program. The main thread in class MathExpression
creates and starts
the worker threads thread1
and thread2
and waits for their
completion. When the two threads complete their execution, we can ask
each for its computed value. The main thread then prints the product of
these values, which is the result of the expression we want to evaluate.
public class MathExpression {
public static void main (String[] args) {
double K = 120, a = 1.2, t = 2;
Thread1 thread1 = new Thread1(K, a, t);
Thread2 thread2 = new Thread2(a, t);
thread1.start(); // Start thread1
thread2.start(); // Start thread2
try { // Wait for both threads to complete
thread1.join();
thread2.join();
System.out.println("Value of expression: " +
thread1.getValue()*thread2.getValue());
}
catch (InterruptedException e) {
System.out.println("A thread didn't finish!");
}
}
}
We want to make it absolutely clear when threads are created, start executing, and finish. These details are crucial for the finer points of concurrent Java programming. In Figure 13.5, it appears as if execution of the concurrent math expression evaluation begins with Thread 1 which spawns Thread 2. Although that figure explains the basics of task decomposition well, the details are messier for real Java code.
In the code above, execution starts with the main()
method in
MathExpression
. It creates Thread1
and Thread2
objects and waits
for them to finish. Then, it reads the values from the objects after
they’ve stopped executing. We could have put the main()
method in
the Thread1
class, omitting the MathExpression
class entirely. Doing
so would make the execution match Figure 13.5
more closely, but it would make the two Thread
subclasses less
symmetrical: The main thread and thread1
would both independently
execute code inside the Thread1
class while only thread2
would
execute code inside the Thread2
class.
MathExpression
, Thread1
, and Thread2
.Figure 13.6 shows the execution of thread1
and
thread2
and the main thread. Note that the JVM implicitly creates and starts
the main thread which explicitly creates and starts thread1
and thread2
.
Even after the threads associated with thread1
and thread2
have stopped running,
the objects associated with them continue to exist. Their methods and fields can still be
accessed.
13.4.5. The Runnable
interface
Although it’s possible to create Java threads by inheriting from the
Thread
class directly, the Java API allows the programmer to use an
interface instead.
As an example, the Summer
class takes an array of int
values and
sums them up within a given range. If multiple instances of this class
are executed as separate threads, each one can sum up different parts of
an array.
public class Summer implements Runnable {
int[] array;
int lower;
int upper;
int sum = 0;
public Summer(int[] array, int lower, int upper) {
this.array = array;
this.lower = lower;
this.upper = upper;
}
public void run() {
for(int i = lower; i < upper; i++)
sum += array[i];
}
public int getSum() { return sum; }
}
This class is very similar to one that inherits from Thread
. Imagine
for a moment that the code following Summer
is extends Thread
instead of implements Runnable
. The key thing a class derived from
Thread
needs is an overridden run()
method. Since only the run()
method is important, the designers of Java provided a way to create a
thread using the Runnable
interface. To implement this interface, only
a public void run()
method is required.
When creating a new thread, there are some differences in syntax between
the two styles. The familiar way of creating and running a thread from a
Thread
subclass is as follows.
Summer summer = new Summer(array, lower, upper);
summer.start();
Since Summer
doesn’t inherit from Thread
, it doesn’t have a
start()
method, and this code won’t compile. When a class only
implements Runnable
, it’s still necessary to create a Thread
object
and call its start()
method. Thus, an extra step is needed.
Summer summer = new Summer(array, lower, upper);
Thread thread = new Thread(summer);
thread.start();
This alternate way of implementing the Runnable
interface seems more
cumbersome than inheriting directly from Thread
, since you have to
instantiate a separate Thread
object. However, most developers prefer
to design classes that implement Runnable
instead of inheriting from
Thread
. Why? Java only allows for single inheritance. If your class
implements Runnable
, it’s free to inherit from another parent class
with features you might want.
In domain decomposition, we often need to create multiple threads, all from the same class. As an example, consider the following thread declaration.
public class NumberedThread extends Thread {
private int value;
public NumberedThread(int input) { value = input; }
public void run() {
System.out.println("Thread " + value);
}
}
Now, suppose we want to create 10 thread objects of type
NumberedThread
, start them, and then wait for them to complete.
NumberedThread[] threads = new NumberedThread[10]; (1)
for(int i = 0; i < threads.length; i++) {
threads[i] = new NumberedThread(i); (2)
threads[i].start(); (3)
}
try {
for(int i = 0; i < threads.length; i++)
threads[i].join(); (4)
}
catch(InterruptedException e) {
System.out.println("A thread didn't finish!");
}
| 1 | First, we declare an array to hold references to NumberedThread
objects. Like any other type, we can make an array to hold objects that
inherit from Thread . |
| 2 | The first line of the for loop instantiates a
new NumberedThread object, invoking the constructor which stores the
current iteration of the loop into the value field. The reference to
each NumberedThread object is stored in the array. Remember that the
constructor does not start a new thread running. |
| 3 | The second line of the for loop does that. |
| 4 | We’re also interested in when the threads stop. Calling the join()
method forces the main thread to wait for each thread to finish. |
The entire second for
loop is nested inside of a try
block. If the
main thread is interrupted while waiting for any of the threads to
finish, an InterruptedException
will be caught. As before, we warn the
user that a thread didn’t finish. For production-quality code, the
catch
block should handle the exception in such a way that the thread
can recover and do useful work even though it didn’t get what it was
waiting for.
13.5. Examples: Concurrency and speedup
Speedup is one of the strongest motivations for writing concurrent programs. To understand speedup, let’s assume we have a problem to solve. We write two programs to solve this problem, one that’s sequential and another that’s concurrent and, hence, able to exploit multiple cores. Let ts be the average time to execute the sequential program and tc the average time to execute the concurrent program. So that the comparison is meaningful, assume that both programs are executed on the same computer. The speedup obtained from concurrent programming is defined as ts/tc.
Speedup measures how much faster the concurrent program executes relative to the sequential program. Ideally, we expect tc < ts, making the speedup greater than 1. However, simply writing a concurrent program doesn’t guarantee that it’s faster than the sequential version.
To determine speedup, we need to measure ts and
tc. Time in a Java program can easily be measured with
the following two static methods in the System
class.
public static long currentTimeMillis()
public static long nanoTime()
The first of these methods returns the current time in milliseconds
(ms). A millisecond is 0.001 seconds. This method gives the difference
between the current time on your computer’s clock and midnight of
January 1, 1970 Coordinated Universal Time (UTC). This point in time is
used for many timing features on many computer platforms and is called
the Unix epoch. The other method returns the current time in
nanoseconds (ns). A nanosecond is 0.000000001 or 10-9 seconds. This method also
gives the difference between the current time and some fixed time, which
is system dependent and not necessarily the Unix epoch. The
System.nanoTime()
method can be used when you want timing precision
finer than milliseconds; however, the level of accuracy it returns is
again system dependent. The next example show how to use these methods
to measure execution time.
Suppose we want to measure the execution time of a piece of Java code.
For convenience, we can assume this code is contained in the work()
method. The following code snippet measures the time to execute
work()
.
long start = System.currentTimeMillis();
work();
long end = System.currentTimeMillis();
System.out.println("Elapsed time: " + (end - start) + " ms");
The output will give the execution time for work()
measured in
milliseconds. To get the execution time in nanoseconds, use the
System.nanoTime()
method instead.
Now that we have the tools to measure execution time, we can measure speedup. The next few examples show the speedup (or lack of it) that we can achieve using a concurrent solution to a few simple problems.
Recall the concurrent program in Example 13.6 to evaluate a simple mathematical expression. This program uses two threads. We executed this multi-threaded program on an iMac computer with an Intel Core 2 Duo running at 2.16 Ghz. The execution time was measured at 1,660,000 nanoseconds. We also wrote a simple sequential program to evaluate the same expression. It took 4,100 nanoseconds to execute this program on the same computer. Plugging in these values for tc and ts, we can find the speedup.
This speedup is much less than 1. Although this result might be surprising, the concurrent program with two threads executes slower than the sequential program. In this example, the cost of creating, running, and joining threads outweighs the benefits of concurrent calculation on two cores.
In Example 13.3, we introduced the problem of applying a function to every value in an array and then summing the results. Let’s say that we want to apply the sine function to each value. To solve this problem concurrently, we partition the array evenly among a number of threads, using the domain decomposition strategy. Each thread finds the sum of the sines of the values in its part of the array. One factor that determines whether or not we achieve speedup is the complexity of the function, in this case sine, that we apply. Although we may achieve speedup with sine, a simpler function such as doubling the value might not create enough work to justify the overhead of using threads.
We create class SumThread
whose run()
method sums the sines of those
elements of the array in its assigned partition.
import java.util.Random;
public class SumThread extends Thread {
private double sum = 0.0; (1)
private int lower;
private int upper;
private double[] array; (2)
public static final int SIZE = 1000000; (3)
public static final int THREADS = 8;
public SumThread(double[] array, int lower, int upper) { (4)
this.array = array;
this.lower = lower;
this.upper = upper;
}
| 1 | First, we set up all the fields that the class will need. |
| 2 | Note that every SumThread object will have its own reference to the array of data. |
| 3 | We fix the array size at 1,000,000 and the number of threads at 8, but these values could easily be changed or read as input instead. |
| 4 | In its constructor, a SumThread takes a reference to the array of data
and the lower and upper bounds of its partition. Like most
ranges we discuss, the lower bound is inclusive though the upper bound
is exclusive. |
public void run() {
for(int i = lower; i < upper; i++)
sum += Math.sin(array[i]); (1)
}
public double getSum() { return sum; } (2)
| 1 | In the for loop of the run() method, the SumThread finds the sine
of each number in its array partition and adds that value to its running
sum. |
| 2 | The getSum() method is an accessor that allows the running sum to
be retrieved. |
public static void main(String[] args) {
double[] data = new double[SIZE]; (1)
Random random = new Random();
int start = 0;
for(int i = 0; i < SIZE; i++) (2)
data[i] = random.nextDouble();
SumThread[] threads = new SumThread[THREADS];
int quotient = data.length / THREADS;
int remainder = data.length % THREADS;
for(int i = 0; i < THREADS; i++) {
int work = quotient;
if(i < remainder)
work++;
threads[i] = new SumThread(data, start, start + work); (3)
threads[i].start(); (4)
start += work;
}
| 1 | The main() method begins by instantiating the array. |
| 2 | It fills it with random values. |
| 3 | Then, each thread is created by passing in a reference to the array and lower and upper bounds that mark the thread’s partition of the array. If the process using the array length and the number of threads to determine upper and lower bounds doesn’t make sense, refer to Section 6.11 which describes the fair division of work to threads. If the length of the array is not divisible by the number of threads, simple division isn’t enough. |
| 4 | After each thread is created, its start() method is called. |
double sum = 0.0; (1)
try {
for(int i = 0; i < THREADS; i++) {
threads[i].join(); (2)
sum += threads[i].getSum(); (3)
}
System.out.println("Sum: " + threads[0].getSum()); (4)
}
catch(InterruptedException e) {
e.printStackTrace(); (5)
}
}
}
| 1 | Once the threads have started working, the main thread creates its own running total. |
| 2 | It iterates through each thread waiting for it to complete. |
| 3 | When each thread is done, its value is added to the running total. |
| 4 | Finally, the sum is printed out. |
| 5 | If the main thread is interrupted while waiting for a thread to complete, the stack trace is printed. |
In Example 13.4, we discussed the importance of matrix operations in many applications. Now that we know the necessary Java syntax, we can write a concurrent program to multiply two square matrices A and B and compute the resultant matrix C. If these matrices have n rows and n columns, the value at the ith row and jth column of C is
In Java, it’s natural for us to store matrices as 2-dimensional arrays.
To do this multiplication sequentially, the simplest approach uses three
nested for
loops. The code below is a direct translation of the
mathematical notation, but we do have to be careful about bookkeeping.
Note that mathematical notation often uses uppercase letters to
represent matrices though the Java convention is to start all variable
names with lowercase letters.
for(int i = 0; i < c.length; i++)
for(int j = 0; j < c[i].length; j++)
for(int k = 0; k < b.length; k++)
c[i][j] += a[i][k] * b[k][j];
The first step in making a concurrent solution to this problem is to
create a Thread
subclass which will do some part of the matrix
multiplication. Below is the MatrixThread
class which will compute a
number of rows in the answer matrix c
.
public class MatrixThread extends Thread {
private double[][] a;
private double[][] b;
private double[][] c;
private int lower;
private int upper;
public MatrixThread(double[][] a, double[][] b, (1)
double[][] c, int lower, int upper) {
this.a = a;
this.b = b;
this.c = c;
this.lower = lower;
this.upper = upper;
}
public void run() { (2)
for(int i = lower; i < upper; i++)
for(int j = 0; j < c[i].length; j++)
for(int k = 0; k < b.length; k++)
c[i][j] += a[i][k] * b[k][j];
}
}
| 1 | The constructor for MatrixThread stores references to the arrays
corresponding to matrices A, B, and
C as well as lower and upper bounds on the rows of
C to compute. |
| 2 | The body of the run() method is identical
to the sequential solution except that its outermost loop runs only from
lower to upper instead of through all the rows of the result. It’s
critical that each thread is assigned a set of rows that does not
overlap with the rows another thread has. Not only would having multiple
threads compute the same row be inefficient, it would very likely lead
to an incorrect result, as we’ll see in
Chapter 14. |
The following client code uses an array of MatrixThread
objects to
perform a matrix multiplication. We assume that an int
constant named
THREADS
has been defined which gives the number of threads we want to
create.
MatrixThread[] threads = new MatrixThread[THREADS];
int quotient = c.length / THREADS;
int remainder = c.length % THREADS;
int start = 0;
for(int i = 0; i < THREADS; i++) {
int rows = quotient;
if(i < remainder)
rows++;
threads[i] = new MatrixThread(a, b, c, start, start + rows); (1)
threads[i].start(); (2)
start += rows;
}
try {
for(int i = 0; i < THREADS; i++) (3)
threads[i].join();
}
catch(InterruptedException e) {
e.printStackTrace();
}
| 1 | We loop through the array, creating a MatrixThread object for each
location. As in the previous example, we use the approach described in
Section 6.11 to allocate rows to each thread fairly.
Each new MatrixThread object is given a reference to each of the three
matrices as well as an inclusive starting and an exclusive ending row. |
| 2 | After the MatrixThread objects are created, we start them running with
the next line of code. |
| 3 | Next, there’s a familiar for loop with the join() calls that force
the main thread to wait for the other threads to finish. |
Presumably,
code following this snippet will print the values of the result matrix
or use it for other calculations. If we didn’t use the join()
calls to be sure the threads have finished, we might print out a result
matrix that’s only been partially filled in.
We completed the code for threaded matrix multiplication and executed it on an iMac computer with an Intel Core 2 Duo running at 2.16 Ghz. The program was executed for matrices of different sizes (n × n). For each size, the sequential and concurrent execution times in seconds and the corresponding speedup are listed in the following table.
| Size (n) | ts (s) | tc (s) | Speedup |
|---|---|---|---|
100 |
0.013 |
0.9 |
0.014 |
500 |
1.75 |
4.5 |
0.39 |
1,000 |
15.6 |
10.7 |
1.45* |
Only with 1,000 × 1,000 matrices did we see improved performance when using two threads. In that case, we achieved a speedup of 1.45, marked with an asterisk. In the other two cases, performance became worse.
13.6. Concepts: Thread scheduling
Now that we’ve seen how multiple threads can be used together, a number of questions arise: Who decides when these threads run? How is processor time shared between threads? Can we make any assumptions about the order in which the threads run? Can we affect this order?
These questions focus on thread scheduling. Because different concurrent systems handle scheduling differently, we’ll only describe scheduling in Java. Although sequential programming is all about precise control over what happens next, concurrency takes much of this control away from the programmer. When threads are scheduled and which processor they run on is handled by a combination of the JVM and the OS. With normal JVMs, there’s no explicit way to access the scheduling and alter it to your liking.
Of course, there are a number of implicit ways a programmer can affect scheduling. In Java, as in several other languages and programming systems, threads have priorities. Higher priority threads run more often than lower priority threads. Some threads are performing mission-critical operations which must be carried out as quickly as possible, and some threads are just doing periodic tasks in the background. A programmer can set thread priorities accordingly.
Setting priorities gives only a very general way of controlling which
thread will run. The threads themselves might have more specific
information about when they will and won’t need processor time. A
thread may need to wait for a specific event and won’t need to run
until then. Java allows threads to interact with the scheduler through
Thread.sleep()
and Thread.yield()
, which we’ll discuss in
Section 13.7, and through the wait()
, method which
we’ll discuss in Chapter 14.
13.6.1. Nondeterminism
In Java, the mapping of a thread inside the JVM to a thread in the OS varies. Some implementations give each Java thread an OS thread, some put all Java threads on a single OS thread (with the side effect of preventing parallel execution), and some allow for the possibility of changing which OS thread a Java thread uses. Thus, the performance and, in some cases, the correctness of your program might vary, depending on which system you’re running. This is, yet again, one of those times when Java is platform independent…but not entirely.
Unfortunately, the situation is even more complicated. Making threads part of your program means that the same program could run differently on the same system. The JVM and the OS have to cooperate to schedule threads, and both programs are complex mountains of code which try to balance many factors. If you create three threads, there’s no guarantee that the first will run first, the second second, and the third third, even if it happens that way the first 10 times you run the program. Exercise 13.18 shows that the pattern of thread execution can vary a lot.
In all the programs before this chapter, the same sequence of input would always produce the same sequence of output. Perhaps the biggest hurdle created by this nondeterminism is that programmers must shift their paradigm considerably. The processor can switch between executions of threads at any time, even in the middle of operations. Every possible interleaving of thread execution could crop up at some point. Unless you can be sure that your program behaves properly for all of them, you might never be able to debug your code completely. What’s so insidious about nondeterministic bugs is that they can occur rarely and be almost impossible to reproduce. In this chapter, we’ve introduced how to create and run threads, but making these threads interact properly is a major problem we tackle in subsequent chapters.
After those dire words of warning, we’d like to remind you that nondeterminism is not in itself a bad thing. Many threaded applications with a lot of input and output, such as server applications, necessarily exist in a nondeterministic world. For these programs, many different sequences of thread execution may be perfectly valid. Each individual program may have a different definition of correctness. For example, if a stock market server receives two requests to buy the last share of a particular stock at almost the same time from two threads corresponding to two different clients, it might be correct for either one of them to get that last share. However, it would never be correct for both of them to get it.
13.6.2. Polling
So far the only mechanism we’ve introduced for coordinating different
threads is using the join()
method to wait for a thread to end.
Another technique is polling, or busy waiting. The idea is to keep
checking the state of one thread until it changes.
There are a number of problems with this approach. The first is that it wastes CPU cycles. Those cycles spent by the waiting thread continually checking could have been used productively by some other thread in the system. The second problem is that we have to be certain that the state of the thread we’re waiting for won’t change back to the original state or to some other state. Because of the unpredictability of scheduling, there’s no guarantee that the waiting thread will read the state of the other thread when it has the correct value.
We bring up polling partly because it has a historical importance to parallel programming, partly because it can be useful in solving some problems in this chapter, and partly because we want you to understand the reasons why we need better techniques for thread communication.
13.7. Syntax: Thread states
A widely used Java tool for manipulating scheduling is the
Thread.sleep()
method. This method can be called any time you want a
thread to do nothing for a set period of time. Until the sleep timer
expires, the thread will not be scheduled for any CPU time, unless it’s
interrupted. To make a thread of execution sleep, call Thread.sleep()
in that thread of execution with a number of milliseconds as a
parameter. For example, calling Thread.sleep(2000)
will make the
calling thread sleep for two full seconds.
Another useful tool is the Thread.yield()
method. It gives up use of
the CPU so that the next waiting thread can run. To use it, a thread
calls Thread.yield()
. This method is useful in practice, but
according to official documentation, the JVM doesn’t have to do to
anything when a Thread.yield()
call happens. The Java specification
doesn’t demand a particular implementation. A JVM could ignore a
Thread.yield()
call completely, but most JVMs will move on to the next
thread in the schedule.
Figure 13.7 shows the lifecycle of a thread. A
thread begins its life in the New Thread state, after the constructor is
called. When the start()
method is called, the thread begins to run
and transitions to the Runnable state. Being Runnable doesn’t
necessarily mean that the thread is executing at any given moment but
that it’s ready to run at any time. When in the Runnable state, a
thread may call Thread.yield()
, relinquishing use of the processor,
but it will still remain Runnable.
However, if a thread goes to sleep with a Thread.sleep()
call, waits
for a condition to be true using a wait()
call, or performs a blocking
I/O operation, the thread will transition to the Not Runnable state. Not
Runnable threads cannot be scheduled for processor time until they wake
up, finish waiting, or complete their I/O. The final state is
Terminated. A thread becomes Terminated when its run()
method
finishes. A Terminated thread cannot become Runnable again and is no
longer a separate thread of execution.
Any object with a type that’s a subclass of Thread
can tell you its
current state using the getState()
method. This method returns an
enum type, whose value must come from a fixed list of constant
objects. These objects are Thread.State.NEW
, Thread.State.RUNNABLE
,
Thread.State.BLOCKED
, Thread.State.WAITING
,
Thread.State.TIMED_WAITING
, and Thread.State.TERMINATED
. Although
the others are self explanatory, we lump the Thread.State.BLOCKED
,
Thread.State.WAITING
, and Thread.State.TIMED_WAITING
values into
the Not Runnable state, since the distinction between the three isn’t
important for us.
Threads also have priorities in Java. When an object that’s a subclass
of Thread
is created in Java, its priority is initially the same as
the thread that creates it. Usually, this priority is
Thread.NORM_PRIORITY
, but there are some special cases when it’s a
good idea to raise or lower this priority. Avoid changing thread
priorities because it increases platform dependence and because the
effects are not always predictable. Be aware that priorities exist, but
don’t use them unless and until you have a good reason.
Let’s apply the ideas discussed above to a lighthearted example. You
might be familiar with sound of soldiers marching: “Left, Left, Left,
Right, Left!” We can design a thread that prints Left
and another
thread that prints Right
. We can combine the two to print the correct
sequence for marching and loop the whole thing 10 times so that we can
see how accurately we can place the words. We want to use the scheduling tools
discussed above to get the timing right. Let’s try Thread.sleep()
first.
public class LeftThread extends Thread {
public void run() {
for(int i = 0; i < 10; i++) {
System.out.print("Left "); (1)
System.out.print("Left ");
System.out.print("Left ");
try { Thread.sleep(10); } (2)
catch(InterruptedException e) {
e.printStackTrace();
}
System.out.println("Left"); (3)
}
}
}
| 1 | Inside, the for loop, this thread prints out Left three times. |
| 2 | The, it waits for 10 milliseconds. |
| 3 | Finally, it prints out Left again and repeats the loop. |
public class RightThread extends Thread {
public void run() {
try {
Thread.sleep(5); (1)
for(int i = 0; i < 10; i++) {
System.out.print("Right "); (2)
Thread.sleep(10); (3)
}
}
catch(InterruptedException e) {
e.printStackTrace();
}
}
}
| 1 | This thread waits for 5 milliseconds to get synchronized. |
| 2 | Inside its for loop, it prints out Right . |
| 3 | Then, it waits for 10 milliseconds and repeats the loop. |
The driver program below creates a thread for each of these
classes and then starts them. If you run this program, you should see 10
lines of Left Left Left Right Left
, but there are a few problems.
public class MilitaryMarching {
public static void main(String[] args) {
LeftThread left = new LeftThread();
RightThread right = new RightThread();
left.start();
right.start();
try {
left.join();
right.join();
}
catch(InterruptedException e) {
e.printStackTrace();
}
}
}
The first problem is that we have to wait some amount of time between
calls. We could shorten the Thread.sleep()
calls, but there are limits
on the resolution of the timer. The bigger problem is that the two
threads can sometimes get out of sync. If you run the program many
times, you might see a Right
out of place once in a while. If you
increase the repetitions of the for
loops to a larger number, the
errors will become more likely. Whether or not you see errors is somewhat system
dependent. We can try Thread.yield()
instead of Thread.sleep()
.
public class LeftYieldThread extends Thread {
public void run() {
for(int i = 0; i < 10; i++) {
System.out.print("Left ");
System.out.print("Left ");
System.out.print("Left ");
Thread.yield();
System.out.println("Left");
}
}
}
public class RightYieldThread extends Thread {
public void run() {
for(int i = 0; i < 10; i++) {
System.out.print("Right ");
Thread.yield();
}
}
}
These new versions of the two classes have essentially replaced calls to
Thread.sleep()
with calls to Thread.yield()
. Without the need for
exception handling, the code is simpler, but we’ve traded one set of
problems for another. If there are other threads operating in the same
application, they’ll be scheduled in ways that will interfere with the
pattern of yielding. If you’re running this code on a machine
with a single processor and a single core, you have a good chance of
seeing something which matches the expected output. However, if you’re running
it on multiple cores, everything will be jumbled. It’s likely that
the LeftYieldThread
will be running on one processor with the
RightYieldThread
on another. In that case, neither has any competition
to yield to.
Finally, let’s look at a polling solution which still falls short of the mark. To do this, we need state variables inside of each class to keep track of whether or not it’s done. Each thread needs a reference to the other thread to make queries, and the driver program must be updated to add these in before starting the threads.
public class LeftPollingThread extends Thread {
private RightPollingThread right;
private boolean done = false;
public void setRight(RightPollingThread right) {
this.right = right;
}
public void run() {
for(int i = 0; i < 10; i++) {
System.out.print("Left ");
System.out.print("Left ");
System.out.print("Left ");
done = true;
while(!right.isDone());
right.setDone(false);
System.out.println("Left");
}
}
public boolean isDone() { return done; }
public void setDone(boolean value) { done = value; }
}
public class RightPollingThread extends Thread {
private LeftPollingThread left;
private boolean done = false;
public void setLeft(LeftPollingThread left) {
this.left = left;
}
public void run() {
for(int i = 0; i < 10; i++) {
while(!left.isDone());
left.setDone(false);
System.out.print("Right ");
done = true;
}
}
public boolean isDone() { return done; }
public void setDone(boolean value) { done = value; }
}
Whether single core or multicore, this solution will always give the
right output. Or it should. Java experts will point out that we are
violating a technicality of the Java Memory Model. Because we’re not
using synchronization tools, we have no guarantee that the change of the
done
variable will even be visible from one thread to another. In
practice, this problem should affect you rarely, but to be safe, both of
the done
variables should be declared with the keyword volatile
.
This keyword makes Java aware that the value may be accessed at any time
from arbitrary threads.
Another issue is that there’s no parallel execution. Each thread must wait
for the other to complete. Of course, this problem does not benefit from
a parallelism, but applying this solution to problems which can
benefit from parallelism might cause performance problems. Each thread
wastes time busy waiting in a while
loop for the other to be done,
consuming CPU cycles while it does so. You’ll notice that the code
must still be carefully written. Each thread must set the other thread’s
done
value to false
. If threads were responsible for setting their
own done
values to false
, one thread might print its information and
go back to the top of the for
loop before the other thread had reset
its own done
to false
.
In short, coordinating two or more threads together is a difficult problem. None of the solutions we give here are fully acceptable. We introduce better tools for coordination and synchronization in Chapter 14.
13.8. Solution: Deadly virus
Finally, we give the solution to the deadly virus problem. By this
point, the threaded part of this problem should not seem very difficult.
It’s simpler than some of the examples, such as matrix multiplication.
We begin with the worker class FactorThread
that can be spawned as a
thread.
public class FactorThread extends Thread {
private long lower;
private long upper;
public FactorThread(long lower, long upper) {
this.lower = lower;
this.upper = upper;
}
public void run() {
if(lower % 2 == 0) // Only check odd numbers
lower++;
while(lower < upper) {
if(Factor.NUMBER % lower == 0) {
System.out.println("Security code: " + (lower + Factor.NUMBER / lower));
return;
}
lower += 2;
}
}
}
The constructor for FactorThread
takes an upper and lower bound,
similar to MatrixThread
. Once a FactorThread
object has those
bounds, it can search between them. The number to factor is stored in
the Factor
class. If any value divides that number evenly, it must be
one of the factors, making the other factor easy to find, sum, and print
out. We have to add a couple of extra lines of code to make sure that we
only search the odd numbers in the range. This solution is tuned for
efficiency for this specific security problem. A program to find general
prime factors would have to be more flexible. Next, let’s examine the
driver program Factor
.
public class Factor {
public static final int THREADS = 4; (1)
public static final long NUMBER =<PHONE_NUMBER>1248659L;
public static void main(String[] args) {
FactorThread[] threads = new FactorThread[THREADS]; (2)
long root = (long)Math.sqrt(NUMBER); // Go to square root
long start = 3; // No need to test 2
long quotient = root / THREADS;
long remainder = root % THREADS;
for(int i = 0; i < THREADS; i++) {
long work = quotient;
if(i < remainder)
work++;
threads[i] = new FactorThread(start, start + work); (3)
threads[i].start();
start += work;
}
try {
for(int i = 0; i < THREADS; i++)
threads[i].join(); (4)
}
catch(InterruptedException e) {
e.printStackTrace();
}
}
}
| 1 | Static constants hold both the number to be factored and the number of threads. |
| 2 | In the main() method, we create an array of threads for
storage. |
| 3 | Then, we create and start each FactorThread object, assigning upper and
lower bounds at the same time, using the standard technique from
Section 6.11 to divide the work fairly. Because we
know the number we’re dividing isn’t even, we start with 3. By only
going up to the square root of the number, we know that we will only
find the smaller of the two factors. In that way we can avoid having one
thread find the smaller while another is finds the larger. |
| 4 | Afterward, we have the usual join() calls to make sure that all the
threads are done. In this problem, these calls are unnecessary. One
thread will print out the correct security code, and the others will
search fruitlessly. If the program went on to do other work, we might
need to let the other threads finish or even interrupt them. Don’t
forget join() calls since they’re usually very important. |
13.9. Summary
In this chapter we’ve explored two strategies to obtain a concurrent solution to programming problems. One strategy, task decomposition, splits a task into two or more subtasks. These subtasks can then be packaged as Java threads and executed on different cores of a multicore processor. Another strategy, domain decomposition, partitions input data into smaller chunks and allows different threads to work concurrently on each chunk of data.
A concurrent solution to a programming problem can sometimes execute more quickly than a sequential solution. Speedup measure how effective a concurrent solution is at exploiting the architecture of a multicore processor. Note that not all concurrent programs lead to speedup as some run slower than their sequential counterparts. Writing a concurrent program is a challenge that forces us to divide up work and data in a way that best exploits the available processors and OS.
Java provides a rich set of primitives and syntactic elements to write concurrent programs, but only a few of these were introduced in this chapter. Subsequent chapters give additional tools to code more complex concurrent programs.
13.10. Exercises
Conceptual Problems
-
The
start()
,run()
, andjoin()
methods are essential parts of the process of using threads in Java. Explain the purpose of each method. -
What’s the difference between extending the
Thread
class and implementing theRunnable
interface? When should you use one over the other? -
How do the
Thread.sleep()
method and theThread.yield()
method each affect thread scheduling? -
Consider the expression in Example 13.2. Suppose that the multiply and exponentiation operations require 1 and 10 time units, respectively. Compute the number of time units required to evaluate the expression as in Figure 13.2(a) and (b).
-
Suppose that a computer has one quad-core processor. Can the tasks in Example 13.1 and Example 13.2 be further subdivided to improve performance on four cores? Why or why not?
-
Consider the definition of speedup from Section 13.5. Let’s assume you have a job 1,000,000 units in size. A thread can process 10,000 units of work every second. It takes an additional 100 units of work to create a new thread. What’s the speedup if you have a dual-core processor and create 2 threads? What if you have a quad-core processor and create 4 threads? Or an 8-core processor and create 8 threads? You may assume that a thread does not need to communicate after it’s been created.
-
In which situations can speedup be smaller than the number of processors? Is it ever possible for speedup to be greater than the number of processors?
-
Amdahl’s Law is a mathematical description of the maximum amount you can improve a system by only improving a part of it. One form of it states that the maximum speedup attainable in a parallel program is 1/(1 - P) where P is the fraction of the program which can be parallelized to an arbitrary degree. If 30% of the work in a program can be fully parallelized but the rest is completely serial, what’s the speedup with two processors? Four? Eight? What implications does Amdahl’s Law have?
-
Consider the following table of tasks:
Task Time Concurrency Dependency Washing Dishes
30
3
Cooking Dinner
45
3
Washing Dishes
Cleaning Bedroom
10
2
Cleaning Bathroom
30
2
Doing Homework
30
1
Cleaning Bedroom
In this table, the Time column gives the number of minutes a task takes to perform with a single person, the Concurrency column gives the maximum number of people who can be assigned to a task, and the Dependency column shows which tasks can’t start until other tasks have been finished. Assume that people assigned to a given task can perfectly divide the work. In other words, the time a task takes is the single person time divided by the number of people assigned. What’s the minimum amount of time needed to perform all tasks with only a single person? What is the minimum amount of time needed to perform all tasks with an unlimited number of people? What’s the smallest number of people needed to achieve this minimum time?
-
Consider the following code snippet.
x = 13; x = x * 10;
Consider this snippet as well.
x = 7; x = x + x;
If we assume that these two snippets of code are running on separate threads but that
x
is a shared variable, what are the possible valuesx
could have after both snippets have run? Remember that the execution of these snippets can be interleaved in any way.
Programming Practice
-
Re-implement the array summing problem from Example 13.10 using polling instead of
join()
calls. Your program should not use a single call tojoin()
. Polling is not an ideal way to solve this problem, but it’s worth thinking about the technique. -
Composers often work with multiple tracks of music. One track might contain solo vocals, another drums, a third one violins, and so on. After recording the entire take, a mix engineer might want to apply special effects such as an echo to one or more tracks.
To understand how to add echo to a track, suppose that the track consists of a list of audio samples. Each sample in a mono (not stereo) track can be stored as a
double
in an array. To create an echo effect, we combine the current value of an audio sample with a sample from a fixed time earlier. This time is called the delay parameter. Varying the delay can produce long and short echoes.If the samples are stored in array
in
and the delay parameter is stored in variabledelay
(measured in number of samples), the following code snippet can be used to create arrayout
which contains the sound with an echo.double[] out = new double[in.length + delay]; // Sound before echo starts for(int i = 0; i < delay; i++) out[i] = in[i]; // Sound with echo for(int i = delay; i < in.length; i++) out[i] = a*in[i] + b*in[i - delay]; // Echo after sound is over for(int i = in.length; i < out.length; i++) out[i] = b*in[i - delay];
Parameters
a
andb
are used to control the nature of the echo. Whena
is1
andb
is0
, there is no echo. Whena
is0
andb
is1