CSE 132 (Spring 2009)
Lab 3a: Maze setup
(Double Locks and Array Review)
No upload necessary, but demo to TA before leaving
This is the setup of a lab that will take 2 or 3 weeks in its entirety.
Some work will be due each week. For this week, you will apply the
double lock solution you developed in
Studio 4 to eliminate the deadlock present
in the code you are given.
You will also generalize the maze construction beyond the 2×2
maze you are given. This will involve some review of arrays. See
the appropriate CSE131
material for support (or ask TA or prof).
for using the KWIC index and add some interesting features.
You are really encouraged, but not required, to work in groups on this lab.
It's really helpful to have eclipse open on one computer and this lab writeup
visible on another.
- Open eclipse and go to your CSE132 project.
- Save the lab 3a zip to your desktop.
- In eclipse, right click CSE132 and import the zip file
as a general archive file.
- Run the Lab class as a Java Application. Here's
what you should be seeing:
- All of the real work is achieved from the Maze class.
Maze's initMaze() method sets up a 2×2 maze
The frame you see is divided into 4 equal-sized sections, each representing
a room. You see a label at the top left of each section showing the room
For example, you should see Room 0 with no brackets
- Centered within each section, you see a larger colored rectangle
that itself contains other smaller rectangles.
- The larger rectangle, which may be changing color now and then, represents
a room, and in particular, a Set associated with that room.
Initially, each room is in its own set. That set is shown in text above
the larger rectangle. For example, [Room 0] is shown just
above the larger rectangle representing Room 0.
- Hallways (you cannot see, but you will add visualizaitons for these)
run up-and-down and left-to-right
between the rooms that you do see. There are no diagonal hallways.
- The code you are executing (in the Maze class
repeatedly does the following:
- Maze.workMaze() picks a Hall h at random. That hallway connects two
rooms, possibly horizontally, possibly vertically.
- Maze.workMaze() calls Hall.attempToConnectRooms()
on the randomly chosen Hall.
- The Hall.attempToConnectRooms()
method tries to get a lock on each of the two rooms, using
This is reflected by the smaller rectangles in each room. Each one depicts
the status of its adjoining hallway trying to get a lock:
No attempt is currently pending to get a lock on the Room.
- Red: the hallway is attempting to
get a lock on the Room.
- Green: the hallway has
a lock on the Room.
- Once a lock is held on both of the Hall's rooms,
the code inside Hall.attempToConnectRooms() makes each
Room's Set equal to the union of the two
Rooms. This is reflected in the text you see, but not
yet in the color of the room.
- At this point, you should be able to narrate the story shown before
you to a TA or a prof.
Don't go forward until you can narrate the story, explaining what the
halls, rooms, sets, etc. are doing as you watch things change.
When you are good at that, increase the pace of the lab by
changing the sleep time in Lab.sleep. Remmeber that the
value used there is in milliseconds (thousandths of a second).
- As with the Dining Philsophers of Studio 4,
let this program run until you see deadlock.
Explain to a TA or the prof what you see and what it means before you
- (5 minutes)
OK so you've seen this before. Take a look at the
DoubleLock implementation that came with this zip, and
observe that it operates unsafely.
Replace my implementation with one that works, and run the application again.
Make sure you never see deadlock any more. Remember you can increase
the pace of the Lab by modifying Lab.sleep().
- (15 minutes) When the Set associated with a Room changes,
the color chosen in SetViz is random. Let's make it dependent
on a Room's Set, so that two Rooms are in
the same Set, then their visualization will appear the same color:
Open SetViz in eclipse and look at the method
computeColor. Fix that method so that it computes
a Color based on the hashCode() of the Room's
Follow the advice given in comments for computeColor so that
you pick colors that will work with the rest of this lab.
- (40 minutes) The Maze as given to you creates only a
2×2 maze. Let's generalize this to any number of rows and columns:
- The only method you have to modify is
initMaze() in Maze.
- Maze already has two int instance variables
rows and cols.
- You should draw and think before you code.
Sketch out the maze on paper with labels to show rows and columns.
Check the conditions that should hold true for a horizontal or vertical
hall to be placed between two rooms.
- Using your CSE131 Jedi array skills, fashion an array of
the objects you need to represents Rooms and iterate over
them to adjoin them correctly with the right kinds of Halls.
Important: You must call the HorizHall(r1,r2) constructor
with Room r1 to the left of (west of) r2.
Likewise, you must call the VertHall(r1,r2) constructor with
Room r1 above (north of) r2.
- Be sure to change the GridLayout of the Container to
have the right number of rows and columns for your larger maze.
- Be sure to add any Rooms you make to the rooms list.
- Be sure to add any Halls you make to the halls list.
- Be sure to add a new RoomViz to viz for each
Room you make.
Demo your work
To receive credit for lab 3a, simply grab a demo sheet and
demo your efforts to a TA.
He or she will look over your code and you will get full credit for this lab
if all is well.
If you have time, take a look at Lab 3b. This will
be discussed in class next week.
Last modified 20:10:47 CST 11 January 2010
by Ron K. Cytron