Exam 2 Comments

1. (10) Which design is better? Provide a clear, brief argument supporting your answer.

Answer: Design B has several advantages: modularity, code reusability by means of inheritance, ease of extending the hierarchy, ease of work division and testing.

Design A has the advantage that there are fewer classes to implement and test. However, it would be very hard build a system using design A, especially if it is used for AirTrafficController. Note that the reason we needed to choose design B for the rest of the exam is that we would need multiple versions of the addPlane and takeoffPlane methods if we choose design A. Without subtyping, we would need to provide two addPlane methods — one that takes a Propeller as its parameter, and one that takes a Jet. If we wanted to extend the system with a new kind of plane, with design B this would be easy: just add a new subtype of Plane. With design A, we would need to change AirTrafficController also.

2. (15) The specification for requestTakeoff is flawed — it does not handle the case when there are no available runways.

a. One way to solve this problem would be to add a REQUIRES clause (and make no other changes). What requires clause would you add?

Answer:

REQUIRES: There is an r in this.runways that is not in any tuple <x, r> in this.reservations. Another correct answer is that the number of elements in this.runways must be greated than the number of elements in this.reservations.

b. Describe a better solution to this problem and explain why it is better.

Answer: A resonable solution would be to change the specification to:

   public Runway requestTakeoff (Plane p) throws NoMatchingPlaneException, 
                                                 NoAvailableRunwayException
      // MODIFIES: this
      // EFFECTS: If p is not a plane in this.planes, throws 
      //     NoMatchingPlaneException.  Otherwise, returns a runway r
      //     from this.runways such that there is no entry in 
      //     this_pre.reservations that matches < x, r > 
      //     and this_post.reservations contains < p, r >.  If there
      //     is no such runway, throws NoAvailableRunway.

This would require planes to keep calling requestTakeoff if they get the NoAvailableRunway exception to keep waiting until a runway is available.

An alternative might be to leave the specification essentially unchanged: if there are no runways available, requestTakeoff just waits until a runway is available before returning. With this solution, we need to be very careful about deadlocks since requestTakeoff will block until a runway is available.

3. (15) Clyde Swift argues that the rep invariant for AirTrafficController should contain the term:

   //    Each plane may appear in an element of reservations at most once

Describe the changes that should be made to the AirTrafficController implementation if the new rep invariant term is added. (Hint: one change is neccessary to ensure the rep invariant is preserved; the other change is a performance improvement enabled by the rep invariant.)

Answer: Full credit was given for (1) noting that the rep invariant would be violated in requestTakeOff, (2) clearly describing a strategy to fix this problem, and (3) noting that in takeOffPlane the for loop could be terminated after finding the plane, improving performance.

4. (15) The implementation of requestTakeoff has some potential race conditions. Describe at least one of them. Your description should clearly explain an ordering of events that could lead to a violation of the representation invariant for AirTrafficController (and possibly more disastrous consequences after that).

Answer: The most serious race condition is that the thread could switch between the isReserved(r) check and the reservations.add call that adds the runway reservation. A thread for plane 1 could call requestTakeoff on an airport where runway r1 is currently unreserved. So, !isReserved(r1) returns true. After this, executions switches to a different thread which also calls requestTakeoff. Runway r1 is still unreserved, since the first thread did not reserve it yet, so thread 2 reserves runway r1 for plane 2, and returns runway r1. Once execution switches back to thread 1, it will add a reservation for plane 1 and runway r1, and return r1. Hence, two planes have reservations for the same runway! Since two planes could be scheduled on the same runway in this case, the rep invariant clause

    //    Each runway may appear in an element of reservations at most once

is violated.

Note that there are other race conditions in our implementation. For example, if lookupPlane(p) happens before another thread calls takeoffPlane(p), then requestTakeoff could return with a state where this clause of the rep invariant is not true either:

    //    Every plane that appears in an element of reservations is an element of planes

5. (15) Rewrite requestTakeoff to solve the race condition you identified in question 4. For full credit, your solution should lock as few objects as possible for as little time as possible. The original requestTakeoff code is reproduced below, with plenty of space for you to make the necessary changes.

Answer: The best solution is to synchronize on only the runway you are about to reserve:

   public Runway requestTakeoff (Plane p) throws NoMatchingPlaneException {
	   lookupPlane (p); // throws NoMatchingPlaneException
	   for (Enumeration enum = runways.elements (); enum.hasMoreElements (); ) {
               Runway r = (Runway) runways.nextElement ();
	       synchronized (r) { 
                  if (!isReserved (r)) {
                      reservations.add (new Reservation (p, r));
                      return r;
                   } 
               }
         }

         return null; // This code assumes a moderately bad answer to question 2b.
    }

You could also solve the race condition by locking the this object or the this.runways object, but that would lock more resources than necessary.

Note that this does not prevent all of the race conditions (such as the lookupPlane race).

6. (10) What value is stored in local variable location 0 after executing the following bytecodes:

      ldc 201          
      istore_0 
      ldc 200          
      istore_1 
      iload_1  
      iload_0  
      iadd     
      istore_0 
      iload_1  
      iload_0  
      iadd     
      istore_0 

Answer: 601

7. (10) What type error would the Java bytecode verifier detect for the following class file?

.source Enigma.java
.class  public synchronized Enigma
.super  java/lang/Object

	;;; Default  method removed

