CS 3733 Operating Systems, Spring 2007 Assignment 2

Due Monday, February 26

In this assignment you will be using the process scheduling simulator that was discussed in class and used in the recitation sections.

Part 0:
Copy all of the files from your assign2/rec03 directory into a new directory, assign2/main. You should be able to run the simulator from any of our Linux machines.

How the simulator handles the duration and cpu burst parameters:
There is often confusion about the relationship between the duration of a process and the CPU bursts. The duration represents the total CPU time the process will use and is calculated when the process is created. The simulator keeps track of the total CPU time used by each process. When a process finishes its CPU burst, a the total CPU time used is updated. If this is equal to the duration, the process terminates without doing any additional I/O. Otherwise, a new I/O burst time is calculated.

When a process enters the ready queue, the simulator uses the cpu burst distribution to calculate the next CPU burst time. This is compared to the difference between the duration and total CPU time used so far. If necessary, the calculated CPU burst time is reduced so that the process will not use more CPU time than its duration.

Answer the following question:
Suppose a process uses the following parameters:
duration constant 10
cpuburst uniform 20 30
How many CPU bursts will this process have and how long will they be?

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.

Run the simulator with the default configuration as you did in recitation 3. Calculate the load average for each of the two 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 two 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 two runs from Part 1. You should get the values .286 and .285. Now run the simulator using these context switch times and log the result. You can do a run with context switch time 0.286 by adding the following to the end of a run line in the exp file:
cstin 0.285
For example you can use the following exp file for this experiment: 
name myexp
comment This experiment contains 4 runs and tests context switch time.
run myrun algorithm FCFS key "FCFS"
run myrun algorithm SJF key "SJF"
run myrun algorithm FCFS key "FCFS cstin .286" cstin .286
run myrun algorithm SJF key "SJF cstin .285" cstin .285
Analyze the results and see if it agrees with your calculation.

Part 3:
Start by copying the files from assign2/main into a new directory, assign2/part3. You will modify these files to do a new experiment.

Part 3a:
Design an experiment in which preemptive shortest job first performs much better than the non-preemptive version. The preemptive version should have an average waiting time of at least 20 percent less than the non-preemptive version. The experiment should have two runs that are identical except for the algorithm used and both should use the default context switch time of 0. Each process should have at least 5 CPU bursts and there should be at least 5 processes.

Run the experiment and produce a log file containing the tabular data.

Part 3b:
Think about how the context switch time will affect the average waiting time in the two runs of your experiment. Use the method of Part 2 to estimate the average waiting time of each run when the context switch time is about 10 percent of the smallest CPU burst. Then run the simulator with this context switch time an compare the result to your calculation. Your experiment should have 4 runs, two identical to those in Part 3a and two with the same non-zero context switch time.

Part 3c:
You would expect that preemptive SJF will have more context switches than the non-preemptive version, and so increasing the context switch time would increase the average waiting time more for PSJF than SJF. This is not always the case. Under what conditions would PSJF do better relative to SJF as the context switch time is increased?

Handing in your assignment
Use this cover sheet. Consecutively number all of the other pages you turn in except for the log files from Part 3. 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.

Similarly, write out your calculations for Part 3b and compare them with the results of your runs. Also, write out your answer to Part 3c. You do not have to put each of these on a separate page, but clearly label each one. Put the required numbers from the experiment in Part 3 on the answer sheet.

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.