Course Map

Agenda

• Understand how multiple threads can execute in parallel
• Learn how to implement threads
• Understand race conditions and deadlocks
• Be able to avoid corruption of shared objects by using synchronized methods
• Be able to use threads for programming animations

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
• 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

Subclassing Thread

• Implement a class that extends the Thread class
• Place the code for your task into the run method of your class
• Create an object of your subclass
• Call the start method of your class to start the thread
• When a Thread object is started, the code in its run method is executed in a new thread

GreetingThread Outline

public class GreetingThread extends Thread
{
   public void run()
   {
      //thread action
      . . .
   }
   //variables used by the thread action
   . . .
}

Thread Action for GreetingThread

• Print a time stamp
• Print the greeting
• Wait a second

GreetingThread

• We can get the date and time by constructing a Date object
  Date now = new Date();
• To wait a second, use the sleep method of the Thread class
  sleep(milliseconds)
• A sleeping thread can generate an InterruptedException
  • Catch the exception
  • Terminate the thread

GreetingThread run method

public run()
{
   try
   {
      //thread action
   )
   catch (InterruptedException exception)
   {
      //cleanup, if necessary
   }
}

File GreetingThread.java

To Start the Thread

• Construct an object of your thread class
  

  GreetingThread t = new GreetingThread("Hello World");

• Call the start method
  

  t.start();

File GreetingThreadTest.java

Output

Thu Dec 28 23:12:03 PST 2004 Hello, World!
Thu Dec 28 23:12:03 PST 2004 Goodbye, World!
Thu Dec 28 23:12:04 PST 2004 Hello, World!
Thu Dec 28 23:12:05 PST 2004 Hello, World!
Thu Dec 28 23:12:04 PST 2004 Goodbye, World!
Thu Dec 28 23:12:05 PST 2004 Goodbye, World!
Thu Dec 28 23:12:06 PST 2004 Hello, World!
Thu Dec 28 23:12:06 PST 2004 Goodbye, World!
Thu Dec 28 23:12:07 PST 2004 Hello, World!
Thu Dec 28 23:12:07 PST 2004 Goodbye, World!
Thu Dec 28 23:12:08 PST 2004 Hello, World!
Thu Dec 28 23:12:08 PST 2004 Goodbye, World!
Thu Dec 28 23:12:09 PST 2004 Hello, World!
Thu Dec 28 23:12:09 PST 2004 Goodbye, World!
Thu Dec 28 23:12:10 PST 2004 Hello, World!
Thu Dec 28 23:12:10 PST 2004 Goodbye, World!
Thu Dec 28 23:12:11 PST 2004 Goodbye, World!
Thu Dec 28 23:12:11 PST 2004 Hello, World!
Thu Dec 28 23:12:12 PST 2004 Goodbye, World!
Thu Dec 28 23:12:12 PST 2004 Hello, World!

Implementing Runnable

Often more flexible to implement Runnable than extend Thread

1. Create an object of your subclass that implements Runnable

   Runnable r = new MyRunnable();

2. Construct a Thread object from the runnable object.

   Thread t = new Thread(r);

3. Call the start method to start the thread.

   t.start();

 1 public class Animal {
 2 }

 1 public class Cat extends Animal implements Runnable {
 2
 3     private final String msg;
 4     private final long sleepTime;
 5
 6     public Cat(String msg, long sleepTime) {
 7         this.msg = msg;
 8         this.sleepTime = sleepTime;
 9     }
10
11     public void run() {
12
13         while (true) {
14
15             System.out.println(msg);
16             try {
17                 Thread.sleep(sleepTime);
18             }
19             catch (InterruptedException e) {
20             }
21         }
22     }
23 }

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

Thread Scheduler

• 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.
• Time Slicing - the thread scheduler runs each thread for a short amount of time called a time slice
• Then the scheduler picks another thread from those that are runnable
• A thread is runnable if it is not asleep or blocked in some way
• There is no guarantee about the order in which threads are executed

Self Check

1. What happens if you change the call to the sleep method in the run method to Thread.sleep(1)?
2. What would be the result of the program if the main method called

   t1.run();
   t2.run();

   instead of starting threads?

Answers

