Threads from aritma

java core 2005. 2. 12. 08:15
 
From
 
Objects and Java Seminar by Bill Venners
Threads
Lecture Handout

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.

'java core' 카테고리의 다른 글

Annotation  (0) 2005.03.18
Java condition variable  (0) 2005.02.18
Reference object model from java world  (0) 2005.01.28
Garbage collection from javaworld  (0) 2005.01.28
자바 코드 컨벤션  (0) 2005.01.24
Posted by '김용환'
,