Your task is to write the SortingThread class so it works in combination with the code in lab10.zip. SortingThread should implement the Runnable interface so that when SortingThreadTest is run, it will print something similar to the following:

0 unsynchronized 1

0 unsynchronized 4

0 unsynchronized 4

0 unsynchronized 5

0 unsynchronized 6

0 unsynchronized 7

0 unsynchronized 8

0 unsynchronized 9

0 unsynchronized 9

0 unsynchronized 9

1 unsynchronized 0

1 unsynchronized 1

1 unsynchronized 2

1 unsynchronized 3

1 unsynchronized 3

1 unsynchronized 6

1 unsynchronized 6

1 unsynchronized 7

1 unsynchronized 8

1 unsynchronized 9

1 synchronized 0

0 synchronized 1

1 synchronized 1

1 synchronized 2

1 synchronized 3

1 synchronized 3

0 synchronized 4

0 synchronized 4

0 synchronized 5

0 synchronized 6

1 synchronized 6

1 synchronized 6

0 synchronized 7

1 synchronized 7

0 synchronized 8

1 synchronized 8

1 synchronized 9

0 synchronized 9

0 synchronized 9

0 synchronized 9

Each thread will get 10 numbers (generated randomly) to sort. Each thread first prints out the numbers without any synchronization. In the above printout, thread 0 printed its numbers before thread 1. It is ok if your program print the unsynchronized numbers in a different order, possibly different on each run.

Next, each thread prints out the numbers synchronizing with the other thread using a SortingBuffer object. One example in the above printout is where thread 0 had to wait for thread 1 to print a few numbers before thread 0 could print a 4.

SortingThread

The SortingThread class must implement the Runnable interface. The constructor needs to remember the parameters in instance variables (the first parameter is the thread number).

The run method of SortingThread is where all the work happens. This is how to synchronize with the SortingBuffer object. For each value in the array, you must first call SortingBuffer's waitUntilMinimum method before printing out the value in the array (printing a line like those shown above). After printing all the values in the array, you must call SortingBuffer's finished method.

SortingBuffer

The waitUntilMinimum method in SortingBuffer stores a value for each thread. It makes a thread wait until its value is the minimum. Sentinel values are used for initialization and finalization. Note that whenever the currentValue array is changed, notifyAll is called.

SortingBuffer could be improved in a couple of ways (not required for this lab, nor do you get extra credit). One would be to compute the minimum more efficiently. Another would be to add a generic type parameter so that SortingBuffer (and SortingThread) could be used for any Comparable type; this would make the initialization and finalization a little bit more difficult.

Lab10.zip

import java.util.*;

import java.util.concurrent.*;

/**

* Test SortingThread code.

*

* @author Tom Bylander

*/

public class SortingThreadTest {

public static void main(String[] args) {

ExecutorService application = Executors.newCachedThreadPool();

int alength = 10;

int[] array0 = new int[alength];

int[] array1 = new int[alength];

Random random = new Random();

for (int i = 0; i < alength; i++) {

array0[i] = random.nextInt(alength);

array1[i] = random.nextInt(alength);

}

SortingBuffer buffer = new SortingBuffer(2);

application.execute(new SortingThread(0, array0, buffer));

application.execute(new SortingThread(1, array1, buffer));

application.shutdown();

}

}

import java.util.Arrays;

/**

* The idea of this class is to get a value from each thread, and

* have each thread wait until its value becomes the minimum.

*

* @author Tom Bylander

*/

public class SortingBuffer {

/**

* The number of threads to help synchronize

*/

private int numberOfThreads;

/**

* The current value from each thread

*/

private int[] currentValue;

/**

* Initialize numberOfThreads and current values for each thread.

*

* @param numberOfThreads

*/

public SortingBuffer(int numberOfThreads) {

this.numberOfThreads = numberOfThreads;

currentValue = new int[numberOfThreads];

// Use a sentinel value to initialize array

Arrays.fill(currentValue, Integer.MIN_VALUE);

}

/**

* Store the value from this thread. Wait until the value is the minimum

* from all the threads. Return when the value becomes the minimum.

*

* It's not a very efficient way to compute the minimum, but it is

* straightforward.

*

* @param thread

* @param value

*/

public synchronized void waitUntilMinimum(int thread, int value)

throws InterruptedException {

currentValue[thread] = value;

notifyAll();

int min;

do {

min = currentValue[0];

for (int i = 1; i < numberOfThreads; i++) {

if (currentValue[i] < min)

min = currentValue[i];

}

if (min < value)

wait();

} while (min < value);

return;

}

/**

* Indicates that the the thread is done with this object.

*

* @param thread

*/

public synchronized void finished(int thread) {

// Use a sentinel value to indicate that the thread is done with this

// object.

currentValue[thread] = Integer.MAX_VALUE;

notifyAll();

}

}