Programming Assignment III

Due on Friday, October 30, 2009 @ 11pm

70 points

Baboons Crossing a Canyon

A canyon cuts through the territory of a colony of baboons. The baboons use a rope stretching across the canyon to cross from one side to the other. The rope is strong enough to permit any number of baboons to cross in the same direction at the same time. However, the rope is too thin for the baboons to cross the canyon in both directions at the same time. Consequently, a baboon that wants to cross from west to east must wait until all westward-moving baboons have finished crossing and the rope is free. If the rope is being used by westward-moving baboons, then other baboons may start to cross from east to west no matter how many eastward-moving baboons are waiting on the other side.

Unfortunately, this simple protocol could cause starvation. Why? Figure it out yourself. To overcome this problem, when a baboon that wants to cross to the east (resp, west) arrives at the rope and finds baboons crossing to the west (resp., east), it waits until the rope is empty, but no more westward-moving (resp., eastward-moving) baboons are allowed to start crossing until at least one waiting baboon has crossed the other way.

In the system, baboons are simulated by threads. Initially, there are e > 0 baboons going eastward, and w > 0 baboons going westward. Each baboon makes t > 0 trips and then disappears forever (i.e., exits the system). Each eastward-moving (resp., westward-moving) baboon goes to the east (resp., west) end and magically comes back to the west (resp., east) end for the next trip. This repeats t times. The following shows a template of a baboon thread, where DIRECTION is the moving direction, and GetOnRope() and GetOffRope are monitor procedures:

for (int i = 1; i <= t; i++) {
     Delay();                     // plays for a while       
     GetOnRope(DIRECTION, ...);   // makes a request to move on the rope
     Delay();                     // has the permission     
                                  // gets on the rope and        
                                  // moves for a while
     GetOffRope(DIRECTION, ...);  // gets off the rope        
     // at the other end now, print message         
     // magically comes back
}

Your monitor maintains all necessary information to make sure baboons will cross the canyon based on the give conditions. In particular, your monitor must guarantee the following:

Baboons on the rope only move in the same direction.
Baboons must use the rope to cross the canyon. In other word, baboons cannot magically cross the canyon and magically come back. This magic only applies to the returning trip.
No baboon can get on the rope without a permission.
When a baboon arrives and there are baboons on the rope moving in the opposite direction, no baboon can get on the rope and move in the opposite direction. More precisely, if a eastward-moving baboon arrives and there are a number of westward-moving baboons on the rope, then no other westward-moving baboons, whether they are waiting or just arrive, can be on the rope.

Write a C++ program using ThreadMentor to simulate this activities. You can only use one monitor to solve this problem. Your program will not be counted as a correct one if any other synchronization primitives are used.

Input and Output

The input of your program consists of the following:

The number of eastward-moving baboons e, westward-moving baboons w, and and the number of trips t to be made for each baboon should be taken from the command line arguments as follows:
```
prog2  e w t
```
Thus, prog2 15 8 12 means there are 15 eastward-moving baboons, 8 westward-moving baboons, and each baboon will make 12 trips. If any one of these command line arguments is 0, the default value 10 should used. For example, prog2 0 3 0 means that there are 10 eastward-moving baboons, 3 westward-moving baboons and 10 trips. You can assume that all command line arguments are non-negative integers, and both e and w are less than or equal to 15.

Your program should generate an output similar to the following:

    Eastward-moving baboon 3 started
Westward-moving baboon 1 started
      Eastward-moving baboon 4 started
         ......
Eastward-moving baboon 1 arrives at the west end
    Westward-moving baboon 3 arrives at the east end
         ......
Eastward-moving baboon 1 is on the rope 
    Eastward-moving baboon 3 is on the rope
      Eastward-moving baboon 4 is on the rope
  Westward-moving baboon 2 arrives at the east end
        Eastward-moving baboon 5 arrives at the west end
    Eastward-moving baboon 3 completes crossing the canyon (1)
Westward-moving baboon 1 arrives at the east end
      Eastward-moving baboon 4 completes crossing the canyon (3)
