URL to the prompt since the formatting looks horrible.

https://henricasanova.github.io/ics332_spring2018/morea/Threads/experience-threads.html

Exercise #1: Multi-threading for Speed [30 pts] Overview You are hired by a company and tasked with setting up a driving directions app in Java. Like Google Map, the idea is to pre-compute a bunch of all-pair-shortest-paths so that user queries can be answered quickly. The concern is that the compute time will be problematic because, as you know from ICS311, the Floyd-Warshall algorithm has complexity O(n3) for a graph with n vertices.

Apparently, youre the only one who knows how to use threads in Java (side note: in real life this should not happen). The goal is to multi-thread the application to see how much faster it can run.

This exercise corresponds to the simplest possible more speed with threads scenario.

Question #1 [2 pts] You are given two Java source files that form a package called paths:

ComputePaths.java: the main class, which runs Floyd-Warshall on 2520 random graphs

ComputePaths.java

package paths;

public class ComputePaths {

public void compute(int graph_size, int num_threads) {

for (long i = 0; i < 2520; i++) { new FloydWarshall(graph_size, i).floydWarshall(); }

}

public static void main(String[] args) {

if (args.length != 2) { System.err.println("Usage: java ComputePaths <# threads>"); System.exit(1); }

int graph_size = 0; int num_threads = 0; try { graph_size = Integer.parseInt(args[0]); num_threads = Integer.parseInt(args[1]); if ((graph_size <= 0) || (num_threads < 1)) { throw new NumberFormatException(); } } catch (NumberFormatException e) { System.err.println("Invalid command-line arguments"); System.exit(1); }

double now = System.currentTimeMillis();

new ComputePaths().compute(graph_size, num_threads);

System.out.println("All graphs computed in " + (System.currentTimeMillis() - now) / 1000 + " seconds");

}

}

FloydWarshall.java: an implementation of the Floyd-Warshall algorithm that prints the sum of all shortest path lengths

package paths;

/* * The Floyd-Warshall algorithm is used to find the shortest path between * all pairs of nodes. * * The running time of the algorithm is O(n^3), being n the number of nodes in * the graph. * * This implementation is self contained and has no external dependencies. It * does not try to be a model of good Java OOP, but a simple self contained * implementation of the algorithm. */

import java.util.Arrays; import java.util.Random;

public class FloydWarshall {

// graph represented by an adjacency matrix private double[][] graph;

private long seed;

public FloydWarshall(int n, long seed) { this.graph = new double[n][n]; this.seed = seed; initGraph(seed); }

private void initGraph(long seed) { Random rng = new Random(seed); for (int i = 0; i < graph.length; i++) { for (int j = 0; j < graph.length; j++) { if (rng.nextFloat() < 1.0 / (10 + 10 * seed)) { graph[i][j] = Double.POSITIVE_INFINITY; } else { graph[i][j] = 1 + seed / 2520.0; } } } }

// average all-pairs shortest path public void floydWarshall() { double[][] distances; int n = this.graph.length; distances = Arrays.copyOf(this.graph, n);

for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { distances[i][j] = Math.min(distances[i][j], distances[i][k] + distances[k][j]); } } }

double average_distance = 0; for (int i=0; i < n; i++) { for (int j=0; j < n; j++) { average_distance += distances[i][j]; } } System.out.println("Ran Floyd-Warshall on Graph #" + String.format("%1$4s", this.seed) +": " + (int)average_distance); }

}

Download these files to a directory called paths, and you can compile and run from the command-line as follows (or use whatever IDE, etc.):

% ls -R paths

./paths: ComputePaths.java FloydWarshall.java

