Homework 3 Sample Solutions
CS338, Fall 2000, Jim Teresco
Answers here gathered from student submissions where possible.

Graded out of 20 points

1. Log in to your account on the SGI Origin 2000 at NCSA. Run the MPI
   and pthread hello world programs. (0 points)


2. Andrews, Exercise 3.3(a) Suppose a computer has an atomic swap
   instruction, defined as follows:

   Swap(var1, var2) : 
     < tmp = var1; var1 = var2; var2 = tmp; >

   where tmp is an internal register.

  Using Swap, develop a solution to the critical section problem for n
  processes.  Do not worry about the eventual entry property.
  Describe clearly how your solution works and wht it is correct. (5 points)

1. boolean waiting[1:n], in[1:n] = ([n] false); in[1] = true;
2. process CS[i=1 to n] {
3. 	while(1) {
4. 		waiting[i]=true;
5. 		while (!in[i]) skip;
6. 		/* Critical Section */
7. 		int j=i;
8. 		while (!waiting[++j]);
9. 		swap(in[i], in[j]);
10.		waiting[i]=false;
	}
}

line 1 initializes variables and grants process 1 initial access to its
critical section.
line 4 asserts each processes desire to be chosen next
line 5 waits until that process is chosen
line 8 chooses the next process from those that are waiting
line 9 swaps the "in"s for those two processes, giving the next process
access to its critical section
line 10 asserts that process i is no longer waiting

this is correct because mutual exclusion is preserved (only one process is
ever granted access to its critical section)--after one process is finished
with its C.S. it "swaps" access rights with the next process which is
waiting.  thus, only one process is ever executing its C.S. since swap is
implemented as an atomic process.


3. In class, we looked at the algorithm below which implements a
   counting semaphore using a binary semaphore. What does the binary
   semaphore S3 do?  (5 points)

        Data structure includes: 

        binary_semaphore S1=1;
        binary_semaphore S2=0;
        binary_semaphore S3=1;
        int C=initial value of S;

        wait operation 

          wait(S3);
          wait(S1);
          C--;
          if (C < 0) {
            signal(S1);
            wait(S2);
          }
          else {
            signal(S1);
          }
          signal(S3);

        signal operation 

          wait(S1);
          C++;
          if (C <= 0) {
            signal(S2);
          }
          signal(S1);

S3 provides serialization.  It prevents a process which is leaving the
wait operation from coming right back around again before another
process would have a chance.  If S3 is a fair semaphore, the counting
semaphore we are implementing is also fair.

4. Andrews, Exercise 3.12 In the critical section protocols in the
   text, every process executes the same algorithm.  It is also
   possible to solve the problem using a coordinator process.  In
   particular, when a regular process CS[i] wants to enter its
   critical section, it tells the coordinator, then waits for the
   coordinator to grant permission. (5 points)

   (a) Develop protocols for the regular processes and the
   coordinator.  Do not worry about the eventual entry property.

   (b) Modify your answer to (a) so that it also ensures eventual entry.

Everyone answered (a) with an answer to (b).  Here's an example:

a)The coordinator has an outer loop which repeats forever:
	while (1)
	  do {
	     for (i = 1..n){
		if (arrive[i]==1) /*1 is true*/{
		arrive[i]=0;
		continue[i]=1;
		while (continue[i])
			spin wait for worker to finish what it's doing in the CS	
		}
	  }

   The worker:
	arrive[k] = 1; /* setting a request to enter the CS */
	while (!continue[k]){
	  spin wait;
	}
	/* enter CS */
	  do CS;
	/* exit CS*/
	continue[k] = 0; /* this will release the spin wait that the coordinator is doing */


5. In class, we looked at the Bakery Algorithm, shown below. What
   would happen is the choosing flags were eliminated? Which of the
   required properties of a solution to the critical section problem
   would this still satisfy? (5 points)

        Shared data, initialized to 0's and false 

        boolean choosing[n];
        int number[n];

        Process Pi 

        while (1) {
          choosing[i]=true;
          number[i]=max(number[0],number[i],...,number[n-1])+1;
          choosing[i]=false;
          for (j=0; j<n; j++) {
            while (choosing[j]);
            while ((number[j]!=0) &&
                   ((number[j],j) < (number[i],i)));

            /* critical section */

          number[i]=0;

            /* non-critical section */

        }

If the choosing flags are eliminated, a process may obtain a number
and assume no one else has gotten that same number.  Meanwhile,
another process may obtain that number and move along into the
critical section by the tiebreaker which uses the pid.