CS201J: Exam 2

University of Virginia, Department of Computer Science
CS201J: Engineering Software, Fall 2003

Exam 2 Out: 2 December 2003
Due: Friday, 5 December 2003, 3:55pm
Absolutely no exams will be accepted (without prior arrangement) after 3:55pm Friday.

Name: _________________________________________________________
Collaboration Policy (read carefully)
Work alone. You may consult any material you want including the course notes, text and additional sources (including anything you find on the Web). If you use a source other than the course materials or text, you should cite the source in your answer.
You may not discuss this exam with any human, other than the course staff (who will answer clarification questions only). You may not use a Java compiler, assembler or disassembler during this exam.
Answer all eight questions (100 points total). Write your answers on this exam. You should not need more space than is provided to write good answers, but if you want more space you may attach extra sheets. If you do, make sure the answers are clearly marked.
There is no time limit on this exam, but it should not take more than a few hours to complete.

Question Value Score

1. 10

2. 15

3. 15

4. 15

5. 15

6. 10

7. 10

8. 10

Total 100

Subtyping and Design
On her flight home for Thanksgiving, Colleen M. Hacker is delayed because of airport congestion. She decides to write a distributed simulation to experiment with approaches for controlling airplane traffic to develop a better solution.
Her simulation will need to model moving objects at the airport:

Jet Airplanes — large, fast moving airplanes that carry many passengers
Propeller Airplanes — small, slow airplanes that carry only a few passengers and break down frequently
Fueling Trucks — trucks that provide fuel for airplanes

Two possible designs for the subtype hierarchy are shown below:

Design A
Design B

1. (10) Which design is better? Provide a clear, brief argument supporting your answer.
For the following questions, we assume Design B.
Our airport simulator will use an AirTrafficController class to control movement of airplanes in the airport. The AirTrafficController needs to keep track of all the airplanes and respond to requests for takeoff and landing. An airplane may land or takeoff on a particular runway only if there are no other airplanes on that runway. A preliminary specification for AirTrafficController is shown below.
public class AirTrafficController {
   // OVERVIEW: An AirTrafficController manages the movements of airplanes in an airport.
   //     It keeps track of the locations of all the airplanes in the airport and 
   //     authorizes planes to land or takeoff on particular runways.
   //
   //     A typical AirTrafficController is < planes, runways, reservations >
   //     where planes is a set of Plane objects at the airport, runways is a set of
   //     Runway objects, and reservations is a table of < plane, runway > pairs.
   //     All planes and runways that appear in the reservations table must be
   //     in the planes and runways sets; each runway may appear in the reservations
   //     table no more than once.

   public AirTrafficController ()
      // EFFECTS: Initializes this to a new AirTrafficController with no
      //    planes, runways or reservations: this = < {}, {}, {} >

   public void addRunway (Runway r) throws DuplicateRunwayException
      // MODIFIES: this
      // EFFECTS: If r is a runway in this.runways, throws
      //    DuplicateRunwayException. Otherwise, adds r to  this.runways.

   public void addPlane (Plane p) throws DuplicatePlaneException
      // MODIFIES: this
      // EFFECTS: If p is a plane in this.planes, throws
      //    DuplicatePlaneException.  Otherwise, adds p to this.planes.

   public void takeoffPlane (Plane p) throws NoMatchingPlaneException
      // MODIFIES: this
      // EFFECTS: If p is not a plane in this.planes, throws
      //     NoMatchingPlaneException.  Otherwise, removes p from
      //     this.planes and removes all entries matching < p, x > 
      //     from this.reservations. 

   public Runway requestTakeoff (Plane p) throws NoMatchingPlaneException
      // 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 >.
}
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?

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

The following questions concern the implementation of AirTrafficController given on the last two pages of this exam. You may remove those pages from your exam so it is easier to look at the code while you answer the following questions.
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.)

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).

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.
   public Runway requestTakeoff (Plane p) throws NoMatchingPlaneException {


	   lookupPlane (p); // throws NoMatchingPlaneException


	   for (Enumeration enum = runways.elements (); enum.hasMoreElements (); ) {
 

               Runway r = (Runway) runways.nextElement ();


               if (!isReserved (r)) {


                      reservations.add (new Reservation (p, r));


                      return r;


               } 


         }


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


    }
Byte Codes and Type Safety
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
Note: the last iload_0 was missing from the original version of the exam handed out.

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
8. (10) What output would the class from question 7 produce when executed using java -noverify Enigma?

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?

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

End of Exam
The following two pages are the AirTrafficController implementation for questions 3-5.

