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

1.

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