Parallel Sort Screenshot Collection

Last updated on 11-10-29.

Description. The source for this application can be found in our reference collection.

Stage 1

1. Stage 1

All sorter threads have been created, the synchronization mechanism is configured to coordinate the start and termination of all threads using two CountDownLatch objects-- one with a count of 1, to synchronize the start of all threads, and one with a count of 5, to synchronize the termination of all threads. The threads are waiting for the start signal.

Stage 2

2. Stage 2

The start method is about to decrement the start CountDownLatch. Within this method, the main thread waits for the termination CountDownLatch, which is released only when all sort threads decrement the termination CountDownLatch.

Stage 3

3. Stage 3

All sorting threads running .

Stage 4

4. Stage 4

The Quick Sort thread is notifying its termination to its listeners and is about to decrement the termination CountDownLatch.

Stage 5

5. Stage 5

The Merge Sort thread is notifying its termination to its listeners and is about to decrement the termination CountDownLatch.

Stage 6

6. Stage 6

The Selection Sort thread is notifying its termination to its listeners and is about to decrement the termination CountDownLatch.

Stage 7

7. Stage 7

The Insertion Sort thread is notifying its termination to its listeners and is about to decrement the termination CountDownLatch.

Stage 8

8. Stage 8

The Bubble Sort thread is notifying its termination to its listeners and is about to decrement the termination CountDownLatch.

Stage 9

9. Stage 9

The start method is about to complete, after waiting on the termination CountDownLatch.

Stage 10

10. Stage 10

The main method is about to complete, after waiting for start to complete.

Stage 11

11. Stage 11

The final state of the application after execution completes.

Bug

12. Incorrect Termination

The diagram above shows the final state of the execution of an earlier, buggy version of the parallel sorting application. Notice that the main thread terminated before the Bubble Sort thread could notify its termination to its listeners (this happens in the done method). As a result, the Bubble Sort thread does not terminate properly and some outstanding method calls never have the chance complete successfully. The visualization of the final state was essential in solving the bug-- after inspecting the code, we observed that notification to the listeners was happening outside the region synchronized by the CountDownLatch. Hence, the following thread interleaving would explain the diagram above: the last thread completes its sorting routine and decrements the CountDownLatch, the main thread is released and completes, forcing the last thread to terminate abnormally with any number of outstanding method calls. After identifying the bug visually, it was straightforward to fix the problem, pushing the listener notification code so that it executes before the CountDownLatch is decremented.