   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 Pi
```while (1) {
choosing[i]=true;
number[i]=max(number,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 */

}
```

Jim Teresco
2000-09-21