CSE 132 (Spring 2015)
OLD (2011) Midterm Exam

Name: ________________________  ALL 6 ID digits: ____________________

• This exam is open notes, and you can look at any code you have developed on your own or with others in studio or lab.
• The code you write for this midterm must be entirely your own, and not taken from any other source, human or electronic.
• You are not to discuss this exam with anyone except the professor.
• You are on your honor to do your work on your own.
• The exam is due at the beginning of of class on March 29. There are no extensions.
• You must use your personal repository for this exam. Try this early to make sure it works for you. No extensions will be given because of problems you have with your repository. The exam requires you to commit code and make note of commit numbers on this exam and on some printouts.
• Submission of this midterm requires you to include some printouts. You are responsible for having these ready, on-time, completing them as described below, and turning them in with your exam.

  Do not email your work to me, or put your work in my mailbox. You work is due as stated above, so plan ahead to have everything ready.

• Although ColorSet contains all methods (some by extension) that are necessary to implement the Set interface, most of the methods throw an UnsupportedOperationException and those methods are not needed for this midterm.
• However, ColorSet offers two extra features useful for Lab 3:
  • Each ColorSet has-a Color that is specified when the set is instantiated. It is final, so it cannot change after it has been established by the constructor.
  • The coloredMerge method takes this set and that set (parameter), and returns the union of the two sets as a ColorSet whose color is copied from the larger of the two sets. The sets participating in the union are not mutated by this call. This is effectively the computation needed in Hall to form the union of the two rooms' sets that are joined by an opening hallway.

• In your repository you will find a midterm package with an implementation of ColorSet and RWLock (used with permission of Kevin Kieselbach and Nathan Duke, adapted by the instructor as indicated by comments).
• You are given the JUnit test ColorSetTest, which throws errors because the ColorSet class is not yet thread-safe. You can use this test to determine when you have sufficient exclusion in your code, but you will get full credit only if your exclusion is necessary. Think things through and avoid unnecessary exclusion.
• The ColorSet class makes extensive use of its toArray() method, which returns a copy of the set with one element in each of the returned array's slots.
  • By operating on a thread-safe copy of the set, the methods can avoid many unsafe race conditions.
  • For example, the size() method retrieves a copy of the set via toArray() and returns the length of that array as the size of the set.

1. 15 points Your first task is to decide which methods, other than colorMerge, require the synchronized keyword to make the class thread-safe. Once you are sure of your solution, insert comments to explain why each method does or does not need to be synchronized to operate correctly.

   • Do not worry about colorMerge yet. The multithreaded test in ColorSetTest does not use that method.
   • Credit will not be given without an explanation provided in comments above each method.
   • Explanations are required for why a method does or does not need to be synchronized.
   • Verify your solution using the unit test, but your code must be correct even if the unit test misses something.
   • Commit your code at this point, and make note of the revision number associated with ColorSet. This is necessary to receive credit.
   • Print out this version of ColorSet for turning in, and write clearly on the printout:
     • your name
     • your ID (all 6 digits)
     • the revision number for your ColorSet
     • Write that revision number here as well: ___________

2. 25 points Your next task is to remove the synchronized keywords and consider where your code requires readers and writer locks to operate correctly. There is already an instance of an RWLock in your ColorSet class. Use it and the implementation of RWLock given to you in the midterm package. Do not use RWLockPub!

   • Make sure all your synchronized keywords are gone from the previous part.
   • Continue to ignore colorMerge. We're not ready for it yet.
   • The implementation you are given for RWLock is re-entrant. A thread already holding the write lock can subsequently ask for writer or readers locks without having to wait.
   • As usual, each lock acquire (re-entrant or not) must be matched by a release.
   • Specify your lock actions using rwlock.acquireReadOnly(), rwlock.acquireReadWrite(), and rwlock.release(). Do not use lockInvoke.
   • Use the before/after pattern to make sure locks will be released whether the code executed while holding the lock terminates normally or by exception.
   • Be sure to use the appropriate lock (readers or writer) as needed.
   • Explanations are required for why a section of code needs a particular kind of lock.
   • Verify your solution using the unit test, but your code must be correct even if the unit test misses something.
   • Commit your code at this point and make note of the revision number associated with ColorSet.
   • Print out this version of ColorSet for turning in, writing clearly on the printout:
     • your name
     • your ID (all 6 digits)
     • the revision number for your ColorSet
   • Write that revision number here as well: ________________

3. 10 points Take a look at RWLock and the comments in acquireReadOnly() bracketed by RKC. If that section of code is deleted, the resulting code should deadlock when you run the unit test on ColorSet with RWLocks.

   Below, explain exactly why the deadlock occurs.

    
    
    
    
    
    
    
    
   

4. 10 points The ColorSet is missing an implementation of hashCode(). Let's assume two ColorSets are identical if they contain the same elements (order does not matter, nor does the Color associated with the set). Write a reasonable implementation of hashCode() into your ColorSet class. You get 2 points for a correct impelementation, and full credit for a reasonable attempt to differentiate hashcode values for non-equal sets. You will print this out with the next part below. Below, explain your approach:

    
    
    
    
    
    
    
    
   

5. 25 points OK let's fix colorMerge. Continue with the RWLock version of ColorSet. Using more RWLocks as necessary, create a safe, deadlock-free, and maximally live (least locking needed to be safe and deadlock-free) colorMerge. Below, explain your approach:

    
    
    
    
    
    
    
    
   

   • Your code should now have hashCode() implemented as well as your solution for colorMerge.
   • Commit your code at this point and make note of the revision number associated with ColorSet.
   • Print out this version of ColorSet for turning in, writing clearly on the printout:
     • your name
     • your ID (all 6 digits)
     • the revision number for your ColorSet
   • Write that revision number here as well:________________

6. 15 points
   • What is your ID? ___________________
   • What is the 7-digit 10's complement of 123456? ________________
   • Below, compute the subtraction of 123456 from your ID, carried out in 7-digit 10's complement arithmetic. Show all of your work!