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

Review studio procedures, if necessary, before starting.

Some guidelines for this week's studio:


Problems:

  1. Readers/writer locks
    1. In the studio5 of your studio workspace, run the Bank class as a Java application.
      You should see race conditions similar to what you saw in Studio 3. We will fix those, but using a different concurrency control mechanism.
    2. Review the BoundedInteger implementation from class this morning, which has been included in your studio workspace.
    3. Based on what you learned in class about interprocess communication, complete the RWLock class to implement a readers/writer lock.
      Your implementation should allow only one of the following statements to be true at any given point in a program.
      • There are currently no readers or writers.
      • There is currently a positive number of readers but no writer.
      • There is currently exactly one writer but no readers.
      Things to think about:
      • Your implementation must keep track, reliably, of the number of readers and writers that have a given RWLock on an object. What does your implementation need to do this and how do you avoid race conditions?
      • Stick to the pattern taught in class about how processes threads should use notifyAll and wait.
      • Remember that you should only hold any lock for as long as you really need it. Extending that principle to readers/writer, you should only obtain writer lock when you really need it. Use readers locks whenever possible.
    4. Now use your RWLock object properly in the Account object you installed, and ensure that it passes the test.

  2. How can we tell a good maze from a bad one?
  3. 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, and that is the only path between those rooms.

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


    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.
    Complete the questions in feedback.txt for this part.

Submitting your work (read carefully)



Last modified 08:59:28 CDT 03 June 2010 by Ron K. Cytron