##### SJF scheduling

Shortest-Job-First(SJF) Scheduling

• Best approach to minimize waiting time.
• Actual time taken by the process is already known to processor.
• Impossible to implement.
• example:-

In Preemptive Shortest Job First Scheduling, jobs are put into ready queue as they arrive, but as a process with short burst time arrives, the existing process is preempted.

#### Contributor's Info

Created:
##### Shortest Job First Scheduling Algorithm(preemptive and non- preemptive)

Shortest Job First Scheduling Algorithm(non- preemptive): SJF is based on prediction of burst time. SJF schedules a process with smallest burst time. In simple words, this algorithms executes process with their increasing order of CPU burst time. If all processes are having same CPU burst time then this works as FCFS algorithm. SJF minimizes average waiting time, however it’s hard to predict CPU burst time in advance.

Example: Consider the following table:

 Process no. Arrival Time Burst Time P1 0 6 P2 2 1 P3 4 4 P4 5 3

Find the average waiting time and average turn arround time using SJF(non-preemptive) algorithm?

Solution:  Using SJF(non-preemptive) algorithm, gantt chart is:

Therefore,

 Waiting Time Turn around Time Completion Time Process No. Arrival Time Burst Time 6 - 6 = 0 6 - 0 = 6 6 P1 0 6 5 - 1 = 4 7 - 2 = 5 7 P2 2 1 9 - 4 = 5 14 - 5 = 9 14 P3 5 4 4 - 3 = 1 10 - 6 = 4 10 P4 6 3

So,

Average Turn arround time  = (6 + 5 + 9 + 4) / (4) = 6

Average Waiting time = (0 + 4 + 5 + 1) / (4) = 2.5

Shortest Remaining Time First(SRTF) algorithm: This is preemptive version of shortest job first algorithm.  It’s minimize average turn arround time. If all processes are arrived at same time, then it works as SJF.

Example: Consider the following table:

 Process no. Arrival Time Burst Time P1 0 6 P2 2 1 P3 4 4 P4 5 3

Find the average waiting time and average turn arround time using SRTF(preemptive) algorithm?

Solution: Using SRTF(non-preemptive) algorithm, gantt chart is:

Therefore,

 Waiting Time Turn around Time Completion Time Process No. Arrival Time Burst Time 7 - 6 = 1 7 - 0 = 7 7 P1 0 6 1 - 1 = 0 3 - 2 = 1 3 P2 2 1 9 - 4 = 5 14 - 5 = 9 14 P3 5 4 4 - 3 = 1 10 - 6 = 4 10 P4 6 3

So,
Average Turn arround time  = (7 + 1 + 9 + 4) / (4) = 5.25

Average Waiting time = (1 + 0 + 5 + 1) / (4) = 1.75

Created: