Prove that the SPF strategy is optimal in the sense that it minimizes average response times. [Hint: Consider a list of processes each with an indicated duration. Pick any two processes arbitrarily. Assuming that one is larger than the other, show the effect that placing the smaller process ahead of the longer one has on the waiting time of each process. Draw an appropriate conclusion.]

What will be an ideal response?

As per the problem statement, pick any two processes that are to be run consecutively. Suppose they run for t1 and t2 time units, respectively. Suppose t1 is greater than t2. If the processes run in t1 then t2 order, the response time of the first process is t1 and of the second is t1 + t2, so the average response time is (2 × t1 + t2)/2. If the processes are run in t2 then t1 order, then the response time of the first process is t2 and of the second is t2 + t1, so the average response time is (2 × t2 + t1)/2 which is smaller because t2 is smaller than t1. Applying this argument repeatedly to adjacent pairs of processes yields the result that SPF is optimal in giving the smallest average response times. But it does this, of course, to the detriment of longer processes.