Assignment #2 Requirements

The primary purpose of this document is to specify the format of your source code and documentation, and the format of your program's input and output. This enforces some measure of uniformity among the appearance and results of your programs in order to facilitate marking.

Electronic submission procedure

Electronic submission is due electronically by 12:00 on 9 November 2000.
Pick *one* team member to do the submission. If you submit again, you must submit from the same account.
Each problem should be in its own directory containing only source files, data files, output files, documentation files, and a shell script for building the program.
Do not submit any compiled (.class) files.
The shell script should be named "compile".
When I type "./compile" in the directory containing your program, all the .class files should get built.
Documentation can be any format readable on CDF; if you use anything besides ASCII text or PostScript, there should be a README.TXT with explicit instructions on how to view it.

Printed submission procedure

Printed submission is due in class at 14:10 on 9 November 2000.
Clearly indicate your names and student numbers, the assignment number, and the course number(s) on the cover page. Indicate which students are in CSC2204 and which are in CSC468.
All pages must be securely affixed by staples or a paper binder. Paper clips and envelopes are not acceptable.
Margins should be no less than 2.5 cm all around.
Print on one side of the page only.
Your submission must be typed -- no handwriting (you may hand-draw Q2's graph if you wish).

Source code and sample output should be single-spaced and printed with a monospace (fixed-width) font of size no less than 10pt. You are encouraged to use "enscript -2r" to print your program output 2 virtual pages side-by-side in landscape mode, but don't print your source code this way.

Documentation should be double-spaced and printed with a legible font of size no less than 10pt.
Do not print the reference string for Q2.

Approximate mark distribution

Correctness/cleverness: 60%
Style/clarity/internal documentation: 20%
Report/writeup: 20%
Programs that do not compile, run, or take arguments as requested may be severely penalized. If typing "compile" and then trying to run the program with the standard arguments doesn't work, then every extra second it takes me to figure out how to compile and run your program loses you 2% for that problem.

Style/clarity/internal documentation

Rule of thumb: your code must be easily readable and understandable.
Keep line lengths under 81 characters; lines shouldn't wrap on your printed source code.
Pick any standard indentation style and use it consistently.
Comment any code whose purpose is not immediately obvious.
Keep comments as concise and meaningful as possible. You will lose marks if you are needlessly verbose.
Concentrate on documenting not *what* your code does, but rather *why* your code does what it does.
Use a modular, object-oriented paradigm. Keep your methods brief and focused; if any one method is more than a few dozen lines long, that may be a hint to split it up into more specialized methods.
Each non-trivial method should have a header indicating its name, and explanation of its arguments, and its purpose.

Requirements specific to Q1

You need to declare two random number generators: one to generate job arrival time, and one to generate job service time. Seeds to the random number generators will be passed on the command line.
Use the nextDouble() method in your routine(s) for generating service times and arrival times.
See http://java.sun.com/j2se/1.3/docs/api/java/util/Random.html for instructions on declaring and using random number generators with specified seed values.
Your main class name should be called "a2q1". The command-line parameters are the seed value for the arrival time generator, the seed value for the service time generator, the number of simulated CPUs, and the length of the simulation (in number of jobs) in that order.
Your program output should be in the following format:

-------- START OF FCFS SIMULATION ----------

Time Job # Action Service time left

-------- --------- -------------- -----------------

3.0023 0 arrives 14.2435

3.0023 0 gets CPU 1 14.2435

5.2701 1 arrives 2.0010

5.2701 1 gets CPU 2 2.0010

6.0006 2 arrives 3.1416

7.2711 1 finishes 0.0000

7.2711 2 gets CPU 2 3.1416

119.2499 14 finishes 0.0000

127.7730 13 finishes 0.0000

-------- END OF FCFS SIMULATION ----------

-------- START OF SRTF SIMULATION ----------

Time Job # Action Service time left

-------- --------- -------------- -----------------

-------- END OF SRTF SIMULATION ----------

-------- START OF RR SIMULATION ----------

Time Job # Action Service time left

-------- --------- -------------- -----------------

-------- END OF RR SIMULATION ----------

-------- START OF HRRN SIMULATION ----------

Time Job # Action Service time left

-------- --------- -------------- -----------------

-------- END OF HRRN SIMULATION ----------

Summary of job waiting time:

Algorithm Mean Variance Maximum

--------- -------- -------- --------

FCFS 8.2255 1.4458 13.7123

SRTF 7.8534 1.5835 11.2216

RR 5.2135 3.1124 11.2275

HRRN 3.7530 0.9899 5.8800

Line up numerical columns to the decimal place if possible; use at least four digits of precision after the decimal point.
Submit typescripts ("man script" for instructions) for the following test cases:

java a2q1 23 32767 1 15

java a2q1 23 32767 2 15

java a2q1 2048 5555 1 14

java a2q1 2048 5555 2 14

Name the typescripts test1.txt, test2.txt, test3.txt, and test4.txt. Include them with both your electronic and paper submission.

For external documentation, prepare a short report (one to three double-spaced pages) indicating how you solved the problem and giving a general overview of how your program is structured.
For the purposes of statistical accuracy, run your simulation with a fairly large number of jobs. Using the results, prepare another short report (no more than one double-spaced page) discussing the relative strengths and weaknesses of the various scheduling algorithms.

Requirements specific to Q2

Name your main class "a2q2".
The command-line parameter should be the name of the file containing the reference string.
Sample execution:

java a2q2 a3_data.txt

Your output should match the following format:

# of page references = 923

======================================================

FIFO

======================================================

Frames 6 10 16

------------------------------------------------------

Page faults 707 701 201

Faults/frames 117.8333 70.1000 12.5625

======================================================

LFU

======================================================

Frames 6 10 16

------------------------------------------------------

Page faults 514 444 418

Faults/frames 85.6667 44.4000 26.1250

======================================================

PFF

======================================================

Threshold 8 12 16

------------------------------------------------------

Frames (total) 3322 4419 5527

Frames (mean) 3.5991 4.7876 5.9881

Page faults 407 400 126

Faults/frames 113.0838 83.5492 21.0417

Again, try to line up columns to the decimal place, and use at least four digits of precision after the decimal when printing floating-point numbers.
A large component of your mark will be for cleverness and optimization -- that is, how few passes of the reference string you made when performing the simulation.
Make a typescript of your output using the a3_data.txt file and call it "a2q2_output.txt". Submit it with both printed and electronic formats.
For external documentation, prepare a short report (one to three double-spaced pages) indicating how you solved the problem and giving a general overview of how your program is structured. Indicate how many passes of the reference string you used.
Using your results and the graph thereof, prepare another short report (no more than one double-spaced page, excluding the graph and results table) discussing the relative strengths and weaknesses of the various page replacement algorithms.