Agenda

• Introduce multi-threading
• Show two ways to start a thread
• Talk about synchronization for mutual exclusion
• Discuss thread cooperation
• Look at the Java monitor
• Look at thread blocking, liveness, and scheduling

---

Multi-Threading in Java

• Java has support for multi-threading built into the language
• Threads are "sub-processes" within a process
  • User-interface responsiveness
  • Server responsiveness
  • Can take advantage of multi-processors
• Each process has a private data segment. Threads share the data segment of their process.
• Two kinds of synchronization: mutual exclusion and co-operation

---

Subclassing Thread

• In Java, threads are represented by an instance of class java.lang.Thread
• Two ways to define a thread starting point: extend Thread or implementing Runnable
  
  

   1 // In file threads/ex1/RepetitiveThread.java
   2 public class RepetitiveThread extends Thread {
   3
   4     private final String msg;
   5     private final long sleepTime;
   6
   7     public RepetitiveThread(String msg, long sleepTime) {
   8         this.msg = msg;
   9         this.sleepTime = sleepTime;
  10     }
  11
  12     public void run() {
  13
  14         for (;;) {
  15
  16             System.out.println(msg);
  17             try {
  18                 sleep(sleepTime);
  19             }
  20             catch (InterruptedException e) {
  21             }
  22         }
  23     }
  24 }
  
   1 // In file threads/ex1/Example1.java
   2 public class Example1 {
   3
   4     // Args to this application specify "msg"
   5     // and "sleepTime" for multiple threads.
   6     // For example, the command:
   7     //
   8     // $ java Example1 Hi 100 Lo 1000
   9     //
  10     // requests two threads, one that prints
  11     // out "Hi" every 100 milliseconds and
  12     // another that prints out "Lo" every
  13     // 1000 milliseconds.
  14     //
  15     public static void main(String[] args) {
  16
  17         // Require an even argCount
  18         int argCount = args.length;
  19         if ((argCount / 2) == 1) {
  20             --argCount;
  21         }
  22
  23         for (int i = 0; i < argCount; i += 2) {
  24
  25             String msg = args[i];
  26             long sleepTime = Long.parseLong(args[i + 1]);
  27
  28             RepetitiveThread rt =
  29                 new RepetitiveThread(msg, sleepTime);
  30
  31             rt.start();
  32         }
  33     }
  34 }
  

• Java applications keep running until there are no more non-daemon threads.
• Extending Thread often difficult because its hard to fit Thread into the inheritance hierarchy.

---

Implementing Runnable

• Often more flexible to implement Runnable than extend Thread:
  
  

  1 // In file threads/ex2/Animal.java
  2 public class Animal {
  3 }
  
   1 // In file threads/ex2/Cat.java
   2 public class Cat extends Animal implements Runnable {
   3
   4     private final String msg;
   5     private final long sleepTime;
   6
   7     public Cat(String msg, long sleepTime) {
   8         this.msg = msg;
   9         this.sleepTime = sleepTime;
  10     }
  11
  12     public void run() {
  13
  14         for (;;) {
  15
  16             System.out.println(msg);
  17             try {
  18                 Thread.sleep(sleepTime);
  19             }
  20             catch (InterruptedException e) {
  21             }
  22         }
  23     }
  24 }
  
   1 // In Source Packet in file threads/ex2/Example2.java
   2 public class Example2 {
   3
   4     // Args to this application specify "msg"
   5     // and "sleepTime" for multiple threads.
   6     // For example, the command:
   7     //
   8     // $ java Example1 Meow 100 Grrr 1000
   9     //
  10     // requests two threads, one that prints
  11     // out "Meow" every 100 milliseconds and
  12     // another that prints out "Grrr" every
  13     // 1000 milliseconds.
  14     //
  15     public static void main(String[] args) {
  16
  17         // Require an even argCount
  18         int argCount = args.length;
  19         if ((argCount / 2) == 1) {
  20             --argCount;
  21         }
  22
  23         for (int i = 0; i < argCount; i += 2) {
  24
  25             String msg = args[i];
  26             long sleepTime = Long.parseLong(args[i + 1]);
  27
  28             Cat cat = new Cat(msg, sleepTime);
  29
  30             Thread catThread = new Thread(cat);
  31             catThread.start();
  32         }
  33     }
  34 }
  

---

Mutual Exclusion

• Java has an object-oriented way to deal with thread synchronization.
• Data is protected by controlling access to code. (Hence, the data must be private.)
• Can mark blocks of code, or entire methods, as synchronized.
• Synchronized means only one thread at a time can execute the code.

