Multithreading in Java

What is a thread?

Operating systems can run several programs in parallel. This is called multitasking or multi-processing. If the computer has several processors, then each program might run on a different processor. This is true parallel processing. Otherwise, the programs take turns running on whatever processors are available. This is simulated parallel processing. The operating system facilitates the turn-taking by quickly switching from one program to the next.

Operating systems also allow programs to execute several functions in parallel. This is called multithreading. Again each function might be running on a separate processor—true parallelism—or they might take turns running on whatever processors are available—simulated parallelism. Here too the operating system facilitates the turn-taking by quickly switching from one function to the next.

Think of a thread as a virtual processor with its own stack, registers, and instruction pointer. If a program has 10 threads, then 10 functions can be executing in "parallel".

Applications of threads

Application 1: User interface thread

A program might have a function that runs forever or at least for a long time. The user would like to be able to suspend, resume, or stop the execution of this function. But how? If the program is sucking up all of the processor time, then how will the user tell the program to stop? Simple. The user interface runs in a different thread from the function. While the function is busy burning processor cycles in its thread, the user interface thread is listening for user inputs.

Application 2: Server threads

A server perpetually listens for incoming requests from clients. For example, a web server perpetually listens for HTTP requests from web browsers. Servers are often bombarded with requests coming from all over the world. In the time it would take for a server to service a single request many more requests may have come in and been ignored, causing frustration for users. Instead, the server creates a thread and runs the request handler function in it, then goes back to listening for more requests.

Application 3: Multi-Agent Programs

An agent is an autonomous, goal-driven object:

class Agent {
  State state, goal;
  void run() {
     while(state != goal) {
        state = update(state);
     }
  }
  State update(State state) { ... }
}

Agents are useful for modeling populations of animals, machines, companies, characters in a game, etc. But each agent's run loop may run forever or for a very long time, blocking other agents from running their run loops. To overcome this, each agent's run loop can run in a separate thread.

Active Objects

In object-oriented programming an active object is an object that owns a thread. Any method called by the object is executed in its thread (even if the method belongs to a different object).

In UML notation a class of active objects (called an active class) has double borders on its sides:

Active Objects in Java

Active objects implement Java's runnable interface.

interface Runnable {
   public void run();
}

For example:

class Agent implements Runnable {
  State state, goal;
  void run() {
     while(state != goal) {
        state = update(state);
     }
  }
  State update(State state) { ... }
}

Threads are instances of Java's Thread class:

class Thread implements Runnable {
   private Runnable runner;
   public void start() {
      if (runner!= null) runner.run();
      else run();
   }
   public void run() { /* no-op */ } // overridable
   // etc.
}

If it has a runner, a thread executes its run function:

Thread thread = new Thread(new Agent());
thread.start();

Alternatively, programmers can directly extend Thread and override run:

class Agent extends Thread {
  State state, goal;
  void run() {
     while(state != goal) {
        update();
     }
  }
  void update() { ... }
}

This technique is a bit simpler because we don't need to create a separate thread:

Agent agent = new Agent();
agent.start();

However, Agent can't extend from more classes.

Example

In this example states are integers. The goal is to reach state 0 by repeatedly dividing by 3:

class Agent implements Runnable {

  private int state, goal;
  private String name;
 
  public Agent(String name, int state) {
     this.goal = 0;
     this.state = state;
     this.name = name;
  }
 
   public String toString() {
       return name + ".state = " + state;
    }

  public void run() {
     while(state != goal) {
        update();
        System.out.println(this.toString());
     }
  }

  public void update() {
     state = state/3;
  }

}

A manager manages a population of three agents:

public class Manager {
 
  private Agent[] agents;
 
  public Manager() {
     agents = new Agent[3];
     agents[0] = new Agent("Agent 1", 50);
     agents[1] = new Agent("Agent 2", -30);
     agents[2] = new Agent("Agent 3", 75);
  }
 
  public void run() {
     for(int i = 0; i < agents.length; i++) {
        Thread thread = new Thread(agents[i]);
        thread.start();
     }
     System.out.println("all done");
  }
 
