Programming Assignment II

Due on Friday, October 16, 2009 @ 11pm

70 points

Santa Claus

Santa Claus sleeps in his shop up at the North pole, and can only be wakened up by either all nine reindeers being back from their year long vacation on the beaches of some tropical island in the South Pacific, or by some elves who are having some difficulties making the toys.

One elf's problem is never serious enough to wake up Santa (otherwise, he may never get any sleep). So, the elves visit Santa in a group of three. When three elves are having their problems solved, any other elves wishing to visit Santa must wait for those elves to return. If Santa wakes up to find three elves waiting at his shop's door, along with the last reindeer having comeback from the tropics, Santa has decided that the elves can wait until after Christmas, because it is more important to get his sleigh ready as soon as possible. It is assumed that the reindeers don't want to leave the tropics, and therefore they stay there until the last possible moment. They might not even come back, but since Santa is footing the bill for their year in paradise. This could also explain the quickness in their delivering of presents, since the reindeers cannot wait to get back to where it is warm. The penalty for the last reindeer to arrive is that it must get Santa while the others wait in a warming hut before being harnessed to the sleigh.

Here are some specifics. For each elf, he waits for two more elves in order to wake up Santa. A group of three elves submit their problems to Santa and wait until their problems are answered. Then, go back to work until a new problem comes up.

For each reindeer, it tans on the beaches for some time and returns to paradise. If all reindeers (say 9) have returned, the last (i.e., the 9th) one wakes up Santa and all nine wait to be attached to the sleigh. Then, fly off to deliver the toys and head back to the Pacific island.

The Santa takes some rests until (1) all reindeers have come back or (2) there are three elves posting questions. If it is the first case, Santa calls up all reindeer except the one who waked Santa up, setup sleigh for each reindeer. Then, the team flies off to deliver toys for a while and returns. Finally, release all reindeers. If it is the second case, Santa lets all three elves in and solves the (three) problems that the elves bring in. After solving the problem, Santa goes in bed again!

Well, Santa may want to take a long vacation as everybody does. So, Santa has made a decision that after delivering toys for some number of times (say 10), he will lay off all elves and reindeers and call for a quit. That is why you have not received toys from Santa for many years!

Each elves is a thread with the following pattern: 

while (1) {
     Delay();                 // make toys
     AskQuestion(...);        // encounter a problem
     Delay();                 // problem solved, take a rest
}

AskQuestion() is a function. When an elf has a question, he calls AskQuestion(), which blocks the calling elf until a gang of three is possible. When the control returns, the question is answered.

The following shows a reindeer thread: 

while (1) {
     Delay();                 // tan on the beaches
     ReindeerBack(...);       // report back to Santa
     WaitOthers(...);         // wait for others
                              // Don't forget: the last wakes up Santa
     WaitSleigh(...)          // wait for attaching sleigh
     FlyOff(...);             // fly off to deliver toys
                              // Santa will let go all reindeers
     Delay();                 // prepare for vacation
}

ReindeerBack(), WaitOthers(), WaitSleigh() and FlyOff() are all functions. Reindeers come back one by one. When it comes back, it calls ReindeerBack() to register this event. Then, it calls WaitOthers() to wait for the other reindeers. Keep in mind that the last reindeer must wake up the Santa. After a reindeer returns from the call to WaitOthers(), all reindeers will act as a group. Next, all reindeers call WaitSleigh(), waiting to be attached to a sleigh. Again, all reindeers act as a single group. Once this step completes, all reindeers fly off as a single group to deliver toys.

The Santa thread looks like the following: 

while (not retire) {
     Sleep(...);              // take a nap
                              // wakened up by elves or the last reindeer
     what is the reason?      // note that toy delivering is more important
     if (all reindeers are back) { // delivery has a higher priority
          // gather all reindeers
          // put on sleigh
          // and fly off
          Delay();            // Santa delivers toys
          // release all reindeer for vacation
     }
     if (elves have a question) { // there many be a # of groups waiting
          // let elves in
          Delay();            // solve their problem
          // solve the problem and release elves
     }
}

Santa sleeps first with function Sleep(), which means he is blocked until three elves ask questions, or the last reindeer wakes him up. Santa always takes care the reindeers first. If Santa is wakened up by the last reindeer, he releases all waiting reindeers. Santa waits all reindeers are there. Then, he attaches the sleigh (this is the reason that all reindeers must act as a single group). After the sleigh is attached, Santa and reindeers fly off. On the other hand, if Santa is wakened up by elves, he takes some time to solve the problem, and releases all three elves.

Your implementation must correctly handle the following important situations:

Write a C++ program using ThreadMentor to simulate these activities. Note that you can only use mutex locks and semaphores. 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:

Submission Guidelines

  1. All programs must be written in ANSI C++.
  2. 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 without visual is required. Name your executable prog2.
  3. I will use the following approach to compile and test your programs: 
    make                <-- make your program
prog2 e r t         <-- test your program
    I will repeat the above procedure several times with different command line arguments to see if your program performs correctly.
  4. Your implementation should fulfill the program specification as stated. Any deviation from the specification will cause you to receive zero point.
  5. 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.
  6. No late submission will be graded.
  7. 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.
  8. Since the rules are all clearly stated above, no leniency will be given. So, if you have anything in doubt, please ask for clarifications.
  9. Click here to see how your program will be graded.