CSE132 Practice Midterm Exam


  1. Model/View/Controller (15 points)

    Consider the class Die shown below, that represents a controller for a die.

    import java.util.Random;
    public class Die {
       final private Random rand;
       private int curValue;
       public Die() {
          rand = new Random();
          toss();
      }
    
      public int getValue() {
         return curValue;
      }
    
      public void toss() {
         curValue = rand.nextInt(6);
      }
    }
    
    Using classes already aware of model/view/controller (as we did in Week 1 and in Studio 1), show how you would modify Die to implement model/view/controller:
    1. What is the model, where is it instantiated, and how is it used in Die?
    2. Describe one or more reasonable views of the model.
    3. Describe the user interaction possibilities with the view. How can the user control the die to be toss()ed from the view?

  2. Concurrency (60 points)

    Consider the following ticket manager (TM) class that manages integers given out for a take-a-number system. Such systems manage crowds of customers by having each customer take a ticket, which bears a number. When the number is called, the customer is served. For this problem, do not concern yourself with limits on the value an int can assume.

    public class TM {
        private int currentlyServed;   // ticket number now being served
        private int lastCustomer;      // last ticket given out so far
        /**
          *  currentlyServed >= lastCustomer  means nobody is waiting
          */
    
        public TM() {
           currentlyServed = 0;
           lastCustomer    = -1;
        }
    
        public Ticket takeNumber() {
           lastCustomer = lastCustomer + 1;
           return new Ticket(this, lastCustomer);
        }
    
        //  Number now being served
        public int nowServing() {
           return currentlyServed;
        }
    
        public void returnTicket(Ticket t) {
           if (t.getNumber() == currentlyServed) 
              advance();
           else throw new Error("Security violation! (assume this won't happen)");
        }
    
        protected void advance() {
           currentlyServed = currentlyServed + 1;
        }
    
    }
    
    The above class should meet the following conditions:
    Numbers are given out in sequence and no two people get the same number.
    1. When used unmodified in a multithreaded environment, the above conditions can be violated. Show in detail how that can happen.
    2. Modify the TM class so that it is thread-safe. Use only as much synchronization as is necessary to maximize concurrency and to get full credit.
    3. Using your solution for TM from the previous question, complete the Ticket class (on an extra sheet of paper, neatly) so that it operates correctly and is thread-safe.
      Do not make any other modifications to TM in your response for this question.

      public class Ticket {
         private final TM tm;
         private final int num;
         public Ticket(TM tm, int myNumber) {
            this.tm  = tm;
            this.num = myNumber;
         }
      
         // You must implement the method below according to the following:
         //  When it's my turn to be served now, return true
         //  If I am too late ever to be served, return false
         //  otherwise wait until one of the above conditions holds
         public boolean waitForMyTurn() {
         }
      
         // When I am done being served, I must call done
         public void done() {
            tm.returnTicket(this);
         }
      
         // No need to change this
         public boolean invokeWhenMyTurn(Runnable r) {
             if (waitForMyTurn()) {
                 try {
                    r.run();
                 }
                 finally {
                    done();
                 }
                 return true;
             }
             else return false;
         }
      
         public int getNumber() {
            return num;
         }
      
      }
      
    4. Why is the Runnable invoked within a try...finally block in invokeWhenMyTurn(Runnable)?
    5. Under what circumstances would a customer find that his or her turn was passed up? In other words, what sequence of actions would cause invokeWhenMyTurn(Runnable) to return false?
      Your response must be restricted to the code we both see (based on your answers) for the TM and Ticket classes.
    6. Why is advance() not public? Consider a subclass of TM that calls advance() at will (when getting impatient for a customer to take his or her turn).

      How does this affect the operation of the system?

  3. Deadlock and liveness (25 points)

    Consider a grocery store that has multiple take-a-number stations (for example, the deli, bakery, fish market). Each station operates by calling numbers from its own TM and waiting on its own customers.

    Consider a Customer object that is instantiated with an array of TM objects. The Customer constructor can take at most one number from each of the TMs provided.

    1. What steps must the grocery store take to ensure there is no deadlock among Customers due to the multiple take-a-number stations?
    2. Describe how you would implement Customer so as to maximize liveness (i.e., minimize waiting time for this and all Customers). For example, a Customer should not have to wait long to do something if one station has a long wait and another has no wait at all.
      Because each station's service times are unpredictable, do not base your response on the apparent time remaining before a given ticket might be called.