  public static void main(String[] args) {
     Manager manager = new Manager();
     manager.run();
  }
}

Here's the output produced:

all done
Agent 1.state = 16
Agent 1.state = 5
Agent 1.state = 1
Agent 1.state = 0
Agent 3.state = 25
Agent 3.state = 8
Agent 3.state = 2
Agent 3.state = 0
Agent 2.state = -10
Agent 2.state = -3
Agent 2.state = -1
Agent 2.state = 0

Notice that each agent reached its goal, but they didn't take turns. That's because some operating systems don't interrupt threads unless the thread is suspended for some reason such as waiting for input. A cooperative thread suspends itself after each update by going to sleep for a few milliseconds:

Here's the run method of a cooperative agent:

public void run() {
  while(state != goal) {
     update();
     try {
        Thread.sleep(100); // be cooperative
     } catch (Exception e) {
           System.out.println(e);
     }
     System.out.println(this.toString());
  }
}

Here's the output produced:

all done
Agent 1.state = 16
Agent 3.state = 25
Agent 2.state = -10
Agent 2.state = -3
Agent 3.state = 8
Agent 1.state = 5
Agent 3.state = 2
Agent 1.state = 1
Agent 2.state = -1
Agent 2.state = 0
Agent 1.state = 0

Waiting for threads to die

Notice that the manager's run function terminates immediately after it starts its threads. (We can tell this because the "all done" message appears before the agents begin producing output.) This is a problem if the manager needs to do some work after the agents have stopped. For example, each agent might be computing the length of a route from San Jose to New York. After the lengths are computed, the manager must select the shortest one.

To solve this problem the Thread class has a join method. Calling this method causes the joiner to block until the thread finishes execution.

Unfortunately, our agents aren't threads. Instead, they run inside of threads (it would be different if Agent extended Thread). Somehow, the agent must catch the thread that it's running inside of. Fortunately, the thread class maintains a static reference to the currently executing thread. Here's how we can make use of this:

public class Agent implements Runnable {

  private Thread thread;
 
  public void join() throws InterruptedException {
     if (thread != null) thread.join();
  }

  public void run() {
     thread = Thread.currentThread(); // catch my thread
     while(!isStopped()) {
        update();
        if (state == goal) stop();
        else
           try {
              Thread.sleep(100);
           } catch (Exception e) {
              System.out.println(e);
           }
        System.out.println(this.toString());
     }
  }
  // etc.
}

After launching the threads, the manager joins the first thread, when it stops, it joins the second thread, etc. Joining a thread that's already stopped does nothing.

public class Manager {
 
  public void run() {
     for(int i = 0; i < agents.length; i++) {
        Thread thread = new Thread(agents[i]);
        thread.start();
     }
     // wait for agents to die
     for(int i = 0; i < agents.length; i++) {
        try {
           agents[i].join();
        } catch(InterruptedException ie) {
           System.err.println(ie.getMessage());
        } finally {
           System.out.println(agents[i].getName() + " has died");
        }
     }
     System.out.println("all done");
  }
  // etc.
}

Here's the output produced. Notice that the "all done" message appears at the end.

Agent 3.state = 25
Agent 2.state = -10
Agent 1.state = 16
Agent 3.state = 8
Agent 2.state = -3
Agent 1.state = 5
Agent 1.state = 1
Agent 1.state = 0
Agent 3.state = 2
Agent 2.state = -1
Agent 3.state = 0
Agent 1 has died
Agent 2.state = 0
Agent 2 has died
Agent 3 has died
all done

Stopping, Pausing and Resuming threads

Many of the built-in methods for stopping, suspending, and resuming threads are deprecated (no longer supported, eventually going away). We can implement our own stop, suspend and resume methods by introducing a run state:

enum AgentState {
  RUNNING, SUSPENDED, STOPPED, READY
}

Agent and Manager are declared here: Manager.java.

Manager extends Console.java.

Here's a session:

