 |
Lecture Notes Six: Threads
|
Individual execution paths (with or without sharing).
Here‘s an applet that illustrates the notion.
A thread is a single sequential flow of control within a process.
A single process can have multiple concurrently executing threads. For example, a process may have a thread reading input from the user, while at the same time another thread is updating a database containing the user‘s account balance, while at the same time a third thread is updating the display with the latest stock quotes. Such a process is called a multithreaded process; the program from which this process executes is called a multithreaded program. The Thread class is used to represent a thread, with methods to control the execution state of a thread.
To create a new thread of execution, you first declare a new class that is a subclass of Thread and override the run() method with code you want executed in this thread.
class myThread extends Thread {
public void run() {
// do something
}
}
You then create an instance of this subclass, followed by a call to the start() method (which really is, because of inheritance, Thread.start(). That method will execute the run() method defined by this subclass.
myThread m = new myThread();
m.start();
// something else
You can achieve the same effect by having the class directly implement the Runnable interface.
class A implements Runnable {
public void run () {
// do something
}
}
To create a thread to execute this run() method, do the following:
A a = new A();
Thread m = new Thread(a);
m.start();
// do something else
Thread Priorities Each thread has a priority that is used by the Java runtime in scheduling threads for execution. A thread that has a higher priority than another thread is typically scheduled ahead of the other thread. However, the way thread priorities are precisely affect scheduling is platform-dependent. A thread inherits its priority from the thread that created it. A thread‘s priority can be changed subsequent to the thread‘s creation at any time using the setPriority() method in the Thread class, if allowed by the security manager.
Thread State and Synchronization between Threads When a thread is started, its state is active. Its state remains active until it has terminated execution or is stopped. An active thread can be executing or suspended. When a thread is first started, it starts executing its run() method. The Thread class provides methods for you to suspend an executing thread, to resume execution of a suspended thread, and to stop a thread completely (it can no longer run unless restarted at the beginning of its run() method). These methods can be invoked only if allowed by the security manager. In addition to these methods in the Thread class, you can also use synchronization methods available in the Object class (wait() and notify()) to control the execution of a thread.
Interrupts A thread can send an interrupt to another thread. This sets a flag in the target thread to indicate that it has been interrupted. The target thread can then check for this flag at its discretion and react appropriately.
Examples
There are four kinds of threads programming:
- unrelated threads
- related (but unsynchronized) threads
- mutually-exclusive threads
- communicating and mutually-exclusive threads
1. Unrelated Threads The simplest threads program involves threads of control that do different things and don‘t interact with each other, and this will be our first example.
frilled.cs.%cat Drinks.java
public class Drinks {
public static void main(String[] a) {
Coffee t1 = new Coffee();
t1.start();
new Tea().start(); //an anonymous thread
}
}
class Coffee extends Thread {
public void run() {
try {
while (true) {
System.out.println("I like coffee...");
sleep(500);
}
} catch (InterruptedException e) {
return; // end this thread
}
}
}
class Tea extends Thread {
public void run() {
try {
while (true) {
System.out.println("I like tea...");
sleep(700);
}
} catch (InterruptedException e) {
return; // end this thread
}
}
}
frilled.cs.%javac Drinks.java
frilled.cs.%java Drinks
I like coffee...
I like tea...
I like coffee...
I like tea...
I like coffee...
I like tea...
I like coffee...
I like coffee...
I like tea...
I like coffee...
I like tea...
I like coffee...
I like tea...
I like coffee...
I like coffee...
I like tea...
I like coffee...
I like tea...
I like coffee...
I like coffee...
I like tea...
I like coffee...
I like tea...
I like coffee...
I like tea...
I like coffee...
I like coffee...
I like tea...
I like coffee...
frilled.cs.%
This was our first example.
2. Related but Unsynchronized Types
This level of complexity has threaded code to partition a problem, solving it by having multiple threads work on different pieces of the same data structure. The threads don‘t interact with each other. Here, threads of control do work that is sent to them, but don‘t work on shared data, so they don‘t need to access it in a synchronized way.
An example of this would be spawning a new thread for each socket connection that comes in.
A less common but still interesting example of related but unsynchronized threads involves partitioning a data set, and instantiating multiple copies of the same thread to work on different pieces of the same problem. Be careful not to duplicate work, or even worse, to let two different threads operate on the same data at once.
Here‘s an example program that tests whether a given number is a prime number. That involves a lot of divisions so it‘s a good candidate for parcelling the work out among a number of threads. Tell each thread the range of numbers it is to test-divide into the possible prime. Then let them all loose in parallel, as illustrated below. First the code:
frilled.cs.%cat TestPrime.java
public class TestPrime {
public static void main(String s[]) {
long possPrime = Long.parseLong(s[0]);
int centuries = (int) (possPrime/100) + 1;
for (int i=0; i < centuries; i++) {
new TestRange(i*100, possPrime).start();
}
}
}
class TestRange extends Thread {
static long possPrime;
long from, to;
// constructor
// record the number we are to test, and
// the range of factors we are to try
TestRange (int argFrom, long argPossPrime) {
possPrime = argPossPrime;
if (argFrom == 0) from = 2;
else from = argFrom;
to = argFrom + 99;
}
public void run () {
for (long i = from; i <= to && i < possPrime; i++) {
if (possPrime % i == 0) { // i divides possPrime exactly
System.out.println("factor " + i +
" found by thread " + getName());
return;
}
yield();
}
}
}
frilled.cs.%javac TestPrime.java
frilled.cs.%java TestPrime 9001
frilled.cs.%java TestPrime 9002
factor 2 found by thread Thread-0
factor 643 found by thread Thread-6
factor 1286 found by thread Thread-12
factor 4501 found by thread Thread-45
frilled.cs.%
I will have a few questions in class but won‘t list them here now.
3. Mutually-Exclusive Threads
Here‘s where threads start to interact with each other, and that makes life a little more complicated. In particular we use threads which need to work on the same pieces of the same data structure. These threads need to take steps to stay out of each others‘ way so that they don‘t each simultaneously modify the same piece of data leaving an uncertain result. Staying out of each other‘s way is known as mutual exclusion. Here‘s an example.
The code below simulates a steam boiler. It defines some values (the current reading of a pressure gauge, and the safe limit for that gauge), and then instantiates 10 copies of a thread called pressure storing them in an array. The main routine concludes by waiting for each threads to finish (.join) and then prints the current value of the pressure gauge.
public class SteamBoiler {
static int pressureGauge = 0;
static final int safetyLimit = 20;
public static void main(String[] args) {
Pressure[] p1 = new Pressure[10];
for (int i = 0; i < 10; i++) {
p1[i] = new Pressure();
p1[i].start();
}
try {
for (int i=0; i < 10; i++)
p1[i].join();
} catch (Exception e) {
System.out.println(e);
}
System.out.println("gauge reads " + pressureGauge + ", safelimit is 20.");
}
}
class Pressure extends Thread {
void RaisePressure () {
if (SteamBoiler.pressureGauge < SteamBoiler.safetyLimit - 15) {
// wait briefly to simulate some calculations
try {
sleep(100);
} catch (Exception e) {
}
SteamBoiler.pressureGauge += 15;
} else ; // pressure too high -- don‘t add to it.
}
public void run() {
RaisePressure();
}
}
And here‘s the output when you try to run it:
frilled.cs.%java SteamBoiler
gauge reads 150, safelimit is 20.
frilled.cs.%
That‘s not good.
This is a classic example of what is called a data race or a race condition. A race condition occurs when two or more threads update the same value simultaneously.
To avoid data races, follow this simple rule: whenever two threads access the same data, they must use mutual exclusion. You can optimize slightly, by allowing multiple readers at one instant.
In Java, thread mutual exclusion is built on data Objects. Every Object in the system has its own mutex semaphore (strictly speaking this is only allocated if it is being used), so any Object in the system can be used as the "turnstile" or "thread serializer" for threads. You use the synchronized keyword and explicitly or implicitly provide an Object, any Object to synchronize on. The runtime system will take over and apply the code to ensure that, at most, one thread has locked that specific object at any given instant. The synchronized keyword can be applied to a:
- class
- method
- block of code
In each case, the mutex (MUTual EXclusion) lock of the name object is acquired, then the code is executed, then the lock is released. If the lock is already held by the another thread, then the thread that wants to acquire the lock is suspended until the lock is released.
The Java programmer never deals with the low-level and error-prone details of creating, acquiring and releasing locks, but only specifies the region of code and the object that must be exclusively held in that region. You want to make your regions of synchronized code as small as possible, because mutual exclusion really chokes performance. Here are examples of each of these alternatives of synchronizing over a class, a method, or a block, with comments on how exclusion works.
Mutual exclusion over an entire class
This is achieved by aplying the keyword synchronized to a class method (a method with the keyword static). Only one static synchronized method for a particular class can be running at any given time. The threads are implicitly synchronized using the class object.
static synchronized void RaisePressure() { ... }
Here are some exercises for your practice.
 EXERCISES
- first, make the threads report their names when raising the pressure
- then solve the problem with a static and synchronized method
- then try to solve it with a non-static synchronized method
- then make your solution report the name of the thread that raised the pressure
Mutual exclusion over a block of statements
This is achieved by attaching the keyword synchronized before a block of code. You also have to explicitly mention in parens the object whose lock must be acquired before the region can be entered.
void RaisePressure () {
synchronized(someObject) {
if (SteamBoiler.pressureGauge < SteamBoiler.safetyLimit - 15) {
// same code as before
} else ; // pressure too high -- don‘t add to it.
}
}
You need to provide the Obj object, so we declare it in steamBoiler:
static Object semaphore = new Object();
 EXERCISES
- solve the problem this way
- why is
this not working
- solve the problem so it reports the thread that raises the pressure
- change the problem so threads wait a bit (randomly) before checking the pressure
Mutual exclusion over a method
This is achieved by applying the keyword synchronized to an ordinary (non-static) method. Note that in this case the object whose lock will provide the mutual exclusion is implicit, (it is the this object on which the method is invoked).
synchronized void fun() { ... }
is equivalent to
void fun() {
synchronized(this) {
...
}
}
Note: this won‘t work in our example for obvious reasons (each one of the 10 pressure checker threads will be able to seize a lock on themselves and the race condition will reoccur).
 EXERCISES
- when could we use this method to solve our original problem or, could we?
Synchronized methods are useful when you have several different methods that might be called simultaneously on the same one object. It ensures that at most one of all the methods designated as synchronized will be invoked on that one object at any given instant. The synchronized methods will exclude each other but they do not exclude a non-synchronized method, nor a (synchronized or non-synchronized) static (class) method from running (which is useful to know).
4. Communicating and Mutually-Exclusive Threads
Here‘s where things become downright complicated until you get familiar with the protocol. The hardest kind of threads programming is where the threads need to pass data back and forth to each other. Imagine that we are in the same situation as in the previous section: we have threads that process the same data, so we need to run synchronized. However, in our new case, imagine that it‘s not enough just to say "don‘t run while I am running". We need the threads to be able to say: "OK, I have some data ready for you" and to suspend themselves if there isn‘t data ready.
There‘s a convenient parallel programming idiom, known as wait/notify that does exactly this.
Wait/notify is a tricky language-dependent protocol that has been developed by ingenious minds. You just need to accept it as the right solution to your problem. It is used when synchronized methods in the same class need to communicate with each other.
The most common occurrence of this is a producer/consumer situation - one thread is producing the data irregularly, and another thread is consuming (processing) it when it can.
Usually the producer is storing the produced data into some kind of bounded buffer which means that the produce(r) may fill it up and will need to wait() until there is room. The consumer will need to notify() the producer when something is removed from the buffer.
Here‘s the pseudo-code for the WaitNotify.java program below:
//producer thread: produces one datum
enter synchronized code (i.e., grab mutex lock)
while (buffer_full)
wait() // read below the semantics of wait (re: lock)
produce_data
notify()
leave synchronized code (i.e., release lock)
//consumer thread: consumes one datum
enter synchronized code (i.e., grab mutex lock)
while (no_data) // buffer_empty
wait()
consume_data()
notify
leave synchronized code (i.e., release lock)
Wait and Notify:
- Wait says:
Oops, even though I have the lock I can‘t go any further until you have some data for me, so I will release the lock, and suspend myself here. One of you notifiers (grab the lock and) carry on!
- Notify says:
Hey, I just produced some data, so I will release the lock and suspend myself here. One of you waiters (grab the lock from me and) carry on!
wait and notify are methods in the basic class Object so they are shared by all objects in the system.
There are several variants:
public final native void notify();
public final native void notifyAll();
public final void wait () throws InterruptedException;
public final void wait (long time, int nanos) throws InterruptedException;
public final native void wait (long timeout) throws InterruptedException;
The difference between
is that the second one
- wakes up all threads that are in the wait list of this object.
There are three classes below.
- The first is a class that contains a main driver program. It simply instantiates a producer thread and a consumer thread and lets them go at it. (This one is in
WaitNotify.java)
- The second class is the Producer class. It implements the pseudo-code above, and demonstrates the use of
wait/notify.
It has two key methods:
- one that produces actual data (called
banana(), only reads the number of millisecs the program has been running) and stores it into an array (called buffer).
- the other method (called
consume()) will try to return successive values from this array. The value of this set-up is that produce() and consume() can be called from separate threads: they won‘t overrun the array; they won‘t get something before it has been produced; they won‘t step on each other; neither ever gets in a busy wait.
- The third class is another thread that will be the consumer in this example.
It starts off with a common Java idiom: another instance is passed into the constructor, and all the constructor does is save a copy of this object for later use. This is the way that the consumer can call the consume() method of the producer.
Here‘s the code and a sample run:
frilled.cs.%ls -ld *.java
-rw------- 1 dgerman 517 Apr 10 16:04 Consumer.java
-rw------- 1 dgerman 1002 Apr 10 16:27 Producer.java
-rw------- 1 dgerman 173 Apr 10 15:59 WaitNotify.java
frilled.cs.%cat W*.java
public class WaitNotify {
public static void main(String args[]) {
Producer p = new Producer();
p.start();
Consumer c = new Consumer(p);
c.start();
}
}
frilled.cs.%cat P*.java
class Producer extends Thread {
private String[] buffer = new String[8];
private int pi = 0; // produce index
private int gi = 0; // get index
public void run () {
// just keep producing
for (;;)
produce();
}
private final long start = System.currentTimeMillis();
private final String banana() {
return "" + (int) (System.currentTimeMillis() - start);
}
synchronized void produce() {
// while there isn‘t room in the buffer
while (pi-gi + 1 > buffer.length) {
try {
wait();
} catch (Exception e) { }
}
buffer[pi&0x7] = banana();
System.out.println("produced[" + (pi&0x7) + "] " + buffer[pi&0x7]);
pi++;
notifyAll();
}
synchronized String consume() {
// while there‘s nothing left to take from the buffer
while (pi == gi) {
try {
wait();
} catch (Exception e) { }
}
notifyAll();
return buffer[gi++&0x7];
// mask off the bits (lowest 3 bits - circular buffer)
}
}
frilled.cs.%cat C*.java
class Consumer extends Thread {
Producer whoIamTalkingTo;
// java idiom for constructor
Consumer (Producer who) { whoIamTalkingTo = who; }
public void run() {
java.util.Random r = new java.util.Random();
for (;;) {
String result = whoIamTalkingTo.consume();
System.out.println("consumed: " + result);
// next line is just to make it run a bit slower
int randomtime = r.nextInt() % 250;
try { sleep(randomtime); } catch (Exception e) { }
}
}
}
frilled.cs.%javac W*.java
frilled.cs.%java WaitNotify
produced[0] 3
produced[1] 5
produced[2] 6
produced[3] 7
produced[4] 7
produced[5] 7
produced[6] 8
produced[7] 8
consumed: 3
produced[0] 10
consumed: 5
produced[1] 96
consumed: 6
consumed: 7
consumed: 7
consumed: 7
consumed: 8
consumed: 8
consumed: 10
consumed: 96
produced[2] 349
produced[3] 349
produced[4] 350
produced[5] 350
produced[6] 350
produced[7] 351
produced[0] 351
produced[1] 351
consumed: 349
consumed: 349
consumed: 350
consumed: 350
consumed: 350
produced[2] 507
produced[3] 513
produced[4] 513
produced[5] 514
produced[6] 514
consumed: 351
produced[7] 626
consumed: 351
produced[0] 796
consumed: 351
consumed: 507
consumed: 513
produced[1] 926
produced[2] 927
produced[3] 927
consumed: 513
produced[4] 956
consumed: 514
consumed: 514
produced[5] 1126
produced[6] 1126
consumed: 626
produced[7] 1276
consumed: 796
produced[0] 1336
consumed: 926
produced[1] 1346
consumed: 927
consumed: 927
consumed: 956
produced[2] 1566
produced[3] 1567
produced[4] 1567
consumed: 1126
consumed: 1126
consumed: 1276
produced[5] 1656
produced[6] 1657
produced[7] 1657
consumed: 1336
consumed: 1346
consumed: 1566
consumed: 1567
produced[0] 1907
produced[1] 1907
produced[2] 1907
produced[3] 1908
consumed: 1567
produced[4] 2076
^Cfrilled.cs.%exit
 EXERCISES
- change the program to work with one producer and several consumers
Notes
- Code like this:
try { sleep (randomtime); } catch (Exception e) { }
try { wait(); } catch(Exception e) {}
acknowledges the fact that one thread can interrupt another sleeping thread by calling its interrupt() method. This will make the interrupted thread wake up. It really needs to tell the difference between waking up because it has been "notified" and waking up because it has been "interrupted". So the second case is detected by raising the exception InterruptedException in the thread, Statements like sleep() and wait() that are potentially prone to being interrupted in the middle need to catch this exception.
- Always catch the narrowest type of exception you can or you may catch more than you bargained for. And always do something sensible with it, like print an error message.
- Synchronized code isn‘t a perfect solution, you need to make sure you avoid deadlock.
Last updated: Apr 8, 2002 by Adrian German for NC009
|