Eastward-moving baboon 1 completes crossing the canyon (2)
  Westward-moving baboon 2 is on the rope
          ......
  Westward-moving baboon 2 completes all (xx) crossings and retires.  Bye-Bye!

Due to the dynamic behavior of multithreaded programs, you will not be able to generate an output that is exactly identical to the above.

The following output line tells us that the eastward-moving baboon 3 has started:
```
   Eastward-moving baboon 3 started
```
The following output line tells us that eastward-moving baboon 1 arrives at the west end:
```
Eastward-moving baboon 1 arrives at the west end
```
The following output line tells us that eastward-moving baboon 4 completes a crossing. The number at the end of the message indicates the number of crossing this baboon has completed.
```
         Eastward-moving baboon 4 completes crossing the canyon (3)
```
The following output line tells us that eastward-moving baboon 3 is on the rope:
```
      Eastward-moving baboon 3 is on the rope
```
The following output lines show the effect of an important point. After eastward-moving baboons 1, 3 and 4 are on the rope, westward-moving baboon 2 arrives at the other end. Even though eastward-moving baboon 5 arrives at the west end and wants to cross the canyon in the same direction, it cannot get on the rope, because it arrives later than westward-moving baboon 2! Hence, after eastward-moving baboons 1, 3 and 4 arrive at the east end, westward-moving baboon 2 can get on the rope.
```
Eastward-moving baboon 1 is on the rope 
    Eastward-moving baboon 3 is on the rope
      Eastward-moving baboon 4 is on the rope
  Westward-moving baboon 2 arrives at the east end
        Eastward-moving baboon 5 arrives at the west end
    Eastward-moving baboon 3 completes crossing the canyon (1)
Westward-moving baboon 1 arrives at the east end
      Eastward-moving baboon 4 completes crossing the canyon (3)
Eastward-moving baboon 1 completes crossing the canyon (2)
  Westward-moving baboon 2 is on the rope
```
The following output line tells us that westward-moving baboon 2 has completed all of its required trips, indicated by the number in parenthesis, and retires:
```
  Westward-moving baboon 2 completes all (xx) crossings and retires.  Bye-Bye!
```
Note the indentation in the output. More precisely, baboons that move in the same direction are numbered as 1, 2, 3, etc. Baboon i has an indentation of 2×i spaces. For easy grading purpose, use the above output style. Do not invent your own output, because our grader does not have enough time to digest your output.

Submission Guidelines

All programs must be written in C++ using ThreadMentor.
Use the submit command to submit your work. You can submit as many times as you want, but only the last one will be graded. A makefile is required. Name your executable prog3.
I will use the following approach to compile and test your programs:
```
make                <-- make your program
prog3 e w t         <-- test your program
```
I may repeat the above procedure several times to see if your program performs correctly.
Your implementation should fulfill the program specification as stated. Any deviation from the specification will cause you to receive zero point.
You should aim for maximum parallelism. That is, implement the solution as stated and make sure all required threads will execute simultaneously. Without doing so, you risk very low grade.
No late submission will be graded.
My rule of grading is deduction based. I assume you always receive 100%. If you missed something, some points will be taken off based on the following rules. Read these rules carefully. Otherwise, you could receive low or very low grade. Click here to see how your program will be graded.

Your programs must contain enough comments. Programs without comments or with insufficient comments will cost you 30%.

For each program, the first piece should be a program header to identify yourself like this:

// ----------------------------------------------------------- 
// NAME : John Smith                         User ID: xxxxxxxx 
// DUE DATE : mm/dd/yyyy                                       
// PROGRAM ASSIGNMENT #                                        
// FILE NAME : xxxx.yyyy.zzzz (your unix file name)            
// PROGRAM PURPOSE :                                           
//    A couple of lines describing your program briefly        
// -----------------------------------------------------------

For each function in your program, include a simple description like this:

// ----------------------------------------------------------- 
// FUNCTION  xxyyzz : (function name)                          
//     the purpose of this function                            
// PARAMETER USAGE :                                           
//    a list of all parameters and their meaning               
// FUNCTION CALLED :                                           
//    a list of functions that are called by this one          
// -----------------------------------------------------------

Bad programming style and missing headers will cost you 30%.

