SI411 Operating Systems Fall AY07

Team Programming Project 1

Due: Close of Business, Friday, October 20, 2006

 Close of business is defined as under my office door prior to my arriving to work the next work day (usually around 0800). If you slide your project under my door after the due date, write the date and time that you slid it under my door to stop any late penalty computation, otherwise the project will be considered to have been placed under my door just moments before I arrived.

For the purposes of COMPSCIDEPTINST 1531.1C (available http://www.usna.edu/CS/academics/honor.htm)

this programming project is designated as a Team Programming Project, and as such midshipmen may give no assistance whatsoever to any person not on their assigned

team and may receive no assistance whatsoever from any person not on their assigned team other than the assigning instructor.  Further, midshipmen may not use information

in any format, electronic or printed, other than their own or a teammate’s class notes, the course textbook, or materials distributed by the instructor.

If midshipmen wish to use additional sources, they must receive explicit permission from their instructor.

Background: In this project, you will put the author's "rule of thumb" concerning round robin scheduling's time quantum size to the test. The author's rule of thumb (see page 186 of the course text) is that "...80% of the CPU bursts should be shorter than the time quantum". Your task is to implement a Java-based Round-Robin scheduler and perform simulation runs to determine the effects of varying the quantum size. You are to work within your assigned software development team (see course web page for team assignments), and follow the guidelines given in the course policy (and reiterated above) regarding collaboration. Start this project from scratch (ie., do not start from the round robin scheduler code discussed in Chapter 6). 

You may make the following assumptions:

  1. All jobs arrive at time zero.
  2. All jobs are essentially CPU bound. This means that for the purposes of your simulation, you can assume that jobs do not perform I/O (i.e., they have only ONE CPU burst, although it may take several quanta to complete the burst).
  3. You may assume that there will be exactly 10 jobs in any given batch of jobs.
  4. The CPU burst for each job will be a positive value.

 

Early/Late policy: As per the course policy, projects turned in after the submission deadline will incur an automatic deduction of 3n points where n represents the number of work days (rounded up for fractions of days) after deadline passage. For early submissions, 3n extra-credit points (up to maximum of 9 points) will be awarded, where n represents the number of days early that the project was submitted (not including the day the project is due). 

 

Requirements:

  1. Variable names, commenting. Your Java program is to be well commented that uses a descriptive naming convention. For classes, capitalize the beginning letter of each word in the class name (ie., ClassName). For constants, capitalize all letters, and put underscores between interior words (ie., DEFAULT_TIME_SLICE). For objects/variables, capitalize only the first letter of interior words (ie., numContextSwitches). Note that numCS would NOT be considered a descriptive variable name.  

 

  1. Input. The program will present the user with a choice of either using static input for burst lengths or use random burst length generation:

 

    1. Static Input: If the user selects "Static Input", your program will use EXACTLY the following input: 1 10 3 9 4 7 4 7 5 6 which represents the burst requirements of the 10 jobs your program is to schedule. You may assume the first integer listed is Job1, the second integer listed is Job2, etc. The above 10 integers map to Job1 having a burst time of 1, Job2 having a burst time of 10, Job 3 having a burst time or 3, Job 4 having a burst time of 9, …,etc.

                          

    1. Random Burst Length Generation: If the user selects "Random Generation", your program will randomly generate 10 integers between 1 and 10 (inclusive), except that you must write your random number generator such that the bursts produced for the jobs generally complies with the Histogram in Figure 6.2 of the text (meaning that most of the bursts are in the 1-5 range, followed in frequency by bursts in the 6-8 range, and bursts in the 9-10 range occur least frequently).  Assume that the first integer you generate will be the burst for Job1, the second integer generated will be the burst for Job2, etc. 

 

  1. Time quanta. Based on the 10 job bursts from part 2a or 2b, your program is to then determine what 5 different time quantum sizes are needed to ensure that 20%, 40%, 60%, 80% and 100% of the jobs finish in one time quantum. As an example, the above data file would indicate a time quantum of 10 was needed to get 100% of the jobs finished in one time quantum each.  Hint: Load the job bursts into an array, sort the array. The largest cell will contain the time quantum needed to ensure 100% of the jobs complete in one burst.

Note: You are encouraged to get requirements 1, 2, and 3 working before you attempt requirements 4 and 5.

  1. Multi-threaded Programming. Your program is to then launch 5 separate Java threads that concurrently execute and determine the WaitingTime, TurnaroundTime, and number of ContextSwitches for each of the 10 jobs read from 2a or 2b above. Note that the original (ie, non-sorted) job order is to be used when conducting the simulation.  Each thread must also compute the average WaitingTime, average TurnaroundTime, and total number of Context Switches for the given job sequence. Hints: Write a single thread class that takes as arguments to its constructor the information that it needs to conduct the simulation, such as time quantum size, name of file to write to, etc. Then create 5 thread instances that each take on an appropriate time quantum from 3 above. Also, make sure your threads manually copy any arrays as needed so that each thread has its own version of the array that it can manipulate, rather than having all threads use a reference to the same array.

 

  1. Output. EACH thread is to write the following information specific to its time quantum percentage to one of 5 output files. The output files are to be named as follows, and contain the appropriate thread output:
    1. "output20.dat",
    2. "output40.dat",
    3. "output60.dat",
    4. "output80.dat",
    5. "output100.dat".
  1. Data Analysis.

For the data collected from your program when input from 2a was selected:

For each time quantum size, the following output is required in tabular form (with the X's replaced with the actual data):

Round Robin Scheduling Algorithm with Quantum size XX

Job #  Burst   Wait-Time  Turnaround-Time   # of Context Switches

XXX   XXX     XXX         XXX                    XXX

XXX   XXX     XXX         XXX                    XXX

...

Average Burst Time: XXX.XX

Average Waiting Time: XXX.XX

Average Turnaround Time: XXX.XX

Percentage of jobs that finished on the first pass: XX %

Total number of context switches: XX

 

For the data collected from your program when input from section 2b was selected:

-        Run your program 10 times using the input choice from section 2b.  Manually record the following information for each run:

o       The 10 sets of randomly generated integers, in original unsorted order.

o       The average wait time, turnaround time, and # of context switches for burst sizes (20%, 40%, 60%, 80%, 100%) for each of the 10 sets (so, there should be 10 sets with each set having an avg wait time, an average turnaround time, and the # of contest switches).  

 

Deliverables: Turn in ONE of each of the following PER TEAM by the deadline on the top of this project specification:

1. Paper copy of all source code. Include the following as comments at the top of each file you turn in:

·         the names of the midshipmen in your assigned team,

·         the filename of the source code, and

·         a brief description of the source code in the file.

2. A paper copy of each of the five output files from part 5 above, when run on the input discussed in Requirements section 2.A’s static input.  Note that you DO NOT need to turn in the output files from the Random Burst Length Generation in section 2.B

3. Three separate hand drawn or excel graphs that plot the following for the input file in Requirements section 2.A.

a.       Average Turnaround time vs. % of jobs that complete in 1 time quantum

b.      Average Waiting time vs. % of jobs that complete in 1 time quantum

c.       Number of context switches vs. % of jobs that complete in 1 time quantum

4.  Three separate hand drawn or excel graphs that plot the following for the data from part Requirements section 2.B.

a.       Average Turnaround time vs. % of jobs that complete in 1 time quantum showing all 10 runs on the same chart.

b.      Average Waiting time vs. % of jobs that complete in 1 time quantum showing all 10 runs on the same chart.

c.       Number of context switches vs. % of jobs that complete in 1 time quantum showing all 10 runs on the same chart.

5. Your conclusions as to whether or not the author's rule of thumb is valid. Support your conclusions by citing the results you show in parts 3 and 4.  Your discussion should be no more than one page in length.

6. Send your instructor an e-mail message with the subject line of “SI411 Project Delivery”.  Include as attachments your final (to be graded) source files and .txt files discussed above.

7. Your project is not considered submitted until all paper copies and the e-mail has been received by the instructor.