Before doing these problems, read Chapter
7.7 Monitors (page 216ff) from Operating System Concepts,
or chapters on monitors from another book.
You will also need to refer to the short slide presentation on
a one-lane bridge traffic
controller.
This is a group project. Work on this project as a study
team. Put the names of all members who participate in the
project on the report. The report will be graded as a unit and
the grade passed to each member. See the CS571 web site for
more information on group projects.
This is a programming project. You can use either the
Sun Solaris multithreaded package or Java. You will find
resources about these packages on the CS571 web site.
The objective of the project is to produce a brief engineering
report about simulations of a traffic controller on a one-lane
bridge. In your report, discuss the architecture of your
programs, your experiments, and your
findings. Attach your programs to your report as an appendix.
Be sure to include an acknowledgements section in your report.
In this project you will consider the
design of a controller for car traffic crossing a one-lane
bridge. Study the slides defining the problem and outlining
a solution (see above for the link). These slides present only
a sketch; you will have to fill in many details.
The controller solution outlined in the slides is in the form of a
monitor. A monitor is a programming construct that packages a
set of procedures, private data, and condition variables
together. Many threads can call the monitor in parallel and
the monitor will only execute one of them at a time. Condition
variables are used internally to sequence the threads while
they are inside the monitor.
In addition to the controller, you will implement a simulator
of the cars on the bridge. Your controller will tell each car,
represented as a thread, when to enter the bridge. You can think
of each car as a repeating loop in which the car delays for a random
time (with mean R) before approaching the bridge,
then it arrives at one end of the bridge or
the other, then it waits for permission to enter, then it crosses
in a fixed time C, then it exits the bridge.
The ratio
R/C is a measure the of the "traffic intensity" -- the greater
the ratio, the less often cars come and the less congestion for a
fixed total number of cars.
(1) Examine the solution outlined in the slides. Assuming it
is implemented as a monitor, outline a proof why it works
correctly.
(2) Develop a simulator of cars crossing the bridge with the
help of your controller.
To do this, you will need to
represent the set of cars on the bridge and the directions they
are traveling. The contoller will tell you what cars to admit to
the bridge. The cars themselves are represented as individual
threads. You will need to specify the travel time for cars to
cross the bridge and a random time that it will take a car
(thread) to return to the bridge for another crossing. Test your
simulator for simple cases, such as all cars going the same
direction only and no restriction on the number on the bridge;
collect data to enable you to draw graphs of traffic ratio
versus average number of cars on the bridge.
(3) Implement your simulator with the controller
embedded in it, as a set of routines without
the monitor. In other words, implement the control routines
without any attempt at proper synchronization. Run your
simulation under different traffic conditions and see if it exhibits
invalid behaviors.
(4) Implement your simulator with the controller embedded
within it, as a monitor. Repeat your tests and show that it
exhibits correct behavior.
(5) Summarize your findings and conclusions.