George Mason University
DEPARTMENT OF COMPUTER SCIENCE

CS571 Operating Systems Fall 2001

Project P1 (Group Project, 20 points)

Due 10/16/01




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.