CS 3733 Operating Systems, Spring 2004 Assignment 2
Was due Thursday, February 19, 2004, now due Tuesday, February 24
Due to change in the due date, all assignments must be handed in by the
start of class on Feb. 24.
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/rec02 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 2.
Calculate the load average for each of the two runs. Show how you got your
answers.
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.
You can do this by pushing the All Data button.
This puts some
data for each run in the yellow window.
The value "Times CPU Entered" is the number of times
a process enters the running state and is the number of context switches
done.
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:
- Let the context switch time be x.
- If there are n context switches and load 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.
Show this calculation for each of the two runs from Part 1.
Part 3:
Start by copying the files from assign2/main into
assign2/part3. You will modify these files to do a new experiment.
-
Think about the conditions under which preemptive shortest job first (PSJF)
will perform better than shortest job first without preemption (SJF).
The measure of performance we will use is average waiting time.
Write a statement describing these conditions in some detail.
-
Now design an experiment which will support your statement.
The experiment must use at least 20 processes, and the average waiting time
for PSJF should be at most half that of SJF. 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 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.
-
One disadvantage of PSJF is that it may require additional context
switches. If your experiment requires more context switches for PSJF,
calculate the context switch time that would cancel out the advantage that
PSJF has in your experiment. Express the answer in the time units of
the simulator.
- Another disadvantage of PSJF is that there is additional overhead each
time a process enters the ready queue while a process is running. The algorithm
needs to decide whether or not to preempt the running process. Estimate the
number of times this needs to be done in your PSJF experiment.
You can use the All Data button to display the
number of times the ready queue was entered. The calculate
the time one of these extra calculations would need to take in order to
cancel out the advantage of PSJF over SJF. Ignore the context switch time
in this calculation. Show how you got your answer.
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.
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 experiment in Part 3b and describe to what
extent your results support your statement 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.