Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
add comment

3 Answers

up vote 2 down vote accepted

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.

share|improve this answer
    
Thanks, by starvation in your paragraph 1, do you mean that a single long process might have to wait for many short processes and thus not run until a very long time (after they all finish)? –  David Faux Jan 17 '12 at 4:09
1  
Yes, starvation means a process is waiting to be executed, but it isn't able to get enough resources for its execution. Take for example a case in which you have 4 processes that execute in 5 secs, and 1 process that executes in 20 secs. Suppose that they arrive at the same time. In SJF, the waiting times for would be 0, 4, 8, 12 and 16. But if the longer process would have been executing first, the waiting times would be 0 (for the large process) and 20, 24, 28 and 32 for the smaller processes. –  c0da Jan 17 '12 at 4:20
add comment

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.

share|improve this answer
    
@Killan, could you please explain where do you get the (2) from? Let us say you have to identical machines with jobs A and B. On 10:00. Assume that Job A takes 5 minutes to complete. Assume that B takes 55 minutes to complete. You start machine 1 with schedule A then B and you start machine 2 with Schedule B then A. Are you saying that machine1 will take 2*5+55 = 1:05 minutes to finish and machine 2 will take 2*55+5=115 minutes to complete? –  Emmad Kareem Jan 17 '12 at 10:10
    
No, not at all. The point is that the average waiting time for the customer, i.e. the guy submitting the job, is longer. The computer doesn't care in what order it does things, but the human before the counter cares how long they have to wait until they can go home! By 'total wait time' I mean the person-hours wasted by standing in front of the counter. –  Kilian Foth Jan 17 '12 at 10:18
    
OK, thanks for your reply. –  Emmad Kareem Jan 17 '12 at 10:30
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.