Explain the following scheduling algorithms (Shortest Job First (SJF) & Shortest Remaining Time (SRT))

1. Shortest Job First (SJF)

 

• Other name of this algorithm is Shortest-Process-Next (SPN).
• Shortest-Job-First (SJF) is a non-preemptive discipline in which waiting job (or process) with the smallest estimated run-time-to-completion is run next. In other words, when CPU is available, it is assigned to the process that has smallest next CPU burst.
• The SJF scheduling is especially appropriate for batch jobs for which the run times are known in advance. Since the SJF scheduling algorithm gives the minimum average time for  a given set of processes, it is probably optimal.
• The SJF algorithm favors short jobs (or processors) at the expense of longer ones.
• The obvious problem with SJF scheme is that it requires precise knowledge of how long a job or process will run, and this information is not usually available.
• The best SJF algorithm can do is to rely on user estimates of run times.
• In the production environment where the same jobs run regularly, it may be possible to provide reasonable estimate of run time, based on the past performance of the process. But in the development environment users rarely know how their program will execute.
• Like FCFS, SJF is non preemptive therefore, it is not useful in timesharing environment in which reasonable response time must be guaranteed.

         Scheduling

• Key concept of this algorithm is: “CPU is allocated to the process with least CPU-burst time.” Amongst the processes in the ready queue. CPU is always assigned to the process with least CPU burst requirement. If the two processes having the same length, next CPU burst, fcfs scheduling is used i.e. one which arrives first, will be taken up first by the CPU.
• This algorithm can be preemptive or non-preemptive.
• Let us consider, the following set of processes having their CPU burst time mentioned in millisecond and having arrived almost at the same time.

Process	CPU Burst Time
P1	10
P2	5
P3	2

          The Gantt chart:

shortest job first scheduling

Waiting time for P3 = 0 millisecond
Waiting time for P2= 2 millisecond
Waiting time for P1 = 7 millisecond
Average waiting time= (0+2+7) /3 = 3 millisecond

1. 2 Shortest Remaining Time (SRT)

• also known as shortest remaining time first (SRTF), is a scheduling method that is a preemptive version of shortest job next scheduling. In this scheduling algorithm, the process with the smallest amount of time remaining until completion is selected to execute. Since the currently executing process is the one with the shortest amount of time remaining by definition, and since that time should only reduce as execution progresses, processes will always run until they complete or a new process is added that requires a smaller amount of time.
• Shortest remaining time is advantageous because short processes are handled very quickly. The system also requires very little overhead since it only makes a decision when a process completes or a new process is added, and when a new process is added the algorithm only needs to compare the currently executing process with the new process, ignoring all other processes currently waiting to execute.
• Like shortest job first, it has the potential for process starvation; long processes may be held off indefinitely if short processes are continually added. This threat can be minimal when process times follow a heavy-tailed distribution.
•  Like shortest job next scheduling, shortest remaining time scheduling is rarely used outside of specialized environments because it requires accurate estimations of the runtime of all processes that are waiting to execute.

         Scheduling

• Shortest remaining time scheduling is the preemptive counter part of SJF and is useful in time sharing system. In SRT, process with the smallest estimated run time to completion is run next, in SJF once a job begin executing, it runs to completion. In SRT a running process may be preempted by a user process with a shorter estimated run time.
•  Consider an example, where three processes arrived in the order P1, P2, P3 at the time mentioned below, and then the average waiting time using SJF scheduling algorithm will be calculated as:

Process	CPU Burst Time	Time of Arrival
P1	10	0
P2	5	1
P3	2	2

 

          The Gantt chart:

• In this, the CPU will be taken away from the currently executing process whenever a process will less CPU burst time.
• As shown in figure, the time when P2 arrives P1 needs 9 millisecond more to finish. As B’s cpu burst in 5 millisecond < 9 millisecond, therefore, P1’s execution will be preempted and P2 will be executed but against as P3 arrives P2’s execution needs 3 more millisecond where as P3 needs only 2 millisecond to execute, thus P3 takes over P2 and so on. 

shortest job first scheduling

 

 Waiting time for P1 = 0+ (8-1) = 7 millisecond
Waiting time for P2 = 1+ (4-2) = 3 millisecond
Waiting time for P3 = 2 millisecond
Average waiting time = (7+3+2) / 3 = 4 millisecond