1. The messages are printed about one millisecond apart.
2. The first call to run would print ten "Hello" messages, and then the second call to run would print ten "Goodbye" messages.

Terminating Threads

• A thread terminates when its run method terminates
• Do not terminate a thread using the deprecated stop method
• Instead, notify a thread that it should terminate

  t.interrupt();

• interrupt does not cause the thread to terminate–it sets a boolean field in the thread data structure

Terminating Threads

• A thread's run method should check occasionally whether it has been interrupted
  • Use the isInterrupted method
  • An interrupted thread should release resources, clean up, and exit
• The sleep method throws an InterruptedException when a sleeping thread is interrupted
  • Catch the exception
  • Terminate the thread

public void run() {
   try
   {
      for (int = 1;
           i <= REPETITIONS && !isInterrupted();
           i++)
      {
         //do the work
      }
   }
   catch (InterruptedException exception)
   {
	// exit interrupted thread
   }
   //cleanup
}

• Java does not force a thread to terminate when it is interrupted
• It is entirely up to the thread what it does when it is interrupted
• Interrupting is a general mechanism for getting the thread's attention

Making a Thread Sleep and Controlled Stopping

Applying Thread.sleep() or inJava 5 the utility TimeUnit class

Clock.java

volatile
Roughly speaking, a volatile field is safe for concurrent use by two or more threads. More accurately, volatile says that the value of a field must always be read from to main memory and that it may not be cached by a thread (in register or CPU cache).

Self Check

3. Suppose a web browser uses multiple threads to load the images on a web page. Why should these threads be terminated when the user hits the "Back" button?

Self Check

4. Consider the following runnable.

   public class MyRunnable implements Runnable
   {
      public void run()
      {
         try
         {
            System.out.println(1);
            Thread.sleep(1000);
            System.out.println(2);
         }
         catch (InterruptedException exception)
         {
            System.out.println(3);
         }
         System.out.println(4);
      }
   }

   Suppose a thread with this runnable is started and immediately interrupted.

   Thread t = new Thread(new MyRunnable());
   t.start();
   t.interrupt();

   What output is produced?

Answers

3. If the user hits the "Back" button, the current web page is no longer displayed, and it makes no sense to expend network resources for fetching additional image data.
4. The run method prints the values 1, 3, and 4. The call to interrupt merely sets the interruption flag, but the sleep method immediately throws an InterruptedException.

Race Conditions

• When threads share a common object, they can conflict with each other
• Sample program: multiple threads manipulate a bank account
  Here is the run method of DepositThread:

  public void run()
  {
     try
     {
        for (int i = 1; i <= count; i++)
        {
           account.deposit(amount);
           Thread.sleep(DELAY);
        }
     }
     catch (InterruptedException exception)
     {
     }
  }

• The WithdrawRunnable class is similar

Sample Application

• Create a BankAccount object, with a zero balance
• Create a DepositThread t0 to deposit $100 into the account for 10 iterations
• Create a WithdrawThread t1 to withdraw $100 from the account for 10 iterations
• The result should be zero, but sometimes it is not

Scenario to Explain Non-zero Result

• The first thread t0 executes the lines

  System.out.print("Depositing " + amount);
  double newBalance = balance + amount;

• t0 reaches the end of its time slice and t1 gains control
• t1 calls the withdraw method which withdraws $100 from the balance variable.
• Balance is now -100
• t1 goes to sleep
• t0 regains control and picks up where it left off.
• t0 executes the lines

  System.out.println(", new balance is " + newBalance);
  balance = newBalance;

• The balance is now 100 instead of 0 because the deposit method used the OLD balance
• This is called a race condition.

Race Condition

• Occurs if the effect of multiple threads on shared data depends on the order in which they are scheduled
• It is possible for a thread to reach the end of its time slice in the middle of a statement
• It may evaluate the right-hand side of an equation but not be able to store the result until its next turn

  public void deposit(double amount)
  {
     balance = balance + amount;
     System.out.print("Depositing " + amount + ", new balance is " + balance);
  }

  Race condition can still occur:

  balance = the right-hand-side value

Corrupting the Contents of the balance Field

File BankAccountThreadTest.java

