CSE 132 (Spring 2011)
Lab 3a: Maze setup
(Double Locks and Array Review)
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).
You are really encouraged, but not required, to work in groups on this lab.
- If the exact same people are involved, you can use the group name
that you used for Lab 2a. Feel free to ask for
a new group name if your groups have changed or if you want a fresh start.
It's really helpful to have eclipse open on one computer and this lab writeup
visible on another.
- Open eclipse and update your workspace to see the code for this lab.
All of the code is in the lab3a and its subpackages. The structure
is like that you saw in Studio 4.
- Run the Lab class as a Java Application. Here's
what you should be seeing:
- In addition to the visualization, there is a logging trace of the
StatusChanger PCS activity in the console window. This shows
when locks are requested, granted, released, and shows when rooms
are changing their sets (see below).
- 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.
For now, ignore the color of the larger rectangles, but look at the
gray, red, and green of the hallways (described below).
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 eventually 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.
For example, above rooms 2 and 3 you might see the set written as
[Room 2, Room 3], but the colors of the two rooms are
currently different (we'll fix that, to show that they are in the same
set, later in this lab session).
- 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 DELAY value in Lab. Remeber 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. If things are too slow,
then decrease the DELAY in Lab.
Explain to a TA or the prof what you see, and what it means in terms
of deadlock, 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 the code in DoubleLock with the code you developed
in Studio 4 that works,
and run the application again.
Make sure that you never see deadlock any more. Remember you can increase
the pace of the Lab by modifying DELAY in Lab.
- (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.
If you have time, take a look at Lab 3b. This will
be discussed in class next week.
Submitting your work
A TA will demo you or your group on the day the lab is due.
Before asking the TA to demo you:
- Make sure you completed the cover-sheet
- Make sure your work is committed
- All team members must be present
When you done with this lab, you must be cleared by the TA to receive credit.
- Commit all your work to your repository
- Fill in the form below with the relevant information
- Have a TA check your work
- The TA should check your work and then fill in his or her name
- Click OK while the TA watches
Last modified 05:29:00 CST 17 February 2011
by Ron K. Cytron