---

The Thread-Safe Object

• A state machine RGBColor object (not thread-safe)

 1 // In file objectidioms/ex6/RGBColor.java
 2 // Instances of this class are NOT thread-safe.
 3
 4 public class RGBColor {
 5
 6     private int r;
 7     private int g;
 8     private int b;
 9
10     public RGBColor(int r, int g, int b) {
11
12         checkRGBVals(r, g, b);
13
14         this.r = r;
15         this.g = g;
16         this.b = b;
17     }
18
19     public void setColor(int r, int g, int b) {
20
21         checkRGBVals(r, g, b);
22
23         this.r = r;
24         this.g = g;
25         this.b = b;
26     }
27
28     /**
29     * returns color in an array of three ints: R, G, and B
30     */
31     public int[] getColor() {
32
33         int[] retVal = new int[3];
34         retVal[0] = r;
35         retVal[1] = g;
36         retVal[2] = b;
37
38         return retVal;
39     }
40
41     public void invert() {
42
43         r = 255 - r;
44         g = 255 - g;
45         b = 255 - b;
46     }
47
48     private static void checkRGBVals(int r, int g, int b) {
49
50         if (r < 0 || r > 255 || g < 0 || g > 255 ||
51             b < 0 || b > 255) {
52
53             throw new IllegalArgumentException();
54         }
55     }
56 }

---

Write/Write Conflicts

Thread	Statement	r	g	b	Color
none	object represents green	0	255	0	GREEN
blue	blue thread invokes setColor(0, 0, 255)	0	255	0	GREEN
blue	checkRGBVals(0, 0, 255);	0	255	0	GREEN
blue	this.r = 0;	0	255	0	GREEN
blue	this.g = 0;	0	255	0	GREEN
blue	blue gets preempted	0	0	0	BLACK
red	red thread invokes setColor(255, 0, 0)	0	0	0	BLACK
red	checkRGBVals(255, 0, 0);	0	0	0	BLACK
red	this.r = 255;	0	0	0	BLACK
red	this.g = 0;	255	0	0	RED
red	this.b = 0;	255	0	0	RED
red	red thread returns	255	0	0	RED
blue	later, blue thread continues	255	0	0	RED
blue	this.b = 255	255	0	0	RED
blue	blue thread returns	255	0	255	MAGENTA
none	object represents magenta	255	0	255	MAGENTA

---

Read/Write Conflicts

Thread	Statement	r	g	b	Color
none	object represents green	0	255	0	GREEN
blue	blue thread invokes setColor(0, 0, 255)	0	255	0	GREEN
blue	checkRGBVals(0, 0, 255);	0	255	0	GREEN
blue	this.r = 0;	0	255	0	GREEN
blue	this.g = 0;	0	255	0	GREEN
blue	blue gets preempted	0	0	0	BLACK
red	red thread invokes getColor()	0	0	0	BLACK
red	int[] retVal = new int[3];	0	0	0	BLACK
red	retVal[0] = 0;	0	0	0	BLACK
red	retVal[1] = 0;	0	0	0	BLACK
red	retVal[2] = 0;	0	0	0	BLACK
red	return retVal;	0	0	0	BLACK
red	red thread returns black	0	0	0	BLACK
blue	later, blue thread continues	0	0	0	BLACK
blue	this.b = 255	0	0	0	BLACK
blue	blue thread returns	0	0	255	BLUE
none	object represents blue	0	0	255	BLUE

---

Thread-Safe RGBColor Object

 1 // In file objectidioms/ex7/RGBColor.java
 2 // Instances of this class are thread-safe.
 3
 4 public class RGBColor {
 5
 6     private int r;
 7     private int g;
 8     private int b;
 9
10     public RGBColor(int r, int g, int b) {
11
12         checkRGBVals(r, g, b);
13
14         this.r = r;
15         this.g = g;
16         this.b = b;
17     }
18
19     public void setColor(int r, int g, int b) {
20
21         checkRGBVals(r, g, b);
22
23         synchronized (this) {
24
25             this.r = r;
26             this.g = g;
27             this.b = b;
28         }
29     }
30
31     /**
32     * returns color in an array of three ints: R, G, and B
33     */
34     public int[] getColor() {
35
36         int[] retVal = new int[3];
37
38         synchronized (this) {
39
40             retVal[0] = r;
41             retVal[1] = g;
42             retVal[2] = b;
43         }
44
45         return retVal;
46     }
47
48     public synchronized void invert() {
49
50         r = 255 - r;
51         g = 255 - g;
52         b = 255 - b;
53     }
54
55     private static void checkRGBVals(int r, int g, int b) {
56
57         if (r < 0 || r > 255 || g < 0 || g > 255 ||
58             b < 0 || b > 255) {
59
60             throw new IllegalArgumentException();
61         }
62     }
63 }

