CSE 132 (Spring 2009)
Studio 5: Mazes and Locks

Review studio procedures, if necessary, before starting.

Some guidelines for this week's studio:


Problems:

  1. How can we tell a good maze from a bad one?
  2. Mazes are supposed to have the following properties:

    Behold the beauty and wonder of a good maze:

    For example, the path between rooms 24 and 47 goes: 24, 30, 36, 42, 43, 44, 45 46, 47

    Pick any pair of rooms and convince yourselves there is exactly one path between them.

    and that is the only path between those rooms.
    On the other hand, below you see a bad maze (cue the sinister music):

    For example, rooms 7, 8, 13, and 14 are involved in a cycle.

    Find more cycles and convince yourselves of the abhorrence of this maze.


    Devise an algorithm that determines if a Maze is good:
    1. All rooms are connected.
    2. No cycles.
    More specifically, and apropos the CheckMaze class you must implement for Lab 3b, if you started at some random Room, how could you tell if the maze is good?
    To get an idea of the methods you can call on various objects for this lab, consult the JavaDoc for the lab.
    Bounce your ideas around, and off of other groups, and talk with the TAs and professor about this.

  3. Readers/writer locks
    1. Download this zip, install it in your eclipse project, and run the Bank class as a Java application.
    2. Review the BoundedInteger implementation from class this morning.
    3. Based on what you learned in class about interprocess communication, fill in the class below to implement a readers/writer lock. This will allow
      • Any number of readers execute concurrently, or
      • Only one writer (and no readers) execute.
      package studio5locks;
      
      public class RWLock {
      
      	/**
      	 * First half of a read-only lock.  Should this be synchronized?
      	 */
      	public void acquireReadOnly() {
      
      	}
      
      	/**
      	 * First half of a read-or-write lock.  Should this be synchronized?
      	 */
      	public void acquireReadWrite() {
      
      	}
      
      	/**
      	 * Second half of either lock.  Should this be synchronized?
      	 * Release whichever of the two locks the current thread holds.
      	 * Make sure a Thread doesn't invoke this method without having one of the two locks!
      	 */
      	public void release() {
      
      	}
      
      	/**
      	 * For convenience, acquire the read-only lock, run, release
      	 * Should this be synchronized?
      	 * @param r Run r after acquiring a read-only lock
      	 */
      	public void acquireReadOnly(Runnable r) {
      		try {
      			acquireReadOnly();
      			r.run();
      		}
      		finally {
      			release();
      		}
      
      	}
      	
      	/**
      	 * For convenience, acquire the read-write lock, run, release
      	 * Should this be synchronized?
      	 * @param r Run r after acquiring a read-write lock
      	 */
      	public void acquireReadWrite(Runnable r) {
      		try {
      			acquireReadWrite();
      			r.run();
      		}
      		finally {
      			release();
      		}
      
      	}
      
      }
      
      
    4. Now use your RWLock object properly in the Account object you installed, and ensure that it passes the test.
    Show your RWLock implementation and demo it working correctly to the TA.