Starting from:
$29.99
Implement Java Threads_Assignment 2 Solution
Assignment 2: Java Threads
This assignment includes two problems that implement Java Threads.
Problem 1: Finding the Maximum Fast!
The usual way to find the maximum of a set of integers is as the following:
max = x[0]; for (i = 1; i < n; i++) if (x[i] max) max = x[i]; This is based on the fact that you have only one CPU and use n - 1 comparisons to find the maximum. But if we have multiple CPUs, we can find the maximum faster:
Let us use a thread to simulate a CPU. Suppose we have n distinct integers x0, x1, ..., xn-1. We first initialize a working array of n entries, say w, to all 1s. This can be done with n threads, each of which writes a 1 into its corresponding entry. More precisely, thread Ti writes 1 into wi. Since each thread (or CPU if you prefer) takes one step to complete its task and since all threads run concurrently, the initialization step only needs one step. After this initialization step, two more steps are required.
Step 2: For each pair of integers xi and xj, we create a thread (or a CPU if you prefer) Tij. This thread compares xi and xj, and writes a 0 into wi if xi < xj. Otherwise, it writes a 0 into wj. Therefore, in this step, we need n(n-1)/2 threads, each of which executes one compare and one write.
Step 3: This step requires n threads. The i-th thread checks the value of wi. If it is a 0, this thread does nothing. If it is a 1, this threads displays the value of xi because it is the maximum! It also requires one step to output the maximum.
Thus, if we have n(n-1)/2 threads, it only takes three comparison steps to find the maximum!
Example
Consider the following example. Suppose we have 4 numbers, x0 = 3, x1 = 1, x2 = 7, x3 = 4. Array w is initialized to 1, 1, 1, 1 (i.e., w0 = w1 = w2 = w3 = 1). In Step 2, we need 4×(4-1)/2= 6 threads:
Thread Name Its Comparison Output T01 Compares x0 = 3 and x1 = 1 Writes 0 into w1 T02 Compares x0 = 3 and x2 = 7 Writes 0 into w0 T03 Compares x0 = 3 and x3 = 4 Writes 0 into w0 T12 Compares x1 = 1 and x2 = 7 Writes 0 into w1 T13 Compares x1 = 1 and x3 = 4 Writes 0 into w1 T23 Compares x2 = 7 and x3 = 4 Writes 0 into w3
After this step, w0, w1 and w3 are set to zero, and w2 is still 1. Therefore, in Step 3, the thread associated with w2 sees a 1 and outputs the value of x2, which is 7. Thus, the maximum is 7.
2
Input and Output
Input and Output:
The input to your program should be taken from command line arguments. Your executable must be named as prog1. The command line looks like the following:
java prog1 n x0 x1 ... xn-1
It starts with the name of your executable prog1, followed by an integer n, followed by that number of distinct integers. You can assume the value of n is in the range of 3 and 10 and all input values are correct so that you do not have to do error checking.
Here is what should be shown by your program:
The values of array w after the initialization step. The activity performed by thread Tij in Step 2. The values of array w after Step 2. The maximum and its location.
Suppose the command line is java prog1 4 3 1 7 4 Then, you program's output should look like the following: Number of input values = 4 Input values x = 3 1 7 4 After initialization w = 1 1 1 1 .......... Thread T(1,3) compares x[1] = 1 and x[3] = 4, and writes 0 into w[1] .......... After Step 2 w = 0 0 1 0 Maximum = 7 Location = 2
Problem 2: Print sequence of characters abc
Write a Java program that uses three threads to print abc. One thread should print just one of the characters: a, b, or c. You should control the threads so that the program prints a first, then b, last c, and then repeat this sequence, until the running of the program is terminated.
For example, your thread 0 prints a, thread 1 prints b, and thread 2 prints c. You should synchronize the three threads so that thread 0 prints first, thread 1 prints next, thread 2 prints last, and repeat the sequence.
The output should be: abcabcabcabcabc……
Note: The sequence may repeat infinitely, or for a certain number of times. You should create only 3 threads in the entire process to achieve the print task (all the threads are at either runnable or blocked state after they are created and before terminated).
This assignment includes two problems that implement Java Threads.
Problem 1: Finding the Maximum Fast!
The usual way to find the maximum of a set of integers is as the following:
max = x[0]; for (i = 1; i < n; i++) if (x[i] max) max = x[i]; This is based on the fact that you have only one CPU and use n - 1 comparisons to find the maximum. But if we have multiple CPUs, we can find the maximum faster:
Let us use a thread to simulate a CPU. Suppose we have n distinct integers x0, x1, ..., xn-1. We first initialize a working array of n entries, say w, to all 1s. This can be done with n threads, each of which writes a 1 into its corresponding entry. More precisely, thread Ti writes 1 into wi. Since each thread (or CPU if you prefer) takes one step to complete its task and since all threads run concurrently, the initialization step only needs one step. After this initialization step, two more steps are required.
Step 2: For each pair of integers xi and xj, we create a thread (or a CPU if you prefer) Tij. This thread compares xi and xj, and writes a 0 into wi if xi < xj. Otherwise, it writes a 0 into wj. Therefore, in this step, we need n(n-1)/2 threads, each of which executes one compare and one write.
Step 3: This step requires n threads. The i-th thread checks the value of wi. If it is a 0, this thread does nothing. If it is a 1, this threads displays the value of xi because it is the maximum! It also requires one step to output the maximum.
Thus, if we have n(n-1)/2 threads, it only takes three comparison steps to find the maximum!
Example
Consider the following example. Suppose we have 4 numbers, x0 = 3, x1 = 1, x2 = 7, x3 = 4. Array w is initialized to 1, 1, 1, 1 (i.e., w0 = w1 = w2 = w3 = 1). In Step 2, we need 4×(4-1)/2= 6 threads:
Thread Name Its Comparison Output T01 Compares x0 = 3 and x1 = 1 Writes 0 into w1 T02 Compares x0 = 3 and x2 = 7 Writes 0 into w0 T03 Compares x0 = 3 and x3 = 4 Writes 0 into w0 T12 Compares x1 = 1 and x2 = 7 Writes 0 into w1 T13 Compares x1 = 1 and x3 = 4 Writes 0 into w1 T23 Compares x2 = 7 and x3 = 4 Writes 0 into w3
After this step, w0, w1 and w3 are set to zero, and w2 is still 1. Therefore, in Step 3, the thread associated with w2 sees a 1 and outputs the value of x2, which is 7. Thus, the maximum is 7.
2
Input and Output
Input and Output:
The input to your program should be taken from command line arguments. Your executable must be named as prog1. The command line looks like the following:
java prog1 n x0 x1 ... xn-1
It starts with the name of your executable prog1, followed by an integer n, followed by that number of distinct integers. You can assume the value of n is in the range of 3 and 10 and all input values are correct so that you do not have to do error checking.
Here is what should be shown by your program:
The values of array w after the initialization step. The activity performed by thread Tij in Step 2. The values of array w after Step 2. The maximum and its location.
Suppose the command line is java prog1 4 3 1 7 4 Then, you program's output should look like the following: Number of input values = 4 Input values x = 3 1 7 4 After initialization w = 1 1 1 1 .......... Thread T(1,3) compares x[1] = 1 and x[3] = 4, and writes 0 into w[1] .......... After Step 2 w = 0 0 1 0 Maximum = 7 Location = 2
Problem 2: Print sequence of characters abc
Write a Java program that uses three threads to print abc. One thread should print just one of the characters: a, b, or c. You should control the threads so that the program prints a first, then b, last c, and then repeat this sequence, until the running of the program is terminated.
For example, your thread 0 prints a, thread 1 prints b, and thread 2 prints c. You should synchronize the three threads so that thread 0 prints first, thread 1 prints next, thread 2 prints last, and repeat the sequence.
The output should be: abcabcabcabcabc……
Note: The sequence may repeat infinitely, or for a certain number of times. You should create only 3 threads in the entire process to achieve the print task (all the threads are at either runnable or blocked state after they are created and before terminated).
1 file (220.7KB)