Submit a one-page description of your solution, discussing the following issues:
- The logic of your program
- Why does your program work?
- The meaning, initial value and the use of each variable. Explain why their initial values and uses are correct. Justify your claim.
- Convince me that GetOnRope() and GetOffRope(), work properly. More precisely, the following points have to be addressed properly. Make sure you will have a convincing argument for each of these questions. Note that argument such as "because a monitor and condition variables are used to ....., the indicated situation cannot happen" will not be counted as convincing. You should explain why the situation will not happen through the use of monitor and condition variables. Providing arguments like that will receive low or very low grade. To enforce good and convincing arguments for this exercise, the maximum deduction assigned to your README is increased to 50%.
  1. Why do GetOnRope() and GetOffRope() work properly? More precisely, explain to me that your version of GetOnRope() and GetOffRope() can always guarantee
    1. Baboons on the rope only move in the same direction.
    2. Baboons must use the rope to cross the canyon. In other word, baboons cannot magically cross the canyon and magically come back. This magic only applies to the returning trip.
    3. No baboon can get on the rope without a permission.
    4. When a baboon arrives and there are baboons on the rope moving in the opposite direction, no baboon can get on the rope and move in the opposite direction. More precisely, if a eastward-moving baboon arrives and there are a number of westward-moving baboons on the rope, then no other westward-moving baboons, whether they are wait or just arrive, can be on the rope.
  2. You must terminate your program gracefully. More precisely, after all baboons complete t trips, your program terminates, and your program cannot terminate if there are baboons on the rope and waiting on either end of the canyon.
Name this file README rather than readme or Readme. Spell check this file; otherwise, you may risk lower grade.
Missing README costs you 50%, poorly written README costs you 50%, and submitting a non-text file costs you 30%.
Programs not written in the guidelines for monitors receive no more than 50%.
The use of any other synchronization primitives (e.g., mutex locks and semaphores) receives no more than 50%.
Not-compile programs receive 0 point. By not-compile, I mean any reason that could cause an unsuccessful compilation, including missing files, incorrect filenames, syntax errors in your programs, incorrect makefile and so on. Double check your files before you submit, since I will not change your program to make it work.
Compile-but-not-run programs receive no more than 50%.
Compile-but-not-run means you have attempted to solve the problem to certain extent but you failed to make it working properly. A meaningless or vague program receives no credit even though it compiles successfully. Another common problem is that your makefile could successfully process your source files (i.e., compiled successfully); but, your makefile does not generate an executable file with the desired filename (i.e., prog3 in this assignment). If this happens, I will consider your submission as compile-but-not-run.
Programs delivering incorrect result, incomplete result, or incompatible output receive no more than 70%.
You must use the Hoare style monitor and use it properly. Improper uses and/or inefficient uses will cost you 50%.
Each race condition, busy waiting, or deadlock costs you 10%.
All deductions mentioned above are cumulative! This means that even though you have turned in a correct program, you could get very low grade. For example, if your submission does not have the necessary program and function headings (30% off), does not have enough comments (30% off), compiles but not runs correctly (30% off), and contains a race condition, then you will receive 60×(100-30-30-30-10)%=0 points.
Programs submitted to wrong class and/or wrong sections will not be graded.
Your submission should include the following files:
1. File thread.h that contains all class definitions of your threads.
2. File thread.cpp contains all class implementations of your threads.
3. File rope-monitor.h contains the class definition of your monitor.
4. File rope-monitor.cpp contains the class implementation.
5. File thread-main.cpp contains the main program.
6. File Makefile is a makefile that compiles the above three files to an executable file prog3. Note also that without following this file structure your program is likely to fall into the compile-but-not-run category, and, as a result, you may get low grade. So, before submission, check if you have the proper file structure and correct makefile. Note that your Makefile should not activate the visualization system.
7. File README.
Always start early, because I will not grant any extension if your home machine, your phone line or the department machine crashes in the last minute.

Since the rules are all clearly stated above, no leniency will be given. So, if you have anything in doubt, please ask for clarifications.
Click here to see how your program will be graded.

A Hint

Study the readers-writers and bridge-crossing problems and their solutions carefully.