Programming Lab
Synchronization with Semaphores

Look at the Java program Sorting.java that sorts an array by sorting its two halves seperately and then merges the results. Compile and run the program. Try to understand the algorithm.

The program has been prepared for concurrent execution by moving the sortings and the merge into classes to be instantiated by the sorting/merge-interval. Since only 10 numbers are sorted, thread preemption will not occur when executed on a mono-processor. Therefore, pauses have been inserted at various places in the code. These pauses will, with a certain probability, cause a thread switch. By this, a multi-processor execution of the threads is simulated.

1. Modify the program such that the two sortings are done concurrently, followed by the merge. Run the program.

2. Further modify the program such that the two sortings as well as the merge take place concurrently. Run the program several times and explain the results.

3. A class Semaphore.java is given, implementing general semaphores. A new semphore object initialized to n is created by: new Semaphore(n). On such a semaphore s, the usual operations can be applied: s.Down() and s.Up().

   Use semaphores to make the necessary thread synchronization. Run the program until you are sure it works.