Project 1

Due Monday, Feburary 5, 2007

Note: You are responsible for reading the web forum and making sure to follow any notes or updates posted about the project there.

Introduction

In this project, you will write a simple multi-threaded simulation in Java, and a tool to check that the output is sensible.

The Simulation

Your program will simulate a building containing a set of elevators, with people entering and exiting the elevators at various times. All the elevators should run in parallel, as should all the people (so the total number of threads in your system should be at least the number of elevators plus the number of people). I should be able to run your simulation with

java Simulation n f file

where n is the number of elevators (numbered consecutively starting from 0), f is the number of floors (numbered consecutively from 0), and file is the name of a text file describing the people's behavior. The simulation ends when every person has visited all the floors they wanted to visit. The file should consist of a sequence of lines each of the form

name [f0; f1; ...; fn] t s

where

name is a string containing the person's name
[f0; f1; ...; fn] contains a list of floor numbers that the person wishes to go to, in order from f0 to fn
t is the time, in seconds, that the person spends on each floor after they leave the elevator
s is the floor the person starts on.

For example, a file containing

bill [1; 2; 0] 2 0
bob [2; 1; 0] 2 0

would mean that both bill and bob start on floor 0, bill goes to floor 1, waits 2 seconds, then goes to floor 2, waits 2 seconds, and then goes to floor 0 and waits 2 seconds; and bob goes to floors 2, then 1, then 0, waiting 2 seconds upon arriving at each floor.

As the people participate in the simulation, they should print out messages to standard output saying what they are doing:

name waiting on f for floor g should be printed when name is currently on floor f and is waiting to board an elevator to go to floor g
name taking elevator e should be printed when name boards the elevator numbered e
name arrived at floor f should be printed when name disembarks from the elevator at floor f

All of these messages should each be printed on their own line. Collectively, this trace output captures what happened during the simulation.

Elevator e should start at floor e mod numFloors, where numFloors is the total number of floors in the building. Each elevator may hold at most 3 people. When an elevator arrives at a floor, it should print

Elevator e arrived at floor f

where e is the elevator number and f is the floor number. Then the elevator should sleep for 1 second, during which time people may enter or exit the elevator. After the elevator wakes up, it should print

Elevator e serviced floor f

An elevator should service every floor it reaches, and the floors must be serviced in order (i.e., after servicing floor 1, the elevator should either service floor 2 or 0 next, depending on its direction.)

To keep things simple, we will use the following algorithm to control the elevators: Every elevator will begin moving up, until it has serviced the top (highest-numbered) floor, and then it will switch and move down, until it reaches floor 0, and then switches direction etc.

Important note: In Java, the output of multiple threads can be interleaved arbitrarily. To make sure the output trace from your execution makes sense, you should do two things when you print to standard output: First, make sure that you print before releasing a lock (i.e., in the critical section with the action that you are printing a message about); second, be sure to invoke the flush method to flush standard output after each print statement.

The Verifier

The other part of this project is to write a program to verify that the output of your simulation makes sense. Because the simulation is non-deterministic, the sequence of events is not guaranteed to be the same on each run, but there are certain invariants that must hold. In particular:

Every person should visit all the floors they intended to visit, in the order they intended.
The elevators should start at the specified floor, then move up or down as appropriate.
Each elevator may hold at most three people, and each person should be either on a floor or inside one elevator.
Floors should be serviced in order
People should depart from the elevator on the floor they wanted to. (Note that due to the scheduler, it is possible that a person may get stuck in an elevator, and may not be able to get out until the elevator comes back to the floor they wanted.)

To run your verifier, I will do the following:

java Simulation n f file > out.txt
verify n f file out.txt

where verify is the name of your program to verify the output. If the output verifies, your program should print yes, otherwise it should print no, along with a helpful message explaining what failed to verify. Be sure to include a README file telling me how to run your verifier, and make sure I can run it on junkfood.

You may write your verifier in any language. I recommend a scripting language with support for regular expressions, but languages like C, Java, or OCaml should also be fine.

Collaboration

All of the work on your project should be your own, but for this project only, you may collaborate in the following two ways:

You may share sample simulation inputs with the whole class by posting them on the web forum.
You may share sample verifier inputs (i.e., simulation outputs), also on the web forum.

When grading your projects, I intend to use different people's verifiers on different people's output.

CMSC 838F, Spring 2007

Language-Based Techniques for Concurrent and Distributed Software

Project 1

Introduction

The Simulation

The Verifier

Collaboration