CSCI 340: Operating Systems
Spring 2005
Program 4: Multi-Thread Bridge Simulator
Due: Midnight Friday December 9 (this is the last week of classes)
Grading Weight: 3
Overview:

A two-lane north-south road contains a one-lane bridge.  A southbound (or northbound) car can use the bridge only if there are no oncoming cars when the car arrives at the bridge.  In order to prevent accidents, two traffic lights (one at the north end, one at the south end) have been installed on the bridge.  Write a program that simulates the traffic lights and cars crossing the bridge.

You may work by yourself or with one other student.  You may work in a group even if you have done the other assignments independently.  Only one person from each group should turn in the assignment.  Put both names and ecst usernames at the top of your file.

Requirements:

Write a single program (you can put it in a single file such as bridge.cpp or bridge.c) that creates three types of threads:
  1. A main() thread that start the simulation and determines when the simulation is over.
  2. One car generating thread that generates the specified number of cars at random intervals.
  3. Many car threads each of which simulates a single car.
Input:
The bridge program must take two required command line arguments and a third optional argument.  The first is the number of northbound cars, the second is the number of southbound cars, the third is a seed for the random number generator.  For example:

% bridge 100 10 42

Will result in a simulation with 100 northbound cars, 10 southbound cars, and will seed the random number generator with 42.  If the third argument is not given, seed the random number generator using the clock.

Output:
Messages should be written to standard out every time:
  1. A car arrives at the bridge
  2. A car starts driving over the bridge
  3. A car exits the bridge
  4. A signal changes color.
For example, the output from a simulation with 2 northbound cars and 1 southbound car might look like this:
N red
S green
N1 arrived
S red
N green
N1 enters
S1 arrived
N2 arrived
N2 enters
N1 exits
N2 exits
N red
S green
S1 enters
S1 exits
Simulation over

Output the exact same messages as this example.


Simulation Details:
Each car must take a random amount of time on the bridge.  You can use one of the UNIX random functions and one of the UNIX sleep functions to implement this.

Label the cars N1, N2, .. Nn, S1, S2, ..., Sm, where n is the number of northbound cars and m is the number of southbound cars.

Multiple cars may be on the bridge at any time, as long as all the cars are going in the same direction.

Cars cannot pass each other on the bridge.  In other words, a car cannot exit the bridge before all the cars in front of it have exited (all cars that entered the bridge before it).

Cars should not have to wait if there is no opposing traffic.

The actions of the cars should obey the traffic lights.  For example, if the northbound light is red, no northbound cars should enter the bridge.  However, it is possible that a northbound car is still on the bridge when the north light turns red, just make sure the south light doesn't turn green before all the northbound cars are off the bridge.

The creation of northbound cars should be randomly distributed over the entire duration of the simulation.  The creation of the southbound cars should also be randomly distributed over the entire duration of the simulation.  For example, if there are 100 northbound cars and 10 southbound cars, it should be a very unlikely event that the first 20 cars contain 10 northbound and 10 southbound cars.  It would be more likely that the first 20 cars contain 18 northbound cars and 2 southbound cars.

Implementation Details:
Use semaphores to provide thread synchronization.

Do not use busy waits.

Use the POSIX pthread library to create the threads.

Use GNU gcc or g++ to compile your program.

You may implement your program in the cygwin environment, OS X, or Linux.  If you use OS X and it does not work on my Linux machine, you will have to bring your OS X machine to my office and demonstrate the program.
Hints:

I recommend writing a simple two-thread program that uses a semaphore to synchronize the processes before you start on this program.  After you learn how semaphores and threads work, work on the algorithmic portion of the assignment.  You may use my pthread.cpp as a starting point.  void.cpp  gives an example of using void pointers to pass arguments to thread functions.

You can distribute the creation of north and south cars by calculating the ratio of north cars to total cars and then generating a number between 0-1.  If the number is less than the north-total_car ratio then generate a north car.  If it is greater then the ratio generate a south car.  However, you must not generate cars once you have reached the max (that is, if there are 10 south cars and you have already created 10 south cars, all the rest of the cars must be north).

If you use the C/C++ random() function, you will always get the same series of numbers.  Thus every time you run your program you will get the same simulation.  A real simulation should be different every time.  To make random() generate a new series of numbers each time you run your program, you have to set its seed.  An easy way to do this is to use the current time.  Since time never repeats itself, you will get a new seed each time:
srandom(time(0));

The problem with this approach is that it is very hard to debug a program when it generates different random numbers each time you run it.  Thus you don't want to seed using the clock  while debugging.  As an alternative, an optional command line argument can be used as the seed.  Specifically, if there is a 4th command line argument use it as the seed, otherwise use the clock.   This will allow you to experiment during debugging and find seeds that test specific features.
if (argc == 4)
    srandom(atoi(argv[3]));
else srandom(time(0));


You may use the car threads to control the signals.  If you do the extra credit you may find it easier if there is one (or more) dedicated process(es) to control the signals.
Extra Credit (10%)
Modify your solution so that cars are not starved.  For example, northbound cars should not monopolize the bridge if there are southbound cars waiting.

However, northbound and southbound cars should not just take turns.  When several cars are waiting to go in one direction, more than one car should cross the bridge, but the car in the other direction should not have to wait for all the cars to cross.
If you do the extra credit, turn in an ASCII text file called algorithm, that describes the algorithm you used to control how cars cross the bridge.  Include an explanation on how you prevent starvation.
Simulation Viewer:

I've written a program called sim_viewer that graphically displays the output from the bridge simulator program.  It is in the src/sim_viewer directory.  You can download sim_viewer.tar.  The Makefile supports Linux, Cygwin, and OS X, but you have to comment in/out the appropriate libraries.  Read the comments in the Makefile.

Your program must output the messages exactly as described in the project description for the viewer to work.

You can pipe the output from your program directly to the viewer:  % bridge 5 3 | sim_viewer.  Or you can save the output of your program to a file and then direct it into sim_viewer: 

% bridge 10 3 > test01.out   
% sim_viewer < test01.out.

I've provided two sample input files in src/sim_viewer: input.good and input.bad.

Since sim_viewer uses a graphics window, you cannot use it over telnet or putty.

You must install OpenGL and the glut library on your machine to use sim_viewer.  If you run cygwin.exe you can choose to install OpenGL from the graphics menu.  Newer versions of cygwin include the glut library.

On OS X you must reference the OpenGL and GLUT packages when linking.
How to turn in code:
Turn in all the files necessary to make your program work including a Makefile.  My solution contains the files:
bridge.cpp
Makefile

copy your files to the turn in directory for this assignment.

See How to turn in assignments for details on turning in assignments.

If you are working with someone, only turn in one copy of the assignment.  It is very helpful is people working together always turn their assignments in under the same name.  Make sure you list both names at the top of all files.

Late assignments:
You will lose 10% for each 24 hours your assignment is late.

e-mail late assignments to me (create a .tar file for all your files and e-mail the .tar file to me)

It may take me much, much longer to grade late assignments (if I have already graded the other assignments, grading late assignments gets a low priority).

I use the time I receive your e-mail, not the time you send your e-mail as the turn in time (sometimes e-mail from an ISP takes a day or two).  If you want to be absolutely sure your assignment gets to me immediately, e-mail it from your ecst account (use your browser (webmail.ecst.csuchico.edu) to e-mail the file to me).