---

Ready for Threads

Thread	Statement	r	g	b	Color
none	object represents green	0	255	0	GREEN
blue	blue thread invokes setColor(0, 0, 255)	0	255	0	GREEN
blue	checkRGBVals(0, 0, 255);	0	255	0	GREEN
blue	blue thread acquires lock	0	255	0	GREEN
blue	this.r = 0;	0	255	0	GREEN
blue	this.g = 0;	0	255	0	GREEN
blue	blue gets preempted	0	0	0	BLACK
red	red thread invokes setColor(255, 0, 0)	0	0	0	BLACK
red	checkRGBVals(255, 0, 0);	0	0	0	BLACK
red	red thread blocks because object locked	0	0	0	BLACK
blue	later, blue thread continues	0	0	0	BLACK
blue	this.b = 255	0	0	0	BLACK
blue	blue thread returns and releases lock	0	0	255	BLUE
red	later, red thread acquires lock and continues	0	0	255	BLUE
red	this.r = 255;	0	0	255	BLUE
red	this.g = 0;	255	0	255	MAGENTA
red	this.b = 0;	255	0	255	MAGENTA
red	red thread returns and releases lock	255	0	0	RED
none	object represents red	255	0	0	RED

---

The Thread-Safe Object

• Make instance variables private
• Figure out what the monitor regions should be and mark them synchronized
• Make objects thread-safe only if they'll actually be used in a multi-threaded environment
• Why? Performance hit from acquiring the lock and the possibility of deadlock

---

Synchronized Class Methods

• Can also synchronize class methods, as in:
  
  

  // In file Cat.java
  public class Cat {
      public static final int MAX_LIVES = 9;
      private static Cat[] lives = new Cat[MAX_LIVES];
      public static synchronized Cat[] getLives() {
          return lives;
      }
      //...
  }
  

• To enter a synchronized class method, must lock the class's java.lang.Class object.

---

Thread Cooperation

• Mutual exclusion is only half of the thread synchronization story: Java also supports thread cooperation.
• Example: Producer thread and consumer thread
  
  

  Thread	Action	Data
  consumer	Any Data?	none
  consumer	WAIT	none
  producer	Buffer Full?	none
  producer	Give	1, 2, 3
  producer	NOTIFY	1, 2, 3
  producer	Process	1, 2, 3
  consumer	Any Data?	1, 2, 3
  consumer	Take	none
  consumer	NOTIFY	none
  consumer	Process	none
  consumer	Any Data?	none
  consumer	WAIT	none
  producer	Buffer Full?	none
  producer	Give	5, 7, 11
  producer	NOTIFY	5, 7, 11
  producer	Process	5, 7, 11
  producer	Buffer Full?	5, 7, 11
  producer	WAIT	5, 7, 11
  consumer	Any Data?	5, 7, 11
  consumer	Take	none
  consumer	NOTIFY	none
  consumer	Process	none
  producer	Buffer Full?	none
  producer	Give	13, 17, 19
  producer	NOTIFY	13, 17, 19
  producer	Process	13, 17, 19
  consumer	Any Data?	13, 17, 19
  consumer	Take	none
  consumer	NOTIFY	none
  consumer	Process	none
  consumer	Any Data?	none
  consumer	WAIT	none

---

The Java Monitor

• A monitor is like a building that contains one special room (which usually contains some data) that can be occupied by only one thread at a time.
  
  

---

