Prev Next

Java Threads

Threads can be thought of as different strands of a program in execution. Each strand is a sequence of instructions to achieve a specific task. A thread scheduler, working at the behest of runtime system, provides the CPU for a quantum of time to each thread.

Why is multithreading relevant?

Multithreading enables better use of CPU time thereby achieving parallelism and bringing down the time taken for the program execution. When a thread is waiting for an I/O task to complete, it is simple idling without using the CPU. Another thread could very well use the CPU during this duration and progress on its task. The thread scheduler allocates CPU to each thread for a specified duration so that every thread can make progress in a simultaneous manner.

Java supports wide set of libraries to support multithreaded programming. Here we will address only the basics. For a more extensive coverage, please look into various resources on the web.

1. Creating Threads

To create a thread in Java, you have to define a class that extends Thread class or implements Runnable interface and implement the run() method. The run() method is the starting point of the thread (just as main() is the starting point of the program). When an instance of the class comes into existence, a new thread is created. This thread can be started by start method. The thread scheduler will then run the thread in near future.

As a first example, consider a program wherein both the main thread and the new thread iterates for 1000 times and prints the iteration count to the terminal.

    1. The NewThread.java extends Thread class. The run() method implements the loop mentioned.

    2. The Main.java implements main() which first creates NewThread instance, starts it and loops.

  // Main.java
  public class Main {
    public static void main(String[] args) {
      NewThread nt = new NewThread();
      nt.start();

      for (int i=0; i<1000; i++)
        System.out.println("main:" + i);
    }
  }

  // NewThread.java
  public class NewThread extends Thread {

    public void run() {
      for (int i=0; i<1000; i++)
        System.out.println("NewThread:" + i);
    }
  }

2. Alternate implementation

Alternately, the main thread (Race.java) can create two instances of thread (Racer.java) and exit. The thread instances race among each other and terminate. In order to distinguish between the output printed by each thread, an attribute can be introduced. Creating more threads is a matter of creating more instances of Racer. The implementation below:

  // Race.java
  public class Race {
    public static void main(String[] args) {
      System.out.println("Main thread started");

      Racer r1 = new Racer('A');
      r1.start();
      Racer r2 = new Racer('B');
      r2.start();

      // r1.join();
      // r2.join(); 

      System.out.println("Main thread ended");
   }
  }

  // Racer.java
  public class Racer extends Thread { // or implements Runnable
    private char id;

    public Racer(char id) {
      this.id = id;
    }

    public void run() {
      for (int i=0; i<1000; i++)
        System.out.println(id + ":" + i);
    }
  }

A few points to note below.

    1. The output of the threads are interspersed. This reveals that the control of the CPU indeed shifts between the threads.

    2. Each run of the program results in different interspersed output revealing that the scheduling of the threads is arbitrary.

    3. The execution also demonstrates the race condition, a charateristic of multithread programs, where each thread competes with the other to progress on their task.

    4. The main thread exits as soon as it starts the two racer threads since it does not have any more instructions to execute. This is evident from the printing of Main thread ended well ahead.

    5. In order to make the main thread wait till the racer threads complete, join() method of Thread class (or Runnable interface) can be used.

3. Interdependent threads and synchronization

In the above program, the two threads are independent. Also, the run() method does the trivial task of iteration count. In real scenarios, they have some form of interdependency. i.e. one thread cannot advance more than X number of steps in comparison to other. Threads are dependent on each other and make progress in a coordinated manner. Several issues arise if they don't coordinate well.

Race conditions in a multithreaded program can result in unpredictable behavior. Why?

Since threads are part of the same program, the objects in the heap are accessible to all the threads. Two or more threads can attempt to modify the same shared object in a simultaneous fashion. This can result in unexpected behavior or incorrect output. Note that the scheduling is arbitrary and not in the programmer's control, such errors can be hard to detect.

Consider the following program on updating the counter. The Incrementer thread increments the counter value by 1 while the Decrementer thread decrements the value by 1. There are four classes.

  1. Counter: Implements methods increment() and decrement().
  2. Incrementer: A thread that triggers incrementing by calling Counter's increment().
  3. Decrementer: A thread that triggers decrementing by calling Counter's decrement().
  4. Main: Creates an instance of Counter, Incrementer, Decrementer and starts them.
// Incrementer.java
public class Incrementer extends
                        Thread {
  private Counter counter;

  public Incrementer(Counter c) {
    counter = c;
  }

  public void run() {
    while (true)  // run forever
      counter.increment();
  }  
}  

// Decrementer.java
public class Decrementer extends 
                        Thread {
  private Counter counter;

  public Decrementer(Counter c) {
    counter = c;
  }
  
  public void run() {
    while (true)  // run forever
      counter.decrement();
  }  
}    

// Counter.java
public class Counter {
  private int val;

  public Counter() 
  {  val = 0;  }

  public void increment()  
  {  ++val; print();  }

  public void decrement()  
  {  --val; print();  }

  public void print() {
   System.out.print(val); 
  }  
}

// CounterTest.java
public class CounterTest {

  public static void main(String[] a) {

    System.out.println("Main started");

    Counter c = new Counter();
    Incrementer i = new Incrementer(c);
    Decrementer d = new Decrementer(c);

    i.start();
    d.start();

    System.out.println("Main ended");
  }
}