File DepositThread.java

File WithdrawThread.java

File BankAccount.java

Output

Depositing 100.0, new balance is 100.0
Withdrawing 100.0, new balance is 0.0
Depositing 100.0, new balance is 100.0
Withdrawing 100.0, new balance is 0.0
. . .
Withdrawing 100.0, new balance is 400.0
Depositing 100.0, new balance is 500.0
Withdrawing 100.0, new balance is 400.0
Withdrawing 100.0, new balance is 300.0

Self Check

5. Give a scenario in which a race condition causes the bank balance to be -100 after one iteration of a deposit thread and a withdraw thread.
6. Suppose two threads simultaneously insert objects into a linked list. Explain how the list can be damaged in the process.

Answers

5. There are many possible scenarios. Here is one:
   • The first thread loses control after the first print statement.
   • The second thread loses control just before the assignment balance = newBalance.
   • The first thread completes the deposit method.
   • The second thread completes the withdraw method.
6. One thread calls addFirst and is preempted just before executing the assignment first = newLink. Then the next thread calls addFirst, using the old value of first. Then the first thread completes the process, setting first to its new link. As a result, the links are not in sequence.

Synchronizing Object Access

• To solve problems such as the one just seen, use a lock object
• A lock object is used to control threads that manipulate shared resources
• In Java: Lock interface and several classes that implement it
  • ReentrantLock: most commonly used lock class
  • Locks are a feature of Java version 5.0
  • Earlier versions of Java have a lower-level facility for thread synchronization

Synchronizing Object Access

• Typically, a lock object is added to a class whose methods access shared resources, like this:

  public class BankAccount
  {
     public BankAccount()
     {
        balanceChangeLock = new ReentrantLock();
        . . .
     }
     . . .
     private Lock balanceChangeLock;
  }

Synchronizing Object Access

• Code that manipulates shared resource is surrounded by calls to lock and unlock:

  balanceChangeLock.lock();
  Code that manipulates the shared resource
  balanceChangeLock.unlock();

Synchronizing Object Access

• If code between calls to lock and unlock throws an exception, call to unlock never happens
• To overcome this problem, place call to unlock into a finally clause:

  public void deposit(double amount)
  {
     balanceChangeLock.lock();
     try
     {
        System.out.print("Depositing " + amount);
        double newBalance = balance + amount;
        System.out.println(", new balance is " + newBalance);
        balance = newBalance;
     }
     finally
     {
        balanceChangeLock.unlock();
     }
  }

Synchronizing Object Access

• When a thread calls lock, it owns the lock until it calls unlock
• A thread that calls lock while another thread owns the lock is temporarily deactivated
• Thread scheduler periodically reactivates thread so it can try to acquire the lock
• Eventually, waiting thread can acquire the lock
• The Java Memory Model
  If a thread changes shared data and then releases a lock, and another thread acquires the same lock and reads the same data, then it is guaranteed to see the changed data.
• Use locks or synchronized methods when accessing shared data among multiple threads (multiple CPUs), even if you are not concerned about race condition.

Self Check

7. If you construct two BankAccount objects, how many lock objects are created?
8. What happens if we omit the call unlock at the end of the deposit method?

Answers

7. Two, one for each bank account object. Each lock protects a separate balance field.
8. When a thread calls deposit, it continues to own the lock, and any other thread trying to deposit or withdraw money in the same bank account is blocked forever.

Avoiding Deadlocks

• A deadlock occurs if no thread can proceed because each thread is waiting for another to do some work first
• BankAccount example

  public void withdraw(double amount)
  {
     balanceChangeLock.lock();
     try
     {
        while (balance < amount)
           Wait for the balance to grow
        . . .
     }
     finally
     {
        balanceChangeLock.unlock();
     }
  }

Avoiding Deadlocks

• How can we wait for the balance to grow?
• We can't simply call sleep inside withdraw method;
  thread will block all other threads that want to use balanceChangeLock
• In particular, no other thread can successfully execute deposit
• Other threads will call deposit, but will be blocked until withdraw exits
• But withdraw doesn't exit until it has funds available
• DEADLOCK

Condition Objects

