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