Title: Threads
Course: CPS 261: Advanced Java Concepts ~ DL & MM MASTER

Threads

Synchronization Issues

Having 2 independant threads running at the same time can cause a new set of problems. Problems begin to show up when 2 or more threads are accessing a datastructure and one thread updates the datastructure.

Consider the following example of a Bank class. We have 5 customers that have both a checking account and a savings account. Note the savings and checking arrays below which indicate how much money each customer starts out with.

Execute it and observe the following sequence of events:

1. The main routine (which is actually running in a Thread that we didn't start), starts up an audit Thread.
2. The audit Thread, sleeps for 5 seconds and then calls printTotals. The printTotals routine prints out the total amount of money the bank has in savings accounts, the total money in checking accounts and the grand total of all money (savings + checking).
3. The main routine (i.e. the original Thread) now makes the 2 calls:
ba.chk2save(2, 40);
ba.chk2save(3, 50);
4. Each call to chk2save(customer_index, amount_money) , moves the amount of money specified from the checking account to the saving account for customer index. Each call to chk2save, first adds the money to the savings account and then removes it from the checking account.
5. Suppose that our audit thread happens to get scheduled while the main Thread is in the middle of a chk2save call. Suppose the the chk2save call has added money to savings but hasn't removed the money from checking. Our audit will show that our bank has more total money than it really has. This is because savings has been increased, but checking hasn't been reduced.
6. The problem is that there is a region of code in chk2save where we hope we don't get interrupted. Sometimes regions of code like this are referred to as critical regions.
7. Normally the chances of this happening would be very small, because our Main Thread would need to lose the CPU in a bad spot and the audit thread would need execute during that time. I have added a sleep call in chk2save to make the window of vulnerability extremely large.
8. Small windows of opportunity are deadly, because you may have a large system that passed your quality assurance testing and you never hit the small window of vulnerability. Unfortunately, when the system went to production and thousands of customers started hitting your system, you hit the vulnerable window. So every so often your system does wierd things and the head of your company finds out about it and you are told that your job is on the line to solve this problem. Sound familiar.

Bank.java


import java.util.*;

class Bank implements Runnable
{
    int savings[] = {100, 200, 300, 400, 500};
    int checking[] = {100, 200, 300, 400, 500};
    boolean stopFlag = false;

// To fix the synchronization problem, you can change
//  the following to
//  synchronized void chk2save(int index, int amount)
    void chk2save(int index, int amount)
    {
        System.out.println("-----Starting chk2save: " +index + "," +amount);
        if (index >= 0 && index < savings.length)
        {
            if (amount <= checking[index])
            {
              // Begin Vulnerable region
                savings[index] += amount;
                // The following sleep, makes our
                // vulnerable window huge
                try
                 {
                    Thread.sleep(6000);
                 }
                catch (InterruptedException e){}

                checking[index] -= amount;
              // End Vulnerable region
            }
        }
        System.out.println("-----Ending chk2save");
    }

// To fix the synchronization problem, you can change
//  the following to
//  synchronized void printTotals()
    void printTotals()
    {
        int totalSavings=0, totalChecking=0;

        System.out.println(); // blank line
        System.out.println("*********************************");
        for (int i=0; i < savings.length; i++)
            totalSavings += savings[i];
        System.out.println("Total Savings = " + totalSavings);

        for (int i=0; i < checking.length; i++)
            totalChecking += checking[i];
        System.out.println("Total Checking = " + totalChecking);
        System.out.println("*******Grand Total = " +
                (totalSavings + totalChecking));
        System.out.println(); // blank line

    }

    public void run()
    {
        for (;;)
        {
            printTotals();
            try
            {
                Thread.sleep(5000);
            }
            catch (InterruptedException e)
	    {
	        System.out.println("InterruptedException occurred in auditor");
	    }
            if (stopFlag) break;
        }
    }
    void delay(int num_seconds)
    {
        try {
		Thread.sleep(1000 * num_seconds);
            }
        catch (InterruptedException e){}
    }
    public static void main(String[] args)
    {
        String str="";
        Bank ba = new Bank();

        Thread audit = new Thread(ba);
        audit.start();

        ba.delay(6);      // delay for 6 seconds
        ba.chk2save(2, 40);

        ba.delay(6);      // delay for 6 seconds
        ba.chk2save(3, 50);

        ba.delay(25);     //delay for 25 seconds

        ba.stopFlag = true;
        audit.interrupt();
        System.out.println("BYE");
    }

}


Fixing Synchronization Problems

Java provides an extremely simple solution. I have solved these problems in other languages, and the Java solution is very nice and clean relative to approaches in older languages.

The keyword synchronized provides the solution. First of all we need to add the keyword synchronized to the printTotals routine like so:

synchronized void printTotals()

We also need to synchronize chk2save. You can synchronize a complete method or you can just synchronize a block of code inside of a method. So for example, here are 2 possible replacements for our chk2save routine.

Fix the original Bank.java program with either of the following solutions and rerun the Bank program.

synchronized on the whole method:



    synchronized void chk2save(int index, int amount)
    {
        System.out.println("Doing chk2save: " +index + "," +amount);
        if (index >= 0 && index < savings.length)
        {
            if (amount <= checking[index])
            {
                savings[index] += amount;
                try
                 {
                    Thread.sleep(6000);
                 }
                catch (InterruptedException e){}

                checking[index] -= amount;
            }
        }
    }


synchronized on a block of code inside of a method:



    void chk2save(int index, int amount)
    {
        System.out.println("Doing chk2save: " +index + "," +amount);
        if (index >= 0 && index < savings.length)
        {
            if (amount <= checking[index])
            {
	      synchronized(this)
	      {
                savings[index] += amount;
                try
                 {
                    Thread.sleep(6000);
                 }
                catch (InterruptedException e){}

                checking[index] -= amount;
              }
            }
        }
    }


A synchronized block of code or a synchronized method works as follows:

1. Only one thread can be in any synchronized section of an object instance at any one time. If one or more other threads want to execute a synchronized section of code, the Java Run Time system will Queue up the other threads until the first thread exits the synchronized section. Once the first thread exits, the Java Run Time system will schedule the next thread waiting to execute the synchronized section.
2. Note that synchronization occurs on an object instance. In otherwords, if I have 2 instances of some object, each object can have a thread in its critical section. We will try to demonstrate this later.
3. You can imagine that each object has a lock. In order for a Thread to execute a synchronized region of a class, the Thread must obtain the lock. When the Thread exits the synchronized section the lock is returned.
4. If your Class has more than one synchronized section or method, then the lock applies to the whole object. This means that only one of your synchronized regions can be executing an any point in time.
5. Consider the following snippet of code. If one thread is in the middle of
aThing.put(int);
Then a second thread will be suspended if it tries to execute:
value = aThing.get();
However, the second thread could execute the following with no suspension:
value = anotherThing.get();
Also note that aThing.do_something() is allowed at all times because this method is not synchronized


class Something
{
  synchronized int get()
  { // some code
    another_synchronized_method();
  }
  synchronized void put(int)
  { // some code
  }
  synchronized void another_synchronized_method()
  {
     // some code
  }
  void do_something()
  { // some code
  }
}


Something aThing = new Something();
Something anotherThing = new Something();



6. Note that once a Thread has obtained the object lock, the Thread can call any number of other synchronized methods. In the above example, the get method is synchronized and it calls another synchronized method called another_synchronized_method. No problem with this.

Deadlocks

It is possible to have 2 threads that are deadlocked(i.e. neither thread can make progress and both threads will wait forever) because of a poorly designed set of synchronized methods.

1. In the News.java example below, we have a Sports class instance and a Business class instance that contain synchronized methods. We can have 2 threads that want to use both classes. The sequence of events are as follows:
  - The First Thread obtains the lock for the Business object
  - The Second Thread obtains the lock for the Sports object
  - The First Thread tries to obtain the lock for the Sports object, but needs to be suspended until the Second Thread releases the Sports object lock.
  - The Second Thread tries to obtain the lock for the Business object, but needs to be suspended until the First Thread releases the Business object lock.
2. This program can never complete as it is currently written. The problem is that each thread needs execute critical regions in 2 different synchronized objects (Sports and Business).
3. One way to fix this problem (assuming this meets with the design criterea for the News.java program), is to remove the synchronized keyword from either of (or both of) the methods:
getBusiness_Sports
getSports_Business
4. A second way to fix this problem is to require that the 2 synchronized objects must be accessed in a specific order. For example, if you rewrite this application so that Sports is always accessed before Business, then no deadlock can occur. Hopefully, I will remember to give you my 2 pen illustration of this problem.

News.java


// This example creates a deadlock

class Sports
{
    synchronized String getSports(int id)
    {
       System.out.println (id + " entered getSports");

      // pretend like we get this info from the internet
      // and it takes a little while (5 secs)
       try
       {
            Thread.sleep(5000);
       }
       catch (InterruptedException e){}

       System.out.println (id + " exitted getSports");
       return " Sports Headline ";
    }
    synchronized String getSports_Business (int id,Business b)
    {
        String retval;
        System.out.println (id + " entered getSports_Business");
        retval = getSports(id) ;

        System.out.println(id + " Deadlock Occurs on the next call");

        // Here we own the Sports lock and we will try to acquire the
        // Business Lock

        retval += b.getBusiness(id);
        // Never execute the following statement
        System.out.println(id + " Deadlock didn't happen");
        return retval;
    }
}

class Business
{
    synchronized String getBusiness(int id)
    {
      System.out.println (id + " entered getBusiness");
      // pretend like we get this info from the internet
      // and it takes a little while (5 secs)
       try
       {
            Thread.sleep(5000);
       }
       catch (InterruptedException e){}
       System.out.println (id + " exitted getBusiness");
       return " Business Headline ";
    }
    synchronized String getBusiness_Sports (int id, Sports s)
    {
      String retval;
      System.out.println (id + " entered getBusiness_Sports");
      retval = getBusiness(id) ;

      System.out.println(id + " Deadlock Occurs on the next call");

      // Here we own the Business lock and we will try to acquire the
      // Sports Lock

      retval += s.getSports(id);
      // Never execute the following statement
      System.out.println(id + " Deadlock didn't happen");

      return retval;
    }
}

class News implements Runnable
{
    Business b = new Business();
    Sports s = new Sports();
    Thread t1,t2;
    static int id_number = 1;

    public void run()
    {
        int id = id_number++;
        String str;
        if (id == 1)
        {
            str = b.getBusiness_Sports(id, s);
            System.out.println(id + " finished with " + str);
        }
        else
        {
            str = s.getSports_Business(id, b);
            System.out.println(id + " finished with " + str);
        }
    }
    void doit()
    {
        t1 = new Thread(this);
        t2 = new Thread (this);
        t1.start();
        t2.start();

    }
    public static void main(String[] args)
    {
        News news = new News();
        news.doit();
    }

}


BusyLoop

Image that you have a bucket of water, and you have one Thread who has the job of filling the bucket when it is empty (call this Thread the Producer). You have another Thread who has the job of emptying the bucket of water(call this Thread the Consumer). Pretend like we are fighting fires in the old days.

1. We create a Bucket class and provide a put method for filling the bucket. We provide a get routine for emptying the bucket. A put call can only succeed if the bucket is empty, and a get call can only succeed when the bucket is full.
2. To avoid conflicts, we synchronize the get and put methods. The code shows up below.
3. The code works, but there is a very inefficient thing happening. The Consumer needs to make a lot of unproductive calls to the get method, because get returns a fail boolean when the bucket is empty.
4. There must be a better way ----> Move on to the next example.


class Bucket {
    private int contents;
    private boolean BucketEmpty = true;

    public synchronized boolean get(int consumerNumber) {
        if (!BucketEmpty)
        {
            System.out.println("Consumer " + consumerNumber +
                " Emptying Bucket " + contents);
            BucketEmpty = true;
            return true; // successful
        }
        return false; // unsuccessful
    }

    public synchronized boolean put(int value) {
        if(BucketEmpty)
        {
            System.out.println("Filling Bucket " + value);
            contents = value;
            BucketEmpty = false;
            return true; // successful
        }
        return false; // unsuccessful
    }
}
// ******************************************************
class Producer extends Thread {
    private Bucket bucket;
    private int number;

    public Producer(Bucket c, int number) {
        bucket = c;
        this.number = number;
    }

    public void run() {
        int numSuccess = 0;
        int numTries = 0;
        int fillValue;

        do
        {
            try {
                sleep((int)(Math.random() * 2000));
            } catch (InterruptedException e) { }

            fillValue = numSuccess + number*100;
            if (bucket.put(fillValue)) numSuccess += 1;
            numTries += 1;
         } while (numSuccess < 10);
        System.out.println(number + "****Terminating Producer " +
            numTries + " numTries");
    }
}

//********************************************************
class Consumer extends Thread {
    private Bucket bucket;
    private int number;

    public Consumer(Bucket c, int number) {
        bucket = c;
        this.number = number;
    }

    public void run() {
        int numSuccess = 0;
        int numTries = 0;
        do
        {
            try {
                   sleep((int)(Math.random() * 20));
                 } catch (InterruptedException e) { }

            if (bucket.get(number)) numSuccess += 1;
            numTries += 1;
        } while (numSuccess < 10);

        System.out.println(number + "****Terminating Consumer " +
            numTries + " numTries");
    }
}

//**********************************************************

public class BusyLoop {
    public static void main(String[] args) {
        Bucket bucket = new Bucket();
        Producer p1 = new Producer(bucket,1);
        Consumer c1 = new Consumer(bucket,1);

        c1.start();
        p1.start();
        System.out.println("BusyLoop main will exit now");
    }
}



Solution to the Busy Loop

Java provides a very elegant solution to the above problem. The object class has 3 key methods that are available to any Java class:

- wait - The effect of this call is to put the calling thread on a queue of waiting threads. Once this thread is on the queue, the object lock becomes available and other threads can enter a synchronized function. The thread that calls wait is removed from the waiting queue, when some other thread calls either notify or notifyall. The wait call has a timeout feature that allows the thread to also exit the queue because a certain amount of time has elapsed.
wait(number_of_milliseconds);
- notify -The effect of this call is to remove one of the threads on the suspension queue and to have it rescheduled to return from it's wait call.
- notifyall - The effect of this call is to schedule all of the threads on the suspension queue.
- To call these 3 routines, you must be executing inside of a synchronized section for the object instance of interest (i.e. Bucket class instance in the above example)
- Take a look at the online help for the Object class to see these methods. You will see that certain exceptions can be thrown for these 3 methods if you don't follow the rules. Most of these exceptions are derived from RuntimeException which means the compiler doesn't force you to catch them. However, the wait method can throw an InterruptedException and this exception is not a RuntimeException so you have deal with it.

WaitNotify.java


class Bucket {
    private int contents;
    private boolean BucketEmpty = true;

    public synchronized int get(int consumerNumber) {
        while (BucketEmpty) {
            try {
                wait();
            } catch (InterruptedException e) { }
        }
        System.out.println("Consumer " + consumerNumber +
                " Emptying Bucket " + contents);
        BucketEmpty = true;
        notify(); // Wake up any Producer waiting for an empty bucket
        return contents;
    }

    public synchronized void put(int value) {
        while (!BucketEmpty) {
            try {
                wait();
            } catch (InterruptedException e) { }
        }
        System.out.println("Filling Bucket " + value);
        contents = value;
        BucketEmpty = false;
        notify(); // Wake up any Consumer waiting for a full bucket
    }
}
// ******************************************************
class Producer extends Thread {
    private Bucket bucket;
    private int number;

    public Producer(Bucket c, int number) {
        bucket = c;
        this.number = number;
    }

    public void run() {
        int fillValue;
        for (int i = 0; i < 10; i++) {
            try {
                sleep((int)(Math.random() * 2000));
            } catch (InterruptedException e) { }

            fillValue = i + number*100;
            bucket.put(fillValue);
        }
        System.out.println("****Terminating Producer " + number);
    }
}

//********************************************************
class Consumer extends Thread {
    private Bucket bucket;
    private int number;

    public Consumer(Bucket c, int number) {
        bucket = c;
        this.number = number;
    }

    public void run() {
        int value = 0;
        for (int i=0; i < 10; i++) {
            value = bucket.get(number);
        }
        System.out.println("****Terminating Consumer " + number);
    }
}

//**********************************************************

public class WaitNotify {
    public static void main(String[] args) {
        Bucket bucket = new Bucket();
        Producer p1 = new Producer(bucket,1);
        Consumer c1 = new Consumer(bucket,1);

        c1.start();
        p1.start();
        System.out.println("WaitNotify will exit now");
    }
}




Getting more parallel activity.

If you want to double your fire fighting capability, add the lines of code shown below:


 Bucket bucket2 = new Bucket();
 Producer p2 = new Producer(bucket2,2);
 Consumer c2 = new Consumer(bucket2,2);
 c2.start();
 p2.start();


Note that I can have consumer c2 inside of the get method of bucket2 at the same time as consumer c1 is inside of the get method of bucket1. Remember synchronization only prevents 2 threads inside of a synchronized method of the same object .

Fire Fighting Becomes popular

Suppose that a lot of people want to get involved in the Fire Fighting activity, but we don't have a chance to go and buy any more Buckets from Sears.

1. We can now have M Producers and N Consumers. In the previous example, producing and consuming was very balanced. So when a producer or a consumer accessed the bucket successfully 10 times, it voluntarily exitted. For example, you can go with 4 Producers and 5 Consumers with the following call:
java WaitNotify2 4 5
2. Now we would like the main routine to detect when the producers are done ( they still finish after 10 successful bucket accesses). When the producers are done, we would like to have the main routine tell the consumers to quit.
3. Our main routine periodically looks at each Producer thread and calls the Thread method isAlive() to determine if the Thread is still around.
4. Once all producers have terminated, the main routine calls a new method in the bucket class called stop. The stop method sets a flag and calls notifyAll(). Since it is possible to have multiple Consumers who are waiting, we use the notifyAll routine to schedule all of them. Each Consumer will wake up and sense the flag which will result in terminating the Thread.
5. Note that notify reschedules the next Thread in a waiting queue. The notifyAll routine reschedules ALL Threads in the waiting queue.

WaitNotify2.java


class Bucket {
    private int contents;
    private boolean BucketEmpty = true;
    boolean timeToStop = false;

    public synchronized int get(int consumerNumber) {
        while (BucketEmpty) {
            try {
                wait();
            } catch (InterruptedException e) { }
            if (timeToStop) return -1;
        }
        System.out.println("Consumer " + consumerNumber +
                " Emptying Bucket " + contents);
        BucketEmpty = true;
        notify();  // Need to wake up interested producer
                      // Note this could wake up other consumers
        return contents;
    }

    public synchronized void put(int value) {
        while (!BucketEmpty) {
            try {
                wait();
            } catch (InterruptedException e) { }
        }
        System.out.println("Filling Bucket " + value);
        contents = value;
        BucketEmpty = false;
        notify(); // Wake up interested consumers
                  // Note this could wake up other producers
    }
    public synchronized void stop()
    {
        timeToStop = true;
        notifyAll();
    }
}
// ******************************************************
class Producer extends Thread {
    private Bucket bucket;
    private int number;

    public Producer(Bucket c, int number) {
        bucket = c;
        this.number = number;
    }

    public void run() {
        int fillValue;
        for (int i = 0; i < 10; i++) {
            try {
                sleep((int)(Math.random() * 2000));
            } catch (InterruptedException e) { }

            fillValue = i + number*100;
            bucket.put(fillValue);
        }
        System.out.println("****Terminating Producer " + number);
    }
}

//********************************************************
class Consumer extends Thread {
    private Bucket bucket;
    private int number;

    public Consumer(Bucket c, int number) {
        bucket = c;
        this.number = number;
    }

    public void run() {
        int value = 0;
        for (; ;) {
            value = bucket.get(number);
            if (value < 0) break; // Time to exit
        }
        System.out.println("****Terminating Consumer " + number);
    }
}

//**********************************************************

public class WaitNotify2 {
    public static void main(String[] args) {
        Bucket bucket = new Bucket();
        int numProducers = 1;
        int numConsumers = 1;
        Producer p[];
        Consumer c[];

        if (args.length > 0)
            numProducers = Integer.parseInt(args[0]);
        if (args.length > 1)
            numConsumers = Integer.parseInt(args[1]);

        p = new Producer[numProducers];
        c = new Consumer[numConsumers];
        for (int i = 0; i < numConsumers; i++)
        {
           c[i] = new Consumer(bucket, i+1);
           c[i].start();
        }
        for (int i = 0; i < numProducers; i++)
        {
           p[i] = new Producer(bucket, i+1);
           p[i].start();
        }

  // Monitor Status of Producers.
  // When the producers go away, get rid of the
  // Consumer.

  outer:for (;;)
        {
            try
            {
                Thread.sleep(1000);
            }
            catch (InterruptedException e) {}

            for (int i= 0; i < numProducers; i++)
            {
               if (p[i].isAlive()) continue outer;
            }
            System.out.println("Stopping Consumers");
            bucket.stop();
            break;
         }
    }
}




One Last Approach

Suppose that you want to change the above program so that the producers execute indefinitely. You want the main task to wait on a user input from the keyboard ("quit" command). When the quit command occurs, you want the main task to cleanly terminate everything. See if you can come with a solution. HINT: check out the interrupt() method in the Thread class.

Dining Philosopher Problem

One of the classic problems that Academic people use to describe problems that you encounter in Operating Systems is the Dining Philosopher's problem. The image below describes the situation.

Philosophers think for a random amount of time. It doesn't require any special resources to think. Then a Philosopher needs to eat for a random amount of time. Unfortunately it takes 2 forks for a Philosopher to eat.

This means that Philosophers must have some algorithm to avoid starvation. For example, if each philosopher grabbed the fork to his left and then held onto it until he acquired the fork on his right, we would end up with a pile of dead starved philospher bodies.

If you run the solution below, you will see smiley faces for each philosopher who is eating. The code below has a table with 15 philosophers.

The algorithm used is to try to acquire the right fork. If this fails, wait for the right fork. If the right fork is acquired, we then try to acquire the left fork. If this succeeds, we go and eat. If it fails, it is very important that we put the right fork back on the table.

DiningPhilo.java


//Fork class with synchronized methods
class Fork{
    private int whichFork;
    private boolean available = true;

    Fork(int num)
    {
       whichFork = num;
    }
    public synchronized boolean get() {
        if (available)
        {
           available = false;
           return true;
        }
        return false;
    }
    public synchronized void put() {
        available = true;
        notifyAll();
    }
    public synchronized void waitForFork()
    {
       try
       {
           wait();
       }
       catch (InterruptedException e) { }
    }
}
// ******************************************************
// Class to represent the table containing the N Forks
class Table{
   // Array of Fork classes
   Fork[]  theForks;
   int maxForks;
   Table(int num)
   {
       maxForks = num;
       theForks = new Fork[num];
       for (int i=0; i < num; i++)
           theForks[i] = new Fork(i);
   }
   public void getForks(int rightFork){
       int leftFork = rightFork+1;
       if (leftFork >= maxForks) leftFork = 0;

       for ( ;;){ // We starve without forks.
           if (!theForks[rightFork].get() ) // Try to get the right fork
               {
                   // Failed to get fork --  Wait for right fork
                   theForks[rightFork].waitForFork();
                   continue;
               }
           if (!theForks[leftFork].get() ) // Try to get the left fork
               {
                   // Failed to get the left fork
                   theForks[rightFork].put(); // Return the right fork
                   // Wait for left fork
                   theForks[leftFork].waitForFork();
                   continue;
               }
           return;
       }


   }
   public void putForks(int rightFork){
       int leftFork = rightFork+1;
       if (leftFork >= maxForks) leftFork = 0;

       theForks[leftFork].put(); // Put down the left fork.
       theForks[rightFork].put(); // Put down the right fork.
   }
}
// ********************************************************
// Class that creates the displayable  output.  Eating philosophers
// show up with a smiley face, thinking philosophers are blank
class Display{
    private int number;
    boolean[] eating;
    Display(int n){
        number = n;
        eating = new boolean [n];
        for (int i=0; i < eating.length; i++)
            eating[i] = false;
    }
    synchronized void terminate(String msg)
    {
        System.out.println(msg);
    }
    synchronized void update(int philo, boolean eat_flag)
    {
        eating[philo] = eat_flag;
        System.out.println("------------------------------------------------------");
        for (int i=0; i < number; i++)
            if (i < 10)
                System.out.print(i + "    ");
             else
                System.out.print(i + "   ");
        System.out.println();
        for (int i=0; i < number; i++)
            if (eating[i])
                System.out.print(":-)  ");
            else
                System.out.print("     ");
        System.out.println();
    }
}

// ********************************************************
// Dining Philosopher Thread
class Philo extends Thread {
    private Table theTable;
    private Display theDisplay;
    private int number;
    private boolean keepRunning = true;

    public Philo(Display display, Table table, int number) {
        theTable = table;
        theDisplay = display;
        this.number = number;
    }
    public void stopRunning()
    {
       keepRunning = false;
       this.interrupt();
    }

    public void run() {
       int nSleep;

        for (; keepRunning; )
          {

           // Enter Thinking mode
            try {
                nSleep = (int)(Math.random()*3000);
                sleep(nSleep);
                } catch (InterruptedException e) { }
            if (!keepRunning)
               break;

            // Enter Eating mode
             try {
                   theTable.getForks(number);
                   if (keepRunning)
                   {
                        theDisplay.update(number, true); // we are now eating
                        nSleep = (int)(Math.random()*8000);
                        sleep(nSleep);
                    }
                 } catch (InterruptedException e) { }

             theDisplay.update(number, false); // we are about to start thinking
             theTable.putForks(number);
             if (!keepRunning)
               break;
           }// End of for loop for Philosopher

             theDisplay.terminate("Philosopher Exiting: "+number);

    }
}


//**********************************************************
 public class DiningPhilo {
    private final static int NUM_PHILOS = 15;
 public static void main(String[] args) {

    Table theTable= new Table(NUM_PHILOS);
    Philo[] thePhilos = new Philo[NUM_PHILOS];
    Display display = new Display(NUM_PHILOS);

       for (int i = 0; i < NUM_PHILOS; i++)
       {
           thePhilos[i] = new Philo(display, theTable, i);
           thePhilos[i].start();
       }

       try{ Thread.sleep(20000); }
       catch(InterruptedException e){}

       System.out.println("After 20 Seconds, we Terminate");
       for (int i=0; i < NUM_PHILOS; i++)
          thePhilos[i].stopRunning();

    }//End of main
}






A few points that didn't show up in the examples above:

Thread Thread.currentThread() - this static method is sometimes useful. It returns a pointer to the Thread that is currently executing.

boolean isInterrupted() - this method returns true if this thread has been interrupted.

One final point is that wait, notify and notifyAll must always be called in a synchronized section of code. They must also be called inside of method of the relavent object instance. Failing to follow these rules will result in an exception.

Some Extra Examples --

These multi-threaded programs use GUI interfaces so we won't look at them very carefully now. But it is fun to look at the outputs.

Exercises

1. Create an application which writes to the screen what the user types. If the user doesn't type anything on 10 seconds, a message should show up on the screen saying:
Nothing received in the last 10 seconds

Hint: You need another thread in addition to the main thread. One of the threads will just read MyInput to collect user input. You will need a synchronizing class (can be done in many ways). The other thread will be waiting inside of a method in the synchronizing class (note that wait can have a timeout). This thread will wake up under either a timeout condition or because a message was sent to it to publish. The MyInput reading thread will call a method in the synchronizing class to set the message to be written.
2. Create a writer thread that contains synchronized methods postMessage, getMessage. The writer thread calls getMessage and writes the acquired messages to some logging file. Create several (5) reader threads that periodically send messages to the writer thread. Create a Mother thread that starts the whole thing going. The Mother thread creates the writer thread and the reader threads. The Mother thread will periodically check to see if the reader threads are alive and when they are all dead, it will tell the writer thread to terminate. In our first version of the writer task, we will only hang onto one String to be written. In an upgraded version, we will keep a linked list of Strings to be written. Discuss issues on why a circular queue might be desireable here.
3. Create a Copy program that uses 2 threads. One thread for reading the input file and a second thread for writing out the data. For a datastructure, create a circular queue using an array. Provide get and put methods for your circular queue. Each entry in the circular queue has a buffer and a number of bytes. Provide a synchronized get and put method to your circular queue.
4. Take the previous problem one step further. Create 3 threads. The first thread reads buffers into a circular que. The second thread pulls buffers out of the circular queue and upper cases the characters. The output is placed into a second circular queue. The third thread pulls buffers out of the second queue and writes out the data to a file. If you are looking for a lot text, copy from the Java Certification link.
Solution (don't peek until you have thought about this for a while)
5. Suppose you are writing software to process ATM transactions from multiple ATM threads. After each Transaction, the transaction needs to be written back to a single Audit file back at the Bank's head quarters. Simulate this job with a thread to write out the Audit File. Provide multiple ATM threads which send transaction messages to the Audit File Thread. Simulate an ATM thread by having each thread open up a "Canned" Transaction file which is read after random delays.
6. Create 5 threads that wait to be notified. The main thread takes commands like:
wakeup 3
wakeup 1

The main thread should wakeup the specified thread. Solve this by having an array of synchronization objects (one for each of the 5 threads). Each of the 5 threads can wait on its own unique object. The main thread can notify just the one specified by the command.
7. Solve the previous problem with one synchronization object. In this case, you will need to have all 5 threads waiting on the same object, and each thread will have to check if he is the "one" that should be scheduled.
8. Go back to the Collections class in the List-Collections link to discover how to create a synchronized ArrayList. Create 5 threads which put messages in this synchronized list at random times. After each thread has put out 5 messages, dump out the Synchronized ArrayList.
9. Rewrite the Dining Philosopher program to get rid of the Fork Class. Instead, make the Table class have synchronized functions for getForks and putForks. The forks can be managed as an array of available boolean flags. In this scheme, putting the forks down causes a notifyAll to occur on the Table object for all Philosophers needing forks.
10. Modify the WaitNotify.java program to be more general. Instead of one Bucket, make a BucketArr class that contains an array of 4 buckets. Your BucketArr class should have 2 indexes. A get index which indicates the next bucket entry to be fetched by the Consumer and a put index which indicates the next bucket entry to be filled. The Consumer should be modified to Sleep for some random amount of time between each consumption. The Producer must wait when the Queue is full. The Consumer must wait when the Queue is empty. Run your program with 5 producers and 5 consumers. HINT: consider the following sketched out code ---
HINT2: You might find it necessary to do a notifyAll if you can't have the Consumers waiting on a different object than the Producers---- This requires some thought.

class BucketArr
{
    int get_index = 0;
    int put_index = 0;
    int count = 0;
    final int max_size = 4;
    int [] bucket_contents = new int[max_size];

    // We store a max of 4 bucket contents in an array with 4 entries
    // get_index and put_index take on values 0,1,2,3,0,1,2,3,0, etc.
    // You can use an expression:
    // next_get = (get_index +1) % max_size; // gives the next position available
    // count == 0; // empty condition
    // count == max_size; // full condition


    synchronized int get()
    {
        int value;

        while (count == 0)
        {
            // Fill in the details here
        }

        // You may have to add a few more
        // details here.


        value = bucket_contents[get_index];
        get_index = (get_index + 1) % max_size;
        count -= 1;
        return value;

    }

    synchronized void put(int value)
    {

        while (count == max_size)
        {
            // full condition
            // fill in details here
        }

        // You may need to fill in some
        // details here
        bucket_contents[put_index] = value;
        put_index = (put_index +1) % 4;
        count += 1;

    }

}


Scheduling Games

The techniques in the following example are rarely used, but this example is designed to give you some idea about Thread scheduling.

1. This program implements a race. You can have a fair race or an unfair race (the default is unfair). In the unfair race we give each Racing Thread a different priority.
java Racing fair
or
java Racing unfair
The results of this program will be platform dependent, because we are in effect testing the scheduling characteristics of the Java Runtime system. When I ran this in class, the priorities (unfair race) seemed to have a much larger impact on Windows than on Linux.
2. We will create threads using both techniques described above. We will have a Racer class which is derived from Thread. Our main class is called Racing and it implements the Runnable interface. We will create 5 Threads based on the Racer class. We will also create one thread based on the Racing class. The Racing class will monitor the progress of each of the Racer threads an print out status updates indicating how much CPU time has been burned up by each Racer thread.
3. Normally, most threads encounter natural suspensions when they wait for input from I/O (i.e. keyboard, files, or for some event to occur).
4. In the following example, we are creating a Thread called Racer which burns up CPU time. The Racer thread will Hog as much CPU time. There is a yield_flag parameter passed to the Racer thread. If the yield_flag is set, then the Racer Thread will be a "good citizen" and volountarily give up the CPU after 500 iterations. This allows other Threads (probably another Racer Thread) to execute. Giving up the CPU is done by calling:
yield();
The yielding Thread can be rescheduled immediately if no one else wants the use the CPU. If other Threads want the CPU, then the yielding thread will sit in a Scheduler Queue waiting for another turn to use the CPU.
5. To turn on the yield flag, you need to have a second parameter that contains the value yield. The default is for the Racer to do no yielding. Here are some of your options:
java Racing fair yield
or
java Racing unfair noyield
or
java Racing fair noyield
or
java Racing unfair yield
6. To create an unfair race, we play games with Thread priorities. I would recommend that normally you don't mess with priorities. However, in this example we are exploring Thread Scheduling possibilities. When a thread is created, it is possible to change its priority with the Thread method:
setPriority(priority);
The priority possibilities is 1,2, ... 10. You can also use Thread.MIN_PRIORITY which is 1, Thread.MAX_PRIORITY which is 10, or Thread.NORM_PRIORITY which is 5.

Racing.java


class Racer extends Thread
{
    static long bigNumber = 999999999999999L;
    boolean yield_flag = false;
    long current_count = 0;
    Racer(boolean y){
        yield_flag = y;
    }
    public void run(){

        for (; current_count < bigNumber; current_count++)
        {
            double x;
            // if yield_flag is on, call yield every 500 iterations
            if (yield_flag && (current_count % 500) == 0)
                yield();
            x = Math.sqrt( Math.tan(13.9)); // burn up some time
        }
    }
}
class Racing implements Runnable
{
    int numRunners =5;
    Racer[] runners = new Racer[numRunners];

   // Just print out on the screen the amount of work done
   // by each Thread
    void screenUpdate()
    {
        long maxLoop=0;
	// Find the leader total.
        for(int i=0; i < numRunners; i++)
            if (runners[i].current_count > maxLoop)
                maxLoop = runners[i].current_count;
        System.out.println("------------------------------------");
        if (maxLoop == 0) return; // race not started yet

      // The leader always gets 40 stars
      // Other racers get an appropriate number of stars
      // to indicate how they compare with the leader.
        for (int i=0; i < numRunners; i++)
        {
            long curr = runners[i].current_count;
            long numStars = (curr * 40)/ maxLoop;
            for (long j=0; j < numStars; j++)
                System.out.print("*");
            System.out.println("  " + curr);
        }

    }
    public void run(){
        for (;;)
        {
            try {Thread.sleep(2000);}
            catch (InterruptedException e){}
            screenUpdate();
        }
    }

    void doit(boolean fair, boolean yield)
    {
        Thread display;

        System.out.println("fair: " + fair + "  yield: " + yield);

        // Create Threads with desired Priorities
        for(int i=0; i < numRunners; i++)
        {
           int priority = Thread.MIN_PRIORITY;
           if (!fair) priority += i;
           // Don't ever want to use a priority > MAX_PRIORITY
           priority = Math.min(Thread.MAX_PRIORITY, priority);
           runners[i] = new Racer(yield);
           runners[i].setPriority(priority);
        }
        // Use the fact that the Racing class implements
        // the Runnable Interface
        display = new Thread(this);
        display.setPriority(Thread.MAX_PRIORITY);
        display.start();

        // Start the Race
        for(int i=0; i < numRunners; i++)
           runners[i].start();
    }

    public static void main(String[] args)
    {
        boolean fair=false;
        boolean yield = false;
        Racing racing = new Racing();

        System.out.println("Useage: Racing [fair] [yield]");

        if (args.length > 0 && "fair".equals(args[0]))
            fair = true;
        if (args.length > 1 && "yield".equals(args[1]))
            yield = true;

        racing.doit(fair, yield);
        System.out.println("main is done");
     }

}


PizzaStore.java

So you decide to get into the Pizza business. This example doesn't really use any new concepts, but it provides a more meaningful example. To implement this we take the following steps:

1. We define a Pizza class for each order, and we create a PizzaStore class that contains a LinkedList of Pizza Orders.
2. We define a Customer Thread. A Customer thread is created for each new Pizza Order. The primary function of the Customer Thread is to wait for the Pizza order to complete.
3. We define a Baker Thread to bake the Pizzas. We create 3 Baker Threads to keep up with out business. Bakers remove Pizzas from the front of the LinkedList and bake the Pizzas.

Here is the sequence of activity:

1. The main routine of the PizzaStore allows us to type in Pizza Orders. For each Pizza Order, the orderPizza method is called. The orderPizza Method creates a new Pizza order and adds it to the tail of the LinkedList. The orderPizza method also calls notify to let any sleeping bakers know there is more work to do.
2. The main routine also creates a Customer Thread to wait for the Pizza to be baked. The primary job of the Customer Thread is to call the waitForPizza method in the Pizza class. This method will end up calling wait(), because it takes some time to bake a Pizza.
3. Meanwhile, if there is an available Baker, then the Pizza order has been removed from the LinkedList with a call to getPizzaToBake.
4. The Baker then calls the bake method in the Pizza class. This method takes some time to bake the Pizza. When the Pizza is done, the bake method calls notify. This call should wake up the hungry Customer.

To terminate this program, we need to do a Control-C which terminates everything.


import java.util.*;

class Pizza
{
    boolean done=false;
    String name;
    int bakerIdent=-1;
    String[] toppings;
    Pizza(String n, String[] t)
    {
        name =n;
        toppings =t;
    }
    void print()
    {
        System.out.println("Pizza for " + name + " BakerId = " + bakerIdent);
        System.out.print("toppings: ");
        for (int i=0; i < toppings.length; i++)
            System.out.print(toppings[i] + " ");
        System.out.println();
    }
    synchronized void bake(int id)
    {
        bakerIdent = id;
        try {
        // Takes 20 seconds to bake a Pizza
            Thread.sleep(20000);
            done = true;
            notify(); // Wake up Waiting Customer in waitForPizza
        }
        catch (InterruptedException e)
        {
        }
    }
    synchronized void waitForPizza()
    {
        while (!done )
        {
            try { wait(); } // Wait for Pizza Baking Completion
            catch (InterruptedException e) {}
        }
        System.out.println(" ******Customer: Pizza Delivered --- ready to eat");
        print();
    }
}
class Customer extends Thread
{
    Pizza pizza;
    Customer (Pizza p)
    {
        pizza =p;
    }
    public void run()
    {
        pizza.waitForPizza();
    }
}

class Baker extends Thread
{
    int ident;
    PizzaStore store;
    Baker (int id, PizzaStore ps)
    {
        ident = id;
        store = ps;
    }
    public void run()
    {
        Pizza pizza;

        for (;;)
        {
            pizza = store.getPizzaToBake();
            pizza.bake(ident);
        }
    }
}



class PizzaStore{
    LinkedList pizzaList = new LinkedList();

    synchronized Pizza orderPizza(String name, String[] toppings)
    {
        Pizza pizza= new Pizza(name, toppings);
        pizzaList.addLast(pizza);
        notify(); // Wake up any sleeping Bakers
        return pizza;
    }
    synchronized Pizza getPizzaToBake()
    {
        Pizza pizza=null;
        do
        {
            try
            {
                if (pizzaList.size() > 0)
                    pizza = (Pizza) pizzaList.removeFirst();
             }
             catch (NoSuchElementException e)
             {
                //We get here when the Bakers have
                //baked all of the Pizzas ordered so far
                pizza = null;
             }
            if (pizza == null)
            {
                try { wait();} // Wait for incomming Pizza Order
                catch (InterruptedException e){}
            }
        } while (pizza == null );
        return pizza;
    }

    public static void main(String[] args)
    {
        PizzaStore store = new PizzaStore();
        Baker[] baker = new Baker[3];
        Customer customer;
        Pizza pizza;
        Scanner in = new Scanner(System.in);
        String str, custName;
        String[] toppings;
        StringTokenizer token;
        int count;

        // Create 3 bakers
        for (int i=0; i < baker.length; i ++)
        {
          baker[i] = new Baker(i+1, store);
          baker[i].start();
        }
        for (;;)
        {
            System.out.println("ENTER: Name Topping1 Topping2 ...");
            System.out.println("ENTER: BYE to quit");
            str = in.nextLine();
            str = str.trim();
            if (str.equals("BYE")) break;
            token = new StringTokenizer(str);
            count = token.countTokens();
	    if (count <= 0)
	    {
	        System.out.println("incomplete order");
		continue;
	    }
            toppings = new String[ count -1];
            custName = (String)token.nextElement();
            for (int i=0; i < toppings.length; i++)
                toppings[i] = (String) token.nextElement();

            pizza = store.orderPizza(custName, toppings);
            customer = new Customer(pizza);
            customer.start();
        }


    }// End of Main
}


Terminating Processes:

If you look at online help for the Thread class, you will note some methods with the name of stop that are Deprecated. This means that the routine exists, but the recommendation is that you don't use it. In many cases it is a signal that future releases may not support these routines. Why do you think the stop routine is being removed???

The recommended way to remove threads is to get the thread to voluntarily terminate. In the following example, we will implement a Termination process that immediately gets rid of all of our threads using such a technique.

PizzaStore.java: Second Version

Suppose we want to have a command called BYE that lets us go out of business cleanly. If we just exit the main routine when we encounter the BYE command, we will leave 3 bakers continuing to run. We will also leave Customers waiting for their Pizzas. This is not a very professional way to go out of business. We would like to add some logic associated with BYE that will be as courteous as to deliver Pink slips to the Bakers. We also would like our Bakers to be polite enough to terminate their active Pizza Orders.

I have marked up the changes. Its a bit messy but seems to work. The only new feature that I have used is the method in the Thread class called
interrupt()
This method will wake a Thread from a sleep call or a wait call. The thread will get an InterruptedException in this case.


import java.util.*;

class Pizza
{
    boolean done=false;
    boolean inBusiness = true;
    String name;
    int bakerIdent=-1;
    String[] toppings;
    Pizza(String n, String[] t)
    {
        name =n;
        toppings =t;
    }
    void print()
    {
        System.out.println("Pizza for " + name + " BakerId = " + bakerIdent);
        System.out.print("toppings: ");
        for (int i=0; i < toppings.length; i++)
            System.out.print(toppings[i] + " ");
        System.out.println();
    }
    synchronized void bake(int id)
    {
        bakerIdent = id;
        try {
            Thread.sleep(20000);
            done = true;
            notify(); // Wake up Waiting Customer in waitForPizza
        }
        catch (InterruptedException e)
        {
            outOfBusiness();
        }
    }
    synchronized void outOfBusiness()
    {
       inBusiness = false;
       notify(); // let customer know we went out of business
       System.out.println("pizza.Out of business");
    }
    synchronized void waitForPizza()
    {
        while (!done && inBusiness)
        {
            try { wait(); }  // Wait for Pizza Baking Completion
            catch (InterruptedException e) {}
        }
        if (inBusiness)
            System.out.println(" ******Customer: Pizza Delivered --- ready to eat");
        else
            System.out.println(" ******Customer: Pizza Store out of business ");
        print();
    }
}
class Customer extends Thread
{
    Pizza pizza;
    Customer (Pizza p)
    {
        pizza =p;
    }
    public void run()
    {
        pizza.waitForPizza();
    }
}

class Baker extends Thread
{
    int ident;
    PizzaStore store;
    Baker (int id, PizzaStore ps)
    {
        ident = id;
        store = ps;
    }
    public void run()
    {
        Pizza pizza;

        for (;;)
        {
            pizza = store.getPizzaToBake();
            if (pizza == null) break; // Out of business
            pizza.bake(ident);
        }
        System.out.println("*****Baker " + ident + " terminating");
    }
}



class PizzaStore{
    LinkedList pizzaList = new LinkedList();
    boolean inBusiness = true;

    synchronized Pizza orderPizza(String name, String[] toppings)
    {
        Pizza pizza= new Pizza(name, toppings);
        pizzaList.addLast(pizza);
        notify(); // Wake up any sleeping Bakers
        return pizza;
    }
    synchronized Pizza getPizzaToBake()
    {
        Pizza pizza=null;
        if (!inBusiness) return null;
        do
        {
            try
            {
                if (pizzaList.size() > 0)
                    pizza = (Pizza) pizzaList.removeFirst();
             }
             catch (NoSuchElementException e)
             {
                pizza = null;
             }
            if (pizza == null)
            {
                try { wait();} // Wait for incomming Pizza Order
                catch (InterruptedException e){}
            }
        } while (pizza == null && inBusiness);
        return pizza;
    }
    synchronized void outOfBusiness()
    {
        inBusiness = false;
        notifyAll(); // Wake up all bakers so they can terminate
        while (pizzaList.size() > 0)
        {
	    // For all of the Pizzas sitting in the queue, we need to
	    // let hungry customers know that we are out of business
            Pizza pizza = (Pizza)pizzaList.removeFirst();
            pizza.outOfBusiness();
        }
    }

    public static void main(String[] args)
    {
        PizzaStore store = new PizzaStore();
        Baker[] baker = new Baker[3];
        Customer customer;
        Pizza pizza;
        Scanner in = new Scanner ( System.in);
        String str, custName;
        String[] toppings;
        StringTokenizer token;
        int count;

        // Create 3 bakers
        for (int i=0; i < baker.length; i ++)
        {
          baker[i] = new Baker(i+1, store);
          baker[i].start();
        }
        for (;;)
        {
            System.out.println("ENTER: Name Topping1 Topping2 ...");
            System.out.println("ENTER: BYE to quit");
            str = in.nextLine();
            str = str.trim();
            if (str.equals("BYE")) break;
            token = new StringTokenizer(str);
            count = token.countTokens();
	    if (count <= 0)
	    {
	        System.out.println("incomplete order");
		continue;
	    }
            toppings = new String[ count -1];
            custName = (String)token.nextElement();
            for (int i=0; i < toppings.length; i++)
                toppings[i] = (String) token.nextElement();

            pizza = store.orderPizza(custName, toppings);
            customer = new Customer(pizza);
            customer.start();
        }
        System.out.println("Exitting Loop Logic");
        store.outOfBusiness();
        for (int i=0; i < baker.length; i ++)
        {
          baker[i].interrupt();
        }

    }// End of main
}


Alternative approach to going out of business:

The above approach assumed that BYE meant I want to exit everything cleanly immediately. Create an alternative approach that isn't quite so impatient. Assume that it is OK for our bakers to empty the Pizza Queue and bake all outstanding orders before they exit their job. You should find this approach is a lot simpler --- but it takes a little longer to clean up.

Last Updated: October 3, 2012 9:26 AM