On a uniprocessor, it is apparently optimal to schedule jobs that take less time first assuming non-preemptive scheduling - once a job runs, it must finish. Why?
I am confused about how the ordering would change the overall latency. Since a uniprocessor can only take on a single process at a time, wouldn't the latency be the same regardless of order?
The measure of how good scheduler is would be average/total wait.
Assume you have a set of jobs J, within these you have job x which is the longest. Let y be any other job.
If you put x last, total wait time of the jobs executed before will be total(J)-time(x), while for any other it'll be total(J)-time(y). Thus only putting the longest job last minimizes wait time. Then you repeat that for set of remaining jobs J-{x}, and so on recursively, always putting longest one last. End result is, that you have them ordered from shortest to longest.
If the short job (A) runs before the long job (B), then A has to wait only its own length for completion, while B has to wait its own length + the length of A. If B goes first, it has to wait only its own length, but A has to wait the entire length of B plus its own. In other words, you have a total wait time of 2B+A rather than 2A+B. Since the denominator is 2 in either case, the former solution is better. That's all there is to that rule.
Although this algorithm was designed to provide maximum throughput in all the scenarios, this is not correct for all situations. What if the processor has a lot of small processes? It will definitely lead to starvation. The turnaround time of small processes will be low, whereas that of large processes will be large as compared to other scheduling algorithms.
Wikipedia says:
Since turnaround time is based on waiting time plus processing time, longer processes are significantly affected by this. Overall waiting time is smaller than FIFO, however since no process has to wait for the termination of the longest process.
If you schedule larger jobs first, lots of small processes would have to wait for the process to terminate (as this is non-preemptive). And since turnaround time is total time between submission of a process and its completion, this would definitely be low. But in SJF, very few large processes wait for some small processes, so turnaround time of only those large processes would be affected.
Check out this link for a comparison of various techniques.
