More Java Threads
Operating Systems Lab Class 4
In this lab session we will get hands on the basics of thread programming in Java. You will learn how to create threads and how to wait for them to terminate. We will also exploit the data parallelism pattern to speed up the processing of input data.
1 Sorting
We are going to write a program that sorts lists of numbers or strings as shown below. The program should first divide the input list into two halves. Each half will be sorted by a thread. Then, as soon as they have finished, the resulting lists will be passed to a thread that merges them.
1.1 Getting Started
Start by reading the Sorting Task Examples in Appendix 1.
1. Download the os-lab4.zip archive from Canvas and unzip it into your workspace.
2. Start NetBeans and open the project. The project should contain three files in the src directory: Sorting.java, SortTask.java and MergeTask.java.
3. Compile and run the code. This should work without problems.
1
1.2 Implementation
4. Complete the three Java classes. The program will work as follows:
• The program takes a list of integers and sorts them in ascending order. E.g. running java
Sorting 27 12 3 should output 3
12
27
• If there are non-integer arguments the program should print a usage message and exit.
• As explained above the list will be sorted by a two stage pipeline. We want to keep this pipeline generic, i.e. SortTask and MergeTask should work with lists of Integer as well as with lists of String or any other type without having to change their code. This can be implemented uniformly by using lists (or arrays) of objects that implement the
Java.lang.Comparable interface.
E.g. Integer does implement this interface and therefore provides a compareTo method that can be used for sorting, such as in java.util.Collections.sort()
and java.util.Arrays.sort()
• The main method is responsible for parsing the command line arguments, creating and coordinating the threads as well as producing the output.
• You are not allowed to use java.util.Collections.sort() in MergeTask (why?). 1.3 Reflection
5. Discuss the advantages of this multithreaded sorting algorithm in comparison with a purely sequential one. What is the complexity of the operatons involved? Quantify the gain in per- formance assuming that both sorting threads can run in parallel. What would be the gain in performance if we used a sorting algorithm for the merge operation?
6. How can the above algorithm be further improved?
7. Extra question: Extend the program to splitting the list into N parts (with N being a power of 2) and then merging the resulting lists in several stages. E.g. split the list into four parts each of which will be sorted, resulting in four result lists. Then two of them will be merged, resulting in two result lists. Finally, the latter two will be merged to obtain the final result.
2 Java Thread Library API References
http://docs.oracle.com/javase/8/docs/api/java/lang/Runnable.html
http://docs.oracle.com/javase/8/docs/api/java/lang/Thread.html
http://docs.oracle.com/javase/8/docs/api/java/lang/Comparable.html
http://docs.oracle.com/javase/8/docs/api/java/util/Collections.html
http://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html
http://docs.oracle.com/javase/8/docs/api/java/lang/Integer.html
Appendix 1
Download and run sortingTaskExamples project from Study Direct.