Shortest Job First Scheduling algorithm | Preemptive and Non-Preemptive Scheduling

Shortest Job First Scheduling algorithm | Preemptive and Non-Preemptive Scheduling | SJF Scheduling

Shortest Job First (SJF) is an algorithm in which the process having the smallest execution time is chosen for the next execution. There are basically two types of SJF methods:

Non-Preemptive SJF
Preemptive SJF

Non Pre-emptive Shortest Job First:-

We have taken 5 processes P1,P2,P3,P4,P5 available in the ready queue for execution, with arrival time t= 0 for all and given burst times.

CPU Scheduling Example-Shortest Job First Algorithm

Gaint Chart:-

Average Waiting Time:-(15+2+9+5+0)/5=6.2

Problem with Non Pre-emptive SJF (Starvation Problem):-

If the arrival time for processes are different, which means all the processes are not available in the ready queue at time t= 0, and some jobs arrive after some time, in such situation, sometimes process with short burst time have to wait for the current process's execution to finish, because in Non Pre-emptive SJF, on arrival of a process with short duration, the existing job/process's execution is not stopped to execute the short job first. This leads to the problem of Starvation, where a shorter process has to wait for a long time until the current longer process gets executed. we can understand this Process by using Following Example

CPU Scheduling Example-Shortest Job First Algorithm-Starvation

Here At t=0, Process P1 start Executing , since it is a non preemptive Algorithm no process will run untill Process Completes its Execution. after the time t=4 the processes P2,P3,P4 will wait for completion of Process P1.

Solution of Starvation Problem:-

this can be solved using the concept of aging (a technique of increasing the priority of processes that wait in the system for a long time.).

Pre-emptive Shortest Job First

In Preemptive SJF Scheduling, jobs are put into the ready queue as they come.
A process with shortest burst time begins execution.
If a process with even a shorter burst time arrives, the current process is removed or preempted from execution, and the shorter job is allocated CPU cycle.

Step-1:- at time t=0

Ready queue:- P1(16)

Step-2 At Time=1

Ready queue:- P1(15) , P2(5)

At Time=2

Ready Queue P1(15) , P2(4),P3(6)

Step-3 At Time t=3

Ready queue:- P1(15) , P2(3),P3(6),P4(1)

Step-4 At Time t=4

Ready queue:- P1(15) , P2(3),P3(6),P5(2)

Step-5 At Time t=6

Ready queue P1(15) , P2(3),P3(6)

Step-6 At Time t=9

Ready queue:- P1(15) , P3(6)

Step-7 At Time t=15

Ready queue:- P1(15)

Turn around Time:-

It is the time interval from the time of submission of a process to the time of the completion of the process.
TAT=Completion Time – Arrival time

Waiting Time:-

The time spent by a process waiting in the ready queue for getting the CPU.

Waiting time=Turn Around Time-Burst Time

Average waiting Time = (14+3+7+0+0)/5

= 24/5

=4.8

Average turn around Time = (30+8+13+1+2)/5

=10.8

This scheduling algorithm is optimal if all the processes are available at the same time.

Disadvantages of SJF:-

To successfully implement it, the burst time/duration time of the processes should be known to the processor in advance, which is practically not feasible all the time.
This algorithm may cause very long turnaround times or starvation.

Ask question #Pywix

Facebook Page :- https://www.facebook.com/rgrahulgarg786
Twitter :- https://twitter.com/rgrahulgarg786
Instagram:- https://www.instagram.com/rahulgupta.786/
youTube:- https://www.youtube.com/pywixclasses
Please Like, Comment, Share and Subscribe THANK YOU!

IN-FEED-AD

Shortest Job First Scheduling algorithm | Preemptive and Non-Preemptive Scheduling | SJF Scheduling