Process Schedule Log generated Wed Feb 25 09:44:10 CST 1998

Note: This log has been modified from the original. Extraneous data has been removed to save paper.
Group data for 4 groups follows:


 Process Group: demo1
Constant CPU burst, negligible I/O
duration: constant 500.00
cpu burst: constant 50.00
io burst: constant 1.00
priority: 1.00


 Process Group: demo2
Uniform CPU burst, negligible I/O
duration: constant 500.00
cpu burst: uniform 40.00 to 60.00
io burst: constant 1.00
priority: 1.00


 Process Group: demo3
Uniform CPU burst, negligible I/O
duration: constant 500.00
cpu burst: uniform 10.00 to 90.00
io burst: constant 1.00
priority: 1.00


 Process Group: demo4
Uniform CPU burst, negligible I/O
duration: constant 500.00
cpu burst: uniform 49.00 to 51.00
io burst: constant 1.00
priority: 1.00


Hypothesis: FCFS and SJF should be identical when the cpu burst times are constant. As the variation in CPU burst times increases, SJF should have a shorter average waiting time.

We start by running 20 processes with each algorithm. The CPU burst time is 50 in each case and the total running time is 500. The processes do a minimal amount of I/O after each CPU burst.

Scheduling: FCFS

Wed Feb 25 09:44:42 CST 1998

Creating processes from demo1.create

creates one type of process with negligible I/O
Creating 20 processes from demo1 with first arrival time 0
Arrival Time Distribution: constant 0.00

Reset

Scheduling: SJF

Wed Feb 25 09:45:02 CST 1998

Creating processes from demo1.create

creates one type of process with negligible I/O
Creating 20 processes from demo1 with first arrival time 0
Arrival Time Distribution: constant 0.00
Wed Feb 25 09:45:13 CST 1998

Ratio of CPU Time to Ready Time Plus CPU Time



Description Algorithm Time Processes Finished CPU Utilization Throughput Turnaround Time Waiting Time
demo1 FCFS 10000.00 20 20 1.00000 .002000 9525.00 9016.00
demo1 SJF 10000.00 20 20 1.00000 .002000 9525.00 9016.00




Turnaround Time Waiting Time
Description Algorithm Average Minimum Maximum SD Average Minimum Maximum SD
demo1 FCFS 9525.00 9050.00 10000.00 288.31 9016.00 8541.00 9491.00 14.42
demo1 SJF 9525.00 9050.00 10000.00 288.31 9016.00 8541.00 9491.00 14.42

So far our hypothesis is confirmed. For constant CPU burst time FCFS and SJF give identical results.

Now we try a similar set of processes with a variance of CPU burst times. Each time the process is scheduled for the CPU, it chooses a CPU burst time from a uniform distribution between 40 and 60. The mean is the same as in the previous runs.

Reset

Scheduling: FCFS

Wed Feb 25 09:46:15 CST 1998

Creating processes from demo2.create

creates one type of process with negligible I/O
Creating 20 processes from demo2 with first arrival time 0
Arrival Time Distribution: constant 0.00

Reset

Scheduling: SJF

Wed Feb 25 09:46:37 CST 1998

Creating processes from demo2.create

creates one type of process with negligible I/O
Creating 20 processes from demo2 with first arrival time 0
Arrival Time Distribution: constant 0.00

Wed Feb 25 09:48:06 CST 1998

Ratio of CPU Time to Ready Time Plus CPU Time





Description Algorithm Time Processes Finished CPU Utilization Throughput Turnaround Time Waiting Time
demo1 FCFS 10000.00 20 20 1.00000 .002000 9525.00 9016.00
demo1 SJF 10000.00 20 20 1.00000 .002000 9525.00 9016.00
demo2 FCFS 10000.00 20 20 1.00000 .002000 9725.53 9216.18
demo2 SJF 10002.00 20 20 .99980 .002000 6710.54 6201.14






Turnaround Time Waiting Time
Description Algorithm Average Minimum Maximum SD Average Minimum Maximum SD
demo1 FCFS 9525.00 9050.00 10000.00 288.31 9016.00 8541.00 9491.00 14.42
demo1 SJF 9525.00 9050.00 10000.00 288.31 9016.00 8541.00 9491.00 14.42
demo2 FCFS 9725.53 9156.71 10000.00 255.59 9216.18 8647.71 9490.00 12.76
demo2 SJF 6710.54 2512.32 10002.00 2300.31 6201.14 2002.32 9493.00 115.02

We see that the average waiting time for SJF is about 30 percent smaller than that for FCFS.

Now we expect that the difference between the two algorithms show grow as we increase the variance in the CPU times.

The next runs use CPU burst times from a uniform distribution from 10 to 90. Again this has the same mean as before.

Scheduling: FCFS

Reset


Reset

Scheduling: FCFS

Wed Feb 25 09:48:26 CST 1998

Creating processes from demo3.create

creates one type of process with negligible I/O
Creating 20 processes from demo3 with first arrival time 0
Arrival Time Distribution: constant 0.00
Scheduling: SJF

Reset


Wed Feb 25 09:48:43 CST 1998

Creating processes from demo3.create

creates one type of process with negligible I/O
Creating 20 processes from demo3 with first arrival time 0
Arrival Time Distribution: constant 0.00

