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

Exam 2 Comments

Average: 83.5/100

Astrological Guidance

In your returned exam, you will find a star inside a black ink circle (don't be confused if you have other stars on your exam not inside black circles). The color of the star should help you decide whether or not you need to take the final. In no case will taking the final count against you.

Subtyping

1. (average 7.6 out of 10) Assume the following code is valid Java code: 

   MysteryType1 mt1;
   MysteryType2 mt2;
   ... (anything could be here)
   mt1 = mt2.ossifrage (mt1);
Could MysteryType2 be a subtype of Wombat (as specified below) that satisfies the substitution principle? Explain why or why not clearly. 
    public class Wombat extends Object {
       // OVERVIEW: A Wombat represents a confused bat.

       public Wombat () 
          // EFFECTS: Initialize this to a new Wombat.

       public Wombat ossifrage (Object o)
          // EFFECTS: Returns the ossifrage of this and o.
    }
From the code excerpt, we know MysteryType2 has a method named ossifrage that can be passed a MysteryType1 (hence, its parameter must be a supertype of MysteryType1) and that returns a subtype of MysteryType1 (since it can be assigned to mt1). The Wombat specification satisfies this if MysteryType1 is a supertype of Wombat. Hence, MysteryType2 could be a subtype of Wombat if Wombat is a subtype of MysteryType1.
2. (8.7 / 10) What can you determine about the specification of the MysteryType2 class? Be as specific as possible, but do not make any assumptions about the class that are not necessary for the code above to be correct. (Note: you should not assume MysteryType2 is a subtype of the Wombat type mentioned in the previous question.)
If a Java compiler will compile the code without complaint, you can determine: If the code is correct, you can also determine:
3. (9.2 / 10) Recall the SimObject class from Problem Set 5, excerpted and slightly modified below (see Exam 2 for code).

Would the SnakeSimObject class specified on the next page (see Exam 2 for code) satisfy the substitution principle rules to be a subtype of SimObject? For full credit, you answer must clearly explain why or why not.

Yes, the SnakeSimObject satisfies the substitution principle.

It defines all the methods of SimObject. The constructor satisfies the substitution principle: its postcondition is stronger than the postcondition of the SimObject constructor since the only differences in its effects clause concern state properties that do not apply to a SimObject (the length and direction). The init method satisifes the substitution principle since its type signature is identical, its precondition is identical, and the only differences in its postcondition concern state properties that do not apply to a SimBoejct. The executeTurn method satisfies the substitution principle since its precondition is weaker (requires true is the weakest possible precondition; all calling environments satisfy it) and its postcondition is stronger (it includes the postcondition of SimObject.executeTurn but provides more details on what a turn is for a SnakeSimObject). The getColor method satisfies the substitution principle since its postcondition is stronger than that of SimObject.getColor — it specifies the color of the snake.

4. (8.7 / 10) Suppose we changed the specification of the constructor to: 
    public SnakeSimObject ()
	// EFFECTS: Creates a new initialized SnakeSimObject at (0,0)
	//	with length 3 and facing direction N.
	//@ensures isInitialized
    { }
Illustrate why this specification would not satisfy the substitution principle by showing a short code fragment where a SnakeSimObject could not be safely used in place of a SimObject and explain what could go wrong.
Here is a code fragment: 
   SimObject s = new SimObject (); // new SnakeSimObject ()
   s.init (5, 5, grid);
This is okay as shown, but invalid if we use the SnakeSimObject instead. The problem is that the init method requires an object that is !isInitialized. The ensures clause for SimObject satisfies this, but the ensures clause for SnakeSimObject does not. This violates the substitution (as evidenced by the example) since the postcondition of the subtype constructor does not imply the postcondition of the supertype constructor.
5. (8.7 / 10) Explain how the implementation below could exhibit a race condition if this code were used as part of a distributed voting machine (where the same Candidate object may be referenced by multiple threads). [See exam for code.]
If there are two threads that call tallyVote on the same Candidate object, their execution could interleave like this: thread 1 calls getVotes () and it returns 0; thread 2 calls getVotes () and it returns 0; thread 1 assigns the result of getVotes () + 1 (= 1) to votes; thread 2 assigns the result of getVotes () + 1 (= 1) to votes. Two votes were cast, but the value of votes is only 1.
6. (4.6 / 5) Explain what small change you would make to the code to fix the problem you identified in question 5?
Use a synchronized block to prevent two threads from entering the tallyVote code at the same time: 
public void tallyVote () {
   synchronized (this) {
      ... // same body as before
   }
}
7. (10.8 / 15) In Problem Set 5, Question 7, we suggested solving the deadlock where three philosophers interact by adding a rep invariant the requires colleage relationships to be reflexive (that is, if A is B's colleague, B must be A's colleague). Suppose we did not want to place this restriction on colleagues. Instead, we should be able to have three philosophers where A is B's colleague, B is C's colleague and C is A's colleague. Describe a locking strategy that would allow this without ever deadlocking. A good strategy description is worth 10 points, but for full credit, you must show (pseudocode is fine) how you would modify code for the philosophize method below to implement your strategy: 
    public void philosophize () {
	Object lock1, lock2;

	if (colleague != null) { // Need a colleague to start and argument.
	    // Always grab the lock for whichever name is alphabetically first
	    if (name.compareTo (colleague.name) < 0) {
		lock1 = this;
		lock2 = colleague;
	    } else {
		lock1 = colleague;
		lock2 = this;
	    }
	        
	    synchronized (lock1) {
		synchronized (lock2) {
		    System.err.println (name + "[Thread " + Thread.currentThread().getName () + "] says " + quote);
		    colleague.argue ();
		} 
	    }
	}
    }
This was a bad question — it is not clear that the described deadlock situation even exists. The easiest solution is to grab all the connected locks in alphabetical order. This depends on knowing all the philosopher's who may have common colleagues, which is not possible with the provided implementation. If B is A's colleague, A can determine B's colleague from accessing B; on the other hand, A has no way to determine that C's colleague is A since there is no way to even know that the object C exists within the implementation of A. Students were give almost full credit for describing strategies in which all the locks were acquired in alphabetical order, but preventing all possible deadlocks is not possible without more substantial code changes.

Memory Management

8. (7.1 / 10) Consider the following classes (similar to Problem Set 4 and Lecture 17) [See exam for code.]

Fill in the missing parts in the small code fragment below so that a mark and sweep garbage collector that runs at the marked location would collect exactly 2 garbage Species objects. 

   SpeciesSet ss = new SpeciesSet ();
   Species s1 = new Species ("snake", "ACATGA");
   Species s2 = [[[ fill in space 1 ]]]; 
   Species s3 = [[[ fill in space 2 ]]];

   ss.insert (s1);
   s1 = null;
   ss.insert (s2);
   s2 = null;
   ss.insert (s3);
   s3 = null;

   ← mark and sweep collector runs here
   ...
The insert method adds a Species object to the set if its name is different from all current elements in the set; otherwise, it does nothing. So, to have two garbage objects at the marked point, we need to make s2 and s3 new objects that are not added to ss (since then, they would be reachable through ss). Hence, they must be new Species objects with names matching "snake" (it doesn't matter what the genome is): 
   Species s2 = new Species ("snake", "HARVEY");
   Species s3 = new Species ("snake", "SALLY");

9. (7.6 / 10) In a language with explicit memory management like C, explain why it would be useful to change the specification of insert to: 

   public boolean insert (/*@non_null@*/ Species s) 
	// MODIFIES: this
	// EFFECTS: If s already contains a Species whose name matches
	//	the name of s, returns false and does nothing.
	//	Otherwise, returns true and adds s to the elements of
	//	this: this_post = this_pre U { s }
If the passed Species object is not added to the set, the caller may need to deallocate that object. If the object is added, the caller must not deallocate that object, since it is reachable through the set. For example, 
   if (!ss.insert (s)) {
      Species_free (s);
   }
10. (8.8 / 10, a good answer is worth bonus points; a complete language design and implementation is worth an automatic A+ in CS201J) After being barred from using Sun's Java trademarks, a large software company in Mondred, Washington has decided to attempt to implement a new language that will offer the performance advantages of C with the saftey and ease of development advantages of Java. They call their new language Db (pronounced "D flat"), not to be confused with its tonal near-equivalent C# ("C sharp"). In particular, they would like it to be possible to build a reference counting garbage collector that will work for Db but still be able to manipulate memory addresses directly in at least some of the ways allowed by C. Assume they will start their design with C, and add or remove features to produce Db. Either argue why their goal is impossible to achive, or explain what changes they should make to C to achieve their goal.

See Lecture 22.
11. (Optional, no credit, but I might give bonus points for good answers) Describe what CS201J is about using one word or a short phrase.

See Lecture 21.
CS201J University of Virginia
Department of Computer Science
CS 201J: Engineering Software
 		Sponsored by the
National Science Foundation 		cs201j-staff@cs.virginia.edu