-> start
ok
-> status
Agent 1.state = 6
Agent 2.state = 7
Agent 3.state = 0
ok
-> status
Agent 1.state = 5
Agent 2.state = 6
Agent 3.state = 7
ok
-> status
Agent 1.state = 7
Agent 2.state = 0
Agent 3.state = 1
ok
-> suspend
ok
-> status
Agent 1.state = 2
Agent 2.state = 3
Agent 3.state = 4
ok
-> status
Agent 1.state = 2
Agent 2.state = 3
Agent 3.state = 4
ok
-> stop
ok
-> quit
bye

Notes

It doesn't look like anything special is going on. The user interface is waiting for my command. Meanwhile the three agents are running mod-8 counters in the background. This can be seen because we get different results when we ask for the agent status. However, the status is unchanged when the agents are suspended.

Lab 1

Create two subclasses of Agent: PiApproximator and PrimeGenerator.

PiApproximator maintains a crude approximation of pi. On each update, the approximation is improved by adding the next term in the infinite series:

pi = 4 – 4/3 + 4/5 – 4/7 + ...

Each improvement is displayed in the console window:

pi = 3.1415...

PrimeGenerator maintains a field called lastPrime, which is the last prime number it discovered and displayed. On each update it repeatedly increments lastPrime and tests it to see if it's prime:

lastPrime % i != 0 for 2 <= i <= lastPrime/2

Hint: assume lastPrime is prime and try to find a divisor. If one is found, then increment lastPrime and start over. Don't worry, there's always a next prime. (Do you know the proof?)

Here's a sxample output:

-> start
ok
-> next prime = 2
pi = 4.0
next prime = 3
pi = 2.666666666666667
next prime = 5
pi = 3.466666666666667
next prime = 7
pi = 2.8952380952380956
next prime = 11
pi = 3.3396825396825403
next prime = 13
pi = 2.9760461760461765
next prime = 17
pi = 3.2837384837384844
next prime = 19
pi = 3.017071817071818
next prime = 23
pi = 3.2523659347188767
next prime = 29
pi = 3.0418396189294032
snext prime = 31
pi = 3.232315809405594
next prime = 37
pi = 3.058402765927333
unext prime = 41
pi = 3.2184027659273333
next prime = 43
pi = 3.0702546177791854
next prime = 47
pi = 3.208185652261944
snext prime = 53
pi = 3.079153394197428
next prime = 59
pi = 3.200365515409549
pnext prime = 61
pi = 3.0860798011238346
next prime = 67
pi = 3.1941879092319425
enext prime = 71
pi = 3.09162380666784
nnext prime = 73
pi = 3.189184782277596
next prime = 79
pi = 3.0961615264636424
dnext prime = 83
pi = 3.1850504153525314
next prime = 89
pi = 3.099944032373808

next prime = 97
pi = 3.1815766854350325
ok

Lab 2

Create a generic agent class with state space = State and a generic Manager class. Redo lab 1 using this framework:

Thread States

Every thread has an associated state that changes throughout the thread's lifetime:

class Thread {
   public static final int CREATED = 0, READY = 1, RUNNING = 2, ... ;
   private int state = Thread.CREATED;
   // etc.
}

State transitions are caused by events such as interrupts, preemptions, and timeouts, or by explicit method invocations. Not all state transitions are possible. Here's a partial state diagram showing some of the states and the transitions between them:

The Master-Slave Design Pattern

Many multithreaded applications instantiate the Master-Slave Design Pattern:

Notes

·       The master manages a collection of active slave objects.

·       The master has the ability to start, stop, suspend or resume some or all of the slaves.

·       The master also provides services to the slaves. For this reason each slave has a pointer to the master.

·       One type of service is message passing—providing a mechanism for slaves to pass messages to each other.

·       The master might allow slaves to broadcast messages to all of the slaves.

·       Another type of service is discovery. A slave can ask the master to pair it with another slave.

·       The master might also provide a shared environment consisting of resources to be shared by the slaves.

·       In the example above the manager plays the role of master and the agents play the role of slaves.