For his 2020 New Years resolution, Larry Candlepin wants to bowl a perfect 300. However, it's already April, and Larry can barely bowl a 90 on a good day. Thankfully, you tell him about a strategy that can make his training more efficient -- he can clone himself and bowl on every lane of the alley! This genious multithreading strategy can help Larry get in all the practice he needs to improve his bowling skills by the end of the year! But first, he needs you to teach him how to multithread so he can acheive his dream of becoming a bowling star!
In this lab you will learn the basics of threading in Java. Java has a lot of threading tools, and you should look at the java.util.concurrent and java.util.concurrent.atomic packages if you want to learn more.
This lab has two parts: Counting Primes and conceptual KD-Tree Search. For this lab, we will be working on a code base separate from the Autocorrect project. You can get access to the stencil code here.
Part 1: Counting Primes
For this part of the lab, you are going to count the number of
primes less than some number n. In the stencil,
you have access to the PrimeCalculator class, which has an
isPrime(int num) method that tests if a number is prime.
PrimeCalculator.isPrime(5) will return
You don't have to worry about how it's implemented. One important thing to
note is that this implementation considers 1 to be prime.
A Working Solution
Take a look at the Main.java class. It is currently mostly empty. The
MAX_NUMBER_TO_TEST field is set to 8,000,000. We want to find the number of primes less than
this number. The prime-number theorem in
mathematics states that the number of prime numbers less than n is approximately n/log n. For
what it's worth, the correct answer for our case is 539,778 (including 1).
Read the TODO:[Part 1] statement and fill in the appropriate code. You do not need threads for this part. When you have finished, run the program and make note of the number of primes that is printed out as well as how long it took. Verify that the resulting number of primes is correct.
Improving the Solution
You've probably realized that if you really want to verify the approximation, you'll need a much large value for
MAX_NUMBER_TO_TEST. But even with the current value, it still takes a long time to count the number
of primes. How can we make this program run faster?
One way to improve the runtime is to distribute the work of counting primes to many separate processes, known as threads. Each thread runs independently and concurrently, which means that more operations can be done in the same amount of time.
There are two TODO:[Part 2] blocks for you to fill out, one in Main.java and one in PrimeCalcThread.java. You should probably do the latter first. Once you are done, run the program. You should notice that it takes a lot less time to count all the primes.
Note: When you start running a thread, you want to start it by running the
start() method (e.g.
thread.start();), not the
run() method. If you run the method by calling
run(), it will run that method in the main thread. However, if you run the thread with
start(), it will run the
run() method on a separate thread. To join the threads, you
want to call the
join() method from the main thread (e.g.
thread.join();). This will
ensure that the main thread will wait until all the threads that have been joined are done, before continuing
the program. Once you start all the threads, you will then want to join them and output the value of the counter.
(Thread) Safety First
Though you have made your program a lot faster, there is a problem. If you run the program multiple times, you
will notice that the final number you get will change every time and will not be equal to the number you got in
non-threaded solution. The reason for this is because when multiple threads call the
increment() method in
IntWrapper, the value might not get actually incremented correctly. This is an example of a concurrency
issue, where concurrently modifying a field causes indeterminate behaviour. In our case the only issue is that
the output value is wrong, but if you were using threads to concurrently modify more complex objects, your
program could crash.
In order to solve this, you can use Java's
synchronized keyword, which you can read about here. There is a
simple way to modify IntegerWrapper to make
increment() synchronized and you should do this
for TODO:[Part 3]. Once you make this small change, your part 1 and part 2 solutions should
output te same values.
We will now try another threaded solution that instead of dividing the bounds of search for each thread,
we will have each thread increment a single primality counter. This can be done using Java's
module. There are two TODO:[Part 4] blocks for you to fill out, one in Main.java and one in
DistributionThread.java. The four different DistributionThreads should each be incrementing a single shared AtomicInteger
(the current value being tested for primality) and IntWrapper (the counter for the number of primes so far).
If you get the same output consistently for all the TODOs, you've finished the coding portion of the lab! Please show a TA the changes you've made to get checked off.
Part 2: Conceptual KD-Tree Search
Think about the following conceptual question and prepare an answer to give to your TA for checkoff:
If you have a very large dataset of n-dimensional points, how could you multithread the construction of a KDTree to make it more efficient?