This is a semaphore programming assignment. Take your multithreaded unidirectional TSP Java program, the one that works backwards from right to left with a thread in each row, and use a barrier (implemented with semaphores) for synchronization instead of the nap() kludge. For each row in the matrix, create an independent thread that works backwards from column n to column 1, calculating the minimum path from that column forward (to the right), as we discussed in class. Use the barrier gate(j) method to force each thread to wait for all the other threads to finish their row computations before proceeding to the next row to the left.
A barrier is a synchronization object, like a semaphore. A barrier object can be created for a bunch of threads and used by them for synchronization and coordination, like a semaphore. The barrier class is actually implemented with semaphores. The basic idea is that the barrier blocks each of the threads until all of them have reached a certain point in their code, then they are all realeased after they have all gotten there. Each thread calls b.gate(j) when it reaches the ``barrier'' point in its code. Here b is a reference to the barrier object and i is the thread number or identifier (in your TSP program, the row number the thread is working on). After all threads have called gate(), they are all released. In other words, each thread is blocked at its gate() call until the last thread in the bunch finally calls gate(). Then they are all released to do more computation until they call gate() again.
If each thread is executing in its own object, probably the case in your TSP programs, then only create one barrier object, say in main(), and pass it to the constructors of the thread objects.
There is a one dimensional and a two dimensional constructor in the barrier class. Use the one dimensional one for this assignment since there is a thread for each row of the weight matrix.
Here is a two dinemsional example from Chapter 7 of the text.
Animate your program using XtangoAnimator.java. First do the base assignment as specified above and turn it in. Then do an animation of it as a separate program.