Homework #2

Due Date: Friday, February 4, 2000 at 11:59PM
Points: 80 regular, 10 extra credit

Short-Answer Questions

These can be answered in a sentence or two, and are intended to reinforce important points.

1. (6 points) What are the three basic components of a system nucleus? What does each do?
2. (6 points) What are the three conditions any solution to the critical section problem must meet?
3. (6 points) Justify the statement "if the semaphore operations up and down are not executed atomically, then mutual exclusion may be violated when using them to solve the critical section problem."

Long-Answer Questions

These questions require some thought and longer answers than the short-answer questions. They are intended to have you use the concepts discussed in class, to be sure you understand them and can work with them.

4. (25 points) Two processes p₀ and p₁ share the following variables:

    1. var flag: array[0..1] of boolean; (* initially false *)
    2.     turn: 0..1;
   

   The algorithm below is for process p_i (i = 0 or i = 1) with p_j (j = 1 or j = 0) being the other process.

    3. repeat
    4.     flag[i] := true;
    5.     while turn <> i do begin
    6.         while flag[j] do (* nothing *);
    7.         turn := i;
    8.     end;
    9.     (* critical section *)
   10.     flag[i] := false;
   11.     (* remainder section *)
   12. until false;
   

   Does this algorithm correctly implement critical sections? Either prove that it does, or prove that at least one condition is not met
5. (12 points) Consider the implementation of monitors by semaphores (see the handout Monitors and Semaphores). Under each of the following assumptions the code implementing the monitor may be simplified. Show the new code in each case:
   1. The monitor contains no wait or signal operations.
   2. The use of signal is restricted such that it may occur only as the last instruction of any monitor.
6. (25 points) (The Model Builders' Problem) Consider a system with three model airplane building processes and one agent process. Each building process requires a tube of glue, a piece of newspaper, and a model kit to put a model airplane together. One of the processes has tubes of glue, another pieces of newspaper, and the third model kits. The agent has an infinite supply of all three. The agent places two of the ingredients for the model builders on the table. The process who has the remaining ingredient can then build one model airplane. It signals the agent upon completion. The agent then puts out another two of the three ingredients and the cycle repeats. Write a program to synchronize the agent and the model building processes using monitors.

Extra Credit

7. (10 points) Consider a computer that does not have a TEST AND SET LOCK instruction but does have an instruction to swap the contents of a register and a memory word in a single indivisible action. Can that be used to write a routine enter_region such as the one found in Fig. 2-10? (text, chapter 2, problem 9)