• To overcome problem, use a condition object
• Condition objects allow a thread to temporarily release a lock, and to regain the lock at a later time
• Each condition object belongs to a specific lock object
• You obtain a condition object with newCondition method of Lock interface

  public class BankAccount
  {
     public BankAccount()
     {
        balanceChangeLock = new ReentrantLock();
        sufficientFundsCondition = balanceChangeLock.newCondition();
        . . .
     }
     . . .
     private Lock balanceChangeLock;
     private Condition sufficientFundsCondition;
  }

Thread Cooperation: Condition Objects

• It is customary to give the condition object a name that describes condition to test
• You need to implement an appropriate test
• As long as test is not fulfilled, call await on the condition object:

  public void withdraw(double amount)
  {
     balanceChangeLock.lock();
     try
     {
        while (balance < amount)
        sufficientFundsCondition.await();
        . . .
     }
     finally
     {
        balanceChangeLock.unlock();
     }
  }

Thread Cooperation: Condition Objects

• Calling await
  • Makes current thread wait
  • Allows another thread to acquire the lock object
• To unblock, another thread must execute signalAll on the same condition object

  sufficientFundsCondition.signalAll();

• signalAll unblocks all threads waiting on the condition
• signal: randomly picks just one thread waiting on the object and unblocks it
• signal can be more efficient, but you need to know that every waiting thread can proceed
• Recommendation: always call signalAll

File BankAccountThreadTester.java

File BankAccount.java

File DepositRunnable.java

File WithdrawRunnable.java

Output

Depositing 100.0, new balance is 100.0
Withdrawing 100.0, new balance is 0.0
Depositing 100.0, new balance is 100.0
Depositing 100.0, new balance is 200.0
. . .
Withdrawing 100.0, new balance is 100.0
Depositing 100.0, new balance is 200.0
Withdrawing 100.0, new balance is 100.0
Withdrawing 100.0, new balance is 0.0

Self Check

9. What is the essential difference between calling sleep and await?
10. Why is the sufficientFundsCondition object a field of the BankAccount class and not a local variable of the withdraw and deposit methods?

Answers

9. A sleeping thread is reactivated when the sleep delay has passed. A waiting thread is only reactivated if another thread has called signalAll or signal.
10. The calls to await and signal/signalAll must be made to the same object.

Solving the Race Condition Problem - Low-Level Approach

• A thread must be able to lock an object temporarily
• When a thread has the object locked, no other thread can modify the state of the object.
• In Java, use synchronized methods to do this
• Tag all methods that contain thread-sensitive code with the keyword synchronized

Synchronized Methods: Mutual Exclusion

public class BankAccount
{
   public synchronized void deposit(double amount)
   {
      . . .
   }

   public synchronized void withdraw(double amount)
   {
      . . .
   }
   . . .
}

Monitors and Non-reentrant  Mutually Exclusive Locks (Mutex)

A monitor is a body of code (not necessarily contiguous, developed by C. A. R. Hoare), access to which is guarded by a mutual-exclusion locks (or mutex) that is associated with an object. The central notion of mutex is ownership. Only one thread can own the mutex at a time. If a second thread tries to acquire ownership, it will block (be suspended) until the owning thread releases the mutex.

synchronized(obj) {

	// guard code

}

is effectively the same as this code:

obj.myMutex.acquire();
try {

	// guard code

}
finally {

	obj.myMutex.release();

}

Synchronized Method:  Mutual Exclusion

• By declaring both the deposit and withdraw methods to be synchronized
  • Our program will run correctly
  • Only one thread at a time can execute either method on a given object
  • When a thread starts one of the methods, it is guaranteed to execute the method to completion before another thread can execute a synchronized method on the same object.
    

Synchronized Methods: Mutual Exclusion

• By executing a synchronized method:
  • The thread acquires the object lock.
  • No other thread can acquire the lock.
  • No other thread can modify the state of the object until the first thread is finished

Visualization of Synchronized Thread Behavior

• Imagine the object is a restroom that only one person can use at a time
• The threads are people
• If the restroom is empty, a person may enter
• If a second person finds the restroom locked, the second person must wait until it is empty
• If multiple people want to gain access to the restroom , they all wait outside
• The people may not form an orderly queue;
• A randomly chosen person may gain access when the restroom becomes available again

