Computer Science 338 - Homework/Lab 3
due: 9:55 AM, Thursday, September 28, 2000

1.

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

2.

Andrews, Exercise 3.3(a)

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?

• 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);
  

4.

Andrews, Exercise 3.12

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?

• Shared data, initialized to 0's and false

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

• Process P_i

  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 */
  
  }