OS- SJF,SRT and HRN Scheduling


Shortest-job-first(SJF) is a non preemptive scheduling discipline in which the waiting job with the smallest estimated run-time to completion is run next. SJF reduces average waiting time over FIFO. SJF favors short jobs at the expense of longer ones. SJF selects jobs for service in a manner that ensures the next job service in a manner that ensures the next job will complete and leave the system as soon as possible. This tends to reduce the number of waiting jobs, and also reduces the number of jobs waiting behind large jobs. The obvious problem with SJF is that it requires precise knowledge of how long a job of process will run, and this information is not usually available. The best SJF can do is to rely on user estimates of run times.

If users know that the system is designed to favor jobs with small estimated run-times they may give small estimates. The scheduler can be designed to remove this temptation. The user can be forewarned that if the job runs longer than estimated, it will be terminated and the user will be charged for the work. A second option is to run the job for the estimated time plus a small percentage extra, and then to shelve it ie., preserve it in its current form so that it can be restarted at a later time. Another solution is to run the job for the estimated time at normal billing rates, and then to charge a premium rate, well above the normal charges, for additional execution time. SJF is nonpreemptive and thus not useful in timesharing environments in which reasonable response times must be guaranteed.

Shortest-Remaining-Time Scheduling(SRT) is the preemptive counterpart of SJF and is useful in timesharing. In SRT, the process with the smallest estimated run-time to completion is run next, including new arrivals. In SJF, once a job begins executing, it runs to complete. In SRT a running process may be preempted by a new process with a shorter estimated run-time. SRT has higher overhead than SJF. It must keep track of the elapsed service time of the running job, and must handle occasional preemptions. Arriving small processes will run almost immediately. SRT requires that elapsed service times be recorded , and this contribution to the schemes overhead.

Suppose a running job is almost complete, and a new job with a small estimated service time arrives. Should the running job be preempted? The pure SRT discipline would perform the preemption, but is it really worth it? This situation may be handled by building threshold value so that once a running job needs less than this amount of time to complete, the system guarantees it will run to completion uninterrupted.


Brinch Hansen developed the highest-response-ratio-next strategy that correct some of the weaknesses in SJF, particularly the favor toward short new jobs. HRN is a nonpreemptive scheduling discipline in which the priority of each job is a function not only of the jobs service time but also of the amount of time the jobs has been waiting for service. Dynamic priorities in HRN are calculated according to the formula. priority= (time waiting +service time)/service time
Share this article :
Copyright © 2012. Best Online Tutorials | Source codes | Programming Languages - All Rights Reserved