Homework 3
due Tuesday, October 1, 2002, 12:01 AM

Turn in your source code for the first question (interleaving.c). Your answers to the other questions should be submitted as a plain text file hw03.txt, a postscript file hw03.ps, or a PDF file hw03.pdf.

  1. Write a C program that will list all possible orderings of the machine instructions generated for the critical sections of the Producer-Consumer example from class. Recall that the statements counter++ and counter- actually generate machine code such as
    Producer Consumer
    P1 R0 = counter; C1 R1 = counter;
    P2 R0 = R0 + 1; C2 R1 = R1 - 1;
    P3 counter = R0; C3 counter = R1;

    Your program should list all possible interleavings of the statements P1, P2, P3, C1, C2, and C3. Also have your program print which interleavings produce a correct result (that counter has the same value it started with).

    Write your program in a file called interleaving.c. (8 points)

  2. Consider the Bakery Algorithm from class. Explain why the following is true:

    If Pi is in its critical section, and Pk (k != i) has already chosen number[k] != 0, then (number[i],i) < number[k],k).

    This does not need to be a formal proof, just a convincing explanation. (3 points)

  3. Tanenbaum, Exercise 6, p. 153. (1 point)
  4. Tanenbaum, Exercise 8, p. 153. (1 point)
  5. Tanenbaum, Exercise 11, p. 154. (1 point)
  6. Tanenbaum, Exercise 21, p. 154. (1 point)