For this homework, you will modify the work queue implementation such that it tracks and waits for pending (unfinished) work, eliminating the need for a "task manager" class. Then, your code should use this work queue to find prime values.

Motivation

Your search engine project will allow for multithreaded building and searching of your inverted index data structure. Rather than create new thread instances for each task, it must use a thread pool and work queue to manage threads.

The work queue class modified in this homework can be used directly in the multithreading project. The approach to finding primes using that work queue might be similar to how the work queue will be used in your project as well.

Benchmarking

This homework bundle includes benchmarking code. When benchmarking, keep in mind:

• Runtimes vary significantly by system and even between runs on the same system.
• Benchmarking in Java is especially difficult due to optimizations made by the JVM while your code runs.
• The GitHub Actions virtual environment only includes 2 cores, limiting the speedups possible from multithreading.

Your code might not pass the first try on GitHub Actions.

It is okay if it takes a few tries as long as it passes with a decent speedup (between x1.3 and x1.8 times faster). It it takes more tries and barely has a speedup, then there is still likely a performance issue with your approach.

<aside> <img src="/icons/info-alternate_gray.svg" alt="/icons/info-alternate_gray.svg" width="40px" /> Always check if there are any incidents with GitHub Actions when your tests fail. Sometimes they are experiencing degraded performance, which could impact the tests.

</aside>

Hints

Below are some hints that may help with this homework assignment:

• Add a pending variable to the WorkQueue class to track unfinished work and implement the finish() method to wait until there is no more pending work.
• There should not be a pending variable or TaskManager nested class in the PrimeFinder class! You will need to create an inner "task" or "work" class, however.
• Implement the multithreaded findPrimes(int, int, int) method in PrimeFinder using your modified WorkQueue class. There should be 1 task or Runnable object for each number being tested and the run() method of these objects should use the isPrime(int) method.
• Be wary about using lambda expressions or streams for your initial approach.
• The Javadoc for the test methods tries to provide hints on why a specific test might fail.