George Mason University

CS571 Operating Systems Spring 2002

Project P1
Report 15 points
Exhibition 5 points

Due 3/5/02

Before doing these problems, read Chapter 7.7 Monitors (page 216ff) from Operating System Concepts, or chapters on monitors from another book.

The objective of this project is to implement the elevator controller of Assignment A2 in Java and use it as the heart of a simulation in which you collect statistics about elevator usage and compare elevator policies.

This is a group project. Work on this project as a team and hand in a single report.

The result of the project is a brief engineering about the simulations of the elevator controller, with findings and recommendations about which elevator policy is best. 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.

Start this project with a solution to the elevator controller of Assignment A2. The solution for A2 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 passengers using the elevator. Your controller will tell each passenger, represented by a thread, when to enter the elevator and when to exit. The passenger threads are programmed as loops, representing the same (or another) person coming back to use the elevator again. The total number of passenger threads represents the total population of the building in which the elevator is situated.

Let D represent the delay in the passenger loop before the elevator interaction. Recall the elevator timing parameters: 15 seconds to move from one floor to the next, and 2 seconds for each passenger to board or exit. Normally, D will be many minutes.

Develop a simulator that will create N threads each using the same delay D. You will need to add some data-collection statements to the UP, DOWN, SELECT, and passenger-exit operations so that you can measure how long a passenger takes in the elevator interaction.

Get your simulator working with N=10 and D=5 minutes. Measure the average waiting time (from UP/DOWN push to elevator entry) and the average trip time (from UP/DOWN push to elevator exit). Try N=20, 30, 40, and 50 and plot these averages as function of N. Also try D=1, 5, 10, and 15 minutues and plot these averages as a function of D. Draw conclusions about elevator performance under heavy and light loads.

Try a different elevator policy and see how it affects performance. The policy suggested in A2 is that the elevator moves in a given direction until there are no more requests to enter or exit in that direction; then it goes quiescent or reverses. Another policy is FIFO: the elevator contoller maintains a record of the total state as a list ordered by times at which events occurred; the events are button-pushes of UP/DOWN/SELECT. The elevator visits the floors in order of this list, which can make it suddenly change direction.