Deadlock

• A deadlock occurs if no thread can proceed because each thread is waiting for another to do some work first
• BankAccount example

  public synchronized void withdraw(double amount)
  {
     while (balance < amount)
        //wait for balance to grow
     . . .
  }

Thread Cooperation with Mutexes

• Mutual exclusion is only half of the thread synchronization story: Java also supports thread cooperation.
• The wait method temporarily releases the object lock and deactivates the thread
• Restroom analogy
  • Don't want the person in the restroom to go to sleep if there is no toilet paper.
  • Think of the person giving up and leaving
  • This gives another person a chance to enter and refill the toilet paper

withdraw Method to Cooperate and Avoid Deadlock

public synchronized void withdraw(double amount)
   throws InterruptedException
{
   while (balance < amount)
      wait();
}

Object.wait() and Object.notify(), Object.notifyAll()

• A thread that calls wait is in a blocked state
• It will not be activated by the thread scheduler until it is unblocked
• It is unblocked when another thread calls notify, notifyAll
• When a thread calls notifyAll, all threads waiting on the object's monitor are unblocked
• notify wakes up a single thread that is waiting on this object's monitor
• Only the thread that has the lock can call notify, notifyAll

Restroom wait/notifyAll Analogy

• The thread calling wait corresponds to the person who enters the restroom and finds there is no toilet paper
• The person then leaves the restroom and waits outside
• Other people may enter and leave, but the first person just waits
• Eventually an attendant enters the restroom, refills the toilet paper, and shouts a notification
• All the waiting people compete for the restroom

The Java Monitor

• A monitor is like a building that contains one special room (which usually contains some data - analog: toilet, toilet paper) that can be occupied by only one thread at a time.  Each object has its own monitor.
  
  

Thread Blocking

• A thread can be in one of the following 6 states:
  • NEW
    A thread that has not yet started is in this state.
  • RUNNABLE
    A thread executing in the Java virtual machine is in this state.
  • BLOCKED
    A thread that is blocked waiting for a monitor lock is in this state.
  • WAITING
    A thread that is waiting indefinitely for another thread to perform a particular action is in this state.
  • TIMED_WAITING
    A thread that is waiting for another thread to perform an action for up to a specified waiting time is in this state.
  • TERMINATED
    A thread that has exited is in this state.

  A thread can be in only one state at a given point in time. These states are virtual machine states which do not reflect any operating system thread states.

  A thread in the blocked state is waiting for a monitor lock to enter a synchronized block/method or reenter a synchronized block/method after calling Object.wait

  A thread is in the waiting state due to calling one of the following methods:

  • Object.wait with no timeout
  • Thread.join with no timeout

  A thread is in the timed waiting state due to calling one of the following methods with a specified positive waiting time:

  • Thread.sleep
  • Object.wait with timeout
  • Thread.join with timeout

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

class IsSafe {

	double x;

	public void synchronized mark() (
		x = 0;
	}

	public void john() {
		x = -1;
	}
}

File BankAccountThreadTest.java

Using synchronized methods: cooperation

File BankAccount.java

Counting Semaphores (1965, E. W. Dijkstra)

Conceptually, a semaphore maintains a set of permits. Each acquire() blocks if necessary until a permit is available, and then takes it. Each release() adds a permit, potentially releasing a blocking acquirer. However, no actual permit objects are used; the Semaphore just keeps a count of the number available and acts accordingly.

• A semaphore is a synchronizer that uses a counter of one or more permits to limit the number of threads that can access limited resources
• Threads call to acquire() obtain a permit
• If no permits are available acquire() blocks
• Acts like bouncer, only allowing so many people into the party at one time
• Semaphores are often used to restrict the number of threads than can access some (physical or logical) resource
• Binary semaphore
  Semaphore sem = new Semaphore (1, false);
• Binary semaphores have no notion of ownership, the "lock" can be released by a thread other than the owner

Controlling Access to a Pool of Items

The semaphore encapsulates the synchronization needed to restrict access to the pool, separately from any synchronization needed to maintain the consistency of the pool itself.

