CS 3733 Operating Systems, Fall 1998 Assignment 2 Comments

Part 1

Because the number of processes times the average CPU burst is smaller than the typical I/O burst, it will be rare that the ready queue will contain more than one process, as shown by the low CPU utilization and the small average waiting time which is less than half of the average total CPU time.

Part 2

Notice that the longer processes all arrive first and so one of these starts executing immediately. Under SJF, this one is allowed to finish its CPU burst of 100 and all of the short processes need to wait for this length of time. Under PSJF, this long-burst process is kicked out of the CPU which the short processes arrive and so the short processes only have to wait for each other. This is why PSJF has such a short waiting time compared to SJF.

The CPU utilization is almost the same (and fairly high) for all of the algorithms because the number of processes times the average CPU burst is about equal to the average I/O burst. Notice that FCFS has a slightly higher CPU utilization than SJF and FCFS. This is not because of the context switch time or the overhead of the algorithm, as the simulator does not take these into account. With SJF and PSJF, the shorter-burst processes finish early, leaving fewer processes to keep the CPU busy at the end of the run.

Part 3

In general, SJFA will work well (close to SJF) when the CPU bursts of a given process are all near each other. This allows the algorithm to predict the next burst based on the previous ones. If the bursts come from a distribution, there is no relationship between the various bursts and so SJFA will not do well. However, if the processes form two groups whose CPU bursts come from distributions with different means, SJFA can distinguish between these as long as these distributions have little overlap. This will allow the short bursts to be executed before the long ones, but will not be able to distinguish among processes with the same distribution.

Also, in order for SJFA to work well, each process needs to have a large number of CPU bursts. Since the initial approximation is always 0, it may take several bursts before SJFA can approximate the mean. The number of bursts needed will depend on alpha.

For the types of processes that can be used by this simulator, the value of alpha is usually not critical except for the extreme values of 0 and 1, and when the number of CPU bursts is small.

Common Mistakes

• The simulator does not count context switch times.
• It is the CPU burst, and not the duration of the process that has a direct effect on the algorithms.
• SJF does not make more efficient use of the CPU to produce lower waiting times. Efficient use of the CPU refers to CPU utilization, and often SJF has a poorer CPU utilization than FCFS.
• Do not make a statement like "CPU utilization and turnaround time are bad." This does not mean much unless you are comparing these to something. Usually, the CPU utilization depends mainly on the number of processes and their relative CPU and I/O bursts. This is not under the control of the OS designer. In some ways, one of the goals of a computer system design is to keep the CPU utilization low. This gives a better response time.
• When designing an experiment, if all processes have the same distribution of CPU burst times and each process has a large number of CPU bursts, all of the processes will behave similarly. Each process will have some short bursts and some long bursts. With an exponential distribution it is more likely that a few processes will have an unusually long burst. In cases where the ready queue always has more than one process, these processes will be starved out for a long time under SJF.
• When making runs using different algorithms with processes whose properties come from distributions, two runs may be based on sets if processes with very different properties because of the statistical variation of the distributions between runs. The simulator eliminates this when you specify a seed, but keep in mind that a single run with a small number of processes may not behave the same as additional runs using different seeds.
• As explained above, CPU utilization under different algorithms using the simulator cannot be explained by the overhead of the calculations that the algorithm requires.
• When two values differ by a few percent in different runs, you should not make a statement that one is better than the other. The correct conclusion is that the difference is not statistically significant.
• Don't use the word "because" when you mean "and."
• Don't make statements such as the "turnaround time is large." It only makes sense to talk about turnaround time (or many other measured parameters) when comparing it to something, usually a different run.
• When the CPU bursts are given by a distribution, there is no relationship between consecutive bursts other than that they come from the same distribution. The value of the previous burst only gives information about the type of distribution it was chosen from.
• Many chose experiments in which there were only one or two CPU bursts per processes. SJFA will perform like FCFS with these.
• Do not try to do a bar graph of 10 simultaneous runs. Three or four should be the maximum.
• Waiting time reflects time spent in the ready queue, not time waiting for I/O.
• Don't say that one algorithm is more fair than another unless you are going to say what you mean by the word fair.
• true or False: IF all processes have the same constant CPU burst time, then SJF and FCFS will have the same behavior.