Cooperation Example

 1 // In file threads/ex6/IntBuffer.java
 2 public class IntBuffer {
 3
 4     private final int buffSize;
 5     private int[] buff;
 6
 7     // Keeps track of next buff array location
 8     // to be filled. When nextBuffIndex ==
 9     // buffSize, the buffer is full. When
10     // nextBuffIndex == 0, the buffer is
11     // empty.
12     private int nextBuffIndex;
13
14     IntBuffer(int buffSize) {
15
16         this.buffSize = buffSize;
17         buff = new int[buffSize];
18     }
19
20     public synchronized void add(int val) {
21
22         while (nextBuffIndex == buffSize) {
23
24             try {
25                 wait();
26             }
27             catch (InterruptedException e) {
28             }
29         }
30
31         buff[nextBuffIndex] = val;
32         ++nextBuffIndex;
33
34         notifyAll();
35     }
36
37     public synchronized int removeNext() {
38
39         while (nextBuffIndex == 0) {
40
41             try {
42                 wait();
43             }
44             catch (InterruptedException e) {
45             }
46         }
47
48         // This buffer is FIFO, so remove the
49         // first int added and shift the rest
50         // over.
51         int val = buff[0];
52
53         --nextBuffIndex;
54         for (int i = 0; i < nextBuffIndex; ++i) {
55
56             buff[i] = buff[i + 1];
57         }
58
59         notifyAll();
60         return val;
61     }
62 }

 1 // In file threads/ex6/PrimeNumberGenerator.java
 2 public class PrimeNumberGenerator implements Runnable {
 3
 4     private final IntBuffer buff;
 5
 6     public PrimeNumberGenerator(IntBuffer buff) {
 7
 8         this.buff = buff;
 9     }
10
11     public void run() {
12
13         int primeNum = 1;
14         int numToCheck = 2;
15
16         buff.add(primeNum);
17
18         for (;;) {
19
20             boolean foundPrime = true;
21
22             for (int divisor = numToCheck / 2; divisor > 1;
23                 --divisor) {
24
25                 if (numToCheck % divisor == 0) {
26                     foundPrime = false;
27                     break;
28                 }
29             }
30
31             if (foundPrime) {
32                 primeNum = numToCheck;
33                 buff.add(primeNum);
34             }
35
36             ++numToCheck;
37         }
38     }
39 }

 1 // In source packet in file threads/ex6/IntPrinter.java
 2 public class IntPrinter implements Runnable {
 3
 4     private final IntBuffer buff;
 5
 6     public IntPrinter(IntBuffer buff) {
 7
 8         this.buff = buff;
 9     }
10
11     public void run() {
12
13         for (;;) {
14
15             int val = buff.removeNext();
16             System.out.println(val);
17         }
18     }
19 }

 1 // In file threads/ex6/Example6.java
 2 public class Example6 {
 3
 4     public static void main(String[] args) {
 5
 6         IntBuffer buff = new IntBuffer(3);
 7
 8         PrimeNumberGenerator png = new PrimeNumberGenerator(buff);
 9         IntPrinter ip = new IntPrinter(buff);
10
11         Thread producer = new Thread(png);
12         Thread consumer = new Thread(ip);
13
14         producer.start();
15         consumer.start();
16     }
17 }

---

Thread Blocking

• A thread can be in any of 4 states:
  
  
  • new
  • runnable
  • dead
  • blocked
  
  
• A thread can be blocked for any of 4 reasons:
  
  
  • Sleeping (the thread invoked sleep())
  • In entry set of a monitor (the thread invoked a synchronized method)
  • In wait set of a monitor (the thread invoked wait())
  • Waiting for an I/O operation

---

Program Liveness

• Liveness means a program will isn't "hung" and will eventually do something useful.
• A multi-threaded program can lose its liveness in several ways:
  
  
  • Deadlock
  • Unsatisfied wait condition
  • Starvation
  
  
• Thread safety often conflicts with thread liveness.
  
  
  • If no synchronized methods, program can't deadlock.

---

Thread Scheduling

• The JVM holds non-blocked threads in priority-based scheduling queues.
  
  
  • By default, each new thread gets the same priority as its creator.
  • Can change a thread's priority by invoking setPriority().
  
  
• JVMs are encouraged to:
  
  
  • Cycle through highest priority threads (not necessarily in a fair way).
  • Preempt lower priority threads in favor of higher priority threads.
  
  
• Invoking yield() indicates to the JVM that you are ready for a rest.
• Don't depend on "time-slicing" for program correctness.

---

Exercise: The Dreaded, Threaded Fibonacci Generator

Create a Java application named Problem1 that generates the Fibonacci sequence. The first two numbers of the Fibonacci sequence are 1 and 1. Each subsequent number is calculated by summing the previous two numbers, as in: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, and so on.

Input to the Application

The Problem1 application will write the Fibonacci sequence to the standard output. The Problem1 application, which requires no command line arguments, should print out the first 92 Fibonacci numbers The output will look like:

1
1
2
3
5
8
13
<...>

