Problem Set 3

Assigned: Feb. 12
Due: Feb. 19

Problem 1

In the solution to the "Producer-consumer" problem in the notes to lecture 5, the operations on the buffer are surrounded by "DOWN(b) ... UP(b)" The notes explain the necessity of this by saying "We assume the buffer itself is only serially accessible", but don't explain why one would assume that.

Suppose that the buffer is in fact a stack, which is defined in C as the following data structure

const BUFSIZE 1024

struct buffer {
   int data[BUFSIZE],
       pointer;
}

struct buffer buf1;
with the two operations "push" and "pop":
void push(X)
int X;

{ buf1.data[buf1.pointer] = X; 
  buf1.pointer++;
}

int pop()
{ buf1.pointer--;
  return(buf1.data[buf1.pointer]);
}

(I omit checking for errors.)

Show how a race condition can occur if mutual exclusion is not enforced on the buffer operations. Assume that buf1 resides in shared memory that all processes can access.

Problem 2

Tanenbaum chap 3 problem 18 (p. 187)