CSE132 Practice Midterm Exam
Solution

Solution comments are shown like this. Grading and points advice is shown like this, within the solution comments.

  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?
      • 5 points
      • Model should be something like BoundedRangeModel, instantiated in Die, and configured to use 0 through 5 or 1 through 6.
      • If Die itself is the model, make sure they automatically push changes to the mode out to any listeners -4 if they didn't
    2. Describe one or more reasonable views of the model.
      5 points View could be a button or label showing the value, a slider, a graphic depiciting the Die---anything that reflects the value of the Die visually. The view must be connectable to the model so that when the model changes, the view does too -4 if they didn't allow for that
    3. Describe the user interaction possibilities with the view. How can the user control the die to be toss()ed from the view?
      5 points There should be some provision to throw the Die. A button comes to mind. There could be a provision to set the Die to some specific value, as if the die were picked up by hand and set down (not necessary, but nice).

  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.
      • This problem is worth 10 points. If they don't show any detail, take 5 points. If the details are sketchy, your call from 1-5 points off.
      • takeNumber has a race that can allow the following:
        • Two threads enter takeNumber, each sees lastCustomer value == 0
        • Each bumps by one to compute lastCustomer == 1
        • Two tickets are issued with the same ticket number (1)
    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.
      • This is worth 10 points.
      • takeNumber must have synchronization around the computation for lastCustomer. The method could be synchronized, or just that statement could be synchronized---doesn't matter. 5 points for getting this right
      • advance also has a race condition, BUT the synchronization is more properly applied to returnTicket, since it compares the ticket number with currentlyServed.
        • If they synchronize BOTH advance and returnTicket, take off 3 points.
        • If they synchronize advance but not returnTicket, take off 3 points
        • If they synchronize neither, take off 5 points
        • If they synchronize returnTicket and not advance, take off nothing.
      • If they synchronized nowServing, take off 3 points more
    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.

      • This is worth 15 points.
      • Grading this is tricky, and I've offered just one solution below.
      • Make sure they do not spin, but actually wait as I show below. -5 if they sleep or spin instead of wait
      • They need to wait on the right object. It won't work to wait on this within the Ticket object. -5 if they wait but it's on the wrong object.
      • Make sure they honor the contract of returning true if it's this ticket's turn and false if it was passed up. -3 if they get this wrong.
      • When a ticket is returned, notifyAll() has to be called, and they were instructed not to modify TM. The call thus has to be from Ticket, and I show how to do that below. -5 if they fail to notifyAll() (don't take an additional 5 off if they both wait and notifyAll on the wrong object).
      • I don't show the try..catch that should surround a wait(). Don't count off if they fail to put in the try...catch.
      • I do show that I have a lock on the TM object when I wait() or notifyAll(). They better do that. -3 if they fail to have the lock.
      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() {
      
            synchronized(tm) {
               while ( tm.nowServing() < num ) tm.wait();
               //
               // Here, tm.nowServing() ≥ num
               //
               return tm.nowServing() ==  num;
            }
      
         }
      
         // When I am done being served, I must call done
         public void done() {
            tm.returnTicket(this);
      
            //
            // when a ticket is returned, this has to happen somewhere
            //
            synchronized(tm) {
               tm.notifyAll();
            }
      
      } // 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 points The Runnable is beyond control of the Ticket. Should it return normally or by exception, the Ticket is done and we want to allow the next customer to proceed.
    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.
      10 points There should be no circumstances in which this can happen. Read what they say and see what you think in grading this. They may cite possible fault in classes that extend TM that might call advance() spuriously.
    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?

      10 points This would be like letting customer's press the "next" button. Certainly turns could get skipped if advance() is public.

  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?
      10 points No steps should be necessary, since multiple resources need not be acquired before acting. The act of getting a ticket does not hold any lock. A customer wanting service at multiple TMs does so in any sequence, since only one is needed at a time.

      A solution might point out that a customer could take forever. In that case, the act of serving a customer might come with a timer that when expired, causes the customer to lose his or her turn and serice to pass on to the next customer.

    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.
      15 points I expect some thought here. Note that once a thread calls invokeWhenMyTurn that it will wait until it's number is called on that particular ticket. What should be considered here is the case when a customer holds multiple tickets to different TMs. In that case, liveness is increased if the customer can effectively wait for his or her turn on any of the TMs.

      This requires threads! My solution would be to have a thread per ticket that a customer holds (this would be the customer's responsibility).

      The consequence of not doing this is longer waiting time for a given customer which could delay everybody else as well.