Table of Contents
View all the videos from this unit a single playlist on youtube
Java Threads #
What are “threads”? #
In a single-threaded program, which is what you’ve been dealing with up until now (sort-of, except that whole GUI thing, remember?), an executing program consists of a function call stack that grows and shrinks as functions are called and functions return. At the bottom of that function call stack is the call record for main(), and when that call returns, the program is over. In a multi-threaded program, there are multiple function call stacks that execute simultaneously. The “main thread” has the main() function call record on the bottom of the stack - other executing function call stacks (an executing function-call stack is called a thread) may have different function calls on the bottom-most function call record. The program ends when every thread has exited, i.e. when the bottom-most function-call record of each call stack has returned.
However, there are many reasons to have multi-threaded execution. For example, your web browser might have a separate thread running for each individual tab. The web server (host) your browser connects to might also have a pool of threads in order to serve pages. Your text editor (like MSWord) also probably has several concurrent threads running at the same time; one of them might be constantly spell-checking your writing in real-time. These are just some examples; note that they all share some of the same data that the threads all act upon.
Java threads: the very basic basics #
The Java API has a class called Thread that includes two important methods:
public void run();
public void start();
Creating a new thread (i.e. a new function call stack) works like this:
- an instance of
Threadis created - the
start()method is called on the instance - the
run()method is called bystart(), and that call becomes the bottom-most record on a new function call stack
So, if you have something specific you want a new thread to do, you derive a new class from Thread (extend Thread) and override the run() method to do whatever it is you want done.
import java.util.*;
public class Ex0 {
public static void main(String[] args) {
Thread t = new Foo();
t.start();
int x = 5 * 5;
System.out.println(x);
}
}
public class Foo extends Thread {
public void run() {
int x = 7 * 7;
System.out.println(x);
}
}
Hopefully the following picture gives you some idea of how this works.
Some important points to take away are:
- It’s wrong to say “such and such object is in thread 1”. Objects live in the heap, outside of any of the call-stacks!
- Local varaiables, be they primitive types or references, do belong to a particular thread, since they live in function call records.
- It’s wrong to say “such and such function is in thread 1”. A given function call belongs to a thread, but there could be many threads with active function calls for the same function.
Getting data in and out: it’s all in the Object #
If you look at the above picture, what should strike you the Thread object - more literally the Foo object f in this example - is pointed to by references from both threads (from both call stacks). That means that it can be a repository of data that we want to share between threads. We can add fields to Foo f for data we want to communicate between the two threads. Below is an example of a fun little program that uses the Thread object to communicate data from the main thread to the new thread. I want you to pay attention to how both threads (both call stacks) make calls to the same methods: Ex1.printSlow().
It makes used of the thread’s sleep() method to put a thread to sleep for a specified amount of
milliseconds. This method must be called inside a try-catch block for reasons we’ll discuss in a bit.
import java.util.*;
public class Ex1 {
public static Random rand = new Random();
public static void printSlow(String s, String t) {
for (int i = 0; i < s.length(); i++) {
try {
Thread.sleep(rand.nextInt(1000));
} catch (Exception e) {}
System.out.println(t + s.charAt(i));
}
}
public static void main(String[] args) {
String s = "Mississippi";
Thread t = new Foo(s, " ");
t.start();
printSlow(s, " ");
}
}
public class Foo extends Thread {
private String msg, tab;
public Foo(String s, String t) {
this.msg = s;
this.tab = t;
}
public void run() {
Ex1.printSlow(this.msg, this.tab);
}
}
The output will look something like this:
(base) > java Ex1
M
M
i
s
i
s
i
s
s
s
i
s
i
s
p
p
s
i
i
p
p
i
The outer layer of printing comes from main, while the inner layer of printing comes from the run method of the thread after its start was called.
Not pictured here is the Random object.
Concurrency #
The join() and join(int) methods #
Java provides another method called join that forces the thread it is called upon to wait (to finish) before allowing the other thread to continue. What?
For example, if you have the following code inside a main method as above:
t.start();
...
try {
t.join(5000);
} catch (InterruptedException e) {
System.out.println("Interrupted while joining a thread...");
}
this code will force the main thread (where we started t) to wait for five seconds, potentially allowing the run() method of t to finish. You can also call join() without any argument to force the wait until t finishes completely.
Note that the join() must be called inside a try-catch block; this is known as a checked exception because the method was declared (in the library) as possibly raising an exception; the developer is forced to write code to handle this case (even if, as on the worksheet, the exception never occurs). If something interrupts the thread, catching the exception allows you to handle it elegantly.
The isAlive() method #
The isAlive() method can be called on a thread to check if it is still running. This can be useful when you want to know if a thread is finished, but don’t want to block the execution as above.
Race Conditions #
In general, parallel programming is fraught with peril! If you’re not careful, you can end up with bugs whose occurrence or precise behavior depends on the exact order in which the instructions of each thread are executed relative to one another. This kind of bug is called a race condition.
To see a nice example of how this might happen, let’s turn back to our old friend the Queue class. The following program has a single Queue, Q, that is shared by two threads. Both threads call enqueue 1,000 times, and after the second thread dies, the main thread then counts that there were indeed 1,000 items enqueued by each thread.
public class Ex0 {
public static class QThread extends Thread {
Queue Q;
public QThread(Queue Q) {
this.Q = Q;
}
public void run() {
for(int i = 0; i < 1000; i++)
Q.enqueue("b" + i);
}
}
public static void main(String[] args) {
Queue Q = new Queue();
Thread t = new QThread(Q);
t.start();
while (Q.empty()) {}
for(int i = 0; i < 1000; i++) {
Q.enqueue("a" + i);
}
while(t.isAlive()) {}
int a = 0, b = 0;
while(!Q.empty()) {
if(Q.dequeue().charAt(0) == 'a')
a++;
else
b++;
}
System.out.println("a=" + a + " b=" + b);
}
}
public class Queue {
public void enqueue(String s) {
if(head == null) {
head = tail = new Node(s, null);
} else {
tail.next = new Node(s, null);
tail = tail.next;
}
}
public String dequeue() {
Node t = head;
head = head.next;
if(head == null) {
tail = null;
}
return t.data;
}
public boolean empty() {
return head == null;
}
private class Node {
public String data;
public Node next;
public Node(String d, Node n) {
data = d;
next = n;
}
}
private Node head = null, tail = null;
}
So what happens when I run this? #
One of two things may occur …
You may see the program crash #
When I run this … it crashes. Why? Well there are a couple of possible race conditions here. The one that just happened to me went something like this: Things were OK for a while, each thread enqueuing values, but then we had a bad interleaving of execution of instructions. It probably happened like is shown in the following table:
Thread 2 (run)
tail.next = new Node(s,null);
tail = tail.next;
Thread 1 (main)
tail.next = new Node(s,null);
tail = tail.next;
// ---------
// this causes the problem
// because Thread 2 has just
// set tail to point to a
// Node whose "next" is null!
You mays see the program stuck in an infinite loop #
When I run this it gets stuck in an infinite loop. Why? Well, the lines
Thread t = new QThread(Q);
t.start();
while(Q.empty()) {}
start up a new thread and then wait until the new thread actually gets something enqueued in Q to continue. The problem is that the Java compiler / VM perform certain optimizations. In this case, one or the other of them may decide that recomputing Q.empty() is a pointless waste of time, since the call Q.empty() doesn’t actually change any fields, and nothing else happens in the loop, and thus either Q.empty() gives true every time or false every time - why recompute it? And so it is transformed to
Thread t = new QThread(Q);
t.start();
boolean tmp = Q.empty();
while(tmp) {}
… and we get our infinite loop. The problem is that the compiler/JVM is not taking into account the possibility that there may be other threads changing Q.head and Q.tail, and thus the result of Q.empty() may indeed change.
We can add the modifier volatile to Q.head and Q.tail
private volatile Node head = null, tail = null;
volatile tells the compiler/JVM that, as it does its optimizing, it cannot assume that other threads won’t be modifying these fields. This fixes the infinite loop.
Synchronization in general, and the synchronized keyword in particular #
While for the most part we want threads to process independently, in parallel, what we just saw is that there are times when we need to coordinate, or synchronize the execution of separate threads in order to avoid race conditions. To the previous example, we need to ensure that the two threads don’t simultaneously execute enqueue’s - they need to take turns. Our problem was that two threads could interleave their executions inside of the enqueue method (on the same linked list object): we want a way to make sure that if one thread is inside the enqueue method, the other is now allowed to enter it (which would solve our race condition above).
Perhaps the simplest of the many mechanisms Java provides for synchronizing the execution of threads are synchronized methods. Declaring one or more methods in a class with the synchronized modifier causes the Java virtual machine to ensure that no two threads execute overlapping calls of synchronized methods on the same object. It does this by temporarily delaying threads as needed. To be clear, suppose we have a class Foo:
public class Foo {
...
public sychronized void bar() {
...
}
...
}
If var1 and var2 are references to distinct objects of type Foo then Thread x could call var1.bar() and Thread y could call var2.bar(), and the two methods could execute simultaneously. However, if both threads called var1.bar() at the same time (note: we calling bar() on the same object this time!), then one Thread would execute bar() while the other Thread was delayed, and only after the first thread had completed its call to bar() could the second thread start executing its call.
So, to fix our bug, all we need to do is declare enqueue (and dequeue) with the synchronized modifier.
public class Queue {
public synchronized void enqueue(String s) {
if(head == null) {
head = tail = new Node(s, null);
} else {
tail.next = new Node(s, null);
tail = tail.next;
}
}
public synchronized String dequeue() {
Node t = head;
head = head.next;
if(head == null) {
tail = null;
}
return t.data;
}
public boolean empty() {
return head == null;
}
private class Node {
public String data;
public Node next;
public Node(String d, Node n) {
data = d;
next = n;
}
}
private volatile Node head = null, tail = null;
}
A Race Condition Example: Counting #
Here is another example, slightly contrived, but that illustrates further how synchronized works. Imagine you need to process a lot of data files, and you realize that you could parallelized the processing by assigning a new thread to each data file. Instead of one main thread looping over all the files, launch all the threads at the same time.
The program below takes file paths as arguments, and creates a CountThread for each one. The threads share a single SafeCounter object which simply counts how many lines are in the files. Each thread increments the counter. This is a classic race condition. There is a single value int to update as the counter that is shared across all threads. As the threads grab the value, in between reading its value and then sending the ++ updated value, another thread might read the value as well and miss the new update.
Sharing memory between threads is dangerous, but often necessary. This is why we have the synchronized keyword; although it is used with methods, it forces the method to be an ‘atomic transaction’ – that is, you can’t break it down into smaller statements. Either the whole method runs, or it doesn’t (because it is waiting for another call to the same method to finish).
Try running this on a couple large files, and remove the synchronized keyword from the methods. You’ll see different counts output from different runs. With the synchronized keyword, it will always be the same (correct) value.
public class SafeCounter {
private int value = 0;
public synchronized void increment() {
value++;
}
public synchronized int getValue() {
return value;
}
}
public class CountThread extends Thread {
String filename;
SafeCounter counter;
public CountThread(String filename, SafeCounter counter) {
this.filename = filename;
this.counter = counter;
}
public void run() {
try {
Scanner scan = new Scanner(new File(filename));
while(scan.hasNextLine()) {
scan.nextLine();
counter.increment();
}
scan.close();
} catch(Exception ex) {
ex.printStackTrace();
}
}
}
/**
* Counts the lines in the given files. Sums all counts up.
* One thread per given filename command-line argument.
*/
public class CountFiles {
public static void main(String[] args) {
SafeCounter counter = new SafeCounter();
CountThread[] threads = new CountThread[args.length];
for(int xx = 0; xx < args.length; xx++)
threads[xx] = new CountThread(args[xx], counter);
for(int xx = 0; xx < args.length; xx++)
threads[xx].start();
try {
for(int xx = 0; xx < args.length; xx++)
threads[xx].join();
} catch(Exception ex) {
ex.printStackTrace();
}
System.out.println("Final count = " + counter.getValue());
}
}
Material in this unit adopted with permission from IC211 at USNA