AirTrafficController Implementation
Here is the implementation of AirTrafficController used in questions 3-5.
import java.util.Enumeration;
import java.util.Vector;

class Plane {
    private String name;
    public Plane(String s) {
	name = s;
    }    
    public boolean equals (Object o) {
	if (o instanceof Plane) {
	    return name.equals (((Plane) o).name);
	} else {
	    return super.equals (o);
	}
    }
}

class Reservation {
    public Plane plane;
    public Runway runway;
    public Reservation(Plane p, Runway r) {
	plane = p;
	runway = r;
    }
}

class Runway {
    private String name;
    public Runway(String s) {
	name = s;
    }
    public String toString() {
	return "";	
    }
    public boolean equals (Object o) {
	if (o instanceof Runway) {
	    return name.equals (((Runway) o).name);
	} else {
	    return super.equals (o);
	}
    }
}

public class AirTrafficController {
    // NOTE: This code was written for a CS201J exam.  Only a true
    //    idiot would use any of it in a real air traffic
    //    control system!
    
    private Vector planes; // Vector of Plane objects
    private Vector runways; // Vector of Runway objects
    private Vector reservations; // Vector of Reservation objects
    
    // Rep Invariant:
    //    No duplicates in planes
    //    No duplicates in runways
    //    Every plane that appears in an element of reservations is an element of planes
    //    Every runway that appears in an element of reservations is an element of runways
    //    Each runway may appear in an element of reservations at most once
    
    public AirTrafficController() {
	planes = new Vector();
	runways = new Vector();
	reservations = new Vector();
    }
    
    private int lookupRunway(Runway r) throws NoMatchingRunwayException {
	// EFFECTS: If r matches a runway in this.runways, returns 
	//     i such that runways.get(i) == r.  Otherwise, throws
	//     NoMatchingRunwayException.
	for (int i = 0; i < runways.size(); i++) {
	    Runway rel = (Runway) runways.get(i);
	    if (r.equals(rel))
		return i;
	}
	throw new NoMatchingRunwayException();
    }
    
    private int lookupPlane(Plane p) throws NoMatchingPlaneException {
	// EFFECTS: If p matches a plane in this.planes, returns 
	//     i such that planes.get(i) == p.  Otherwise, throws
	//     NoMatchingPlaneException.
	for (int i = 0; i < planes.size(); i++) {
	    Plane pel = (Plane) planes.get(i);
	    if (p.equals(pel)) 
	       return i;
	}
	throw new NoMatchingPlaneException();
    }
    
    public void addRunway(Runway r) throws DuplicateRunwayException {
	try {
	    lookupRunway(r);
	    throw new DuplicateRunwayException();
	} catch (NoMatchingRunwayException e) {
	    runways.add(r);
	}
    }
    
    public void addPlane(Plane p) throws DuplicatePlaneException {
	try {
	    lookupPlane(p);
	    throw new DuplicatePlaneException();
	} catch (NoMatchingPlaneException e) {
	    planes.add(p);
	}
    }
    
    public void takeoffPlane(Plane p) throws NoMatchingPlaneException {
	int i = lookupPlane(p); // thows NoMatchingPlaneException in header
	planes.remove(i);
	// remove reservations for p
	for (int j = 0; j < reservations.size(); j++) {
	    Reservation r = (Reservation) reservations.get(j);
	    if (r.plane.equals(p)) {
		reservations.removeElementAt(j);
		j = j - 1;
	    }
	}
    }
    
    private boolean isReserved (Runway r) {
	// EFFECTS: Returns true iff there is a reservation for runway r (that is,
	//     this.reservations contains an element whose runway matches r.)
	for (int j = 0; j < reservations.size(); j++) {
	    Reservation rsv = (Reservation) reservations.get(j);
	    if (rsv.runway.equals(r)) {
		return true;
	    }
	}				
	return false;
    }
    
    public Runway requestTakeoff(Plane p) throws NoMatchingPlaneException {
	lookupPlane(p); // throws NoMatchingPlaneException
	for (Enumeration enum = runways.elements(); enum.hasMoreElements();) {
	    Runway r = (Runway) enum.nextElement();
	    if (!isReserved(r)) {
		reservations.add(new Reservation(p, r));
		return r;
	    }
	}
	return null; // This code assumes a moderately bad answer to question 2b.
    }
}

Question	Value	Score
1.	10
2.	15
3.	15
4.	15
5.	15
6.	10
7.	10
8.	10
Total	100

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

Sponsored by the
National Science Foundation

cs201j-staff@cs.virginia.edu