Wed Feb 25 09:48:54 CST 1998

Ratio of CPU Time to Ready Time Plus CPU Time







Description Algorithm Time Processes Finished CPU Utilization Throughput Turnaround Time Waiting Time
demo1 FCFS 10000.00 20 20 1.00000 .002000 9525.00 9016.00
demo1 SJF 10000.00 20 20 1.00000 .002000 9525.00 9016.00
demo2 FCFS 10000.00 20 20 1.00000 .002000 9725.53 9216.18
demo2 SJF 10002.00 20 20 .99980 .002000 6710.54 6201.14
demo3 FCFS 10000.00 20 20 1.00000 .002000 9036.72 8527.27
demo3 SJF 10005.00 20 20 .99950 .001999 6889.73 6380.23








Turnaround Time Waiting Time
Description Algorithm Average Minimum Maximum SD Average Minimum Maximum SD
demo1 FCFS 9525.00 9050.00 10000.00 288.31 9016.00 8541.00 9491.00 14.42
demo1 SJF 9525.00 9050.00 10000.00 288.31 9016.00 8541.00 9491.00 14.42
demo2 FCFS 9725.53 9156.71 10000.00 255.59 9216.18 8647.71 9490.00 12.76
demo2 SJF 6710.54 2512.32 10002.00 2300.31 6201.14 2002.32 9493.00 115.02
demo3 FCFS 9036.72 7263.20 10000.00 782.65 8527.27 6757.20 9487.00 39.04
demo3 SJF 6889.73 2881.04 10005.00 2109.61 6380.23 2371.04 9498.00 105.51

Wed Feb 25 09:48:54 CST 1998

Reset

Scheduling: FCFS
This result was unexpected. The difference between the two algorithms did not increase and in fact decreased a bit.

Now we will try an experiment with a very small variance. The CPU burst time varies uniformly between 49 and 51.


Wed Feb 25 09:49:58 CST 1998

Creating processes from demo4.create

creates one type of process with negligible I/O
Creating 20 processes from demo4 with first arrival time 0
Arrival Time Distribution: constant 0.00

Quantum changed to 1.1

Reset

Scheduling: SJF

Wed Feb 25 09:50:09 CST 1998

Creating processes from demo4.create

creates one type of process with negligible I/O
Creating 20 processes from demo4 with first arrival time 0
Arrival Time Distribution: constant 0.00
Wed Feb 25 09:50:16 CST 1998

Ratio of CPU Time to Ready Time Plus CPU Time









Description Algorithm Time Processes Finished CPU Utilization Throughput Turnaround Time Waiting Time
demo1 FCFS 10000.00 20 20 1.00000 .002000 9525.00 9016.00
demo1 SJF 10000.00 20 20 1.00000 .002000 9525.00 9016.00
demo2 FCFS 10000.00 20 20 1.00000 .002000 9725.53 9216.18
demo2 SJF 10002.00 20 20 .99980 .002000 6710.54 6201.14
demo3 FCFS 10000.00 20 20 1.00000 .002000 9036.72 8527.27
demo3 SJF 10005.00 20 20 .99950 .001999 6889.73 6380.23
demo4 FCFS 10000.00 20 20 1.00000 .002000 9750.20 9240.70
demo4 SJF 10003.00 20 20 .99970 .001999 6869.42 6360.07










Turnaround Time Waiting Time
Description Algorithm Average Minimum Maximum SD Average Minimum Maximum SD
demo1 FCFS 9525.00 9050.00 10000.00 288.31 9016.00 8541.00 9491.00 14.42
demo1 SJF 9525.00 9050.00 10000.00 288.31 9016.00 8541.00 9491.00 14.42
demo2 FCFS 9725.53 9156.71 10000.00 255.59 9216.18 8647.71 9490.00 12.76
demo2 SJF 6710.54 2512.32 10002.00 2300.31 6201.14 2002.32 9493.00 115.02
demo3 FCFS 9036.72 7263.20 10000.00 782.65 8527.27 6757.20 9487.00 39.04
demo3 SJF 6889.73 2881.04 10005.00 2109.61 6380.23 2371.04 9498.00 105.51
demo4 FCFS 9750.20 9046.22 10000.00 315.68 9240.70 8537.22 9490.00 15.76
demo4 SJF 6869.42 2947.06 10003.00 2215.88 6360.07 2437.06 9494.00 110.80

This is a surprise. We expected very little difference between FCFS and SJF when the variation in CPU burst time was small. In fact we found that any variance in the CPU burst times causes a large difference in these algorithms.

The explanation is simple (and obvious, once you think about it correctly. If a process gets a relatively large CPU burst near the beginning of its execution it will stay in the ready queue until all other processes have finished execution. This is because we chose to have very small I/O time and so there are always a lot of ready processes. With no aging, once a process has a long CPU burst, it can be delayed indefinitely (starvation). Since we have only 20 processes, the delay is bounded, but still large.

Detailed analysis of the processes shows that one process had a CPU burst of 50.69 followed by a CPU burst of 50.98. Since the maximum possible CPU burst in this run is 51, this process had to wait until all other processes completed and was the last to finish.

Process Schedule Log completed Wed Feb 25 09:51:00 CST 1998