% javac paths/*.java

% java paths.ComputePaths Usage: java ComputePaths <# threads> The program requires two command-line arguments:

a graph size: how big should the random graphs be a number of threads: how many threads should be used (this argument is ignored in the code provided to you) Running the program for graphs with 250 vertices (and passing 1 for the number of threads, which is ignored anyway) produces this output on my laptop:

% java paths/ComputePaths 250 1 Ran Floyd-Warshall on Graph # 0: 58187 Ran Floyd-Warshall on Graph # 1: 55577 Ran Floyd-Warshall on Graph # 2: 54699 [...] Ran Floyd-Warshall on Graph #2518: 105764 Ran Floyd-Warshall on Graph #2519: 105785 All graphs computed in 59.627 seconds

By trial-and-error (i.e., doing a human-driven binary search), determine the graph size that leads this code to run in between 25 and 30 seconds on your machine. Note that repeated runs will show some variation.

In your report (README.txt) simply state what value you found for the graph size. Use this value for all subsequent questions.

Warning: You should run your code on a quiescent system, i.e., without running any other applications at the same time.

Question #2 [20 pts] Enhance ComputePaths.java so that it uses the specified number of threads. The idea is to split up the work among threads. For instance, when using 2 threads each thread should compute 2520/2 = 2260 graphs; using 3 threads, each thread should compute 2520/3 = 840 graphs; etc. Note that I picked 2520 because it is divisible by 1, 2, 3, , 10.

For instance, on my laptop, repeating the run from the previous question but specifying 2 threads, the output from the enhanced program looks like:

% java paths/ComputePaths 250 2 Ran Floyd-Warshall on Graph #1260: 79359 Ran Floyd-Warshall on Graph # 0: 58187 Ran Floyd-Warshall on Graph # 1: 55577 [...] Ran Floyd-Warshall on Graph #2518: 105764 Ran Floyd-Warshall on Graph #2519: 105785 All graphs computed in 29.967 seconds You should observe that using 2 threads your program goes faster. If not, you most likely have a bug. Make sure your program uses the number of threads thats specified.

Hints:

The Ran Floyd-Warshall messages will appear out of order, which is fine Of course you should create a thread class. I suggest a class called Worker thats nested in class ComputePaths and that implements the Runnable interface. Using an array of threads is a good idea Because 2520 is divisible by all integers up to and including 10, and because we wont run this code with more than 10 threads, its absolutely trivial to divide up the work among the threads. The only method you have to modify in the ComputePaths class is compute(). Your code should still work if one specifies 1 thread (and use only only thread).

Question #3 [8 pts] Run your code for 1, 2, 3, , 10 threads. For each number of threads, run your code 5 times and compute the average execution time. In your report (README.txt) list the average execution time for each number of threads. Then answer the following quick questions:

q1: How much faster does the program run with 2 threads when compared to using 1 thread? (e.g., 1.95x faster) q2: How many physical cores do you have on your machine? q3: Is using more threads than the number of physical cores useful on your machine? q4: What is the largest acceleration factor you observe in your results when compared to the 1-thread case?

Exercise #2: Multi-threading for Interactivity [30 pts] Overview You get hired by a company that does a lot of Java development in Linux environments. Many applications being developed there need a file system watcher feature: something that will give them a callback whenever a file is created in some directory. You get tasked with implementing a FSWatcher class that provides that feature.

Disclaimer: As you might expect, Java already has something like this. Its in the java.nio package. Its really difficult to come up with an original systems idea, and when one does, one doesnt waste it on a programming assignment for a course but instead make money :) So, we are pretending java.nio (which is a wonderful package) does not provide this feature.

Question #0 [0 pts] Of course you dont want to implement all that file system watching stuff in Java directly because its a lot of work. Instead, you happen to know that there is a Linux package called inotify-tools that provides a program called inotifywait that does what you need!

Install the inotify-tools package as follows:

% sudo apt install inotify-tools Now, test inotifywait with the following command:

% inotifywait -e create -m /tmp/ Setting up watches. Watches established. The above command will not return (i.e., you wont get the prompt back), but it will print some message each time a new file is created in directory /tmp/. Lets test this. In another terminal/shell just create a file in /tmp/, for instance by doing touch /tmp/whatever. You should now see one output line from the inotifywait command:

% inotifywait -e create -m /tmp/ Setting up watches. Watches established. /tmp/ CREATE whatever This line of output from inotifywait says that in /tmp/ a file names whatever was created!

Make sure you have all the above working on your system before you proceed to the next question.

Question #1 [15 pts] You are provided a use-case (which you should not modify) for this question: FSWatcherUseCaseQ1.java

package fswatcher;

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.nio.file.Files; import java.nio.file.Paths; import java.util.ArrayList;

public class FSWatcherUseCaseQ1 {

private ArrayList watchers; private FSWatcherQ1 fswatcher;

FSWatcherUseCaseQ1() { this.watchers = new ArrayList<>(); this.fswatcher = new FSWatcherQ1(); }

private void go() {

while (true) { switch (getMenuChoice()) { case 1: { String dir = getPath(); if (!Files.isDirectory(Paths.get(dir))) { System.err.println(dir + ": invalid directory"); break; } addDirWatcher(dir); break; } } } }

private String getPath() { System.out.print("Enter a directory path: "); BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); String line = ""; try { line = reader.readLine(); } catch (IOException e) { System.exit(1); } return line; }

private void addDirWatcher(String dir) { this.watchers.add(dir); this.fswatcher.watch(dir, (s) -> { System.out.println("New file in directory " + dir + ": " + s.split(" ")[2]); }); // printMenuChoices(); }

private static void printMenuChoices() { System.out.println(); System.out.println("1. Watch a directory"); System.out.println();

}

private int getMenuChoice() {

while (true) { printMenuChoices(); InputStreamReader reader = new InputStreamReader(System.in);

try { int input = reader.read() - '0'; if ((input >= 1) && (input <= 1)) { return input; } } catch (IOException e) { System.err.println("I/O Error while reading from keyboard"); System.exit(1); } } }

public static void main(String[] args) { new FSWatcherUseCaseQ1().go(); } }

This class contains a main() method, and is in package fswatcher. It expects another class in that package, FSWatcherQ1, which you are to implement (in source file FSWatcherQ1.java).

The FSWatcherQ1 class should just have single method called watch() with the following signature:

public void watch(String dirname, Consumer method); The first parameter is the path of a directory that should be watched (e.g., /tmp/). The second parameter is a lambda expression (welcome to Java 8): an anonymous method that takes a string as input. The watch() should:

Start a process (external to the JVM) that runs inotifywait -e create -m dirname (where dirname is the first argument passed to the watch() method) Read output lines from that process, and for each line invoke the lambda expression passing it the line Once implemented, you can run FSWatcherUseCaseQ1:

% java fswatcher/FSWatcherUseCaseQ1 This is an interactive application, which was demoed in class while going over the assignment and is pretty self explanatory. Use CTRL+C to terminate the application.

Doing the above likely involves things youve never done in Java, so below are two brief tutorials.

Tutorial #1: Calling a lambda expression Your method needs to call the lambda expression passed to it (the method parameter). Without getting into any details, assuming the string you want to pass to method is stored in variable line, you would invoke method as:

method.accept(line); Thats it. So, whenever you get a line produced by inotifywait, just do the above. See the large Java documentation about lambdas for all wonderful details.

Tutorial #2: Creating an external process from the JVM It turns out that Java can create a process in a fork-exec fashion. This is done with something called ProcessBuilder. You can of course find tons of tutorial information on-line for this. Instead of duplicating this here, I am simply showing a small example:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 String[] tokens = ("ls -la /tmp/").split("[ \t ]+"); Process p = null; ProcessBuilder pb = new ProcessBuilder(tokens);

try { p = pb.start(); } catch (IOException e) { System.err.println(e.getMessage()); System.exit(1); }

InputStream sstdout = p.getInputStream(); BufferedReader stdout = new BufferedReader(new InputStreamReader(sstdout));

String output_line; while (true) { output_line = stdout.readLine(); if (output_line == null) { break; } else { System.out.println("Got some output from the ls command: " + output_line); } } At line 1, we create an array of strings based on a command-line string. In this example we want to run ls -la /tmp/ (which lists files in /tmp/), and we simply build array [ls, -la, /tmp/].

At line 3 we create a ProcessBuilder object for the command-line, which we start at line 6 (catching an exception if there is an error). This produced a Process object.

At line 12 we get an input stream based on the external process output (i.e., the output of the process is input to us).

The loop at line 15 just gets output from the ls process and prints then out.

So this is just like fork-exec, but in Java!

Question #2 [15 pts] The implementation in the previous question is really, really weak because we can only watch a single directory. That is, we dont get control back at all. The objective now is to enhance your implementation, in a new class called FSWatcherQ2 to avoid this problem.

The way to do this is to use a thread to do the getting lines from inotifywait loop. In other terms, your watch() method does:

Creates the inotifywait process using ProcessBuilder Spawn a thread that will do the while loop Return You are provided with a use-case: FSWatcherUseCaseQ2.java

package fswatcher;

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.nio.file.Files; import java.nio.file.Paths; import java.util.ArrayList;

public class FSWatcherUseCaseQ2 {

private ArrayList watchers; private FSWatcherQ2 fswatcher;

FSWatcherUseCaseQ2() { this.watchers = new ArrayList<>(); this.fswatcher = new FSWatcherQ2(); }

private void go() {

while (true) { switch (getMenuChoice()) { case 1: { String dir = getPath(); if (!Files.isDirectory(Paths.get(dir))) { System.err.println(dir + ": invalid directory"); break; } addDirWatcher(dir); break; } case 2: { for (String dir : this.watchers) { System.out.println("---> " + dir); } break; } } } }

private String getPath() { System.out.print("Enter a directory path: "); BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); String line = ""; try { line = reader.readLine(); } catch (IOException e) { System.exit(1); } return line; }

private void addDirWatcher(String dir) { this.watchers.add(dir); this.fswatcher.watch(dir, (s) -> { System.out.println("New file in directory " + dir + ": " + s.split(" ")[2]); }); // printMenuChoices(); }

private static void printMenuChoices() { System.out.println(); System.out.println("1. Watch a directory"); System.out.println("2. List of watched directories"); System.out.println();

}

private int getMenuChoice() {

while (true) { printMenuChoices(); InputStreamReader reader = new InputStreamReader(System.in);

try { int input = reader.read() - '0'; if ((input >= 1) && (input <= 2)) { return input; } } catch (IOException e) { System.err.println("I/O Error while reading from keyboard"); System.exit(1); } } }

public static void main(String[] args) { new FSWatcherUseCaseQ2().go(); } }

The use-case is pretty self-explanatory and was demoed in class when going over the assignment. Use CTRL+C to terminate the application.