; >> METHOD 2 <<
.method public static main([Ljava/lang/String;)V
    .limit stack 2
    .limit locals 3
.var 0 is args [Ljava/lang/String; from Label1 to Label4
Label1:
    ldc "nut"
    astore_1
.line 4
.var 1 is s1 Ljava/lang/String; from Label2 to Label4
Label2:
    ldc "bunnies"
    astore_2
.var 2 is s2 Ljava/lang/String; from Label3 to Label4
Label3:
    aload_1
    ldc " "
    invokevirtual java/lang/String/concat(Ljava/lang/String;)Ljava/lang/String;
    astore_1
    iload_1
    aload_2
    invokevirtual java/lang/String/concat(Ljava/lang/String;)Ljava/lang/String;
    astore_1
    getstatic java/lang/System/out Ljava/io/PrintStream;
    aload_1
    invokevirtual java/io/PrintStream/println(Ljava/lang/String;)V
    return
Label4:
.end method

Answer: Under Label3, astore_1 stores a reference to an object or array in location 1. The next instruction, iload_1, attempts to load an integer from location variable 1, but the previous instruction stored an object there. Hence, the code will result in a type safety verification error.

8. (10) What output would the class from question 7 produce when executed using java -noverify Enigma?

Answer: nut bunnies

9. (Optional, no credit) Is there anything you think I should take into account in determining your final grade that won't be apparent from your performance on this exam, the problem sets and exam 1?

Here is a selected sampling of comments people wrote:

• "Last year I struggled through CS101 (poor grade), but after taking your class I fell that if I took CS101 again I would ace it. If the problem sets don't shot it, it doesn't mean I haven't learned much. Your class has taught me how to think logically and computationally. I've also learned that I can teach myself anything if I put the work into it."
• "Although my programs were never as good or complicated as others, I fell like I put as much effort into writing and understanding my programs. This material was harder for me to pick up than others. I don't think all my grades and programs represent the effort I put into them because it was a slow and frustrating process at times trying to figure everything out. I think there are some people in the class who had either had some Java before or were just GENIUS and picked up on everything quickly, but I definitely did not fall into that class. Basically, I worked hard for what I did, but nevery got the end produce that others, who it came more easily to got."
• "Although it may seem like I have not put a lot of effort into this class, I actually have spent more time on the problem sets and exams than I have for any other class. Unlike some of the people in the class who have extensive programming backgrounds, I have only takes on CS class in my life (CS101 which also spent ungodly hours on and did horribly in). While many of the students who are similar to me have gotten into groups with good programmers, I have chosen to work alone for the last two problem sets in an attempt to show you that I am putting forth my own individual effort. I have actually done well on all of the portions of the problem sets that don't involve coding (this is my downfall)."
• "I started offknowing absolutely nothing about Java and knowing how to code, but I have put in a lot of work all semester to learn what I'm doing and I feel as if I made a lot of improvements. I went from being completely lost in the beginning of the semester to now feeling like I have a very strong grasp on the material. I hope my poor performance on the first couple of problem sets doesn't dramatically hurt my grade."
• "You should take into account the initiative and hard work I put into attempting to solve a 7 row peg board and give me an A++."
• "I have perfect attendance for lecture and always follow along and pay attention."
• "Perhaps consistent attendance to class should be included in our grades?"

  I don't believe grading in college should depend on attendance. Students have different ways of learning, and different constraints on their lives that make it harder or easier to attend class. On the other hand, attending class should be beneficial, since hopefully you learn things in class that help you do well on the assignments and exams.

• "A" is my favorite letter of the alphabet. Addition ("+") is my favorite mathematics function.

10. (Optional, no credit) Is there anything else you want me to know about CS201J?

Here is a selected sampling of comments people wrote:

• "I have really enjoyed your classes. They really remind me why I came to the College. Odd that you teach in the E-school."
• "I did enjoy the class. I found the peg problem set to be the best. I was wondering if anyone got it to do a 7 row board in under 6 hours. We tried to get ours to, but couldn't."

  No, no one has solved the 7-row board. But, feel free to keep working on it over winter break!

• "Ali G is the man."
• "I really enjoyed the last lecture as well. I couldn't think of a better way to end the class!"
• "I hated everything about programming and machine languages before this class. Now, I'm thinking about minoring in CS. Thank you."
• "It was an excellent course, that was well taught. The class definitely changed my opinion as to what a good coding style is, and I feel sucessfully demonstrated the benefits of software engineering rather than hacking together working code."
• "Yes, it was my favorite class this semester — definitely not my easiest or least time consuming, but definitely my favorite — Thanks!!!"
• "You know how you said that you wanted us to write programs to change the workd or to just delta it...Well I was thinking about that and I had a simple idea...."
• "I'm curious how to become and assistant coach for this class. It's something I'd really enjoy doing, seeing as I really enjoyed this class... So, if you're looking for assistant coaches, or any help for that matter, I'd love to join the team."

  I recruit assistant coaches based on class performance first and foremost, then based on contributions to the class and observing how well students work with their classmates and me during the course. I'm not expecting to teach a CS201J-like course next year, but if I do, I will be looking to recruit assistant coaches from students who did well in this course. If you are interested in being an undergraduate TA for another course, the department is always looking for TAs. See http://www.cs.virginia.edu/jobs/form-all.html for details.

---

University of Virginia Department of Computer Science CS 201J: Engineering Software

Sponsored by the National Science Foundation

cs201j-staff@cs.virginia.edu