class Pool {
   private static final MAX_AVAILABLE = 100;
   private final Semaphore available = new Semaphore(MAX_AVAILABLE, true);

   public Object getItem() throws InterruptedException {
     available.acquire();
     return getNextAvailableItem();
   }

   public void putItem(Object x) {
     if (markAsUnused(x))
       available.release();
   }

   // Not a particularly efficient data structure; just for demo
   protected Object[] items = ... whatever kinds of items being managed
   protected boolean[] used = new boolean[MAX_AVAILABLE];

   protected synchronized Object getNextAvailableItem() {
     for (int i = 0; i < MAX_AVAILABLE; ++i) {
       if (!used[i]) {
          used[i] = true;
          return items[i];
       }
     }
     return null; // not reached
   }

   protected synchronized boolean markAsUnused(Object item) {
     for (int i = 0; i < MAX_AVAILABLE; ++i) {
       if (item == items[i]) {
          if (used[i]) {
            used[i] = false;
            return true;
          } else
            return false;
       }
     }
     return false;
   }

 }
 

Other Synchronizers

• java.util.concurency.CountDownLatch
A synchronization aid that allows one or more threads to wait until a set of operations being performed (preprocessing) in other threads completes.
A CountDownLatch is initialized with a given count. The await methods block until the current count reaches zero due to invocations of the countDown() method, after which all waiting threads are released and any subsequent invocations of await return immediately.
• java.util.concurency.Exchanger
A synchronization point provides for thread rendezvous at which two threads can exchange objects.
Each thread presents some object on entry to the exchange method, and receives the object presented by the other thread on return.
• java.util.concurency.CyclicBarrier
A synchronization aid (multiple thread rendezvous) that allows a set of threads to all wait for each other to reach a common barrier point. CyclicBarriers are useful in programs involving a fixed sized party of threads that must occasionally wait for each other. The barrier is called cyclic because it can be re-used after the waiting threads are released.
  Useful for master/slave applications - CyclicBarrier(int parties, Runnable barrierAction)

Animation

• Animation shows different objects moving or changing as time progresses
• Thread programming is useful in animation
• An algorithm animation helps visualize the steps in the algorithm

Algorithm Animation

• Runs in a separate thread that periodically updates an image of the current state of the algorithm
• It then pauses so the user can see the change
• After a short time the algorithm thread wakes up and runs to the next point of interest
• It updates the image again and pauses again

Selection Sort Algorithm Animation

• Items in the algorithm's state
  • The array of values
  • The size of the already sorted area
  • The currently marked element
• To visualize the algorithm
  • Show the sorted part of the array in a different color
  • Mark the currently visited array element in red.

Selection Sort Algorithm Animation

• Add an Applet instance variable to the algorithm class

  public class SelectionSorter
  {
     public SelectionSorter(int[] anArray, Applet anApplet)
     {
        a = anArray;
        applet = anApplet;
     }
     . . .
     private Applet applet
  }

Selection Sort Algorithm Animation

• Supply a pause method that sleeps for a time proportional to the number of steps involved,  one unit of time for each array element visited

  public void pause(int steps)
        throws InterruptedException
  {
     if (Thread.currentThread().isInterrupted())
        throw new InterruptedException();
     applet.repaint();
     Thread.sleep(steps * DELAY);
  }

Selection Sort Algorithm Animation

• Add a draw method to draw the current state of the array

  public void draw(Graphics2D g2)
  {
     int deltaX = applet.getWidth() / a.length;
     for (int i = 0; i < a.length; i++)
     {
        if (i == markedPosition)
           g2.setColor(Color.red);
        else if (i <= alreadySorted)
           g2.setColor(Color.blue);
        else
           g2.setColor(Color.black);
        g2.draw(new Line2D.Double(i * deltaX, 0,
           i * deltaX, a[i]));
     }
  }

Selection Sort Algorithm Animation

• Add a pause to the minimumPosition method

  public int minimumPosition(int from)
     throws InterruptedException
  {
     int minPos = from;
     for (int i = from + 1; i < a.length; i++)
     {
        if (a[i] < a[minPos]) minPos = i;
  
        markedPosition = i;
        pause(2);
     }
     return minPos;
  }

