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*operationwait(S3); wait(S1); C--; if (C < 0) { signal(S1); wait(S2); } else { signal(S1); } signal(S3);

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

- Data structure includes:
- 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 */ }

- Shared data, initialized to 0's and false