What to do

• Fill in the missing subprogram bodies in modules Simulate and PerfData.
• Write a main program that uses these modules to perform the simulation as described above.
• Thoroughly test all parts of the program, and produce annotated test runs that demonstrate its correctness. Use trace mode judiciously to help show that your program is correct. You may temporarily change things like the capacity of the priority queue in order to force certain testing conditions to arise. Make sure that you explain such things in your testing plan.
• Write an explanation of your testing strategy, to include in your report.

Part B: Experiments

1. Run the simulation 10 times with the following values:

   

   Are all of the results close to each other? If not, why not? How can you make the results come out close without changing the code?

2. Design experiments to find out what happens to the throughput of the system as the inter-arrival time decreases (i.e., as the processes arrive more frequently). Explain your experiments and results.

3. Consider the following combinations of average inter-arrival time and average amount of CPU time required:
   1. average inter-arrival time equals average amount of CPU time required
   2. average inter-arrival time is much smaller than average amount of CPU time required
   3. average inter-arrival time is much greater than average amount of CPU time required
   Under each of these conditions, systematically experiment with various numbers of CPUs. (Keep the other parameters constant, but choose ``reasonable'' values for them). What general conclusions can you draw? Some things to think about: Is it always better to have more CPUs? Does ``performance'' always double when there are twice as many CPUs? What do you mean by performance?

4. Design experiments to determine whether the average wait times are better (i.e., lower) with a time slice limit than without one, and if so, what the limit should be. Explain your experiments and results. Some things to think about: There are several average wait times. Which do we want to be low? Can they all be low?

Part C: Correctness

1. Consider changing the exit statement in procedure PriorityQueue.Arrive's conditional loop to

   exit when (where > count) or (prty <= contents(where).prty)

   Under what conditions would the procedure then work or not work? Use examples to help with your explanation.

2. The priority queue module contains an array called contents that holds the contents of the priority queue, and a variable called count that indicates the number of elements currently in the priority queue. When the module is declared, these are declared and appropriately initialized, and every exported procedure is carefully designed to keep them set up "properly". For instance, after any appropriate call to an exported procedure, it must be true that:

   contents[1..count] contains all the elements that have arrived
   in the priority queue, but have not left it. (1)

   This is a data invariant: something that must be true upon declaration of the module, and after any appropriate call to an exported procedure.

   There are several other data invariants for this module. State them.

3. State appropriate loop invariants for the conditional loop in procedure PriorityQueue.Arrive. Hint: Consider the value of where, and of contents(where).prty.

4. Prove that condition (1) is true immediately after module PriorityQueue has been declared and PriorityQueue.Initialize has been called. This is a very short and simple proof.

How to submit your assignment

• a printout of the complete program (do not hand in a diskette);
• annotated test runs that cover all the cases necessary to show that your program works;
• your report. It is not necessary for this assignment to hand in the complete report that is described in the Course handbook; rather, your report should contain only answers to the questions above (in a section called ``Answers to Questions''), and the standard section on Testing.

The cover sheet provided here (or a photocopy of it) must be filled out, signed, and taped to the envelope containing your assignment.

Some useful advice

The most effective way to get the program done quickly is to spend plenty of time thinking about simulation, priority queues, and the starter code that we have supplied before you try to write your program. (This is probably the most challenging aspect of the assignment.) Trace the code by hand and watch how it works. Try to do this as soon as possible, so that you have plenty of opportunity to go to office hours if you have questions.

When you are ready to begin writing the code necessary to complete the program, write it out on paper, and trace the program by hand before you ever go near a computer, in order to get rid of as many errors as possible.

Try to get the programming parts of your assignment finished early. The computers are likely to be very crowded in the day or two before the assignment is due. Extensions will not be granted just because the printers are backed up; this is a normal situation. Get your printouts well ahead of time.

How your assignment will be marked

It is your job, in your testing, to provide evidence that will convince the grader that your program works. If you hand in no test runs, or poor testing, you will get few or no marks for correctness of your program.

Below is the grading scheme that we currently expect to use. It may be changed somewhat as the assignment unfolds, but should give you an idea of where to focus your efforts.

University of Toronto
csc148 -- Introduction to Computer Science, Fall 1995

Cover sheet for Assignment 2

Complete this page, and tape it to the front of the envelope containing your assignment.