CS 3733 Operating Systems, Fall 2004 Assignment 2

Due Thursday, October 7

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 in the Sun lab as well as in the Linux lab.

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 not directly available from the simulator but it can 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. Show how you got your answers. You should get the values 20.59 and 10.07.

Part 2:
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:

Each time a context switch occurs, the context switch time must be added to the waiting time of each process in the ready queue. In Part 1, you calculated the average number of processes in the ready queue. Find out the number of context switches for each of the two runs in Part 1. This is given in the first table of data under one of the Entries columns. The number of times processes enter the CPU is the number of context switches.

• Let the context switch time be x.
• If there are n context switches and the load average is L, the total waiting time due to context switches is nxL.
• Set this equal to 10 percent of the total waiting time and solve for x.

Part 3:
Start by copying the files from assign2/main into two new directories, assign2/part3b and assign2/part3c. You will modify these files to do a new experiments.

1. Think about how the average waiting time depends on the quantum. When the quantum is large, RR behaves like FCFS. In the original example from class, RR had a better average waiting time than FCFS.
   1. Under what conditions will the average waiting time decrease with decreasing quantum?
   2. Under what condition will the average waiting time increase with decreasing quantum?
   In the next two parts you will design experiments which will support your statements.
   
2. Design an experiment in which will support your first statement in part 3a. Put this in assign2/part3b. The experiment must use at least 20 processes, and the average waiting time for RR should decrease as the quantum is decreased starting with the largest CPU burst. Choose parameters so that the load average is at least 1.0 and the CPU utilization is at least 50%. Write a paragraph describing what your experiment does and how it relates to your first statement in Part 3a. Do 5 runs with different values of the quantum. Run the experiment and create a log file. The log file should contain a table of the data generated by the simulator.
3. Redo Part 3b for your second statement in Part 3a. Put this in assign2/part3c. That is, design an experiment in which the average waiting time for RR increases as the quantum is decreased from the largest CPU burst. The constraint on the parameters is the same as in Part 3b. Write a paragraph describing what your experiment does and how it relates to your second statement in Part 3a. Run the experiment and create a log file. The log file should contain a table of the data generated by the simulator.
4. One disadvantage of RR with a small quantum is that it requires additional context switches. For your experiment in Part 3b, the average waiting time seemed to decrease as the quantum decreased, but the number of context switches increased. For your experiment in Part 3b, calculate the context switch time that would make the average waiting time for your run with the largest quantum to be the same as that for the smallest quantum. Show your calculations including the formulas you used and the values put into the formula. How does the value obtained compare to the smallest quantum you used?

Handing in your assignment
Use this cover sheet. Consecutively number all of the other pages you turn in except for the log file from Part 3. Do the calculations for 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 answers for Part 3a, Part 3c and Part 3d. Include copies of your .run and .exp files. Write out a description of your experiments in Parts 3b and 3c and describe to what extent your results support your statements in Part 3a.

If you have a machine at home with Java installed, you can run the simulator at home by downloading the simulator code. You must have version 1.052 of the simulator or later. If you have an earlier version, you should update it. Click here for more details.