• Add a similar pause to the sort method

Applet to Provide User Interface

• Start the animation with a mousePressed event
  If an animation is already running, interrupt the thread to terminate it

  public class SelectionSortApplet extends Applet
  {
     public SelectionSortApplet()
     {
        class MousePressListener extends MouseAdapter
        {
           public void mousePressed(MouseEvent event)
           {
               if (animation != null && animation.isAlive())
                 animation.interrupt();
              startAnimation();
           }
        }
  
        MouseListener listener = new MousePressListener();
        addMouseListener(listener);
        . . .
        animation = null;
      }
  
     . . .
     private Thread Animation
  }
     

Applet to Provide User Interface

• The Applet's paint method calls the draw method of the algorithm

     public void paint(Graphics g)
     {
        if (sorter == null) return;
        Graphics2D g2 = (Graphics2D)g;
        sorter.draw(g2);
     }

Applet to Provide User Interface

• The Applet provides a startAnimation method
  • It constructs a SelectionSorter with a new array and a this reference to the Applet
  • It constructs a thread
  • The thread's run method calls the sorter's sort method

Applet to Provide User Interface

• startAnimation method

  public void startAnimation()
  {
     class AnimationThread extends Thread
     {
        public void run()
        {
           try
           {
              sorter.sort();
           }
           catch (InterruptedException exception)
           {
           }
        }
      }
  
      int[] values = ArrayUtil.randomIntArray(30, 300);
      sorter = new SelectionSorter(values, this);
      animation = new AnimationThread();
      animation.start();
  }

A Step in the Animation of the Selection Sort Algorithm

File SelectionSortApplet.java

File SelectionSorter

ArrayUtil

Making a System Call

• Use the exec() method of the java.lang.Runtime class.
• A new way of executing a command in a separate process, through a class called ProcessBuilder.
• ProcessBuilder in the java.lang package (like Runtime and Process).
• The Runtime class, also allows you to discover memory usage and add a shutdown hook.
• The six versions of the exec() method of Runtime:

public Process exec(String command)
             throws IOException

public Process exec(String command,
                    String[] envp)
             throws IOException

public Process exec(String command,
                    String[] envp,
                    File dir)
             throws IOException

public Process exec(String[] cmdarray)
             throws IOExceptionjava

public Process exec(String[] cmdarray,
                    String[] envp)
             throws IOException

public Process exec(String[] cmdarray,
                    String[] envp,
                    File dir)
             throws IOException

An example using Runtime: DoRuntime

• It that shows how to execute a command with the Runtime class.
• The command to run is passed in from the command line.

   import java.io.*;
   import java.util.*;
   
   public class DoRuntime {
     public static void main(String args[]) throws IOException {
       if (args.length <= 0) {
         System.err.println("Need command to run");
         System.exit(-1);
       }
       Runtime runtime = Runtime.getRuntime();
       Process process = runtime.exec(args);
       InputStream is = process.getInputStream();
       InputStreamReader isr = new InputStreamReader(is);
       BufferedReader br = new BufferedReader(isr);
       String line;
       System.out.printf("Output of running %s is:", 
           Arrays.toString(args));
       while ((line = br.readLine()) != null) {
         System.out.println(line);
       }

       // check for a command failure  
       try {
           if (process.waitFor() != 0) 
                   System.err.println("exit value = " +
                   process.exitValue());
            }
       }
       catch (InterruptedException e) {
           System.err.println(e);
       }
     }
    } 

• If you run DoRuntime in Solaris like this:

  java DoRuntime ls

• You get output that looks something like this (which depends on the contents of the directory):

  Output of running ls is:DoRuntime.class
  DoRuntime.java   

• Linux users could also pass in "ls" as the command to get a directory listing.
• On a Microsoft Windows platform, commands such as "dir" are internal to the command processor so the single command-line argument would be the quoted string: "cmd /c dir" (again, output would depend on the contents of the directory).

  >java DoRuntime "cmd /c dir"
   Volume in drive D is Users
   Volume Serial Number is 2841-2ED0

   Directory of D:\...

  04/15/2006  09:30 AM    <DIR>          .
  04/15/2006  09:30 AM    <DIR>          ..
  04/15/2006  09:30 AM             1,146 DoRuntime.class
  04/15/2006  09:23 AM               724 DoRuntime.java
  ...