The safety issue that can arise is when both the Incrementer (Thread i) and Decrementer (Thread d) call Counter's increment & decrement methods and simultaneously modify val. The following sequence of operations can lead to incorrect result.

  1. Thread i invokes increment().
  2. Thread i reads val (say val = 10) and is about to increment.
  3. The scheduler gives the control to Thread d in the meanwhile.
  4. Thread d invokes decrement().
  5. Thread d reads the same val. (i.e. 10)
  6. Thread d decrements val from 10 to 9.
  7. Thread d calls print() which prints 9.
  8. The scheduler gives the control to Thread i.
    (Thread i missed the latest val which is 9 since it has already read val in step 2.)
  9. Thread i increments val from 10 to 11.
  10. Thread i calls print() which prints 11 (instead of the correct value 10).

This is not the only error that can happen. If Thread d does few more decrements before control shifts back to Thread i, then counter value will differ by more.

Solution: Mutual exclusion using synchronized construct

The solution is to enforce mutual exclusion of threads. When Thread i is incrementing, Thread d should not be allowed to decrement and vice-versa. Java's way of enforcing mutual exclusion is to mark the interfering methods increment() and decrement() as synchronized. This will ensure that whenever increment() method is active, decrement() cannot be active and vice-versa.

Essenstially, the synchronized keyword has the effect of locking the Counter object when a (synchronized) method is already active. So, even though control shifts from Thread i to Thread d with active increment(), Thread d cannot invoke decrement() but instead will go to wait state. The scheduler will have to give the control back to Thread i.

// Counter.java with synchronized methods
public class Counter {
  private int val;

  public Counter() 
  {  val = 0;  }

  public synchronized void increment()
  {  ++val; print();  }

  public synchronized void decrement()
  {  --val; print();  }

  public void print() {
    System.out.print(val); 
  }  
}

4. Other forms of synchronization

Mutual exclusion is a basic form of synchronization that ensures two or more threads don't interfere with each other while working on a shared data/object. However, tighter forms of synchronization may be necessary in many scenarios.

Consider the classical Producer-Consumer scenario where two threads namely, Producer and Consumer share a common buffer. The producer fills the buffer with data while the consumer grabs the data.

  • As the producer writes a piece of data into the buffer, the consumer has to read it before the producer writes the next piece. Otherwise the older piece of data is lost.
  • Similarly, if consumer reads a piece of data more than once in an immediate fashion, it will end up reading the stale data.

Note that we do not have control over the scheduler. Consider the implementation of the producer- consumer example below.

// Producer.java
public class Producer extends 
                        Thread {
  Buffer buf;

  public Producer(Buffer b) {
    buf = b;
  }

  public void run() {
    for (int i=0; i<100; i++)
      buf.write(i);
  }
}  

// Consumer.java
public class Consumer extends 
                        Thread {
  Buffer buf;

  public Consumer(Buffer b) {
    buf = b;
  }

  public void run() {
    for (int i=0; i<100; i++)
      buf.read();
  }
}  

// Buffer.java
public class Buffer {
  private int data;

  public synchronized void write(int i) 
  {
    data = i;
    System.out.println("P" + data);
  }

  public synchronized int read() 
  {
    System.out.println("C" + data);
    return data;
  }
}  

// Test.java
public class Test {
  Buffer b;
  Producer p;
  Consumer c;

  public static void main(
            String[] args) {
    b = new Buffer();
    p = new Producer(b);
    c = new Consumer(b);

    p.start();
    c.start();
  }
}

While the above implementation guarantees mutual exclusion of reading from and writing into the buffer, it does not guarantee write and read to happen in a strictly alternate fashion. Note that we no control over the thread scheduler. This is another problem of race condition.

Solution: Condition variables + wait & notify methods

To enable tight synchronization, Java provides special constructs - wait() and notify() methods. The wait() method can be invoked by a thread to voluntarily go into a waiting state thereby relinquishing the cpu and enabling the scheduler to handover the control to one of the other waiting threads. The notify() method can be invoked to notify the next thread in the queue (among all waiting threads).

Tight synchronization can be achieved by use of condition variables and wait/notify constructs. In the producer-consumer implementation below, we use a condition variable flag to know if buffer contains data or not.

  • flag is false indicates buffer is empty.
  • flag is true indicates buffer is not empty.
  • The producer sets flag to true as soon as it writes into the buffer.
  • The producer then notifies the scheduler.
  • The consumer reads from the buffer and sets the flag to false.
  • If the buffer is not empty (i.e. flag is true), producer has to wait till the consumer reads it.
  • If the buffer is empty (i.e. flag is false), consumer has to wait till producer writes into it.

The modified implementation of write and read methods of Buffer is given below.

// Improved Buffer.java that implements tight sychronization
public class Buffer {
  private int data;
  private boolean flag;

  public synchronized void write(int i) 
  {
    while (flag) { 
      try {  wait(); } 
      catch (InterruptedException ie) { }
    } 

    data = i;
    flag = true;  
    System.out.println("P" + data);
    notify();
  }

  public synchronized int read() 
  {
    while (!flag) { 
      try {  wait(); } 
      catch (InterruptedException ie) { }
    } 

    System.out.println("C" + data);
    flag = false;
    notify();
    return data;
  }
}

The above examples demonstrated the safety issues with respect ot multithreading and how they can be taken care in the code by use of synchronization construction. Multithreading can also introduce more issues relating to safety, liveness and fairness.

    Liveness: Cyclic dependency of resources among threads leading to a deadlock.

    Fairness: A thread does not get the CPU for long leading to starvation.

A final note

Java threads support specifiation of priority for each thread. Consequently, the scheduler gives more cpu time for threads with higher priority. The sleep() method can be used wait for certain duration (specified in milliseconds). This is in contrast to wait() method which waits on a condition. sleep() is often considered as a crude form of wait.

One can look at readers-writer's and dining philosophers implementation to get a better insight into multithreaded concepts and Java's librarires.