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

Name: ________________________  ALL 6 ID digits: ____________________
In Lab 3, sets change color somewhat randomly as they are formed from computing set-unions. In this midterm, you are given ColorSet, an implementation of the Set interface:

  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


Last modified 15:27:30 CST 20 February 2015 by Ron K. Cytron