CS 3733 Operating Systems, Spring 2005 Assignment 2

Due Friday, March 4

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.

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:

Think about the conditions under which preemptive shortest job first performs much better than the non-preemptive version. Write a statement describing these conditions.

Part 3b:

Design an experiment in which PSJF performs much better than SJF. The experiment should have 2 runs which differ only in the scheduling algorithm. Try to design an experiment with the following characteristics:
• At least 10 processes are used, each having many CPU bursts.
• The average waiting time for SJF is at least twice that of PSJF.
• The CPU utilization is between 50 and 90 percent.
• The load average is greater than 1.
Run the experiment using the simulator. Create a log file containing the tabular data and Gantt charts for the two runs. Turn in the log file and copies of your run and exp files. Calculate the load average for your experiment.

If you did the experiment according to the specifications, the simulator shows that PSJF has a shorter waiting time than SJF for these processes. However, the simulator does not take into account the context switch time and PSJF has more context switches than SJF.

For very long context switch times, it is possible that SJF would have a shorter average waiting time. Calculate the context switch time that would make your two runs have the same average waiting time. Use the method of Part 2.

Part 3d:

Suppose you or some other student doing this part gets a negative time for the calculation in Part 3c. Is this possible? What does it mean?

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 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 answers for 3a, 3c, and 3d. 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 3b on the answer sheet. Include copies of your .run and .exp files. Write out a description of your experiment in Part 3 and describe to what extent your results satisfied the requirements.

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.056 of the simulator or later. If you have an earlier version, you should update it. You will need the 5 files from this directory. Put all of the files in a single directory and execute runps in a command window to run the simulator.