Homework 3

22C:116, Fall 1999

Due Friday Sept 10, 1999, in class

1. Background Consider the following written to run under the example thread manager:

   void may()
   /* each call to this function might relinquish */
   {
   	if (random() & 7) thread_relinquish();
   }
   
   int a[SIZE];
   
   void sorter_thread( int n )
   {
   	int n1 = n + 1;
   	while (1) {
   		may();
   		if (a[n] > a[n1]) {
   			int t;
   			may();
   			t = a[n];
   			may();
   			a[n] = a[n1];
   			may();
   			a[n1] = t;
   			may();
   		}
   	}
   }
   
   int main()
   {
           thread_manager_init();
   	{
   		int i;
   		for (i = 0; i < (SIZE-1); i++)
   			thread_launch( 4000, sorter_thread, i );
   	}
           thread_manager_start();
           /* control never reaches this point */
   }
   

   The above program is incomplete, but it represents an idea for a parallel sort algorithm, using SIZE-1 processes to sort an array of SIZE elements. The function may() is inserted between each pair of consecutive statements in the program in order to simulate the nondeterminism that would be expected on a real multiprocessor.

   Many details are omitted, for example, reading values into the array a and program termination!

   Part A: This program contains a major error. If the array A initially contains SIZE distinct values randomly arranged in its cells, as the sorter threads operate, it is possible for values to be lost, so that, in the end, the array contains multiple copies of one or more value and fewer than SIZE distinct values. Explain how this is possible.

   Part B: We could simply eliminate some of the calls to may() in order to eliminate the problem you identified in part a. Show the code for the sorter_thread incorporating this solution. Preserve as many calls to may() as possible in this version of your solution!

   Note: This solution to the problem reduces the potential for parallelism, and as such, it may not be desirable. Of course, this entire approach to sorting is not desirable!

   Part C: Semaphores may be used to ensure mutual exclusion for shared resources. Give a solution to the you problem identified in part a that uses semaphores and that maximizes the potential for parallelism in this program.

   Note: No part of this assignment requires that you actually compile or run your program!

2. Background In most modern programming environments for languages like Ada, Pascal, C, C++ or Java, the heap manager used to allocate applications-level data structures allocates these structures from a heap that is itself composed of many pages, stored in contiguous virtual addresses within the program's data segment.

   Part A: Conside the following two choices: First, a boundary tag heap manager that searches the heap starting from the start whenever it needs a free block, and second, the same heap manager, but always searching from the point where it most recently made an allocation. Which would give fewer page faults in a virtual memory environment?

   Part B: In general, what is the relationship between fragmentation in the heap and the rate at which the application program suffers page faults. Consider, for the purposes of this problem, holding the application program fixed and varying the heap manager in order to control the degree of fragmentation.