CS 3733 Operating Systems, Fall 2008 Assignment 2

Due Friday, October 3

This assignment is based on the process scheduling simulator that was discussed in class and used in the recitation sessions.

Part 1:
The traditional UNIX CPU scheduling algorithm uses the load average in its calculations. The load average is the average number of processes in the ready queue. This information is available from the simulator but it can also be calculated using Little's Law which implies that the load average is the total waiting time divided by the time for the experiment. The total waiting time is the total for all of the processes. You can find it by using the average waiting time given in the simulator tables and multiplying by the number of processes. The time for the experiment is the time the last process finishes and is given in the table.

Add the following line to the default myexp.exp:
run myrun algorithm PSJF key "PSJF"

Run the simulator with this configuration as you did in recitation 3. Calculate the load average for each of the three runs as described above. Show how you got your answers and confirm that it agrees with the values given by the simulator.

Part 2:
By default, the simulator does not take into account the context switch time or the time the scheduling algorithm uses to pick the next process to schedule. We can take the context switch time into account as follows:

Now, for each of the three runs in Part 1, calculate the context switch time that would add 10 percent to the average waiting time. Do this as follows: Show this calculation for each of the three runs from Part 1. You should get the values .286, .285, and .240. Now run the simulator using these context switch times and log the result. Make sure you include the table data in the log file. You can do a run with non-zero context switch by appending to the run line in the exp file.
For example you can use the following exp file for this experiment: 
name myexp
comment This experiment contains 6 runs and tests context switch time.
run myrun algorithm FCFS key "FCFS"
run myrun algorithm SJF key "SJF"
run myrun algorithm PSJF key "PSJF"
run myrun algorithm FCFS key "FCFS cstin .286" cstin .286
run myrun algorithm SJF key "SJF cstin .285" cstin .285
run myrun algorithm PSJF key "PSJF cstin .240" cstin .240
Analyze the results and see if it agrees with your calculation.

Part 3:
Think about the following statement:
Since PSJF does more context switches than FCFS or SJF, a long context switch time will always increase the the average waiting time more for PSJF than it does for FCFS or SJF.

Decide whether you agree or disagree with this statement.

Now do the following experiment. Run the simulator as in part 2, but use the same context switch time of 0.10 for each of the three final runs. Run the experiment and create a log file containing the table data. Determine the amount of increase in average waiting time between a run with context switch time of 0 and the same algorithm with a context switch time of 0.10. For which of the algorithms does the long context switch time have the largest effect? For which is it the smallest?

Now write a sentence or two describing whether or not you think the statement at the beginning of this part of the assignment is true and why.

Handing in your assignment
Use this cover sheet. Consecutively number all of the pages you turn in. Do the calculations for each of Part 1 and Part 2 on separate numbered sheets. Since you are given the answers, it is important that you show your work to receive credit.

If you have a machine at home with Java installed, you can run the simulator at home by downloading the simulator code. You can download the simulator from here. Put all of the files in a single directory and execute runps in a command window to run the simulator. Make sure you are running version 1.1 or later.