Question

Describe how the Shortest Job First (SJF)Scheduling algorithm works. Explain the differences of working procedure between preemptive and non-preemptive version of this algorithm.

Answer 1

We use Shortest Job First (SJF)Scheduling algorithm to take care of order in which processes will be scheduled onto the CPU . In this algorithm process having shortest burst time will get The CPU first to complete itself. It significantly reduces the average waiting time for other processes awaiting execution

There are two Types

1. Non Pre-Emptive

2. Pre- Emptive

In Non -Preemptive approach once any process is scheduled onto to the CPU then it can be pre-empt in between in other words process will leave CPU only when it has completed its burst time or entered into waiting state and till that Time other processes have to wait .

In Pre-Emptive Approach once any process is scheduled onto to the CPU and while it is a executing if any new process with shorter burst time came then current process is pre-empted and new process will be scheduled onto the CPU .

Lets see Working of both with help a example

For example we have three processes P1 ,P2 and P3 with Burst Time as 20 , 7,3 and Arrival time as 0 , 5, 2

Using Non pre-emptive

1. As process P1 has arrived first at T=0 so it will get the CPU and it starts running

2. At T = 2 Process P3 arrives and it has shorter burst time than P1 as Left over Burst Time of P1 is 18 > 3 . But as we using non - preemptive approach so it has to wait until P1 ends

3. At T = 5, P2 also arrives and face same issue as P3

4. At T= 20 P1 ends and both P2 and P3 are waiting in queue But according to SJF Burst Time P3 < Burst Time P2 . So P3 will be scheduled first.

5 Then at last P2 is scheduled

This is how process execution will take place when we use non-preemptive method

Problem is : If at start only any longer process is scheduled then all the shorter process that came after it have to wait until it ends . This can cause problem of starvation for smaller processes

So we have Pre-Emptive Approach

1. Here when At T = 2 Process P3 arrives and it has shorter burst time than P1 . So P1 is pre-empted and P3 is scheduled onto the CPU and P1 wait in Queue

2. At T=4 P3 completes and in queue Only P1 is there so it gets the CPU back

3. Again At T=5 P2 arrived and it has shorter burst time than P1 .So again P1 gets pre-empted and P2 is scheduled onto the CPU and P1 wait in Queue

4. At last P1 get completes as no other shorter processes arrives

This is how working is done in pre-emptive One . Here also we can have starvation as if shorter process keep on coming back to back then longer processes will not get chance to get the CPU and they have to wait for long time to run itself .

Hence we say SJF has problem of starvation. And SJF is better if we know Burst Time of processes before hand .

Hence we saw The SJF working in Both Pre-Emptive and Non- Preemptive Manner and how process scheduling is done in SJF

If u like the answer do Upvote it and have any doubt ask in comments

Thank You