CS 3733 Operating Systems, Spring 2006 Assignment 2

Due Friday, March 10

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 on the Sun or 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 new 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 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 a new directory, assign2/part3. You will modify these files to do a new experiment.

Part 3a: In a time-sharing system, each process looks as if it has exclusive access to the CPU, but the CPU may seem to be slower than it actually is because of competition with other processes. Consider the following statement:

If 20 similar processes are scheduled using Round Robin with a small enough quantum, the result for one of the processes is similar to running it on a non-timesharing system with no other processes, but using a CPU that is 20 times slower.

Write a few sentences indicating whether you agree or disagree with this statement. Assume that the time to do the scheduling and the context switch can be ignored. Put your answer on the back of the cover sheet.

Part 3b:

Think about what it would mean to test the statement in Part 3a using a simulator. Answer the following questions on the back of the cover sheet.

1. To what value would you compare the quantum to know if it is small enough?
2. Which simulator parameters need to change to simulate a CPU that is 20 times slower?
3. What can you say about the average waiting time when there is only one process?
4. Which performance measurements would you use to test the statement in Part 3a?

Part 3c
Use the simulator to perform an experiment to back up your what you said about the statement in Part 3a. In one run you should have a single process. You can use the FCFS scheduling algorithm which will always schedule the process for its full CPU burst. In other runs use Round Robin with 20 processes and make the quantum smaller and smaller. Compare the results.

Create a log file containing tabular data and Gantt charts. Write a paragraph explaining what your experiment does and how well it supports what you wrote in Part 3a. Be specific and refer to numbers given in your tables or to the Gantt charts.

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

Write your answers to Part 3a and Part 3b on the cover sheet. Put your paragraph for Part 3c on a separate page. The answer to Part 3c should be typed rather than hand-written. You do not need to use a word processor. Just type it in using an editor and print it out.

Note: Make sure that your log file contains tabular data for all of your runs.

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 the latest version of the simulator, version 1.081 or later. If you have an earlier version, you should update it. You can get the current version of the simulator here. Unzip the files in a single directory and execute runps in a command window to run the simulator.