System Call in a Different Directory

• As coded, the command executes in the current working directory with its environment variables intact.
• If you want to run the command in a different directory, and you need to add more arguments to the exec() command, you change:

    Runtime runtime = Runtime.getRuntime();
    Process process = runtime.exec(command);

to:

    File file = new File(other directory);
    Runtime runtime = Runtime.getRuntime();
    Process process = runtime.exec(command, null, file);

• The second parameter in the call to the exec() method identifies the environment variable settings. Because the parameter is "null", the subprocess inherits the environment settings of the current process.

An example using ProcessBuilder: DoProcessBuilder

• The Runtime.exec approach doesn't necessarily make it easy to customize and invoke subprocesses.
• The ProcessBuilder class simplifies things. Through various methods in the class, you can easily modify the environment variables for a process and start the process.

   import java.io.*;
   import java.util.*;
   
   public class DoProcessBuilder {
     public static void main(String args[]) throws IOException {
       if (args.length <= 0) {
         System.err.println("Need command to run");
         System.exit(-1);
       }
       Process process = new ProcessBuilder(args).start();
       InputStream is = process.getInputStream();
       InputStreamReader isr = new InputStreamReader(is);
       BufferedReader br = new BufferedReader(isr);
       String line;
       System.out.printf("Output of running %s is:", 
          Arrays.toString(args));
       while ((line = br.readLine()) != null) {
         System.out.println(line);
       }
      
       // check for a command failure  
       try {
           if (process.waitFor() != 0) 
                   System.err.println("exit value = " +
                   process.exitValue());
            }
       }
       catch (InterruptedException e) {
           System.err.println(e);
       }
     }
    } 
 
  
  > java DoProcessBuilder ls
  Output of running ls is:DoProcessBuilder.class 
  DoProcessBuilder.java
  DoRuntime.class
  DoRuntime.java   

• Notice that the following two lines in DoRuntime:

    Runtime runtime = Runtime.getRuntime();
    Process process = runtime.exec(command);

were changed to the following line in DoProcessBuilder:

    Process process = new ProcessBuilder(command).start();

Using ProcessBuilder

• The ProcessBuilder class has two constructors.
• One constructor accepts a List for the command and its arguments.
• The other constructor accepts a variable number of String arguments.

public ProcessBuilder(List<String> command)
public ProcessBuilder(String... command)

• With ProcessBuilder, you call start() to execute the command.
• Prior to calling start(), you can manipulate how the Process will be created.
• If you want the process to start in a different directory, you don't pass a File in as a command line argument. Instead, you set the process builder's working directory by passing the File to the directory() method:

public ProcessBuilder directory(File directory)

• Setting environment variables, get a Map of the variables through the environment() method, then you manipulate the Map:

   ProcessBuilder processBuilder = new ProcessBuilder(command);
   Map<String, String> env = processBuilder.environment();
   // manipulate env

• The options for manipulating the environment include adding environment variables with the put() method, and removing them with the remove() method. For example:

   ProcessBuilder processBuilder = new ProcessBuilder(
                                       command, arg1, arg2);
   Map<String, String> env = processBuilder.environment();
   env.put("var1", "value");
   env.remove("var3");

• After the environment variables and directory are set, call start():

   processBuilder.directory("Dir");
   Process p = processBuilder.start();

• You can also clear() all the variables from the environment and explicitly set the ones you want.
• With methods such as environment() for adding and removing environment variables from the process space, and start() for starting a new process, ProcessBuilder should make it easier to invoke a subprocess with a modified process environment.
• You can get the initial set of environment variables by calling the getenv() method of System. Understand that not all platforms support changing environment variables. If you try to change an environment variable on a platform that forbids it, the operation will throw either an UnsupportedOperationException or an IllegalArgumentException. Also, when running with a security manager, you'll need the RuntimePermission for "getenv.*", otherwise a SecurityException will be thrown.
• It is possible that the examples will deadlock if the subprocess generates enough output to overflow the system. A more robust solution requires draining the process stdout and stderr in separate threads.