The maximum of 92 arises because the 93rd Fibonacci number is too big to express in a Java long. The biggest Fibonacci number that will fit in Java's long (a 64 bit signed integer) is 7540113804746346429L, which is the 92nd Fibonacci number.

Structure of the Application

The application will be made up of four classes, named:

FibonacciGenerator.java
LongBuffer.java
LongBufferToOutputThread.java
Problem1.java

The application will contain three threads, the main thread and two extra threads that the main thread will start. The two extra threads are defined by FibonacciGenerator, which implements Runnable, and LongBufferToOutputThread, which directly subclasses class Thread.

The main() method of the Problem1 application will create and start these two threads and connect the output of the FibonacciGenerator thread to the input of the LongBufferToOutputThread. The Fibonacci numbers will be generated by the FibonacciGenerator thread, which writes one long value at time into a LongBuffer. The LongBufferToOutputThread will then read long's from the LongBuffer and write them to the standard output.

Classes of the Application

Class Problem1

The main() method should:

• Create a LongBuffer object with a buffer size of 3.
• Create a FibonacciGenerator. object
• Create a LongBufferToOutputThread object.
• Start the FibonacciGenerator and LongBufferToOutputThread threads.
• This main thread is now finished and can just return from the main() method.

Class LongBuffer

You can base this class on the IntBuffer class from the lecture slides, which is in the Threads/examples/ex6 directory of the sample code:

// In source packet in file threads/ex6/IntBuffer.java
public class IntBuffer {
    private final int buffSize;
    private int[] buff;
    // Keeps track of next buff array location
    // to be filled. When nextBuffIndex ==
    // buffSize, the buffer is full. When
    // nextBuffIndex == 0, the buffer is
    // empty.
    private int nextBuffIndex;
    IntBuffer(int buffSize) {
        this.buffSize = buffSize;
        buff = new int[buffSize];
    }
    public synchronized void add(int val) {
        while (nextBuffIndex == buffSize) {
            try {
                wait();
            }
            catch (InterruptedException e) {
            }
        }
        buff[nextBuffIndex] = val;
        ++nextBuffIndex;
        notifyAll();
    }
    public synchronized int removeNext() {
        while (nextBuffIndex == 0) {
            try {
                wait();
            }
            catch (InterruptedException e) {
            }
        }
        // This buffer is FIFO, so remove the
        // first int added and shift the rest
        // over.
        int val = buff[0];
        --nextBuffIndex;
        for (int i = 0; i < nextBuffIndex; ++i) {
            buff[i] = buff[i + 1];
        }
        notifyAll();
        return val;
    }
}

Basically, LongBuffer has to do a similar thing to what IntBuffer does, but for longs instead of ints. It needs an add() method and a long removeNext() method, and it must assume different threads will be calling these methods. Thus, the add() and removeNext() methods must be synchronized and use wait() and notifyAll().

Class FibonacciGenerator

This class extends Object and implements Runnable. It has one constructor, which takes one argument: a LongBuffer reference.

It's run() method simply produces the Fibonacci sequence one long at a time and writes each one to the LongBuffer as it is produced. To indicate that it is finished producing numbers, the FibonacciGenerator class declares a public static final int END_OF_DATA field that is initialized to -1. When the FibonacciGenerator's run() method is done generating the first 92 Fibonacci numbers, it writes an END_OF_DATA to the LongBuffer. After that, this thread is finished and the run() method simply returns.

Class LongBufferToOutputThread

This class extends Thread. It has one constructor, which takes one argument: a LongBuffer.

It's run() method simply reads one long at a time from the LongBuffer and writes it as a String to the standard output, placing a return ('\n') after each number it prints. It keeps doing this until it reads an FibonacciGenerator.END_OF_DATA from the LongBuffer. When it finds END_OF_DATA, the run() method returns, and this thread expires.

Odds and Ends

How the app knows to terminate: A Java application terminates when all non-daemon threads expire. In this application, there are three non-daemon threads. The main thread sets up and starts the other two threads, then returns. One thread down. The FibonacciGenerator thread generates the numbers, stores them into the LongBuffer, then writes an END_OF_DATA into the LongBuffer, and returns. By returning from run(), the FibonacciGenerator thread expires. Two threads down. The LongBufferToOutputThread reads from the LongBuffer and writes to the standard output until it finds an END_OF_DATA in the LongBuffer. It then returns. By returning from run(), the LongBufferToOutputThread thread expires. Because this is the third and only remaining non-daemon thread, the entire application terminates.